Geometric constraint solver using multivariate rational spline functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometric constraint solver using multivariate rational spline functions

Full text

Pdf (783 KB)

Source

ACM Symposium on Solid and Physical Modeling archive
Proceedings of the sixth ACM symposium on Solid modeling and applications table of contents

Ann Arbor, Michigan, United States

Pages: 1 - 10

Year of Publication: 2001

ISBN:1-58113-366-9

Authors

Gershon Elber	Department of Computer Science, Technion, Israel Institute of Technology, Haifa 32000, Israel
Myung-Soo Kim	School of Computer Science and Engineering, Seoul National University, Seoul 151-742, Korea

Sponsor

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 43, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/376957.376958 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.

CITED BY 27

	André Galligo , Jean Pascal Pavone, Selfintersections of a bézier bicubic surface, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.148-155, July 24-27, 2005, Beijing, China
	Dae-Eun Hyun , Bert Jüttler , Myung-Soo Kim, Minimizing the distortion of affine spline motions, Graphical Models, v.64 n.2, p.128-144, March 2002
	Iddo Hanniel , Ramanathan Muthuganapathy , Gershon Elber , Myung-Soo Kim, Precise Voronoi cell extraction of free-form rational planar closed curves, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.51-59, June 13-15, 2005, Cambridge, Massachusetts
	Myung-Soo Kim , Gershon Elber , Joon-Kyung Seong, Geometric computations in parameter space, Proceedings of the 21st spring conference on Computer graphics, May 12-14, 2005, Budmerice, Slovakia
	J.-K. Seong , G. Elber , J. K. Johnstone , M.-S. Kim, The convex hull of freeform surfaces, Computing, v.72 n.1-2, p.171-183, April 2004
	Chee K. Yap, Complete subdivision algorithms, I: intersection of Bezier curves, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Iddo Hanniel , Gershon Elber, Subdivision termination criteria in subdivision multivariate solvers using dual hyperplanes representations, Computer-Aided Design, v.39 n.5, p.369-378, May, 2007
	Michael Bartoň , Bert Jüttler, Computing roots of polynomials by quadratic clipping, Computer Aided Geometric Design, v.24 n.3, p.125-141, April, 2007
	Kwanhee Lee , Joon-Kyung Seong , Ku-Jin Kim , Sung Je Hong, Minimum distance between two sphere-swept surfaces, Computer-Aided Design, v.39 n.6, p.452-459, June, 2007
	David E. Johnson , Elaine Cohen, Computing surface offsets and bisectors using a sampled constraint solver, Proceedings of Graphics Interface 2009, May 25-27, 2009, Kelowna, British Columbia, Canada
	Ioannis Z. Emiris , George M. Tzoumas, A real-time and exact implementation of the predicates for the Voronoi diagram of parametric ellipses, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	Xianming Chen , Richard F. Riesenfeld , Elaine Cohen, Sliding windows algorithm for B-spline multiplication, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	Ioannis Z. Emiris , George M. Tzoumas, Exact and efficient evaluation of the InCircle predicate for parametric ellipses and smooth convex objects, Computer-Aided Design, v.40 n.6, p.691-700, June, 2008
	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
	Iddo Hanniel , Gershon Elber, Computing the Voronoi cells of planes, spheres and cylinders in R³, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	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
	Adarsh Krishnamurthy , Rahul Khardekar , Sara McMains , Kirk Haller , Gershon Elber, Performing efficient NURBS modeling operations on the GPU, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	Diana Pekerman , Gershon Elber , Myung-Soo Kim, Self-intersection detection and elimination in freeform curves and surfaces, Computer-Aided Design, v.40 n.2, p.150-159, February, 2008
	L. Alberti , B. Mourrain , J. Wintz, Topology and arrangement computation of semi-algebraic planar curves, Computer Aided Geometric Design, v.25 n.8, p.631-651, November, 2008
	L. Alberti , B. Mourrain , J. Wintz, Topology and arrangement computation of semi-algebraic planar curves, Computer Aided Geometric Design, v.25 n.8, p.631-651, November, 2008
	Xiao-Diao Chen , Jun-Hai Yong , Guozhao Wang , Jean-Claude Paul , Gang Xu, Computing the minimum distance between a point and a NURBS curve, Computer-Aided Design, v.40 n.10-11, p.1051-1054, October, 2008
	Iddo Hanniel , Gershon Elber, Computing the Voronoi cells of planes, spheres and cylinders in R3, Computer Aided Geometric Design, v.26 n.6, p.695-710, August, 2009
	Antoine Vacavant , David Coeurjolly , Laure Tougne, A framework for dynamic implicit curve approximation by an irregular discrete approach, Graphical Models, v.71 n.3, p.113-124, May, 2009
	B. Mourrain , J. P. Pavone, Subdivision methods for solving polynomial equations, Journal of Symbolic Computation, v.44 n.3, p.292-306, March, 2009
	Xiao-Diao Chen , Linqiang Chen , Yigang Wang , Gang Xu , Jun-Hai Yong , Jean-Claude Paul, Computing the minimum distance between two Bézier curves, Journal of Computational and Applied Mathematics, v.229 n.1, p.294-301, July, 2009
	Ligang Liu , Lei Zhang , Binbin Lin , Guojin Wang, Fast approach for computing roots of polynomials using cubic clipping, Computer Aided Geometric Design, v.26 n.5, p.547-559, June, 2009
	Angelos Mantzaflaris , Bernard Mourrain , Elias Tsigaridas, Continued fraction expansion of real roots of polynomial systems, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan