SURFACE TOPOLOGY AND GEOMETRY RECONSTRUCTION FROM WIRE-FRAME MODELS

A method, a system, and a program product for reconstructing surface geometry from discrete points on an object are disclosed. The method comprises steps of; providing input data derived from said discrete points; generating a graph from said input data, said graph including biconnected graphs; subjecting said graph to triconnected component decomposition to generate a component graph; generating all possible embeddings including possible face loops from said surface geometry; filling said possible face loops with possible surface to reconstruct said surface geometry; examining geometrical acceptance of said surfaces and omitting embeddings, including at least one geometrically unacceptable surface from computation thereafter and scoring said embeddings depending on said examination; and sorting said embeddings with respect to said scores to select embeddings for reconstructing said surface geometry.