Archived

This topic is now archived and is closed to further replies.

davekerr

Subdividing polygons

Recommended Posts

Hi there, i''m writing a 3d modeling app, and my polygon class has a large vertex array, and an array of ''faces'' which are each just arrays of indexes into the array. This is the most common 3d poly class implementation i''ve seen, and i''ve been trying to add some simple functions to my app. i''ve got ''triangulate'' working really well, and i wrote the algorythm by hand and spent ages getting it really fast (it is used on nearly every object by my render engine). however, could anyone tell me where to go, or give me any information on subdiving the faces of a polygon? i don''t have a clue how to do this... if this is really simple maths, i''m sorry, but i''m 15 and haven''t even taken my maths GCSE yet, and the fact that i''m writing some 3d modeling software at all is bizarre enough... thanks in advance!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Subdividing them into triangles?

One way is to make a triangle fan out of your polygon.

Pick one vertex. All your triangles will contain this vertex. Then select consecutive pairs around your polygon (You''ll need to know which are adjacent vertexes) going clockwise from your picked vertex, until you get all the way around the polygon. This will make a ''fan'' of triangles. (Which can be rendered quickly by openGL or directX)

Share this post


Link to post
Share on other sites
The key for most tesselations is performing them on EDGES. So i suggest you incorporate edge array into your model class as well, in addition to vertices and faces.
So when subdividing a triangle, you can just split one of the edges to half, thus producing one new vertex and three new edges ( two halves of the original, and one from the opposite corner of triangle) and discarding the old one you split.
For fastest operations its best to keep two-way pointers from each data unit ( vertex, edge and face )
In consistent model ( no disjoint vertices ) you will always have:
Polygon has 3..n *vertices, and 3..n *edges
Vertex has 1..n *polygons, and 2..n *edges
Edge has exactly 2 vertices, and 1..n polygons

Now for actual triangle splitting you can use some different methods. The one i described above: splitting one edge, creating new vertex in the middle of edge. If the edge is shared by other triangles, those will have to be split too.
Or, you can create new vertex in the middle of triangle, thus forming three new edges.
The nicest method is to split all three edges of triangles, creating three new vertices, three new edges and potentially forcing splitting of quite a lot of adjacent polygons.

Note that array of edges doesnt have to be saved along with model, you can rebuild it from face info when you need it. Edge information is not necessary for solid rendering either, but can be useful when rendering wireframe.

Share this post


Link to post
Share on other sites