I''m trying to generate a sphere of evenly distributed triangles. So I start with a unit octahedron and subdivide it, splitting each triangle into 4 new triangles. The problem is, I end up with a lot of "overlapping" vertices because each vertex belongs to one triangle only. I want the triangles to share vertices. What''s the fastest way to find the right vertex indices? The brute force method is to first subdivide the triangles and then loop through the vertex list and merge verices that are close enough. But this is obviously too slow. Any better ideas?

quote:Original post by Ulf O
I''m trying to generate a sphere of evenly distributed triangles. So I start with a unit octahedron and subdivide it, splitting each triangle into 4 new triangles. The problem is, I end up with a lot of "overlapping" vertices because each vertex belongs to one triangle only. I want the triangles to share vertices. What''s the fastest way to find the right vertex indices?

The brute force method is to first subdivide the triangles and then loop through the vertex list and merge verices that are close enough. But this is obviously too slow.

Any better ideas?

Why is that too slow? You aren''t going to be retesselating your sphere every frame, are you?

computational geometry ...
ok heres how i did it once:
Build edge list of your model, so that every edge holds pointers to two vertices, BUT make room for one extra vertex and initialize it to NULL or somesuch. something like
typedef struct edge {
VERTEXINDEX a,b;
VERTEXINDEX extra;
} EDGE;

this way you can keep track of extra vertices you are creating. Now when splitting triangles, you have to split three edges. When splitting an edge, if the extra vertex slot is empty, just create it, and store it and return its value. When it isnt empty, create new edge so that it points to (a;extra;NULL), and make old one to point to (extra;b;NULL).
Of course, in the process you have to also keep triangles pointing to proper edges as well.
Easy ?

Anonymous Poster: Not every frame no, but for hi-res spheres it''s too slow even once. For 7 subdivisions, you get 8*4^7 triangles. Wich means something like half a milion vertices that have to be tested against each other. Even my 2Mhz P4 would probably choke on that.

no way: Sounds like a good idea. I''ll try it. Thanks.

There is sample source for tesselating spheres everywhere, including on Flipcode in ratcliffe''s stuff and in various openGL scene graph libraries.

If you really need speed you shouldn''t be generating them at run time anyway, you should generate a bunch of varying tesselatted spheres at load time and then instance them and scale them with your world transform.