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 land Sydney on 23 de julho de 2017 - 7:40 am

    It offers sailing arօᥙnd the lake іn summer аnd skating in winter; Chicago has ѕomething fоr all ᧐f coᥙrse,
    if you would want to discover а homе in the
    Chicago area, your besst opportunities ϲould poѕsibly bee іn getting a
    Chicago foreclosure. Ѕᥙn-kissed skin, yachts, beach, fresh fruit juices, martinis, colorful hats аnd bikinis, shades –
    moost ⲟf these mеans summer ԝhich iѕ faѕt approaching.

    Տome apartmeent complexes аllow no pets, οthers alⅼow
    just cats, and others аllow animals whidh ɑre smɑll compared t᧐ 20 pounds.

  2. #2 by seo definition on 23 de julho de 2017 - 7:50 am

    Here is a good Weblog You may Obtain Exciting that we Encourage You

  3. #3 by Pilihmana on 23 de julho de 2017 - 8:07 am

    Hiya, I am really glad I have found this info. Today bloggers publish just about gossip and web stuff and this is actually annoying. A good website with interesting content, that is what I need. Thank you for making this website, and I’ll be visiting again. Do you do newsletters by email?

  4. #4 by packaging supplies on 23 de julho de 2017 - 8:43 am

    please stop by the web pages we adhere to, which includes this 1, because it represents our picks in the web

  5. #5 by Toko Obat Herbal Online on 23 de julho de 2017 - 8:48 am

    Hey there. I discovered your site by means of Google at the same time as searching for a related topic, your site came up. It seems to be great. I have bookmarked it in my google bookmarks to come back then.

  6. #6 by games like the sims 4 on 23 de julho de 2017 - 9:10 am

    Very good post. I am going through some of these
    issues as well..

  7. #7 by KennethTag on 23 de julho de 2017 - 9:37 am

    wh0cd115885 [url=http://cialisonline.us.org/]Cialis Prescriptions[/url] [url=http://buyzithromax.us.org/]zithromax 250mg[/url] [url=http://amitriptyline.us.org/]amitriptyline online[/url]

  8. #8 by Leitura adicional on 23 de julho de 2017 - 12:51 pm

    Fui em varios sites na internet para pesquisar sobre isso, li varios
    sites e nenhum se compara a esse aqui, seu Artigo e exelente,
    muito bem feito e explicativo, adorei. obrigado pelas
    informaçoes.
    desculpe o portugues estou fora do BR a anos.

  9. #9 by Judi bola on 23 de julho de 2017 - 12:55 pm

    Awesome write-up. I’m a normal visitor of your website and appreciate you taking the time to maintain the nice site. I will be a regular visitor for a really long time.

  10. #10 by daftar game rts offline on 23 de julho de 2017 - 1:24 pm

    Hiya, I’m really glad I have found this info. Nowadays bloggers publish just about gossip and internet stuff and this is really irritating. A good site with exciting content, this is what I need. Thank you for making this website, and I will be visiting again. Do you do newsletters by email?

  11. #11 by harga rumahminimalis semua type terbaru on 23 de julho de 2017 - 1:25 pm

    Hiya, I am really glad I have found this information. Today bloggers publish only about gossip and internet stuff and this is actually annoying. A good web site with interesting content, that is what I need. Thanks for making this web site, and I will be visiting again. Do you do newsletters by email?

  12. #12 by link building youtube on 23 de julho de 2017 - 2:05 pm

    that will be the end of this write-up. Right here you will obtain some web sites that we feel you will appreciate, just click the hyperlinks over

  13. #14 by ufc 214 live stream on 23 de julho de 2017 - 2:38 pm

    Hello all, here every person is sharing such experience, so it’s pleasant to read
    this website, and I used to go to see this blog every day.

  14. #15 by bali good driver on 23 de julho de 2017 - 2:56 pm

    Awesome write-up. I am a normal visitor of your blog and appreciate you taking the time to maintain the excellent site. I’ll be a regular visitor for a long time.

  15. #16 by link building in 2017 on 23 de julho de 2017 - 3:01 pm

    check beneath, are some completely unrelated websites to ours, nevertheless, they are most trustworthy sources that we use

  16. #17 by Biloxi Corporate rentals on 23 de julho de 2017 - 5:16 pm

    we came across a cool internet site which you might delight in. Take a search in the event you want

  17. #18 by red bottom shoes replica on 23 de julho de 2017 - 5:59 pm

    Our supplement is at that ideal rates I never ever idea the actual excellent is so that exceptional. It’s striking. That mama might appreciate they at Christmas day anytime she opens up gifts and it appearance like I spent far more, then again pricing was exclusively great!!

  18. #19 by http://www.hexpilot.com/help_cartier.aspx on 23 de julho de 2017 - 6:00 pm

    We have purchased this particular brand name concerning bracelet some occasions. Every single one is ultra adorable, prepared well, cannot tarnish to meaningful depending on which an individual you purchase furthermore who one present this in order to.

  19. #20 by business plan on 23 de julho de 2017 - 6:45 pm

    Thanks for the sensible critique. Me and my neighbor were just preparing to do a little research on this. We got a grab a book from our local library but I think I learned more from this post. I am very glad to see such fantastic info being shared freely out there.

1 450 451 452
(não será publicado)