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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
<!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 in Sector Visibility</TITLE>
<META NAME="description" CONTENT="Crystal Space: VIS in Sector Visibility">
<META NAME="keywords" CONTENT="Crystal Space: VIS in Sector Visibility">
<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="SEC402"></A>
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_187.html#SEC401"> < </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_189.html#SEC403"> > </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.7 In-Sector Visibility </H4>
<!--docid::SEC402::-->
<P>
For a normal sector which has no octree in-sector visibility is really
very simple. Everything which is not culled by the view frustum or
the portal/sector visibility system is visible.
</P><P>
If a sector has an octree then the situation is vastly different.
Here is where the main work of the visibility algorithm happens.
In-sector visibility is also 2D based (screen coordinates). This is why
the discussion for detail objects in the previous section (Portal/Sector
Visibility) is relevant here too. In general we will try to avoid to
do as little culling work as possible while still trying to cull as
much as possible.
</P><P>
The above comment is why it is important to have a good world design.
World geometry (which is at the basis of visibility culling) should
contain as little polygons as possible but they should be as big as
possible and also potentially cull lots of geometry. Culling objects
should be found for all large detail objects which can potentially
cull large numbers of other objects or portals.
</P><P>
The current culler works with the c-buffer. For every scanline we have a list
of not rendered spans (i.e. the Crystal Space c-buffer keeps empty spans
instead of full spans). Initially we will have a list of <EM>H</EM> spans with
<EM>H</EM> being the number of scanlines on the screen. Every span will have a
width of <EM>W</EM> with <EM>W</EM> being the number of horizontal screen pixels.
When a polygon is added to the c-buffer it will be scan-converted and every
scan of the polygon will be inserted at the appropriate line of the c-buffer.
</P><P>
An important issue with the c-buffer is that it doesn't have Z information.
So adjacent empty or full spans can be merged. This is in contrast
with the s-buffer which keeps Z information for every span.
This keeps complexity down enormously and also improves efficiently.
The downside of this method is that it requires perfect front to back
sorting in order to work properly (more on ways to solve that later).
</P><P>
So given an octree and the c-buffer we can explain how the basic
visibility algorithm works.
</P><P>
We start by initializing the c-buffer to empty.
Then we traverse all nodes and polygons from front to back. Every polygon
that is encountered is fed to the c-buffer and added to it. This means
projecting the polygon to camera space and then perspective projecting
it. If the c-buffer indicates that a polygon is not visible it will be
culled at this stage already. This is called polygon culling. More important
than polygon culling is node culling. Before traversing into a new
octree node we take the convex outline of the node box and test if that
convex outline is visible to the c-buffer. This is the main reason that
the c-buffer culling is in Crystal Space. Culling octree nodes can be a huge
speed benefit as they can often contain thousands of polygons and also
other child nodes.
</P><P>
This is the basic idea behind c-buffer culling. But here we have several
choices on what to do with individual polygons and detail objects.
</P><P>
Let's first focus on individual polygons. In the discussion above we told
you that we can cull individual polygons by feeding them to the c-buffer
and seeing if they are actually visible or not. We cannot get around
the fact that we need to put them in the c-buffer (we're talking about
world geometry here, not detail objects). And since we do that the test
to see if the c-buffer was modified (i.e. the polygon is visible) is
trivial. On the other hand, in order to be able to use this visibility
test for individual polygons we need strict front to back order. This
is provided by the BSP trees. Traversing the BSP tree itself involves
some overhead. First of all because it does some processing with regards
to testing on which side of every splitter the camera is and also before
the BSP tree itself caused polygons to be split so there are actually
more polygons to consider. So we could consider rendering and feeding
the polygons from the octree node in original unsorted order. This way
we would not be able to use visibility information for the polygons
themselves but the c-buffer would still be correctly filled. This will
cause a big number of overdraw so this should only be done on hardware
that is fast enough. Also this approach may mean that it would be better
to lower the number of polygons at which the octree reverts to BSP
trees (i.e. 150 right now). This means we'll get smaller octree nodes
and thus reduce overdraw that way. This is an area where some
experimentation is needed.
</P><P>
Detail objects are another issue. Similar to what was discussed in
the portal/sector visibility section we have several options here. First
we could just say that all detail objects that are in some node are
visible when the node itself is visible. This is easy to do and would
give little overhead with regards to the c-buffer. On the other hand
it can cause considerable overdraw and if the detail objects are complex
it may be too slow.
</P><P>
The other option is to test a bounding box (or the convex outline
of the bounding box) against the c-buffer. There is even the option
of a hybrid approach. i.e. simple detail objects can be considered
as visible if the parent node is visible while complex objects will
have a bounding box that is tested.
</P><P>
So again, there is much room for experimentation to see what approach
works best. It may be that we will have to make things configurable
depending on the selected hardware.
</P><P>
<A NAME="VIS PVS"></A>
<HR SIZE=1>
<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_187.html#SEC401"> < </A>]</TD>
<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="cs_189.html#SEC403"> > </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>
|
