Remeshing is a key component of many geometric algorithms, including modeling, editing, animation and simulation. As such, the rapidly developing field of geometry processing has produced a profusion of new remeshing techniques over the past few years. In this paper we survey recent developments in remeshing of surfaces, focusing mainly on graphics applications. We classify the techniques into five categories based on their end goal: structured, compatible, high quality, feature and error-driven remeshing.We limit our description to the main ideas and intuition behind each technique, and a brief comparison between some of the techniques. We also list some open questions and directions for future research.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Alexa. Merging polyhedral shapes with scattered features. In Proceedings of the International Conference on Shape Modeling and Applications (SMI-99), pages 202-210, 1999.
M. Alexa. Recent advances in mesh morphing. Computer Graphics Forum, 21(2):173-196,2002.
P. Alliez and C. Gotsman. Recent advances in compression of 3d meshes. In Proceedings of the Symposium on Multiresolution in Geometric Modeling, 2003.
P. Alliez, N. Laurent, H. Sanson, and F. Schmitt. Mesh approximation using a volumebased metric. In Proceedings of the 7th Pacific Conference on Computer Graphics and Applications 1999, pages 292-301, Los Alamitos, 1999. IEEE Computer Society.
P. Alliez, M. Meyer, and M. Desbrun. Interactive geometry remeshing. Acm Transactions on Graphics, 21(3):347-354, 2002.
Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Levy, and Mathieu Desbrun. Anisotropic polygonal remeshing. ACM.Transactions on Graphics, 22:485-493, 2003.
Pierre Alliez, Eric Colin de Verdiere, Olivier Devillers, and Martin Isenburg. Isotropic surface remeshing. In M.S. Kim, editor, SMI ’03: Proceedings of Shape Modeling International 2003, pages 49-58, Los Alamitos, 2003. IEEE Computer Society.
N. Amenta, M. Bern, and M. Kamvysselis. A new voronoi-based surface reconstruction algorithm. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 415-422, Jul 1998.
M. Attene, B. Falcidieno, J. Rossignac, and M. Spagnuolo. Edge-sharpener: recovering sharp features in triangulations of non-adaptively re-meshed surfaces. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing 2003, pages 62-69. ACM Press, 2003.
M. Attene, B. Falcidieno, M. Spagnuolo, and J. Rossignac. Swingwrapper: Retiling triangle meshes for better edgebreaker compression. Acm Transactions on Graphics, 22(4):982-996, 2003.
M. Attene, B. Falcidieno, M. Spagnuolo, and G. Wyvill. A mapping-independent primitive for the triangulation of parametric surfaces. Graphical Models, 65(5):260-273, 2003.
J. D. Boissonnat and S. Oudot. Provably good surface sampling and approximation. In Proc. of Symp. on Geo. Processing, pages 9-18, 2003.
Houman Borouchaki, Frederic Hecht, and J.Frey Pascal. Mesh gradation control. In Proceedings of 6th International Meshing Roundtable, pages 131-141. Sandia National Laboratories, 1997.
Mario Botsch and Leif Kobbelt. A remeshing approach to multiresolution modeling. In R. Scopigno and D. Zorin, editors, Proceedings of 2nd Eurographics Symposium on Geometry Processing, pages 189-196. Eurographics, 2004.
L. Paul Chew. Guaranteed-quality mesh generation for curved surfaces. In Proceedings of the ninth annual symposium on Computational geometry, pages 274-280. ACM Press, 1993.
D. Cohen-Steiner, P. Alliez, and M. Desbrun. Variational shape approximation. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, 2004.
T.K. Dey and R. Wenger. Reconstructing curves with sharp corners. Computational Geometry Theory and Applications, 19:89-99, 2001.
S. Dong, S. Kircher, and M. Garland. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Computer Aided Geometric Design, 2005. To appear.
Q. Du, V. Faber, and M. Gunzburger. Centroidal Voronoi Tesselations: Applications and Algorithms. SIAM review, 41(4):637-676, 1999.
M. Eck, T. De Rose, T. Duchamp, H. Hoppe, M.Lounsbery, and W. Stuetzle. Multiresolution analysis of arbitrary meshes. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 173-182, 1995.
H. Edelsbrunner and D. Guoy. Sink-insertion for mesh improvement. In Proceedings of the seventeenth annual symposium on Computational geometry, pages 115-123. ACM Press, 2001.
M.S. Floater and K. Hormann. Surface Parameterization: a Tutorial and Survey. Springer, 2004.
P. J. Frey and H. Borouchaki. Geometric surface mesh optimization. Computing and Visualization in Science, 1:113-121, 1998.
Pascal J. Frey. About surface remeshing. In Proceedings of the 9th International Meshing Roundtable, pages 123-136. Sandia National Laboratories, 2000.
M. Garland. Multiresolution modeling: Survey & future opportunities. In Eurographics ’99, State of the Art Report (STAR), pages 111-131. Eurographics, 2000.
A. Gersho. Asymptotically optimal block quantization. IEEE Transactions on Information Theory, IT-25(4):373-380, July 1979.
C. Gotsman, X.F. Gu, and A. Sheffer. Fundamentals of spherical parameterization for 3d meshes. Acm Transactions on Graphics, 22(3):358-363, 2003.
C. Gotsman, S. Gumhold, and L. Kobbelt. Simplification and compression of 3D-meshes. 2002.
X. Gu, S.J. Gortler, and H. Hoppe. Geometry images. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 355-361, 2002.
I. Guskov, K. Vidimce, W. Sweldens, and P. Schroeder. Normal meshes. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 95-102, 2000.
E. Hartmann. A marching method for the triangulation of surfaces. the Visual Computer, 14(3):95-108, 1998.
P. Heckbert and M. Garland. Survey of polygonal surface simplification algorithms, 1997.
H. Hoppe. Progressive meshes. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 99-108, 1996.
Hugues Hoppe, Tony De Rose, Tom Duchamp, John McDonald, and Werner Stuetzle. Mesh optimization. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 19-26, 1993.
K. Hormann and G. Greiner. Quadrilateral remeshing. In Proceedings of Vision, Modeling, and Visualization 2000, pages 153-162, 2000.
T. Ju, F. Losasso, S. Schaefer, and J. Warren. Dual contouring of hermite data. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 339-346, 2002.
T. Kanai, H. Suzuki, and F. Kimura. Metamorphosis of arbitrary triangular meshes. Ieee Computer Graphics and Applications, 20:62-75, 2000.
A. Khodakovsky and I. Guskov. Compression of Normal Meshes. Springer-Verlag, 2003.
A. Khodakovsky, N. Litke, and P. Schr öder. Globally smooth parameterizations with low distortion. ACM.Transactions on Graphics, 22:350-357, 2003.
A. Khodakovsky, P. Schroeder, and W. Sweldens. Progressive geometry compression. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 271-278, 2000.
L. Kobbelt, S. Bischoff, M. Botsch, K. Kahler, C. R össl, R. Schneider, and J. Vorsatz. Geometric modeling based on polygonal meshes. In Euroraphics 2000 Tutorial, 2000.
L. Kobbelt and M. Botsch. Feature sensitive mesh processing. In SCCG ’03: Proceedings of the 19th Spring Conference on Computer Graphics, pages 17-22. ACM Press, 2003.
L. Kobbelt, J. Vorsatz, U. Labsik, and H.-P. Seidel. A shrink wrapping approach to remeshing polygonal surfaces. Computer Graphics Forum, 18:119-130, 1999.
L.P. Kobbelt, M. Botsch, U. Schwanecke, and H.P. Seidel. Feature sensitive surface extraction from volume data. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 57-66, Aug 2001.
V. Kraevoy and A. Sheffer. Cross-parameterization and compatible remeshing of 3d models. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, 2004.
A. Lee, D. Dobkin, W. Sweldens, and P. Schr öder. Multiresolution mesh morphing. In Siggraph 1999, Computer Graphics Proceedings, pages 343-350, 1999.
A.W.F. Lee, W. Sweldens, P. Schroeder, L. Cowsar, and D. Dobkin. Maps: Multiresolution adaptive parameterization of surfaces. Computer Graphics, 32:95-104, 1998.
J. L. Lin, J. H. Chuang, C. C. Lin, and C. C. Chen. Consistent parametrization by quinary subdivision for remeshing and mesh metamorphosis. In GRAPHITE ’03: Proceedings of the 1th International Conference on Computer Graphics and Interactive Techniques in Austalasia and South East Asia 2003, pages 151-158. ACM Press, 2003.
M.l Lindenbaum, M. Porat, Y. Y. Zeevi, and Y. Eldar. The farthest point strategy for progressive image sampling, 1996.
S. Lloyd. Least square quantization in PCM. IEEE Trans. Inform. Theory, 28:129-137, 1982.
W.E. Lorensen and H.E. Cline. Marching cubes: a high resolution 3d surface reconstruc- tion algorithm. Computer Graphics, 21:163-169, 1987.
D. Luebke. A developer’s survey of polygonal simplification algorithms. Ieee Computer Graphics and Applications, 2001.
D. Luebke, M. Reddy, J. Cohen, A. Varshney, B. Watson, and R. Huebner. Level of Detail for 3D Graphics. Morgan-Kaufmann, San Francisco, 2002.
M. Marinov and L. Kobbelt. Direct anisotropic quad-dominant remeshing. In Proceedings of the 12th Pacific Conference on Computer Graphics and Applications, pages 207-216, 2004.
T. Michikawa, T. Kanai, M. Fujita, and H. Chiyokura. Multiresolution interpolation meshes. In Proceedings of the 9th Pacific Conference on Computer Graphics and Applications 2001, pages 60-69, Los Alamitos, 2001. IEEE Computer Society.
G. L. Miller. A time efficient delaunay refinement algorithm. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 400-409. Society for Industrial and Applied Mathematics, 2004.
C. Moenning and N. A. Dodgson. Fast marching farthest point sampling. Technical Report UCAM-CL-TR-562, University of Cambridge, Computer Laboratory, 2003.
V. Ostromoukhov. A Simple and Efficient Error-Diffusion Algorithm. In Proceedings of SIGGRAPH, pages 567-572, 2001.
V. Ostromoukhov, C. Donohue, and P. M. Jodoin. Fast hierarchical importance sampling with blue noise properties new york, ny, usa. ACM.Transactions on Graphics, 23, Aug 2004.
F. Payan and M. Antonini. 3d mesh wavelet coding using efficient model-based bit allocation. In Proceedings of the 1st International Symposium on 3D Data Processing Visualization and Transmission 2002, pages 391-394, 2002.
P. P. Pebay and T. J. Baker. A comparison of triangle quality measures. In Proceedings, 10th International Meshing Roundtable, pages 327-340, 2001.
G. Peyr é and L. Cohen. Surface Segmentation Using Geodesic Centroidal Tesselation. In Proceedings of 2nd International Symposium on 3D Data Processing, Visualization, and Transmission, pages 995-1002, 2004.
Gabriel Peyre and Laurent Cohen. Geodesic remeshing using front propagation. In Proceedings of 2nd IEEE Workshop on Variational, Geometric and Level Set Methods in Computer Vision 2003, pages 33-40, Los Alamitos, 2003. IEEE Computer Society.
E. Praun and H. Hoppe. Spherical parametrization and remeshing. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 340- 349,2003.
E. Praun, W. Sweldens, and P. Schr öder. Consistent mesh parameterizations. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 179-184, 2001.
A. Rassineux, P. Villon, J.M. Savignat, and O. Stab. Surface remeshing by local hermite diffuse interpolation. International Journal for Numerical Methods in Engineering, 49:31-49, 2000.
C. Rocchini, P. Cignoni, F. Ganovelli, C. Montani, P. Pingi, and R. Scopigno. Marching intersections: an efficient resampling algorithm for surface management. In Proceedings of the International Conference on Shape Modeling and Applications, pages 296-305, 2001.
J. Ruppert. A delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of Algorithms, 18(3):548-585, 1995.
P. Sander, S. Gortler, J. Snyder, and H. Hoppe. Signal-specialized parametrization. In EGWR ’02: 13th Eurographics Workshop on Rendering 2002. Eurographics, 2002.
P. Sander, Z. Wood, S. Gortler, J. Snyder, and H. Hoppe. Multi-chart geometry images. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing 2003, pages 246-255. ACM Press, 2003.
J. Schreiner, A. Asirvatham, E. Praun, and H. Hoppe. Inter-surface mapping. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, 2004.
P. Schr öder. Subdivision for modeling and animation, 1998.
J. Sethian. Level Sets Methods and Fast Marching Methods. Cambridge University Press, 2nd edition, 1999.
J. R. Shewchuk. What is a good linear element? interpolation, conditioning, and quality measures. In Proceedings of 11th International Meshing Roundtable, 2002.
K. Shimada and J. Liao. Quadrilateral Meshing with Directionality Control through the Packing of Square Cells. In 7th Intl. Meshing Roundtable, pages 61-76, oct 1998.
Oren Sifri, Alla Sheffer, and Craig Gotsman. Geodesic-based surface remeshing. In Proceedings of 12th International Meshing Roundtable, pages 189-199. Sandia National Laboratories, 2003.
V. Surazhsky and C. Gotsman. Explicit surface remeshing. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing 2003, pages 20-30. ACM Press, 2003.
Vitaly Surazhsky, Pierre Alliez, and Craig Gotsman. Isotropic remeshing of surfaces: a local parameterization approach. In Proceedings of 12th International Meshing Round-table, pages 215-224. Sandia National Laboratories, 2003.
W. Sweldens and P. Schr öder, editors. Digital Geometry Processing. SIGGRAPH Conference course notes, 2001.
A. Szymczak, J. Rossignac, and D. King. Piecewise regular meshes: Construction and compression. Graphical.models., 2003.
G. Taubin. Geometric signal processing on polygonal meshes. In Euroraphics 2000: State of the Art Report (STAR). Eurographics, 2000.
J.R. Tristano, S.J. Owen, and S.A. Canann. Advancing Front Surface Mesh Generation in Parametric Space Using a Riemannian Surface Definition. In Proceedings of the 7th Int. Meshing Roundtable, 1998.
Greg Turk. Re-tiling polygonal surfaces. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 55-64, 1992.
Sebastien Valette and Jean Marc Chassery. Approximated centroidal voronoi diagrams for uniform polygonal mesh coarsening. Computer Graphics Forum, 2004.
A. Vlachos, J. Peters, C. Boyd, and J. L. Mitchell. Curved PN triangles. In Symposium on Interactive 3D Graphics, pages 159-166, 2001.
J. Vorsatz, C. R össl, L. Kobbelt, and H.-P. Seidel. Feature sensitive remeshing. Computer Graphics Forum, pages 393-401, 2001.
J. Vorsatz, C. R össl, and H.-P. Seidel. Dynamic remeshing and applications. In SMA ’03: Proceedings of the 3th ACM Symposium on Solid Modeling and Applications 2003, pages 167-175. ACM Press, 2003.
D.J. Walton and D.S. Meek. A triangular G1 patch from boundary curves. Computer Aided Design, 28(2):113-123, 1996.
Jianhua Wu and Leif Kobbelt. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum, 24(3):277-284, 2005.
Soji Yamakawa and Kenji Shimada. Triangular/quadrilateral remeshing of an arbitrary polygonal surface via packing bubbles. In Proceedings of Geometric Modeling and Processing 2004, Los Alamitos, 2004. IEEE Computer Society.
Dong-Ming Yan, Yang Liu, and Wenping Wang. Quadric surface extraction by variational shape approximation. In Proceedings of Geometric Modeling and Processing 2006, 2006.
D. Zorin and P. Schr öder. Subdivision for modeling and animation. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Alliez, P., Ucelli, G., Gotsman, C., Attene, M. (2008). Recent Advances in Remeshing of Surfaces. In: De Floriani, L., Spagnuolo, M. (eds) Shape Analysis and Structuring. Mathematics and Visualization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-33265-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-33265-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33264-0
Online ISBN: 978-3-540-33265-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)