Partial surface reconstruction

Question

I need an algorithm to repair 3D triangular meshes. The desired condition is that 2n triangles (most of the time 2 triangles) share an edge. In contrast the input meshes contain cases with 2n+1 triangles (1,3,..) at an edge . I have implemented some heuristics:

• Close vertices (due to rounding errors) are merged into one.

• Border edges are split if afterwards the new vertex can be merged with a resonable other one.

• Holes are triangulated up to some area threshold.

This works quite well for many inputs (I care about selfintersections in a later stage), but there are meshes where these heuristics fail. The main problem is that repairing an edge is not a decision with just local consequences: Each created triangle reduces the set of edges available for the subsequent repair steps. Thus, just one bad decision may lead to a chain of consecutive faults.

This problem seems close to the surface reconstruction problem, but I have already most of the surface, so a partial reconstruction algorithm is needed which respects the existing triangles. Any ideas?

Answer 1

Rather than making triangle creation irreversible, you could do a limited combinatoric exploration, dynamic-programming style. You could assign a cost to each operation (and possibly also to the outcomes), to evaluate which combinations are most promising at any given stage.

Presumably most cases would be localized, and would not need the full power (and expense) of dynamic programming. However, cases requiring multiple dependent operations could be explored in parallel, and the best semi-local solution selected from among those that achieve closure.