Occlusion culling

Occlusion culling, papers, graphics, culling

[ Pobierz całość w formacie PDF ]
Fast and Simple Occlusion Culling
Wagner T. Corrêa – Princeton University –
James T. Klosowski – IBM Research –
j
Cláudio T. Silva – AT&T Labs-Research –
c
Introduction
In many graphics applications, such as building walkthroughs and first-person games, the
user moves around the interior of a virtual environment and the computer creates an
image for each location of the user. For any given position, the user typically sees only a
small fraction of the scene. Thus to speed up the image rendering, an application should
avoid drawing the primitives in the environment that the user cannot see. There are
several classes of algorithms to determine which primitives should be ignored, or culled.
Back-face culling algorithms determine those primitives that face away from the user.
View frustum culling determines the primitives that lie outside of the user's field of view.
Occlusion culling determines the primitives that are occluded by other primitives.
While back-facing and view frustum culling algorithms are trivial, occlusion culling
algorithms tend to be complex and usually require time consuming preprocessing steps.
This gem describes two occlusion culling algorithms that are practical, effective, and
require little preprocessing. The first one is the prioritized-layered projection (PLP)
algorithm, which is an approximate algorithm that determines, for a given budget, a set of
primitives that are likely to be visible. The second algorithm, cPLP, is a conservative
version of PLP that guarantees to find all visible primitives.
The Visibility Problem
Given a scene composed of modeling primitives and a viewing frustum, we need to
determine which primitive fragments are visible, i.e., connected to the eye-point by a line
segment that meets the closure of no other primitive [Dobkin97]. Researchers have
studied this problem extensively and many approaches to solve it exist [Cohen-Or01,
Durand99]. In their survey on visibility algorithms, Cohen-Or et al. classify algorithms
according to several criteria. Next, we briefly summarize those that are of most relevance
to our gem:
From-point vs. from-region:
Some algorithms compute visibility from the eyepoint
only, while others compute visibility from a region in space. Since the user often stays for
a while in the same region, the from-region algorithms amortize the cost of visibility
computations over a number of frames.
Precomputed vs. online:
Many algorithms require an off-line computation,
while others work on the fly. For example, most from-region algorithms require a
preprocessing step to divide the model in regions, and compute region visibility.
Fast and Simple Occlusion Culling
1
Object space vs. image space:
Some algorithms compute visibility in object space, using
the exact original 3D primitives. Others operate in image space, using only the discrete
rasterization fragments of the primitives.
Conservative vs. approximate:
Few visibility algorithms compute exact visibility. Most
algorithms are conservative, and overestimate the set of visible primitives. Other
algorithms compute approximate visibility, and do not guarantee finding all visible
primitives.
In this gem, we describe two visibility algorithms that are simple solutions and work well
in practice: the prioritized-layered projection algorithm, PLP, and its conservative
version, cPLP.
The PLP Algorithm
PLP [Klosowski00] is an approximate, from-point, object-space visibility algorithm that
requires very little preprocessing. PLP may be understood as a simple modification to the
traditional hierarchical view frustum culling algorithm [Clark76]. The traditional
algorithm recursively traverses the model hierarchy from the root node down to the leaf
nodes. If a node is outside the view frustum, we ignore the node and its children. If the
node is inside or intersects the view frustum, we recursively traverse its children. The
traversal eventually visits all leaves within the view frustum. The PLP algorithm differs
from the traditional one in several ways. First, instead of traversing the model hierarchy
in a predefined order, PLP keeps the hierarchy leaf nodes in a priority queue called the
front
, and traverses the nodes from highest to lowest priority. When we visit a node (or
project
it, in PLP parlance), if it is visible, we add it to the
visible set
. Then, we remove it
from the front, and add its
layer
of unvisited neighbors to the front (hence, the
algorithm’s name: prioritized-layered projection). Second, instead of traversing the entire
hierarchy, PLP works on a
budget
, stopping the traversal after a certain number of
primitives have been added to the visible set. Finally, PLP requires each node to know
not only its children, but also all of its neighbors.
An implementation of PLP may be simple or sophisticated, depending on the heuristic to
assign priorities to each node. Several heuristics precompute the initial
solidity
of a node,
and accumulate the solidities along a traversal path. The node’s accumulated solidity
estimates how likely it is for the node to occlude an object behind it [Klosowski00]. In
this gem, we use an extremely simple heuristic to assign priorities to the nodes. The node
containing the eyepoint receives priority –1; its neighbors receive priority –2; their
neighbors –3, and so on. Using this heuristic, the traversal proceeds in layers of nodes
around the eyepoint. This is simple to implement, very fast, and quite accurate (we will
show accuracy measurements when we present the run-time results). The only
precomputation this heuristic requires is the construction of the hierarchy itself.
We use PLP as a front-end to the hardware's implementation of the Z-buffer algorithm
[Foley90]. For a given budget, PLP gives us the set of primitives it considers most likely
to maximize image quality. We simply pass these primitives to the graphics hardware.
Fast and Simple Occlusion Culling
2
Implementation
class Plp {
public:
explicit Plp(const char *file_name);
void start(const View &view);
bool step();
enum {DEFAULT_BUDGET = 10000};
enum {NS_CLEAN, NS_PROJECTED, NS_ENQUEUED,
NS_UNSEEN};
protected:
void front_push(OctreeNode *node);
OctreeNode *front_pop();
void project(OctreeNode *node);
void add_neighbors_to_front(OctreeNode *node);
bool is_potentially_visible(OctreeNode *node);
typedef set<OctreeNode *,
OctreeNode::CompareSolidity> plp_front_t;
plp_front_t _front;
vector<OctreeNode *> _visible_set;
unsigned _budget, _num_triangles_rendered;
unsigned _time_stamp;
Octree _octree;
const View *_view;
OctreeNode *_closest_leaf;
ImageTileSet _tiles;
Plp::Plp(const char *file_name)
: _budget(DEFAULT_BUDGET),
_num_triangles_rendered(0), _time_stamp(0),
_view(NULL), _closest_leaf(NULL)
{
}
_octree.read(file_name);
void Plp::start(const View &view)
{
_view = &view;
_num_triangles_rendered = 0;
_time_stamp = 0;
reset_node_states();
_front.clear();
_visible_set.clear();
_closest_leaf = _octree.find_closest_leaf(_view);
if (_closest_leaf == NULL)
return;
Fast and Simple Occlusion Culling
3
};
}
_closest_leaf->set_solidity(0.0);
_closest_leaf->set_layer(0);
front_push(_closest_leaf);
bool Plp::step()
{
if (_front.empty())
return false;
OctreeNode *node = front_pop();
project(node);
add_neighbors_to_front(node);
return _num_triangles_rendered < _budget;
}
void Plp::front_push(OctreeNode *node)
{
node->set_time_stamp(_time_stamp);
_time_stamp++;
_front.insert(node);
set_node_state(node, NS_ENQUEUED);
}
// returns node most likely to be visible
OctreeNode *Plp::front_pop()
{
OctreeNode *node = *(_front.begin());
_front.erase(_front.begin());
return node;
}
bool Plp::is_potentially_visible(OctreeNode *node)
{
}
return _view->camera().sees_ignoring_near_plane(
node->bounding_box());
void Plp::project(OctreeNode *node)
{
set_node_state(node, NS_PROJECTED);
if (is_potentially_visible(node)) {
_visible_set.push_back(node);
_num_triangles_rendered +=
node->num_triangles();
}
}
Fast and Simple Occlusion Culling
4
void Plp::add_neighbors_to_front(OctreeNode *node)
{
const vector<OctreeNode *> &neighbors =
node->neighbors();
for (unsignedi=0;i<neighbors.size(); i++) {
OctreeNode *neighbor = neighbors[i];
if (node_state(neighbor) != NS_CLEAN)
continue;
if (!is_potentially_visible(neighbor)) {
set_node_state(neighbor, NS_UNSEEN);
continue;
}
}
neighbor->set_layer(node->layer() + 1);
neighbor->set_solidity(neighbor->layer());
front_push(neighbor);
}
The cPLP Algorithm
Although PLP is in practice quite accurate for most frames, it does
not
guarantee image
quality, and some frames may show objectionable artifacts. To circumvent this potential
problem, we use cPLP [Klosowski01], a conservative extension of PLP.
The main idea of cPLP is to use the visible set given by PLP as an initial guess, and keep
adding nodes to the visible set until the front (the priority queue with nodes) is empty.
This guarantees that the final visible set is conservative [Klosowski01]. There are many
ways to implement cPLP, including exploiting new platform-dependent hardware
extensions for visibility computation. The implementation we describe in this gem uses
an item-buffer technique that is portable to any system that supports OpenGL.
The cPLP main loop consists of two steps. First, we determine the nodes in the front that
are visible. We draw the bounding box of each node in the front using flat shading and a
color equal to its identification number. We then read back the color buffer, and
determine the nodes seen. Second, for each front node found to be visible, we project it
(maybe adding it to the visible set), remove it from the front, and add its unvisited
neighbors to the front. We iterate the main loop until the front is empty. The bottleneck
of the item buffer-based implementation of cPLP is reading back the color buffer. To
avoid reading the entire color buffer at each step, we break the screen into tiles. Tiles that
are not modified in one step may be ignored in subsequent steps.
Implementation
void Plp::find_visible_front()
{
// save masks
Fast and Simple Occlusion Culling
5
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

happyhour.opx.pl