📄 osr.htm
字号:
<!--Header-->
<HTML>
<HEAD>
<TITLE>GPMega - Advanced Section - Object Space Rejection</TITLE>
</HEAD>
<BODY BGCOLOR=#000000 TEXT=#FFFFFF LINK=#00FF00 VLINK=#00FF00 ALINK=#0000FF>
<!--End Header-->
<!--Advertiser-->
<CENTER>
<TABLE>
<TR>
<TD>
<A HREF="http://www.ugo.com/">
<IMG SRC="/GPMega/ugologo120.gif" BORDER=0 WIDTH=120 HEIGHT=60></A>
</TD>
<TD>
<IMG SRC="/GPMega/sponsored.gif" WIDTH=468 HEIGHT=10><br><br>
<SCRIPT LANGUAGE= "JavaScript">
<!--
var now = new Date();
var random_num = now.getSeconds();
document.write("<A HREF='http://www.ugo.net/RealMedia/ads/click_nx.cgi/www.perplexed.com/GPMega/advanced/osr.htm/" + random_num + "/@Top'>");
document.write("<IMG SRC='http://www.ugo.net/RealMedia/ads/adstream_nx.cgi/www.perplexed.com/GPMega/advanced/osr.htm/" + random_num + "/@Top' BORDER='0' WIDTH='468' HEIGHT='60'></A>");
//-->
</SCRIPT>
</TD>
</TR>
</TABLE>
</CENTER>
<!--End Advertiser-->
<!--Splitter-->
<BR>
<!--End Splitter-->
<!--Body-->
<FONT SIZE=2 FACE=Helvetica>
<STRONG>
<!--Top Navigation-->
<A NAME="top"></A>
<CENTER>
<TABLE WIDTH=75%>
<TR VALIGN=MIDDLE>
<TD ALIGN=LEFT>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1><BR><BR>
<A HREF="http://www.perplexed.com/GPMega/"><IMG SRC="logo.jpg" BORDER=0 ALT="Home" WIDTH=80 HEIGHT=47 ALIGN=CENTER></A>
<FONT COLOR=#666666 FACE=HELVETICA SIZE=-1><I>
This Article Is Taken From <A HREF="http://www.perplexed.com/GPMega/">The Game Programming MegaSite</A>, A Definitive Resource For Game Developers!
</I></FONT><BR>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1>
</TD>
</TR>
</TABLE>
</CENTER>
<BR><!--End Top Navigation-->
<!--Title-->
<H3 ALIGN=CENTER><font color="#FFF400">O</font><font color="#FFE900">b</font><font color="#FFDE00">j</font><font color="#FFD300">e</font><font color="#FFC800">c</font><font color="#FFBD00">t</font><font color="#FFB200"> </font><font color="#FFA700">S</font><font color="#FF9C00">p</font><font color="#FF9100">a</font><font color="#FF8600">c</font><font color="#FF7B00">e</font><font color="#FF7000"> </font><font color="#FF6500">R</font><font color="#FF5A00">e</font><font color="#FF4F00">j</font><font color="#FF4400">e</font><font color="#FF3900">c</font><font color="#FF2E00">t</font><font color="#FF2300">i</font><font color="#FF1800">o</font><font color="#FF0D00">n</font><BR><FONT SIZE=-2>By: Jeff Weeks</FONT></H3>
<!--End Title-->
<P>Speed is an obvious concern when writing a
3D engine, particularly a software based engine. While speed-ups can
present themselves in many forms, the most obvious, and greatest
speed-up can be gained by merely rejecting points and polygons as
fast as possible if they aren't needed.
<P>Typically this job is left to backface
culling which can remove approximately half the workload from all
your 3D routines by cutting your object in half and removing all
those polygons which are invisible (see my backface culling article
for more information). However, this method also assumes that you've
transformed all your points into world space, seeing as though you
must cull against the camera's position, which is specified in world
space.
<P>What if it were possible to backface cull
in object space? Not only could you skip transforming all your points
into world space just to end up rejecting half of them, but you also would be
able to shade your object in object space, thereby removing the need
to transform the many polygon and vertex normals. This is all
possible through a simple technique which involves transforming the
camera into object space.
<H3><FONT COLOR=YELLOW><I>The Bounding Sphere Test</I></FONT></H3>
<P>Before going through with all this,
however, it makes sense to check if the object will even be visible
in the long run. This can be done by using a bounding sphere test.
Your bounding sphere is a sphere which encompases the entire object.
You can calculate this by merely storing the highest x, y and z
values of your object, when loading, and then converting this into a
distance (the bounding sphere's radius):</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
radius = sqrt( highest_x * highest_x +
highest_y * highest_y + highest_z * highest_z );
</FONT></PRE>
</BLOCKQUOTE>
<P>Now that you have a bounding sphere
definition (all you need is its radius) you can use this to test if
the object will be visible to the camera. This process involves
transforming the object's center position ( which would be (0,0,0) )
into camera space (the space which the camera sees, sometimes called
view space):</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
object_center = new Vertex(0,0,0);
object_center = object_center * to_view_space_matrix;
</FONT></PRE>
</BLOCKQUOTE>
<P>and checking the bounding sphere against
the clip planes of the frustum. The frustum has six clipping planes,
but some may choose to ignore the front and back planes. That is up
to you, of course. The planes are described as:</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
x = <IMG SRC="clip_plane.gif" NAME="Object1" ALIGN=ABSMIDDLE WIDTH=36 HEIGHT=16 BORDER=0>
y = <IMG SRC="clip_plane.gif" NAME="Object2" ALIGN=ABSMIDDLE WIDTH=36 HEIGHT=16 BORDER=0>
z = d
z = f
</FONT></PRE>
</BLOCKQUOTE>
<P>Where:</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
2h is the view plane window dimension
d is the view plane distance
f is the far plane distance
</FONT></PRE>
</BLOCKQUOTE>
<P>If your object is visible, it will be
withen these boundaries. If not, it stands to reason it will then be
invisible to the camera, and can be rejected. A whole object is then
removed from your work load with a minimal number of calculations. I
do the bounding sphere test as follows:</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
center = new Vertex(0,0,0);
center = center * to_view_space;
clip_x = (view->xoff * center->z) / view->d;
clip_y = (view->yoff * center->z) / view->d;
// Test the extremities of the bounding sphere
visible += (center->x + radius < -clip_x);
visible += (center->x - radius > clip_x);
visible += (center->y + radius < -clip_y);
visible += (center->y - radius > clip_y);
visible += (center->z + radius < view->d);
visible += (center->z + radius > view->f);
// if not visible simply quit
if(visible > 0) return;
</FONT></PRE>
</BLOCKQUOTE>
<P>The process is very simple and requires
only a couple multiplies and divides plus a matrix multiplication to
possibly reject and entire object.
<H3><FONT COLOR=YELLOW><I>Object Space Rejection</I></FONT></H3>
<P>Now for the actual topic of
this article; object space rejection. If you've decided, by means of
the bounding sphere test, that your object is going to be visible it
is now time to move the camera into object space. This is actually a
fairly simple manoever, considering what you have at your disposal.
<P>Your object will, or should,
have a matrix to transform points from object space to world space.
If we take the inverse of this matrix we can then transform points
from world space back into object space. This is perfect, seeing as
though the camera is in world space, and we want it in the object
space of the object. We just have to act as though the camera is
actually part of the object (Afterall, it is the object's matrix
we're using. This matrix is very object specific). To do this,
merely specify the camera's position as an offset from the object's
position in world space. I do all the above as follows:</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
// here's the inverse matrix calculation
to_object_space.matrix[0][0] = to_world_space.matrix[0][0];
to_object_space.matrix[0][1] = to_world_space.matrix[1][0];
to_object_space.matrix[0][2] = to_world_space.matrix[2][0];
to_object_space.matrix[0][3] = 0;
to_object_space.matrix[1][0] = to_world_space.matrix[0][1];
to_object_space.matrix[1][1] = to_world_space.matrix[1][1];
to_object_space.matrix[1][2] = to_world_space.matrix[2][1];
to_object_space.matrix[1][3] = 0;
to_object_space.matrix[2][0] = to_world_space.matrix[0][2];
to_object_space.matrix[2][1] = to_world_space.matrix[1][2];
to_object_space.matrix[2][2] = to_world_space.matrix[2][2];
to_object_space.matrix[2][3] = 0;
to_object_space.matrix[3][0] = 0; to_object_space.matrix[3][1] = 0;
to_object_space.matrix[3][2] = 0; to_object_space.matrix[3][3] = 1;
// Now calculate the offset from the camera's position and the object's position
camera.x = view->camera->matrix[0][3] - to_world_space.matrix[0][3];
camera.y = view->camera->matrix[1][3] - to_world_space.matrix[1][3];
camera.z = view->camera->matrix[2][3] - to_world_space.matrix[2][3];
</FONT></PRE>
</BLOCKQUOTE>
<P>As you can see, I've inverted
the to_world_space matrix and stored it in to_object_space and I've
also stored the camera's position as an offset from the object's
position in a vertex. From here on in it's all downhill. The tough
part is over. To transform the camera into object space merely
multiply the above vertex by the above matrix:</P>
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
camera = camera * to_object_space;
</FONT></PRE>
</BLOCKQUOTE>
<P>You can now use the resultant
vertex to perform backface culling, in object space. The only
difference now is that when you find that a polygon is visible you
must now transform it into world space to use it. It would be very
wise, of course, to keep track of which vertices you've transformed
already (considering one vertex could be shared by many polygons and
you only need to transform it once). I do this by keeping a large
array of 32-bit integers, one for each vertex. If the value in the
array for the point in question is equal to the current frame number
(I keep a running total of how many frames have been displayed so
far) then the point has already been transformed, otherwise I
transform it and set the array value equal to the frame number.
<P>That about covers it. It is a
fairly simple process, but the advantages are many. I would suggest
doing your shading in object space as well because then you don't
need to transform the vertex normals into world space at all. I
would not recommend clipping in object space. Yes, it is possible to
transform the view frustum into object space and clip there, but it
is certainly not worth it. Think of it this way; most objects are
made up of 3 or 4 point polygons and will almost always clip to
polygons with more points than the original, therefore just making
more work when transforming to world space.</P>
<!--Bottom Navigation-->
<A NAME="bottom"></A>
<!--End Bottom Navigation-->
</STRONG>
</FONT>
<!--End Body-->
<!--Bottom-->
<BR>
<IMG SRC="gradbar.jpg">
<BR>
<FONT SIZE=2 COLOR=#8B8B8B FACE=Helvetica>
<I><font color="#FBFBFB">T</font><font color="#F7F7F7">h</font><font color="#F3F3F3">e</font><font color="#EFEFEF"> </font><font color="#EBEBEB">G</font><font color="#E7E7E7">a</font><font color="#E3E3E3">m</font><font color="#DFDFDF">e</font><font color="#DBDBDB"> </font><font color="#D7D7D7">P</font><font color="#D3D3D3">r</font><font color="#CFCFCF">o</font><font color="#CBCBCB">g</font><font color="#C7C7C7">r</font><font color="#C3C3C3">a</font><font color="#BFBFBF">m</font><font color="#BBBBBB">m</font><font color="#B7B7B7">i</font><font color="#B3B3B3">n</font><font color="#AFAFAF">g</font><font color="#ABABAB"> </font><font color="#A7A7A7">M</font><font color="#A3A3A3">e</font><font color="#9F9F9F">g</font><font color="#9B9B9B">a</font><font color="#979797">S</font><font color="#939393">i</font><font color="#8F8F8F">t</font><font color="#8B8B8B">e</font> - ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -