Transcript Lecture notes.

Last Time
• Simplification for LOD
• Progressive Meshes
• Runtime LOD
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Today
• Terrain
– Creation
– Rendering
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Terrain
• Terrain is obviously important to many games
• As a model, it is very large
• Creating every point explicitly by hand is not feasible, so
automated terrain generation methods are common
• When rendering, some of the terrain is close, and other parts
are far away, leading to terrain LOD algorithms
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Representing Terrain
• The base representation for terrain is usually a height field
– z=f(x,y) for (x,y) within the limits of the space
– Precludes things like caves and overhangs, which must be treated specially
• There are two common ways to represent the function f(x,y)
– Explicitly store the value of f(x,y) for a discrete grid of (x,y) locations
• Generally interpolate (bilinear) or triangulate to get points not on the grid
• Easy to figure out what the height of the terrain is at any given (x,y)
• Expensive to store the entire terrain
– Store a polygonal mesh
• Cheaper if the terrain has large flat areas
• Harder to figure out what the height is under the player (have to know which
triangle they are in)
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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 continuous LOD algorithms are similar in style
• An alternative is to create fixed LODs for sub-regions and
figure out how to join them at the seams
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Triangle Bintree Example
3
1
4
6
1
2
2
5
3
8
7
13
10
14
9
11
10/16/03
7
4
8
9
5
10
12
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Cuts
3
1
4
6
1
2
2
5
3
8
7
7
4
8
9
5
10
10
9
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
11
6
12
13
14
Neighbors
8
7
10
6
9
5
•
•
•
•
•
•
5: left neighbor 6, right neighbor 9
6: left neighbor 8, right neighbor 5
7: left neighbor 8, base neighbor 10
8: base neighbor 6, right neighbor 7
9: base neighbor 5, left neighbor 10
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
Note the T-vertex - causes
cracks in rendering
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
2
4
8
9
5
10
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
8
9
10
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Todo
• By Monday, Oct 20, Stage 3 goals
• By Monday, Nov 3, Stage 3 demo
10/16/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin