11 ms·

Drawing a circle, point-by-point, without floating point support

79 points by threeme3 5y ago

dark-star 5y ago
This is how we did it on the C64, back in the 80's :-D
anlunx 5y ago
dahfizz 5y ago
> It requires only additions, subtractions and bit shifts: 2x is the same as x<<1, of course. It also requires only integer arithmetic. Does any of this mean anything in JS, where AFAIK there are no real ints? 2x is an fpu operation under the hood, and not a bit shift.
- Kranar 5y ago
  IEEE double-precision floating-point numbers can exactly represent 53-bit integers and hence they are suitable for most integer related operations (ignoring bitwise operations). For bitwise operations, JavaScript will first convert the number to a 32-bit two's complement signed integer.
  - dahfizz 5y ago
    I guess the question is really whether JS takes advantage of these facts. Will JS, at runtime, realize that X is an int and optimize 2 * X into a bit shift operation? Will JS recognize that Y and Z are perfectly represented integers stored in floats and so use integer instructions when adding Y + Z? Would such a thing even save time with all the casting back and forth to fp?
- selcuka 5y ago
  I guess JS is only used as a tool to demonstrate the algorithm.
- masswerk 5y ago
  I think, using the `(…) | 0` (expression binary ORed with zero) construct most JS engines will use true integers in optimized code.
  - ygra 5y ago
    In fact, the specification even guarantees that for all the bitwise operators.
    - masswerk 5y ago
      However, this is relatively new and there may still be some legacy engines around.
      - ygra 5y ago
        That goes back to at least ECMAScript 1 in 1997. Possibly further. Not sure there are that many legacy engines from before that still around.
        masswerk 5y ago
        Oh, I thought this came only with what was related to EMScripten before WASM (I forgot what the fast optimization standard is/was called). This took some years to propagate to all browsers. As for interpreted JS, a binary operator returns a 32-bit integer value, but it would be still stored as a Number (float). (Meaning, a | 0 => int, b = a | 0 => float stored in b, there is no other primitive numeric type. – Instead of optimizing for speed, you would be adding implicit type conversions.)
        ygra 5y ago
        Ah, now I get the confusion. Yeah, most of interpreters probably wouldn't have made the in-memory distinction between small ints and doubles. So the conversion would have to happen back and forth every time a bitwise operator would be applied. Nowadays the semantics if what happens are still the same, but things happen a bit more optimized by usually avoiding the round-trip to double when not necessary.
