Quote:Original post by quasar3d
That bsp tree method is just overkill imho, and it will result in much more triangles than necessary.

Quote:Original post by grhodes_at_work

1) Choose one vertex of the polygon to be the local origin, O = (O.x, O.y, O.z).

2) Create a unit vector from O to the next vertex along an edge connected to O. Call the unit vector X = (X.x, X.y, X.z). This will be the direction of the X axis in the 2D plane in which you will be doing the triangulation

3) Find a unit normal vector to the polygon by taking X and any other edge that is not parallel to X and doing a cross product. (See articles here at gamedev or do a forum search to learn how to do a cross product). Call the normal Z = (Z.x, Z.y, Z.z).

4) Do another cross product, Y = Z cross X, and normalize it for good measure. (We need to make sure it has length 1.0).

5) Now, X and Y are the two directions that define the plane in which you will do the triangulation.

6) Form a 3 x 3 rotation matrix:

    [X.x X.y X.z]R = |Y.x Y.y Y.z|    [Z.x Z.y Z.z]

This is the so-called "world to object" rotation matrix, which maps vectors in world space into the coordinate system of interest, e.g., it converts vectors in world space into the coordinate system given by X, Y, and Z. The transpose of R is the object to world rotation matrix, which takes vectors in the object's space and maps them to the world. (The tranpose rules is only true if R contains no scaling factors...this one does not, since we made sure X, Y, and Z all had length 1.0).

7) Now, map all your polygon vertices:

V_mapped = R * (V_world_space - O)

8) Now that all your vertices are mapped, your V_mapped vectors *are* the 2D vertices you need! Just drop the Z coordinate!