PDA

View Full Version : Subdivision algorithm of a tetrahedron



Leonardave
03-16-2009, 02:40 AM
Does anybody know how to subdivide a tetrahedron to be a sphere, what kind of algorithm is applicable? Thanks in advance.

Nicolai de Haan Brøgger
03-16-2009, 03:14 AM
You can look in the Red Book, chapter 2 towards the end for an idea.

Leonardave
03-16-2009, 06:59 PM
Thanks, that is very helpful.

Yomboprime
11-27-2009, 01:01 PM
Hey I'm doing exactly this right now. I subdivide the four triangles by calling a recursive function that takes three points as parameters (the three vertices), and an integer meaning the recursion level. Then in the function you simply stop at a given recursion level and draw the triangle (normalizing the vertices to a sphere of the radius you want), or do four recursive calls. In this case the steps are:

1 - increment the recursion level integer to pass it further in the recursive calls.
2 - compute the midpoints. If you have vertices v0, v1 and v2 you compute v01 = 0.5 * (v0 + v1), v12 = 0.5 * (v1 + v2), and v20 = 0.5 * (v0 + v2)
3 - make the four recursive calls by using the vertices:
first call: v0, v01, v20
second call: v01, v1, v12
third call: v12, v2, v20
fourth call: v01, v12, v20

I'm not using a tetrahedron, instead I use an octoedron wich gives me no problems of texture coordinate wrapping (a tetrahedron doesn't have a line from pole to pole through triangle segments), but I think that it is giving me problems in the culling.
I use culling of triangles (if a triangle at a given recursion level does have the vertex normals and the triangle normal facing outwards the camera, I discard it, i.e. I don't draw nor make more recursion with it), but the culling doesn't work well in some cases and I think i's because I'm using an octoedron and the triangles are not normal to the sphere anymore.
I suppose I'll have to use a tetrahedron and split the triangles falling at the "meridian 0" so no texture wrapping problems appear.