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

research-article

'Meshsweeper': Dynamic Point-to-Polygonal-Mesh Distance and Applications

Author:

André GuéziecAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 7, Issue 1

Pages 47 - 61

https://doi.org/10.1109/2945.910820

Published: 01 January 2001 Publication History

Abstract

We introduce a new algorithm for computing the distance from a point to an arbitrary polygonal mesh. Our algorithm uses a multiresolution hierarchy of bounding volumes generated by geometric simplification. Our algorithm is dynamic, exploiting coherence between subsequent queries using a priority process and achieving constant time queries in some cases. It can be applied to meshes that transform rigidly or deform nonrigidly. We illustrate our algorithm with a simulation of particle dynamics and collisions with a deformable mesh, the computation of distance maps and offset surfaces, the computation of an approximation to the expensive Hausdorff distance between two shapes, and the detection of self-intersections. We also report comparison results between our algorithm and an alternative algorithm using an octree, upon which our method permits an order-of-magnitude speed-up.

References

[1]

L. Markosian J.M. Cohen T. Crulli and J. Hughes, “Skin: A Constructive Approach to Modeling Free-Form Shapes,” SIGGRAPH '99 Proc., pp. 393-400, Aug. 1999.

Digital Library

[2]

D. Baraff, “Curved Surfaces and Coherence for Non-Penetrating Rigid Body Simulation,” Computer Graphics, vol. 24, no. 4, pp. 19-28, 1990.

Digital Library

[3]

E. Gilbert D. Johnson and S. Keerthi, “A Fast Procedure for Computing the Distance between Complex Objects in Three-Dimensional Space,” IEEE J. Robotics and Automation, vol. 4, pp. 193-203, Apr. 1988.

[4]

M. Lin, “Efficient Collision Detection for Animation and Robotics,” PhD thesis, Univ. of California, Berkeley, 1993.

Digital Library

[5]

F. Aurenhammer, “Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, pp. 345-405, 1991.

Digital Library

[6]

K.E. Hoff T. Culver J. Keyser M. Lin and D. Manocha, “Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware,” SIGGRAPH '99 Proc., pp. 277-285, Aug. 1999.

Digital Library

[7]

H. Samet, The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.

Digital Library

[8]

H. Samet, Applications of Spatial Data Structures. Reading, Mass.: Addison-Wesley, 1990.

Digital Library

[9]

O. Guenther, “Efficient Structures for Geometric Data Management,” PhD thesis, Univ. of California at Berkeley, 1987.

Digital Library

[10]

H. Hoppe, “Progressive Meshes,” SIGGRAPH '96 Proc., pp. 99-108, Aug. 1996.

Digital Library

[11]

L. Kobbelt J. Vorsatz and H.-P. Seidel, “Multiresolution Hierarchies on Unstructured Triangle Meshes,” Computational Geometry: Theory and Applications, vol. 14, pp. 5-24, Dec. 1999.

Digital Library

[12]

S. Quinlan, “Efficient Distance Computation between Non-Convex Objects,” Proc. Conf. Robotics and Automation, pp. 3324-3329, 1994.

[13]

E. Larsen S. Gottschalk M.C. Lin and D. Manocha, “Fast Proximity Queries with Swept Sphere Volumes,” Technical Report TR99-018, Univ. of North Carolina Chapel Hill, 1999.

[14]

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

[15]

P. Besl and N. McKay, “A Method for Registration of 3-D Shapes,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 239-256, Feb. 1992.

Digital Library

[16]

D.A. Simon, “Fast and Accurate Shape-Based Registration,” PhD thesis, Carnegie Mellon Univ., CMU-RI-TR-96-45, Dec. 1996.

Digital Library

[17]

S. Gottschalk M.C. Lin and D. Manocha, “Obbtree: A Hierarchical Structure for Rapid Interference Detection,” SIGGRAPH '96 Proc., pp. 171-180, Aug. 1996.

Digital Library

[18]

D. Johnson and E. Cohen, “A Framework for Efficient Minimum Distance Computation,” Proc. Conf. Robotics and Automation, pp. 3678-3683, 1998.

[19]

J.T. Klosowski M. Held J.S.B. Mitchell H. Sowizral and K. Zikan, “Efficient Collision Detection Using Bounding Volume Hierarchies of k-dops,” IEEE Trans. Visualization and Computer Graphics, vol. 4, no. 1, pp. 21-36, Jan.-Mar. 1998.

Digital Library

[20]

J.C. Xia and A. Varshney, “Dynamic View-Dependent Simplification for Polygonal Models,” Proc. Visualization 96, R. Yagel and G. Nielson, eds., pp. 327-334, Oct. 1996.

Digital Library

[21]

H. Hoppe, “View-Dependent Refinement of Progressive Meshes,” Proc. SIGGRAPH '97, pp. 189-198, Aug. 1997.

Digital Library

[22]

L. De Floriani P. Magillo and E. Puppo, “Building and Traversing a Surface at Variable Resolution,” Proc. Visualization '97, pp. 103-110, 1997.

Digital Library

[23]

A. Maheshwahri P. Morin and J.-R. Sack, “Progressive TINs: Algorithms and Applications,” Proc. Fifth Int'l Workshop Advances in Geographic Information Systems, pp. 24-29, 1997.

Digital Library

[24]

A. Guéziec G. Taubin F. Lazarus and W. Horn, “A Framework for Streaming Geometry in VRML,” IEEE Computer Graphics and Applications, vol. 19, no. 2, pp. 68-78, Mar.-Apr. 1999.

Digital Library

[25]

L. De Floriani and P. Magillo, “Horizon Computation on a Hierarchical Triangulated Terrain Model,” The Visual Computer, vol. 11, pp. 134-149, 1995.

[26]

U. Ramer, “An Iterative Procedure for the Polygonal Approximation of Plane Curves,” Computer Graphics and Image Processing, vol. 1, pp. 244-256, 1972.

[27]

D.H. Douglas and T.K. Peucker, “Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature,” The Canadian Cartographer, vol. 10, no. 2, pp. 112-122, Dec. 1973.

[28]

J. Cohen M. Olano and D. Manocha, “Appearance-Preserving Simplification,” Proc. SIGGRAPH '98, pp. 115-122, July 1998.

Digital Library

[29]

C. Bajaj and D. Schikore, “Error-Bounded Reduction of Triangle Meshes with Multivariate Data,” Proc. Visual Data Exploration and Analysis III, pp. 34-45, Mar. 1996.

[30]

A. Guéziec, “Locally Toleranced Polygonal Surface Simplification,” IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 2, pp. 178-199, Apr.-June 1999.

Digital Library

[31]

M. Garland and P. Heckbert, “Surface Simplification Using Quadric Error Metrics,” SIGGRAPH '97 Proc., pp. 209-216, Aug. 1997.

Digital Library

[32]

H. Hoppe, “New Quadric Metric for Simplifying Meshes with Appearance Attributes,” Proc. Visualization '99, pp. 59-66, Oct. 1999.

Digital Library

[33]

R. Ronfard and J. Rossignac, “Full-Range Approximation of Triangulated Polyhedra,” Computer Graphics Forum, vol. 15,no. 3, pp. C67-C76, 1996.

[34]

T.H. Cormen C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. MacGraw-Hill, 1989.

Digital Library

[35]

D. Eberly, “Magic Software,” http://www.magic-software.com/, 2000.

[36]

J. Cohen M. Lin D. Manocha and K. Ponamgi, “I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale,” Proc. Symp. Interactive 3D Graphics, pp. 189-196, 1995.

Digital Library

[37]

P.M. Hubbard, “Interactive Collision Detection,” Proc. IEEE Symp. Research Frontiers in Virtual Reality, pp. 24-31, Oct. 1993.

[38]

N. Max, “Visualizing Hilbert Curves,” Proc. Visualization '98, pp. 447-450, Oct. 1998.

Digital Library

[39]

R. Dafner D. Cohen-Or and Y. Matias, “Context-Based Space Filling Curves,” Computer Graphics Forum, vol. 19, no. 3, pp. C209-C217, 2000.

[40]

A. Kaufman, “Efficient Algorithms for 3D Scan-Conversion of Parametric Curves, Surfaces, and Volumes,” Computer Graphics (Proc. SIGGRAPH), vol. 21, no. 4, pp. 171-179, July 1987.

Digital Library

[41]

P.E. Danielsson, “Euclidean Distance Mapping,” Computer Graphics and Image Processing, vol. 14, pp. 227-248, 1980.

[42]

D. Baraff A. Witkin and M. Kass, “Physically Based Modelling,” Course Notes 36, ACM SIGGRAPH '99, Aug. 1999.

[43]

M. Chow, “Optimized Geometry Compression for Real-Time Rendering,” Proc. Visualization '97, pp. 415-421, Oct. 1997.

Digital Library

[44]

G. Taubin W.P. Horn F. Lazarus and J. Rossignac, “Geometry Coding and VRML,” Proc. IEEE, vol. 86, no. 6, pp. 1228-1243, June 1998.

[45]

T. Moeller, “A Fast Triangle-Triangle Intersection Test,” J. Graphics Tools, vol. 2, no. 2, pp. 25-30, 1997.

Digital Library

[46]

