Premium
A Graph–Based Approach to Surface Reconstruction
Author(s) -
Mencl Robert
Publication year - 1995
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.1995.cgf143_0445.x
Subject(s) - euclidean minimum spanning tree , computer science , graph , regular polygon , surface (topology) , surface reconstruction , object (grammar) , computer vision , euclidean geometry , set (abstract data type) , spanning tree , artificial intelligence , computer graphics (images) , mathematics , theoretical computer science , combinatorics , geometry , minimum degree spanning tree , programming language
A new approach to the reconstruction of a surface from an unorganized set of points in space is presented. The point set may for example be obtained with a laser scanner or a manual digitizing tool, and is the only source of information about the shape of the acquired object. The basic idea is to calculate the Euclidean minimum spanning tree (EMST) of the given points. The EMST is then augmented to the so‐called surface description graph (SDG). Finally the wire frame defined by the SDG are filled with triangles. The advantage of our approach is that also highly non‐convex and even disconnected surfaces are reconstructed quite reliably. This is demonstrated for a variety of data sets.