International Journal of Computational Geometry & Applications

In this paper we propose a universal data structure (UDS), termed as UDS, which will aid in the design of optimal boundary data structures. We later show, with the aid of some recently published data structures, that any data structure can be expressed as a special case of UDS. We demonstrate how the application of the optimality concepts of the UDS can lead us to the discovery of more efficient data structures than popular data structures. We also discuss two approaches for optimization. We show that a globally optimal data structure is better than a special purpose optimal data structure.

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 lo 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 GSG. 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.

In this paper we present the Brep-index, a multidimensional space partitioning data structure that provides quick spatial access to the vertices, edges and faces of a boundary representation (Brep), thus yielding a single unified representation for polyhedral solids. We give an algorithm for the construction of the Brep-index and prove its correctness. We show that its size is Ω(v+e+f), where v, e, and f are the number of vertices, edges, and faces of the Brep. The lower bound can be achieved for some Breps by compressing the structure using simple rewrite rules. We then demonstrate robust point and line/Brep classification methods given an implementation that uses finite-precision arithmetic.

The present paper addresses the problem of detecting closed compartments produced by a set of planar faces in the space. The topology of the set is general, and edges in the final piecewise planar surface can belong to one, two or more faces; boundary representations for non-manifold solids are an example. An octree structure (dubbed eightit compartment Octree) that defines a 3D graph through the volume defined by the set of faces is proposed, and it is shown that a seed propagation algorithm on the graph can be used to detect the existing closed compartments. The algorithm can either compute the total number of compartments or detect if the set of faces define a closed solid volume, the outside part being considered as a separate compartment.

Form features may be represented both as faces and as volumes. Feature volumes are necessary in automated process planning for relating a feature to the extent of material to be removed from a part, and for capturing the global characteristics of a part, such as tool accessibility. In this paper, a method will be presented for generating a feature volume from a set of feature faces, based on the technique of face extension. The implementation is currently limited to polyhedral parts. Examples will be given to illustrate the algorithm.

An algorithm is presented for constructing a topologically and geometrically valid Domain Delaunay Tetrahedrization (DDT) of an arbitrarily shaped solid model with quadric curved faces (including objects with holes and nonmanifold objects). The algorithm operates on the boundary representation (B-rep) of the solid, and makes extensive use of properties of the Delaunay triangulation. This algorithm also includes a mechanism for transferring neighborhood information from the solid model to the elements of the tetrahedral model. Neighborhood information is used for identifying tetrahedra to be included in the DDT, and — in combination with geometric criteria — for ensuring that the DDT approximates satisfactorily the curved faces of the solid.

In this paper, an algorithm to construct the approximate medial axis of an object is proposed. The algorithm is based on the Delaunay triangulation of points on the object boundaries. Because the medial axis constructed by this algorithm consists of a set of discrete points, we call it the discrete medial axis. Based on the classification of these discrete points, the structure of the medial axis surfaces of a three-dimensional object are discussed in detail. The correctness of the algorithm is substantiated by a brief theoretical analysis.

Twenty open problems from the Seventh ACM Symposium on Computational Geometry are presented.