📄 octree.htm
字号:
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
</head>
<body text="#FFFFFF" bgcolor="#000000">
<p align="center"><font size="7" color="#FFFF00"><img border="0" src="images/title.jpg" width="636" height="66"></font></p>
<p align="center"> </p>
<p align="left"><br>
<b><font size="5" color="#FFFF00"><img border="0" src="images/OctreeDefinitionTitle.jpg" width="320" height="32"></font></b></p>
<p align="left">An <b>octree</b> is a way of subdividing 3D space, otherwise
known as <b>space partitioning</b>. It allows you to only draw the part of
your world/level/scene that is in your frustum (camera's view). It can
also be used for collision detection. Let me give you an example of why
space partition is necessary. Assume you created a world for your game and
it has over 100, 000 polygons to draw. If you did a loop and passed in
every one of those polygons, on top of your characters polygons per frame your
frame rate would come to a crawl. If you have a nice Geforce card it might
not be as horrible, but you just restricted anyone from viewing your game that
doesn't have a $300+ graphics card. Sometimes, even though you have a
really nice graphics card, the part that slows it down a considerable amount is
the loop that you use to pass in that data. Wouldn't it be great if there
was a way to only render the polygons that the camera was looking at? This
is the beauty of an octree. It allows you to quickly find the polygons
that you are in your view and only draw them.</p>
<p align="left"><br>
<br>
<b><font size="5" color="#FFFF00"><img border="0" src="images/HowOctreeWorksTitle.jpg" width="318" height="31"></font></b></p>
<p align="left">An octree works in <b>cubes</b>. Initially, the octree
starts with a root node that has an axis aligned cube surrounding the entire world, level or
scene. So, imagine an invisible cube around your whole world (<font color="#FFFF00"><b>Figure
1.1</b></font>). </p>
<p align="center"><img border="0" src="images/RootNode.jpg" width="320" height="200"><font color="#FFFF00"><b>Figure
1.1</b></font></p>
<p align="left"><br>
So this root node now stores all the vertices in the world. Currently,
this wouldn't do us much good because it will draw the whole thing. We
want to subdivide this node into 8 parts (hence the word <b>oct</b>ree).
Once we subdivide there should be 8 cubes inside of the original root node's
cube. That means 4 cubes on top and 4 on the bottom. Take a look at
<font color="#FFFF00"><b>Figure 1.2</b></font>. Keep in mind the yellow
lines outlining each node would not be there. The lines were added in to
get a visual idea of what is going on.</p>
<p align="center"><img border="0" src="images/SubdividedNode.jpg" width="320" height="200"><font color="#FFFF00"><b>Figure
1.2</b></font></p>
<p align="left">We have just divided the world into 8 parts with just 1
subdivision. Can you imagine how effective this would be if we had 2, 3 or
4 subdivisions? Well, now what? We subdivided the world, but what do
we do with this? Where does the speed come from that I mentioned?
Let's say that the camera is in the middle of the world looking towards the back
right corner (<font color="#FFFF00"><b>Figure 1.3</b></font>). If you look
at the lines you will notice that we are only looking at 4 of the 8 nodes in the
octree. These nodes include the 2 back top and bottom nodes. This
means we would only need to draw the vertices stored in those nodes. <br>
</p>
<p align="center"><img border="0" src="images/PartialVisibility.jpg" width="320" height="200"><font color="#FFFF00"><b>Figure
1.3</b></font></p>
<p align="left"><br>
How do we do check which nodes are in our view? This is pretty easy if you
have frustum culling. You can get the dimensions of your frustum and then
check each cube if it intersects or is inside of your viewing frustum.
There is a frustum culling tutorial at <a href="http://www.GameTutorials.com">
www.GameTutorials.com</a> for more reference. If a cube intersects the
frustum, we then draw the vertices that are assigned to that node.
Basically, in the example above we just cut the amount we need to draw down by
50 %. Remember, this was just <b>1</b> subdivision of our world. The
more subdivisions the more accuracy we will achieve (to a point). Of
course we don't want too many nodes because it could slow us down a bit with all
that recursion. Is this starting to make sense? Let's subdivide yet
another level. Take a look at <font color="#FFFF00"><b>Figure 1.4</b></font>.</p>
<p align="center"><img border="0" src="images/SubdividedNode2.jpg" width="320" height="200"><font color="#FFFF00"><b>Figure
1.4</b></font></p>
<p align="left">You'll notice something different about <b>
<font color="#FFFF00">Figure 1.4</font> </b>from the last subdivision.
This level of subdivision didn't create 8 cubes inside of each of the original 8
cubes. The top and bottom parts of the original 8 nodes aren't subdivided.
This is where we get into the nitty gritties of the octree creation process.
You always try to subdivide a node into 8 more nodes, but if there are no
triangles stored in that area, we disregard that node and don't allocate any
memory for it. The further we subdivide, the more the nodes shape the
original world. If we went down another level of subdivision the cubes
would form a closer resemblance to the scene. To further demonstrate this,
let's take a look at <font color="#FFFF00"><b>Figure 1.5</b></font>. There
are 2 spheres in the scene, but on completely opposite sides. Notice that
in the first subdivision (Left) it splits the world into only 2 nodes, not 8.
This is because the spheres only reside in 2 of the nodes. If we subdivide
2 more times (Right) it more closely forms over the spheres. This shows
that nodes are only created where they need to be. A node will <b>not</b>
be created if there is no triangles occupying it's space.<br>
</p>
<p align="center"><b>
<font color="#FFFF00"><img border="0" src="images/SpheresSub1.jpg" width="304" height="304">
<img border="0" src="images/SpheresSub3.jpg" width="304" height="304">Figure 1.5</font></b></p>
<p align="left"><br>
<b><font size="5" color="#FFFF00"><br>
<img border="0" src="images/StopSubdividingTitle.jpg" width="319" height="27"></font></b></p>
<p align="left">Now that we understand how the subdivision works, we need to
know how to stop it so it doesn't recurse forever. There are a few ways
which we can do this. 1) We could stop subdividing the current node if it
has a triangle count that is less than a max triangle count that we define.
Say for instance, we chose 100 for the max. That means that before we
subdivide the node, it will check to see if the total amount of triangles it has
contained in it's area is less than or equal to the max triangle count that we
decided. If it is less than or equal to the max, then we stop subdividing
and assign all those triangles to that node. Note that we never assign any
triangles to a node unless it's the end node. If we subdivide a node we do
not store the triangles in that node, but in it's children node, or their
children's nodes, or even their children, etc... This will make more sense
when we go over how we draw the octree. 2) Another way to check if we want
to stop subdividing is if we subdivide past a certain level of subdivision.
We could create a max subdivision level like 10, and if we recurse above that
number then we stop and assign the vertices in the cube's area to that node.
When I saw "above that number" I mean 11 levels of subdivision. 3) The
last check we can perform is if the nodes exceed a max node variable.
Let's say we set this constant variable to 500. Every time we create a
node we increment the current nodes created variable, then before we create
another node we check if our current node count is less than or equal to the max
node count. If we get to 501 nodes in our octree then we should not
subdivide that node, but assign it's current vertices to it. I personally
use the 1st and 3rd method, but it's a good idea to start with the 1st and 2cnd
method so you can test the different levels of subdivision visually and
manually. </p>
<p align="left"><br>
<b><font size="5" color="#FFFF00"><img border="0" src="images/DrawTheOctreeTitle.jpg" width="324" height="27"></font></b></p>
<p align="left">Once the octree is created we can then draw the nodes which are
in our view. The cubes don't have to be all the way inside our view, just a little
bit. That is why we want to make our triangle count in each node somewhat
small so if we have a little corner of a node in our frustum it won't draw
thousands of triangles. To draw the octree we start at the root node.
We have a center point stored for each node and a width. This is perfect
to pass into a function like so:</p>
<p align="left"><b><font color="#00FF00">// This function takes the center point
of the cube (x, y, z) and it's size (width / 2)</font><font color="#FFFF00"><br>
bool CubeInFrustum( float x, float y, float z, float size );</font></b></p>
<p align="left">This will return a <b><font color="#0000FF">true</font></b> or
<b><font color="#0000FF">false</font></b>, depending on if the cube is in the
frustum (Once again refer to the frustum tutorial at
<a href="http://www.GameTutorials.com">www.GameTutorials.com</a> for frustum
source code). If the cube is in the frustum them we check all of it's
nodes to see if they are in the frustum, otherwise we ignore that whole branch
in the tree. Once we get to a node that is in the frustum but does not
have any nodes under it, we want to draw the vertices stored in that end node.
Remember, only the end nodes have vertices stored in them. Take a look at
<b><font color="#FFFF00">Figure 1.6</font></b> to see an example run through of
the octree. The nodes that are shaded are the ones that were in the
frustum. The white cubes are the ones that are not in the frustum.
This just shows the hierarchy of 2 levels of subdivision.</p>
<p align="center"><br>
<b><font color="#FFFF00"><img border="0" src="images/OctreeNodeHeirarchy.jpg" width="320" height="200">Figure
1.6</font></b></p>
<p align="center"> </p>
<p align="left"><b><font size="5" color="#FFFF00"><img border="0" src="images/CollisionTitle.jpg" width="324" height="24"></font></b></p>
<p align="left">An octree isn't just for rendering, but can be used for
collision detection as well. Since collision detection varies from game to
game, you will want to pick your own algorithm for checking if your character or
object collided with the world. Here are a few examples on how you could
check for this: 1) You will want to create a function that allows you to
pass in a point in 3D space to your octree and return the vertices that are
found around that point. The point that you would pass in could be the
center point of your character or object. This alone might work some
times, but what if the point is right near the edge of one of the nodes?
Your character or object could be colliding with vertices that are in another
node. To solve this problem you could do a couple things. You could
pass in either a radius or bounding box of the character/object and then check
if that radius or bounding box (easier with a cube) collides with another of the
surrounding nodes. This would all depend on the shape of your
character/object that you are testing. The following are some function
prototypes for these ideas:</p>
<p align="left"><b><font color="#00FF00">// This function takes the center point
of the character/object (x, y, z) and returns the vertices near it<br>
</font><font color="#FFFF00">CVector3 *GetVerticesFromPoint( float x, float y,
float z );</font></b></p>
<p align="left"><b><font color="#00FF00">// This function takes the center point
of the character/object (x, y, z) and radius, then returns the vertices in the
nodes that collide with it<br>
</font><font color="#FFFF00">CVector3 *GetVerticesFromPointAndRadius( float x,
float y, float z, float radius );</font></b></p>
<p align="left"><b><font color="#00FF00">// This function takes the center point
of the character/object (x, y, z) and cube size, then returns the vertices in
the nodes that collide with it<br>
</font><font color="#FFFF00">CVector3 *GetVerticesFromPointAndCube( float x,
float y, float z, float size );</font></b></p>
<p align="left"><br>
I am sure you can think of more optimal ways to speed these checks up, but this
should get you started on the basics. Once you get the vertices that are
in that area of your character/object you can do your more intense
calculations. Once again, when it comes to collision it's totally how your
game works.</p>
<p align="left"><br>
<b><font size="5" color="#FFFF00"><img border="0" src="images/ConclusionTitle.jpg" width="162" height="30"></font></b></p>
<p align="left">This tutorial should give you enough information to get started
creating your own octree. There is also a code tutorial that is associated
with this document. If it is not you can find it at <a href="http://www.GameTutorials.com">www.GameTutorials.com</a>.
I hope this helps someone struggling with these advanced concepts. Good
luck!</p>
<p align="left"><br>
Ben Humphrey (DigiBen)<br>
Game <a href="mailto:ProgrammerDigiBen@GameTutorials.com">Programmer<br>
DigiBen@GameTutorials.com<br>
</a>Co-Web Host of www.GameTutorials.com</p>
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -