Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-12-10
2004-04-06
Jones, Hugh (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C345S420000, C345S423000, C345S440000, C382S154000
Reexamination Certificate
active
06718290
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the field of computers and, in particular, to systems and methods for compressing and/or decompressing data corresponding to 3D finite element meshes.
2. Description of the Related Art
A simple representation of a tetrahedral mesh whose boundary is a manifold surface typically consists of two tables: a vertex table (which keeps vertex coordinates and vertex data, such as temperature or pressure, for instance) and a tetrahedron table (which stores quadruples of vertex indices, representing vertex sets for each one of the m tetrahedra in the mesh). The tetrahedron table describes explicitly only the vertex incidence for each tetrahedron. However, all other connectivity information, like tetrahedron-face or triangle-vertex incidence can be derived from it algorithmically. For a mesh with one million vertices and six million tetrahedra, the tetrahedron table requires 128m≈7.68×10
8
bits if 4-byte pointers are used to reference vertices or 80m≈4.8×10
8
bits if the vertex references are stored as 20-bit integers crossing the byte boundaries. The total size of the vertex coordinates and data (12-bit coordinates and 16-bit for a single scalar value) of such a mesh amounts to 5.2×10
7
bits: almost ten times less. Therefore, the connectivity information dominates the storage cost.
Numerous data structures have been proposed that combine adjacency and incidence information complex (see J. Rossignac, Through the cracks of the solid modeling milestone,
From Object Modeling to Advanced Visual Communication
, Eds. S. Coquillard, W. Strasser, P. Stucki, Springer-Verlag, pp. 1-75, 1994) for a review. Examples include winged-edge representation (see B. G, Baumgart,
Winged Edge Polyhedron Representation
, AIM-79, Stanford University, Report STAN-CS-320, 1972, and B. G. Baumgart,
A Polyhedron Representation for Computer Vision
, AFIPS Nat. Conf Proc., Vol. 44, 589-596, 1975), face-adjacency hypergraph (see L. Floriani and B. Falcidieno,
A Hierarchical Boundary Model for Solid Object Representation
, ACM Transactions on Graphics 7(1), pp. 42-60, 1988), half-edge structure (see M. Mantyla,
An Introduction to Solid Modeling
, Computer Science Press, Rockville, Md. 1988, and Y. E. Kalay, The Hybrid Edge:
A Topological Data Structure for Vertically Integrated Geometric Modeling, Computer
-
Aided Design
21(3), pp.
130
-
140
,
1989
), radial-edge structure (see E. Gursoz and F. Prinz,
Boolean Set Operators on Non
-
Manifold Boundary Representation Objects, Computer Aided Design
23(1), pp. 33-39, January/February 1991, and E. Gursoz, Y. Choi and F. Prinz,
Node
-
Based Representation of Non-Manifold Surface Boundaries in Geometric Modeling
, In: J. Turner, M. Wozny and K. Preiss eds.,
Geometric Modeling for Product Engineering
, North-Holland 1989), and selective geometric complex (see J. Rossignac and M. O'Connor,
SGC: A Dimension
-
independent Model for Pointsets with Internal Structures and Incomplete Boundaries, in Geometric Modelingfor Product Engineering
, Eds. M. Wosny, J. Turner, K. Preiss, North-Holland, pp. 145-180, 1989).
The goal behind the design of these data structures is to provide an efficient way of accessing different kinds of adjacency information without taking up much storage space. A common idea is to store some of the adjacency relations (possibly in a partial form) explicitly and use them to derive the ones which are not explicitly stored. For example, in the winged-edge representation, each face and vertex point to one of the adjacent edges and each edge—to its endpoints, the two adjacent faces and the four edges adjacent to that edge and the neighboring two faces. Using the above relations it is possible to compute all others (for example, all edges adjacent to a face or all edges adjacent to a vertex) in time proportional to the local complexity of the mesh (for our two examples, the number of edges of the face and the number of edges our of a vertex, respectively). One of the concerns is to reduce storage space needed to keep adjacency information while minimizing access time. Therefore, it is not fair to treat boundary data structures as a compression scheme. In fact, as shown in T. C. Woo,
A Combination Analysis of Boundary Data Structure
, IEEE Computer Graphics and Applications, Vol. 5, pp. 19-27, 1985, such a data structure requires at least 4E pointers, where E is the number of edges of the mesh—more than tetrahedron table.
Staadt and Gross (see O. Staadt and M. Gross,
Progressive Tetrahedralization
, Proc. IEEE Visualization, pp. 397:402, Research Triangle Park, Oct. 18-23, 1998) and Trotts et al (see I. Trotts, B. Hamann, K. Joy, D. Wiley,
Simplification of Tetrahedral Meshes
, Proc. IEEE Visualization, pp. 287:295, Research Triangle Park, Oct. 18-23, 1998) independently propose a tetrahedral mesh simplification process, which removes tetrahedra by collapsing their edges in a sequence that attempts to minimize, at each stage, the error computed using different cost functions. Such a simplification may be viewed as a lossy compression technique and complements our loss-less compression, which may be used to compactly encode the simplified meshes.
Deering's approach (see M. Deering, Geometric Compression,
Computer Graphics
(Proc. SIGGRAPH), p. 13-20, August 1995) is a compromise between a standard triangle strip and a general scheme for referencing any previously decoded vertex. Deering uses a 16 register cache to store temporarily 16 of the previously decoded vertices for subsequent uses. One could envision extending the notion of a triangle strip to tetrahedra. Keeping 3 registers for the last 3 vertices used, each new tetrahedron will be defined by these 3 vertices and a fourth vertex either new (the next vertex received in the compressed input stream) or previously received (and identified by its location or id in main memory or cache). One of the vertices in the registers will be replaced by the forth one and the operation repeated. Unfortunately, we do not know of simple and efficient algorithms for identifying the suitable sequence of tetrahedra.
Hoppe's Progressive Meshes (see H. Hoppe,
Progressive Meshes, Computer Graphics
(Proc. SIGGRAPH), P. 99-108, August 1996) permit to transfer a 3D mesh progressively, starting from a coarse mesh and then inserting new vertices one by one. Instead of a vertex insertion to split a single triangle, as suggested in D. Dobkin and D. Kirkpatrick,
A linear algorithm for determining the separation of convex polyhedra
, Journal of Algorithms, Vol. 6, pp. 381-392, 1985, for convex polyhedra, Hoppe applies a vertex insertion that is the inverse of the edge collapse operation popular in mesh simplification techniques (see H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle, Mesh Optimization,
Computer Graphics
(Proc. SIGGRAPH), p. 19-26, August 1993, R. Ronfard and J. Rossignac,
Full
-
range approximation of triangulated polyhedra
, Proc. Eurographics'96, Computer Graphics Forum, pp. C-67, vol. 15, no. 3, August 1996, and P. Heckbert and M. Garland,
survey of Polygonal Surface Simplification Algorithms in Multiresolution Surface Modeling Course
, ACM SIGGRAPH Course Notes, 1997). A vertex insertion identifies a vertex v and two of its incident edges. It cuts the mesh open at these edges and fills the hole with two triangles. The vertex v is thus split into two vertices. Each vertex is transferred only once in the Hoppe's scheme.
Hoppe suggests that it may be possible to extend this scheme to tetrahedra. Each vertex split would require identifying one vertex of the current (simplified) version of the mesh and a cone of incident triangles. As the new vertex is extruded into an edge, these triangles would be extruded into new tetrahedra. The cost of this approach is the identification of each vertex (log
2
v per vertex) and the identification of the cone of incident edges, which on average would require 15 bits per vertex. Although simple, this approach wo
Rossignac Jarek R.
Szymczak Andrzej
Day Herng-der
Georgia Tech Research Corporation
Jones Hugh
Thomas Kayden Horstemeyer & Risley LLP
LandOfFree
Systems and methods for encoding tetrahedral meshes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for encoding tetrahedral meshes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for encoding tetrahedral meshes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3261494