C:/Doug/CSharp/XnaCollisionLib/XnaCollisionLib/OctTree.cs

Go to the documentation of this file.

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace XnaCollisionLib
{
    public class OctTree
    {
        private List<Triangle> _Triangles;
        private OctTree[] _Children;
        private BoundingBox _Box;
        private int _Count;

        private OctTree()
        {
            _Triangles = new List<Triangle>();
            _Children = new OctTree[8];
            for (int i = 0; i != _Children.Length; i++)
                _Children[i] = null;
            _Box = new BoundingBox();
            _Count = 0;
        }

        private int CountTriangles()
        {
            int count = _Triangles.Count;

            foreach (OctTree node in _Children)
                if (node != null)
                    count += node.CountTriangles();
            return count;
        }

        public int Count
        {
            get { return _Count; }
        }

        public Nullable<float> ISect(Ray ray, ref float nearestDistance, ref Triangle nearestTriangle)
        {
            Nullable<float> t = ray.Intersects(_Box);

            if (t.HasValue && t.Value >= 0 && t.Value < nearestDistance)
            {
                t = null;

                foreach (Triangle triangle in _Triangles)
                {
                    Nullable<float> t2 = triangle.ISect(ray);

                    if (t2.HasValue && t2.Value >= 0 && t2.Value < nearestDistance)
                    {
                        nearestDistance = t2.Value;
                        nearestTriangle = triangle;
                        t = t2;
                    }
                }
                foreach (OctTree node in _Children)
                    if (node != null)
                    {
                        Nullable<float> t2 = node.ISect(ray, ref nearestDistance, ref nearestTriangle);

                        if (t2.HasValue)
                            t = t2;
                    }
            }
            return t;
        }

        public void Query(BoundingBox box, List<Triangle> triangles, Matrix transform)
        {
            if (_Box.Contains(box) == ContainmentType.Disjoint)
                return;

            foreach (Triangle triangle in _Triangles)
                triangles.Add(new Triangle(triangle, transform));
            foreach (OctTree node in _Children)
                if (node != null)
                    node.Query(box, triangles, transform);
        }

        public static OctTree Create(IEnumerable<Triangle> triangles, int minTrianglesPerNode)
        {
            OctTree node = new OctTree();

            node._Triangles.AddRange(triangles);
            Create(node, minTrianglesPerNode);
            node._Count = node.CountTriangles();

            return node;
        }

        private static void Create(OctTree node, int minTrianglesPerNode)
        {
            node._Box.Min = node._Box.Max = node._Triangles[0].A;
            for (int i = 0; i != node._Triangles.Count; i++)
            {
                CollisionHelper.AddToBox(ref node._Box, node._Triangles[i].A);
                CollisionHelper.AddToBox(ref node._Box, node._Triangles[i].B);
                CollisionHelper.AddToBox(ref node._Box, node._Triangles[i].C);
            }
            if (node._Triangles.Count < minTrianglesPerNode)
                return;

            Vector3 center = (node._Box.Max + node._Box.Min) / 2;
            Vector3[] corners = node._Box.GetCorners();
            List<Triangle> keepTriangles = new List<Triangle>();

            for (int i = 0; i != 8; i++)
            {
                node._Children[i] = new OctTree();
                node._Children[i]._Box.Min = node._Children[i]._Box.Max = center;
                CollisionHelper.AddToBox(ref node._Children[i]._Box, corners[i]);
                for (int j = 0; j != node._Triangles.Count; j++)
                    if (node._Children[i]._Box.Contains(node._Triangles[j].A) != ContainmentType.Disjoint &&
                        node._Children[i]._Box.Contains(node._Triangles[j].B) != ContainmentType.Disjoint &&
                        node._Children[i]._Box.Contains(node._Triangles[j].C) != ContainmentType.Disjoint)
                        node._Children[i]._Triangles.Add(node._Triangles[j]);
                    else
                        keepTriangles.Add(node._Triangles[j]);
                node._Triangles = new List<Triangle>(keepTriangles);
                keepTriangles.Clear();
                if (node._Children[i]._Triangles.Count == 0)
                    node._Children[i] = null;
                else
                    Create(node._Children[i], minTrianglesPerNode);
            }
        }
    }
}