Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

yurichev.com

Post reply on HN
Print view View original

31–40 of 42 posts

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

#31

Post by dahfizz »

Kranar wrote: post #18
dahfizz wrote: post #3

> It requires only additions, subtractions and bit shifts: 2x is the same as x 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.

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.

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?

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

#32

Post by Asraelite »

userbinator wrote: post #9

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

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.

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

#33

Post by jacquesm »

thealig wrote: post #22
christkv wrote: post #5

You can always try Bresenham’s circle drawing algorithm.

that was my first reaction on reading the title..that's how retro computers back in the day displayed circles on sparse pixel displays

And pen based vector plotters.

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

#34

Post by ygra »

masswerk wrote: post #28
ygra wrote: post #15

Earlier quoted context omitted.

In fact, the specification even guarantees that for all the bitwise operators.

However, this is relatively new and there may still be some legacy engines around.

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.

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

#35

Post by rep_lodsb »

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.

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

#36

Post by masswerk »

ygra wrote: post #34
masswerk wrote: post #28

Earlier quoted context omitted.

However, this is relatively new and there may still be some legacy engines around.

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.

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.)

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

#37

Post by ygra »

masswerk wrote: post #36
ygra wrote: post #34

Earlier quoted context omitted.

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.

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…

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.

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

#38

Post by masswerk »

ygra wrote: post #37
masswerk wrote: post #36

Earlier quoted context omitted.

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…

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.

Isn't there even a formal specification that hot code maintains values or-ed with zero internally as integers?

(I think, this had been originally introduced by Mozilla and propagated to other browsers to varying extent. This optimization allowed a significant speed up for things like EMScripten before WASM.)

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

#39

Post by christkv »

jacquesm wrote: post #33
thealig wrote: post #22

Earlier quoted context omitted.

that was my first reaction on reading the title..that's how retro computers back in the day displayed circles on sparse pixel displays

And pen based vector plotters.

I loved pen based plotters it was mesmerising to watch them draw.

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

#40

Post by jacquesm »

christkv wrote: post #39
jacquesm wrote: post #33

Earlier quoted context omitted.

And pen based vector plotters.

I loved pen based plotters it was mesmerising to watch them draw.

Indeed, but oh those pens were so expensive and woe to you if a pen ever punctured the paper. That could get messy in a hurry. And then of course the printerbuffer would have another 250K worth of plotter commands and good luck getting that to stop.
Post reply on HN