1

I'm trying to draw a curve between two points, specifically I leave a picture of what I want:

enter image description here

This image was taken from this pdf on page 10.

I understand that applies the concept of Bresenham algorithm but do not know how to implement the concept for draw the curve.

On page 11 of the pdf pseudocode algorithm shown, but do not understand the concept of "error" to implement. Please if anyone can help me understand this. I work with C ++ and OpenGL.

Pseudocode:

set up x, y to x0, y0
set up error variable exy for P(x0+1,y0+1)
loop
set pixel x, y
   if ex + exy > 0 then increment x, sub difference error
   if ey + exy < 0 then increment y, add difference error
loop until end pixel

Thanks you all.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
Jonatan Lavado
  • 954
  • 2
  • 15
  • 26
  • 4
    "*I understand that applies the concept of Bresenham algorithm but do not know how to implement the concept for draw the curve.*" You don't Bresenham's algorithm is for drawing lines, not curves. Now, you can use Bresenham's algorithm to draw a curve by first splitting it into a bunch of lines. But that's a different matter. – Nicol Bolas Oct 10 '16 at 02:12
  • So go and look-up cubic &/or quadratic splines. There are reams written about calculating the points on each. As Nicol said - Bresenham's algorithm has no (or very limited, at best) practical use here. – enhzflep Oct 10 '16 at 02:15
  • Bresenham algorithm for curves is always only for a specific equation/curve type you derive at compile/code time. so if you create Bresenham for ellipse it will always draw just ellipse. This limitation is unacceptable for arbitrary curve shape not to mention the subdivision by inflex points etc... Use cubic curves instead. see [Proper implementation of cubic spline interpolation](http://stackoverflow.com/a/20517874/2521214) All of the cubic curves are handled in the same manner the only difference is how are you computing the coefficients. – Spektre Oct 10 '16 at 07:49

2 Answers2

3

This paper you cited draws curves from a low level of abstraction to try to gain performance increases. Normally when you go to draw curves you should use a higher abstraction such as Beziers with De Casteljau's algorithm which your pdf mentions on page 22. I've done this in c++ and it's not hard at all. Pomax has an awesome guide that explains it well. You basically subdivide your curve until it's many straight lines looks curved. Then you draw all the straight lines.

Eric Bischoff
  • 253
  • 1
  • 6
1

The idea of this algorithm is that you define your curve by a function f(x, y) = 0. That is to say that the function f(x, y) should return zero for the (x, y) coordinates of any point which lies on the curve. For any point which does not lie on the curve, the function should return a nonzero value, whose magnitude and sign should indicate the distance and direction, respectively, of the given point from the curve. This value is referred to as “error”.

Thus, the “error” value for any pixel can be computed simply by calling f(x, y) for the (x, y) coordinates of the pixel in question.

Entropy
  • 275
  • 1
  • 8