Solid Model Reconstruction of Wireframe CAD Models Based on Topological Embeddings of Planar Graphs

Abstract

This paper describes a robust and versatile method based on graph embedding for reconstructing a solid model from a wireframe model. The robustness and versatility of the conventional methods are limited in that: (1) most of them are heuristic and thus less robust, and (2) the rest, deterministic ones, can handle only small class of wireframes. Unlike the conventional methods, our approach is deterministic and covers a larger class of wireframes that are topologically 2-connected planar multigraphs. The class includes wireframes that can be interpreted as a closed two-manifold in multiple ways. The proposed algorithm consists of three steps: (1) all topological solutions are exhaustively generated using triconnected component decomposition; (2) the surface geometries for all the topological solutions are generated; and (3) the solutions are pruned down to geometrically valid ones. We also show the algorithm is extendable to the class of general planar multigraphs. The approach is characterized by generating the complete set of topological solutions without referring to the geometry of the wireframe, which makes the process free from geometric errors and instabilities. The algorithm is also fast, because even when there are many topological solutions, the total number of different faces is very small. The proposed approach provides a method for easy and intuitive geometric modeling as well as a conversion tool for legacy wireframes.