David Dobkin
John Hershberger
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.
- 1 J. Boyse and J. Gilchrist. GMSolid: interactive modeling for design and analysis of solids. IEEE Computer Graphics and Applications, 2:86-97, 1982.Google Scholar
Digital Library
- 2 C. Brown. PADL-2: a technical summary. IEEE Computer Graphics and Applications, 2:69-84, 1982.Google ScholarDigital Library
- 3 B. M. Chazelle. Computational Geometry and Convexity. Technical Report CMU-CS-80-150, Carnegie-Mellon University, Department of Computer Science, Pittsburgh, PA, 1980.Google Scholar
- 4 H. Edelsbrunner. Algorithms in Combinatorial Geometry. Volume 10 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1987. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 6 R. L. Graham and F. F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms, 4:324-331, 1983.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 10 D. T. Lee. On finding the convex hull of a simple polygon.Google Scholar
- 11 M. M. Mano. Digital Logic and Computer Design. Prentice- Hall, 1979. Google ScholarDigital Library
- 12 M. Mantyla. An Introduction to Solid Modeling. Computer Science Press, 1987. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 14 A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters, 25:11-12, 1987. Google ScholarDigital Library
- 15 M. Mortenson. Geometric Modeling. John Wiley & Sons, 1985. Google ScholarDigital Library
- 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.Google Scholar
- 17 J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. Google ScholarDigital Library
- 18 T. Pavlidis. Analysis of set patterns. Pattern Recognition, 1:165-178, 1968.Google ScholarCross Ref
- 19 D. Peterson. Hal fspace Representation of Extrusions, Solids of Revolution, and Pyramids. SANDIA Report SAND84- 0572, Sandia National Laboratories, 1984.Google Scholar
- 20 F. P. Preparata and M. I. Shamos. Computational Geometry. Springer Verlag, New York, 1985. Google ScholarDigital Library
- 21 A. Requicha. Representations for rigid solids: theory, methods, and systems. ACM Computing Surveys, 12:437-464, 1980. Google ScholarDigital Library
- 22 A. A. Sch~ffer and C. J. Van Wyk. Convex hulls of piecewisesmooth Jordan curves. Journal of Algorithms, 8:66-94, 1987. Google ScholarDigital Library
- 23 W. Tiller. Rational B-splines for curve and surface representation. IEEE Computer Graphics and Applications, 3, 1983.Google Scholar
- 24 S. B. Tor and A. E. Middleditch. Convex decomposition of simple polygons. ACM Transactions on Graphics, 3(4):244- 265, 1984. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
Index Terms
- An efficient algorithm for finding the CSG representation of a simple polygon
Recommendations
An efficient algorithm for finding the CSG representation of a simple polygon
SIGGRAPH '88: Proceedings of the 15th annual conference on Computer graphics and interactive techniquesWe 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 ...
An efficient algorithm for finding the CSG representation of a simple polygon
Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior ...
A counterexample to an algorithm for computing monotone hulls of simple polygons
A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon P^* which is monotonic in both the x and y directions and which contains the ...
Comments