Sorting vertices for a 3D mesh

Abstract

There are files on the Internet which describe 3D meshes that you'd like to use, but the vertices of the faces are by random chance sometimes arranged clockwise and sometimes counterclockwise. Some triangulation routines and some normal generators will freak out at such a mesh, producing visible faces sometimes on the outside of your object and sometimes on the inside - you will appear to have 'holes' in your rendered object. I describe a simple algorithmic approach to take care of this problem.

Real life example

An Internet site called "Science U" informs, among many other things, about Platonic and Archimedean solids. They show you these thingies in VRML and as Java applets. They also kindly give you the coordinates in .OFF format. You can find this stuff by searching Google for "Archimedean". I was hoping to use one of these meshes in an Anfy3d applet. I hand-transposed all the coordinates and face vertex lists into arrays in my program, rendered the solid and ended up with a lot of unsightly holes.

Assumptions

My approach only works when the meshed solid is what I call "very convex". This means that all faces must be fully or at least mostly visible from some point in the middle that you identify as the "center" without being obscured by other faces of the solid. Similarly, all the faces (in 2D, now) need to be convex as well. Essentially, no gaping chasms or crevasses in the outside topology. Of course, Platonic and Archimedean solids fulfill this requirement to a tee.

Approach

For each face:

1. Find the center of the face. Taking the average of the coordinates of all the vertices does the trick nicely. I'm going to call this midpoint P₀ and all of the original vertex points P₁, P₂, ... P_{(however-many)}.
2. Construct a transform that will rotate P₀ around the center of the solid such that P₀' lies at x=0 and y=0 (or x=0 and z=0, whichever coordinate system you prefer). The idea is to take the face from wherever it may be and to map it flat on to a "wall" in front of your "eyes", assuming that your "eyes" are at (0,0,0) or somewhere similarly convenient. The "wall" should end up mostly perpendicular to the vector from your "eyes" to the midpoint of the face as mapped onto this imaginary "wall".
3. "measure" (i.e. mathematically determine) the relative angles of all vectors drawn from P₀' (on the wall, of course) to each of the vertices (P_1', P₂', ... ) of the face. Sort the vertices such that the angles form an ascending sequence. This will put the vertices into counterclockwise order as seen from inside the object and clockwise from the outside.

Disclaimer

I'm a jack-of-all-trades programmer, not a mathematician. Thus,

• If none of the above, starting from "abstract", made any sense to you, then you probably have no use for this information. I'm sorry I wasted your time. I wrote this in the hope that some day some poor sod will have the same problems as I did, and will find this useful.
• There's probably a much more succinct way of saying what I just explained. To mathematicians, anyway. But then I suspect a mathematician would already know about this anyway.
• This method worked fine for me and I expect it to work fine for you if your application is similar to mine and you fill in the places where I covered ignorance with hand-waving. But if it doesn't work, or it seems to work and you construct an important building and it collapses, killing thousands, please bear in mind that this method comes with no guarantees whatsoever.