The only differences between an Octree and a Quadtree is an additional axis. This post will cover bounding box checks; for Tree psuedo code and structure breakdown go to my Quadtree page. Please note an interactive example is below for this tree structure. For spheres and cubes (circles/rectangles in 2d) it’s always quicker to check intersections by comparing centers and length or radius. For simplicity I only store a bounding boxes length and center.
To test if a point is inside a bounding box. Take the absolute value of the distance between the point and this boxes center, if this value is less than 1/2 it’s length (I times the distance by two because I don’t store half lengths). If it’s true for every axis this point is inside.
|
1 2 3 4 5 6 |
private bool PointInBoundingBox(Vector3 Point, BoundingBox Box) { return (Mathf.Abs(Point.x - Box.BoxCenter.x) < (Box.HalfLength) && Mathf.Abs(Point.y - Box.BoxCenter.y) < (Box.HalfLength) && Mathf.Abs(Point.z - Box.BoxCenter.z) < (Box.HalfLength)); } |
To test if bounding boxes overlap. Take the ABS of the distance between the two boxes (times by two or compare to their half lengths) and check if that value is less than the boxes combined length. If it is, they overlap.
|
1 2 3 4 5 6 |
private bool BoundingBoxesOverlap(BoundingBox BoxA, BoundingBox BoxB) { return (Mathf.Abs(BoxA.BoxCenter.x - BoxB.BoxCenter.x) * 2 < (BoxA.BoxLength + BoxB.BoxLength) && Mathf.Abs(BoxA.BoxCenter.y - BoxB.BoxCenter.y) * 2 < (BoxA.BoxLength + BoxB.BoxLength) && Mathf.Abs(BoxA.BoxCenter.z - BoxB.BoxCenter.z) * 2 < (BoxA.BoxLength + BoxB.BoxLength)); } |
To find the child node a point falls into can be solved with three axis checks. Example of how I arranged the nodes to the left (the cube that isn’t visible is 101.)
|
1 2 3 4 5 6 |
InsertArea = 0; if (Point.x > Node.BoundingBox.BoxCenter.x) { InsertArea += 100; } // 0 x is E, 100 X is W if (Point.y > Node.BoundingBox.BoxCenter.y) { InsertArea += 10; } //0 y is B, 10 Y is T if (Point.z > Node.BoundingBox.BoxCenter.z) { InsertArea += 1; } //0 Z is S, 1 Z is North switch (InsertArea){...} |
(Please note interactive example below takes about 30 seconds to load):