Transcript Lecture notes.

Today
• Terrain
– Terrain LOD
10/23/2001
CS 638, Fall 2001
Terrain LOD
• As you have heard by now, terrain poses problems
for static LOD methods
– Must have high resolution in the near field, and low
resolution in the distance, all in one model
• Dynamic LOD methods are the answer
– All based on the idea of cuts through a tree of potential
simplifications
• We will discuss the ROAM algorithm in detail
– Other algorithms are similar in style, but this is the best
10/23/2001
CS 638, Fall 2001
Terrain is Easier!
• Assumption: We are starting with a height field defined on a
regular grid
– Assume it’s a square to make it easier
– We can mesh it by forming triangles with the data points
• The data is highly structured
– Every data point has the same number of neighbors
– Every triangle can be the same size
– Hence, the tree of possible simplifications is very regular
• Still, multiple possibilities exist for the triangulation and the
simplification operations
10/23/2001
CS 638, Fall 2001
Triangle Bintrees
• Binary trees in which:
– Each node represents a right-angled isosceles triangle
– Each node has two children formed by splitting from the right angle
vertex to the midpoint of the baseline
– The leaf nodes use vertices from the original height field
• Another way to build a spatial partitioning tree, but
particularly well suited to simplification algorithms
– Easy to maintain neighbor information
– Easy to avoid T-vertices
10/23/2001
CS 638, Fall 2001
Triangle Bintree Example
3
1
4
6
1
2
2
5
3
8
7
13
10
14
9
11
10/23/2001
7
12
CS 638, Fall 2001
4
8
9
5
10
11
6
12
13
14
Bintree Data Structure
• Parent and child pointers
• Neighbors
– A left neighbor, a right neighbor, and a base neighbor
– Note that the base and right angle give us a way to orient the triangle
– Neighbors are not necessarily at your own level
• Later, error bounds that say how much variation in height
there is in your children
10/23/2001
CS 638, Fall 2001
Cuts
3
1
4
6
1
2
2
5
3
8
7
7
10
9
10/23/2001
CS 638, Fall 2001
4
8
9
5
10
11
6
12
13
14
Neighbors
• 5: left neighbor 6, right neighbor 9
• 6: left neighbor 8, right neighbor 5
8
7
10
• 7: left neighbor 8, base neighbor 10
6
• 8: base neighbor 6, right neighbor 7
9
• 9: base neighbor 5, left neighbor 10
5
• 10: base neighbor 7, right neighbor 9
• Note that 8 is 6’s left neighbor but 6 is 8’s base neighbor
– If you are someone’s left/right/base neighbor they are not always
your right/left/base neighbor
• In other words, neighbors need not come from the same
level in the tree
10/23/2001
CS 638, Fall 2001
Not All Cuts Are Created Equal
3
1
1
4
6
2
3
5
7
8
2
4
8
9
5
10
11
6
12
13
7
10
9
10/23/2001
CS 638, Fall 2001
Note the T-vertex - causes
cracks in rendering
14
Generating Cuts
• Cuts are generated by a sequence of split or merge
steps
– Split: Drop the cut below to include your children
– Merge: Lift the cut up above two children
• To avoid T-vertices, some splits lead to other,
forced, splits
• An LOD algorithm chooses which steps to apply to
generate a particular triangle count or error rate
10/23/2001
CS 638, Fall 2001
A Split
• A split cuts a triangle in two by splitting its base edge
– If the base edge is on a boundary, just split, as shown
– If the base edge is shared, additional splits are forced
• Add a new triangle to the mesh
1
3
6
7
10/23/2001
2
CS 638, Fall 2001
4
8
9
5
10
11
6
12
13
14
Forced Splits
• Triangles are always split
along their base
• Hence, must also be able to
split the base neighbor
– Requires neighbors to be
mutual base neighbors
– If they are not base neighbors,
even more splits are needed
– Simple recursive formulation
10/23/2001
CS 638, Fall 2001
Merges
• A diamond is a merge candidate if the children of it’s
members are in the triangulation
– The children of the 7-10 diamond below are candidates
– Look for parents of sibling leaf nodes that are base neighbors or
have no base neighbors
• Reduces the triangle count
1
8
2
7
10
3
4
5
6
9
7
10/23/2001
CS 638, Fall 2001
8
9
10
11
12
13
14
Refinement LOD Algorithm
• Start with the base mesh
• Repeatedly split triangles until done
– Stop when a specific triangle count is reached, or …
– Stop when error is below some amount
• To guide the split order, assign priorities to each split and
always do the one with the highest priority
– After each split, update priorities of affected triangles
– Sample priority: High priority to splits that will reduce big errors
• What is the complexity of this? (Roughly)
• A similar algorithm works by simplifying the mesh through
merge operations. Why choose one over the other?
10/23/2001
CS 638, Fall 2001
Refinement Notes
• If the priorities are monotonic, then the resulting terrain is
optimal
– Monotonic: Priorities of children are not larger than that of their
parent
• Priorities can come from many sources:
– In or out of view, silhouette, projected error, under a vehicle, line of
sight, …
• Does not exploit coherence: As the view moves over the
terrain, the triangulation isn’t likely to change much
• We should be able to start with the existing triangulation,
and modify it to produce the new optimal triangulation
10/23/2001
CS 638, Fall 2001
Dual Queue Optimization
• Have the split queue, as before
• Have a merge queue:
– Queue of potential merges, with priority as the max of
the split priority for the triangles in each merge
• Repeat until target size/accuracy and the max split
priority is less than the min merge priority
– If the mesh is too large/accurate, do the optimal merge
• Update data structures appropriately
– Otherwise, do the optimal split
• Update data structures appropriately
10/23/2001
CS 638, Fall 2001
Why Does it Work?
• The merge queue priorities tell you how much error you would
add by doing each merge
• The split queue tells you how much error you would remove
by doing each split
• A merge frees up two triangles, while a split takes at least one
• If you can free some triangles with a merge and use them with
a more effective split, then you win
– The min in the merge queue is the least error you can add with a merge
– The max in the split queue is the most error you can remove with a split
– If you can trade a split for a merge and save some error, then do it
10/23/2001
CS 638, Fall 2001
Projected Error Metrics
• Idea is to figure out how far a sequence of merges
moves the terrain from its original correct location
– Measured in screen space, which is what the viewer sees
• Start with bounds in world space, and then project
the bounds at run-time
– World space bounds are view independent
– Projected screen space bounds are view dependent
10/23/2001
CS 638, Fall 2001
World Space Bounds
• With terrain, merge only moves points up or down
• Bound how far a point can move with a wedgie
– A bintree triangle extruded up and down to contain its children
– Defined by d, the thickness of the extrusion
• Fast to compute, so works for dynamic terrain
– Important for explosion craters and the like
d
10/23/2001
CS 638, Fall 2001
Performance Bottlenecks
• Storing and managing priorities for out-of-view triangles is
a waste of time
– Do standard frustum culling to identify them
• Sending individual triangles is wasteful
– Build strips as triangles are split and merged
• Naively, at every frame, wedgies must be projected, new
priorities computed and the queues re-sorted
– Use the viewer’s velocity to bound the number of frames before a
priority could possibly make it to the top of a heap
– Delay recomputation until then
• Priority queue: Bin priorities to reduce sorting cost
– At low priorities, order within bins doesn’t matter
10/23/2001
CS 638, Fall 2001
Additional Enhancements
• Stop processing after a certain amount of time
– Easily done: just stop processing the next split or merge
– Result no longer optimal, but probably not bad
• Cost of dual queue algorithm depends on the number of
steps required to change one mesh into another
– Check ahead of time how many steps might be required
– If too may, just rebuild mesh from scratch using refinement
algorithm
• Can get accurate line-of-sight or under-vehicle height by
manipulating priorities to force certain splits
10/23/2001
CS 638, Fall 2001
Other Algorithms
• Algorithm from Lindstrom et al is essentially the same idea
as the ROAM refinement algorithm
– Based on square blocks of (triangulated) terrain
• Makes determining forced splits harder
– Slightly different error bounds
• An algorithm from the game community:
– For a particular split operation, the viewer distance is the primary
error factor
– For each split, store distance at which it should occur
– Check current mesh on each frame for splits/merges according to
viewer distance
– Non-optimal, but gets rid of priority queues (the big cost)
10/23/2001
CS 638, Fall 2001
Midterm Info
• Thursday in class
• Bring in:
– Something to write with
– A ruler (it will be helpful)
– A double sided letter sized sheet with anything on it
(except things that increase the surface area)
10/23/2001
CS 638, Fall 2001
Project Next Stage
• LithTech does almost everything we have talked
about in the last six weeks
• So, the next stage is going to be done mostly in
OpenGL (or similar)
– Light maps
– Stencil-buffer shadow volume algorithms
• LOD in LithTech
10/23/2001
CS 638, Fall 2001