Catmull-Clark basis function tables of derivatives

Recommended Posts

malyskolacek    121
Hi! I'm implementing Catmull-Clark subdivision for my terrain as described in the paper "Rapid evaluation of Catmull-Clark surfaces". I created the basis function tables with the program "Subdivide 2.0" exactly as in the paper. It works very well and the tessellation works fine. However, I'm stuck with creating of the basis function tables of derivatives. I need them to compute vertex normals. How do they generate the tables? Is it just sampling the derivatives on the tessellated unit pulse base mesh? I would appreciate some clarification! Thanks very much

Share on other sites
Soiled    286
I'm not quite sure what you mean by sampling the derivatives.

It's the same principle as the limit-surface mask which brings, in one final averaging step, the control mesh to the limit surface. The limit tangent and binormal each have their own limit masks which are applied in the same way when generating the basis tables. So I think the answer to your question is yes.

BTW: Because I didn't use subdivide2.0 to generate my tables I noticed that the limit tangent/binormal mask mentioned in "Piecewise Smooth Subdivision Surfaces with Normal Control" in the appendix is incorrect and the correct mask can be found in the source code of subdivide2.0 (quadrule.cpp). I found this out because for valency 4 vertices you're supposed to get...
-1 -4 -1
0 0 0
1 4 1
...or some rotation of that.

Share on other sites
malyskolacek    121
Quote:
 Original post by SoiledI'm not quite sure what you mean by sampling the derivatives.

I'll try to explain it in more detail...
What I do now:
First, I create the tesselated base mesh(unit pulse) by subdivide2.0. Then I sample the y-values of the vertices of the patch. These sampled values form the basis function table I later use at run-time.

The idea of sampling the derivatives came from the paper (Rapid evaluation of CC surfaces):
Quote:
 Page 4, just under the picture of the base mesh...For all these cases, limit positions and partial derivatives in the two parametric directions were sampled on a 33x33 grid....

I thought I would evaluate the partial derivatives for each of the 33x33 points. Now I don't know if this will work and also what should I sample from the derivatives? The y-component of their vectors?

Share on other sites
Soiled    286
Quote:
 I thought I would evaluate the partial derivatives for each of the 33x33 points. Now I don't know if this will work and also what should I sample from the derivatives? The y-component of their vectors?

I'd say so. Provide a unit pulse to subdivide2.0 (x=0,y=1,z=0) and ask it to produce a limit tangent and a limit binormal (assuming it can do that?) and take the y-component of results and put in your basis table (33x33 for tangent and 33x33 for binormal).
At run-time when subdividing a real control mesh you need to calculate limit-surface normal from cross product of limit tangent and limit binormal (both calculated using basis tables) - I don't think you can generate a table directly for the limit normal.

Share on other sites
malyskolacek    121
Quote:
 Original post by SoiledI'd say so. Provide a unit pulse to subdivide2.0 (x=0,y=1,z=0) and ask it to produce a limit tangent and a limit binormal (assuming it can do that?)

No, subdivide2.0 can't produce the tangent and binormal directly. I thought I would take the unit pulse tesselated by Subdivide2.0 and estabilish the tangents and binormals at each point with something like u=(2, y(x+1, z)-y(x-1, z), 0) v=(0, y(x, z+1)-y(x, z-1), 2) where y(x, z) is the y-coordinate of vertex in the grid at x, z. The y-values of u and v vectors would form the basis table. I don't really know if this would work.

I'd like to produce all basis tables from the unit pulse mesh generated with Subdivide2.0 if possible.

Share on other sites
Soiled    286
That's a shame about subdivide2.0 :(
I know it's got the masks for tangent and binormal in there (I looked at the source code) in quadrule.cpp - I guess it just doesn't expose the limit tangent/binormal in the library interface.

What you're suggesting is effectively a limit mask for tangent and binormal that's applied directly to the limit surface (instead of subdivided control mesh). Something like...
0 0 0
-1 0 1
0 0 0
...for tangent and...
0 -1 0
0 0 0
0 1 0
...for the binormal (or vice-versa or some rotation of). Whereas the correct solution is to apply
-1 -4 -1
0 0 0
1 4 1
...to the subdivided control mesh (instead of limit surface) and that's only for valency=4 vertices.

I guess it would work however there's two issues I see, (1) you also need masks for the extraordinary vertices (you've got them for the regular vertices only), (2) the real masks are designed to make the tangent space continuous so by using your own your tangent-space might look non-smooth in places where it's supposed to be smooth. Although it might be good enough for what you need (ie, might look good enough).

If you're after correctness though, since you've already invested in using subdivide2.0 perhaps you might want to look at the source code and try to figure out how to get access to the limit tangent/binormal (even if you have to hack the code a bit). Just a suggestion since the alternative of coding up your own with all the different combinations of crease edges, etc seems daunting. My case was easier because I dissallowed crease edges, etc so the rules become simple enough for me to code them myself.

Share on other sites
malyskolacek    121
The extraordinary vertices are no problem for me. The mesh I'm working on is made of quads only (there is no vertex with other valence than 4). No crease edges. And I really don't care whether the subdivision is correct on the boundary. That all comes from the fact that I will use this algorithm only for my terrain, where I may set these "limitations".

What would you suggest now?

Share on other sites
Soiled    286
So you have a regular heightfield terrain ? I thought you were trying to avoid heightmaps ? You can have extraordinary vertices with a quad-only mesh (eg, a cube has valency 3 vertices).

