“An efficient algorithm for finding the CSG representation of a simple polygon” by Dobkin, Guibas, Hershberger and Snoeyink

  • ©David P. Dobkin, Leonidas (Leo) J. Guibas, John Hershberger, and Jack Snoeyink

Conference:


Type:


Title:

    An efficient algorithm for finding the CSG representation of a simple polygon

Presenter(s)/Author(s):


Abstract:


    We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formulæ do not always exist for general polyhedra in three dimensions.

References:


    1. J. Boyse and J. Gilchrist. GMSolid: interactive modeling for design and analysis of solids. IEEE Computer Graphics and Applications, 2:86-97, 1982.
    2. C. Brown. PADL-2: a technical summary. IEEE Computer Graphics and Applications, 2:69-84, 1982.
    3. B. M. Chazelle. Computational Geometry and Convexity. Technical Report CMU-CS-80-150, Carnegie-Mellon University, Department of Computer Science, Pittsburgh, PA, 1980.
    4. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Volume 10 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1987.
    5. W. Franklin. Polygon properties calculated from the vertex neighborhoods. In Proceedings of the 3rd ACM Symposium on Computational Geometry, pages 110-118, ACM, June 1987.
    6. R. L. Graham and F. F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms, 4:324-331, 1983.
    7. L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.
    8. L. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry. In Proceedings of the 24 th Annual IEEE Symposium on Foundations of Computer Science, pages 100-111, IEEE, 1983.
    9. K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan. Sorting Jordan sequences in linear time. In Proceedings of the ACM Symposium on Computational Geometry, pages 196-203, ACM, 1985.
    10. D. T. Lee. On finding the convex hull of a simple polygon.
    11. M. M. Mano. Digital Logic and Computer Design. Prentice- Hall, 1979.
    12. M. Mantyla. An Introduction to Solid Modeling. Computer Science Press, 1987.
    13. D. McCallum and D. Avis. A linear algorithm for finding the convex hull of a simple polygon. Information Processing Letters, 9:201-206, 1979.
    14. A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters, 25:11-12, 1987.
    15. M. Mortenson. Geometric Modeling. John Wiley & Sons, 1985.
    16. R. Newell. Solid modelling and parametric design in the Medusa system. In Computer Graphics ’82, Proceedings of the Online Conference, pages 223-235, 1982.
    17. J. O’Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
    18. T. Pavlidis. Analysis of set patterns. Pattern Recognition, 1:165-178, 1968.
    19. D. Peterson. Hal fspace Representation of Extrusions, Solids of Revolution, and Pyramids. SANDIA Report SAND84- 0572, Sandia National Laboratories, 1984.
    20. F. P. Preparata and M. I. Shamos. Computational Geometry. Springer Verlag, New York, 1985.
    21. A. Requicha. Representations for rigid solids: theory, methods, and systems. ACM Computing Surveys, 12:437-464, 1980.
    22. A. A. Sch~ffer and C. J. Van Wyk. Convex hulls of piecewisesmooth Jordan curves. Journal of Algorithms, 8:66-94, 1987.
    23. W. Tiller. Rational B-splines for curve and surface representation. IEEE Computer Graphics and Applications, 3, 1983.
    24. S. B. Tor and A. E. Middleditch. Convex decomposition of simple polygons. ACM Transactions on Graphics, 3(4):244- 265, 1984.
    25. H. Voelcker, A. Requicha, E. Hartquist, W. Fisher, J. Metzger, R. Tilove, N. Birrell, W. Hunt, G. Armstrong, T. Check, R. Moote, and J. McSweeney. The PADL-1.0/2 system for defining and displaying solid objects. ACM Comput. Gr., 12(3):257-263, 1978.
    26. J. R. Woodwark and A. F. Wallis. Graphical input to a Boolean solid modeller. In CAD 82, pages 681-688, Brighton, U.K., 1982.

ACM Digital Library Publication:


Overview Page: