Transcript CELLULAR AUTOMATA FOR 3D MORPHING

CELLULAR AUTOMATA FOR 3D
MORPHING
Sudhanshu K Semwal
Kaushal S Chandrashekar
Department of Computer Science
University of Colorado at Colorado Springs
Outline

Introduction to Morphing

Background

Design of volume morphing algorithms

Implementation

Results

Future work

Conclusions
Introduction to Morphing

Morphing
 Given a source model S and a target
model T, morphing constructs a series
of transformations {Wt | t є [0,1]} such
that W0 = S and W1 = T
Introduction to Morphing

Applications of morphing
 Movies
 3D games
 Study of evolution
 Understanding fetal and plant growth
Introduction to Morphing


Types of morphing
 2 dimensional
 3 dimensional
Benefits of 3 dimensional morphing
 Free from lighting and environmental
considerations
 Real-time camera view changes
Background

Types of 3D morphing



Polygonal mesh
Volumetric
Polygonal mesh morphing


Uses polygonal or polyhedral meshes as input
Mesh


Linear surface composed of polygons described as
Vertex/Face/Edge/Graph or vertices
Describes topology of surface
Background contd

Benefits



Very popular format, supported by many
modeling packages
Most approaches are of this form
Drawbacks



Datasets from medical and geological fields
do not support polygonal data
Complex topologies difficult to handle, esp.
with user control
Complex implementations reqd for
processing and rendering
Background contd.

Two parts of the morphing problem

Correspondence problem

Interpolation problem
Background contd

Volumetric morphing



Uses 3 dimensional volumes as source and
target
Volumes composed of voxels
Voxels – atomic unit of volume, short for
volume pixel
Background contd

Volume defined as a collection of scattered
voxels, with each voxel being associated with a
set of values of size S, i.e, the volume V is given
by:
V = {(xi, vi ) | xi Є R3 , vi Є RS, i = 1 .. n } [Chen1995]

Common representation is a 3 dimensional grid

Each (i,j,k) either empty or containing one value
Background contd

Benefits





Free of restrictions of topology and geometries
Can be easily be applied to meshes by
converting them to volumetric data, while the
reverse can result in topologies difficult to morph.
Data in the medical, geological and energy fields
is generated in the volumetric format and needs
to be morphed directly.
Do not need a bijective mapping between
vertices of the source and target formats.
The simple format allows implementation ease.
Background contd.

Drawbacks
 Not
as popular as polygonal formats in the
entertainment industry, fewer test models
available.
 Computationally intensive to process and
render.
Background contd.

[Cohen-Or1998] Uses distance field
transformation method
 Uses user-defined control points
 Morphing done using warping and
cross-dissolving
 Disadvantage – quality of morph
dependent on control points
Background contd.

Problems with current 3D morphing
techniques



Correspondence
Require user-defined control points
Exhibit
TO
Background contd.

Our goal



Less restrictive approach
Minimal or no user control
Natural looking process
Background contd

Cellular Automata


Dynamic system composed of discrete cells,
work in discrete steps of time and are
characterized by local interactions
Some of the characteristics of CA are
[Wolfram1984]:





They utilize a discrete lattice of sites
Discrete time steps drive the simulation.
Each site can only take a finite set of values
Each site evolves according to same
deterministic rules
The evolution of a site only depends on the
neighborhood.
Design contd

Characteristics of CA used





3 dimensional lattice.
The dimension of the lattice is that of the
volume.
Each cell can either be empty or contain one
value.
All cells are equal
The cellular automaton is non-circular.
Design contd

Core increment algorithm





Source and target volumes overlaid within
same CA
Uses intersection of 2 volumes as base
Intersection is called the core
Core incremented step-wise to fill both source
and target volumes
At each iteration, each voxel in the core
checks its surroundings, if source or target
voxel found, adds that voxel to the core.
Design contd







Voxels required to start from core and fill both
volumes recorded in add-array(target volume) and
del-array (source volume) as separate sets.
Process continues until core cannot increment any
more
Source model loaded into new volume
Add and del arrays scanned, former forward and
latter in reverse
At each iteration, voxels for that iteration in the delarray are removed from the source volume and
voxels for that iteration in the add-array are added
Source voxels not intersecting with target are
gradually removed and target voxels are gradually
added
Generates a smooth organic quality
Design contd
Design contd
Design contd
Design contd
Design contd
Design contd

Benefits





Rules defining behavior of cellular automata are
simple, hence easy to upgrade or replace.
Uses 3 dimensional arrays as volumes. Popular
formats can be used directly.
No correspondence required between source
and target models.
The morph can be controlled because of the add
and delete arrays containing the information of
each iteration as separate sets.
Organic quality of morph
Design contd

Disadvantages


Requires intersection of volumes
4 volumes are reqd to be created,




Source, Target, Core, Source for morphing iteration
Volumes containing source and target have to be
of same size, no restrictions on models
themselves
No attempt to preserve mass
Color handling not solved, no solution elsewhere
Design contd

Bacterial growth model



Based on papers using CA for bacterial
simulation
Bacteria modeled as individual agents in
lattice and rules govern its reaction to
environment and other bacteria
Each non-empty voxel in source volume is
considered as a bacterium
Design contd

Rules for bacteria

Non-motile.
Homogenous
Have 2 needs, food and the need to reproduce, the
latter being dependent on the former.
Will reproduce if it finds food and has space to place
its offspring by making a copy of itself.
Creates only one offspring per iteration.
Will live and reproduce infinitely given enough space.
Will die if food is not present in its current position.

Cooperate to keep each other alive.






Design contd

Bacterial Growth Model





Each voxel in target considered inexhaustible
source of food
Target volume overlaid in 3 dimensions over
source
Effectively, food is provided to bacteria in source
For each position (i,j,k) in source, if (i,j,k) in target
is non-empty, then (i,j,k) in source has food
Each bacterium in source checks to see if food
present in current position
Design contd




If food found, and space available,
reproduces with certain probability p1
If food not found in current position, and
not surrounded, dies with certain probability
p2
Bacteria in features that do not intersect
with target starve and die, thus removing
those features
Bacteria are encouraged to grow into
features of the target volume, thus
morphing into that shape
Design contd
Probability of bacteria dying = 0.5
Probability of bacteria reproducing = 1.0
Design contd
Design contd
Design contd

Benefits




Extremely simple algorithm, easy to
implement.
The source and target volumes need to be
loaded only once and morphing can proceed.
No costly pre-processing steps required.
Ideal as a quick and dirty method of
morphing, works well with models of similar
sizes
Design contd

Disadvantages





Requires that input volumes be of same dimensions.
No restriction on the sizes of the models themselves.
Computationally intensive because each voxel has to
be considered. Can be alleviated to a certain extent
by use of iso-surfaces of the source volume
Needs intersection of volumes to work.
No way to control the morphing process.
No support for handling color
Implementation


C++ used as implementation language
Visualization ToolKit used for rendering
Results

Test cases:
a)
•
•
•
Input.bin to Fuel.bin
64 X 64 X 64 volume size
17,000 non-empty voxels
Large extent of intersection
b) Cube256x256x256.bin to aneurism.bin:
• 256 x 256 x 256 sized datasets
• 1.1 million non-empty voxels
• Target dissipated through volume, branch like
• Small amount of overlap
Results contd
c) Cube256x256x256.bin to MRI-head.bin:
•
•
•
•
256 x 256 x 256 sized datasets.
7.1 million non-empty voxels
Source model overlaps and is smaller than
target
Large number of voxel additions
d) MRI-head.bin to bonsai.bin
•
•
•
•
256 x 256 x 256 sized datasets.
7.3 million non-empty voxels
Source model overlaps and is larger than target
Large number of voxel deletions
Bacterial growth model
Source
non-empty
Voxel
Count
Target
non-empty
Voxel
Count
No of
iterations
Avg
Morphing
Time per
iteration
(secs)
Total Time
taken for
morphing
(secs)
Avg
Rendering
Time
(secs)
4096
13731
32
0.02
0.64
0.76
256X256X256
1000000
168948
387
1.16
448.92
3.16
256X256X256
1000000
132
3.38
446.16
2.14
256X256X256
6176412
195
1.33
259.35
2.71
Volume
Dimensions:
a
64 X 64 X 64
b
c
d
6198649
1298598
Results contd

Observations

Complexity is n3 where n is the size of one
dimension of the source or target volume.

In normal cases, the amount of time taken
for each iteration as well as the number of
iterations depend on the size of the volume
and the number of non-empty voxels within
it.
Results contd




In case of test (b), the small amount of overlap
leads to a large amount of additions and
deletions.
The performance of this algorithm is better than
the core increment method due to iso-surfacing
This algorithm seems to do well in cases where
there is a large percentage of overlap between
volumes
The quality of the morphs is in general worse
than the core-increment algorithm
Core increment model
Volume
Dimensions:
Source
non-empty
Voxel
Count
Target
non-empty
Voxel
Count
No of
iterations
Avg.
Morphing
Time
Per Iteration
(secs)
Total Time
Taken for
Morphing
(secs)
Avg.
Rendering
Time
(secs)
a.
64 X 64 X 64
4096
13731
32
.0334
1.07
1.27
b.
256X256X256
1000000
168948
248
2.5027
620.67
4.46
c.
256X256X256
1000000
6198649
120
8.7642
1051.71
3.32
d.
256X256X256
6176412
1298598
175
11.24
1966.24
3.33
Results contd

