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

research-article

Signed Distance Computation Using the Angle Weighted Pseudonormal

Authors:

J. Andreas Baerentzen,

Henrik AanaesAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 11, Issue 3

Pages 243 - 253

https://doi.org/10.1109/TVCG.2005.49

Published: 01 May 2005 Publication History

Abstract

The normals of closed, smooth surfaces have long been used to determine whether a point is inside or outside such a surface. It is tempting to also use this method for polyhedra represented as triangle meshes. Unfortunately, this is not possible since, at the vertices and edges of a triangle mesh, the surface is not C^1 continuous, hence, the normal is undefined at these loci. In this paper, we undertake to show that the angle weighted pseudonormal (originally proposed by Thürmer and Wüthrich and independently by Séquin) has the important property that it allows us to discriminate between points that are inside and points that are outside a mesh, regardless of whether a mesh vertex, edge, or face is the closest feature. This inside-outside information is usually represented as the sign in the signed distance to the mesh. In effect, our result shows that this sign can be computed as an integral part of the distance computation. Moreover, it provides an additional argument in favor of the angle weighted pseudonormals being the natural extension of the face normals. Apart from the theoretical results, we also propose a simple and efficient algorithm for computing the signed distance to a closed C^0 mesh. Experiments indicate that the sign computation overhead when running this algorithm is almost negligible.

References

[1]

G. Thürmer and C. Wüthrich, “Computing Vertex Normals from Polygonal Facets,” J. Graphics Tools, vol. 3, no. 1, pp. 43-46, 1998.

Digital Library

[2]

C.H. Séquin, “Procedural Spline Interpolation in Unicubix,” Proc. Third USENIX Computer Graphics Workshop, pp. 63-83, 1986.

[3]

B. Payne and A. Toga, “Distance Field Manipulation of Surface Models,” IEEE Computer Graphics and Applications, vol. 12, no. 1, pp. 65-71, 1992.

Digital Library

[4]

A. Guéziec, “Meshsweeper: Dynamic Point-to-Polygonal Mesh Distance and Applications,” IEEE Trans. Visualization and Computer Graphics, vol. 7, no. 1, pp. 47-60, Jan.-Mar. 2001.

Digital Library

[5]

J. Sethian, Level Set Methods and Fast Marching Methods Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge Univ. Press, 1999.

[6]

S.J. Osher and R.P. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, first ed. Springer Verlag, Nov. 2002.

[7]

Geometric Level Set Methods in Imaging, Vision, and Graphics, S.nbspOsher and N. Paragios, eds. Springer, 2003.

Digital Library

[8]

M. Lin and S. Gottschalk, “Collision Detection between Geometric Models: A Survey,” Proc. IMA Conf. Math. of Surfaces, 1998.

[9]

M.G. Coutinho, Dynamic Simulations of Multibody Systems. Springer, 2001.

Digital Library

[10]

E. Guendelman R. Bridson and R.P. Fedkiw, “Nonconvex Rigid Bodies with Stacking,” ACM Trans. Graphics, vol. 22, no. 3, pp. 871-878, 2003.

Digital Library

[11]

J. Linhart, “A Quick Point-in-Polyhedron Test,” Computers & Graphics, vol. 14, no. 3, pp. 445-448, 1990.

[12]

F.R. Feito and J.C. Torres, “Inclusion Test for General Polyhedra,” Computers & Graphics, vol. 21, no. 1, pp. 23-30, 1997.

[13]

P.C.P. Carvalho and P.R. Cavalcanti, “Point in Polyhedron Testing Using Spherical Polygons,” Graphics Gems V, A.W. Paeth, ed., pp.nbsp42-49, AP Professional, 1995.

[14]

M. Jones, “The Production of Volume Data from Triangular Meshes Using Voxelisation,” Computer Graphics Forum, vol. 15,no. 5, pp. 311-318, 1996.

[15]

F. Dachille and A. Kaufman, “Incremental Triangle Voxelization,” Proc. Graphics Interface 2000, pp. 205-212, 2000.

[16]

S. Mauch, “Efficient Algorithms for Solving Static Hamilton-Jacobi Equations,” PhD dissertation, Caltech, 2003.

Digital Library

[17]

C. Sigg R. Peikert and M. Gross, “Signed Distance Transform Using Graphics Hardware,” Proc. IEEE Visualization '03, pp. 83-90, 2003.

Digital Library

[18]

A. Sud M.A. Otaduy and D. Manocha, “Difi: Fast 3D Distance Field Computation Using Graphics Hardware,” Proc. Eurographics, vol. 23,no. 3, 2004.

[19]

J. Foley A. van Dam S. Feiner and J. Hughes, Computer Graphics: Principles and Practice in C, second ed. Addison-Wesley, 1995.

Digital Library

[20]

S.F.F. Gibson R.N. Perry A.P. Rockwood and T.R. Jones, “Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics,” Proc. SIGGRAPH 2000, pp. 249-254, 2000.

Digital Library

[21]

J. Huang Y. Li R. Crawfis S.-C. Lu and S.-Y. Liou, “A Complete Distance Field Representation,” Proc. Visualization 2001, pp. 247-254, 2001.

Digital Library

[22]

D.E. Johnson and E. Cohen, “Bound Coherence for Minimum Distance Computations,” Proc. 1999 IEEE Int'l Conf. Robotics and Automation, pp. 1843-1848, 1999.

[23]

E. Larsen S. Gottschalk M.C. Lin and D. Manocha, “Fast Proximity Queries with Swept Sphere Volumes,” technical report, Dept. of Computer Science, Univ. of North Carolina Chapel Hill, 1999.

[24]

J. Wu and L. Kobbelt, “Piecewise Linear Approximation of Signed Distance Fields,” Proc. Vision, Modeling, and Visualization 2003, 2003.

[25]

H. Fuchs Z. Kedem and B. Naylor, “On Visible Surface Generation by A Priori Tree Structures,” Proc. Seventh Ann. Conf. Computer Graphics and Interactive Techniques, pp. 124-133, 1980.

Digital Library

[26]

H. Gouraud, “Continuous Shading of Curved Surfaces,” IEEE Trans. Computers, vol. 20, no. 6, pp. 623-629, June 1971.

Digital Library

[27]

A.S. Glassner, Computing Surface Normals for 3D Models, pp. 562-566. Academic Press, 1990.

Digital Library

[28]

N. Max, “Weights for Computing Vertex Normals from Facet Normals,” J. Graphics Tools, vol. 4, no. 2, pp. 1-6, 1999.

Digital Library

[29]

H. Aanaes and J.A. Baerentzen, “Pseudo-Normals for Signed Distance Computation,” Proc. Vision, Modeling, and Visualization 2003, 2003.

[30]

P. Sander X. Gu S. Gortler H. Hoppe and J. Snyder, “Silhouette Clipping,” Proc. ACM SIGGRAPH Conf. Computer Graphics, pp.nbsp327-334, 2000.

Digital Library

[31]

G. vandenBergen, Collision Detection in Interactive 3D Environments. Morgan Kaufmann, 2004.

[32]

S. Gottschalk, “Collision Queries Using Oriented Bounding Boxes,” PhD dissertation, Univ. of North Carolina at Chapel Hill, 2000.

Digital Library

[33]

M. Botsch and L. Kobbelt, “A Robust Procedure to Eliminate Degenerate Faces from Triangle Meshes,” Vision, Modeling, Visualization 2001 Proc., 2001.

Digital Library

[34]

K. Erleben and H. Dohlmann, personal communications.

[35]

J.R. Shewchuk, “Robust Adaptive Floating-Point Geometric Predicates,” Proc. 12th Ann. Symp. Computational Geometry, pp.nbsp141-150, May 1996.

Digital Library

Cited By

Feng NCrane K(2024)A Heat Method for Generalized Signed DistanceACM Transactions on Graphics10.1145/365822043:4(1-19)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658220
Kusupati UGaillard MThiery JKaiser A(2024)Semantic Shape Editing with Parametric Implicit TemplatesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657421(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657421
Jensen PBærentzen JDahl ADahl V(2024)Finding Space-Time Boundaries with Deformable HypersurfacesJournal of Mathematical Imaging and Vision10.1007/s10851-024-01185-y66:3(380-392)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10851-024-01185-y
Show More Cited By

Index Terms

Signed Distance Computation Using the Angle Weighted Pseudonormal
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A double layer method for constructing signed distance fields from triangle meshes

A new algorithm is proposed for constructing signed distance fields (SDF) from triangle meshes. In our approach, both the internal and external distance fields for the triangle mesh are computed first. Then the desired SDF is computed directly from ...
Signed distance fields for polygon soup meshes
GI '14: Proceedings of Graphics Interface 2014

Many meshes in computer animation practice are meant to approximate solid objects, but the provided triangular geometry is often unoriented, non-manifold or contains self-intersections, causing inside/outside of objects to be mathematically ill-defined. ...
Multiresolution remeshing using weighted centroidal voronoi diagram
ICCS'06: Proceedings of the 6th international conference on Computational Science - Volume Part II

We present a novel method for multiresolution remeshing of irregular mesh. First, the original mesh (two-manifold any genus) is decomposed into several patches, each patch is homeomorphic to a 2D triangle. The goal of this decomposition process is that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 11, Issue 3

May 2005

112 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © 2005.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 May 2005

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng NCrane K(2024)A Heat Method for Generalized Signed DistanceACM Transactions on Graphics10.1145/365822043:4(1-19)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658220
Kusupati UGaillard MThiery JKaiser A(2024)Semantic Shape Editing with Parametric Implicit TemplatesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657421(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657421
Jensen PBærentzen JDahl ADahl V(2024)Finding Space-Time Boundaries with Deformable HypersurfacesJournal of Mathematical Imaging and Vision10.1007/s10851-024-01185-y66:3(380-392)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10851-024-01185-y
Chermain XZanni CMartínez JHugron PLefebvre S(2023)Orientable Dense Cyclic Infill for Anisotropic Appearance FabricationACM Transactions on Graphics10.1145/359241242:4(1-13)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592412
Malyshev ANoreika A(2023)Numerical Method for 3D Quantification of Glenoid Bone LossComputational Science – ICCS 202310.1007/978-3-031-36027-5_21(289-296)Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36027-5_21
Juhl KMorales Xde Backer OCamara OPaulsen R(2021)Implicit Neural Distance Representation for Unsupervised and Supervised Classification of Complex AnatomiesMedical Image Computing and Computer Assisted Intervention – MICCAI 202110.1007/978-3-030-87196-3_38(405-415)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-87196-3_38
Krayer BMüller S(2019)Generating signed distance fields on the GPU with ray mapsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01683-w35:6-8(961-971)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01683-w
Minor D(2018)Making space for cloth simulations using energy minimizationACM SIGGRAPH 2018 Talks10.1145/3214745.3214764(1-2)Online publication date: 12-Aug-2018
https://dl.acm.org/doi/10.1145/3214745.3214764
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
Li YBarbič J(2018)Immersion of self-intersecting solids and surfacesACM Transactions on Graphics10.1145/3197517.320132737:4(1-14)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201327
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents