##
The Extended Convex Differences Tree (ECDT)
Representation for n-Dimensional Polyhedra

We introduce the Extended Convex Differences Tree
(ECDT) representation for n-dimensional polyhedra. The ECDT is
simultaneously a representation and an efficiency scheme.
A set is represented by a tree. Every
node holds a convex bound to the set which it represents
(not necessarily the convex hull). The union
of the sets represented recursively by the children is the set
difference between the parent's convex bound and the set the parent
represents.
The fact that a node holds a bound to its set is useful for avoidance
of unnecessary computations. This bound is convex, permitting
efficient algorithms. The ECDT uses convex
differences and is therefore able to look at concave areas as being
convex.

The ECDT can be viewed as an extension to the Convex
Differences Tree scheme, without its drawbacks,
or as a restricted form of CSG.
We show how Boolean operations are performed directly on the ECDT and
how a CSG tree is converted to ECDT form. Various geometric operations on
the ECDT are detailed, including point membership classification,
slicing by a hyper-plane, and boundary evaluation.

* Intl. Journal of Computational Geometry and Applications, *
1(3):227-241, 1991.
Also: proceedings, * First ACM/Siggraph Symposium on Solid Modeling
Foundations and CAD/CAM Applications*, June 1991, Austin,
ACM Press, pp. 139-148.