International Journal of Computational Geometry & Applications

Solid modeling is computationally intensive. Thus far its use in industry has been limited mainly to simple parts and simple applications, and this is not likely to change much until 'massive' computing power can be made available at an affordable cost. The RayCasting Engine is one specialized source of 'massive' computing power for solid modeling, and it is but the simplest member of a potentially large family of 'classification computers'.

The RayCasting Engine (RCE) is a highly parallel, custom-VLSI computer that classifies grids of parallel lines against solids represented in CSG. The sets of parallel 'in' segments that the RCE produces are called ray representations (ray-reps); they can be thought of as sampled boundary representations. Ray-reps are obviously useful for graphics and mass-property calculation. Less obviously, they are surprisingly versatile if one exploits special properties – for example, boolean combination of solids by interval operations on ray-reps – and the fact that ray-reps are cheap to compute. Overall, the combination of a 'new' representation scheme (ray-reps) and a fast custom processor (the RCE) is changing our approach to solid modeling. We are now seeking 'brute force' solutions to problems, and are finding that some previously intractable problems – for example, spatial sweeping and offsetting – are effectively computable and easy to program. This paper summarizes the genesis and principles of the RCE, some important properties of ray representations, and some exemplary applications of the (ray-rep, RCE) combination.

A parallel algorithm for determining the mass properties of objects represented in the Constructive Solid Geometry (CSG) scheme that uses polygons as primitives is presented. The algorithm exploits the fact that integration of local information around the vertices of the evaluated polygon is sufficient for the determination of its mass properties, i.e., determination of the edges and the complete topology of the evaluated polygon is not necessary. This reduces interprocessor communication and makes it suitable for parallel processing. The algorithm uses data parallelism, spatial partitioning and parallel sorting for parallelization. Tuple-sets on which simple operations have to be performed are identified. The elements of tuple-sets are distributed among the processors for parallelization. The uniform grid spatial partitioning technique is used to generate sub-problems that can be done in parallel and to reduce the cardinality of some of the tuple-sets generated in the algorithm. Parallel sorting is used to sort the tuple-sets between the data-parallel phases of the algorithm.

This paper presents an implementation of an interactive solid modeling system that integrates 1) the definition of objects by graphical interaction and 2) the specification of objects by geometric constraints. In this system, interactive modeling operations for constructing assemblies automatically generate constraints to maintain the properties intended by their invocation, and constraints, in turn, determine the degrees of freedom for further interactive mouse-controlled modeling operations. A symbolic geometric constraint solver is employed for solving systems of simultaneous constraints. Group hierarchies are utilized for representing dependencies and for localizing systems of constraints.

This paper presents a new technique for computing space deformations that interpolate a set of user-defined constraints. Constraints are specified by indicating the images of selected points. The deformation is formulated as the product of a polynomial function f of ℝⁿ into a higher-dimensional space, ℝ^m, with a linear projection from ℝ^m back to ℝⁿ. The projection matrix is computed using a pseudo-inverse technique. For sufficient m, the degrees of freedom may be used to optimize potential functions controlled by attracting and repulsing points. A prototype implementation is presented, which demonstrates the application of this technique to the interactive design of free-form shapes (when n=3) and of deformation processes in space-time domain (when n=4).

This paper introduces methods of creating, modifying and visualizing free-form geometric models, by use of the B-spline hyperpatch. Modeling tools for the hyperpatch, including local control-point interactions, lofting operations and sweeping operations, are described. These operations, together with modeling tools generated for free-form surface design, form a powerful tool hierarchy for the design of complex solids. Techniques are also described by which these hyperpatches may be integrated into conventional visible-surface algorithms. With the defined methods, and the hyperpatch model, the complexity of free-form solid object construction was found to be significantly simplified.

A robust and efficient surface intersection algorithm that is implementable in floating point arithmetic, accepts surfaces algebraic or otherwise and which operates without human supervision is critical to boundary representation solid modeling. To the author's knowledge, no such algorithms has been developed. All tolerance-based subdivision algorithms will fail on surfaces with sufficiently small intersections. Algebraic techniques, while promising robustness, are presently too slow to be practical and do not accept non-algebraic surfaces. Algorithms based on loop detection hold promise. They do not require tolerances except those associated with machine associated with machine arithmetic, and can handle any surface for which there is a method to construct bounds on the surface and its Gauss map. Published loop detection algorithms are, however, still too slow and do not deal with singularities. We present a new loop detection criterion and discuss its use in a surface intersection algorithms. The algorithm, like other loop detection based intersection algorithms, subdivides the surfaces into pairs of sub-patches which do not intersect in any closed loops. This paper presents new strategies for subdividing surfaces in a way that causes the algorithms to run quickly even when the intersection curve(s) contain(s) singularities.

Evaluating the intersection of two rational parametric surfaces is a recurring operation in solid modeling. However, surface intersection is not an easy problem and continues to be an active topic of research. The main reason lies in the fact that any good surface intersection technique has to balance three conflicting goals of accuracy, robustness and efficiency. In this paper, we formulate the problems of curve and surface intersections using algebraic sets in a higher dimensional space. Using results from Elimination theory, we project the algebraic set to a lower dimensional space. The projected set can be expressed as a matrix determinant. The matrix itself, rather than its symbolic determinant, is used as the representation for the algebraic set in the lower dimensional space. This is a much more compact and efficient representation. Given such a representation, we perform matrix operations for evaluation and use results from linear algebra for geometric operations on the intersection curve. Most of the operations involve evaluating numeric determinants and computing the rank, kernel and eigenvalues of matrices. The accuracy of such operations can be improved by pivoting or other numerical techniques. We use this representation for inversion operation, computing the intersection of curves and surfaces and tracing the intersection curve of two surfaces in lower dimension.

The abstracts of the presentations given at the Third Canadian Conference on Computational Geometry (August 1991) are summarized.