Robust Interior

Abstract

The use of 3D models has been rapidly expanding, finding applications in both scientific and commercial fields. One common requirement for these various applications is the geometrical and topological validity of these models. However, many models available online contain deficiencies in various forms, such as duplicated geometry, gaps in the surface, etc.. To cope with those deficiencies, a standard solution is the clean extraction of the model’s boundary, and simultaneously the model’s reconstruction in a way that its structure is valid. This thesis tackles a more generalized problem, the inside-outside classification for these models. Where many approaches might have requirements for running analysis, the methodology presented strives to robustly handle all cases. These last decades, there have been various approaches in solving the ”inside - outside classification problem”. A major attempt utilizes the winding number algorithm, in order to assign values to elements whose position is relevant to the input model. By assessing that value, a decision on whether the element in question is interior or exterior is taken. Other approaches work with casting rays, or other geometric analysis to also identify the borders of a model and segment the interior from the exterior. Also, since deficiencies inhibit the kick-starting of the necessary analysis, there are methods that try to restructure said models in order to clear any existing deficiencies. The methodology within this thesis will attempt a different approach from those that have been presented until now, which is transferring the problem from three into two dimensions. The first step is introducing a planar cross section on the area of interest. From there, through some graph reconstruction, geometric and optimization applications, a valid 1-manifold boundary of the cross-section is created. On that, the application of inside-outside classification through ray casting is possible. Assessing the results of the pipeline proves that the automated process can produce valid results, for a particular point of interest, related to an input model. The pipeline has been proven to function regardless of the cutting plane’s orientation, and can handle robustly a multitude of geometrically and topologically defective models. The results from this thesis can inspire further applications, and improvements on the pipeline can further evolve the quality of its outcome.