Search code examples
c++curve

How are control points referenced in this implementation for drawing a curve?

As an assignment, I have to implement De Casteljau Algorithm in order to draw a Bezier Curve. I understand fully how this algorithm works, and how it produces the curve, but I am failing to understand the coded implementation of the algorithm I have been given to work with.

The assigment consists of 3 parts:

  1. Drawing some number of control points as well as the edges connecting them.

  2. Implementing De Casteljau Algorithm for a given parameter t in the range [0, 1] which will draw all of the De Casteljau lines and the Bezier point according to this parameter. This is done in a function called drawDeCasteljau

  3. Draw the curve by iterating from t = 0.0 to t = 1.0 and passing each t into drawDeCasteljau and painting each Bezier point. This is done in a function called drawBezierCurve

The program will then work in the following way:

  • Click to add a point and an edge from the last point to this new point
  • Click and hold a point to drag it around
  • Press + or - to increment or decrement t. (This is where I currently am)
  • Press 1 to display the De Casteljau lines and Bezier point for the current value of t
  • Press 2 to paint the entire curve

The sample algorithm we have been given to use is:

int numPoints = 3;
Point bezPoints[numPoints][numPoints];

void DrawBezier() {
    for (float u = 0.0; u <= 1.0; u += 0.01) {
        for (int diag = numPoints - 2; diasg >= 0; diag--) {
            for (int i = 0; i <= diag; i++) {
                int j = diag - i;
                bezPoints[i][j] = (1.0 - u)*bezPoints[i][j + 1] + u*bezPoints[i + 1][j];
            }
         }
         setPixel(bezPoints[0][0]);
     }
}

I am completely lost with the bezPoints matrix and the lack of reference to any control points / lines in the algorithm.

Should bezPoints already be filled with the points before DrawBezier() is executed?

If I have 3 control points, why is bezPoints a 3x3 matrix? What exactly are these 9 points it is storing?

How does the algorithm work without ever referencing the control points / lines?

EDIT

Thanks to Nico's help below, I have managed to draw the Bezier curve:

enter image description here

However, I am still struggling to understand how to complete step 2 above in order to draw each of the De Casteljau lines used to find the Bezier point for the current value of t.

Solution

  • The control points should be in the farthest diagonal of the matrix bezPoints. You just have to get used to the indexing. Here is how it works: If you have numPoints = 3, the control points should be at diagonal 2, i.e. bezPoints[0][2], bezPoints[1][1], bezPoints[2][0]:

    i \ j | 0 | 1 | 2
------+---+---+---
   0  |         C
   1  |     C
   2  | C

    The loop over diag fills the other diagonals, i.e. the intermediate points after applying one iteration of the algorithm:

    i \ j | 0 | 1 | 2
------+---+---+---
   0  |D=0 D=1  C
   1  |D=1  C
   2  | C

    And then, the final point is at bezPoints[0][0].

    The variable u represents the curve parameter.