Surface distance maps

ABSTRACT

We present a new parameterized representation called surface distance maps for distance computations on piecewise 2-manifold primitives. Given a set of orientable 2-manifold primitives, the surface distance map represents the (non-zero) signed distance-to-closest-primitive mapping at each point on a 2-manifold. The distance mapping is computed from each primitive to the set of remaining primitives. We present an interactive algorithm for computing the surface distance map of triangulated meshes using graphics hardware. We precompute a surface parameterization and use the it to define an affine transformation for each mesh primitive. Our algorithm efficiently computes the distance field by applying this affine transformation to the distance functions of the primitives and evaluating these functions using texture mapping hardware. In practice, our algorithm can compute very high resolution surface distance maps at interactive rates and provides tight error bounds on their accuracy. We use surface distance maps for path planning and proximity query computation among complex models in dynamic environments. Our approach can perform planning and proximity queries in a dynamic environment with hundreds of objects at interactive rates and offer significant speedups over prior algorithms.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: Ingmar Bitter , Arie E. Kaufman , Mie Sato, Penalized-Distance Volumetric Skeleton Algorithm, IEEE Transactions on Visualization and Computer Graphics, v.7 n.3, p.195-206, July 2001 [doi>10.1109/2945.942688]
• 3: James F. Blinn, Simulation of wrinkled surfaces, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.286-292, August 23-25, 1978
• 4: Heinz Breu , Joseph Gil , David Kirkpatrick , Michael Werman, Linear Time Euclidean Distance Algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.5, p.529-533, May 1995 [doi>10.1109/34.391389]
• 5: Edwin Earl Catmull, A subdivision algorithm for computer display of curved surfaces., The University of Utah, 1974
• 6: H. Choset and J. Burdick. Sensor based motion planning: The hierarchical generalized Voronoi graph. In Algorithms for Robot Motion and Manipulation, pages 47--61. A K Peters, 1996.
• 7: Robert L. Cook, Shade trees, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.223-231, January 1984
• 8: O. Cuisenaire. Distance Transformations: Fast Algorithms and Applications to Medical Image Processing. PhD thesis, Universite Catholique de Louvain, 1999.
• 9: P. E. Danielsson. Euclidean distance mapping. Computer Graphics and Image Processing, 14:227--248, 1980.
• 10: M. Denny. Solving geometric optimization problems using graphics hardware. Computer Graphics Forum, 22(3), 2003.
• 11: Michal Etzion , Ari Rappoport, Computing Voronoi skeletons of a 3-D polyhedron by space subdivision, Computational Geometry: Theory and Applications, v.21 n.3, p.87-120, March, 2002 [doi>10.1016/S0925-7721(01)00056-6]
• 12: I. Fischer and C. Gotsman. Fast approximation of high order Voronoi diagrams and distance transforms on the GPU. Technical report CS TR-07-05, Harvard University, 2005.
• 13: M. Foskey, M. Garber, M. Lin, and D. Manocha. A voronoi-based hybrid planner. Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2001.
• 14: Alain Fournier. Normal distribution functions and multiple surfaces. In Graphics Interface '92 Workshop on Local Illumination, pages 45--52, May 1992.
• 15: Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
• 16: Sarah F. F. Gibson, Using distance maps for accurate surface representation in sampled volumes, Proceedings of the 1998 IEEE symposium on Volume visualization, p.23-30, October 19-20, 1998, Research Triangle Park, North Carolina, United States [doi>10.1145/288126.288142]
• 17: José Gomes , Olivier Faugeras, The Vector Distance Functions, International Journal of Computer Vision, v.52 n.2-3, p.161-187, May-June 2003 [doi>10.1023/A:1022956108418]
• 18: K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Interactive motion planning using hardware accelerated computation of generalized voronoi diagrams. Proceedings of IEEE Conference of Robotics and Automation, 2000.
• 19: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 20: Allison W. Klein , Peter-Pike J. Sloan , Adam Finkelstein , Michael F. Cohen, Stylized video cubes, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545264]
• 21: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 22: Aaron E. Lefohn , Joe M. Kniss , Charles D. Hansen , Ross T. Whitaker, Interactive Deformation and Visualization of Level Set Surfaces Using Graphics Hardware, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.11, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250357]
• 23: Ming Chieh Lin , John F. Canny, Efficient collision detection for animation and robotics, University of California, Berkeley, 1993
• 24: Sean Patrick Mauch , Dan Meiron, Efficient algorithms for solving static hamilton-jacobi equations, California Institute of Technology, Pasadena, CA, 2003
• 25: Calvin R. Maurer, Jr. , Rensheng Qi , Vijay Raghavan, A Linear Time Algorithm for Computing Exact Euclidean Distance Transforms of Binary Images in Arbitrary Dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.2, p.265-270, February 2003 [doi>10.1109/TPAMI.2003.1177156]
• 26: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 27: R. Peikert and C. Sigg. Optimized bounding polyhedra for gpu-based distance transform. In Scientific Visualization: The visual extraction of knowledge from data, 2005.
• 28: Ronald N. Perry , Sarah F. Frisken, Kizamu: a system for sculpting digital characters, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.47-56, August 2001 [doi>10.1145/383259.383264]
• 29: J. A. Sethian. Level set methods and fast marching methods. Cambridge, 1999.
• 30: Christian Sigg , Ronald Peikert , Markus Gross, Signed Distance Transform Using Graphics Hardware, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.12, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250358]
• 31: Avneesh Sud , Naga Govindaraju , Russell Gayle , Dinesh Manocha, Interactive 3D distance field computation using linear factorization, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111432]
• 32: Avneesh Sud , Naga Govindaraju , Russell Gayle , Ilknur Kabul , Dinesh Manocha, Fast proximity computation among deformable models using discrete Voronoi diagrams, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 33: L. Szirmay-Kalos, B. Aszodi, I. Lazanyi, and M. Premecz. Approximate ray-tracing on the gpu with distance impostor. Proc. of Eurographics, 2005.
• 34: M. Teichmann and S. Teller. Polygonal approximation of Voronoi diagrams of a set of triangles in three dimensions. Technical Report 766, Laboratory of Computer Science, MIT, 1997.
• 35: J. Vleugels and M. H. Overmars. Approximating Voronoi diagrams of convex sites in any dimension. International Journal of Computational Geometry and Applications, 8:201--222, 1998.
• 36: M. Woo, J. Neider, and T. Davis. OpenGL Programming Guide, Second Edition. Addison Wesley, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation; Virtual reality

Keywords:
collision detection, deformable models, distance fields, motion planning, parameterization