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 list of car insurances in Mechanicsville VA on 15 de janeiro de 2017 - 6:23 pm

    I never thought I would find such an everyday topic so enthralling!

  2. #2 by car insurance quotes Tyler TX on 15 de janeiro de 2017 - 6:54 pm

    Hello presently there, I discovered your own site by way of Search engines while looking for the related subject, your own website came upward, this appears great. I’ve book-marked this during my search engines book marks.

  3. #3 by home insurance by zip code of washington on 15 de janeiro de 2017 - 7:28 pm

    I just couldn’t depart your web site before suggesting that I really enjoyed the standard information a person provide for your visitors? Is gonna be back often in order to check up on new posts

  4. #4 by http://autoinsurancequotesem.us/TX/Crowley/full-coverage-car-insurance/ on 15 de janeiro de 2017 - 9:58 pm

    You couldn’t pay me to ignore these posts!

  5. #5 by motorcyclist quotes on 15 de janeiro de 2017 - 9:59 pm

    Pretty component to content. I just stumbled upon your site and in accession capital to say that I get actually loved account your blog posts. Anyway I’ll be subscribing on your feeds and even I fulfillment you get entry to consistently quickly.

  6. #6 by http://autoinsurancend.info/CA/San-Francisco/affordable-car-insurance/ on 15 de janeiro de 2017 - 10:08 pm

    You can always tell an expert! Thanks for contributing.

  7. #7 by auto insurance quotes Lake Orion MI on 15 de janeiro de 2017 - 10:59 pm

    quite advantageous…Hi there, Apparent content. There’s a worry together with your web page upon internet explorer, would assess this… VISITOR nonetheless will be the market chief and a huge percentage of women and men may effectively proceed previously mentioned ones pe…

  8. #8 by http://cheapcarinsurancefc.top/IL/Mchenry/direct-auto-insurance/ on 15 de janeiro de 2017 - 11:34 pm

    prenez pas en compte le message précédent de mon imitateur qui se fait maintenant passer pour l’original.L’original de la caricature, c’est moi !

  9. #9 by health insurance nj on 16 de janeiro de 2017 - 12:39 am

    Wow! Thank you! I constantly wanted to write on my blog something like that. Can I take a part of your post to my website?

  10. #10 by http://autoinsurancersr.top/OH/Brunswick/cheapest-auto-insurance-in/ on 16 de janeiro de 2017 - 12:40 am

    Hiya very nice website!! Guy .. Excellent .. Superb .. I will bookmark your web site and take the feeds additionally…I’m satisfied to search out a lot of helpful info here within the submit, we want work out extra strategies on this regard, thanks for sharing.

  11. #12 by Ben Nye Luxury Powder on 16 de janeiro de 2017 - 1:41 am

  12. #13 by How to Meditate on 16 de janeiro de 2017 - 2:42 am

    You made some respectable points there. I regarded on the internet for the problem and found most people will go along with along with your website.

  13. #15 by bitcoin hosting on 16 de janeiro de 2017 - 4:10 am

    You have mentioned very interesting points! ps nice web site.

  14. #16 by Viagra on 16 de janeiro de 2017 - 5:43 am

    I’m no longer positive the place you are getting your information, but good topic. I needs to spend a while learning much more or figuring out more. Thank you for magnificent info I used to be searching for this info for my mission.|

  15. #18 by us agency car insurance Lincoln Park MI on 16 de janeiro de 2017 - 8:01 am

    I received this today:> Date: Tue, 21 Feb 2012 08:48:15 +0100> Subject: Booking> From: > To:>> Good Day, I am Mr Martin Geer and would like to make a reservation> for three single rooms for a full week (12th-18th April),we are> three in number.Get back to me with the total cost including breakfast> every morning.Mode of payment is either credit card of check.>> Thanks>> Mr Martin Geer

  16. #19 by low income auto insurance dmv Bryan TX on 16 de janeiro de 2017 - 8:08 am

    I will be putting this dazzling insight to good use in no time.

  17. #20 by cheap car insurance quotes Elkhart IN on 16 de janeiro de 2017 - 8:55 am

    Orange, of course! (Now I want to pull out my other issue and see what color each of those are!) I liked having Judy Laquidara included in this issue. She does a great job of designing whole quilts and the one with her block is terrific!

  18. #22 by http://autoinsurancend.info/MO/Warrensburg/auto-insurance/ on 16 de janeiro de 2017 - 9:36 am

    Insights like this liven things up around here.

  19. #23 by e Esurance on 16 de janeiro de 2017 - 9:47 am

    Thanks for another informative site. Where else could I get that type of info written in such an ideal way? I’ve a project that I am just now working on, and I have been on the look out for such information.

  20. #24 by esurance life on 16 de janeiro de 2017 - 11:06 am

    I will right away take hold of your rss feed as I can’t in finding your e-mail subscription hyperlink or newsletter service. Do you’ve any? Please let me recognise in order that I may subscribe. Thanks.

  21. #25 by http://autoinsurancersr.top/MD/Potomac/low-income-auto-insurance-dmv/ on 16 de janeiro de 2017 - 11:58 am

    Clear, informative, simple. Could I send you some e-hugs?

  22. #26 by beton imprime on 16 de janeiro de 2017 - 12:18 pm

    I like what you guys are up also. Such intelligent work and reporting! Carry on the superb works guys I¦ve incorporated you guys to my blogroll. I think it will improve the value of my site :)

  23. #27 by Direct insurance group on 16 de janeiro de 2017 - 1:34 pm

    Good day very cool website!! Guy .. Excellent .. Wonderful .. I will bookmark your web site and take the feeds additionally…I am satisfied to find so many useful information here within the submit, we need work out more techniques in this regard, thank you for sharing. . . . . .

  24. #28 by http://besterkreditvergleich.net/privat-kreditvertrag-muster-kostenlos-herunterladen.html on 16 de janeiro de 2017 - 2:42 pm

    I’m actually really curious to hear more about your process on that Finish Line piece. There are different ways to do that I guess, but were you using animated masks to cut out the people? Then layer those back on top of the original with the animated elements sandwiched? Great work and interview!

  25. #29 by yeezy boost 350 store list on 16 de janeiro de 2017 - 3:16 pm

  26. #30 by Online Colleges on 16 de janeiro de 2017 - 4:20 pm

    Very interesting subject, appreciate it for posting.

  27. #31 by geico insurance erie pa on 16 de janeiro de 2017 - 4:38 pm

    You have observed very interesting points! ps decent internet site.

  28. #32 by kredit student negativ telefonnummer on 16 de janeiro de 2017 - 6:09 pm

    Reading posts like this make surfing such a pleasure

  29. #33 by カルティエ 結婚指輪 口コミ usj on 16 de janeiro de 2017 - 6:25 pm

    人気腕時計
    2017新作の展示,新品種類がそろっています!
    当社の商品は絶対の自信が御座います。
    ★信用第一、良い品質、低価格は(*^-^*)
    ★当店の承諾に→誠実 信用
    ★送料無料(日本全国)
    ※ご注文の方は、ご連絡下さい。期待!!
    ※以上 宜しくお願い致します。(^0^)
    カルティエ 結婚指輪 口コミ usj http://kopii.net/products/p1/3/3/index.htm

  30. #34 by パシャ ドゥ カルティエ 財布 zozo on 16 de janeiro de 2017 - 6:25 pm

    2017秋冬モデル100 %実物
    パネライスーパーコピー
    注文特恵中-新作入荷!-価格比較.送料無料!
    主要取扱商品 バッグ、財布、腕時計、ベルト!
    オークション、楽天オークション、売店、卸売りと小売りの第一選択のブランドの店。
    信用第一、良い品質、低価格は 私達の勝ち残りの切り札です。
    当社の商品は絶対の自信が御座います。
    おすすめ人気ブランド腕時計, 最高等級時計大量入荷!
    N品質シリアル付きも有り 付属品完備!
    以上 宜しくお願い致します。
    2017秋冬モデル100 %実物
    パシャ ドゥ カルティエ 財布 zozo http://kopi78.com/products_bigbrandId_2.html

  31. #35 by シャネル時計 修理 値段 ガラス on 16 de janeiro de 2017 - 6:25 pm

    ブラントスーパーコピー品
    マストな新作アイテム続々入荷中…
    長年の豊富な経験と実績を持ち、
    ブラントスーパーコピー品の完壁な品質を維持するために、
    一流の素材を選択し、精巧な作り方でまるで本物のようなな製品を造ります。
    高品質の商品を低価格で提供する、納期を厳守することは弊社の経営理念です。
    今、マストなブランドコピー新作アイテム続々入荷中…
    【シャネルコピー、ヴィトンコピー、コピーグッチ、エルメスコピー】ブランド財布コピー、バッグコピー腕時計コピーぜひおすすめです。
    シャネル時計 修理 値段 ガラス http://bagshop78.com/brandcopy-m-23.html

  32. #36 by カルティエ 財布 ピンク qrコード on 16 de janeiro de 2017 - 6:25 pm

    ブランド靴コピー
    \\\\\V/////
    貴——-族——-店
    /////V\\\\\ブランド服
    ━━……━…━…━…━…━…━…━…━…━… _(._.)_
    ルブタン 靴 コピー、シャネルブランド靴
    グッチ靴激安コピー、バーバリー靴コピー
    クリスチャンルブタン靴コピー
    ━━……━…━…━…━…━…━…━…━…━…(* ^ – ^* )
    ★*通販しますご注文を期待しています*★
    ✿※✿不優待価格で、斬新なデザイン✿※✿
    ✿※✿通気性がよく、着心地がいい✿※✿
    ✿※✿好きな運動の最優秀選択者!✿※✿
    ★歓迎光臨(* ^ – ^ *)送料無料(日本全国)
    ┓┏┓┏┓
    ┻┗┛┗┛%品質保証 満足保障 信用の第1。
    ◎ブランド靴新作大人気再登场!
    ◎靴ブランドコピー通販人気特集!
    カルティエ 財布 ピンク qrコード http://nawane111.com/%e3%82%b9%e3%83%bc%e3%83%91%e3%83%bc%e3%82%b3%e3%83%94%e3%83%bc-11-b0.html

  33. #37 by insurance RATINGs by car on 16 de janeiro de 2017 - 9:01 pm

    I’ve read some excellent stuff here. Definitely value bookmarking for revisiting. I wonder how a lot attempt you put to make this kind of great informative site.

  34. #39 by map on 16 de janeiro de 2017 - 11:12 pm

    Attractions: A small-sized waterfall with several cascades.

    Don’t forget to ask if they take care of the excess dirt. Then find some woodworking plans and patterns
    for a nice little wooden bridge for over your pond and you are done.

  35. #40 by Car Insurance Quotes Online on 16 de janeiro de 2017 - 11:37 pm

    We are using the trend code blue template to get wordpress. I would really like to change every fonts to Trebuchet MS. I have attempted editing the stylesheet yet no fortune. Any recommendations?.

  36. #41 by sofortkredit selbstaendig ohne telefonnummer on 16 de janeiro de 2017 - 11:48 pm

    I guess finding useful, reliable information on the internet isn’t hopeless after all.

  37. #42 by kredit autokredit berechnen excel youtube on 16 de janeiro de 2017 - 11:53 pm

    Hej SanneJeg vil også tabe mig, BIG TIME, noget nær 40 kg. jeg er 172 cm og vejer 115 kg.Det lyder meget godt med at skulle erstatte kartofler, pasta og ris med bønner og linser, men jeg kan ikke fordrage bønner og linser, er der noget andet man kan erstatte det med?

  38. #43 by jordan 12 low max orange for sale on 17 de janeiro de 2017 - 12:25 am

  39. #44 by free download for windows pc on 17 de janeiro de 2017 - 2:36 am

    Unquestionably believe that which you said. Your favorite justification appeared to be on the internet the simplest thing to be aware of. I say to you, I definitely get irked while people think about worries that they just do not know about. You managed to hit the nail upon the top and defined out the whole thing without having side-effects , people could take a signal. Will likely be back to get more. Thanks

  40. #45 by Muk Pokemon on 17 de janeiro de 2017 - 3:16 am

    As I website possessor I believe the content material here is rattling magnificent , appreciate it for your hard work. You should keep it up forever! Good Luck.

  41. #46 by kostenlos mustervertrag kredit zinsen on 17 de janeiro de 2017 - 4:26 am

    This could not possibly have been more helpful!

1 280 281 282
(não será publicado)