Dynamic Octree in XNA


This post will show an implementation of a dynamic octree called loose octree.

Most people use different approaches for dynamics and statics objects when building spatial acceleration algorithms. This one can be used for both scenarios with reasonable speed.

This algorithm is used in our game engine PloobsEngine to perform frustrum culling. People can use it to acelerate world queries (search for objects within a radius ..), for physics ….

The implementation idea was a bit “stollen” from the book Game Gems series (book 4 i think, dont remember exactely) and was a bit of my inspirations =P

The code is in XNA 4.0 and PloobsEngine (some debug drawn routines to see thinks working, it is very easy to replace this part of the code).

The bad thing about this technic is that we need to create the “full expanded octree” in the beggining, the good thing is that the common operations like add, delete, query for objects in a given range, update and draw are very fast.

This implementation id basically changing memory for speed if we campare with the classic octree implementation.

The following implementation has methods for adding, removing and drawing (retrieve objects that are inside of the passed region). The code is simple, the idea is powerfull =P

The usage is pretty simple, just add and remove objects using the add/remove functions =P, for those that are not static, every frame use the “isInside” function and if it is not, remove and add the corresponding objects.

One of the keys to have a good performance with loose octree is right tunning the octree parameters. Try changing and experimenting with the looseness, world size and depth of the octree =P. To start try depth = 5  and looseness = 1.5f =P !!!

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using System;
using System.Collections.Generic;
using PloobsEngine.Features.DebugDraw;

namespace PloobsEngine.SceneControl
{
    /// 
    /// Represents an octree spatial partioning system.
    /// 
    public class Octree
    {
        /// 
        /// The number of children in an octree.
        /// 
        private const int ChildCount = 8;

        /// 
        /// The octree's looseness value.
        /// 
        private float looseness = 0;

        /// 
        /// The octree's depth.
        /// 
        private int depth = 0;

        private static DebugShapesDrawer debugDraw = null;

        /// 
        /// Gets or sets the debug draw.
        /// 
        /// 
        /// The debug draw.
        /// 
        public DebugShapesDrawer DebugDraw
        {
            get { return debugDraw; }
            set { debugDraw = value; }
        }

        /// 
        /// The octree's center coordinates.
        /// 
        private Vector3 center = Vector3.Zero;

        /// 
        /// The octree's length.
        /// 
        private float length = 0f;

        /// 
        /// The bounding box that represents the octree.
        /// 
        private BoundingBox bounds = default(BoundingBox);

        /// 
        /// The objects in the octree.
        /// 
        private List objects = new List();

        /// 
        /// The octree's child nodes.
        /// 
        private Octree[] children = null;

        /// 
        /// The octree's world size.
        /// 
        private float worldSize = 0f;

        /// 
        /// Creates a new octree.
        ///     
        /// The octree's world size.
        /// The octree's looseness value.
        /// The octree recursion depth.
        public Octree(float worldSize, float looseness, int depth)
            : this(worldSize, looseness, depth, 0, Vector3.Zero)
        {
        }

        public Octree(float worldSize, float looseness, int depth, Vector3 center)
            : this(worldSize, looseness, depth, 0, center)
        {
        }

        /// 
        /// Creates a new octree.
        ///     
        /// The octree's world size.
        /// The octree's looseness value.
        /// The maximum depth to recurse to.
        /// The octree recursion depth.
        /// The octree's center coordinates.
        private Octree(float worldSize, float looseness,
            int maxDepth, int depth, Vector3 center)
        {
            this.worldSize = worldSize;
            this.looseness = looseness;
            this.depth = depth;
            this.center = center;
            this.length = this.looseness * this.worldSize / (float)Math.Pow(2, this.depth);
            float radius = this.length / 2f;

            // Create the bounding box.
            Vector3 min = this.center + new Vector3(-radius);
            Vector3 max = this.center + new Vector3(radius);
            this.bounds = new BoundingBox(min, max);

            // Split the octree if the depth hasn't been reached.
            if (this.depth < maxDepth)
            {
                this.Split(maxDepth);
            }
        }

        /// 
        /// Removes the specified obj.
        /// 
        /// The obj.
        public void Remove(T obj)
        {
            objects.Remove(obj);
        }

        /// 
        /// Determines whether the specified obj has changed.
        /// 
        /// The obj.
        /// The transformebbox.
        /// 
        ///   true if the specified obj has changed; otherwise, false.
        /// 
        public bool HasChanged(T obj, BoundingBox transformebbox)
        {
            return this.bounds.Contains(transformebbox) == ContainmentType.Contains;
        }

