Important: Brevity disclaimer.

Intro

This project was done for the customer who needed to perform punching of models with very big number of small holes uniformly distributed over model surface. There were several technical challenges in this project:

• Very large output data: triangles count of input model is typically increased in 50-100 times, so having at the input models with tens of thousands of triangles easily produces several millions of triangles at output.
• Robustness problems: as in some way the task is similar to general 3D boolean task, the same robustness problems that are important for 3D boolean apply here: it’s not possible to use inexact calculations due to critical influence any computation / classification error may have on the end result.
• Portability: target platform was Linux, while development was done on Win32.

In the beginning I attempted to split the whole task in “common” way to sub-tasks of generating punching prisms and then performing 3D boolean between these prisms and original mesh, but it soon appeared that all existing solutions for 3D boolean are inadequate here: some of them are just not robust enough, while others are not designed to cope with that large output.

Therefore, task decomposition was adapted, taking into account very simple, but quite powerful concept: exact holes positions are not important here - thus, instead of evident, but complex approach with placing holes first and then performing boolean with fixed holes positions, we “merge” these two phases by taking into account potential problems retriangulation routine may have at holes placement stage - so that holes placement routine for each potential hole position “asks” retriangulation routine whether it is able to retriangulate this hole, and if not - tries to put hole at some other place.

Having flexibility to refuse retriangulating the particular hole and, thus, excluding all complex and degenerate cases, the design and implementation of retriangulation stage simplifies greatly.

GNU Triangulated Surface Library was used as the kernel library for mesh storage and operations, as well as for Constrained Delaunay Triangulation, which formed the central part of retriangulation code.

Used software and technologies: GTS Library; WildMagic Library; boost library.

Here is one example of the program execution.

Original model

There are 31954 triangles in this model.

Punched model

There are 1350338 triangles in this model, number of punched holes is 56927. Processing time was close to 2 minutes on AMD Athlon64 3800+ CPU with 2 Gb of RAM, memory peak was close to 450 Mb.

Punched model close-up