Back to our problem. Obviously we are in front of this challenge:

It’s not trivial to find those functions. The following is what I call a DIY solution. (If you want the full solution, have a look at pages 511-512 of Computer Graphics – Principles and Practice by Foley, van Dam, Feiner, Hughes). The exact mathematical method derived here is the forward differencing.

The only math tool that we need is Pascal’s Triangle. Blaise Pascal (1623 - 1662) was a French scientist whom, among other things, invented the Pascaline (that is the first mechanical computing machine of the history) and the theory of probability (in collaboration with Fermat). He is a good example of what we call a philosopher (the meaning of this word has changed today) as he worked on several fields of science. He also wrote several books on what we call today sociology and was very interested in religions.

This tool is simple: Imagine a NxM matrix. You define the first horizontal vector with some custom values. The tools give you the rule to get the other rows:

The first column has always the same original value. The others cells are equal to the sum of the cells present in the above row and the one present in the above row and the precedent column. Simple, isn’t it?

Let’s customize it now. We add a factor. Now we multiply the result of the add with the number of the column (the first line (10,4,7,123,0) is totally arbitrary):

In this example: 183 + 2212 = 2395 * 4 = 9580.

Here is the table created with the following starting row: (1,0,0,0,0,…)

This table gives us all the information we need. Again, my goal here is not to demonstrate the resolution of this equation. Rather, I just want to give you simple tools that can be used even by beginners.

Let’s precise the nature of the f function:

f₀ is trivial as it is given by the equation eq2 with uInt = 0. So:

To get the other functions we just have to read the table:

To sum up:

Here comes a justified question: Why all this work about Pascal’s triangle as a pure hand made solution could be sufficient here? The answer will come later in this article as, in order to compute the normals incrementally, we would have to handle a 5 order polynomial the same way!

The work is over for the inner loop. Now we can do the same work for the outer loop.

Remember how we’ve obtained the D vector:

As you can see D[i] is the result of a simple dot product with the same shape than this treated in the inner loop.

Let’s rewrite one more time our tesellator as we would like it to be. See listing 3.

To find the initialization values we just have to express D[i] using the M matrix. The second and final step is to recombine D[i] to get the f_i (eqs3) functions. Few minutes later the result is:

Vtx = M₃₃;
dvVtx = M₃₀ + M₃₁ + M₃₂;
ddvVtx = 6 * M_{30 +} 2 * M₃₁;
dddvVtx = 6 * M₃₀;

duVtx = M₀₃ + M₁₃ + M₂₃;
dvduVtx = M₀₀ + M₀₁ + M₀₂ + M₁₀ + M₁₁ + M₁₂ + M₂₀ + M₂₁ + M₂₂ ;
ddvduVtx = 6 * (M₀₀ + M₁₀ + M₂₀) 2 * (M₀₁ + M₁₁ + M₂₁) ;
dddvduVtx = 6 * (M₀₀ + M₁₀ + M₂₀) ;

dduVtx = 6 * M₀₃ ;
dvdduVtx = 6 * (M₀₀ + M₀₁ + M₀₂) ;
ddvdduVtx = 36 * M₀₀ + 12 * M₀₁ ;
dddvdduVtx = 36 * M₀₀ ;

ddduVtx = 6 * M₀₃ + 2 * M₁₃ ;
dvddduVtx = 6 * (M₀₀ + M₀₁ + M₀₂) + 2 * (M₁₀ + M₁₁ + M₁₂) ;
ddvddduVtx = 36 * M₀₀ + 12 * (M₀₁ + M₁₀) + 4 * M₁₁;
dddvddduVtx = 36 * M₀₀ + 12 * M₁₀;

If you look carefully at this stuff you will find more operations that could be saved.

A few comments about that: We achieved the same gain than for the inner loop: 12 adds vs. 12 adds and 12 muls. That’s good, but not phenomenal. An interesting thing is that we have pushed all the irregular calculation to the setup part. That’s nice because the heart of the tessellator is now composed just with simple vector adds. Another nice thing is the += operators. X86 processors like it as one of the source register must also be the destination one.

The last but not least very very nice thing about our work is that WE HAVE A RAW (read after write) DEPENDENCIES FREE function. This means that we don’t need to wait until the end of one add operation to start next. This is very important because on a pipelined FPU (nearly any FPU out there are pipelined) RAW dependencies cause stalls:

The dark side of our work is the amount of setup calculation that be added. That’s why I said in the beginning that there is not a good and a bad solution. If you just need to tessellate a patch two or three times go use recursive subdivision. If you are working on a landscape on which the average tessellation level is important, forget the setup time and use the incremental tessellator.

GIGnews is a publication of GIGnews.com, Inc.
"Get In the Game" is a registered trademark used with permission.
© 1999- 2005 GIGnews.com, Inc.
Legal