C#实现八叉树算法
八叉树介绍:
octree是一种用于描述三位空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，
每个节点有八个子节点，将八个子节点所表示的体积元素加在一起就等于父节点的体积。
#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[i].GetHashCode()))
{
objects[i].update(elapsedTime);
octManager.objectsUpdated.Add(objects[i].GetHashCode());
if (objects[i].hasMoved)
{
if (!contains(objects[i].position))
{
if (parent != null)
{
parent.addObject(objects[i]);
objects.Remove(objects[i]);
}
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();
}
}
//---------------------------------------------------------------------------------------
}
}
抓抓熊熊小挠挠 -
共有0个回答