sphere triangulation

This comes up occasionally, but with search down it'll probably be easier to tell you than to direct you to a reference. There are two common ways I know of to create a sphere (or ellipsoid) mesh. The first is to parameterize along lattitude and longitude (I believe this is what the OpenGL utility function does). This has the disadvantage of unequal triangle distribution.

A more difficult but perhaps better way is to start with a regular platonic solid (such as, as you suggest, a tetrahedron) and subdivide recursively to the desired level of detail. Then normalize all the vertices, scale by the radius (or radii), and you're done. (I use an icosahedron as the base mesh.)

This is a little more involved, as it involves a subdivision step, which generally requires generating connectivity information. But the results are very nice.

Is your icosahedron difficult to calculate? The dictionary says it has 20 faces.

mike
http://www.coolgroups.com/

Here is a document by Dave Eberly that gives mesh info for various solids. The mesh data can probably be found other places online as well.

If anything is difficult about the sphere construction, it's the recursive subdivision.

The problem is (well, may be) that, assuming you want the same level of detail everywhere, there's a huge difference in the number of triangles between one level and the next when you subdivide.

An alternative might be to create N (any number you like!) unit vectors, initially in randomish directions. Then run some simple iterative procedure on them that makes them all repel each other, and damp. When everything's settled down triangulate the points (equivalent to creating the convex hull, which is pretty easy).

You're right about the increase in number of triangles. One reason I use this method is that it uses support code already in place for my subdivision surface class, which (at least with the algorithm I use) requires subdivision of each triangle into four new ones.

It also works well with a scalable level of detail scheme, in that the vertices of each level of detail are included in the next. Of course you could also have multiple discrete meshes and simply switch between them. However, I find the lod switches with the subdivision method more aesthetically pleasing (just personal preference).

The convex hull is an interesting idea though. Also, if you want more control over the number of triangles and aren't concerned with distribution, you can just use the latitude/longitude method.

Quote:

Original post by MrRowl An alternative might be to create N (any number you like!) unit vectors, initially in randomish directions. Then run some simple iterative procedure on them that makes them all repel each other, and damp. When everything's settled down triangulate the points (equivalent to creating the convex hull, which is pretty easy).

Umm would that be simpler than mesh subdivision of a regular ideal solid.
I think OpenGL utility library uses subdivision of a regular tetrahedron and it seems to work very well.

MrRowl, can you please point me to some simple code that creates the convex hull? My understanding was that it's not that simple.

mike
http://www.coolgroups.com/

jyk, thanks for that document by Dave Eberly. It was helpful, and I created a sphere from a tetrahedron. Out of curiosity, why did you decide to use an icosahedron? It seems like a tetrahedron is sufficient for a great sphere.

mike
http://www.coolgroups.com/

Quote:

Umm would that be simpler than mesh subdivision of a regular ideal solid.

No, but I think his point was that you get a (more or less) regular triangle distribution, but with finer control over the number of triangles.

Quote:

I think OpenGL utility library uses subdivision of a regular tetrahedron and it seems to work very well.

I'm fairly certain that OpenGL parameterizes by latitude and longitude.

Quote:

MrRowl, can you please point me to some simple code that creates the convex hull? My understanding was that it's not that simple.

It's not (in 3d at least). Whatever method you use, there's quite a bit of bookkeeping involved. It's not impractical - it's just probably not something you're going to code up in 15 minutes.

However (and I'm just speculating here), you may not need a general convex hull algorithm for the method Mr. Rowl proposed, given the a priori knowledge about the vertex distribution. For example, you could find the n vertices closest to a given vertex, sort them about the vertex, and construct triangles from them. There'd be some details to handle, but I'm pretty sure you could special-case triangulating a uniformly spaced spherical point set.

Quote:

Out of curiosity, why did you decide to use an icosahedron? It seems like a tetrahedron is sufficient for a great sphere.

No reason, and I may switch to some other primitive in the future. There may be some correlation between the choice of initial primitive and the quality of the final triangle distribution, but if so I can't remember what it is. Maybe someone else can offer some input on that.

Quote:

Original post by mike74 MrRowl, can you please point me to some simple code that creates the convex hull? My understanding was that it's not that simple.

Well, it was pretty simple when I coded it up a few months ago - not super trivial but only took a couple of hours to write and test. I don't have the details now, so I'm sure you can do the web searches as easily as me. Alternatively, I expect you can find some existing implementation you can just use, if you wanted to go this way.

Wow, two hours that's pretty good, two hours for you is 20 for us the rest of the mortals, I can spend that for a good tool.

Quote:

Original post by jyk Quote: Out of curiosity, why did you decide to use an icosahedron? It seems like a tetrahedron is sufficient for a great sphere. No reason, and I may switch to some other primitive in the future. There may be some correlation between the choice of initial primitive and the quality of the final triangle distribution, but if so I can't remember what it is. Maybe someone else can offer some input on that.

the icosahedron is the regular primitive with the largest number of triangles. this means that each individual triangle covers the least amount of sphere possible, therefore having minimal curvature. as you start subdividing the base triangles, the amount of warping/nonuniformity youll get depends on the curvature of the original triangle.

Make some from different shapes, and take a look at them. Basically, although the points of the resulting sphere will all lie on the surface, they will not be evenly distributed, but the more evenly distributed points you start with the less distortion you will have at the end. The distortion is quite visible in wire frame, and focuses on the original triangle tips, where there will be less edges to the vertex than everywhere else (every vertyex of a sub divided sphere has 6 edges attached, except the original vertices, which have 3 for a tetrahedron, 4 for an octahedron, and 5 for a icosahedron).

I don't recommend a tetrahedron - an octahedron is the easiest shape to start from (points at (0,0,1) (0,1,0) (1,0,0) (0,0,-1) (0,-1,0) (-1,0,0) )

There is an icosahedron example program complete with code here: http://www.sulaco.co.za/tut.htm

Just one question about the point distribution... It seems to me that the way I subdivided leads to triangles on the surface of only two sizes - one big size with three small ones around it. So, the distribution shouldn't be too far from uniform. Here's my code:

// this is a helper function for createsphere
// if you just want to make a sphere, just call createsphere
vector spherehelper(vector triangles)
{

vector newtriangles;
vector::iterator i = triangles.begin();

while (i != triangles.end()) {
Triangle t = *i++;
Vector a = t.v0, b = t.v1, c = t.v2;
Vector v1 = buildvector(a[0]+b[0], a[1]+b[1], a[2]+b[2]);
Vector v2 = buildvector(a[0]+c[0], a[1]+c[1], a[2]+c[2]);
Vector v3 = buildvector(b[0]+c[0], b[1]+c[1], b[2]+c[2]);
v1.normalize();
v2.normalize();
v3.normalize();
Triangle newt(a, v1, v2);
newtriangles.insert(newtriangles.end(), newt);
newt = Triangle(c, v2, v3);
newtriangles.insert(newtriangles.end(), newt);
newt = Triangle(b, v3, v1);
newtriangles.insert(newtriangles.end(), newt);
newt = Triangle(v1, v3, v2);
newtriangles.insert(newtriangles.end(), newt);
}

return newtriangles;
}


// levels specifies how many levels of detail we will have
// levels should be 0 or greater
// there will be 4^(levels+1) faces in there sphere
vector createsphere(int levels)
{
vector triangles;

// build a tetrahedron
Vector v0 = buildvector(0.0, 0.0, 1.0);
Vector v1 = buildvector(2.0*sqrt(2.0)/3.0, 0.0, -1.0/3.0);
Vector v2 = buildvector(-sqrt(2.0)/3.0, sqrt(6.0)/3.0, -1.0/3.0);
Vector v3 = buildvector(-sqrt(2.0)/3.0, -sqrt(6.0)/3.0, -1.0/3.0);

Triangle t;
t = Triangle(v0, v1, v2);
triangles.insert(triangles.end(), t);
t = Triangle(v0, v2, v3);
triangles.insert(triangles.end(), t);
t = Triangle(v0, v3, v1);
triangles.insert(triangles.end(), t);
t = Triangle(v1, v3, v2);
triangles.insert(triangles.end(), t);

for (int ctr = 0; ctr < levels; ctr++) triangles = spherehelper(triangles);

return triangles;
}


Please let me know if you think there are only triangles of two sizes.


mike
http://www.coolgroups.com/

No comment on the algorithm - but that code is _horribly_ inefficient simply from the point of view of (a) passing a std::vector by value (not const reference) many times in the loop and (b) returning the result by value (not reference), invoking memory allocations and copies all over the place.

Can we see your convex hull code, mrrowl?

mike
http://www.coolgroups.com/

There is an example on the OpenGL Red book for building an Icosahedron (look for "An Example: Building an Icosahedron" on the page I linked), based on that example you can create an iterative algorithm to subdivide triangles on a tetrahedron (not good looking) or octahedron (IMO the best shape for building a sphere), to get a smoth sphere.

Hope that helps.

Quote:

Original post by mike74 Can we see your convex hull code, mrrowl?

No, sorry, because I wrote it for work. It's simplified in this case though, because you know that every point will end up on the convex hull. I used the "gift wrap" algorithm - e.g. http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
because it's easy (I think I pretty much used brute-force on every lookup I needed to do) and this part wasn't a speed bottleneck.

Another suggestion is to have a number of base objects - octahedron, icosahedron maybe even cube octahedron (split the square faces). Then when you want to generate a sphere approximation with N faces chose the base object that will give you closest to this (or >= N or whatever) when subdivided.

There's another way too - faster than triangulation, maybe faster than recursive subdivision, and reasonably flexible too. Let's say you want your triangles to have side length l, and the sphere radius is R. Calculate an angle a so that the angle generates a distance l on a great circle - i.e.
a / 360 = l / (2*PI*R)
in degrees.

Now start at the top of the sphere (latitude = 90) - make a single vertex there.

Next, latitude -= a - i.e. move down slightly. Walk around the sphere (starting at longitude = 0), making a vertex every "a" degrees. Triangulate as you go - in this case just generate a triangle fan around the polar vertex.

Next, latitude -= a. Do the same thing as above - but this time triangulate the new vertices with the previous ones. Since you'll have more vertices than before as you progress you need to choose the 3 vertices to triangulate each time carefully - doesn't matter if you don't choose perfectly but make sure it wraps around OK!

Continue until you get to the bottom cap.

Clearly you want to tweak the "a" value so that the sphere is symmetrical about the two halves (i.e. 180/a is an integer). You can estimate the total number of triangles that will be generated for a given side length by using the sphere surface area and the area of each individual triangle (assume that on average they're equilateral).

Hope this makes sense... It won't generate a perfect triangulation, but it will be pretty good - certainly good enough for rendering.

Ok, thanks for the tips. On a slight tangent, I should mention that a lot of the copying in my code is because I wanted to get it working quickly, and I wasn't sure what happens to a vector::iterator when you add/delete triangles to the vector. If you add a triangle to the vector after you start iterating, will the iterator go over it?

mike
http://www.coolgroups.com/