1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- Created by texi2html 1.64 -->
<!--
Written by: Lionel Cons <Lionel.Cons@cern.ch> (original author)
Karl Berry <karl@freefriends.org>
Olaf Bachmann <obachman@mathematik.uni-kl.de>
and many others.
Maintained by: Olaf Bachmann <obachman@mathematik.uni-kl.de>
Send bugs and suggestions to <texi2html@mathematik.uni-kl.de>
-->
<HTML>
<HEAD>
<TITLE>Crystal Space: VIS PVS</TITLE>
<META NAME="description" CONTENT="Crystal Space: VIS PVS">
<META NAME="keywords" CONTENT="Crystal Space: VIS PVS">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META NAME="Generator" CONTENT="texi2html 1.64">
</HEAD>
<BODY LANG="" BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#800080" ALINK="#FF0000">
<A NAME="SEC403"></A>
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_188.html#SEC402"> < </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_190.html#SEC405"> > </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_174.html#SEC377"> << </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_181.html#SEC390"> Up </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_190.html#SEC405"> >> </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="index.html#SEC_Top">Top</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_toc.html#SEC_Contents">Contents</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_285.html#SEC711">Index</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_abt.html#SEC_About"> ? </A>]</TD>
</TR></TABLE>
<HR SIZE=1>
<H4> 7.6.7.8 Potentially Visible Set (PVS) </H4>
<!--docid::SEC403::-->
<P>
The c-buffer is a very good way to manage real-time visibility.
i.e. there is no precalculation involved (except for the octree).
However it is a reasonably high overhead since it involves transformation
to camera space, perspective projection, and scan converting every
polygon.
</P><P>
We already presented ways to reduce the overhead by limiting c-buffer
filling to world geometry and culling objects only. But this may not
be enough.
</P><P>
So we present another way to reduce this overhead. This is a PVS
or Potentially Visible Set. Basicly for every octree leaf in the
octree we keep a set of all other visible nodes and polygons.
Before testing a polygon or node against the c-buffer we will first
see if it is in the PVS of the current leaf where the camera is.
If it is not then we don't need to continue testing. This means we
can avoid having to transform, perspective project, and scan convert
the polygon and then test to the c-buffer. This can be a <EM>huge</EM> benefit.
</P><P>
After doing the PVS test we have two choices basicly. We can still
decide to use the c-buffer to do finer culling tests. The PVS only
provides region to region visibility. It is possible that less is
visible from within some point in some region. Whether or not it
is really worth it to cull further is again something which we'll
have to test. For the software renderer it will probably be worthwhile
because overdraw is so expensive there. On the other hand it can
still be useful to use the c-buffer in order to be able to cull
complex detail objects.
</P><P>
Static detail objects (detail objects that cannot move) could also
be included in the PVS easily.
</P><P>
<A NAME="SEC404"></A>
<H4> Calculating the PVS </H4>
<!--docid::SEC404::-->
<P>
Calculating the PVS is a complex and time consuming task in itself.
Currently this is not yet implemented. The approach that is probably
going to be used works as follows.
</P><P>
We traverse every leaf of the octree (ignore BSP nodes and leaves).
For every such leaf we want to build the PVS. So we again traverse
the octree for every other node this time. We are going to test visibility
between the leaf and every other node (called occludee). When we find
that some occludee is not visible we don't have to continue to the children.
They will not be visible either.
</P><P>
So for a given leaf and occludee we initialize a cube of c-buffers (or
some other 2D visibility system like the coverage mask tree). On this
cube we are going to paint all shadows that are caused by occluders
between the leaf and occludee.
</P><P>
So we then again traverse the octree to find all potential occluders.
An occluder will be considered if it is between the leaf and the occludee.
The algorithm works as if the occludee is an area light source.
We will take all the polygons of an occluder and cast shadows from the
light source on the cube surrounding the leaf. If eventually the
cube is entirely shadowed by the collected polygons in all potential
occluders then we say that the occludee is not visible from within the
leaf. So we don't add it to the PVS.
</P><P>
An optimization here is that when an occluder already has a calculated
PVS then we can see if the occludee is visible for the occluder. If not
then the occluder can be seen as a solid box from the viewpoint of the
leaf for the occludee and we can cast a shadow from the entire box at
once.
</P><P>
This is the basic algorithm. More detail will follow later (about the
PVS for polygons and so on).
</P><P>
<A NAME="Rendering Loop"></A>
<HR SIZE=1>
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_188.html#SEC402"> < </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_190.html#SEC405"> > </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_174.html#SEC377"> << </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_181.html#SEC390"> Up </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_190.html#SEC405"> >> </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT"> <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="index.html#SEC_Top">Top</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_toc.html#SEC_Contents">Contents</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_285.html#SEC711">Index</A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_abt.html#SEC_About"> ? </A>]</TD>
</TR></TABLE>
<BR>
<FONT SIZE="-1">
This document was generated
using <A HREF="http://www.mathematik.uni-kl.de/~obachman/Texi2html
"><I>texi2html</I></A>
</BODY>
</HTML>
|
