# face triangulation in .x

This topic is 3934 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

hi, I'm trying to get the correct indices for each triangle of each face in the Mesh template(in .x files). Because you can specify how many face indices for each face I need a way to split these indices into groups of three where each group gives me the 3 correct indices for a triangle of that face. anyone know any algorithms for doing this?

##### Share on other sites
For polygon ABCDEF, you want to make triangles:

ABC
ACD
AEF

You are basically making a triangle with points N, N+1 and N+2, then removing point N+1 from the original shape. Repeat this until the shape has 3 points. This assumes a convex shape, of course.

##### Share on other sites
would this work in all cases, like if the list was in no order at all?

Edit:

I just realized it wouldn't if the list was unordered or if the polygon was concave.

##### Share on other sites
For a concave polygon you could first divide it into convex polygons, and then use the method above.

Also, how is it possible for the list of vertices to be unordered? If this was the case, you would need to find the order anyway before passing it to the graphics card. Maybe you mean something else by "unordered" and "list", although these are pretty common terms.

##### Share on other sites
Quote:
 Original post by speciesUnknownFor polygon ABCDEF, you want to make triangles:ABCACDADEAEFYou are basically making a triangle with points N, N+1 and N+2, then removing point N+1 from the original shape. Repeat this until the shape has 3 points. This assumes a convex shape, of course.

thats a naive triangulation you suggest there

I suggest you to apply the delaunay operator to this triangulation

##### Share on other sites
Quote:
 Original post by speciesUnknownFor a concave polygon you could first divide it into convex polygons, and then use the method above.Also, how is it possible for the list of vertices to be unordered? If this was the case, you would need to find the order anyway before passing it to the graphics card. Maybe you mean something else by "unordered" and "list", although these are pretty common terms.

if the list of vertices were not in any winding order:

I just wrote a function for processing the face data in the mesh template so that it would pre-calculate the triangles of each face and store them, it's working anyway, now I have to figure out a way to recalculate the MeshMaterialList face indices as I've created a totally new face array and the indices are for the old array.

(the monkey from blender, without hidden surface removal)

##### Share on other sites
Quote:
Original post by staticVoid2
Quote:
 Original post by speciesUnknownFor a concave polygon you could first divide it into convex polygons, and then use the method above.Also, how is it possible for the list of vertices to be unordered? If this was the case, you would need to find the order anyway before passing it to the graphics card. Maybe you mean something else by "unordered" and "list", although these are pretty common terms.

if the list of vertices were not in any winding order:

I'm glad to hear it worked. However, I still don't understand how you managed to draw the lines if you didn't know the winding order? The computer is unable to see a boundary when it has a list of vertices. Therefore, any polygon must have some form of rule for the order of the vertices.

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 13
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633692
• Total Posts
3013355
×