The n-dimensional extended convex differences tree (ECDT) for representing polyhedra

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The n-dimensional extended convex differences tree (ECDT) for representing polyhedra

Full text

Pdf (750 KB)

Source

ACM Symposium on Solid and Physical Modeling archive
Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications table of contents

Austin, Texas, United States

Pages: 139 - 147

Year of Publication: 1991

ISBN:0-89791-427-9

Author

Ari Rappoport

Interactive Geometric Modeling, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY

Sponsor

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 11, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/112515.112538 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Batchelor80	Batchelor, B.G., Hierarchical shape description based upon convex hulls of concavities, J. of Cybernetics, 10:205-210, 1980.
	Cameron89	Stephen Cameron, Efficient intersection tests for objects defined constructively, International Journal of Robotics Research, v.8 n.1, p.3-25, February 1989 [doi>10.1177/027836498900800101]
	Chazelle87	B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
	Dobkin83	Dobkin, D., Kirkpatrick, D., Fast detection of polyhedral intersection, Theoretical Comp. Sci., 27:241-253, 1983.
	Edelsbrunner87	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	Hertel84	Hertel, S., M/~ntyla, M., Mehlhorn, K., Nievergelt, J., Space sweep solves intersection of convex polyhedra, Acta Informatica, 21:501-519, 1984.
	Hoffmann89	Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989 [doi>10.1109/2.16223]
	Kim90	Yong Se Kim, Convex decomposition and solid geometric modeling, Stanford University, Stanford, CA, 1990
	Kyprianou80	Kyprianou, L.K., Shape classification in CAD, Ph.D. Thesis, University of Cambridge, 1980.
	Mäntylä88	Mfintylfi, M., An Introduction to Solid Modeling, Computer Science Press, Maryland, 1988.
	Muller78	Muller, D.E., Preparata, F.P., Finding the intersection of two convex polyhedra, Theoretical Comp. Sci., 7:217-236, 1978.
	Preparata85	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Rappoport89a	Ari Rappoport, An efficient algorithm for line and polygon clipping, The Visual Computer: International Journal of Computer Graphics, v.7 n.1, p.19-28, Jan. 1991 [doi>10.1007/BF01994114]
	Rappoport89b	Rappoport, A., The convex differences tree representation for simple polygons, Technical Report 27-89, Computer Science Department, The Hebrew University of Jerusalem, 1989.
	Rappoport89c	A. Rappoport, Using convex differences in hierarchical representations of polygonal maps, Proceedings on Graphics interface '90, p.183-189, June 1990, Halifax, Nova Scotia
	Requicha80	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]
	Requicha85	Requicha, A.G., Voelcker, ll.B., Boolean operations in solid modeling: boundary evaluation and merging algorithms, Proc. of the IEEE, 73(1):30-44, 1985.
	Rossignac90	Jarek R. Rossignac , Aristides A. G. Requicha, Constructive non-regularized geometry, Computer-Aided Design, v.23 n.1, p.21-32, Jan./Feb. 1991 [doi>10.1016/0010-4485(91)90078-B]
	Rossignac89	Jaroslaw R. Rossignac , Herbert B. Voelcker, Active zones in CSG for accelerating boundary evaluation, redundancy elimination, interference detection, and shading algorithms, ACM Transactions on Graphics (TOG), v.8 n.1, p.51-87, Jan. 1989 [doi>10.1145/49155.51123]
	Sklansky72	Sklansky, J., Measuring concavity on a rectangular mosaic, IEEE Tran. Com., c-21:1355-1364, 1972.
	Tilove84	Robert B. Tilove, A null-object detection algorithm for constructive solid geometry, Communications of the ACM, v.27 n.7, p.684-694, July 1984 [doi>10.1145/358105.358195]
	Tor84	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]
	Turner88	Joshua U. Turner, Accurate Solid Modeling Using Polyhedral Approximations, IEEE Computer Graphics and Applications, v.8 n.3, p.14-28, May 1988 [doi>10.1109/38.510]
	Weiler77	Kevin Weiler , Peter Atherton, Hidden surface removal using polygon area sorting, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.214-222, July 20-22, 1977, San Jose, California
	Woo82	Woo, T., Feature extraction by volume decomposition, Technical Report 82-4, Dept. of Indus. and Oper. Eng., The University of Michigan, 1982.
	Woodwark82	Woodwark, J.R., Wallis, A.F., Graphical input to a Boolean solid modeller, proc. CAD-82, Brighton UK, pp. 681-688, 1982.
	Woodwark88	John R. Woodwark, Eliminating Redundant Primitives from Set-Theoretic Solid Models by a Consideration of Constituents, IEEE Computer Graphics and Applications, v.8 n.3, p.38-47, May 1988 [doi>10.1109/38.512]

CITED BY 3

	A. Aguilera , D. Ayala, Orthogonal polyhedra as geometric bounds in constructive solid geometry, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.56-67, May 14-16, 1997, Atlanta, Georgia, United States
	Douglas L. Waco , Yong Se Kim, Geometric reasoning for machining features using convex decomposition, Proceedings on the second ACM symposium on Solid modeling and applications, p.323-332, May 19-21, 1993, Montreal, Quebec, Canada
	Ari Rappoport , Steven Spitz, Interactive Boolean operations for conceptual design of 3-D solids, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.269-278, August 1997

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:
E. Data
E.1 DATA STRUCTURES
Subjects: Trees

General Terms:
Algorithms

Collaborative Colleagues:

Ari Rappoport: colleagues

Peer to Peer - Readers of this Article have also read:

Inferring constraints from multiple snapshots ACM Transactions on Graphics (TOG) 12, 4
David Kurlander , Steven Feiner
Efficient techniques for interactive texture placement Proceedings of the 21st annual conference on Computer graphics and interactive techniques
Peter Litwinowicz , Gavin Miller
LR Parsing ACM Computing Surveys (CSUR) 6, 2
A. V. Aho , S. C. Johnson
Computer-generated pen-and-ink illustration Proceedings of the 21st annual conference on Computer graphics and interactive techniques
Georges Winkenbach , David H. Salesin

Adobe Acrobat

QuickTime

Windows Media Player

Real Player