What s Included

text only
 
progress indicator progress indicator progress indicator progress indicator

Implementing B-Spline Code

Before I get into the code, I need to issue a word of warning. The following code was designed to be far more transparent than efficient. My primary concern was communicating the procedures and not in communicating tight, modular code. Therefore, there are five different projects for this chapter. They all share the same basic code, but each one is tweaked to demonstrate a different facet of this chapter. I decided it was far better to do this than to supply you with one monolithic application with several switches or cryptic options. As you read this, remember that most of this code could be collapsed into one tighter application.

Figure 4.25 shows a screenshot from the open uniform curve application. Almost all of the figures in this chapter were generated using these applications, but Figure 4.25 shows what the application looks like with all the drawing features enabled (control polygon, curve, slope indicator, and basis functions).


Figure 4.25: Application screenshot.

Having said that, I'll begin with the code found in \Code\Chapter04 - Open Uniform B Splines. This code serves as the foundation for the other applications. The basic structure can be seen in BsplineApplication.h

The Open Uniform B-Spline Application

 #include "CurveApplication.h" 

These settings define the number of control points and the curve order. You can change these numbers and recompile to see the effects of different orders. I have not added error checking to ensure that the order is less than or equal to the number of control points; keep that in mind as you experiment.

 #define NUM_CONTROL_POINTS 6 #define CURVE_ORDER        4 

Here I define the number of vertices along the curve.

 #define NUM_CURVE_VERTICES   100 class CBSplineApplication : public CCurveApplication { public: 

These functions define the building blocks of the curve. First, you set the knot vector elements and then generate the basis functions. FillCurveBuffer is called every frame to generate new curve points from moving control points.

 void SetKnotVector();      void DefineBasisFunctions();      BOOL FillCurveBuffer(); 

These three functions draw the curve. The Render function draws the curve. You also have the option of calling the other two functions from Render if you'd like to see the basis functions and the slope.

 virtual void Render();      void DrawBasisFunctions();      void DrawSlope(); 

The knot vector stores a set of normalized knot values in the range of 0.0 to 1.0. The exact values in the knot vector will depend on the type of curve you want to draw.

 float        m_KnotVector[NUM_CONTROL_POINTS + CURVE_ORDER]; 

Instead of deriving the basis functions symbolically and then solving them for every value of t, I recursively evaluate a basis function for every value of t and use the array of precomputed values to create the curve. The following arrays hold those values. You can think of these arrays as holding the values that make up the basis function curves that you've seen throughout this chapter. There is a set of values for each basis function for each order. This takes up more memory than is absolutely necessary for rendering, but it makes it very easy to inspect what is actually happening with each recursive computation. The first array holds the actual basis values. The second array holds the slope at each of those points. You will see how these values are actually computed when I talk about DefineBasisFunctions .

 float        m_BasisFunctions[NUM_CURVE_VERTICES]                                   [NUM_CONTROL_POINTS]                                   [CURVE_ORDER];      float        m_DerivativeBasis[NUM_CURVE_VERTICES]                                    [NUM_CONTROL_POINTS]                                    [CURVE_ORDER]; 

This is a vertex buffer that holds the computed curve points. It must be refilled every time the control points are moved.

 LPDIRECT3DVERTEXBUFFER8 m_pCurveVertices; }; 

The actual implementation of these functions can be found in \Code\Chapter4 - Open Uniform B Splines\BsplineApplication.cpp. As usual, the basic setup occurs in PostInitialize . Here, I create a vertex buffer that is large enough to hold the control points, the curve vertices, and the two end points of the slope line.

 BOOL CBSplineApplication::PostInitialize() {        CCurveApplication::PostInitialize();        if (FAILED(m_pD3DDevice->CreateVertexBuffer(          (NUM_CONTROL_POINTS + NUM_CURVE_VERTICES + 2) * sizeof(GENERAL_VERTEX),           D3DUSAGE_WRITEONLY  D3DUSAGE_DYNAMIC, D3DFVF_GENERALVERTEX,           D3DPOOL_DEFAULT, &m_pCurveVertices)))               return FALSE; 

For this application, I define the knot vector once and compute the basis functions only once. These precomputed values can be used regardless of the position of the control points. They remain valid as long as you don't change the knot values.

 SetKnotVector();        DefineBasisFunctions();        return TRUE; } 

