Development of an algorithm for voxelization of CSG (constructive solid geometry) objects using a 2D CSG processor

ABSTRACTDEVELOPMENT OF AN ALGORITHM FOR VOXELIZATION OF CSG(CONSTRUCTIVE SOLID GEOMETRY) OBJECTS USING A 2D CSGPROCESSORKOÇ, SemaPh. D. In Electrical and Electronics Engineering6XSHUYLVRU$VVRF3URI'U6DYDú8d.81Co-Supervisor: Assist. Prof. DU8OXVd(9ø.May 2005, 106 PagesIn this thesis we present a new approach for the voxelization of volumetric scenegraph. The voxelization algorithm is based on the creation of volume slices using thedepth information of front and back surfaces belonging to scene primitives. Thealgorithm generates slices of the each primitive intended to be voxelized using 2DCSG processor.For the volume scene tree ?Blist (Boolean list)? representation is used. In Blistformulation, a Boolean expression is represented as a list of primitives instead of atree, and this may be evaluated in a pipeline fashion, combining at each step theresult of classifying the cells against the current primitive with the result of theprevious classification. The fundamental breakthrough provided here lies in the factthat the result of the previous classifications does not require the list of values of cell-primitive classification results, nor a stack of intermediate results of evaluating sub-expressions. Instead, Blist passes from one primitive to the next a simple label,which may be stored using at most log(H+1) bits, where H is the height of the CSGtree .Where this study differs from previous works is that it provides the following: thez-buffer based voxelization algorithm can voxelize different type of objects (convexand concave objects, polygons, lines and surfaces), also the algorithm is suitable foriiiaccurately voxelizing objects with hidden cavities. Using Blist representation, thevolume scene tree expression can be evaluated without using recursion or stack.Keywords: volume scene tree, Blist, voxelization, CSG (Constructive solidgeometry), z-buffer.iv