Sign in to follow this  
staticVoid2

face triangulation in .x

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 this post


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

ABC
ACD
ADE
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
For polygon ABCDEF, you want to make triangles:

ABC
ACD
ADE
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.


thats a naive triangulation you suggest there

I suggest you to apply the delaunay operator to this triangulation

Share this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
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.


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

Free Image Hosting at www.ImageShack.us
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.

Free Image Hosting at www.ImageShack.us
(the monkey from blender, without hidden surface removal)

Share this post


Link to post
Share on other sites
Quote:
Original post by staticVoid2
Quote:
Original post by speciesUnknown
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.


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

Free Image Hosting at www.ImageShack.us


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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this