Notes for GI `96 Talk
These are my notes to accompany the slides I used at GI `96.
- Title Slide
- The Problem
- speeding up rendering useful for visualizing large databases more
quickly, eventually for speeding up realtime waltkthroughs
- particularly interested in largely unoccluded scenes (such as
outdoors)
- Related Work
- transition to Next: Barnes-Hut serves as inspiration
- transition to Next: Decided to try simplest thing first
- Our Approach
- color-cube is a cube whose volume is defined by the cell; color
and opacity value per face representing the contained geometry as seen
from that direction
- will come back to the picture. Given here as an icon for
algorithm.
- Outline
- Preprocessing: Octree Creation
- using an adaptive technique that strives to minimize the amount
of geometry rendered per frame.
- we use the triangle as a cost measure
- may want to note that a better algorithm would minimize the
amount of time taken per frame, by accounting for the cost of
traversing the octree to a cell's depth. I.e. use time-based metrics
rather than geometrically-based metrics.
- Preprocessing: Color-cube Creation
- Runtime: Rendering the Octree
- "small" means "a pixel in size" in our implementation
- in picture, point out view frustum
- green = colorcube drawn, red = geometry rendered, blue = culled
- note that coarser cells can be used further from the viewer
- allude to the fact that this method effectively prefilters
distant geometry, resulting in reduced aliasing artifacts -- will be
seen in video
- Drawbacks
- six sampled directions is very finite -- venetian blind example
- transparency artifacts -- caused by "over" compositing, six
sample directions; can be compensated for by "sewing" after colorcube
creation to preserve continuous surfaces, thresholding alphas? (slide
at end to demonstrate more effectively, if necessary)
- Slides Here
- these are slides showing some of our databases, that will be
animated in video at end
- tree slide: 51k polygons, 0.4-5.4 speedup, top row = geometry,
middle = hierarchy, bottom = closeup of hierarchy
- molecule slide: 5.2 million polygons, 0.5 - 136.3 times speedup,
same layout as above
- island database: 3.6 million polygons, 1.7-22.7 times speedup
- spock database: to demonstrate transparency artifacts that can
take place
- all views from off-sampled axis (from 15-40 degrees)
- Sublinearity Assumptions
- assumptions true, for example, in database with even distribution
of primitives
- we will use a counting argument to determine how many cells at each
level will be visited (rendered, culled, children considered)
- Rendering Observation
- for example, dashed subfrustum is where geometry is needed,
subfrustum d is where leaf cells' color-cubes are valid, etc.
- note that the depth of each subfrustum is twice the previous --
this is because each marks where a cube half as big in each dimension
maps to a pixel (half as close to viewer each time)
- note also that sizes of subfrustum are determined by
field-of-view angle, screen size, scene bounding cube -- NOT scene
complexity
- Animation of Algorithm Running (Overlays)
- walk through a few steps, showing how algorithm runs (culling,
drawing color-cubes, subdividing)
- drawing criteria is dependent on cell's center as compared to
subfrustum lines (shown when cells are split)
- note that we keep reducing the problem in scale: each subfrustum
is 1/8 the previous one's size, each cube is 1/8 the previous one's
size.
- number of cells considered at each level is related to number
that fit into subfrustum (ones with anything inside will by drawn or
have their children considered; no more than 7x this number can be
outside and culled)
- number that can fit into subfrustum bounded by a constant
- Sublinearity Argument
- processed in constant time: culled, children considered,
colorcube rendered = constant time operations; rendering geometry =
constant time operation, based on our assumptions
- Sublinearity Results
- repeatedly quadrupled tree database, drew geometry and
hierarchical versions
- culled geometry outside of view frustum
- log-log plot: x-axis = number of trees, y-axis = rendering time
- geometry linear, as expected
- hierarchy sublinear -- almost 100 times faster for 16k trees
- note we lose on smaller databases; this is due to our octree
construction heuristic not taking traversal time into account --
making heuristic time-based should make gap disappear
- Video
- all videos prerecorded, so differences in rendering time not
demonstrated; just used to show quality of images produced
- image sizes: 160x228 for animations 1-4, 320x228 for 5-6
- animation 1: tree model, geometry vs. hierarchy
- 51k triangles (same as in slides)
- 2.5x slower to 17x faster (different than in slides, due to
bigger image size, moving further from viewer)
- note reduced flickering
- animation 2: same thing, but replacing geometry with closeup of
hierarchy
- note leaves amidst cubes even in most distant frames -- indicate
regions of low geometric complexity, in which cubes weren't considered
a win
- animation 3: similar animation to #1, using molcule model
- 5.2 million triangles (same as in slides)
- 2.5x slower to 400x faster (see note for tree)
- note reduced color sparkling
- animation 4: similar to #2, but with molecule
- animation 5: island flythrough using geometry
- 3.6 million triangles
- closeup and 900-frame excerpt from 1200-frame flythrough
- note extreme flickering of distant trees
- rendering time = 2 hrs, 45 minutes
- animation 6: island using hierarchy
- same sequence as before
- trees much more solid and subtle, due to prefiltering
- rendering time = 15 minutes (11x speedup)
- note that geometry is relatively simple, and is therefore kept at
shallower levels of octree, always rendered as geometry -- no special
pains taken to achieve this; happened automatically
- closer trees rendered using geometry (only 7500 polygons each),
thus they flicker as in previous animation
- Future Work
- octree creation using time, not geometry, as complexity measure
- better cell representations to reduce drawbacks, artifacts. only
requirement is that it be constant time and look reasonable
- OS considerations: all these databases fit into memory;
prefetching, memory management techniques for larger databases
- algorithm lends itself to parallel implementation (my area of
interest)
- integration with other approaches (hierarchical Z-buffer, other
simplification techniques for nearfield)
- Conclusions
- putting in new database types as simple as enumerating
primitives, calculating bounding volume of each, rendering each
- Extra Slide: Transparency Artifact
- demonstrates how figure can appear transparent from non-sampled
(or sampled) directions
- Extra Slide: Hidden Surface Artifact
- demonstrates how hidden surfaces can contribue to image in
hierarchy -- not seen to create noticable artifacts, but could be a
problem
Back to the main page.