Important: Brevity disclaimer.

Intro

It’s often the case with triangulated models that due to some reason the number of triangles in the model is higher than needed. Possible reasons include:

• Importing model from CAD representation with too high detail settings or with “dumb” triangulation routine that is not able to perform smart enough triangulation.
• Converting some external model representation (such as point cloud representation or stacked images representation, for example after CT scanning) into triangulated representation.
• Necessity to apply to triangle model some complex algorithm that is just not able to cope with large number of triangles.

In any case, the solution to this problem is typically to run reducer algorithm that will decrease the number of triangles in the mesh while keeping introduced geometric error as small as possible.

The reducing task is well-studied area of computational geometry research - there are a lot of known approaches that give excellent results.

However, it does not mean the task is easy or trivial - there are a lot of factors which make it complex to implement:

• Huge input data: the reducing algorithm should be designed from the ground up with the possibility to take at the input as large input models as possible, after all this is why people need reducing at all. This requirement implies very strict bounds on time and memory algorithm can use.

  The algorithm used in Materialise during some experiments was able to reduce models with number of triangles close to ten millions on average hardware.

• Geometric error control: typically customer wants to place quite restrictive limit on allowed geometric error during reducing, as typically there’s some upper bound of geometric error which the whole processing chain may not violate.

• Control over special surface features: it’s often the case that besides geometric error user wants to minimize model features distortions according to some special criteria, such as “preserve sharp corners of model”, or “preserve the boundary between different models areas”.

All these challenges were solved successfully during reducing algorithm implementation for Materialise.

Female Model Reducing

Model is courtesy of Cyberware, Inc.

Original model

There are 717784 triangles in this model.

Reduced model

There are 113784 triangles in reduced model. Processing time was close to 10 seconds on AMD Athlon64 3800+ CPU with 2 Gb of RAM.

Original model (close up)

Please note regular pattern of triangulation, produced by scanner software.

Reduced model (close up)

Please note that now triangles are distributed non-uniformly: smaller triangles at regions with high curvature and larger ones at flat regions, also triangles edges are collinear with models features.