Having said that, it is possible to create overhangs with a regular (valency 4) catmull-clark surface but it's much easier when you allow arbitrary valency because you can then have tunnels, protrusions, etc, and also your cliffs/overhangs don't stretch too much (because you extrude quads where there's an overhang, ie a quad becomes a cube popping out of the surface, instead of just moving vertices).

Share on other sites
malyskolacek    121
Quote:
 Original post by SoiledSo you have a regular heightfield terrain ? I thought you were trying to avoid heightmaps ? You can have extraordinary vertices with a quad-only mesh (eg, a cube has valency 3 vertices).Having said that, it is possible to create overhangs with a regular (valency 4) catmull-clark surface but it's much easier when you allow arbitrary valency because you can then have tunnels, protrusions, etc, and also your cliffs/overhangs don't stretch too much (because you extrude quads where there's an overhang, ie a quad becomes a cube popping out of the surface, instead of just moving vertices).

OK, I will perhaps try to implement the basis table generation myself with the help of the subdivide2.0 source code. At first I'll perhaps restrict the vertices to valence 4 as I do now, but later, if all goes well, I'll allow other valences(well, I must admit that you have convinced me of the benefits of this [smile]).
I'll start coding and I will see...
And also, be prepared for another load of questions as soon as I get stuck somewhere in the implementation [grin]
And thanks for your input, the whole thing is much clearer to me now!

Share on other sites
Soiled    286
Starting with valency 4 is a good idea.
Are you planning on subdividing on-the-fly as the camera moves around or doing it at pre-compile and paging on-the-fly (or loading whole thing at load-time) ?
Also are you planning on using some form of level-of-detail ?
Reason I ask is because it'll determine how you handle things like hairline cracks appearing between adjacent control quads subdivided to same level due to float imprecision ((a+b)+c not always equal to a+(b+c) for floats) and obvious cracks due to differing subdivision levels.
Quote:
 And also, be prepared for another load of questions as soon as I get stuck somewhere in the implementation [grin]

No probs.

Share on other sites
malyskolacek    121
Quote:
 Original post by SoiledAre you planning on subdividing on-the-fly as the camera moves around or doing it at pre-compile and paging on-the-fly (or loading whole thing at load-time) ?

I'm planning to subdivide on the fly as the camera moves around. My very preliminary tests indicate that the cost of subdividing the patches is acceptable.
Quote:
 Also are you planning on using some form of level-of-detail ?Reason I ask is because it'll determine how you handle things like hairline cracks appearing between adjacent control quads subdivided to same level due to float imprecision ((a+b)+c not always equal to a+(b+c) for floats) and obvious cracks due to differing subdivision levels.

Yes, I would like to implement some sort of LOD later.
I have read the paper about geometry clipmaps from Hoppe and there is an interesting idea of handling the cracks between the patches. They morph the border of the more tesselated patch to match the neighbouring border. To eliminate the gaps caused by T-junctions(I guess it would perhaps solve also the float instability) they render zero-area triangles along the boundary. I have no experience with this, but it's worth trying.

P.S.:I will be on vacation next week so I can't reply until I come back...

Share on other sites
Soiled    286
Quote:
 I'm planning to subdivide on the fly as the camera moves around. My very preliminary tests indicate that the cost of subdividing the patches is acceptable.

Yeah I found that too.
Mine takes 300,000 cycles to subdivide one quad to 17x17 - that's generating limit surface and limit normals. That's unoptimised code but probably won't need optimising - a camera movement of 10metres/sec would cover a quad (each quad is ~4metres wide) in 400msec so no more than a few subdivisions per second.
Quote:
 Yes, I would like to implement some sort of LOD later.I have read the paper about geometry clipmaps from Hoppe and there is an interesting idea of handling the cracks between the patches. They morph the border of the more tesselated patch to match the neighbouring border. To eliminate the gaps caused by T-junctions(I guess it would perhaps solve also the float instability) they render zero-area triangles along the boundary. I have no experience with this, but it's worth trying.

That sounds alright - the only thing is generating the degenerate triangles on the borders at run-time can be a hassle - they don't explain how they do it in the paper but I've found it to be one of the biggest hassles of terrain rendering (removing T-junctions, that is) - you've got to access edges values from adjacent quads for the degenerate tris to counter T-junctions and the quad corners require accessing all quads incident to a corner vertex to counter float instability (ie you pick a value from one of the incident quads and copy it to all the degenerate strips meeting at that vertex) and it gets more complicated if you have hierarchical LOD in something like an ABT tree (ie all quads in a node (leaf or interior) have same subdivision level).
The technique I'm working on now avoids explicitly placing degenerate triangles by morphing to one end of an edge instead of the middle of an edge - it's basically the xvox technique (see http://users.belgacom.net/gc610902/) extended from heightfield to arbitrary quads. So that avoids the T-junctions and I avoid the float instability by generating exact same values for adjacent quads along their common edge in the subdivision code (I actually use fixed-point integers to accumulate the basis tables to calculate limit position/tangent/binormal and then set FPU precision/rounding-mode and then use floats to calculate the normalised normal - the integers are required because the order in which control points are accumulated differs between adjacent quads and floats are not associative even if FPU precision/rounding-mode is the same) - my normals have to be exactly the same too because I use them to displace the limit-surface using a displacement map (and the displaced surface must match at the edge) - there's no float associativity problems when calculating normal=cross(tangent,binormal) so float arithmetic is fine and besides it would be too difficult to do the normalisation with integer arithmetic.

Though I must admit that making the subdivision code produce exact results for arbitrary valency was a tricky (especially for the tangent/binormals since their masks are not symmetric like the position masks are - rotations of the position mask give same results but not so for the tangent/binormal masks). Copying edge/corner values into degenerate strips at run-time could be an easier path - Jon Blow's Unified Rendering LOD articles discuss that option (see http://number-none.com/product/).
Quote:
 P.S.:I will be on vacation next week so I can't reply until I come back...

Hope the vacation is/was enjoyable :)

[Edited by - Soiled on February 18, 2005 6:09:52 PM]