International Journal of Image, Graphics and Signal Processing (IJIGSP)
IJIGSP Vol. 6, No. 2, 8 Jan. 2014
Cover page and Table of Contents: PDF (size: 484KB)
Modified Streaming Format for Direct Access Triangular Data Structures
Full Text (PDF, 484KB), PP.14-22
Views: 0 Downloads: 0
Author(s)
Index Terms
Triangular data structure, Streaming format, Direct access structure
Abstract
We define in this paper an extended solution to improve an Out-of-Core data structure which is the streaming format, by adding new information allowing to reduce file access cost, reducing the neighborhood access delay to constant time.
The original streaming format is conceived to manipulate huge triangular meshes. It assumes that the whole mesh cannot be loaded entirely into the main memory. That's why the authors did not include the neighborhood in the file structure.
However, almost all of the applications need the neighborhood information in the triangular structures. Using the original streaming format does not allow us to extract the neighborhood information easily. By adding the neighbor indices to the file in the same way as the original format, we can benefit from the streaming format, and at the same time, guarantee a constant time access to the neighborhood.
We have adapted our new structure so that it can allow us to apply our direct access algorithm to different parts of the structure without having to go through the entire file.
Cite This Paper
Khaled Abid,Abdelkrim Mebarki,Wahid Hidouci,"Modified Streaming Format for Direct Access Triangular Data Structures", IJIGSP, vol.6, no.2, pp.14-22, 2014. DOI: 10.5815/ijigsp.2014.02.02
Reference
[1]Bruce G. Baumgart. Winged edge polyhedron representation. Technical report, Stanford University, Stanford, CA, USA, 1972.
[2]Bruce G. Baumgart. Winged-edge polyhedron representation for computer vision. In National Computer Conference, May 1975.
[3]Bruce Guenther Baumgart. Geometric Modeling for Computer Vision. PhD thesis, Stanford University, USA, August 1974.
[4]Swen Campagna, Leif Kobbelt, and Hans-Peter Seidel. Directed edges a scalable representation for triangle meshes. Journal of Graphic Tools, 3(4):1–11, 1998.
[5]Luca Castelli Aleardi. Repr′esentations Compactes de Structures de Donn′ees G′eom′etriques. PhD thesis, Ecole Polytechnique, Palaiseau, France, December 2006.
[6]Cgal: Computational geometry algorithms library. www.cgal.org.
[7]Paolo Cignoni, Claudio Montani, Claudio Rocchini, and Roberto Scopigno. External memory management and simplification of huge meshes. IEEE Transactions on Visualization and Computer Graphics, 9(4):525–537, 2003.
[8]Leila De Floriani, Leif Kobbelt, and Enrico Puppo. A survey on data structures for level-of-detail models. In N. A. Dodgson, M. S. Floater, and M. A. Sabin, editors, Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pages 49–74. Springer, Berlin, Heidelberg, 2005.
[9]Michael Garland. A multiresolution representation for massive meshes. IEEE Transactions on Visualization and Computer Graphics, 11(2):139–148, 2005. Student Member-Eric Shaffer.
[10]Leo J. Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams. In STOC ’83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 221–234, New York, NY, USA, 1983. ACM Press.
[11]Martin Isenburg and Peter Lindstrom. Streaming meshes. In Proceedings of the 16th IEEE Visualization Conference (VIS 2005), 23-28 October 2005, Minneapolis, MN, USA, page 30. IEEE Computer Society, 2005.
[12]Marcelo Kallmann and Daniel Thalmann. Star vertices: A compact representation for planar meshes with adjacency information. Journal of Graphics Tools, 6(1):7–18, 2001.
[13]Michael J. Laszlo. Computational Geometry and Computer Graphics in C++. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995.
[14]P. Lienhardt. Subdivisions of n-dimensional spaces and n dimensional generalized maps. In SCG ’89: Proceedings of the Fifth Annual Symposium on Computational geometry, pages 228–236, New York, NY, USA, 1989. ACM Press.
[15]Peter Lindstrom. Out-of-core simplification of large polygonal models. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 259–262, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
[16]Abdelkrim Mebarki. Implantation de structures de donn′ees compactes pour les triangulations. PhD thesis, Universit′e de Nice-Sophia Antipolis, France, April 2008.
[17]Dinesh P. Mehta and Sartaj Sahni. Handbook Of Data Structures And Applications. Chapman & Hall/Crc Computer and Information Science. Chapman & Hall/CRC, 2004.
[18]David E. Muller and Franco P. Preparata. Finding the intersection of two convex polyhedra. Theor. Comput. Sci., 7:217–236, 1978.
[19]Franco P. Preparata and Michael I. Shamos. Computational geometry: an introduction. Springer-Verlag New York, Inc., New York, NY, USA, 1985.
[20]Hanan Samet. Applications of Spatial Data Structures: Computer Graphics, Image processing, and GIS. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1990.
[21]Hanan Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1990.
[22]Robert Sedgewick. Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1984.
[23]C. Silva, Y. Chiang, J. El-Sana, and P. Lindstrom. Out-of-core algorithms for scientific visualization and computer graphics. In IEEE Visualization conference’02. Boston, Massachusets. Course Notes, October, 2002.
[24]Jianhua Wu and Leif Kobbelt. A stream algorithm for the decimation of massive meshes. In Graphics Interface, pages 185–192. CIPS, Canadian Human-Computer Commnication Society, A K Peters, June 2003. ISBN 1-56881-207-8, ISSN 0713-5424.