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

This paper describes a versatile and robust method for reconstructing a solid model from a wireframe model. The problem can be viewed as a graph-embedding problem. However, most conventional methods are heuristic, while non-heuristic deterministic methods apply to only a small class of wireframes. 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. Our algorithm has three steps: first all topological solutions are exhaustively generated using triconnected component decomposition. After determining surface geometries for all solutions in the next step, they 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 empirically very small. The proposed approach provides an easy and intuitive method for inputting geometry as well as a conversion tool for existing wireframes.