A Novel Contour Generation Algorithm for Surface Reconstruction from Dexel Data


This paper presents a method of reconstructing a triangular surface patch from dexel data generated by ray casting to represent solid models for applications, such as virtual sculpting and numerically controlled (NC) machining simulation. A novel contour generation algorithm is developed to convert dexel data into a series of planar contours on parallel slices. The algorithm categorizes the dexels on two adjacent rays into different groups by using a “grouping” criterion. The dexel points in the same group are connected using a set of rules to form subboundaries. After checking the connections among all the dexel points on one slice, a connection table is created and used to obtain the points of connection in a counterclockwise sequence for every contour. Finally, the contours on all the parallel slices are tiled to obtain triangular facets of the boundary surface of the 3D object. Computational costs and memory requirements are analyzed, and the computational complexity analysis is verified by numerical experiments. Example applications are given to demonstrate the described method.


Mechanical and Aerospace Engineering

Keywords and Phrases

Computational Geometry; Ray Tracing; Surface Reconstruction

Document Type

Article - Journal

Document Version


File Type





© 2007 American Society of Mechanical Engineers (ASME), All rights reserved.

Publication Date

01 Sep 2007