        /// 
        /// Stills inside ?
        /// 
        /// The o.
        /// The center.
        /// The radius.
        /// 
        public bool StillInside(T o, Vector3 center, float radius)
        {
            Vector3 min = center - new Vector3(radius);
            Vector3 max = center + new Vector3(radius);
            BoundingBox bounds = new BoundingBox(min, max);

            if (this.children != null)
                return false;

            if (this.bounds.Contains(bounds) == ContainmentType.Contains)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        /// 
        /// Stills inside ?.
        /// 
        /// The obj.
        /// Its bounds.
        /// 
        public bool StillInside(T o, BoundingBox bounds)
        {
            if (this.children != null)
                return false;

            if (this.bounds.Contains(bounds) == ContainmentType.Contains)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        /// 
        /// Adds the given object to the octree.
        /// 
        /// The object to add.
        /// The object's center coordinates.
        /// The object's radius.
        public Octree Add(T o, Vector3 center, float radius)
        {
            Vector3 min = center - new Vector3(radius);
            Vector3 max = center + new Vector3(radius);
            BoundingBox bounds = new BoundingBox(min, max);

            if (this.bounds.Contains(bounds) == ContainmentType.Contains)
            {
                return this.Add(o, bounds, center, radius);
            }
            return null;
        }


        /// 
        /// Adds the given object to the octree.
        ///     
        public Octree Add(T o, BoundingBox transformebbox)
        {
            float radius = (transformebbox.Max - transformebbox.Min).Length() / 2;
            Vector3 center = (transformebbox.Max + transformebbox.Min) / 2;

            if (this.bounds.Contains(transformebbox) == ContainmentType.Contains)
            {
                return this.Add(o, transformebbox, center, radius);
            }
            return null;
        }


        /// 
        /// Adds the given object to the octree.
        /// 
        /// The object to add.
        /// The object's bounds.
        /// The object's center coordinates.
        /// The object's radius.
        private Octree Add(T o, BoundingBox bounds, Vector3 center, float radius)
        {
            if (this.children != null)
            {
                // Find which child the object is closest to based on where the
                // object's center is located in relation to the octree's center.
                int index = (center.X <= this.center.X ? 0 : 1) +
                    (center.Y >= this.center.Y ? 0 : 4) +
                    (center.Z <= this.center.Z ? 0 : 2);

                // Add the object to the child if it is fully contained within
                // it.
                if (this.children[index].bounds.Contains(bounds) == ContainmentType.Contains)
                {
                    return this.children[index].Add(o, bounds, center, radius);

                }
            }
            this.objects.Add(o);
            return this;
        }

        /// 
        /// Draws the octree.
        /// 
        /// The viewing matrix.
        /// The projection matrix.
        /// The objects in the octree.
        /// The number of octrees drawn.
        public int Draw(Matrix view, Matrix projection, List objects)
        {
            BoundingFrustum frustum = new BoundingFrustum(view * projection);
            ContainmentType containment = frustum.Contains(this.bounds);

            return this.Draw(frustum, view, projection, containment, objects);
        }

        /// 
        /// Draws the octree.
        /// 
        /// The viewing frustum used to determine if the octree is in view.
        /// The viewing matrix.
        /// The projection matrix.
        /// Determines how much of the octree is visible.
        /// The objects in the octree.
        /// The number of octrees drawn.
        private int Draw(BoundingFrustum frustum, Matrix view, Matrix projection,
            ContainmentType containment, List objects)
        {
            int count = 0;

            if (containment != ContainmentType.Contains)
            {
                containment = frustum.Contains(this.bounds);
            }

            // Draw the octree only if it is atleast partially in view.
            if (containment != ContainmentType.Disjoint)
            {
                // Draw the octree's bounds if there are objects in the octree.
                if (this.objects.Count > 0)
                {                    
                    if (DebugDraw != null)
                        DebugDraw.AddShape(new DebugBox(this.bounds,Color.White));
                    objects.AddRange(this.objects);
                    count++;
                }

                // Draw the octree's children.
                if (this.children != null)
                {
                    foreach (Octree child in this.children)
                    {
                        count += child.Draw(frustum, view, projection, containment, objects);
                    }
                }
            }

            return count;
        }

        /// 
        /// Splits the octree into eight children.
        /// 
        /// The maximum depth to recurse to.
        private void Split(int maxDepth)
        {
            this.children = new Octree[Octree.ChildCount];
            int depth = this.depth + 1;
            float quarter = this.length / this.looseness / 4f;

            this.children[0] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(-quarter, quarter, -quarter));
            this.children[1] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(quarter, quarter, -quarter));
            this.children[2] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(-quarter, quarter, quarter));
            this.children[3] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(quarter, quarter, quarter));
            this.children[4] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(-quarter, -quarter, -quarter));
            this.children[5] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(quarter, -quarter, -quarter));
            this.children[6] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(-quarter, -quarter, quarter));
            this.children[7] = new Octree(this.worldSize, this.looseness,
                maxDepth, depth, this.center + new Vector3(quarter, -quarter, quarter));
        }

    }
}

, , , , , ,

  1. #1 by Balers on 9 de dezembro de 2016 - 9:42 pm

    The information mentioned inside the report are a number of the very best readily available

  2. #2 by utilOn on 9 de dezembro de 2016 - 9:51 pm

    I apologise, but, in my opinion, you are not right. I can prove it. Write to me in PM, we will talk.
    utilOn

  3. #4 by http://kreditonlineab.info/kredit-ohne-warnung-youtube.html on 9 de dezembro de 2016 - 10:42 pm

    I really wish there were more articles like this on the web.

  4. #5 by louis vuitton keepall on 9 de dezembro de 2016 - 11:34 pm

  5. #7 by car insurance on 10 de dezembro de 2016 - 12:50 am

    Super jazzed about getting that know-how.

  6. #8 by was kostet ein kredit über 30000 on 10 de dezembro de 2016 - 1:08 am

    Ps. YOUTUBE: Why do I get this on some videoes: "This video cannot be watched in your country" ????????I soo wanted to see ESMEDENTERS latest video! But NOO, I cant!

  7. #9 by http://onlinekreditetestsiegergerade.org/kredit-zins-ratenkredit-online.html on 10 de dezembro de 2016 - 2:46 am

    Very valid, pithy, succinct, and on point. WD.

  8. #10 by a 2 b moving company on 10 de dezembro de 2016 - 3:16 am

    below youll locate the link to some sites that we assume you ought to visit

  9. #11 by http://bestekreditevergleichje.info/wie-hoch-kredit-hauskauf.html on 10 de dezembro de 2016 - 3:29 am

    That’s the best answer by far! Thanks for contributing.

  10. #12 by Maximo Strickling on 10 de dezembro de 2016 - 3:45 am

    There is noticeably a bundle to understand about this. I suppose you have made certain nice points in functions also.

  11. #13 by kreditinstitut vs finanzdienstleister on 10 de dezembro de 2016 - 3:48 am

    Touchdown! That’s a really cool way of putting it!

  12. #14 by http://kreditvergleichejetzo.info/40-kredit-neubau-konditionen.html on 10 de dezembro de 2016 - 4:22 am

    Amazing..it would take me a life time to complete all this. All are very beautiful and Congrats on your win.Do you know of Sandy Gervais ? She lives close by, designs fabric and patterns "Pieces of my Heart" and a true quilt professional. Thanks for sharing all your lovely's Have a great weekend

  13. #15 by http://kreditonlineab.info/yapı-kredi-bankası-fatura-ödeme.html on 10 de dezembro de 2016 - 4:27 am

    Jenny ! Hur kan man vara så osmaklig, hur kan du bara ställa sådana frågor du inte har ett dugg med att göra,att bara komma på tanken att fråga,du borde skämmas .Gull i Skåne

  14. #16 by eilkredit arbeitslos hausfrau ohne schufaauskunft dauer on 10 de dezembro de 2016 - 5:35 am

    It’s great to read something that’s both enjoyable and provides pragmatisdc solutions.

  15. #17 by buerge autokredit ffs bank hyundai on 10 de dezembro de 2016 - 6:41 am

    Hmm it appears like your site ate my initial comment (it was super long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog. I as well am an aspiring weblog blogger but I’m still new to everything. Do you might have any points for novice weblog writers? I’d surely appreciate it.

  16. #18 by http://besteonlinekreditjetzo.pw/rückzahlung-db-kredit-obwohl-kein-einkommen.html on 10 de dezembro de 2016 - 6:50 am

    Hello, i think that i noticed you visited my site so i came to “go back the favor”.I am attempting to in finding things to improve my website!I assume its good enough to use some of your ideas!!

  17. #19 by ratenkreditrechner excel on 10 de dezembro de 2016 - 7:58 am

    Your posting really straightened me out. Thanks!

1 255 256 257
(não será publicado)