🔒 Locked

Polygon Triangulation

Started by Shael Jan 18, 2007 at 12:33 AM 1 replies 1.1k views

Original Post

Jan 18, 2007 at 12:33 AM

Hi, Does anyone have some easy to use polygon triangulation code? I'm trying to convert all the faces in Q3 BSP into triangles. I have a list of vertices which need organising into tri's. I need to do this so i can use it for trimesh collisions in physics libs like physx,newton,etc. I can't seem to find any decent code that would do this for me. Does anyone have any? Im under the impression there is none for straight 3D but only for 2D so it needs projecting back and forth? Cheers.

JoeJ

7,824

JoeJ

Jan 18, 2007 at 7:01 AM

Google for a method called "Ear cutting", that's easy to implement but the result is not optimal.
A problem that could happen is a triangle with a very short edge compared to the other two - gives bad normals.
I think there's no need to xform to 2d, because polys from bsp models are usually true flat.

Zipster

511

Zipster

Jan 18, 2007 at 8:57 AM

The polygons from a BSP model are also always convex, which makes this problem rather straightforward -- the concave cases are where you're likely to drive yourself insane. First put the points in order if they aren't already, either clockwise or counter-clockwise, relative to the polygon's plane. Name them v1, v2, v3, ..., vM, vN. The most trivial triangulation would then just be (v1,v2,v3), (v1,v3,v4), (v1,v4,v5), ..., (v1, vM, vN), where all triangles have the same winding as the original polygon. Note that the vertices also form a perfect triangle fan, so for rendering you can just feed them one after another into the API using triangle fan mode making sure to set the correct winding mode so that they're visible.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.