#region Using Statements
using System;
using System.Threading;
using System.Configuration;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
#endregion
namespace Endurance_7
{
public class octNode
{
#region fields
public List<gameObject> objects = new List<gameObject>(); //contains the objects in this node
public List<octNode> nodes = new List<octNode>(); //contains all child nodes
public octNode parent;
private BoundingBox bounds;
private bool isCulled;
public Vector3 center;
public float length;
private VertexPositionColor[] points;
private int[] index;
#endregion
#region initialization
public octNode(Vector3 newCenter, float newLength)
{
center = newCenter;
length = newLength;
load(); //loads bounding lines
}
#endregion
//--------------------------------------------------------------------------------------
//addObjects
//--------------------------------------------------------------------------------------
public void addObject(gameObject newObject)
{
if (nodes.Count != 0)
{
// If we have children, pass the object to them
bool fits = false;
foreach (octNode b in nodes)
{
if (b.contains(newObject.position))
{
b.addObject(newObject);
fits=true;
}
}
if (fits == false)
objects.Add(newObject);
}
else if (objects.Count >= octManager.maxObjectsPerNode)
{
// If no childrem, see if we are already at the max capacity
// and split and redistribute the objects if we are
objects.Add(newObject);
split();
}
else
{
// Otherwise just add the object
objects.Add(newObject);
}
}
//--------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//contains
//--------------------------------------------------------------------------------------
private bool contains(Vector3 checkPoint)
{
return (bounds.Contains(checkPoint) == ContainmentType.Contains);
}
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//distributeObjects
//--------------------------------------------------------------------------------------
private void distributeObjects()
{
foreach (gameObject b in objects)
{
foreach (octNode c in nodes)
{
if (c.contains(b.position))
{
c.addObject(b);
}
}
}
objects.Clear();
}
//--------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//renderNodeLines
//---------------------------------------------------------------------------------------
private void renderNodeLines(GraphicsDevice device)
{
if (nodes.Count == 0)
{
device.VertexDeclaration = octManager.vertexDeclaration;
utility.effect.World = Matrix.Identity;
utility.effect.View = camera.view;
utility.effect.Projection = camera.projection;
utility.effect.DiffuseColor = octManager.lineColor.ToVector3();
utility.effect.Begin();
foreach (EffectPass pass in utility.effect.CurrentTechnique.Passes)
{
pass.Begin();
device.DrawUserIndexedPrimitives<VertexPositionColor>(PrimitiveType.LineList, points, 0, 8, index, 0, 12);
pass.End();
}
utility.effect.End();
octManager.nodesDrawn++;
}
}
//--------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//load loads the vertex lines to display the boundries of the node
//---------------------------------------------------------------------------------------
private void load()
{
float halfLength = length / 2.0f;
points = new VertexPositionColor[8];
points[0] = new VertexPositionColor(center + new Vector3(-halfLength, -halfLength, -halfLength), octManager.lineColor);
points[1] = new VertexPositionColor(center + new Vector3(halfLength, -halfLength, -halfLength), octManager.lineColor);
points[2] = new VertexPositionColor(center + new Vector3(-halfLength, halfLength, -halfLength), octManager.lineColor);
points[3] = new VertexPositionColor(center + new Vector3(halfLength, halfLength, -halfLength), octManager.lineColor);
points[4] = new VertexPositionColor(center + new Vector3(-halfLength, -halfLength, halfLength), octManager.lineColor);
points[5] = new VertexPositionColor(center + new Vector3(halfLength, -halfLength, halfLength), octManager.lineColor);
points[6] = new VertexPositionColor(center + new Vector3(-halfLength, halfLength, halfLength), octManager.lineColor);
points[7] = new VertexPositionColor(center + new Vector3(halfLength, halfLength, halfLength), octManager.lineColor);
int[] inds = {
0, 1, 0, 2, 1, 3, 2, 3,
4, 5, 4, 6, 5, 7, 6, 7,
0, 4, 1, 5, 2, 6, 3, 7
};
index = inds;
Vector3 cornerDistance = new Vector3(halfLength);
bounds = new BoundingBox(center - cornerDistance, center + cornerDistance);
}
//---------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//render
//---------------------------------------------------------------------------------------
public void render(GraphicsDevice device)
{
if (!isCulled)
{
if (octManager.drawOctNodes)
renderNodeLines(device);
// Draw the child objects
foreach (gameObject t in objects)
{
if (!octManager.objectsDrawn.Contains(t.GetHashCode()))
{
t.render(device);
octManager.objectsDrawn.Add(t.GetHashCode());
}
}
// Draw the children down the tree
foreach (octNode t in nodes)
{
t.render(device);
}
}
}
//---------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//split
//--------------------------------------------------------------------------------------
private void split()
{
float offset = length / 4.0f;
for (int x = -1; x <= 1; x += 2)
{
for (int y = -1; y <= 1; y += 2)
{
for (int z = -1; z <= 1; z += 2)
{
octNode newNode = new octNode(
center + new Vector3(x * offset, y * offset, z * offset),
offset * 2.0f
);
newNode.parent = this;
nodes.Add(newNode);
}
}
}
distributeObjects();
}
//---------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//update
//---------------------------------------------------------------------------------------
public void update(float elapsedTime)
{
isCulled = camera.frustum.Contains(bounds) == ContainmentType.Disjoint;
if (objects.Count != 0)
{
for (int i = objects.Count-1; i != -1; i--) //iterating backwards might prevent objects from being skipped.. ?
{
if (!octManager.objectsUpdated.Contains(objects.GetHashCode()))
{
objects.update(elapsedTime);
octManager.objectsUpdated.Add(objects.GetHashCode());
if (objects.hasMoved)
{
if (!contains(objects.position))
{
if (parent != null)
{
parent.addObject(objects);
objects.Remove(objects);
}
else
{
int ii = 0; //the object is outside of the octree! decide what to do later
}
}
}
}
}
}
foreach (octNode b in nodes)
{
b.update(elapsedTime);
}
}
//---------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//makeVisible resets the culling so everything in the node is visible
//---------------------------------------------------------------------------------------
public void makeVisible()
{
isCulled = false;
foreach (octNode n in nodes)
{
n.makeVisible();
}
}
//---------------------------------------------------------------------------------------
}
}
criticize my dynamic octree
Author
After much soul searching, forum reading, and a trip to the bar, I have created a octree that can handle dynamic objects. (note: i did not code this from scratch, I started with a very basic and non-functional octree that from a tutorial, and then heavily modified it)
I'm interested to here your opinions about my solution.
1) all gameObjects include a "hasMoved" bool
2) each node of the octree stores a list of objects that are in the node
3) the octree checks if every object that "hasMoved" is still within the bounds of the node that it is stored in
4) if the object is no longer within the bounds of the node, it is added to the parent node (and removed from the node that it was in)
5) when an object is added to a node, the node first attempts to add it to the child nodes. failing this it checks if the node is already at maximum capacity. if it is the node splits, otherwise the object is added to the node.
Sorry if that was confusing, I guarantee the code is even worse :)
After doing some testing I have determined that having an octree is definitely better than not having an octree. However I haven't tested this design against other designs because it didn't seem like it was worth the trouble (and I'm pretty new to designing these things).
My octree is responsible for handling all objects in the game except for terrain (which I'm currently brute-forcing).
heres the code for an octnode (xna c#)
Hmm, your octree seems to actively try to determine if object has moved, so you have to traverse the whole tree each frame and touch each object even if just to find out that it hasn't moved an inch. Wouldn't it be better to have the octree wait for notification and update only the objects that really moved? No need to access memory you won't use (at that moment).
I would also move culling into the rendering phase for the same reasons (unless you need it for something else). The extra tree traversal in the makeVisible function seems unnecessary to me.
I would also move culling into the rendering phase for the same reasons (unless you need it for something else). The extra tree traversal in the makeVisible function seems unnecessary to me.
Author
hey man,
actually, the octree stores the only instance of the object, and the objects update method is only called through the octree, so the octree updates every object anyways.
I suppose I could store objects in a scene graph that was kept seperate from the octree, but this doesn't seem to offer any noticeable advantages.
actually, the octree stores the only instance of the object, and the objects update method is only called through the octree, so the octree updates every object anyways.
I suppose I could store objects in a scene graph that was kept seperate from the octree, but this doesn't seem to offer any noticeable advantages.
Oh, I missed that.
Scene graph might give you more flexibility, which might be useful later. For example you could have entities that would be disabled and would not need to process the update event. They might get activated in certain time and then become active (eg. when player triggers an event like entering certain area or pushing a button.) Until that, they would be hidden in scene graph hierarchy and not bothered by the program.
Well, that was the first thing that crossed my mind (but it's more scenegraph than octree related :)).
Scene graph might give you more flexibility, which might be useful later. For example you could have entities that would be disabled and would not need to process the update event. They might get activated in certain time and then become active (eg. when player triggers an event like entering certain area or pushing a button.) Until that, they would be hidden in scene graph hierarchy and not bothered by the program.
Well, that was the first thing that crossed my mind (but it's more scenegraph than octree related :)).
Why are you storing game objects based on their position, rather than on their volume? Some objects may be so large that they span across multiple nodes, and these shouldn't be culled just because their center lies within a culled node.
Also, why are you mixing rendering and updating with a spatial structure? Octrees aren't only usefull for rendering, but also for collision detection and other cases where spatial optimization is beneficial. Mixing up these responsibilities may work for now, but can get confusing later on. You don't want your octree to break all of a sudden because you changed your rendering system...
moribundus makes a good point: event-driven updates are more efficient here than polling objects for movement.
Oh, and if an object can be inserted into a child node, you can simply return. There's no need for the 'fits' boolean: if the object didn't fit in any of the child nodes, you add it to the current node, otherwise, the function returns immediatly after adding it to a child node has succeeded.
And one last note: there's no functionality for removing game objects from the octree.
Also, why are you mixing rendering and updating with a spatial structure? Octrees aren't only usefull for rendering, but also for collision detection and other cases where spatial optimization is beneficial. Mixing up these responsibilities may work for now, but can get confusing later on. You don't want your octree to break all of a sudden because you changed your rendering system...
moribundus makes a good point: event-driven updates are more efficient here than polling objects for movement.
Oh, and if an object can be inserted into a child node, you can simply return. There's no need for the 'fits' boolean: if the object didn't fit in any of the child nodes, you add it to the current node, otherwise, the function returns immediatly after adding it to a child node has succeeded.
And one last note: there's no functionality for removing game objects from the octree.
Author
Quote:I would also move culling into the rendering phase for the same reasons (unless you need it for something else). The extra tree traversal in the makeVisible function seems unnecessary to me.
whoops I missed this the first time around! The makeVisible function is only used in a special development mode that I made. The mode pauses all updates, and converts the camera into a free camera. In this mode the octree is disabled completely to remove it as a variable from whatever problem I'm trying to look at. Basically the makeVisible function disables the octree by making all of the nodes visible regardless of culling. Since the octree is not updated in this mode, all of the objects in the octree will be rendered until I switch out of the mode. The octree is operated by updating the first node that was created, which then updates all of it's child nodes.
Quote:Why are you storing game objects based on their position, rather than on their volume? Some objects may be so large that they span across multiple nodes, and these shouldn't be culled just because their center lies within a culled node.
yup this is a good point. I was using position because I hadn't worked much with xna's bounding classes yet. This functionality shouldn't be to difficult to add when I get around to researching it.
Quote:
Also, why are you mixing rendering and updating with a spatial structure? Octrees aren't only usefull for rendering, but also for collision detection and other cases where spatial optimization is beneficial. Mixing up these responsibilities may work for now, but can get confusing later on. You don't want your octree to break all of a sudden because you changed your rendering system...
hmmm I guess I'm still not getting this argument. The game objects have to be stored in a list somewhere, and I don't get why I would want to have a seperate list and then have to mess with adding pointers of every object to the octree. The octree seems like the logical place to store the gameObjects to me. I guess I also don't understand why it's a problem to have the octree handle the render and update calls. If the octree decides what gets rendered, why wouldn't it handle the render calls?
To clarify, the actual rendering code resides in a animation class that inherits from gameObject. Octree just calls the render method in the abstract class "gameObject", which is overridden by the animation class. With this method I can have as many different rendering styles as I want, I just need to make a new animation class for each one.
Quote:moribundus makes a good point: event-driven updates are more efficient here than polling objects for movement.
but if I'm already iterating through the list to call every objects update method, the overhead should be exactly the same as if this code was in each objects update method instead of being in the octree.
Since my physics isn't event driven, and is calculated every frame (gravity has to be applied among other things) there really aren't movement events, and "hasMoved" is a simple comparison of an object's current position with it's previous position.
Quote:Oh, and if an object can be inserted into a child node, you can simply return. There's no need for the 'fits' boolean: if the object didn't fit in any of the child nodes, you add it to the current node, otherwise, the function returns immediatly after adding it to a child node has succeeded.
ah good point. I never really thought of that. In some areas I'm really quite new to C#. I learned it from a game programming perspective, and ended up missing a lot of little things like that.
Quote:And one last note: there's no functionality for removing game objects from the octree.
ahh heheh I completely forgot about that. the base gameObject has a "active" bool. I guess I will just test for and remove inactive objects during the update for each node. This is a another example of where it just seems easier to let the octree handle updating.
thanks for all the insight guys
edit: I'll read up on scene graphs. It sounds like I'm trying to make this more simple than it should be. But this being only my second major game attempt with xna, maybe I should't get in too deep with the engine framework. I've still gotta do something with the terrain too
[Edited by - nordwindranger on January 15, 2008 10:00:38 PM]
Quote:Original post by nordwindranger
I guess I also don't understand why it's a problem to have the octree handle the render and update calls.
Single Responsibility Principle. Rendering and collision detection are two different things, and they can have very different requirements. Separating them into two different classes will make the classes easier to maintain and extend (you won't have to worry about breaking you collision detection code when you update your rendering system).
Also, storing the objects in two different places can make sense sometimes. Collision detection and rendering have different requirements, and it's sometimes advantageous to have two different spatial structures for each system (because the partitioning criteria in each case might be different). The data these structures store can also be very different. For example, the rendering system will just need a simple bounding box to quickly cull an object, while the collision detection system might need a bounding volume hierarchy to work accurately and efficiently.
For a simple game, you might think it's less important to make this separation, but you should get in the habit of using the SRP whenever you can. It's one of the most important principles to understand, and fortunately one of the easier ones to apply. I strongly recommend that you read the linked article.
Author
that was a very clear and concise article. thanks!
I will seriously consider decoupling rendering and updating from the octree.
I will seriously consider decoupling rendering and updating from the octree.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
