VOLUMETRIC CSG GRAPH AND ITS VOXELIZATION - Sema Koç1.pdf

小小亮

690

4页

1次

2022-07-04

免费下载

VOLUMETRIC CSG GRAPH AND ITS VOXELIZATION

Sema Koç

, Ulus Çevik

e-mail: skoc@gantep.edu.tr

Department of Electrical and Electronic Engineering, University of Gaziantep, 27310 Gaziantep, Turkey

Keywords: volume scene tree, blist, voxelization, slice-sweep

ABSTRACT

This paper introduces a new representation for the

volumetric CSG scene graph. The Boolean list

representation is used for the volume scene tree, which is

differing from the traditional tree representation in the way

that any volume tree expression can be evaluated without

using recursion or stack. The scene evaluation is carried out

by a slice-sweep voxelization algorithm.

I. INTRODUCTION

A volume scene can be constructed from various type of

geometric or volumetric object such as curve, surface, solids

and CT data set. A popular technique in scene composition

is scene graph. It organizes geometric object and rendering

parameters in tree-like hierarchical structure [1].

Evaluation of scene graph is carried out by voxelization

algorithm. In recent years, a number of curve and surface

voxelization algorithms have been proposed [2-6]. Solid

voxelization on the other hand has not been sufficiently

studied. Solid objects are normally represented by their

boundary surfaces. Since the interior of solid object is not

explicitly represented, solid voxelization is difficult and

requires inside test for each voxel involved [7].

In [8], the evaluation of volume scene graph is done in a

brute-force manner, i.e. for each point in volume space,

recursively computing the value of scene graph starting

from the root. This is very expensive procedure, and can

only be used as preprocessing step, which is not practical

for interactive applications [1].

In [7], a hardware voxelization algorithm was described.

Although that algorithm is fast for small scale interactive

applications, its performance have been limited by the need

of generating intermediate object for each Boolean

operation node and hardware restriction in blending

function combination. This voxelization algorithm was

improved by using point classification map for Boolean

operations based on a frame buffer color encoding scheme

[9]. But this algorithm only provides a binary volume,

which may not provide the complete information in

volumetric space.

In [1], another volume pipeline is used which each slice is

applied to the entire CSG tree, rather than performing

volume level voxelization for each CSG node named “slice

sweeping”. Here, the basic idea is to generate a slice for

each object in the scene first, and than apply the blending

and filtering functions on the slice in postfix order of the

volume scene tree. This algorithm needs a slice data

structure to store intermediate result. 2D texture was used to

represent slices in the slice stack. From the view of time

spent, since the slice stack operation by 2D texture mapping

will occupy a large proportion in practice, more slice stack

operation leads to slower volume voxelization process.

Thus, in order to reach higher speed interior operation nodes

must be reduced as much as possible during the design of

volume scene tree.

We propose in this paper a new representation of volume

scene tree, which is named blist [10]. In Blist formulation,

Boolean expression is represented as a list of primitive

instead of tree, and may be evaluated in pipeline fashion,

combining at each step the result of classifying the cells

against the current primitive with the result of the previous

classification. The fundamental breakthrough provided here

lies in the fact that the result of the previous classifications

does not require the list of values of cell-primitive

classification results, nor a stack of intermediate result 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

CSG tree [10].

Using Blist representation volume scene tree expression can

be evaluated without using recursion or stack.

The scene evaluation is carried out by a slice-sweep

voxeliza tion algorithm.

’

OUT

II. BLIST REPRESENTATIO N OF VOLUME SCENE

TREE

In Blist formulation of volume scene tree each primitive

represent input dataset or geometric model. The basic idea

of our algorithm is generate a slice for each primitive in the

list first, then evaluate blist by updating a label, when its

value matches the primitive’s name. At the end if the label

on the voxel is 1(IN name) the voxel inside the volume

scene otherwise, it is out. So, Boolean expression of volume

scene tree is evaluated directly, combining steps used with

traditional recursive evaluation is not necessary. The details

of Blist formulation is as follows:

The Blist method transforms the CSG tree into decision

graph. A primitive classifies a candidate voxel and

depending on the result, forwards the voxel to one or

another primitive. To convert volume CSG tree to blist

representation firstly, convert tree into a positive form by

applying de Morgan’s law (i.e A-B

(A B’, (A’)’ A) and propagating complements

to the leaves, than rotate the tree by switching the left and

right children at each node make the tree left heavy and than

insert the resulting tree, T, as the left-most leaf of a two

level tree: (T U OUT)

right for each leaf, p, fill in the corresponding fields of

BL[p]. Figure 1(a) shows volume scene tree and Figure 1

tree.

In Figure 1 (b) the leaves of tree are visited in the left-to-

right ord er. Then number the leaves with increasing positive

integers. For each leaf, numbered p, we compute its match,

M. Note that each arrow first traces a path upwards, first

reaching a node N1 coming from its left child, then reaching

a node N2 with a different operator still coming from the

left child. If N2 operator= U, the sign of p, Blist[p].sign is

inverted. Then, the arrows follow the pointer to

N2.rightChild and take the left-most child at each internal

node, until they reach the matching leaf M. Then, if M does

not yet a have name, it grab the lowest available strictly

positive integer and use it as its name. We also store that

name as the stamp, Blist[p], of p. on the Figure 1 (c), we

show resulting names for the leaves (inside the circle) and

their stamp, Blist[p].stamp, of p. Note that four leaves do

not have a name and that only one name is needed for the

entire tree.

Blist represent a CSG expression as a table called BL, of

primitive entries. Here BL[p].primitive Reference is the

reference to the primitive’s description, which includes its

type, parameters, color, BL[p].sign is the binary sign value,

when set, that the result of classifying a cell against the

primitive should b e complemented. BL[p].name is the name

associated with the primitive and BL[p].stamp contains the

name of the next primitive in the list that should classify the

voxel that are inside the current primitive if its sign is

positive, or the voxels that are outside of the current

primitive, if its sign is negative.

cube1

cube2

cylin d er1

cylin d er2

(a)

1 1

(c)

(b)

The Blist table resulting from conversion of volume scene

tree in Figure 1 is as follows:

Figure 1 (a) Volume scene tree

(b) blist conversio n process of volume

scene tree