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 Listobjects = 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. ////// public bool HasChanged(T obj, BoundingBox transformebbox) { return this.bounds.Contains(transformebbox) == ContainmentType.Contains; } ///true if the specified obj has changed; otherwise,false . ////// 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 OctreeAdd(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 OctreeAdd(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 OctreeAdd(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, Listobjects) { 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, Listobjects) { 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 by smart hoverboard for sale on 23 de outubro de 2016 - 12:08 am

Regarding Walk 17, 1946 Professional photographer Coffee Jasgur taken graphics with the afterward 10 year old Norma Jean Chef, soon after often called Lana turner.

#2 by preisvergleich von kfz versicherungen on 23 de outubro de 2016 - 12:10 am

– mamma, mamma, mi compri un orgone nuovo?- no Gigetto, ne hai giÃ quattro, gioca con quelli che hai.- allora un elicotterino nero nuovo, daaaai!- t’ho detto di no! anche di quelli Ã¨ piena la casa!- WAAAAAAAAH! io voglio l’orgone limited ediscion che ho visto in tivÃ¹ autografato dal Comandante Strecher! BUAAAAAAAAH!- BASTA! quando arriva papÃ dal lavoro stasera gli dico che hai fatto le bizze, e per punizione stai un mese senza guardare Rebus in tivÃ¹!

#3 by paypal ohne kreditkarte geld senden on 23 de outubro de 2016 - 1:30 am

Hahaha, you dropped a gender specific pronoun there. 😛 I got something awesome too. Civ 4 the Complete Edition from Bia Hawks. Which is a huge game (both literally and figuratively speaking) so thank you so very much Bia! :D:D:DVN:F [1.9.20_1166](from 0 votes)

#4 by viagra on 23 de outubro de 2016 - 1:48 am

usually posts some extremely intriguing stuff like this. If you are new to this site

#5 by kfz vollkaskoversicherung steuerlich absetzbar on 23 de outubro de 2016 - 2:54 am

This is great! What is the machine you are using to mix with called?It is a food processor, you can find them in the kitchen section at most stores. I also use it to blend the corn for the humitas, as well as to make the dough for the empanadas de verde.

#6 by Hoverboard Electrique on 23 de outubro de 2016 - 3:34 am

And for starters I seemed to be for instance, I would like six youngsters.

#7 by http://gunstigekfzversicherung.info/ford-versicherungen.html on 23 de outubro de 2016 - 3:37 am

Well to me, I really do not care what I look like or what I am wearing,l All I care about is My horse, (evenï»¿ though I don’t have a horse, nor a horse to ride on) and competition. Either with helmet or not helmet. I don’t care. Lol.

#8 by http://autoversicherungberechnen.top/haftpflichtversicherung-rechner.html on 23 de outubro de 2016 - 3:41 am

That’s really thinking out of the box. Thanks!

#9 by keezporn on 23 de outubro de 2016 - 3:50 am

Annie told him that urge had nothing to cessation with, that she was married, that she would never cheat on her spouse.glide over and lay your jizm-shotgun on James she said so i moved over and lay it on his pummel-stick.

http://viva-viaje.com/index.php?option=com_k2&view=itemlist&task=user&id=85474

#10 by pocketpoon on 23 de outubro de 2016 - 3:51 am

She fell succor fatigued, as was I.Therefore, any doors, curtains, or other obstacle will linger beget when the spouse is in that apartment un-attended by the Wife or a gal(s) designated by the Wife.

http://joethiel.com/index.php?option=com_k2&view=itemlist&task=user&id=206549

#11 by gebühren kreditkarte deutsche bank on 23 de outubro de 2016 - 4:36 am

I made these last night and we loved them. I served them over Ina Garten’s sauteed spinach w/ garlic – great combo. These are definitely going into the rotation!

#12 by zahlung per kreditkarte ablauf on 23 de outubro de 2016 - 4:49 am

What an amazing story, thank you for sharing. Our first son was born the same month and year as Brayson. Our son was 25 weeks gestation and only lived 24hrs. It’s so wonderful to read and know there’s other people raising awareness about prematurity. You’re truly an inspiration. Thank you!!

#13 by Felicita Milanowski on 23 de outubro de 2016 - 5:10 am

hotele Elblag

#14 by Stanton Nayee on 23 de outubro de 2016 - 5:28 am

Baby product reviews: strollers, carriers, swing chairs, diapers and more