Arno Eigenwillig
ABSTRACT
We present an extension of snap roundingfrom straight-line segments (see Guibas and Marimont, 1998)to Bézier curves of arbitrary degree, and thus the first method for geometric roundingof curvilinear arrangements.Our algorithm takes a set of intersecting Bézier curvesand directly computes a geometric rounding of their true arrangement, without the need of representing the true arrangement exactly.The algorithm's output is a deformation of the true arrangementthat has all Bézier control points at integer pointsand comes with the same geometric guarantees as instraight-line snap rounding: during rounding, objects do not movefurther than the radius of a pixel, and features of thearrangement may collapse but do not invert.
- M. de Berg, D. Halperin, and M. Overmars. An intersection-sensitive algorithm for snap rounding. Comput. Geom., 36(4):159--165, 2007. Google Scholar
Digital Library
- O. Devillers and P. Guigue. Inner and outer rounding of set operations on lattice polygonal regions. In Proc. 20th Annu. Sympos. Comput. Geom. (SCG'04), pages 429--437, 2004. Google ScholarDigital Library
- A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL, a computational geometry algorithms library. Software -- Practice and Experience, 30:1167--1202, 2000. Google ScholarDigital Library
- G. Farin. Curves and Surfaces for Computer-Aided Geometric Design. Academic Press, 4th edition, 1997.Google Scholar
- M. Goodrich, L.J. Guibas, J. Hershberger, and P. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proc. 13th Annu. Sympos. Comput. Geom. (SCG'97), pages 284--293, 1997. Google ScholarDigital Library
- D.H. Greene. Integer line segment intersection. Unpublished manuscript, cited after {8}.Google Scholar
- D.H. Greene and F.F. Yao. Finite-resolution computational geometry. In Proc. 27th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS'86), pages 143--152, 1986.Google ScholarDigital Library
- L.J. Guibas and D.H. Marimont. Rounding arrangements dynamically. Internat. J. of Comput. Geometry & Applications, 8:157--176, 1998.Google ScholarCross Ref
- D. Halperin and E. Leiserowitz. Controlled perturbation for arrangements of circles. Internat. J. of Comput. Geometry & Applications, 14(4-5):277--310, 2004.Google ScholarCross Ref
- D. Halperin and E. Packer. Iterated snap rounding. Comput. Geom., 23(2):209--225, 2002. Google ScholarDigital Library
- D. Halperin and C.R. Shelton. A perturbation scheme for spherical arrangements with application to molecular modeling. Comput. Geom., 10(4):273--287, 1998. Google ScholarDigital Library
- J. Hershberger. Improved output-sensitive snap rounding. In Proc. 22nd Annu. Sympos. Comput. Geom. (SCG'06), pages 357--366, 2006. Google ScholarDigital Library
- J.D. Hobby. Practical segment intersection with finite precision output. Comput. Geom., 13:199--214, 1999. Google ScholarDigital Library
- L. Kettner and S. Näher. Two computational geometry libraries: LEDA and CGAL. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 65, pages 1435--1463. CRC Press LLC, Boca Raton, FL, 2nd edition, 2004.Google Scholar
- K. Mehlhorn and S. Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, 1999. Google ScholarDigital Library
- K. Mehlhorn, R. Osbild, and M. Sagraloff. Reliable and efficient computational geometry via controlled perturbation. In Automata, Languages and Programming, 33rd Internat. Colloquium (ICALP'06), Part I, volume 4051 of LNCS, pages 299--310. Springer, 2006. Google ScholarDigital Library
- V. Milenkovic and E. Sacks. An approximate arrangement algorithm for semi-algebraic curves. In Proc. 22nd Annu. Sympos. Comput. Geom. (SCG'06), pages 237--246, 2006. Full version to appear in shape Internat. J. of Comput. Geometry & Applications. Google ScholarDigital Library
- V.J. Milenkovic. Shortest path geometric rounding. Algorithmica, 27:57--86, 2000.Google ScholarCross Ref
- V.J. Milenkovic and L.R. Nackman. Finding compact coordinate representations for polygons and polyhedra. IBM J. Res. Develop., 34(5):753--769, 1990. Google ScholarDigital Library
- E. Packer. Iterated snap rounding with bounded drift. In Proc. 22nd Annu. Sympos. Comput. Geom. (SCG'06), pages 367--376, 2006. Google ScholarDigital Library
- H. Prautzsch, W. Boehm, and M. Paluszny. Bézier and B-Spline Techniques. Springer, 2002. Google ScholarDigital Library
- L. Ramshaw. Blossoms are polar forms. Research Report 34, Digital, Systems Research Center, Palo Alto, CA, USA, January 1989. ftp://ftp.digital.com/pub/DEC/SRC/research--reports/SRC--034.pdf.Google ScholarDigital Library
- C.K. Yap. Robust geometric computation. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 41, pages 927--952. CRC Press, Boca Raton, FL, 2nd edition, 2004.Google Scholar
- C.K. Yap. Complete subdivision algorithms, I: Intersection of Bezier curves. In Proc. 22nd Annu. Sympos. Comput. Geom. (SCG'06), pages 217--226, 2006. Google ScholarDigital Library
Index Terms
- Snap rounding of Bézier curves
Recommendations
Isoptics of Bézier curves
Given a planar curve s(t), the locus of those points from which the curve can be seen under a fixed angle is called isoptic curve of s(t). Isoptics are well-known and widely studied, especially for some classical curves such as e.g. conics (Loria, 1911)...
Approximating conic sections by constrained Bézier curves of arbitrary degree
In this paper, an algorithm for approximating conic sections by constrained Bezier curves of arbitrary degree is proposed. First, using the eigenvalues of recurrence equations and the method of undetermined coefficients, some exact integral formulas for ...
Weighted Lupaş q -Bézier curves
This paper is concerned with a new generalization of rational Bernstein-Bézier curves involving q -integers as shape parameters. A one parameter family of rational Bernstein-Bézier curves, weighted Lupaş q -Bézier curves, is constructed based on a set ...
Comments