Observations

The complexity of this algorithm is of the order of n3.

The time taken to morph increases linearly with the

dimension of the volume.
There is no performance hit even when the overlap
in test (b) is significantly lower than the others.

Tests suggest that the core increment algorithm is
more stable with a varied type of source and target
models than the bacterial growth models.
Results contd

Movies of Results
Future Work





Handling non-intersecting volumes
Multi-value volume support
Parallelization
Color handling
Scripting language support
Conclusion





Two algorithms for morphing volumetric
data developed
Do not require any correspondence
information
Do not require any user control.
Disparate models can be morphed
Applications



Entertainment
Medicine
Evolution, geology, education etc
Thank you
Any Questions?
Introduction to Morphing

Desirable features of 3D morphing are:



Intermediate transitions should undergo
continuous 3D transformations
Should apply to a variety of shapes and
topologies
Should be able to use user input, but work
well without it also
Background contd.

Current research



[Lee1999] simplify source and target
meshes to form coarse base domains
Since base domains are simple meshes,
easy to find correspondence
Allows user defined features
Background contd.

Current Research


[He1994] use Direct interpolation
For a function s(x,y,z) representing the
source volume in 3D space and a function
t(x,y,z) representing the target volume
Ig(x,y,z) = (1 – g) s(x,y,z) + g t(x,y,z) , 0 <= g <= 1
where Ig is a function that represents the
intermediate volumes.
 Problems with high frequency components
Background contd


Volumetric morphing used
Reason for using volumetric morphing



Fertile area of research, allowing more room for
innovation.
Simple
and
unrestricted
nature
allow
unconventional approaches to be implemented
with ease.
The cellular automata based algorithm fits the
volumetric approach in comparison to other 3D
techniques such as polygonal morphing
Background contd.

Applications






VLSI design [Sarkar2000]
Fault tolerant computing [Sarkar2000]
Ecological simulations[Bezzi2000]
Medical simulations [Sloot2002]
Crowd behavior and social interaction
models [Hamagami2003]
Physics modeling in games [Forsyth2002]
Background contd.

Current Research
 [Droun2003] simulate highly deformable
substances
 Concept of virtual clay
 3D CA used with integer in each cell
representing amount of clay
 Based on input, amount of clay is
redistributed as model is manipulated
Background contd.
[Claudia2001] use CA to simulate
landslides
 Use the Cellular Automata Network model
 Each component of system represented by
a CA and interactions between
components form network.
 Dependency graph generated to satisfy
dependencies of one component on
another

Implementation contd

Input File Format





Count of rows: unsigned char
Count of columns: unsigned char
Count of depth: unsigned char
Raw data in horizontal slice fashion, with
(0,0,0) at the top front part of the volume
and (row-max, col-max, depth-max) at the
bottom back part : unsigned char
Dimensions have to be lesser than 1024
Design

Basis of design





Search for simplicity – Occam's Razor
Analyzed problem at most basic level, ignoring
correspondence and interpolation problems
Looked at volumetric morphing as a collection of
voxels comprising the source model trying to
achieve similarity with the voxels in the target
model
Realized global control mechanisms not reqd.
Cellular automata was perfect answer
Implementation contd

Supporting Programs

raw2nativeformat


resizevolume


resizevolume inputfilename rows colums depth
outputfilename
createtestcube


raw2nativeformat rows columns depth inputfilename
outputfilename
createtestcube volumerows volumecols volumedepth
cubeStartx cubeStarty cubeStartz width height depth
valueToFill outputfilename
volviewer

volviewer filename
Implementation contd

VTK classes used in thesis
 VtkRenderer
 VtkRenderWindow
 VtkPiecewiseFunction
 VtkVolumeProperty
 VtkVolumeRayCastCompositeFunction
 VtkVolume
 VtkColorTransferFunction
 VtkVolumeRayCastMapper
 VtkStructuredPoints
 VtkRenderWindowInteractor
VTK Pipeline
Class Structure
Implementation contd

Classes implemented







CAVolume
CAVData
CAFileReader
CADisplayEngine
CABaseMorph
CACoreIncrementMorph
CABacterialGrowthMorph