SetKnotVector does exactly that. In this case, it sets the knot vector values to create an open uniform knot vector. The values are normalized, so the vector will begin with k zeros, end with k ones, and contain evenly spaced fractional values in between.

 void CBSplineApplication::SetKnotVector() {        int KnotValue = 0;        for (long i = 0; i < CURVE_ORDER + NUM_CONTROL_POINTS; i++)        {               if (i <= NUM_CONTROL_POINTS && i >= CURVE_ORDER)                      KnotValue++;               m_KnotVector[i] = (float)KnotValue /                                 (float)(NUM_CONTROL_POINTS - CURVE_ORDER + 1);        } } 

DefineBasisFunctions is the most important new function. It applies the equations shown earlier in this chapter and evaluates the basis functions for a set of parametric values. As you walk through the code, keep in mind the fact that all of the equations were given with element indices beginning at 1. In code, arrays begin at 0, so I have to account for that when I index into the arrays.

 void CBSplineApplication::DefineBasisFunctions() { 

First, I set all of the values in the array of derivative values to zero. I could get by with only setting the first-order values to zero, but I decided to go with a clean slate.

 memset(m_DerivativeBasis, 0,               NUM_CURVE_VERTICES * NUM_CONTROL_POINTS *               CURVE_ORDER * sizeof(float)); 

This is where things get interesting. I loop through the array of parametric values, setting the evaluated basis value as I move along. Remember, these arrays do not store the final curve positions . Instead, they store the values of the basis functions for each value of t. In this case, I create an evenly spaced set of values from t = 0.0 to t = 1.0.

 for (long Vertex = 0; Vertex < NUM_CURVE_VERTICES; Vertex++)        { 

This is where I set evenly spaced parametric values. You could choose different values. Perhaps you want to create more points along a given section of the curve and less in other sections. This is where you'd make those decisions.

 float t = (float)Vertex / (float)NUM_CURVE_VERTICES; 

Now, loop through the first-order basis functions for each of the control points and apply the first step shown in Equation 4.1.

 for (long ControlPoint = 0;            ControlPoint < NUM_CONTROL_POINTS;            ControlPoint++)       {              if (t >= m_KnotVector[ControlPoint] &&                  t < m_KnotVector[ControlPoint + 1])                     m_BasisFunctions[Vertex][ControlPoint][0] = 1.0f;              else                     m_BasisFunctions[Vertex][ControlPoint][0] = 0.0f;       } } 

At this point, you will have the values for the first-order basis functions. The values will be either zero or one. If you plotted the values, the graph would look something like Figure 4.4. Now that you have the first order, you can recursively solve for the higher-order values by looping through the orders and applying the second part of Equation 4.1. Loop through the order, the control points, and the parametric values.

 for (long Order = 1; Order < CURVE_ORDER; Order++)      {             for (long ControlPoint = 0;                  ControlPoint < NUM_CONTROL_POINTS;                  ControlPoint++)             {                    for (long Vertex = 0;                         Vertex < NUM_CURVE_VERTICES;                         Vertex++)                    { 

I repeatedly define t. It can be argued that perhaps I should have set the values of t in an array so that I only had to define them once. That's a good idea, but I keep redefining them so that it is clear where they come from.

 float t = (float)Vertex / (float)NUM_CURVE_VERTICES; 

These are my cryptically named variables that represent the elements of Equations 4.1 and 4.9. The name Nikm1 stands for Ni, k-1 and so on. These values should have been set by previous iterations through the loops .

 float Nikm1    = m_BasisFunctions[Vertex]                                    [ControlPoint][Order - 1];                   float Nip1km1  = m_BasisFunctions[Vertex]                                    [ControlPoint + 1][Order - 1];                   float Dikm1    = m_DerivativeBasis[Vertex]                                    [ControlPoint][Order - 1];                   float Dip1km1  = m_DerivativeBasis[Vertex]                                    [ControlPoint + 1][Order - 1]; 

These variables are elements of the knot vector. The variable names follow the same pattern described above. In some cases, I have added one to the array index. This is to account for the fact that the index values in Equation 4.1 are one based and these arrays are zero based.

 float xi    = m_KnotVector[ControlPoint];                   float xikm1 = m_KnotVector[ControlPoint +                                              Order - 1 + 1];                   float xik   = m_KnotVector[ControlPoint +                                              Order + 1];                   float xip1  = m_KnotVector[ControlPoint + 1]; 

Now I have all the pieces, so I need to solve the equations. In doing so, I handle the special case where I set 0/0 equal to 0. I find the first and second terms of both the basis function and the derivative.

 float FirstTermBasis;                   float FirstTermDerivative;                   if (fabs(xikm1 - xi) < EPSILON)                   {                          FirstTermBasis      = 0.0f;                          FirstTermDerivative = 0.0f;                   }                   else                   {                          FirstTermBasis      = ((t - xi) * Nikm1) /                                                (xikm1 - xi);                          FirstTermDerivative = (Nikm1 + ((t - xi) *                                                Dikm1)) / (xikm1 - xi);                   }                   float SecondTermBasis;                   float SecondTermDerivative;                   if (fabs(xik - xip1) < EPSILON)                   {                          SecondTermBasis      = 0.0f;                          SecondTermDerivative = 0.0f;                   }                   else                   {                          SecondTermBasis = ((xik - t) * Nip1km1) /                                            (xik - xip1);                          SecondTermDerivative = (((xik - t) * Dip1km1)                                                 - Nip1km1) /                                                 (xik - xip1);                   } 

Now I add the two terms. The array now contains a precomputed basis function value for each value of t.

 m_BasisFunctions[Vertex][ControlPoint][Order]  =                                          FirstTermBasis + SecondTermBasis;                        m_DerivativeBasis[Vertex][ControlPoint][Order] =                                          FirstTermDerivative +                                          SecondTermDerivative;                     }              }        } } 

FillCurveBuffer is called when the application wants to move the control points and recompute the curve. In this case, I call FillCurveBuffer every frame. As usual, I begin by locking the vertex buffer.

 BOOL CBSplineApplication::FillCurveBuffer() {        if (!m_pCurveVertices)               return FALSE;        GENERAL_VERTEX *pVertices;        if (FAILED(m_pCurveVertices->Lock(0,          (NUM_CONTROL_POINTS + NUM_CURVE_VERTICES + 2) *          sizeof(GENERAL_VERTEX),          (BYTE **)&pVertices, D3DLOCK_DISCARD)))               return FALSE;        memset(pVertices, 0,        (NUM_CONTROL_POINTS + NUM_CURVE_VERTICES + 2) *        sizeof(GENERAL_VERTEX)); 

My method of moving the control points runs on autopilot. This loop runs through each control point and animates it in a sinusoidal pattern. In a real application, you would probably move the control points according to mouse input, collisions, and so on. In those cases, you would only refill the curve buffer when the control points actually moved.

 for (long ControlPoint = 0;             ControlPoint < NUM_CONTROL_POINTS;             ControlPoint++)        {               pVertices[ControlPoint].x = (600.0f /               (float)(NUM_CONTROL_POINTS -                                           1) * (float)ControlPoint);               pVertices[ControlPoint].y = 200.0f +                                           ANIMATE(200.0f *                                         sin(pVertices[ControlPoint].x));               pVertices[ControlPoint].z = 1.0f;               pVertices[ControlPoint].color = 0xFF000000;        } 

Now that the control point vertices are set, their values can be used in Equation 4.7. This loop computes the value of each point along the curve based on the control points and the basis function values.

 for (long i = NUM_CONTROL_POINTS;             i < NUM_CURVE_VERTICES + NUM_CONTROL_POINTS;             i++)        {               for (ControlPoint = 0;                    ControlPoint < NUM_CONTROL_POINTS;                    ControlPoint++)               {                      pVertices[i].x += pVertices[ControlPoint].x *                                        m_BasisFunctions[i -                                        NUM_CONTROL_POINTS]                                        [ControlPoint][CURVE_ORDER - 1];                      pVertices[i].y += pVertices[ControlPoint].y *                                        m_BasisFunctions[i -                                        NUM_CONTROL_POINTS]                                        [ControlPoint][CURVE_ORDER - 1];                      pVertices[i].z = 1.0f;                      pVertices[i].color = 0xFFFF0000;               }        } 

I have removed the second half of the function for brevity. The same looping procedure is applied using the basis function derivative values to find the slope at a given point on the curve. The code is very similar to the slope-finding code seen in previous chapters.

Once all the vertices are set, the buffer is unlocked and they are ready to be drawn.

 m_pCurveVertices->Unlock();        return TRUE; } 

DrawBasisFunctions is an extremely inefficient utility function. I wanted it to be self-contained so that it could be removed easily. As a result, it inefficiently re-creates a vertex buffer every time it draws.

 void CBSplineApplication::DrawBasisFunctions() {        LPDIRECT3DVERTEXBUFFER8 pBasisVertices;        if (FAILED(m_pD3DDevice->CreateVertexBuffer(                            NUM_CURVE_VERTICES * sizeof(GENERAL_VERTEX),                            D3DUSAGE_WRITEONLY  D3DUSAGE_DYNAMIC,                            D3DFVF_GENERALVERTEX,                            D3DPOOL_DEFAULT, &pBasisVertices)))               return;        GENERAL_VERTEX *pVertices; 

In this case, looping through the control points is actually looping through the different basis functions. The control points are not used when plotting the basis functions. The code locks and draws each function separately.

 for (long ControlPoint = 0;                 ControlPoint < NUM_CONTROL_POINTS;                 ControlPoint++)       {              if (FAILED(pBasisVertices->Lock(0,                          NUM_CURVE_VERTICES * sizeof(GENERAL_VERTEX),                          (BYTE **)&pVertices, D3DLOCK_DISCARD)))                     return;              for (long x = 0; x < NUM_CURVE_VERTICES; x++)              { 

This code assumes that the values of t are evenly spaced. This x position is based on this assumption. The value of the basis function falls somewhere within the range of 0 to 1. I scale that value by 200 so that you can easily see the shape of the curve. In its current form, this function plots the highest-order basis functions. You can change the code if you'd like to see the other basis functions.

 pVertices[x].x = x / (float)(NUM_CURVE_VERTICES - 1) *                               600.0f;              pVertices[x].y = 200.0f *                               m_BasisFunctions[x]                               [ControlPoint][CURVE_ORDER - 1];              pVertices[x].z = 1.0f;              pVertices[x].color = ControlPoint *                                   (0xffffffff / NUM_CONTROL_POINTS);       }       pBasisVertices->Unlock(); 

This is where each individual curve is plotted.

 m_pD3DDevice->SetStreamSource(0, pBasisVertices,                                           sizeof(GENERAL_VERTEX));             m_pD3DDevice->DrawPrimitive(D3DPT_LINESTRIP, 0,                                         NUM_CURVE_VERTICES - 1);        }        m_pD3DDevice->SetStreamSource(0, NULL, 0);        pBasisVertices->Release(); } 

This is where the curve is actually rendered. FillCurveBuffer animates the control points and recomputes the curve buffer. Once that is done, this code renders the control polygon, the curve, and the slope line. In its current form, this function also draws the basis functions. You can comment out DrawBasisFunctions if you only want to see the curve.

 void CBSplineApplication::Render() {        CCurveApplication::Render();        FillCurveBuffer();        m_pD3DDevice->SetStreamSource(0, m_pCurveVertices,                                      sizeof(GENERAL_VERTEX));        m_pD3DDevice->DrawPrimitive(D3DPT_LINESTRIP, 0,        NUM_CONTROL_POINTS - 1);        m_pD3DDevice->DrawPrimitive(D3DPT_LINESTRIP, NUM_CONTROL_POINTS,                                    NUM_CURVE_VERTICES - 1);        m_pD3DDevice->DrawPrimitive(D3DPT_LINESTRIP,                            NUM_CONTROL_POINTS + NUM_CURVE_VERTICES, 1);        DrawBasisFunctions(); } 

The preceding code provides a foundation for the other example programs. The code was used to create the curves shown in Figure 4.13.

For the remaining code snippets, I will highlight the differences only. The full source code can be found on the CD.

The Open Nonuniform B-Spline Application

The code for open nonuniform curves can be found on the CD in the \Code\Chapter04 - Open Nonuniform B Splines\ directory. There is only one major change here. The SetKnotVector function is changed so that one of the knot vector values is animated.

 void CBSplineApplication::SetKnotVector() {        int KnotValue = 0;        for (long i = 0; i < CURVE_ORDER + NUM_CONTROL_POINTS; i++)        {               if (i <= NUM_CONTROL_POINTS && i >= CURVE_ORDER)                      KnotValue++;               m_KnotVector[i] = (float)KnotValue /                                 (float)(NUM_CONTROL_POINTS - CURVE_ORDER + 1);        } 

The knots are first set as in the previous application, but then the first "inner" knot is animated back and forth between the two surrounding knots. It must not leapfrog the other knots because that would break the rule that the knot values must be monotonically increasing.

 m_KnotVector[CURVE_ORDER + 1] += ANIMATE(1.0f /                                                 (float)(NUM_CONTROL_POINTS +                                                 CURVE_ORDER + 1)); } 

