SURFACE RECONSTRUCTION FROM MULTI-VALUED GRID DATA

The paper presents a graph based combinatorial approach for reconstruction of multi- valued surfaces from the data given in the form of a grid. The input is assumed to be given in the form of a set of quintuplets (i,j,x,y,z) where (i,j) are the grid indices and (x,y,z) are the coordinates of the corresponding point. The given points are first grouped into the sets with identical i-values and sets with identical j-values. For each such set then a novel graph-based curve-fitting algorithm is employed which can generate curves with branch points and discontinuities. These sets of curves are then combinatorially matched to obtain networks of loops, which on tessellation gives the reconstructed surface. The illustrative examples demonstrate that even for apparently simple data set, a topologically wide variety of surfaces can be generated. The present method can handle single valued, multi-valued, manifold, non-manifold surfaces with or without holes.