A few weeks ago I created my first implementation of an Octree… What are Octrees you ask, well, they are super cool is what they are. I have only ever seen them being used in Game Dev, and have always been dying to find a reason to try them out, but alas, my interests have been pulled this way and that way and never got around to playing with them. The last place I thought I would be using them is within Revit as most of my time is within Unity these days, but Revit is a good a place as any to experiment.
Octrees
Octrees are a type of Data structure where basically you take a 3D space (say a bounding box) and recursively subdivide the space into 8 sub-trees (or octants), you can keep subdividing each octant independently depending on the rules. Hmmm, well that’s all well and good, but why would we care about such a thing?!? Well they are a effective method of representing, traversing and indexing 3D space and are used heavily in computer graphics and 3D applications for all kinds of things like frustrum/occlusion culling, 3D grids, spatial indexing etc etc..
Lets have a look at a very simple example… lets say you have a 3D model and it has thousands and thousands of objects and you want to find all the objects nearby to your object, well a naive approach would be to loop through all the objects and query whether the current object is close to the target object. Well, this is one approach, but is quite slow as you have to touch all the objects each time you do the query – in game design, this is very bad for performance as this query would need to run in the game loop and if you were doing this every frame, say 60 fps, it would almost definitely degrade game loop performance and dominate the frames compute time.
Another approach is to use an Octree, on initialisation you create this 3D Tree of boxes within boxes within boxes, each one an eighth of the size of its parent and representing one octant of the box (like a quadrant, but in 3-dimensions), each time you subdivide the parent node into octants, the octants take note of what object they contain and pass it up the tree. Now you have a Tree where the parent node and all child nodes know all the objects within their respective spaces and locate an object easily in relation to another object. This is an optimisation as the tree is created once, then once created you no longer need to loop through the whole set of objects, you only need to find which octant it exists in (1 in 8 chances) and then traverse downwards to find other objects nearby. Now, before some smart person realises some obvious flaws in this approach, this isn’t quite a finished algorithm, but good enough for an example.
My implementation
Anyway, now you know roughly what they are, I thought it would be cool to voxelate my Revit model. There are a few ways to do this, but I have been itching to try out octrees for some time and thought… Hey, why not… and here is the result…
The Code
The main calling method…
public void GenerateOctTree()
{
var uidoc = this.ActiveUIDocument;
var doc = uidoc.Document;
var root = new OctTree(doc, doc.GetModelExtents(false), null);
var lastIter = new List<OctTree>(){ root };
for (int i = 0; i < 7; i++)
{
var currentIter = new List<OctTree>();
foreach (OctTree ot in lastIter)
{
if (ot.CanBranch())
currentIter.AddRange(ot.CreateBranches());
}
lastIter = currentIter;
}
var mat = new FilteredElementCollector(doc).OfClass(typeof(Material)).Where(m => m.Name == "Default").FirstOrDefault();
var grStl = new FilteredElementCollector(doc).OfClass(typeof(GraphicsStyle)).FirstOrDefault();
var options = new SolidOptions(mat.Id, grStl.Id);
var solids = root.GetSolids(options);
solids.ToDirectShape(doc);
}
The Octree class itself…
public class OctTree
{
public enum Octant
{
BottomFrontLeft,
BottomFrontRight,
BottomBackLeft,
BottomBackRight,
TopFrontLeft,
TopFrontRight,
TopBackLeft,
TopBackRight,
}
public OctTree Parent;
public Document Doc;
public BoundingBoxXYZ Extents;
public List<ElementId> IdSet = new List<ElementId>();
public List<OctTree> Branches = new List<OctTree>();
public bool HasChildren()
{
return Branches.Count > 0;
}
public bool HasParent()
{
return Parent != null;
}
public bool ContainsElements()
{
return IdSet.Count > 0;
}
public OctTree(Document doc, BoundingBoxXYZ extents, OctTree parent = null)
{
Doc = doc;
Extents = extents;
if (parent != null)
Parent = parent;
GetIds();
}
private void GetIds()
{
var f1 = new BoundingBoxIntersectsFilter(Extents.ToOutline());
var f2 = new ElementMulticategoryFilter(new List<BuiltInCategory>()
{
BuiltInCategory.OST_Floors,
BuiltInCategory.OST_Walls,
BuiltInCategory.OST_StructuralFraming,
BuiltInCategory.OST_StructuralColumns,
BuiltInCategory.OST_StructuralFoundation
});
var filter = new LogicalAndFilter(f1, f2);
var fec = Parent == null ? new FilteredElementCollector(Doc) : new FilteredElementCollector(Doc, Parent.IdSet);
IdSet = fec.WherePasses(filter).ToElementIds().ToList();
}
public bool CanBranch()
{
return ContainsElements() && !HasChildren();
}
public List<OctTree> CreateBranches()
{
if (CanBranch())
{
Branches.Add(new OctTree(Doc, GetOctant(Octant.BottomFrontLeft), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.BottomBackLeft), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.BottomBackRight), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.BottomFrontRight), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.TopFrontLeft), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.TopBackLeft), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.TopBackRight), this));
Branches.Add(new OctTree(Doc, GetOctant(Octant.TopFrontRight), this));
}
return Branches;
}
private BoundingBoxXYZ GetOctant(Octant octant)
{
var bbox = new BoundingBoxXYZ();
var orig = Extents.Min;
var min = new XYZ();
var max = new XYZ();
var d = Extents.Max.Subtract(Extents.Min);
switch (octant)
{
case Octant.BottomFrontLeft:
{
min = orig;
}; break;
case Octant.BottomBackLeft:
{
min = new XYZ(orig.X, orig.Y + d.Y/2, orig.Z);
}; break;
case Octant.BottomBackRight:
{
min = new XYZ(orig.X + d.X/2, orig.Y + d.Y/2, orig.Z);
}; break;
case Octant.BottomFrontRight:
{
min = new XYZ(orig.X + d.X/2, orig.Y, orig.Z);
}; break;
case Octant.TopFrontLeft:
{
min = new XYZ(orig.X, orig.Y, orig.Z + d.Z/2);
}; break;
case Octant.TopBackLeft:
{
min = new XYZ(orig.X, orig.Y + d.Y/2, orig.Z + d.Z/2);
}; break;
case Octant.TopBackRight:
{
min = new XYZ(orig.X + d.X/2, orig.Y + d.Y/2, orig.Z + d.Z/2);
}; break;
case Octant.TopFrontRight:
{
min = new XYZ(orig.X + d.X/2, orig.Y, orig.Z + d.Z/2);
}; break;
default:
{
min = orig;
} break;
}
bbox.Min = min;
bbox.Max = min.Add(d/2);
return bbox;
}
public List<Solid> GetSolids(SolidOptions options)
{
var solids = new List<Solid>();
if (HasChildren())
foreach (OctTree branch in Branches)
solids.AddRange(branch.GetSolids(options));
else
{
if (ContainsElements())
{
var solid = Extents.ToSolid(options);
Element e = null;
if (DoesSolidIntersect(solid, out e))
{
var elemMat = e.GetMaterialIds(false).FirstOrDefault();
var matId = elemMat == null ? options.MaterialId : elemMat;
var ops = new SolidOptions(matId, options.GraphicsStyleId);
var s = Extents.ToSolid(ops);
solids.Add(s);
}
solid.Dispose();
}
}
return solids;
}
private bool DoesSolidIntersect(Solid solid, out Element e)
{
var filter = new ElementIntersectsSolidFilter(solid);
e = new FilteredElementCollector(Doc, IdSet).WherePasses(filter).ToElements().FirstOrDefault();
return e != null;
}
}
Some extension methods to extend some of the Revit Classes…
public static class RevitHelper
{
/// <summary>
/// Gets the sum of all bounding boxes as one BoundingBox that represents the Extents of the model.
/// Credit to Jeremy Tammik. https://jeremytammik.github.io/tbc/a/1456_bounding_section_box.html
/// </summary>
/// <param name="doc"></param>
/// <returns></returns>
public static BoundingBoxXYZ GetModelExtents(this Document doc, bool incPadding = false)
{
// Slight alteration to filter only Element that have a category and are cuttable...
var elems = new FilteredElementCollector(doc).WhereElementIsNotElementType().WhereElementIsViewIndependent().Where(e => e.Category != null && e.Category.IsCuttable).ToList();
// Slight modification to ensure that there is a bbox...
IEnumerable<BoundingBoxXYZ> bbs = elems.Where(e => e.get_BoundingBox(null) != null).Select<Element,BoundingBoxXYZ>(e => e.get_BoundingBox(null));
var bbox = bbs.Aggregate<BoundingBoxXYZ>((a, b) => {a.ExpandToContain(b); return a;});
//TODO: Change incPadding to a double value for the amount to enlarge by. This should be an optional parameter defaulted to 0. This way if no padding given, then the padding will be 0...
// If we should include padding, then update the Min/Max of the BoundingBox...
var padding = incPadding ? new XYZ(3,3,3) : XYZ.Zero;
// Apply Padding...
bbox.Min = bbox.Min - padding;
bbox.Max = bbox.Max + padding;
return bbox;
}
/// <summary>
/// Expand the given bounding box to include.
/// Credit to Jeremy Tammik. https://jeremytammik.github.io/tbc/a/1456_bounding_section_box.html
/// and contain the given point.
/// </summary>
public static void ExpandToContain(this BoundingBoxXYZ bb, XYZ p)
{
bb.Min = new XYZ(Math.Min(bb.Min.X, p.X), Math.Min(bb.Min.Y, p.Y), Math.Min(bb.Min.Z, p.Z));
bb.Max = new XYZ(Math.Max(bb.Max.X, p.X), Math.Max(bb.Max.Y, p.Y), Math.Max(bb.Max.Z, p.Z));
}
/// <summary>
/// Expand the given bounding box to include.
/// Credit to Jeremy Tammik. https://jeremytammik.github.io/tbc/a/1456_bounding_section_box.html
/// and contain the given other one.
/// </summary>
public static void ExpandToContain(this BoundingBoxXYZ bb, BoundingBoxXYZ other)
{
bb.ExpandToContain(other.Min);
bb.ExpandToContain(other.Max);
}
public static Outline ToOutline(this BoundingBoxXYZ bbox)
{
return new Outline(bbox.Min, bbox.Max);
}
public static CurveLoop GetBaseLoop(this BoundingBoxXYZ bbox)
{
XYZ p1, p2, p3, p4;
p1 = bbox.Min;
p2 = new XYZ(bbox.Min.X, bbox.Max.Y, bbox.Min.Z);
p3 = new XYZ(bbox.Max.X, bbox.Max.Y, bbox.Min.Z);
p4 = new XYZ(bbox.Max.X, bbox.Min.Y, bbox.Min.Z);
var loop = new CurveLoop();
loop.Append(Line.CreateBound(p1, p2));
loop.Append(Line.CreateBound(p2, p3));
loop.Append(Line.CreateBound(p3, p4));
loop.Append(Line.CreateBound(p4, p1));
return loop;
}
public static Solid ToSolid(this BoundingBoxXYZ bbox, SolidOptions options)
{
var loops = new List<CurveLoop>() { bbox.GetBaseLoop() };
var d = bbox.Max.Subtract(bbox.Min);
return GeometryCreationUtilities.CreateExtrusionGeometry(loops, XYZ.BasisZ, d.Z, options);
}
public static Element ToDirectShape(this List<Solid> solids, Document doc)
{
Element model = null;
if (solids != null && solids.Count() > 0)
{
using (Transaction t = new Transaction(doc, "Create OctTree Solids"))
{
var geomObs = solids.Select(x => (GeometryObject)x).ToList();
t.Start();
var ds = DirectShape.CreateElement(doc, new ElementId((int)BuiltInCategory.OST_GenericModel));
ds.SetShape(geomObs);
ds.SetName("OctTree");
model = doc.GetElement(ds.Id);
t.Commit();
}
}
return model;
}
}
Of course if you have a really big model or set the recursion too high this will run for a very long time. I would recommend a similar size of model and not to go higher than 7 for the recursion – the Octree itself isn’t really the issue, but the geometry querying/creation. Also, in reality, you wouldn’t create a Octree each time you run, instead you would run once and cache the Octree and then do what you need with it when you need it.
Hope you found this interesting and maybe useful at some point! Thanks for reading! 🙂
danimosite.wordpress.com 
Leave a Reply