Remember, the basis functions must be redefined whenever the knot vector changes. In this case, I have changed the render function so that the knot vector, the basis functions, and the vertices are updated with every frame. The result is an animated curve similar to the curves shown in Figures 4.19 and 4.20.

The Periodic Uniform B-Spline Application

There are two changes in this application. The first change is that the knot vector is periodic and uniform. The knot values are evenly spaced from 0 to 1.

 void CBSplineApplication::SetKnotVector() {        for (long i = 0; i < NUM_CONTROL_POINTS + CURVE_ORDER; i++)        {               m_KnotVector[i] = (float)i / (float)(NUM_CONTROL_POINTS +                                 CURVE_ORDER);        } 

Once the knot values are computed, you must explicitly redefine the parametric range as shown in Equation 4.8. I have subtracted a very small amount from the maximum value to satisfy the less-than constraint shown in Equation 4.8.

 m_MinT = m_KnotVector[CURVE_ORDER - 1];        m_MaxT = m_KnotVector[NUM_CONTROL_POINTS] - 0.00001f; } 

The new knot vector affects the computation of the basis functions in one minor but important way. The previous examples generated values of t in the range of 0 to 1. Now, you must account for the decreased parametric range. The following code is a snippet from DefineBasisFunctions . It generates a set of even-spaced parametric values in the new range.

 for (long Vertex = 0; Vertex < NUM_CURVE_VERTICES; Vertex++)        {               float t = m_MinT + ((m_MaxT - m_MinT) *                    (float)Vertex / ((float)NUM_CURVE_VERTICES - 1.0f)); 

This method of generating values for t is used in both DefineBasisFunctions and DrawBasisFunctions . You can definitely restrict yourself to some smaller subset of values within that range, but you must not try to use values outside of that range.

The application generates curves like the one seen in Figure 4.12.

Generating Closed Shapes with an Open Knot Vector

The code is identical to the first application except that I explicitly set the five control points to create a closed shape. The following code snippet is taken from the updated FillCurveBuffer function.

 pVertices[0].x = 0.0f;       pVertices[0].y = 0.0f;       pVertices[1].x = 0.0f;       pVertices[1].y = 200.0f;       pVertices[2].x = 200.0f + ANIMATE(200.0f);       pVertices[2].y = 200.0f;       pVertices[3].x = 200.0f;       pVertices[3].y = 0.0f;       pVertices[4].x = 0.0f;       pVertices[4].y = 0.0f; 

The first and last control points match, closing the shape. I have chosen to animate one of the points just to show the effect on the closed shape. The result looks similar to the shape shown in Figure 4.21.

Generating Closed Shapes with a Periodic Knot Vector

The code used for a periodic shape is the same as that used to create a periodic curve. In this case, I have created a triangle with six control points. Four are needed to create the closed triangular control polygon and two (k-2) more are needed to actually close the resulting shape. The following code snippet is from FillCurveBuffer . Notice that the third and sixth points must be animated in the same way. Matching control points must be moved equally if you want the shape to stay closed.

 pVertices[0].x = 0.0f;       pVertices[0].y = 0.0f;       pVertices[1].x = 200.0f;       pVertices[1].y = 400.0f;       pVertices[2].x = 400.0f + ANIMATE(200.0f);       pVertices[2].y = 0.0f;       pVertices[3].x = 0.0f;       pVertices[3].y = 0.0f;       pVertices[4].x = 200.0f;       pVertices[4].y = 400.0f;       pVertices[5].x = 400.0f + ANIMATE(200.0f);       pVertices[5].y = 0.0f; 

The resulting closed shape is similar to the shape shown in Figure 4.24.

Each of these applications has been tweaked to demonstrate the individual concepts found in this chapter. Take some time to experiment with the code. Manipulate the curve by changing the degree, moving the control points, and changing the knot vector. You can use the code to get a better feel for how these effects really work.

progress indicator progress indicator progress indicator progress indicator


Focus on Curves and Surfaces
Focus On Curves and Surfaces (Focus on Game Development)
ISBN: 159200007X
EAN: 2147483647
Year: 2003
Pages: 104
Authors: Kelly Dempski

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net