Triangular mesh generation of octrees of non-convex 3D objects

Dongjoe Shin, Tardi Tjahjadi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A general surface-generating algorithm, the marching cube, produces triangular meshes from octants where the vertices of octants are clearly classified into either inside or outside the object. However, the algorithm is ambiguous for octrees corresponding to non-convex objects generated using a shape from silhouette technique. This paper presents a methodology which involves Delaunay triangulation to generate surface meshes for such octrees. Since the general 3D Delaunay triangulation creates 3D convex hull which consists of tetrahedron meshes, we propose a method which applies the Delaunay algorithm locally in order to deal with non-convex objects. The proposed method first slices an octree and detects the clusters in each slice. All clusters between adjacent slices are linked based on a 3D probability density cube. The Delaunay algorithm is then applied to locally-linked clusters. Finally the accumulation of triangular meshes forms a final non-convex surface mesh.
Original languageEnglish
Title of host publication18th International Conference on Pattern Recognition (ICPR'06)
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)0-7695-2521-0
Publication statusPublished - 18 Sept 2006
Externally publishedYes
EventInternational Conference on Pattern Recognition - Hong Kong, United Kingdom
Duration: 20 Aug 200624 Aug 2006

Publication series

NameIEEE ICPR Proceedings Series
ISSN (Print)1051-4651


ConferenceInternational Conference on Pattern Recognition
Abbreviated titleICPR2006
Country/TerritoryUnited Kingdom
CityHong Kong


Dive into the research topics of 'Triangular mesh generation of octrees of non-convex 3D objects'. Together they form a unique fingerprint.

Cite this