Computing surface offsets and bisectors using a sampled constraint solver

ABSTRACT

This paper describes SCSolver, a geometric constraint solver based on adaptive sampling of an underlying constraint space. The solver is demonstrated on the computation of the offset to a surface as well as the computation of the bisector between two surfaces. The adaptive constraint sampling generates a solution manifold through a generalized dual-contouring approach appropriate for higher-dimensional problems. Experimental results show that the SCSolver approach can compute solutions for complex input geometry at interactive rates for each example application.

REFERENCES

• 1: David E. Breen , Sean Mauch , Ross T. Whitaker, 3D scan conversion of CSG models into distance volumes, Proceedings of the 1998 IEEE symposium on Volume visualization, p.7-14, October 19-20, 1998, Research Triangle Park, North Carolina, United States [doi>10.1145/288126.288137]
• 2: Xianming Chen , Richard F. Riesenfeld , Elaine Cohen , James Damon, Theoretically-based algorithms for robustly tracking intersection curves of deforming surfaces, Computer-Aided Design, v.39 n.5, p.389-397, May, 2007 [doi>10.1016/j.cad.2007.02.015]
• 3: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 4: Gershon Elber , Myung-Soo Kim, Geometric constraint solver using multivariate rational spline functions, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.1-10, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376958]
• 5: J.-c. L. Fabian Schwarzer, Mitul Saha. Exact collision checking of robot paths, 2002.
• 6: M. Foskey, M. Garber, M. Lin, and D. Manocha. A voronoi-based hybrid motion planner for rigid bodies, 2001.
• 7: 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]
• 8: Gregory Michael Hunter, Efficient computation and data structures for graphics., Princeton University, Princeton, NJ, 1978
• 9: João Batista S. de Oliveira , Luiz Henrique de Figueiredo, Robust Approximation of Offsets and Bisectors of Plane Curves, Proceedings of the 13th Brazilian Symposium on Computer Graphics and Image Processing, p.139-145, October 17-20, 2000
• 10: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: Myung-Soo Kim , Gershon Elber, Problem Reduction to Parameter Space, Proceedings of the 9th IMA Conference on the Mathematics of Surfaces, p.82-98, September 04-07, 2000
• 12: E. Larsen, S. Gottschalk, M. Lin, and D. Manocha. Fast distance queries with rectangular swept sphere volumes. In IEEE International Conference on Robotics and Automation (ICRA), pages 24--48, 2000.
• 13: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 14: K. Museth, D. Breen, R. Whitaker, S. Mauch, and D. Johnson. Algorithms for interactive editing of level set models. Computer Graphics Forum, 24(4):1--22, 2005.
• 15: Sotiris L. Omirou , Andreas C. Nearchou, A CNC machine tool interpolator for surfaces of cross-sectional design, Robotics and Computer-Integrated Manufacturing, v.23 n.2, p.257-264, April, 2007 [doi>10.1016/j.rcim.2006.01.001]
• 16: Nicholas M. Patrikalakis, Shape Interrogation for Computer Aided Design and Manufacturing, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 17: D. Pavic and L. Kobbelt. High-resolution volumetric computation of offset surfaces with feature preservation. Computer Graphics Forum, 27(2): 165--174, April 2008.
• 18: Joon-Kyung Seong , Elaine Cohen , Gershon Elber, Voronoi diagram computations for planar NURBS curves, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York [doi>10.1145/1364901.1364913]
• 19: J.-K. Seong, G. Elber, and E. Cohen. Simultaneous precise solutions to the visibility problem of sculptured models. In GMP, pages 451--464, 2006.
• 20: J.-K. Seong, G. Elber, and M.-S. Kim. Trimming local and global self-intersections in offset curves/surfaces using distance maps. Computer Aided Design, 38(3):183--193, 2006.
• 21: Joon-Kyung Seong , David E Johnson , Elaine Cohen, A higher dimensional formulation for robust and interactive distance queries, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom [doi>10.1145/1128888.1128916]
• 22: Evan C. Sherbrooke , Nicholas M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, v.10 n.5, p.379-405, Oct. 1993 [doi>10.1016/0167-8396(93)90019-Y]
• 23: Heinz Siegfried, Surface Reconstruction and Variable Offset, CAD Systems Development: Tools and Methods [Dagstuhl Seminar, 1995], p.199-206, January 1997
• 24: A. Sud, M. Otaduy, and D. Manocha. Difi: Fast 3d distance field computation using graphics hardware. Computer Graphics Forum, 23(3):557--566, 2004.
• 25: K. Wentland and D. Dutta. Method for offset-curve generation for sheet-metal design. Computer-Aided Design, 25(10):662--670, 1993.

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