2
$\begingroup$

I wonder why all the well known algorithms of drawing for example circles (bresenham, mid-point, etc) all use integer arithmetics? For example, here is a simple circle drawn with bresenham algorithm: enter image description here

And this is what I get with a circle drawn using naive algorithm (with real numbers): enter image description here

The bresenham's version just look terrible and feels laggy while the floating point version is much smoother. So why do we read everywhere that "integer" versions are preferred? The integer version is maybe faster but horrible when it comes to animating a moving shape. So the question is: should I use floating point version or bresenham's version in my little toy rasterizer?

Here's a more real world example:

Bresenham:

enter image description here

Floating point:

enter image description here

So what which version is the correct one? The floating point looks wobbly but smoother than Bresenham. Should I stick with Bresenham integer or use a floating point version smoother (or even a fixed point version)?

Improve this question
$\endgroup$
2
  • $\begingroup$ "The bresenham's version just look terrible and feels laggy while the floating point version is much smoother." What about the massive amount of dot crawl in your "naive" algorithm? I'd call that pretty rough. $\endgroup$
    – Nicol Bolas
    Commented Dec 23, 2019 at 14:26
  • $\begingroup$ There is no point on a modern platform, integer algorithms were intended for machines from the 70-80s.. $\endgroup$
    – PaulHK
    Commented Dec 23, 2019 at 14:26

1 Answer 1

Reset to default
2
$\begingroup$

The following is really an assorted set of comments:

Why integer? Floating-point hardware is (in general) far more complex than integer and so on many (old) CPUs it (a) might not have been available (because of silicon budget) and/or (b) took considerably more clock cycles to execute than integer operations.

Re "Bresenham's" algorithm: IIRC there is a branch/decision per pixel. On old CPUs (with relatively little or no pipelining) this would have not been a penalty, but with modern, highly pipelined/superscalar CPUs, each mispredicted branch will be detrimental. Presumably (as I can't see your code) using floating-point removes that decision from the loop but, then again, you could use fixed-point (i.e. integer) to get the same effect.

Having said this, hardware rasterisation is probably using fixed-point (i.e. integer) maths when filling polygons as this (a) makes conforming to the OpenGL fill rules easier and (b) prevents some very nasty problems occuring with long/thin triangles.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ok but regarding the visual result, which of the 2 versions is preferrable? The first version feels laggy but produces perfect circles whereas the second version is much smoother but if we pause the animation, the circles are not very round $\endgroup$
    – Voko
    Commented Dec 23, 2019 at 17:02
  • $\begingroup$ You're asking for an 'artistic/ aesthetic’ evaluation? That's getting into trading-off temporal vs spatial sampling/aiasing/noise. $\endgroup$
    – Simon F
    Commented Dec 23, 2019 at 17:31
  • $\begingroup$ Actually, having taken a snapshot of the "floating point" version, it seems to me that the 'line width' is inconsistent. $\endgroup$
    – Simon F
    Commented Dec 23, 2019 at 17:35
  • 3
    $\begingroup$ @Jojolatino The bresenham version is not "laggy" because of misprediction - it simply allows the circle to move only by a single pixel at a minimum. The floating point version allows subpixel precision in some sense, which causes not all points of the circles to move by the same amount creating an illusion of smoothness. What you are seeing is a combination of aliasing and temporal discontinuity, the floating point version handles it better because it does not enforce the exact same sampling, which gives more of a leeway for temporal continuity. $\endgroup$
    – lightxbulb
    Commented Dec 23, 2019 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.