Chapter 2: Trigonometric Functions

The Source Code

The CD includes the code for Chapter 6 in Code\Chapter06 - Subdivision. For simplicity, I have reverted back to using B-splines, but the method will work equally well for NURBS or Bezier curves. For the most part, it is based on the same underlying code seen in the previous chapters, but there are a couple of changes. The first change is that vertices are now stored as a linked list of points. This makes it easy to rearrange and add points while subdividing. This structure is called SD_VERTEX . It includes a parametric position, a screen position, and a pointer to the next vertex in the linked list.

 typedef struct SD_VERTEX {        float t;        float x, y;        SD_VERTEX *pNextVertex; } SD_VERTEX; 

The class has been expanded to accommodate both the subdivision features. I only highlight the following new features.

 class CBSplineApplication : public CCurveApplication { public: 

These features support the subdivision scheme. m_pHead is the first vertex in the linked list. SubdivideCurve drives the subdivision process. GetPositionForT and FindBestCandidate are helper functions for the subdivision process. The first computes the actual curve point for a value of t and the second returns the line segment that needs subdivision the most. The source code for GetPositionForT is not shown in the text because it is very similar to the curve computation code shown in many of the previous chapters. The new application also keeps track of the number of resulting vertices.

 SD_VERTEX *m_pHead;        void SubdivideCurve(long NumPoints, float Tolerance);        void GetPositionForT(float t, float *pX, float *pY);        SD_VERTEX * FindBestCandidate(float Tolerance);        long m_NumVertices; }; 

This is the code for adaptive subdivision (found in BsplineApplication.cpp in the directory for this chapter). SubdivideCurve drives the entire process.

 void CBSplineApplication::SubdivideCurve(long NumPoints, float Tolerance) { 

First, clear out any old vertices that might be contained in the linked list. This involves walking the list and deleting all of the members .

 SD_VERTEX *pTemp;        while (m_pHead)        {               pTemp = m_pHead;               m_pHead = m_pHead->pNextVertex;               delete pTemp;        } 

Once the old values are gone, start with a uniformly divided set of vertices based on the number of control points. Start by creating one vertex at t = 0.0.

 m_pHead = new SD_VERTEX;        m_pHead->t = 0.0f;        GetPositionForT(m_pHead->t, &(m_pHead->x), &(m_pHead->y));        SD_VERTEX *pCurrent = m_pHead; 

Now, create the rest of the starter vertices. The overall process is very similar to what you've seen in earlier chapters because I'm not adaptively subdividing yet.

 for (int i = 1; i < NUM_CONTROL_POINTS; i++)        {               pCurrent->pNextVertex = new SD_VERTEX;               pCurrent->pNextVertex->pNextVertex = NULL;               pCurrent->pNextVertex->t = (float)i /                                          (float)(NUM_CONTROL_POINTS - 1);               GetPositionForT(pCurrent->pNextVertex->t,                    &(pCurrent->pNextVertex->x),                    &(pCurrent->pNextVertex->y));               pCurrent = pCurrent->pNextVertex;        } 

So far, you just have the starter points.

 m_NumVertices = NUM_CONTROL_POINTS; 

Now it's time for the actual subdivision process. This loop continues until either all tolerances are good or you have reached the maximum number of points.

 while (TRUE)        { 

One of the inputs to this function is the maximum number of vertices you want to create. If that many have been created, the loop stops. You can force it to only pay attention to the tolerance constraint by setting NumPoints extremely high.

 if (NumPoints && m_NumVertices == NumPoints)                      break; 

Every time through the loop, the code picks the best line segment to subdivide based on the midpoint distance comparison. If all segments are within the tolerance, FindBestCandidate will return NULL .

 SD_VERTEX *pBest = FindBestCandidate(Tolerance);               if (pBest)               { 

Subdivide the segment by creating a new vertex at the midpoint, finding the real curve value at the midpoint, and inserting the new point between the old ones. The fact that the real curve position is computed in FindBestCandidate and then immediately recomputed here presents at least one optimization opportunity.

 SD_VERTEX *pNew = new SD_VERTEX;               pNew->t = pBest->t + (pBest->pNextVertex->t - pBest->t) /                        2.0f;               GetPositionForT(pNew->t, &(pNew->x), &(pNew->y));               pNew->pNextVertex = pBest->pNextVertex;               pBest->pNextVertex = pNew;               m_NumVertices++;            }            else               break;      } } 

This function makes use of FindBestCandidate and GetPositionForT , which are both shown next. FindBestCandidate returns a pointer to the starting vertex of the line segment that has the largest gap between the real and interpolated midpoints.

 SD_VERTEX *CBSplineApplication::FindBestCandidate(float Tolerance) {        SD_VERTEX *pCurrent = m_pHead;        SD_VERTEX *pBestCandidate = NULL;        float      CurrentDistance = 0.0f;        float tm;        float xm, ym;        float xi, yi;        float Distance; 

Walk through the entire set of vertices. You could add more sorting mechanisms to make this more efficient. I wanted to make sure that the curve material was not obscured by other code.

 while (pCurrent->pNextVertex)        { 

Find the parametric value in the middle of the two parametric values of the current line segment and find the position for that value.

 tm = pCurrent->t +                   (pCurrent->pNextVertex->t - pCurrent->t) / 2.0f;               GetPositionForT(tm, &xm, &ym); 

Find the interpolated midpoint of the line segment.

 xi = pCurrent->x +                   (pCurrent->pNextVertex->x - pCurrent->x) / 2.0f;               yi = pCurrent->y +                   (pCurrent->pNextVertex->y - pCurrent->y) / 2.0f; 

Compute the distance between the two midpoints. If it's greater than the current maximum and greater than the tolerance, set this point to be the best candidate for subdivision and set the current maximum distance to this distance.

 Distance = sqrt((xi - xm) * (xi - xm) + (yi - ym) * (yi - ym));        if (Distance > CurrentDistance && Distance > Tolerance)       {              pBestCandidate = pCurrent;              CurrentDistance = Distance;       }        pCurrent = pCurrent->pNextVertex; } 

If all segments were within the tolerance, this value will be NULL . Otherwise, it will be a pointer to the endpoint of the worst line segment.

 return pBestCandidate; } 

The final change is that the FillCurveBuffer function is very different. Now, the code copies the vertices created during the subdivision process. I have not included that code in the text, but you might want to make sure you look at it on the CD.