P. Volino and N.M. Thalmann, “Efficient Self-Collision Detection on Smoothly Discretized Surface Animations Using Geometrical Shape Regularity,” Computer Graphics Forum, vol. 13, no. 3, pp. C155-C166, 1994.

Cited By

Roullier BMcQuade FAnjum ABower CLiu L(2024)Automated visual quality assessment for virtual and augmented reality based digital twinsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-024-00616-w13:1Online publication date: 26-Feb-2024
https://dl.acm.org/doi/10.1186/s13677-024-00616-w
Zong CXu JSong JChen SXin SWang WTu C(2023)P2M: A Fast Solver for Querying Distance from Point to Mesh SurfaceACM Transactions on Graphics10.1145/359243942:4(1-13)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592439
Jimenez-Fernandez VTlapa-Carrera VVazquez-Leal HFilobello-Nino U(2023)Comparison of outline-based shape descriptors for alphanumeric characters by using piecewise linear functions: the case of vehicle license plates typefaceMultimedia Tools and Applications10.1007/s11042-023-14976-z82:20(31641-31658)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/s11042-023-14976-z
Show More Cited By

Index Terms

'Meshsweeper': Dynamic Point-to-Polygonal-Mesh Distance and Applications
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming
    2. Mathematical optimization

Recommendations

Low budget and high fidelity relaxed 567-remeshing

567-meshes are a new type of closed and 2-manifold triangular meshes introduced by Aghdaii et al. in 2012 1. Vertices with valence less than 5 or greater than 7 are problematic for many mesh processing tasks such as edge collapse or surface subdivision. ...
Smooth surface and triangular mesh: comparison of the area, the normals and the unfolding
SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

Replacing a smooth surface with a triangular mesh (i.e., a polyedron) "close to it" leads to some errors. The geometric properties of the triangular mesh can be very different from the geometric properties of the smooth surface, even if both surfaces ...
An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle range

This paper presents a novel octree-based dual contouring (DC) algorithm for adaptive triangular or tetrahedral mesh generation with guaranteed angle range. First, an adaptive octree is constructed based on the input geometry. Then the octree grid points ...

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 7, Issue 1

January 2001

96 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © Copyright © 2001 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 January 2001

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
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

Roullier BMcQuade FAnjum ABower CLiu L(2024)Automated visual quality assessment for virtual and augmented reality based digital twinsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-024-00616-w13:1Online publication date: 26-Feb-2024
https://dl.acm.org/doi/10.1186/s13677-024-00616-w
Zong CXu JSong JChen SXin SWang WTu C(2023)P2M: A Fast Solver for Querying Distance from Point to Mesh SurfaceACM Transactions on Graphics10.1145/359243942:4(1-13)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592439
Jimenez-Fernandez VTlapa-Carrera VVazquez-Leal HFilobello-Nino U(2023)Comparison of outline-based shape descriptors for alphanumeric characters by using piecewise linear functions: the case of vehicle license plates typefaceMultimedia Tools and Applications10.1007/s11042-023-14976-z82:20(31641-31658)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/s11042-023-14976-z
Sun FChoi YYu YWang W(2016)Medial Meshes – A Compact and Accurate Representation of Medial Axis TransformIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2015.244808022:3(1278-1290)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1109/TVCG.2015.2448080
Aguilera AMelero FFeito F(2016)Out-of-core real-time haptic interaction on very large modelsComputer-Aided Design10.1016/j.cad.2016.04.00277:C(98-106)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.cad.2016.04.002
Getto RKuijper ALandesberger T(2015)Extended surface distance for local evaluation of 3D medical image segmentationsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-015-1113-z31:6-8(989-999)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s00371-015-1113-z
Xu HBarbič JKry PBunt A(2014)Signed distance fields for polygon soup meshesProceedings of Graphics Interface 201410.5555/2619648.2619655(35-41)Online publication date: 7-May-2014
https://dl.acm.org/doi/10.5555/2619648.2619655
Sanchez MFryazinov OPasko AO'Sullivan C(2013)Efficient evaluation of continuous signed distance to a polygonal meshProceedings of the 28th Spring Conference on Computer Graphics10.1145/2448531.2448544(101-108)Online publication date: 10-Mar-2013
https://dl.acm.org/doi/10.1145/2448531.2448544
Rössl CTheisel H(2010)Couple points --- a local approach to global surface analysisProceedings of the 7th international conference on Curves and Surfaces10.1007/978-3-642-27413-8_39(586-602)Online publication date: 24-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-27413-8_39
Allègre RGalin EChaine RAkkouche S(2008)The HybridTreeHeterogeneous objects modelling and applications10.5555/1806158.1806161(60-89)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1806158.1806161
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents