Geometric constraint solver using multivariate rational spline functions

ABSTRACT

We present a new approach to building a solver for a set of geometric constraints represented by multivariate rational functions. The constraints are formulated using inequalities as well as equalities. When the solution set has dimension larger than zero, we approximate it by fitting a hypersurface to discrete solution points. We also consider a variety of constraint solving problems common in geometric modeling. These include computing ray-traps, bisectors, sweep envelopes, and regions accessible during 5-axis machining.

REFERENCES

• 1: K. Abdel-Malek and H.-J. Yeh. Geometric representation of the swept volume using Jacobian rank-deficiency conditions. Computer-Aided Design, Vol 29, pp 457--468, 1997.
• 2: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: G. Elber and E. Cohen. A unified approach to verification in 5- axis freeform milling environments. Computer-Aided Design, Vol 31, No 13, pp 795-804, November 1999.
• 4: Gershon Elber , Myung-So Kim, The bisector surface of rational space curves, ACM Transactions on Graphics (TOG), v.17 n.1, p.32-49, Jan. 1998 [doi>10.1145/269799.269801]
• 5: Gershon Elber , Myung-Soo Kim, Computing Rational Bisectors, IEEE Computer Graphics and Applications, v.19 n.6, p.76-81, November 1999 [doi>10.1109/38.799747]
• 6: G. Elber and M.-S. Kim. A computational model for nonrational bisector surfaces: curve-surface and surface-surface bisectors. Proc. of Geometric Modeling and Processing 2000, Hong Kong, pp 364-372, April 10-12, 2000.
• 7: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 8: R. T. Farouki , V. T. Rajan, On the numerical condition of polynomials in Berstein form, Computer Aided Geometric Design, v.4 n.3, p.191-216, Nov., 1987 [doi>10.1016/0167-8396(87)90012-4]
• 9: G. H. Golub and C. E Van Loan. Matrix Computation. The Johns Hopkins University Press, Baltimore and London, Third Edition, 1996.
• 10: H.-S. Heo, M.-S. Kim, and G. Elber. The intersection of two ruled surfaces. Computer-Aided Design, Vol 31, No 1, pp 33- 50, January 1999.
• 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: IRIT 8.0 User's Manual, September 2000, Technion. www.cs.technion,ac.il/irit.
• 13: Kenneth I. Joy , Mark A. Duchaineau, Boundary Determination for Trivariate Solids, Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, p.82, October 05-07, 1999
• 14: J. Lane and R. Riesenfeld. Bounds on a polynomial. BIT, Vol 21, pp 112-117, 1981.
• 15: 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
• 16: D. G. Luenberger. Linear and Nonlinear Programming. Second Edition, Addison-Wesley, Menlo Park, California, 1984.
• 17: R. R. Martin , P. C. Stephenson, Sweeping of three-dimensional objects, Computer-Aided Design, v.22 n.4, p.223-234, May 1990 [doi>10.1016/0010-4485(90)90051-D]
• 18: Tomoyuki Nishita , Thomas W. Sederberg , Masanori Kakimoto, Ray tracing trimmed rational surface patches, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.337-345, Aug. 1990
• 19: S. Tabachnikov. Billiards. Paris: Societe Mathematique de France, 1995.
• 20: Thomas W. Sederberg , Ray J. Meyers, Loop detection in surface patch intersections, Computer Aided Geometric Design, v.5 n.2, p.161-171, July 1988 [doi>10.1016/0167-8396(88)90029-5]
• 21: T. W. Sederberg and A. K. Zundel. Pyramids that bound purface patches. Graphical Models and Image Processing, Vol 58, No 1, pp 75-81, 1996.
• 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: D. Wells. The Penguin Dictionary of Curious and Interesting Geometry Penguin Books, New York, 1991.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Design, Measurement, Performance, Theory