📄 engine03.shtml
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE>Dan's Tutorials: 03 - Binary Space Partitioning</TITLE>
<LINK REL="stylesheet" HREF="tutorial_styles.css">
</HEAD>
<BODY BGCOLOR="white">
<a name="top"></a>
<BR>
<CENTER>
<!--
<br>
<DIV CLASS="main1">DAN'S</div><div class="main2">Programming Tutorials</DIV>
<br>
<TABLE WIDTH="700" BORDER="0" CELLPADDING="5" CELLSPACING="0">
<TR><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
[</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<A HREF="index.shtml">news</A></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
tutorials</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<!--A HREF="Files.shtml"--><!--files</a></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<a href="ResourcesWeb.shtml">links</a></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<A HREF="Contact.shtml">contact</A></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
]</B></FONT>
</TD></TR>
</TABLE>
-->
<BR>
<TABLE WIDTH="700" BORDER="0" CELLSPACING="0" CELLPADDING="0" ALIGN="CENTER" VALIGN="TOP">
<TR>
<TD VALIGN="top" ALIGN="left" WIDTH="200">
<TABLE WIDTH="200" BORDER="1" CELLPADDING="3" CELLSPACING="0">
<TR><TD BGCOLOR="silver" ALIGN="center">
<FONT FACE="arial" COLOR="black"><B>Table of Contents</B></FONT>
</TD></TR>
</TABLE>
<TABLE WIDTH="200" BORDER="0" CELLPADDING="3" CELLSPACING="0"><TR><TD>
<FONT FACE="arial" SIZE="-1">
<BR>
<CENTER><B>3D</B></CENTER>
Creating a cutting-edge engine<BR>
<A HREF="Engine01.shtml">01 - Design document</A><BR>
<A HREF="Engine02.shtml">02 - Overall structure</A><BR>
<BR>
<A HREF="Engine03.shtml">03 - Binary Space Partitioning</A><BR>
<A HREF="Engine04.shtml">04 - Constrctive Solid Geometry</A><BR>
<A HREF="Engine05.shtml">05 - Portals</A><BR>
<A HREF="Engine06.shtml">06 - Possible Visible Set</A><BR>
<A HREF="Engine07.shtml">07 - Radiosity lighting</A><BR>
<!--A HREF="Engine08.shtml"-->08 - Mirrors</A><BR>
<BR>
<!--A HREF="Dictionary.shtml"-->Dictionary of 3D terms</A><BR>
<BR>
<CENTER><B>OTHER</B></CENTER>
<!--A HREF="GeneticAlgorithm.shtml"-->A Genetic Algorithm</A><BR>
<A HREF="Line01.shtml">Line drawing</a><BR>
<!--A HREF="Line02.shtml"-->Line clipping</a><BR>
<!--A HREF="Line03.shtml"-->Line antialiasing</a><BR>
<!--A HREF="Line04.shtml"-->Line thickening</a><BR>
<!--A HREF="Line05.shtml"-->Line curving</a><BR>
<br>
<A HREF="ResourcesPrint.shtml">Resources in print</A><BR>
<A HREF="ResourcesWeb.shtml">Resources on the web</A><BR>
<!--A HREF="ResourcesFiles.shtml"-->Resources to download</A><BR>
<BR>
</FONT>
</TD></TR></TABLE>
<TABLE WIDTH="200" BORDER="0" CELLPADDING="0" CELLSPACING="0">
<TR><TD HEIGHT="290"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">
zViewer: The greatest thing since sliced bread. Except butter.</FONT></TD></TR>
<TR><TD HEIGHT="75"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">1:
<A HREF="Resources.shtml#CGPAP">Computer Graphics: Principles & Practice</A></FONT></TD></TR>
<TR><TD HEIGHT="360"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">
Time to build a BSP tree: 0(n<SUP>2</SUP>)<BR><BR>
Time to walk a BSP tree: 0(n)</FONT></TD></TR>
<TR><TD HEIGHT="420"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">Leaf node:
the last node on each branch of a BSP tree.</FONT></TD></TR>
<TR><TD HEIGHT="90"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">Method:<BR>
<FONT COLOR="blue">void</FONT> MyMethod() {<BR>
...<BR>
}<BR>
<BR>
Function:<BR>
A<SUB>1</SUB>x<SUP>1</SUP> + A<SUB>2</SUB>x<SUP>2</SUP> + ... + A<SUB>n</SUB>x<SUP>n</SUP> = 0<br>
<br>
Get it straight, people.</FONT></TD></TR>
<TR><TD HEIGHT="260"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">Get back, funky cat.<br>
<img src="eltonj.jpg" width="100" height="156" alt="Crocodile Rock" border="0"></FONT></TD></TR>
<TR><TD HEIGHT="700"></TD></TR>
<TR><TD><img src="popup.jpg" width=100 height=125 alt="Is it just me?" border="0"></TD></TR>
</TABLE>
</TD>
<TD VALIGN="top" ALIGN="right" WIDTH="500">
<TABLE WIDTH="475" BORDER="0" CELLPADDING="3" CELLSPACING="0">
<TR><TD BGCOLOR="silver">
<FONT FACE="arial"><B>03 - Binary Space Partitioning</B></FONT>
</TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-1">
One of the largest problems when rendering large polygon sets has to do with the order in which the
polygons are supposed to be drawn. What I mean is that you have to have a really fast way of sorting
the polygons so that you can draw the polygons closest to the camera on top of the polygons that are
further back. Better still would be to have <I>zero overdraw</I>, by that I mean you wouldn't draw
over anything and every pixel would be touched just once.<BR>
<BR>
<p align="center">
<IMG SRC="0301.jpg" WIDTH="200" HEIGHT="150" ALT="top view" BORDER="0">
<IMG SRC="0302.jpg" WIDTH="200" HEIGHT="150" ALT="camera view" BORDER="0">
</p>
<BR>
There are a number of different ways of going about polygon sorting. Some of simplest include
the Painter's algorithm and Z-buffering. Portals are (among other things) another very handy way to
ensure front to back zero overdraw but we'll discuss those later.<BR>
<BR>
Binary Space Partitioning trees (BSPs) are very good at a number of things.<BR>
<UL>
<LI><B>Z-sorting polygons</B> so that they draw in the right order.
<LI><B>Collision detection</B> against BSP planes is very quick and easy. It's just as easy to
determine if you are inside our outside of a model represented by BSP.
<LI><B>Fast rendering</B> can be quickly accomplished because the BSP is built ahead of time. For those
of you mathematically inclined, the total time to walk the tree is O(n) while the time to build the
tree is O(n<SUP>2</SUP>).
<LI><B>Node clipping</B> is another precalculated BSP trick to improve rendering speed.
<LI><B>The Possible Visible Set</B> can be calculated with the BSP tree to reduce rendering time even
further.
</UL>
If that isn't enough to convince you of the advantages, then maybe this is:
<TABLE BORDER="0">
<TR><TD><FONT FACE="arial" SIZE="-1">
<UL>
<LI><A HREF="http://www.idsoftware.com">Doom</A>
<LI><A HREF="http://www.idsoftware.com">Doom II</A>
<LI><A HREF="http://www.idsoftware.com">Quake</A>
<LI><A HREF="http://www.idsoftware.com">Quake II</A>
<LI><A HREF="http://www.quake3arena.com">Quake III: Arena</A>
</UL></FONT>
</TD><TD><FONT FACE="arial" SIZE="-1">
<UL>
<LI><A HREF="http://www.unreal.com">Unreal</A>
<LI><A HREF="http://www.sin.com">Sin</A>
<LI><A HREF="http://www.shogo.com">Shogo</A>
<LI><A HREF="http://www.valvesoftware.com/halflife">Half-Life</A>
<LI><A HREF="../zeditor">zViewer</A>
</UL></FONT>
</TD></TR>
</TABLE>
All of these programs use BSPs. "So how," you're asking yourself, "do I jump on the BSP bandwagon?"
Easier said than done.<BR>
<BR>
First of all, here's how they work: BSPs "recursively divide space into pairs of sub spaces, each
separated by a plane of arbitrary orientation and position."<SUP>1</SUP> It's easier to visualize.
Let's say we're given an arbitrary set of polygons. We'll use the planes of the polygons to cut the
world in half, or as close to half as we can find. The first step would look like this:<BR>
<BR>
<p align="center">
<IMG SRC="0303.jpg" WIDTH="200" HEIGHT="150" ALT="the first division" BORDER="0">
<IMG SRC="0304.jpg" WIDTH="200" HEIGHT="150" ALT="the start of the tree" BORDER="0">
</p><BR>
Recurse on both sides until there are no polygons left.<BR>
<BR>
<p align="center">
<IMG SRC="0305.jpg" WIDTH="200" HEIGHT="150" ALT="a node-based world" BORDER="0">
<IMG SRC="0306.jpg" WIDTH="200" HEIGHT="150" ALT="a node-based tree" BORDER="0">
</p><BR>
This is what is referred to as <I>node-based</I> because the polygons are on the nodes. The other type
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -