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

research-article

Efficient evaluation of continuous signed distance to a polygonal mesh

Authors:

Mathieu Sanchez,

Oleg Fryazinov,

Alexander PaskoAuthors Info & Claims

SCCG '12: Proceedings of the 28th Spring Conference on Computer Graphics

Pages 101 - 108

https://doi.org/10.1145/2448531.2448544

Published: 02 May 2012 Publication History

Abstract

An efficient representation of a polygonal mesh by a signed continuous distance field is the main focus of this work. We compare different approaches to implementing such a representation and choose the most efficient one. Several optimizations to the existing methods are presented including the new traversal technique for the BVH-based signed distance evaluation and packet queries. We also discuss details of the GPU implementation of the efficient signed distance evaluation. Several application examples are presented such as blending set operations, linear metamorphosis, space-time blending and microstructure generation for polygonal meshes.

References

[1]

Baerentzen, J. A., and Aanaes, H. 2005. Signed distance computation using the angle weighted pseudonormal. IEEE Transactions on Visualization and Computer Graphics 11 (May), 243--253.

Digital Library

[2]

Buchele, S. F., and Crawford, R. H. 2003. Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations. In Proceedings of the eighth ACM symposium on Solid modeling and applications, ACM, New York, NY, USA, SM '03, 135--144.

Digital Library

[3]

Cohen-Or, D., Solomovic, A., and Levin, D. 1998. Three-dimensional distance field metamorphosis. ACM Trans. Graph. 17 (April), 116--141.

Digital Library

[4]

Dammertz, H., Hanika, J., Keller, and A. 2008. Shallow bounding volume hierarchies for fast SIMD ray tracing of incoherent rays. Computer Graphics Forum 27, 4 (June), 1225--1233.

Digital Library

[5]

Ericson, C. 2004. Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3D Technology). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

Digital Library

[6]

Erleben, K., and Dohlmann, H. 2008. Signed distance fields using single-pass gpu scan conversion of tetrahedra. In GPU Gems 3, H. Nguyen, Ed. Addison-Wesley, 741--763.

[7]

Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, SIGGRAPH '00, 249--254.

Digital Library

[8]

Gagvani, N., and Silver, D. 1999. Parameter-controlled volume thinning. CVGIP: Graph. Models Image Process. 61 (May), 149--164.

Digital Library

[9]

Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obb-tree: a hierarchical structure for rapid interference detection. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH '96, 171--180.

Digital Library

[10]

Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex rigid bodies with stacking. ACM Trans. Graph. 22 (July), 871--878.

Digital Library

[11]

Guéziec, A. 2001. 'meshsweeper': Dynamic point-to-polygonal-mesh distance and applications. IEEE Transactions on Visualization and Computer Graphics 7 (January), 47--61.

Digital Library

[12]

Hart, J. C. 1996. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 10, 527--545.

[13]

Havran, V. 2000. Heuristic Ray Shooting Algorithms. Ph.d. thesis, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague.

[14]

Hoppe, H. 1996. Progressive Meshes. Computer Graphics 30, Annual Conference Series, 99--108.

Digital Library

[15]

Jones, M. W., Baerentzen, J. A., and Sramek, M. 2006. 3d distance fields: A survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics 12 (July), 581--599.

Digital Library

[16]

Jones, M. W. 1996. The production of volume data from triangular meshes using voxelisation. Computer Graphics Forum 15, 311--318.

[17]

Ju, T. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23 (Aug.), 888--895.

Digital Library

[18]

Larsen, E., Gottschalk, S., Lin, M. C., and Manocha, D. 2000. Fast distance queries with rectangular swept sphere volumes. In Proc. of IEEE Int. Conference on Robotics and Automation, 3719--3726.

[19]

Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition of unity implicits. ACM Trans. Graph. 22 (July), 463--470.

Digital Library

[20]

Pasko, A., Adzhiev, V., Sourin, A., and Savchenko, V. 1995. Function representation in geometric modeling: concepts, implementation and applications. The Visual Computer 11, 8, 429--446.

[21]

Pasko, G., Pasko, E., and Kunii, T. 2004. Space-time blending. Journal of Computer Animation and Virtual Worlds 15, 109--121.

Digital Library

[22]

Pasko, A., Fryazinov, O., Vilbrandt, T., Fayolle, P.-A., and Adzhiev, V. 2011. Procedural function-based modelling of volumetric microstructures. Graphical Models 73, 5, 165--181.

Digital Library

[23]

Payne, B. A., and Toga, A. W. 1992. Distance field manipulation of surface models. IEEE Comput. Graph. Appl. 12 (January), 65--71.

Digital Library

[24]

Rosenfeld, A., and Pfaltz, J. L. 1966. Sequential operations in digital picture processing. J. ACM 13 (October), 471--494.

Digital Library

[25]

Wu, J., and Kobbelt, L. 2003. Piecewise linear approximation of signed distance fields. In Proceedings of Vision, modeling and Visualization 03, 513--520.

[26]

Yngve, G., and Turk, G. 2002. Robust creation of implicit surfaces from polygonal meshes. IEEE Transactions on Visualization and Computer Graphics 8 (October), 346--359.

Digital Library

[27]

Zhao, H., and Osher, S. 2002. Visualization, analysis and shape reconstruction of unorganized data sets. In Geometric Level Set Methods in Imaging, Vision and Graphics, S. Osher and N. Paragios, Eds. Springer-Verlag.

Cited By

Bálint CBán RValasek G(2024)Computing the Cut Locus, Voronoi Diagram, and Signed Distance Function of PolygonsComputer Aided Geometric Design10.1016/j.cagd.2024.102388(102388)Online publication date: Sep-2024
https://doi.org/10.1016/j.cagd.2024.102388
Lambourne JWillis KJayaraman PZhang LSanghi AMalekshan K(2022)Reconstructing editable prismatic CAD from rounded voxel modelsSIGGRAPH Asia 2022 Conference Papers10.1145/3550469.3555424(1-9)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3550469.3555424
Zhu XWang Y(2022)A Simple Automatic Hexahedron Mesh Generation and Polyhedral Smoothed Finite Element Method for Mechanics ProblemsComputer-Aided Design10.1016/j.cad.2022.103391152(103391)Online publication date: Nov-2022
https://doi.org/10.1016/j.cad.2022.103391
Show More Cited By

Index Terms

Efficient evaluation of continuous signed distance to a polygonal mesh
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Convolution Filtering of Continuous Signed Distance Fields for Polygonal Meshes

Signed distance fields obtained from polygonal meshes are commonly used in various applications. However, they can have C1 discontinuities causing creases to appear when applying operations such as blending or metamorphosis. The focus of this work is to ...
Precise Hausdorff distance computation between polygonal meshes

We present an exact algorithm for computing the precise Hausdorff distance between two general polyhedra represented as triangular meshes. The locus of candidate points, events where the Hausdorff distance may occur, is fully classified. These events ...
Untangling polygonal and polyhedral meshes via mesh optimization

We propose simple and efficient optimization-based untangling strategies for 2D polygonal and 3D polyhedral meshes. The first approach uses a size-based mesh metric, which eliminates inverted elements by averaging element size over the entire mesh. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SCCG '12: Proceedings of the 28th Spring Conference on Computer Graphics

March 2013

158 pages

ISBN:9781450319775

DOI:10.1145/2448531

Conference Chair:
Carol O'Sullivan
Trinity College Dublin, Ireland

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Comenius University: Comenius University
SIS: Slovak informatics society

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

EU Interreg IVA project

Conference

SCCG'12

Sponsor:

Comenius University
SIS

SCCG'12: Spring Conference on Computer Graphics

May 2 - 4, 2012

Budmerice, Slovakia

Acceptance Rates

Overall Acceptance Rate 67 of 115 submissions, 58%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
377
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bálint CBán RValasek G(2024)Computing the Cut Locus, Voronoi Diagram, and Signed Distance Function of PolygonsComputer Aided Geometric Design10.1016/j.cagd.2024.102388(102388)Online publication date: Sep-2024
https://doi.org/10.1016/j.cagd.2024.102388
Lambourne JWillis KJayaraman PZhang LSanghi AMalekshan K(2022)Reconstructing editable prismatic CAD from rounded voxel modelsSIGGRAPH Asia 2022 Conference Papers10.1145/3550469.3555424(1-9)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3550469.3555424
Zhu XWang Y(2022)A Simple Automatic Hexahedron Mesh Generation and Polyhedral Smoothed Finite Element Method for Mechanics ProblemsComputer-Aided Design10.1016/j.cad.2022.103391152(103391)Online publication date: Nov-2022
https://doi.org/10.1016/j.cad.2022.103391
Barill GDickson NSchmidt RLevin DJacobson A(2018)Fast winding numbers for soups and cloudsACM Transactions on Graphics10.1145/3197517.320133737:4(1-12)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201337
Koschier DDeul CBrand MBender J(2017)An hp-adaptive discretization algorithm for signed distance field generationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2017.273020223:10(2208-2221)Online publication date: 1-Oct-2017
https://doi.org/10.1109/TVCG.2017.2730202
Koschier DDeul CBender JSolenthaler BTeschner MKavan LWojtan C(2016)Hierarchical hp-adaptive signed distance fieldsProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2982818.2982844(189-198)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.5555/2982818.2982844
Mcloughlin LFryazinov OMoseley MSanchez MAdzhiev VComninos PPasko A(2016)Virtual Sculpting and 3D Printing for Young People with DisabilitiesIEEE Computer Graphics and Applications10.1109/MCG.2016.136:1(22-28)Online publication date: Jan-2016
https://doi.org/10.1109/MCG.2016.1
Barclay JDhokia VNassehi A(2016)Additive Manufacturing Simulation Using Signed Distance FieldsSustainable Design and Manufacturing 201610.1007/978-3-319-32098-4_37(435-444)Online publication date: 2-Apr-2016
https://doi.org/10.1007/978-3-319-32098-4_37
Sanchez MFryazinov OFayolle PPasko A(2015)Convolution Filtering of Continuous Signed Distance Fields for Polygonal MeshesComputer Graphics Forum10.1111/cgf.1259934:6(277-288)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1111/cgf.12599

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents