Jump to content
  • Advertisement
Sign in to follow this  
staticVoid2

face triangulation in .x

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

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
Advertisement
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
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 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
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!