Cliff Bowman wrote:
> 
> Some .OBJ faces comprise more than 4 points. I've successfully tested
> turning 4 points into 2 triangles, and this seems to work well. Does
> anyone know how to reliably turn faces with more points into triangle
> meshes? Or has anyone happened on a procedure which "happens to work"
> (like my 1,2,3 - 3,4,1 procedure for 4-point faces)?

Polygon triangulation is a pretty well-studied problem in computational
geometry.  Any textbook on computational geometry ought to have a
lengthy discussion of the topic.  Most of that is overkill, though.

If the polygons are convex, the simplest approach I know of is: 

-pick a point arbitrarily and call it 1
-number the rest of the points around the edge of the polygon as you did
previously, but keep going beyond 4
-divide the face up so it looks rather like a clamshell, with an edge
running from 1 to each of the other vertices
-triangles are <1,2,3>, <3,4,1>, <1, 4, 5>, <5, 6, 1> ...

If the polygons are not convex, recursively lop off pointy bits as
triangles until they are.  There's a bit of hand-waving there, but I'm
trying to wave my hand in the direction of the literature if you need
that kind of detail (not sure you do).

There are some efficiency concerns that are addressed in the literature,
but they are mostly of use to 2-D graphics, where polygons with large
numbers of vertices are used to approximate 2-D curves.  In 3-D
graphics, one seldom sees more N-gons with N>6 (except when the big 2-D
curve approximations get ducted, but that's an isolated case).

-- 
Mark Gordon
mtg### [at] povrayorg

Post a reply to this message