Article | Proceedings of SIGRAD 2010: Content aggregation and visualization; November 25–26; 2010; Västerås; Sweden | On the Quality of Point Set Triangulations based on Convex Hulls

Title:
On the Quality of Point Set Triangulations based on Convex Hulls
Author:
Peter Jenke: Anders Hast: Avdelningen för visuell information och interaktion, Institutionen för informationsteknologi, Uppsala universitet, Sweden Stefan Seipel: Avdelningen för visuell information och interaktion, Institutionen för informationsteknologi, Uppsala universitet, Sweden
Download:
Full text (pdf)
Year:
2010
Conference:
Proceedings of SIGRAD 2010: Content aggregation and visualization; November 25–26; 2010; Västerås; Sweden
Issue:
052
Article no.:
012
Pages:
71-74
No. of pages:
4
Publication type:
Abstract and Fulltext
Published:
2010-11-29
ISBN:
978-91-7393-281-3
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


Export in BibTex, RIS or text

In this paper we describe a method for directly generating triangle strips from unstructured point clouds based on onion peeling triangulation (OPT). It is an iterative reconstruction of the convex hulls of point clouds in the 2D plane; and it uses pairs of subsequent layers to establish triangle strips. We compare the obtained triangulations with the results of Delaunay triangulations in terms of the distribution of the symmetry of obtained triangles and in regard to the number of polygons/vertices emitted. Our initial results show that onion peeling is a straightforward method to directly obtain large triangle strips of point clouds. As expected; the triangulation is not as well behaved as in Delaunay-triangulation [VK07]. In terms of triangle complexity and average strip length OPT is a very favorable triangulation alternative which also lends suitable for the triangulation of 3D point clouds.

Keywords: Surface reconstruction; triangle strip; convex layers; rotating calipers

Proceedings of SIGRAD 2010: Content aggregation and visualization; November 25–26; 2010; Västerås; Sweden

Author:
Peter Jenke, Anders Hast, Stefan Seipel
Title:
On the Quality of Point Set Triangulations based on Convex Hulls
References:

[AHMS94] ARKIN E.; HELD M.; MITCHELL J.; SKIENA S.: Hamiltonian triangulations for fast rendering. In Algorithms – ESA ’94; van Leeuwen J.; (Ed.); vol. 855 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg; 1994; pp. 36– 47. 10.1007/BFb0049395. 1


[BRS05] BOUBEKEUR T.; REUTER P.; SCHLICK C.: Surfel stripping. In GRAPHITE ’05: Proceedings of the 3rd internationalconference on Computer graphics and interactive techniques in Australasia and South East Asia (New York; NY; USA; 2005); ACM; pp. 177–186. 1


[Cha85] CHAZELLE B.: On the convex layers of a planar set. IEEE Transactions on Information Theory IT-31; 4 (1985); 509– 517. 1


[GE04] GOPI M.; EPPSTEIN D.: Single-strip triangulation of manifolds with arbitrary topology. Computer Graphics Forum (EUROGRAPHICS) 23; 3 (2004); 371–379. 1


[Tou83] TOUSSAINT G.: Solving geometric problems with the rotating calipers. In Proceedings of IEEE MELECON ’83 (1983); pp. 10–17. 1


[Tou86] TOUSSAINT G.: New results in computational geometry relevant to pattern recognition in practice. In Pattern Recognitionin Practice II (1986); Gelsema E.; Kanal L.; (Eds.); pp. 135–146. 1


[VK07] VAN?E ?C EK P.; KOLINGEROVÁ I.: Comparison of triangle strips algorithms. Computers & Graphics 31; 1 (2007); 100 – 118. 1; 3

Proceedings of SIGRAD 2010: Content aggregation and visualization; November 25–26; 2010; Västerås; Sweden

Author:
Peter Jenke, Anders Hast, Stefan Seipel
Title:
On the Quality of Point Set Triangulations based on Convex Hulls
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment