research-article

Exact arrangements on tori and Dupin cyclides

Authors:

Eric Berberich,

Michael KerberAuthors Info & Claims

SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling

Pages 59 - 66

https://doi.org/10.1145/1364901.1364912

Published: 02 June 2008 Publication History

Abstract

An algorithm and implementation is presented to compute the exact arrangement induced by arbitrary algebraic surfaces on a parametrized ring dupin cyclide. The family of dupin cyclides contains as a special case the torus. The intersection of an algebraic surface of degree n with a reference cyclide is represented as a real algebraic curve of bi-degree (2n, 2n) in the two-dimensional parameter space of the cyclide. We use eigenwillig and kerber: "exact and efficient 2D-Arrangements of arbitrary algebraic Curves", SODA 2008, to compute a planar arrangement of such curves and extend their approach to obtain more asymptotic information about curves approaching the boundary of the cyclide's parameter space. With that, we can base our implementation on the general software framework by berberich et. al.: "sweeping and maintaining two-dimensional arrangements on surfaces: A first Step", ESA 2007. Our contribution provides the demanded techniques to model the special geometry of surfaces intersecting a cyclide and the special topology of the reference surface of genus one. The contained implementation is complete and does not assume generic position. Our experiments show that the combinatorial overhead of the framework does not harm the efficiency of the method. Our experiments show that the overall performance is strongly coupled to the efficiency of the implementation for arrangements of algebraic plane curves.

References

[1]

Arge, L., Hoffmann, M., and Welzl, E., Eds. 2007. Algorithms - ESA 2007, 15th Annual European Symp., Eilat, Israel, October 8--10, 2007, Proceedings, vol. 4698 of LNCS, Springer.

[2]

Basu, S., Pollack, R., and Roy, M.-F. 2006. Algorithms in Real Algebraic Geometry, 2nd ed., vol. 10 of Algorithms and Computation in Mathematics. Springer.

Digital Library

[3]

Bentley, J. L., and Ottmann, T. A. 1979. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers C-28, 643--647.

Digital Library

[4]

Berberich, E., Hemmer, M., Kettner, L., Schömer, E., and Wolpert, N. 2005. An exact, complete and efficient implementation for computing planar maps of quadric intersection curves. In Proc. of the 21st Annual Symp. on Computational Geometry (SCG 2005), 99--106.

Digital Library

[5]

Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Kettner, L., Mehlhorn, K., Reichel, J., Schmitt, S., Schömer, E., and Wolpert, N. 2005. Exacus: Efficient and exact algorithms for curves and surfaces. In Proc. of the 13th Annual European Symp. on Algorithms (ESA 2005), Springer, vol. 3669 of LNCS, 155--166.

Digital Library

[6]

Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., and Wein, R., 2007. A general framework for processing a set of curves defined on a continuous 2D parametric surface. http://www.cs.tau.ac.il/cgal/Projects/arr_on_surf.php.

[7]

Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., and Wein, R. 2007. Sweeping and maintaining two-dimensional arrangements on surfaces: A first step. In Arge et al. {Arge et al. 2007}, 645--656.

Digital Library

[8]

Bez, H. E. 2007. Rational maximal parametrisations of dupin cyclides. In Mathematics of Surfaces XII, Springer, R. Martin, M. Sabin, and J. Winkler, Eds., vol. 4647 of LNCS, 78--92.

Digital Library

[9]

Boehm, W. 1990. On cyclides in geometric modeling. Computer Aided Geometric Design 7, 243--255.

Digital Library

[10]

Bühler, K. 1995. Rationale algebraische Kurven auf Dupinschen Zykliden. Master's thesis, Universität Karlsruhe. in german.

[11]

Cazals, F., and Loriot, S. 2007. Computing the exact arrangement of circles on a sphere, with applications in structural biology. Technical Report 6049, INRIA Sophia-Antipolis.

[12]

Chandru, V., Dutta, D., and Hoffmann, C. M. 1989. On the geometry of dupin cyclides. The Visual Computer 5, 277--290.

[13]

Dupin, C. 1822. Applications de Gèomètrie et de Meèhanique. Bachelier, Paris.

[14]

Dupont, L., Hemmer, M., Petitjean, S., and Schömer, E. 2007. Complete, exact and efficient implementation for computing the adjacency graph of an arrangement of quadrics. In Arge et al. {Arge et al. 2007}, 633--644.

Digital Library

[15]

Eigenwillig, A., and Kerber, M. 2008. Exact and efficient 2d-arrangements of arbitrary algebraic curves. In Proc. of the Nineteenth Annual ACM-SIAM Symp. on Discrete Algorithms (SODA08), 122--131.

Digital Library

[16]

Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., and Wolpert, N. 2005. A Descartes algorithm for polynomials with bit-stream coefficients. In 8th International Workshop on Computer Algebra in Scientific Computing (CASC 2005), vol. 3718 of LNCS, 138--149.

Digital Library

[17]

Eigenwillig, A., Kerber, M., and Wolpert, N. 2007. Fast and exact geometric analysis of real algebraic plane curves. In Proocedings of the 2007 International Symp. on Symbolic and Algebraic Computation (ISSAC 2007), C. W. Brown, Ed., 151--158.

Digital Library

[18]

Eigenwillig, A. 2008. Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs. PhD thesis, Universität des Saarlandes, Germany.

[19]

Fogel, E., Halperin, D., Kettner, L., Teillaud, M., Wein, R., and Wolpert, N. 2006. Arrangements. In Effective Computational Geometry for Curves and Surfaces, J.-D. Boissonnat and M. Teillaud, Eds. Spinger, ch. 1, 1--66.

[20]

Forsyth, A. 1912. Lectures on the Differential Geometry of Curves and Surfaces. Cambridge University Press.

[21]

Gallier, J., 2001. Internet supplement to 'geometric methods and applications for computer science and engineering', chapter 23: Rational surfaces. http://www.cis.upenn.edu/~jean/gbooks/geom2.html.

[22]

Halperin, D. 2004. Arrangements. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds., 2nd ed. Chapman & Hall/CRC, ch. 24, 529--562.

[23]

Johnstone, J. K. 1993. A new intersection algorithm for cyclides and swept surfaces using cycle decomposition. Computer Aided Geometric Design 10, 1--24.

Digital Library

[24]

Pratt, M. J. 1990. Cyclides in computer aided geometric design. Computer Aided Geometric Design 7, 221--242.

Digital Library

[25]

Pratt, M. J. 1995. Cyclides in computer aided geometric design ii. Computer Aided Geometric Design 12, 131--152.

Digital Library

[26]

Wein, R., Fogel, E., Zukerman, B., and Halperin, D. 2007. 2D arrangements. In CGAL-3.3 User and Reference Manual.

[27]

Yap, C. K. 2004. Robust geometric computation. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds., 2nd ed. CRC Press, ch. 41, 927--952.

Digital Library

Cited By

Luo HPatania AKim JVejdemo-Johansson M(2021)Generalized penalty for circular coordinate representationFoundations of Data Science10.3934/fods.2021024(0)Online publication date: 2021
https://doi.org/10.3934/fods.2021024
Berberich EHemmer MKerber MHurtado Fvan Kreveld M(2011)A generic algebraic kernel for non-linear geometric applicationsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998224(179-186)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998224
Setter OSharir MHalperin D(2010)Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in spaceTransactions on computational science IX10.5555/1986573.1986574(1-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986573.1986574
Show More Cited By

Index Terms

Exact arrangements on tori and Dupin cyclides
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Construction of 3D Triangles on Dupin Cyclides

This paper considers the conversion of the parametric Bézier surfaces, classically used in CAD-CAM, into patched of a class of non-spherical degree 4 algebraic surfaces called Dupin cyclides, and the definition of 3D triangle with circular edges on ...
Topological Classification and Determination of Non-Degenerate Intersections of Two Dupin Cyclides
Abstract
The surface–surface intersection is a fundamental task in CAD/CAM. We present the classification and a full enumeration of the topology of all non-degenerate intersections of two Dupin cyclides. Inversion geometry is first used to ...
Highlights
- For non-degenerate intersections of two Dupin cyclides we provide: 1. A classification and a full enumeration based on a simple algeberaic sequence;2. An ...
Exact, efficient, and complete arrangement computation for cubic curves

The Bentley-Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling

June 2008

423 pages

ISBN:9781605581064

DOI:10.1145/1364901

Conference Chairs:
Eric Haines
Autodesk
,
Morgan McGuire
Williams College

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPM08

Sponsor:

SIGGRAPH

SPM08: SPM '08 - ACM Solid and Physical Modeling Symposium

June 2 - 4, 2008

New York, Stony Brook

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo HPatania AKim JVejdemo-Johansson M(2021)Generalized penalty for circular coordinate representationFoundations of Data Science10.3934/fods.2021024(0)Online publication date: 2021
https://doi.org/10.3934/fods.2021024
Berberich EHemmer MKerber MHurtado Fvan Kreveld M(2011)A generic algebraic kernel for non-linear geometric applicationsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998224(179-186)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998224
Setter OSharir MHalperin D(2010)Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in spaceTransactions on computational science IX10.5555/1986573.1986574(1-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986573.1986574
Setter OSharir MHalperin D(2010)Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in spaceTransactions on computational science IX10.5555/1980587.1980588(1-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1980587.1980588
Berberich EFogel EHalperin DKerber MSetter O(2010)Arrangements on Parametric Surfaces II: Concretizations and ApplicationsMathematics in Computer Science10.1007/s11786-010-0043-44:1(67-91)Online publication date: 13-Oct-2010
https://doi.org/10.1007/s11786-010-0043-4
Berberich EFogel EHalperin DMehlhorn KWein R(2010)Arrangements on Parametric Surfaces I: General Framework and InfrastructureMathematics in Computer Science10.1007/s11786-010-0042-54:1(45-66)Online publication date: 16-Oct-2010
https://doi.org/10.1007/s11786-010-0042-5
Setter OSharir MHalperin D(2010)Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in SpaceTransactions on Computational Science IX10.1007/978-3-642-16007-3_1(1-27)Online publication date: 2010
https://doi.org/10.1007/978-3-642-16007-3_1
Emeliyanenko PBerberich ESagraloff M(2009)Visualizing Arcs of Implicit Algebraic Curves, Exactly and FastProceedings of the 5th International Symposium on Advances in Visual Computing: Part I10.1007/978-3-642-10331-5_57(608-619)Online publication date: 26-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-10331-5_57
Fogel ESetter OHalperin DTeillaud M(2008)Arrangements of geodesic arcs on the sphereProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377711(218-219)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377711

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents