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

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: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 5: W. R. Franklin, Polygon properties calculated from the vertex neighborhoods, Proceedings of the third annual symposium on Computational geometry, p.110-118, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41969]
• 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: Kurt Hoffmann , Kurt Mehlhorn , Pierre Rosenstiehl , Robert E. Tarjan, Sorting Jordan sequences in linear time, Proceedings of the first annual symposium on Computational geometry, p.196-203, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323259]
• 10: D. T. Lee. On finding the convex hull of a simple polygon.
• 11: M. Morris Mano, Digital Logic and Computer Design, Prentice Hall PTR, Upper Saddle River, NJ, 1979
• 12: Martti Mäntylä, An introduction to solid modeling, Computer Science Press, Inc., New York, NY, 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: Avraham A. Melkman, On-line construction of the convex hull of a simple polyline, Information Processing Letters, v.25 n.1, p.11-12, 20 April 1987 [doi>10.1016/0020-0190(87)90086-X]
• 15: Michael E. Mortenson, Geometric modeling, John Wiley & Sons, Inc., New York, NY, 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: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 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: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 21: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 22: Alejandro A. Schäffer , Christopher J. Van Wyk, Convex hulls of piecewise-smooth Jordan curves, Journal of Algorithms, v.8 n.1, p.66-94, March 1987 [doi>10.1016/0196-6774(87)90028-9]
• 23: W. Tiller. Rational B-splines for curve and surface representation. IEEE Computer Graphics and Applications, 3, 1983.
• 24: S. B. Tor , A. E. Middleditch, Convex Decomposition of Simple Polygons, ACM Transactions on Graphics (TOG), v.3 n.4, p.244-265, Oct. 1984 [doi>10.1145/357346.357348]
• 25: H. Voelcker , A. Requicha , E. Hartquist , W. Fisher , J. Metzger , R. Tilove , N. Birrell , W. Hunt , G. Armstrong , T. Check , R. Moote , J. McSweeney, The PADL-1.0/2 system for defining and displaying solid objects, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.257-263, August 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.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Design, Performance, Theory

Keywords:
boundary-to-CSG conversion algorithms, constructive solid geometry, simple polygons, solid modeling