Jump to content
  • Advertisement
Sign in to follow this  
mike74

sphere triangulation

This topic is 4830 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

Does anyone know the easiest way to triangulate a sphere? I think it may be possible to turn a tetrahedron into one, but I'm not sure. I'm also not sure if there may be something easier or not. Thanks. mike http://www.coolgroups.com/

Share this post


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

Share this post


Link to post
Share on other sites
Is your icosahedron difficult to calculate? The dictionary says it has 20 faces.

mike
http://www.coolgroups.com/

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

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!