UMD CMSC 828V - A Survey on Data Structures for Level-Of-Detail Models

Unformatted text preview:

A Survey on Data Structures forLevel-Of-Detail ModelsL. De Floriani1, L. Kobbelt2and E. Puppo11Department of Computer Science, University of Genova, Genova, Italy2Computer Graphics Group, RWTH Aachen University, Aachen, Germany,Summary. In this paper we survey some of the major data structures for encodingLevel Of Detail (LOD) models. We classify LOD data structures according to thedimensionality of the basic structural element they represent into point-, triangle-,and tetrahedron-based data structures. Within each class we will review single-leveldata structures, general data structures for LOD models based on irregular meshesas well as more specialized data structures that assume a certain (semi-) regularityof the data.1 IntroductionDue to the rapidly increasing complexity of three-dimensional data sets suchas geometric free-form shapes, terrain models or volumetric scalar fields, theinvestigation of hierarchical methods to control and adjust the Level Of Detail(LOD) of a given data set has been an active research area – and it still is. ALOD model essentially permits to obtain different representations of an objectat different levels of detail, where the level can also vary over the object. Theoperation of extracting one such representation from a LOD model is calledselective refinement and most applications require that it must be supportedeither in real time, or at least on-line for objects that often exhibit fairlycomplicated geometry. Performance requirements impose several challenges inthe design of systems based on LOD models, where geometric data structuresplay a central role. There is a necessary trade-off between time efficiency andstorage costs. And also there is a trade-off between generality and flexibilityof models on one hand, and optimization of performance (both in time andstorage) on the other hand.In this paper, we provide a survey of geometric data structures that havebeen proposed in the literature to implement LOD models. We consider free-form surfaces described through point primitives or triangle meshes and two-dimensional or three-dimensional scalar fields whose domain is partitionedinto meshes of triangles or tetrahedra. We consider mesh-based LOD modelsdescribed by hierarchies of meshes, which define the underlying discretiza-tion of the surfaces or of the domain of the field. In Section 2, we introducesome background notions on meshes and we give a generic definition of LODmodels. In Section 3, we review point-based data structures that process sur-face data without the need of explicitly constructing a mesh. In Section 4,2 L. De Floriani, L. Kobbelt and E. Puppowe focus on 3D objects represented with meshes of triangles and we describetriangle-based data structures in the three cases of plain geometric models,progressive models, and LOD models supporting selective refinement. In Sec-tion 5, we review, with a similar approach, tetrahedron-based data structuresused to represent volume data. Section 6 makes some concluding remarks.2 Background NotionsIn this Section, we introduce some background notions which we use in thepaper.2.1 MeshesA k-dimensional cell, or a k-cell, for brevity, is a subset of the d-dimensionalEuclidean space Edhomeomorphic to a closed k-dimensional ball, wherek ≤ d. Let M be a connected finite set of cells of heterogeneous dimensionembedded in the Euclidean space Ed, where d is the maximum of the dimen-sions of the cells of M, such that the boundary of each cell in M is a collectionof cells of lower dimensions, called facets, belonging to M . Then, M is a d-dimensional mesh if and only if the interiors of any pair of d-dimensional cellsof M are disjoint, and any k-cell of M , with k < d, bounds at least one d-cellof M. The union as a set of points of the cells of a mesh M is called thecarrier, or the domain of M.A special and interesting case of meshes is that of simplicial meshes. A k-dimensional simplex, or k-simplex, for brevity, in Edis the locus of the pointsin Edthat can be expressed as the convex combination of k + 1 affinelyindependent points. A simplicial mesh Σ is a mesh in which all cells aresimplexes. In a d-dimensional simplicial mesh, every k-simplex with k < dis generated by a subset of vertices of some d-simplex. We call the set ofsimplexes bounded by simplex σ the star of σ.A mesh is called conforming if and only if, for each pair of d-cells σ1and σ2,the intersection of the boundaries of σ1and σ2is either empty, or it consistsof a k-facet belonging to the boundary of both σ1and σ2, for some k < d.The use of conforming meshes as decompositions of the domain of a scalarfield, which is sampled at a finite set of points on a manifold, provides a wayof ensuring at least C0continuity for the resulting approximation, withoutrequiring to modify the values of the field at the facets where discontinuitiesmay arise.The valence of a d-cell C in a mesh M is the number of (d + 1)-cells alsoin M that overlap C. The most important examples are the vertex valencein a triangle mesh being the number of edges that meet at a vertex or theedge valence in a tetrahedral mesh being the number of triangles meeting atan edge.Data Structures for LOD Models 3We call regular grids conforming meshes in which all cells are hypercubes(squares or cubes in two and three dimensions, respectively) and all d-cellshave the same valence respectively. Moreover, we call regular meshes thosemeshes which are defined by the uniform subdivision of a d-cell into scaledcopies of it. Note that the vertices of a regular mesh are a subset of thevertices of a regular grid and that all sub-cells with a given dimension d havethe same valence vd.A semi-regular mesh is generated by starting with an irregular mesh andapplying a uniform refinement operator to each cell. The uniform refinementdoes not generate new vertices or edges with irregular valences nor does itchange the valences of existing elements. As a consequence, a semi-regularmesh is piecewise regular and only has some isolated irregular (a.k.a. extraor-dinary) vertices or edges which correspond to the elements of the original(unrefined) mesh.2.2 Elements of a LOD modelThe basic ingredients of a LOD model of a spatial object are a base mesh, thatdefines the coarsest approximation to the object, a set of updates, that, whenapplied to the base mesh, provide variable resolution mesh-based representa-tions of the spatial object, and a dependency relation among updates, whichallows combining them


View Full Document

UMD CMSC 828V - A Survey on Data Structures for Level-Of-Detail Models

Download A Survey on Data Structures for Level-Of-Detail Models
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Survey on Data Structures for Level-Of-Detail Models and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Survey on Data Structures for Level-Of-Detail Models 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?