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

Abstract

ÖZ%2<87/8&6*<$3,6$/.$7,*(20(75ø øù/(0&ø6ø.8//$1$5$.&6*1(61(/(5ø1ø192.6(/ø=$6<218ødø1%ø5$/*25ø70$1,1*(/øù7ø5ø/0(6øKOÇ, SemaPh. D. In Electrical and Electronics Engineering7H]<QHWLFLVL'Ro'U6DYDú8d.81<DUGÃPFÃ7H]<QHWLFLVL<DU'Ro'U8OXVd(9ø.May 2005, 106 sayfa%XWH]GHKDFLPVHOVDKQHQLQYRNVHOL]DV/RQXLoLQ/HQLELU/DNODúÃPQHULOPHNWHGLU%X YRNVHOL]DV/RQ DOJRULWPDVà Q YH DUND /Â]H/OHULQ GHULQOLN ELOJLOHULQL NXOODQDUDNKDFLPVHONHVLWOHULQROXúWXUXOPDVÃLONHVLQHGD/DQPDNWDGÃU$OJRULWPDYRNVHOL]DV/RQX/DSÃODFDN RODQ KHU ELU QHVQHQLQ NHVLWOHULQL ER/XWOX &6* LúOHPFLVL NXOODQDUDNROXúWXUPDNWDGÃU+DFLPVHO VDKQH D÷DFà LoLQ %OLVW %RROHDQ OLVW JVWHULPL NXOODQÃOPDNWDGÃU %OLVWIRUPÂODV/RQXQGD %RROHDQ DoÃOÃPà D÷Do /HULQH VDKQH WHPHO ÷HOHULQLQ OLVWHVL RODUDNJVWHULOPHNWHGLU NL EX GD KHU ELU YRNVHOLQ VDKQH ÷HOHULQH NDUúà VÃQÃIODQGÃUPDVÃQÃQVRQXFX LOH ELU QFHNL VÃQÃIODQGÃUPDQÃQ VRQXFXQXQ ELUOHúWLULOPHVL LOH DUGÃúÃO RODUDNhesaplanabilir. Burada önemli olan nokta bir önceNL VÃQÃIODQGÃUPD QH KÂFUH-÷HVÃQÃIODQGÃUPDVà VRQXo OLVWHVLQH QHGHDOWDoÃOÃPODUÃQKHVDSODQPDVÃLoLQELUDUD/Ã÷ÃQDLKWL/Do GX/PDNWDGÃU %XQXQ /HULQH %OLVW PHWRGX ELU ÷HGHQ GL÷HULQH VDGHFH ELUHWLNHW NXOODQDUDN JHoHELOPHNWHGLU YH EX HWLNHW GH÷HULQL VDklamak için sadeceORJ+ELW/HWHUOLROPDNWDGÃU%XUDGD+&6*D÷DFÃQÃQ/ÂNVHNOL÷LGLU%XoDOÃúPDúX/QOHULLOHQFHNLoDOÃúPDODUGDQD/UÃOPDNWDGÃUZ-DUDEHOOH÷L WHPHOOL YRNVHOL]DV/RQ DOJRULWPDVà IDUNOà FLVLPOHULQ Lo-EÂNH/ GÃú-bükey cisimler, poligonlDUoL]JLYH/Â]H/OHUYRNVHOL]DV/RQXLoLQNXOODQÃODELOLQLUYHVD/UÃFD DOJRULWPD VDNOà NRYXNOX FLVLPOHULQ GR÷UX ELU úHNLOGH YRNVHOL]DV/RQX LoLQX/JXQGXU %OLVW JVWHULPL NXOODQDUDN KDFLPVHO VDKQH JUDIL÷L /Ã÷ÃQ YH/D ]/LQHOHPHkullanmadan hesaplanabilinir.Keywords:+DFLPVHOVDKQHD÷DFÃ%OLVWYRNVHOL]DV/RQ&6*/DSÃVDONDWÃJHRPHWULZ-DUDEHOOH÷LVI

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