Real-time Voxelization for Complex Models

Zhao Dong, Wei Chen, Hujun Bao, Hongxin Zhang, Qunsheng Peng

​

​

​

State Key Lab of CAD&CG

Zhejiang University, P.R.China

State Key Lab of CAD&CG, Zhejiang University

Outline

• Introduction
• New voxelization algorithm
• Hardware implementation
• Results and applications
• Future work

​

Introduction

• Surface Graphics: Geometric rendering of Continuous Spatial Models (CSM)

​

• Volume Graphics: Volumetric Model (VM)

​

​

Voxelization

CSM

VM

Introduction

• Voxelization: A process of approximating a continuous geometric primitive in the 3D discrete space.
• The result of this process:
• Binary voxelization ( )
• Non-binary voxelization (densities, color, etc.)

​

Introduction

• Voxelization Algorithm
• Quality-oriented algorithm
• Aliasing Filtering Design [Wang 93, Wang 94]
• Performance-oriented algorithm
• Depth Buffer Based Voxelization [Aggeliki 99]
• Slice-based Voxelization [Fang 99, Fang 00]

​

​

Introduction

• The size and complexity of the models are becoming even larger

69,451 triangles

1,132,830 triangles

28,055,742 triangles

Performance has become the main challenge, we focus on it!

Introduction

Convexity

requirement

Introduction

• Slice-based Voxelization [Fang 99, Fang 00]

​

​

​

Original Model

Render Model

Set Clipping Plane

Get ith Slice

Write to ith 3D texture

Z-plane(i+1)

Z-plane(i)

If i < N

(N=Z-resolution)

else

Final Volume dataset

Introduction

• Slice-based Voxelization algorithm
• One slice each time, render model N times
• Scene complexity↑, volume resolution↑, performance ↓
• High video memory cost
• For binary voxeliztion, One voxel 🡪 One byte
• Special hardware requirement
• Write slice to 3D texture memory

Introduction

• Our Challenge
• More slices each time, render model at times as less as possible
• Lower video memory cost
• For binary voxelization, one voxel 🡪 one bit
• GPU on PC platform to support real-time voxelization

New Voxelization Algorithm

GPU work

CPU work

Original Model

Z-oriented

Y-oriented

X-oriented

Sorting geometry by surface normal

Slab

voxelization

Texture

encoding

Final Volume Dataset

Slab

voxelization

Texture

encoding

Slab

voxelization

Texture

encoding

Illustration of new voxelization algorithm stages

Composite three intermediate textures

New Voxelization Algorithm

• A problem of rasterization by graphics hardware

Projection plane

Volume information will be lost

So we need sort geometry according to

surface orientation

New Voxelization Algorithm

• Slab voxelization
• An example of binary voxelization at volume resolution 512³
• One bit(0 or 1) to represent One voxel
• Use 512x512 32bits 2D texture to

record a slab

• If one bit 🡨🡪 one voxel then

512x512x512 = 512x512x32x16

GPU support 4 Render targets simultaneously☺

So we need render models only 4 times

​

New Voxelization Algorithm

• Texture encoding
• After slab voxelization, we get 16 slabs(512x512 2D textures).
• Encode them into a single 2048x2048 2D textures

Slab3

Slab2

Slab1

Slab0

2048x2048 intermediate texture

‘0’ represents Z-nearest

‘15’ represents Z-furthest

Slab4

Slab5

Slab6

Slab7

Slab11

Slab10

Slab9

Slab8

Slab15

Slab14

Slab13

Slab12

New Voxelization Algorithm

• Teapot Example

Slab voxelization

Texture encoding

New Voxelization Algorithm

• Composite three parts into one

​

x

y

z

z

x

y

(All are left-hand coordinates)

(x1,y1,z1)

(x3,y3,z3)

x1 = z3

y1 = x3

z1 = y3

y

z

x

3D coordinates

for Y-oriented patches

​

(x2,y2,z2)

y2 = x1

z2 = y1

x2 = z1

We integrate the voxelization results of Y-oriented and X-oriented

patches into that of Z-oriented patches

3D coordinates

for Z-oriented patches

​

3D coordinates

for X-oriented patches

​

New Voxelization Algorithm

• Composition of three intermediate textures

​

Y-oriented patches

X-oriented patches

Coordinates

Transform

Patches1 in

z-oriented space

Patches2 in

z-oriented space

Original z-oriented

patches

Patches0 in

z-oriented space

Hardware Implementation

• Related Techniques
• Maximum Texture Size
• Dynamic vertex and index buffers
• Multiple render targets
• Dependent texture fetching
• Lookup Textures
• Fetching one bit
• Storing one bit
• Intermediate textures composition

​

​

Efficient bit operation in pixel shader

Hardware Implementation

• Use of the Resultant Volume
• Deferred video memory
• Read back to main memory
• But AGP is an asymmetric bus, read back from video memory will reduce the efficiency
• PCI-express may offer potential solution

​

Applications of Algorithm

• Voxelization of Surface of Other Forms
• Implicit Surface
• Parametric Surface
• CSG Models

​

Implicit Surface:

volume resolution is 128³

Applications of Algorithm

• Transparent Illustration

​

Interactive hybrid volume rendering

Applications of Algorithm

• Collision Detection

​

Applications of Algorithm

• Solid Voxelization
• 3D scan-filling similar to 2D scanning

​

​

​

Surface Voxelization

Solid Voxelization

Results

• Performance

Dragon

871,326 Triangles

439,370 Vertices

Resolution 256³

Voxelization 57ms

Buddha

1,087,514 Triangles

550,868 Vertices

Resolution 256³

Voxelization 64.8ms

Blade

1,765,388 Triangles

898,796 Vertices

Resolution 256³

Voxelization 95ms

Results

Table 1. Voxelization timings for different model sizes.

Volume resolution: 256³, bit-depth: 8.

Results

Results

• Comparisons
• Two algorithms were implemented on the same hardware platform
• CPU: Intel P4 2.4GHz
• Memory: 512M
• GPU: ATI Radeon 9800Pro with 256M video memory

​

​

Table 3. Comparisons between Slice-based method

and our method

Results

Bunny

Wagner

Dragon

Buddha

Future work

• Improvement of the voxelization quality
• Video cards that support the blending operation for floating point textures.
• Now Nvidia Geforce 6800 has supported the blending operation for16bit floating point textures
• Shade Mode 3.0 has been supported. We can use dynamic judgement in shader program, so sorting geometry can also be finished in GPU
• Integration of the voxelization engine 🡪 mature software product for market

​

​

Questions and Answers

• Thanks a lot for your attention ☺