|
 ABSTRACT
The Corner Table (CT) promoted by Rossignac et al. provides a simple and efficient representation of triangle meshes, storing 6 integer references per triangle (3 vertex references in the V table and 3 references to opposite corners in the O table that accelerate access to adjacent triangles). The Compact Half Face (CHF) proposed by Lage et al. extends CT to tetrahedral meshes, storing 8 references per tetrahedron (4 in the V table and 4 in the O table). We call it the Vertex Opposite Table (VOT) and propose a sorted variation, SVOT, which does not require any additional storage and yet provides, for each vertex, a reference to an incident corner from which an incident tetrahedron may be recovered and the star of the vertex may be traversed at a constant cost per visited element. We use a set of powerful wedge-based operators for querying and traversing the mesh. Finally, inspired by tetrahedral mesh encoding techniques used by Weiler et al. and by Szymczak and Rossignac, we propose our Sorted O Table (SOT) variation, which eliminates the V table completely and hence reduces storage requirements by 50% to only 4 references and 9 bits per tetrahedron, while preserving the vertex-to-incident-corner references and supporting our wedge operators with a linear average cost.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
H. Allik and T. J. R. Hughes, Finite element method for piezoelectric vibration, International Journal for Numerical Methods in Engineering, 2 (1970), pp. 151--157.
|
| |
2
|
F. Aurenhammer, Voronoi diagrams- a survey of a fundamental geometric data structure, ACM Comput. Surv., 23 (1991), pp. 345--405.
|
| |
3
|
B. G. Baumgart, A polyhedron representation for computer vision, Proceedings of the May 19--22, 1975, national computer conference and exposition, ACM, Anaheim, California, 1975.
|
| |
4
|
B. G. Baumgart, Winged edge polyhedron representation, Stanford University, 1972.
|
| |
5
|
M. W. Beall and M. S. Shephard, A General Topology-based Mesh Data Structure, International Journal for Numerical Methods in Engineering, 40 (1997), pp. 1573--1596.
|
| |
6
|
U. Bischoff and J. Rossignac, TetStreamer: Compressed Back-to-Front Transmission of Delaunay Tetrahedra Meshes, Proceedings of the Data Compression Conference, IEEE Computer Society, 2005.
|
| |
7
|
J.-D. Boissonnat, Shape reconstruction from planar cross sections, Comput. Vision Graph. Image Process., 44 (1988), pp. 1--29.
|
| |
8
|
M. Botsch, M. Pauly, C. Rössl, S. Bischoll and L. Kobbelt, Geometric modeling based on triangle meshes, Course Notes, ACM SIGGRAPH 2006, ACM Press, 2006.
|
| |
9
|
E. Brisson, Representing geometric structures in d dimensions: topology and order, Proceedings of the fifth annual symposium on Computational geometry, ACM, Saarbruchen, West Germany, 1989.
|
| |
10
|
E. Bruzzone and L. D. Floriani, Two data structures for building tetrahedralizations, Vis. Comput., 6 (1990), pp. 266--283.
|
| |
11
|
J. C. Caendish, D. A. Field and W. H. Frey, An apporach to automatic three-dimensional finite element mesh generation, International Journal for Numerical Methods in Engineering, 21 (1985), pp. 329--347.
|
| |
12
|
S. Campagna, L. Kobbelt and H.-P. Seidel, Directed edges-A scalable representation for triangle meshes, Journal of Graphics Tools, 3 (1998), pp. 1--11.
|
| |
13
|
D. Chen, Y. J. Chiang, N. Memon and X. Wu, Geometry compression of tetrahedral meshes using optimized prediction, European Conference on Signal Processing (2005).
|
| |
14
|
P. Chopra and J. Meyer, TetFusion: an algorithm for rapid tetrahedral mesh simplification, Proceedings of the conference on Visualization '02, IEEE Computer Society, Boston, Massachusetts, 2002.
|
| |
15
|
P. Cignoni, D. Constanza, C. Montani, C. Rocchini and R. Scopigno, Simplification of Tetrahedral meshes with accurate error evaluation, Proceedings of the conference on Visualization '00, IEEE Computer Society Press, Salt Lake City, Utah, United States, 2000.
|
| |
16
|
P. Cignoni, L. D. Floriani, P. Magillo, E. Puppo and R. Scopigno, Selective Refinement Queries for Volume Visualization of Unstructured Tetrahedral Meshes, IEEE Transactions on Visualization and Computer Graphics, 10 (2004), pp. 29--45.
|
| |
17
|
CUBIT, CUBIT Mesh Generation Toolkit, Tech. report Sandia National Laboratories (2001).
|
| |
18
|
B. Cutler, J. Dorsey and L. McMillan, Simplification and improvement of tetrahedral models for simulation, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, ACM, Nice, France, 2004.
|
| |
19
|
E. Danovaro, L. d. Floriani, M. Lee and H. Samet, Multiresolution Tetrahedral Meshes: An Analysis and a Comparison, Proceedings of the Shape Modeling International 2002 (SMI'02), IEEE Computer Society, 2002.
|
| |
20
|
E. Danovaro, L. D. Floriani, P. Magillo, E. Puppo, D. Sobrero and N. Sokolovsky, The Half-Edge Tree: A Compact Data Structure for Level-of-Detail Tetrahedral Meshes, Proceedings of the International Conference on Shape Modeling and Applications 2005, IEEE Computer Society, 2005.
|
| |
21
|
D. P. Dobkin and M. J. Laszlo, Primitives for the manipulation of three-dimensional subdivisions, Algorithmica, 1989, pp. 3--32.
|
| |
22
|
D. P. Dobkin and M. J. Laszlo, Primitives for the manipulation of three-dimensional subdivisions, Proceedings of the third annual symposium on Computational geometry, ACM, Waterloo, Ontario, Canada, 1987.
|
| |
23
|
H. Edelsbrunner, Geometry and Topology for Mesh Generation, Cambridge University Press, 2001.
|
| |
24
|
L. D. Floriani and A. Hui, Data structures for simplicial complexes: an analysis and a comparison, Proceedings of the third Eurographics symposium on Geometry processing, Eurographics Association, Vienna, Austria, 2005.
|
| |
25
|
L. D. Floriani and A. Hui, A scalable data structure for three-dimensional non-manifold objects, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, Eurographics Association, Aachen, Germany, 2003.
|
| |
26
|
R. V. Garimella, Mesh data structure selection for mesh generation and FEA applications, International Journal for Numerical Methods in Engineering, 2002, pp. 451--478.
|
| |
27
|
R. V. Garimella, MSTK - A Flexible Infrastructure Library for Developing Mesh Based Applications, Proceedings of 13th International Meshing Roundtable, 2004, pp. 203--212.
|
| |
28
|
R. V. Garimella and M. S. Shephard, Tetrahedral Mesh Generation With Multiple Elements Through the Thickness, International Meshing Roundtable, 1995, pp. 321--333.
|
| |
29
|
B. Gregorski, M. Duchaineau, P. Lindstrom, V. Pascucci and K. I. Joy, Interactive view-dependent rendering of large isosurfaces, Proceedings of the conference on Visualization '02, IEEE Computer Society, Boston, Massachusetts, 2002.
|
| |
30
|
L. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Trans. Graph., 4 (1985), pp. 74--123.
|
| |
31
|
S. Gumhold, S. Guthe and W. Straser, Tetrahedral mesh compression with the cut-border machine, Proceedings of the conference on Visualization '99: celebrating ten years, IEEE Computer Society Press, San Francisco, California, United States, 1999.
|
| |
32
|
U. Hartmann and F. Kruggel, A Fast Algorithm for Generating Large Tetrahedral 3D Finite Element Meshes from Magnetic Resonance Tomograms, Proceedings of the IEEE Workshop on Biomedical Image Analysis, IEEE Computer Society, 1998.
|
| |
33
|
M. Isenburg, P. Lindstrom, S. Gumhold and J. Shewchuk, Streaming compression of tetrahedral volume meshes, Proceedings of Graphics Interface 2006, Canadian Information Processing Society, Quebec, Canada, 2006.
|
| |
34
|
B. Joe, GEOMPACK - A Software Package for the Generation of Meshes Using Geometric Algorithms, Advances in Engineering Software, 1991, pp. 325--331.
|
| |
35
|
K. I. Joy, J. Legakis and R. MacCracken, Data Structures for Multiresolution Representation of Unstructured Meshes, Hierarchical Approximation and Geometric Methods for Scientific Visualization, 2002.
|
| |
36
|
M. Kallmann and D. Thalmann, Star-vertices: a compact representation for planar meshes with adjacency information, Journal of Graphics Tools, 6 (2001), pp. 7--18.
|
| |
37
|
M. Lage, T. Lewiner, H. Lopes and L. Velho, CHF: A Scalable Topological Data Structure for Tetrahedral Meshes, Proceedings of the XVIII Brazilian Symposium on Computer Graphics and Image Processing, IEEE Computer Society, 2005.
|
| |
38
|
LaGrit, LaGriT - Los Alamos Grid Toolbox, Tech. report Los Alamos National Laboratory (1995).
|
| |
39
|
P. Lienhardt, N-dimensional Generalized Combinatorial Maps and Cellular Quasi-Manifolds, International Journal of Computational Geometry & Applications, 1994, pp. 275--324.
|
| |
40
|
P. Lienhardt, Subdivisions of n-dimensional spaces and n-dimensional generalized maps, Proceedings of the fifth annual symposium on Computational geometry, ACM, Saarbruchen, West Germany, 1989.
|
| |
41
|
A. Liu and B. Joe, Quality local refinement of tetrahedral meshes based on 8-subtetrahedron subdivision, Math. Comput., 65 (1996), pp. 1183--1200.
|
| |
42
|
Y. Liu and J. Snoeyink, A comparison of five implementations of 3d Delaunay tessellation, Combinatorial and Computational Geometry, MSRI series, 2005, pp. 439--458.
|
| |
43
|
H. Lopes and G. Tavares, Structural operators for modeling 3-manifolds, Proceedings of the fourth ACM symposium on Solid modeling and applications, ACM, Atlanta, Georgia, United States, 1997.
|
| |
44
|
M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., 1988.
|
| |
45
|
R. Pajarola, J. Rossignac and A. Szymczak, Implant sprays: compression of progressive tetrahedral mesh connectivity, Proceedings of the conference on Visualization '99: celebrating ten years, IEEE Computer Society Press, San Francisco, California, United States, 1999.
|
| |
46
|
A. Paoluzzi, F. Bernardini, C. Cattani and V. Ferrucci, Dimension-independent modeling with simplicial complexes, ACM Trans. Graph., 12 (1993), pp. 56--102.
|
| |
47
|
J. Pescatore, L. Garnero and I. Bloch, Tetrahedral finite element meshes of head tissues from MRI for the MEG/EEG forward problem, 12th Scandinavian Conference on Image Analysis, 2001, pp. 71--80.
|
| |
48
|
J. F. Remacle, B. K. Karamete and M. S. Shephard, Algorithm Oriented Mesh Database, Proceedings of the 9th International Meshing Roundtable (2000), pp. 349--359.
|
| |
49
|
J. Rossignac, 3D Mesh Compression, in C. Hansen and C. Johnson, eds., The Visualization Handbook, Academic Press, 2006.
|
| |
50
|
J. Rossignac, Surface simplification and 3D geometry compression, in Goodman and O'Rourke, eds., The Handbook of Discrete and Computational Geometry (2nd edition), CRC Press, 2004.
|
| |
51
|
J. Rossignac, Through the cracks of the solid modeling milestone, in S. Coquillart, W. Strasser and P. Stucki, eds., From object modelling to advanced visualization, Springer Verlag, 1994, pp. 1--75.
|
| |
52
|
J. Rossignac and M. O'Connor, SGC: A Dimension-independent Model for Pointsets with Internal Structures and Incomplete Boundaries, Geometric Modeling for Product Engineering, 1989, pp. 145--180.
|
| |
53
|
J. Rossignac, A. Safonova and A. Szymczak, 3D Compression Made Simple: Edgebreaker on a Corner-Table, 3D Compression Made Simple: Edgebreaker with Zip&Wrap on a Corner-Table, IEEE Computer Society, 2001.
|
| |
54
|
J. Rossignac, A. Safonova and A. Szymczak, Edgebreaker on a Corner Table: A simple technique for representing and compressing triangulated surfaces, Hierarchical and Geometrical Methods in Scientific Visualization, 2003, pp. 41--50.
|
| |
55
|
M. Sambridge, J. Braun and H. McQueen, Geophysical parametrization and interpolation of irregular data using natural neighbours, Geophysical Journal International, 122 (1995), pp. 837--857.
|
| |
56
|
M. S. Shephard and P. M. Finnigan, Integration of geometric modeling and advanced finite element preprocessing, Finite Elements in Analysis and Design, 1988, pp. 147--162.
|
| |
57
|
J. R. Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, ACM, Minneapolis, Minnesota, United States, 1998.
|
| |
58
|
H. Si and K. Gaertner, Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations, Proceedings of the 14th International Meshing Roundtable, 2005, pp. 147--163.
|
| |
59
|
R. Sondershaus and W. Straser, View-dependent tetrahedral meshing and rendering, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, ACM, Dunedin, New Zealand, 2005.
|
| |
60
|
O. G. Staadt and M. H. Gross, Progressive tetrahedralizations, Proceedings of the conference on Visualization '98, IEEE Computer Society Press, Research Triangle Park, North Carolina, United States, 1998.
|
| |
61
|
A. Szymczak and J. Rossignac, Grow & fold: compression of tetrahedral meshes, Proceedings of the fifth ACM symposium on Solid modeling and applications, ACM, Ann Arbor, Michigan, United States, 1999.
|
| |
62
|
T. J. Tautges, K. Merkley, C. J. Stimpson and R. J. Meyers, The Sandia Mesh Database Component (MDB), Proceedings of the Seventh Us National Congress on Computational Mechanics, 2003.
|
| |
63
|
TetMesh, TetMesh - GHS3D, Ver. 3.1, Tech. report INRIA/SIMULOG (2001).
|
| |
64
|
I. J. Trotts, B. Hamann and K. I. Joy, Simplification of Tetrahedral Meshes with Error Bounds, IEEE Transactions on Visualization and Computer Graphics, 5 (1999), pp. 224--237.
|
| |
65
|
S.-K. Ueng and K. Sikorski, A Note on a Linear Time Algorithm for Constructing Adjacency Graphs of 3D FEA Data, The Visual Computer, 1996, pp. 445--450.
|
| |
66
|
S.-K. Ueng and K. Sikorski, An out-of-core method for computing connectivities of large unstructured meshes, Proceedings of the Fourth Eurographics Workshop on Parallel Graphics and Visualization, Eurographics Association, Blaubeuren, Germany, 2002.
|
| |
67
|
H. T. Vo, S. P. Callahan, P. Lindstrom, V. Pascucci and C. T. Silva, Streaming Simplification of Tetrahedral Meshes, IEEE Transactions on Visualization and Computer Graphics, 13 (2007), pp. 145--155.
|
| |
68
|
K. Weiler, The radial-edge data structure: a topological representation for non-manifold geometric boundary modeling, Geometric Modeling for CAD Appl., 1988, pp. 3--36.
|
| |
69
|
M. Weiler, P. N. Mallon, M. Kraus and T. Ertl, Texture-Encoded Tetrahedral Strips, Proceedings of the 2004 IEEE Symposium on Volume Visualization and Graphics, IEEE Computer Society, 2004.
|
| |
70
|
C.-K. Yang, T. Mitra and T.-C. Chiueh, On-the-Fly rendering of losslessly compressed irregular volume data, Proceedings of the conference on Visualization '00, IEEE Computer Society Press, Salt Lake City, Utah, United States, 2000.
|
| |
71
|
S.-e. Yoon and P. Lindstrom, Random-Accessible Compressed Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, 13 (2007), pp. 1536--1543.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf