Direct repair of self-intersecting meshes

A fast and exact algorithm to eliminate intersections from arbitrary triangle meshes is presented, without any strict requirement on the input. Differently from most recent approaches, our method does not rely on any intermediate representation of the solid. Conversely, we directly cut and stitch mesh parts along the intersections, which allows to easily inherit possible surface attributes such as colors and textures. We rely on standard floating point arithmetics whenever possible, while switching to exact arithmetics only when the available fixed precision is insufficient to guarantee the topological correctness of the result. Our experiments show that the number of these switches is extremely low in practice, and this makes our algorithm outperform all the state-of-the-art methods that provide a guarantee of success. We show how our method can be exploited to quickly extract the so-called outer hull even if the resulting model is non manifold by design and the single parts have boundaries, as long as the outer hull itself is unambiguously definable. (C) 2014 Elsevier Inc. All rights reserved.