Method and apparatus for fast voxelization of volumetric models

An apparatus for voxelizing a 3D object in 3D space, the 3D object having a surface, the 3D object represented by a predetermined 3D model type, the apparatus comprising:

• a frame buffer memory, including a frame buffer having a 2D array of pixels;
• a memory having a 3D memory storage matrix coupled to the frame buffer of the frame buffer memory;
• a slice generating mechanism coupled to the 3D space and the frame buffer, the slice generating mechanism being operable to generate a series of slices of the 3D object in 3D space by (a) sequentially defining a viewing volume comprising at least a portion of the 3D space, and (b) rendering in the frame buffer the surface of any portion of the 3D object found within the viewing volume, wherein each slice comprises a 2D array of voxels, with each voxel associated with a pixel in the 2D array of pixels in the frame buffer;
• and
• a frame buffer blending mechanism, coupled to the frame buffer and the 3D memory storage matrix, the frame buffer blending mechanism capable of transferring a slice stored in the frame buffer to the 3D memory storage matrix while performing one or more predetermined frame buffer blending functions on each slice stored in the frame buffer, with the performance of any frame buffer blending functions a function of the predetermined 3D model type of the 3D object.

A method for voxelization of a generalized Constructive Solid Geometry (CSG) model of an object in 3D space, the 3D space including a plurality of coordinate points, the object composed of a plurality of primitives, the generalized CSG model including a generalized CSG tree having a lowest level consisting of a leaf node associated with each primitive of the object, each leaf node acting as a child node, at least one binary node associated with two child nodes at a level below the binary node, with each binary node including an associated Boolean operation that governs the interaction between its associated child nodes, each child node associated with only a single binary node above, a leaf node formed by the binary node at the highest level of the CSG tree and composed of two child nodes below, and each binary node other than the leaf node forming a child node for a binary node above, comprising the steps of:

• converting the generalized CSG model into a binary 3D model of the object, including the steps of:
• for each coordinate point in 3D space, creating a classification index for the point indicative of whether the point is interior to or exterior to each primitive;
• for each primitive, creating a point classification map that maps each classification index against the primitive and its associated child node of the CSG tree;
• for each child node, determining a point classification map for its associated binary node based on the child node's point classification map, the point classification map of the other child node associated with its binary node, and the Boolean operation associated with the binary node;
• for each binary node, determining a point classification map for its associated binary node above based on the binary node's point classification map, the point classification map of the other node associated with the binary node above, and the Boolean operation associated with the binary node above;
• and
• recursively determining the point classification maps for binary nodes until the point classification map is determined for the leaf node;
• and
• voxelizing the binary 3D model of the object.

A method for voxelization of a generalized CSG model of an object in 3D space using a computer system, the computer system including a frame buffer and texture memory, the 3D space including a plurality of coordinate points, the object composed of a plurality of primitives, the generalized CSG model including a generalized CSG tree having a lowest level consisting of a child node associated with each primitive of the object, at least one binary node associated with two child nodes at a level below, with each binary node including an associated Boolean operation that governs the interaction between its associated child nodes, each child node associated with only a single binary node above, a leaf node formed by the binary node at the highest level of the CSG tree and composed of two child nodes below, and each binary node other than the leaf node forming a child node for a binary node above, comprising the steps of:

• converting the generalized CSG model into a binary 3D model of the object, including the steps of:
• for each coordinate point in 3D space, creating a classification index in the frame buffer for the point indicative of whether the point is interior to or exterior to each primitive;
• for each primitive, creating a point classification map in the frame buffer that maps each classification index in the frame buffer against the primitive and its associated child node of the CSG tree;
• for each child node, determining a point classification map in the frame buffer for its associated binary node based on the child node's point classification map, the point classification map of the other child node associated with its binary node, and the Boolean operation associated with the binary node;
• for each binary node, determining a point classification map in the frame buffer for its associated binary node above based on the binary node's point classification map, the point classification map of the other node associated with the binary node above, and the Boolean operation associated with the binary node above;
• and
• recursively determining the point classification maps for binary nodes until the point classification map in the frame buffer is determined for the leaf node;
• and
• voxelizing the binary 3D model of the object;
• and
• moving the point classification map for the leaf node into the texture memory.