Computer Structures for Curve-Solid Classification in Geometric Modeling

Geometric modeling is important in CAD/CAM, robotics, computer vision, and other fields. Curve solid classification (CSC) is a computational utility central to many applications of geometric modeling; it effects segmentation of a curve into subsets that are inside, on the boundary, and outside of a solid. CSC is the basis for ray casting (a technique for calculating shaded displays and mass properties of solids), boundary evaluation, collision detection, and so forth. CSC algorithms are dependent on the means used to represent solids. In this work we focus on solids represented in Constructive Solid Geometry (loosely, as ordered "additions" and "subtractions" of simple primitive solids), and seek special computer structures that will allow CSC to be done 10X - 1000X faster than in conventional computers. Two types of modules are needed: domain dependent curve primitive classifiers, and domain independent classification combiners. In this paper we describe the architecture of a machine that can classify curves against CSG solids in parallel at high speed. We concentrate, however, on the design of a ray casting machine. The ray casting machine described here is a parallel, pipelined bit serial machine that classifies a regular lattice of parallel lines. We describe the design of two-bit serial building blocks, the Classification Combine processor (CC) and the incremental, bit serial, pipelined primitive classifier. These building blocks were designed from the outset for custom VLSI implementation. We describe how to use these building blocks to construct a highly parallel synchronous machine for ray casting. The building blocks are arranged in chips as bit slice units. By adding more slices, larger and larger machines can be built.