Tessellation of IGES Files

For the last couple of days, I’ve finally picked up working on the tessellator code again. After dealing with other parts of the software, the rest of the app now works so nice that the tessellator became the limiting factor. The lesson of the day is: if you want to write a good tessellator, start thinking about writing a good set of repair methods! Or as an ex-colleague of mine used to say, “shit in shit out”.

I had written the basic tessellation code a couple of months ago but back then there were a lot of problems when running it on my various test files. Some were related to the n-gon-based approach: the tessellator produces a mesh but I explicitly didn’t want it to produce triangles but n-gons. While this is algorithmically more challenging, n-gons will help when a user wants to continue modeling instead of just using the tessellation for visualization purposes. Anyway, the tessellator worked fine but the code that generates triangles from the n-gons failed as soon as shapes got complicated. So I spent a lot of time making the triangulation code robust.

Still, after fixing the triangulation algorithm, there were a lot of cases where the tessellator produced weird results. As it turns out, most of those problems were actually caused by corrupt data. IGES contains multiple ways to express a trimmed surface, namely:

• Entity 186 (Manifold Solid B-Rep Surface)
• Entity 143 (Bounded Surface)
• Entity 144 (Trimmed Parametric Surface)

While 186 (and the shells, faces, loops inside it) have a definition of curve orientation, 143 & 144 just specify the curves and one has to figure out the correct trim curve orientation oneself. In addition to this, some programs seem to have faulty exporters and trim curves are not only in random orientation, they might also appear in random order within a trim loop!

So I wrote code that corrects inconsistent trim curve orientations, loop orientations and fixes various other NURBS trimming issues. And while there are still some problems, the percentage of faces that work correctly has grown exponentially for the last few days. One of the reasons for the good progress is that I wrote various exporters (OFF, OBJ, STL, IGES), isolated problematic faces and coded unit tests to cover them. This makes for quick turnaround times and ensures that fixing one bug will not re-introduce one fixed earlier.

There are still a few corrupt faces left but the even more limiting factor right now is that a lot of CAD files use entities 143 & 144 which express isolated trimmed surface without any topological information (e.g. tessellation produces cracks between the faces). I guess in addition to the current B-Rep repair code, I’ll also have to write topology repair code.