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 adidas yeezy boost 350 v2 uk sply on 26 de setembro de 2016 - 11:49 am

  2. #2 by cheap car insurance quotes Gainesville GA on 26 de setembro de 2016 - 12:17 pm

    Good job making it appear easy.

  3. #3 by cheap car insurance Union City NJ on 26 de setembro de 2016 - 12:32 pm

    Thank you for this wonderful opportunity to learn. I am fascinated with the subject and eager to learn which wild edibles I can access and start eating here in E.Sussex, UK. <3

  4. #4 by cheapest auto insurance Peoria IL on 26 de setembro de 2016 - 1:12 pm

    Acrimed… Acrimed… c’est pas le site qui a dénoncé le plagiat de… comment s’appelle-t-il déjà… et autres connivences dans le monde des médias* ?*médias : mot induisant que l’auteur de ce com est un paranoïaque.

  5. #6 by michael kors outlet prices on 26 de setembro de 2016 - 1:30 pm

  6. #7 by handmade samurai swords on 26 de setembro de 2016 - 1:53 pm

    Parfait transaction. Ils devraient tous travailler comme ça . Merci beaucoup .

  7. #8 by cheap sr22 insurance Nashville TN on 26 de setembro de 2016 - 2:17 pm

    I’m quite pleased with the information in this one. TY!

  8. #9 by best auto insurance in Statesboro GA on 26 de setembro de 2016 - 3:10 pm

    If you really want to make a case for secession, show how the Federal government subverts, attacks and seeks to destroy Christianity. Few men will risk life, limb and fortune for fortunes yet many more will risk everything for eternal salvation. If interests are threads the strongest most solid of all threads connecting your target audience and more is Christianity.

  9. #10 by true swords on 26 de setembro de 2016 - 3:20 pm

    love it! fast and easy transaction

  10. #11 by laminante on 26 de setembro de 2016 - 4:27 pm

    This is a topic that as close to my heart Many thanks! Where are your contact details though?

  11. #12 by pokemon go funny moments on 26 de setembro de 2016 - 4:50 pm

    Thanks so much for the article post.Really looking forward to read more.

  12. #13 by cheapest auto insurance Rialto CA on 26 de setembro de 2016 - 5:39 pm

    Does your site have a contact page? I’m having problems locating it but, I’d like to send you an email. I’ve got some ideas for your blog you might be interested in hearing. Either way, great blog and I look forward to seeing it develop over time.

  13. #14 by car insurance quotes on 26 de setembro de 2016 - 5:51 pm

    The forum is a brighter place thanks to your posts. Thanks!

  14. #15 by cheap auto insurance quotes New Milford CT on 26 de setembro de 2016 - 6:00 pm

    Cheers pal. I do appreciate the writing.

  15. #16 by grand national runners on 26 de setembro de 2016 - 6:24 pm

    Hey, thanks for the article.Much thanks again. Really Great.

  16. #17 by car insurance quotes Dallas GA on 26 de setembro de 2016 - 6:43 pm

    Anónimo,Es correcto la intención no es establecer la ubicación precisa o exacta, de lo contrario se estaría infringiendo la privacidad de los cibernautas. Revisar la respuesta anterior dirigida a “Cmos”. Sin embargo, gracias por exponer tu punto de vista.

  17. #18 by cheapest car insurance in Burbank CA on 26 de setembro de 2016 - 7:00 pm

    Carlos: Sí, ésto lo publiqué antes de el cierre de Megaupload a cargo del FBI. Afortunadamente los otros discos están en Mediafire. Y sí, tu hermano me sigue en twitter. Respecto a lo de la camara, quizás más adelante, cuando ya hayas encontrado alguna forma de poder grabarte bien, podrás ir subiendo algunos videos tuyos; mientras tanto no es algo urgente ;)Saludos y muchas gracias por tu cmentario.

  18. #19 by http://todosossites.info/site/conacyt.mx on 26 de setembro de 2016 - 7:05 pm

    Amazing blog! Do you have any helpful hints for aspiring writers? I’m planning to start my own site soon but I’m a little lost on everything. Would you advise starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m totally overwhelmed .. Any ideas? Thank you!

  19. #20 by продажба имоти софия лозенец on 26 de setembro de 2016 - 8:02 pm

    An impressive share, I just given this onto a colleague who was doing a little analysis on this. And he in fact bought me breakfast because I found it for him.. smile. So let me reword that: Thnx for the treat! But yeah Thnkx for spending the time to discuss this, I feel strongly about it and love reading more on this topic. If possible, as you become expertise, would you mind updating your blog with more details? It is highly helpful for me. Big thumb up for this blog post!

  20. #21 by deko zum basteln on 26 de setembro de 2016 - 8:11 pm

    Sweet blog! I found it while searching on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I ave been trying for a while but I never seem to get there! Many thanks

  21. #22 by Tsukas on 26 de setembro de 2016 - 8:37 pm

    Thanks! Great Product and shipping

  22. #23 by Tsuba on 26 de setembro de 2016 - 8:37 pm

    recommend seller! Thanks for fast shipping &amp; delivery!

  23. #24 by look auto insurance Abilene TX on 26 de setembro de 2016 - 8:40 pm

    If my problem was a Death Star, this article is a photon torpedo.

  24. #25 by Swords Bags on 26 de setembro de 2016 - 9:49 pm

    Love the shoe! Quick shipping! Great condition!

  25. #26 by Nodachis on 26 de setembro de 2016 - 9:50 pm

    Item as described. Timely shipping.

  26. #27 by cheapest japan rail pass on 26 de setembro de 2016 - 9:59 pm

    Whoa! This blog looks just like my old one! It as on a completely different subject but it has pretty much the same layout and design. Wonderful choice of colors!

  27. #28 by alzheimers care on 26 de setembro de 2016 - 10:26 pm

    that would be the finish of this report. Here you will uncover some web-sites that we believe youll appreciate, just click the links over

  28. #29 by car insurance in New Orleans LA on 26 de setembro de 2016 - 10:51 pm

    Habt ihr eure Geschenke schon beisammen? Baschi ist gerade noch im Geschenke-Stress: “Express Weihnachts Geschenk kaufen !! Wie ich das liebe …. Und so wenig Menschen es hat hahah”

  29. #30 by low income car insurance dmv Elk Grove Village IL on 26 de setembro de 2016 - 11:21 pm

    you’re actually a excellent webmaster. The site loading speed is amazing. It sort of feels that you’re doing any distinctive trick. Moreover, The contents are masterwork. you have performed a wonderful task on this subject!

  30. #31 by rail pass japan cost on 26 de setembro de 2016 - 11:48 pm

    You might be my role designs. Thank you for the write-up

  31. #32 by Naginata Sword on 27 de setembro de 2016 - 12:19 am

    Je vous remercie ! Article juste comme décrit et expédition rapide!

  32. #33 by affordable car insurance Northbrook IL on 27 de setembro de 2016 - 1:24 am

    Something isn't entirely right in this article. While Jews had–until recent times–a similar practice of marrying a relative (maybe, not as widespread as in the Muslim community, but, nevertheless, not illegal or frown upon)–the cognitive benefits of endogamous marriage were as high, if not higher, than the negative effects. I'm talking in statistical terms, not in individual: a sick child is a sick child, one or a thousand doesn't matter to that child or her family.Maybe, consanguinity can amplify both the negative and the positive of the founding population?

  33. #34 by new cars kia on 27 de setembro de 2016 - 1:35 am

    I simply could not leave your site prior to suggesting that I extremely enjoyed the standard information a person supply to your visitors? Is going to be back incessantly to inspect new posts

1 170 171 172
(não será publicado)