More Web Proxy on the site http://driver.im/

article

n-Dimensional multiresolution representation of subdivision meshes with arbitrary topology

Authors:

Lionel Untereiner,

Dominique BechmannAuthors Info & Claims

Graphical Models, Volume 75, Issue 5

Pages 231 - 246

https://doi.org/10.1016/j.gmod.2013.03.003

Published: 01 September 2013 Publication History

Abstract

We present a new model for the representation of n-dimensional multiresolution meshes. It provides a robust topological representation of arbitrary meshes that are combined in closely interlinked levels of resolution. The proposed combinatorial model is formalized through the mathematical model of combinatorial maps allowing us to give a general formulation, in any dimensions, of the topological subdivision process that is a key issue to robustly and soundly define mesh hierarchies. It fully supports multiresolution edition what allows the implementation of most mesh processing algorithms - like filtering or compression - for n-dimensional meshes with arbitrary topologies. We illustrate this model, in dimension 3, with an new truly multiresolution representation of subdivision volumes. It allows us to extend classical subdivision schemes to arbitrary polyhedrons and to handle adaptive subdivision with an elegant solution to compliance issues. We propose an implementation of this model as an effective and relatively inexpensive data structure.

References

[1]

Allaire, G., . 2007. Numerical Mathematics and Scientific Computation, 2007.Oxford University Press.

[2]

Wicke, M., Ritchie, D., Klingner, B.M., Burke, S., Shewchuk, J.R. and O'Brien, J.F., Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. v29. 49:1-11.

Digital Library

[3]

Burkhart, D., Hamann, B. and Umlauf, G., Iso-geometric finite element analysis based on Catmull-Clark subdivision solids. Comput. Graph. Forum. v29 i5. 1575-1584.

[4]

R. MacCracken, K.I. Joy, Free-form deformations with lattices of arbitrary topology, in: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '96, New Orleans, 1996, pp. 181-188.

Digital Library

[5]

Capell, S., Green, S., Curless, B., Duchamp, T. and Popović, Z., A multiresolution framework for dynamic deformations. In: Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA '02, ACM, New York, NY, USA. pp. 41-47.

[6]

S. Schaefer, J.P. Hakenberg, J. Warren, Smooth subdivision of tetrahedral meshes, in: Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing - SGP '04, Nice, France, 2004, pp. 147-154.

Digital Library

[7]

Pascucci, V., Slow growing subdivisions (sgs) in any dimension: towards removing the curse of dimensionality. Comput. Graph. Forum. v21 i3. 451-460.

[8]

4-8 Subdivision. Comput. Aided Geom. Des. v18 i5. 397-427.

[9]

A survey on data structures for level-of-detail models. In: Dodgson, N.A., Floater, M.S., Sabin, M.A. (Eds.), Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, Springer, Berlin Heidelberg. pp. 49-74.

[10]

Tournois, J., Wormser, C., Alliez, P. and Desbrun, M., Interleaving delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Trans. Graph. v28 i3.

[11]

B. Lévy, Y. Liu, Lp centroidal voronoi tesselation and its applications, in: ACM Transactions on Graphics (SIGGRAPH Conference Proceedings) Patent Pending - FR 10/02920 (filed 07/09/10).

[12]

Frey, P. and George, P.-L., Mesh Generation. 2008. John Wiley & Sons.

[13]

DeFloriani, L., Kobbelt, L. and Puppo, E., A survey on data structures for level-of-detail models. Advances in Multiresolution for Geometric Modelling, Series in Mathematics and Visualization. 49-74.

[14]

Lienhardt, P., Topological models for boundary representation: a comparison with n-dimensional generalized maps. Comput. Aided Des. v23 i1. 59-82.

[15]

Dufourd, J.-F., Algebraic map-based topological kernel for polyhedron modellers: algebraic specification and logic prototyping. In: Int. Conf. Eurographics'89, North-Holland. pp. 649-662.

[16]

Croom, F.H., . 1978. Undergraduate Texts in Mathematics, 1978.Springer.

[17]

Kraemer, P., Cazier, D. and Bechmann, D., Extension of half-edges for the representation of multiresolution subdivision surfaces. Visual Comput. v25 i2.

[18]

Bajaj, C., Schaefer, S., Warren, J. and Xu, G., A subdivision scheme for hexahedral meshes. Visual Comput. v18 i5-6. 343-356.

[19]

McDonnell, K.T., Chang, Y., Qin, H. and Interpolatory, solid subdivision of unstructured hexahedral meshes. Visual Comput. v20 i6.

[20]

Loop, C., Smooth subdivision surfaces based on triangles. 1987. Department of Mathematics, University of Utah, Utah, USA.

[21]

Dyn, N., Levine, D. and Gregory, J.A., A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph. v9. 160-169.

Digital Library

[22]

Zorin, D., Schröder, P. and Sweldens, W., Interpolating subdivision for meshes with arbitrary topology. In: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '96, ACM, New York, NY, USA. pp. 189-192.

[23]

Catmull, E. and Clark, J., Recursively generated b-spline surfaces on arbitrary topological meshes. Comput.-Aided Des. v10 i6. 350-355.

[24]

Chang, Y.-S., McDonnell, K.T. and Qin, H., A new solid subdivision scheme based on box splines. In: Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications, SMA '02, ACM, New York, NY, USA. pp. 226-233.

[25]

Burkhart, D., Hamann, B. and Umlauf, G., Adaptive and feature-preserving subdivision for high-quality tetrahedral meshes. Comput. Graph. Forum. v29 i1. 117-127.

[26]

Danovaro, E., de Floriani, L., Magillo, P., Puppo, E., Sobrero, D. and Sokolovsky, N., The half-edge tree: a compact data structure for level-of-detail tetrahedral meshes. In: SMI '05: Proceedings of the International Conference on Shape Modeling and Applications 2005, IEEE Computer Society, Washington, DC, USA. pp. 334-339.

Digital Library

[27]

Luebke, D., Watson, B., Cohen, J.D., Reddy, M. and Varshney, A., Level of Detail for 3D Graphics. 2002. Elsevier Science Inc., New York, NY, USA.

[28]

Simplex and diamond hierarchies: models and applications. Comput. Graph. Forum. v30 i8. 2127-2155.

[29]

Primitives for the manipulation of three-dimensional subdivisions. In: Proceedings of the Third Annual Symposium on Computational Geometry, SCG '87, ACM, New York, NY, USA. pp. 86-99.

[30]

CGoGN, Combinatorial and Geometric Modeling with Generic n-Dimensional Maps. <http://cgogn.unistra.fr>.

[31]

Burstedde, C., Wilcox, L.C. and Ghattas, O., p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees. SIAM J. Sci. Comput. v33 i3. 1103-1133.

[32]

J.-C. Krencker, J.-B. Kammerer, Y. Herve, L. Hebrard, 3d Electro-thermal simulations of analog ics carried out with standard cad tools and verilog-a, in: 2011 17th International Workshop on Thermal Investigations of ICs and Systems (THERMINIC), 2011, pp. 1 -4.

Cited By

Untereiner LKraemer PCazier DBechmann D(2015)CPHComputer Graphics Forum10.1111/cgf.1266734:8(155-166)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1111/cgf.12667
Alayrangues SDamiand GLienhardt PPeltier S(2015)Homology of Cellular Structures Allowing Multi-incidenceDiscrete & Computational Geometry10.1007/s00454-015-9662-554:1(42-77)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00454-015-9662-5

n-Dimensional multiresolution representation of subdivision meshes with arbitrary topology
1. Theory of computation

Recommendations

Subdivision tree based multiresolution representation of arbitrary triangle meshes
Incremental subdivision for triangle meshes

We introduce incremental subdivision as a new adaptive subdivision method for triangle meshes. While regular (global) subdivisions produce a smooth surface from a given polygon mesh by refining all of its faces, adaptive subdivision produces a surface ...
CPH: A Compact Representation for Hierarchical Meshes Generated by Primal Refinement

We present CPH Compact Primal Hierarchy: a compact representation of the hierarchical connectivity of surface and volume manifold meshes generated through primal subdivision refinements. CPH is consistently defined in several dimensions and supports ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Graphical Models

Graphical Models Volume 75, Issue 5

September, 2013

48 pages

ISSN:1524-0703

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2013.

Publisher

Academic Press Professional, Inc.

United States

Publication History

Published: 01 September 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Untereiner LKraemer PCazier DBechmann D(2015)CPHComputer Graphics Forum10.1111/cgf.1266734:8(155-166)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1111/cgf.12667
Alayrangues SDamiand GLienhardt PPeltier S(2015)Homology of Cellular Structures Allowing Multi-incidenceDiscrete & Computational Geometry10.1007/s00454-015-9662-554:1(42-77)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00454-015-9662-5

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents