Someone reminded me that 40 years ago, when we developed games for the Commodore-64, there were no GPUs. That 8-bit CPUs did not even have a machine instruction for multiplication. And they were dreadfully slow.<\/p>\n
Therefore, it was essential to use fast and efficient algorithms for graphics primitives.<\/p>\n
One such primitive is Bresenham’s algorithm<\/a> although back then, I didn’t know it had a name beyond being called a forward differences algorithm. It’s a wonderful, powerful example of an algorithm that produces a circle relying only on integer addition and bitwise shifts; never mind floating point, it doesn’t even need multiplication!<\/p>\n Here’s a C-language implementation for an R=20 circle (implemented in this case as a character map just for demonstration purposes):<\/p>\n And the output it produces:<\/p>\n Don’t tell me it’s not beautiful. And even in machine language, it’s just a few dozen instructions.<\/p>\n Someone reminded me that 40 years ago, when we developed games for the Commodore-64, there were no GPUs. That 8-bit CPUs did not even have a machine instruction for multiplication. And they were dreadfully slow. Therefore, it was essential to use fast and efficient algorithms for graphics primitives. One such primitive is Bresenham’s algorithm although […]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[64,36],"tags":[],"class_list":["post-11170","post","type-post","status-publish","format-standard","hentry","category-computer-games","category-programming","category-64-id","category-36-id","post-seq-1","post-parity-odd","meta-position-corners","fix"],"_links":{"self":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts\/11170","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11170"}],"version-history":[{"count":9,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts\/11170\/revisions"}],"predecessor-version":[{"id":11179,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts\/11170\/revisions\/11179"}],"wp:attachment":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}#include <stdio.h>\r\n#include <string.h>\r\n\r\n#define R 20\r\n\r\nvoid main(void)\r\n{\r\n \u00a0 int x, y, d, dA, dB;\r\n \u00a0 int i;\r\n \u00a0 char B[2*R+1][2*R+2];\r\n\r\n\u00a0 \u00a0 memset(B, ' ', sizeof(B));\r\n \u00a0 for (i = 0; i < 2*R+1; i++) B[i][2*R+1] = 0;\r\n\r\n\u00a0 \u00a0 x = 0;\r\n \u00a0 y = R;\r\n \u00a0 d = 5 - (R<<2);\r\n \u00a0 dA = 12;\r\n \u00a0 dB = 20 - (R<<3);\r\n \u00a0 while (x<=y)\r\n \u00a0 {\r\n \u00a0 \u00a0 \u00a0 B[R+x][R+y] = B[R+x][R-y] = B[R-x][R+y] = B[R-x][R-y] =\r\n \u00a0 \u00a0 \u00a0 B[R+y][R+x] = B[R+y][R-x] = B[R-y][R+x] = B[R-y][R-x] = 'X';\r\n \u00a0 \u00a0 \u00a0 if (d<0)\r\n \u00a0 \u00a0 \u00a0 {\r\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 d += dA;\r\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 dB += 8;\r\n \u00a0 \u00a0 \u00a0 }\r\n \u00a0 \u00a0 \u00a0 else\r\n \u00a0 \u00a0 \u00a0 {\r\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 y--;\r\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 d += dB;\r\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 dB += 16;\r\n \u00a0 \u00a0 \u00a0 }\r\n \u00a0 \u00a0 \u00a0 x++;\r\n \u00a0 \u00a0 \u00a0 dA += 8;\r\n \u00a0 }\r\n\r\n \u00a0 for (i = 0; i < 2*R+1; i++) printf(\"%s\\n\", B[i]);\r\n}<\/pre>\n<\/div>\n XXXXXXXXX \r\n XXX XXX \r\n XX XX \r\n XX XX \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\nX X\r\nX X\r\nX X\r\nX X\r\nX X\r\nX X\r\nX X\r\nX X\r\nX X\r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n X X \r\n XX XX \r\n XX XX \r\n XXX XXX \r\n XXXXXXXXX \r\n<\/pre>\n