On the development of a surface-based triangulation algorithm for 3D cloud points

Jiing Yih Lai, Chen Tung Chi, Wen Der Ueng

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We proposed an algorithm for the triangulation of 3D cloud points. It was essentially a surface-based approach, but with several new concepts to overcome the computational and memory problems in the available algorithms. We proposed a complete data structure to record the connectivity information among the triangular elements and the cloud points. A subdivision algorithm was proposed also to assign each cloud point into an appropriate cell so as to reduce the search required. A rule-based triangulation process was proposed for the growing of new triangles. Six types of triangles were created based on the relationship between the best point and the existing elements. The computational speed of the proposed algorithm was quite efficient. Several examples were provided to demonstrate the feasibility of the proposed algorithm for data up to several hundred thousand points.

Original languageEnglish
Pages (from-to)309-320
Number of pages12
JournalJournal of the Chinese Society of Mechanical Engineers, Transactions of the Chinese Institute of Engineers, Series C/Chung-Kuo Chi Hsueh Kung Ch'eng Hsuebo Pao
Issue number3
StatePublished - 2005


  • Reverse engineering
  • STL data
  • Triangulation


Dive into the research topics of 'On the development of a surface-based triangulation algorithm for 3D cloud points'. Together they form a unique fingerprint.

Cite this