Jump to content
  • Advertisement
Sign in to follow this  
malyskolacek

Catmull-Clark basis function tables of derivatives

This topic is 4895 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Quote:
Original post by Soiled
I'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?

Thanks for your patience :-)

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Soiled
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?)


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Soiled
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).


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!