- xscott 5y ago
  Funny enough JavaScript now has BigInt, which is purely integer: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt#browser_compatibility https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - Someone 5y ago
    It also has typed arrays (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays https://developer.mozilla.org/en-US/docs/Web/JavaScript/Type...), but you can’t calculate with those values (you write floats into them that get rounded to integers, and values conceptually become floats when you read them) WebAssembly has i32 and i64.
- Schroedingersat 5y ago
  JS VMs have real ints (and you can summon them smi reliably usually with |0 ), but you're very much better off calling into some browser capability that will leverage the gpu most of the time.
christkv 5y ago
You can always try Bresenham’s circle drawing algorithm.
- scrubs 5y ago
  Beat me to it. And there are several optimizations on top that by, more or less, by reflecting the points as you compute one quadrant of the circle.
- gotaquestion 5y ago
  This is the era where prior art doesn't exist. Why read a book when you can blog about discovering "something new". I could probably make a killing blogging about my "discovery" of the algorithms in the book "Hacker's Delight".
  - Mr_P 5y ago
    The author titled one of the sections "Midpoint circle algorithm". There happens to be a Wikipedia page on "Midpoint circle algorithm": https://en.wikipedia.org/wiki/Midpoint_circle_algorithm https://en.wikipedia.org/wiki/Midpoint_circle_algorithm The page claims, "Bresenham's circle algorithm is derived from the midpoint circle algorithm." The author of this blog post even made it clear, at the end of their article, that... "many explanations of midpoint algorithm use the final, optimized version. But I added several unoptimized steps." I think there's a lot of value in a blogpost that demonstrates how someone could re-derive a widely-used algorithm from scratch.
  - taneq 5y ago
    This always blows my mind - for the first time in human history we live in a world where almost all prior art is relatively easily discoverable, and people don't even bother. I guess I shouldn't be surprised, after all, I've met a lot of people.
    - pjc50 5y ago
      The sheer weight of information can make it harder to find. Also, nobody gets paid for being the prior art.
userbinator 5y ago
There's an even simpler algorithm if you're fine with "close enough" circles: https://news.ycombinator.com/item?id=15266331 https://news.ycombinator.com/item?id=15266331
- Asraelite 5y ago
  Nevermind the circle, the fractals that algorithm can produce are insane. It would be a good a tweet-sized snippet of code for impressing people.
watersb 5y ago
I love Yurichev's books on assembly language, and he gives them away (CC-BY-4.0). https://beginners.re/ https://beginners.re/
- lelouch11 5y ago
  Actually that book is paywalled now. It's been somewhat of a controversy that people contributed to the book thinking it was a community resource but now it's unavailable.
  - runnerup 5y ago
    wow. although the last time he updated the (singular) username and password was october. i think people could just ask around for it. still, controversial indeed. Weirdly, the book itself says: > Q: May I print this book / use it for teaching? > A: Of course! That’s why the book is licensed under the Creative Commons license (CC BY-SA 4.0) So it would be legal for anyone else to host this.
    - johndough 5y ago
      I found a few versions which are hosted elsewhere: 2017 https://mirrors.ocf.berkeley.edu/parrot/misc/openbooks/programming/ReverseEngineeringForBeginners.en.pdf https://mirrors.ocf.berkeley.edu/parrot/misc/openbooks/progr... 2018 http://ebook.pldworld.com/_eBook/Reverse%20Engineering%20for%20Beginners/beginners.re/RE4B-EN.pdf http://ebook.pldworld.com/_eBook/Reverse%20Engineering%20for... In addition, some foreign languages still seem to be available: French https://beginners.re/RE4B-FR.pdf https://beginners.re/RE4B-FR.pdf German https://beginners.re/RE4B-DE.pdf https://beginners.re/RE4B-DE.pdf Italian https://beginners.re/RE4B-IT.pdf https://beginners.re/RE4B-IT.pdf Japanese https://beginners.re/RE4B-JA.pdf https://beginners.re/RE4B-JA.pdf Polish https://beginners.re/RE4B-PL.pdf https://beginners.re/RE4B-PL.pdf
deleted 5y ago
[deleted]
rep_lodsb 5y ago
With the error initialized to zero, this algorithm will always step immediately after drawing the first pixel, which will cause that pixel to "stick out". y += 1; // y == 1 err += 2*y + 1; // err == 3 x -= 1; // x == radius-1 err -= 2*x + 1; // err == 2-(2*(radius-1)) You could compare the absolute value of the new and old error, or start with err = -(radius-1) instead. And you don't need calculus to come up with the algorithm, just simple high school algebra: (x+1)² - x² = 2x + 1.

79 points by threeme3 5y ago

dark-star 5y ago

This is how we did it on the C64, back in the 80's :-D

anlunx 5y ago

dahfizz 5y ago

> It requires only additions, subtractions and bit shifts: 2x is the same as x<<1, of course. It also requires only integer arithmetic. Does any of this mean anything in JS, where AFAIK there are no real ints? 2x is an fpu operation under the hood, and not a bit shift.

Kranar 5y ago
IEEE double-precision floating-point numbers can exactly represent 53-bit integers and hence they are suitable for most integer related operations (ignoring bitwise operations). For bitwise operations, JavaScript will first convert the number to a 32-bit two's complement signed integer.
- dahfizz 5y ago
  I guess the question is really whether JS takes advantage of these facts. Will JS, at runtime, realize that X is an int and optimize 2 * X into a bit shift operation? Will JS recognize that Y and Z are perfectly represented integers stored in floats and so use integer instructions when adding Y + Z? Would such a thing even save time with all the casting back and forth to fp?
selcuka 5y ago
I guess JS is only used as a tool to demonstrate the algorithm.
masswerk 5y ago
I think, using the `(…) | 0` (expression binary ORed with zero) construct most JS engines will use true integers in optimized code.
- ygra 5y ago
  In fact, the specification even guarantees that for all the bitwise operators.
  - masswerk 5y ago
    However, this is relatively new and there may still be some legacy engines around.
    - ygra 5y ago
      That goes back to at least ECMAScript 1 in 1997. Possibly further. Not sure there are that many legacy engines from before that still around.
      - masswerk 5y ago
        Oh, I thought this came only with what was related to EMScripten before WASM (I forgot what the fast optimization standard is/was called). This took some years to propagate to all browsers. As for interpreted JS, a binary operator returns a 32-bit integer value, but it would be still stored as a Number (float). (Meaning, a | 0 => int, b = a | 0 => float stored in b, there is no other primitive numeric type. – Instead of optimizing for speed, you would be adding implicit type conversions.)
        ygra 5y ago
        Ah, now I get the confusion. Yeah, most of interpreters probably wouldn't have made the in-memory distinction between small ints and doubles. So the conversion would have to happen back and forth every time a bitwise operator would be applied. Nowadays the semantics if what happens are still the same, but things happen a bit more optimized by usually avoiding the round-trip to double when not necessary.
xscott 5y ago
Funny enough JavaScript now has BigInt, which is purely integer: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt#browser_compatibility https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- Someone 5y ago
  It also has typed arrays (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays https://developer.mozilla.org/en-US/docs/Web/JavaScript/Type...), but you can’t calculate with those values (you write floats into them that get rounded to integers, and values conceptually become floats when you read them) WebAssembly has i32 and i64.
Schroedingersat 5y ago
JS VMs have real ints (and you can summon them smi reliably usually with |0 ), but you're very much better off calling into some browser capability that will leverage the gpu most of the time.

christkv 5y ago

You can always try Bresenham’s circle drawing algorithm.

scrubs 5y ago
Beat me to it. And there are several optimizations on top that by, more or less, by reflecting the points as you compute one quadrant of the circle.
gotaquestion 5y ago
This is the era where prior art doesn't exist. Why read a book when you can blog about discovering "something new". I could probably make a killing blogging about my "discovery" of the algorithms in the book "Hacker's Delight".
- Mr_P 5y ago
  The author titled one of the sections "Midpoint circle algorithm". There happens to be a Wikipedia page on "Midpoint circle algorithm": https://en.wikipedia.org/wiki/Midpoint_circle_algorithm https://en.wikipedia.org/wiki/Midpoint_circle_algorithm The page claims, "Bresenham's circle algorithm is derived from the midpoint circle algorithm." The author of this blog post even made it clear, at the end of their article, that... "many explanations of midpoint algorithm use the final, optimized version. But I added several unoptimized steps." I think there's a lot of value in a blogpost that demonstrates how someone could re-derive a widely-used algorithm from scratch.
- taneq 5y ago
  This always blows my mind - for the first time in human history we live in a world where almost all prior art is relatively easily discoverable, and people don't even bother. I guess I shouldn't be surprised, after all, I've met a lot of people.
  - pjc50 5y ago
    The sheer weight of information can make it harder to find. Also, nobody gets paid for being the prior art.

userbinator 5y ago

There's an even simpler algorithm if you're fine with "close enough" circles: https://news.ycombinator.com/item?id=15266331 https://news.ycombinator.com/item?id=15266331

Asraelite 5y ago
Nevermind the circle, the fractals that algorithm can produce are insane. It would be a good a tweet-sized snippet of code for impressing people.

watersb 5y ago

I love Yurichev's books on assembly language, and he gives them away (CC-BY-4.0). https://beginners.re/ https://beginners.re/

lelouch11 5y ago
Actually that book is paywalled now. It's been somewhat of a controversy that people contributed to the book thinking it was a community resource but now it's unavailable.
- runnerup 5y ago
  wow. although the last time he updated the (singular) username and password was october. i think people could just ask around for it. still, controversial indeed. Weirdly, the book itself says: > Q: May I print this book / use it for teaching? > A: Of course! That’s why the book is licensed under the Creative Commons license (CC BY-SA 4.0) So it would be legal for anyone else to host this.
  - johndough 5y ago
    I found a few versions which are hosted elsewhere: 2017 https://mirrors.ocf.berkeley.edu/parrot/misc/openbooks/programming/ReverseEngineeringForBeginners.en.pdf https://mirrors.ocf.berkeley.edu/parrot/misc/openbooks/progr... 2018 http://ebook.pldworld.com/_eBook/Reverse%20Engineering%20for%20Beginners/beginners.re/RE4B-EN.pdf http://ebook.pldworld.com/_eBook/Reverse%20Engineering%20for... In addition, some foreign languages still seem to be available: French https://beginners.re/RE4B-FR.pdf https://beginners.re/RE4B-FR.pdf German https://beginners.re/RE4B-DE.pdf https://beginners.re/RE4B-DE.pdf Italian https://beginners.re/RE4B-IT.pdf https://beginners.re/RE4B-IT.pdf Japanese https://beginners.re/RE4B-JA.pdf https://beginners.re/RE4B-JA.pdf Polish https://beginners.re/RE4B-PL.pdf https://beginners.re/RE4B-PL.pdf

deleted 5y ago

[deleted]

rep_lodsb 5y ago

With the error initialized to zero, this algorithm will always step immediately after drawing the first pixel, which will cause that pixel to "stick out". y += 1; // y == 1 err += 2*y + 1; // err == 3 x -= 1; // x == radius-1 err -= 2*x + 1; // err == 2-(2*(radius-1)) You could compare the absolute value of the new and old error, or start with err = -(radius-1) instead. And you don't need calculus to come up with the algorithm, just simple high school algebra: (x+1)² - x² = 2x + 1.