What's the proper way to build an octree for collision purposes?

Unity Engine
1

I tried making an octree, but it doesn’t work very well. The problem is that when an entity is partially in one octree, and partially in another, it gets added to both. What I want is to get all the entities that don’t fit evenly into a child octree, and compare all of those against each other.

Posdim is for holding the position and the dimensions of an Entity.
BoundingCube represents a cube with a certain size at a certain position.

EDIT: I just realized that I probably shouldn’t be destroying the tree and making a new one every frame…

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Octree {

    public static int octreesLoaded;

    public static short minimumOctreeSize = 16;
    public static short entityCountForSplit = 10;

    public BoundingCube boundingCube;

    public Octree parentOctree;

    public Octree[] childOctrees;

    public List<Entity> containedEntities = new List<Entity>();

    public Octree(Octree parentOctree, List<Entity> containedEntities, BoundingCube boundingCube)
    {
        this.parentOctree = parentOctree;
        this.containedEntities = containedEntities;
        this.boundingCube = boundingCube;
        octreesLoaded++;

        if (boundingCube.size > minimumOctreeSize && this.containedEntities.Count >= entityCountForSplit)
        {
            CreateChildOctrees();
        }
        else
        {
            CheckForCollisions();
        }
    }

    void CheckForCollisions()
    {
        if (containedEntities.Count >= 2)
        {
            for (int i = 0; i < containedEntities.Count; i++)
            {
                for (int j = 0; j < containedEntities.Count; j++)
                {
                    if (containedEntities[i] != containedEntities[j])
                    {
                        if (World.IntersectsWith(containedEntities[j].posdim, containedEntities[i].posdim))
                        {
                            containedEntities[i].RunCollision(containedEntities[j]);
                        }
                    }
                }
            }
        }
    }

        void CreateChildOctrees()
    {
        childOctrees = new Octree[8];
        List<Entity>[] entityArrays = new List<Entity>[8];
        for(int i = 0; i < entityArrays.Length; i++)
        {
            entityArrays[i] = new List<Entity>();
        }
        for (int i = 0; i < containedEntities.Count; i++)
        {
            if (InBounds(boundingCube.LeftBottomFront, containedEntities[i].posdim))
            {
                entityArrays[0].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.RightBottomFront, containedEntities[i].posdim))
            {
                entityArrays[1].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.LeftTopFront, containedEntities[i].posdim))
            {
                entityArrays[2].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.RightTopFront, containedEntities[i].posdim))
            {
                entityArrays[3].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.LeftBottomBack, containedEntities[i].posdim))
            {
                entityArrays[4].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.RightBottomBack, containedEntities[i].posdim))
            {
                entityArrays[5].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.LeftTopBack, containedEntities[i].posdim))
            {
                entityArrays[6].Add(containedEntities[i]);
            }
            if (InBounds(boundingCube.RightTopBack, containedEntities[i].posdim))
            {
                entityArrays[7].Add(containedEntities[i]);
            }
        }
        childOctrees[0] = new Octree(this, entityArrays[0], boundingCube.LeftBottomFront);
        childOctrees[1] = new Octree(this, entityArrays[1], boundingCube.RightBottomFront);
        childOctrees[2] = new Octree(this, entityArrays[2], boundingCube.LeftTopFront);
        childOctrees[3] = new Octree(this, entityArrays[3], boundingCube.RightTopFront);
        childOctrees[4] = new Octree(this, entityArrays[4], boundingCube.LeftBottomBack);
        childOctrees[5] = new Octree(this, entityArrays[5], boundingCube.RightBottomBack);
        childOctrees[6] = new Octree(this, entityArrays[6], boundingCube.LeftTopBack);
        childOctrees[7] = new Octree(this, entityArrays[7], boundingCube.RightTopBack);
    }

    bool InBounds(BoundingCube boundingCube, Posdim posdim)
    {
        if (posdim.Pos.x + posdim.Dim.x > boundingCube.Pos.x && posdim.Pos.x + posdim.Pos.x < boundingCube.Pos.x + boundingCube.size)
        {
            if (posdim.Pos.y + posdim.Dim.y > boundingCube.Pos.y && posdim.Pos.y + posdim.Pos.y < boundingCube.Pos.y + boundingCube.size)
            {
                if (posdim.Pos.z + posdim.Dim.z > boundingCube.Pos.z && posdim.Pos.z + posdim.Pos.z < boundingCube.Pos.z + boundingCube.size)
                {
                    return true;
                }
            }
        }
        return false;
    }
}
2

Providing you not allow duplicates in octree system, you can use overlapping octrees.
Means overlapping cube is a bit bigger and will partially overlap with its neighbors.
One of them take priority to assign your instance child octree, object, or value…

3

That earlier version wasn’t really working that well, so I rewrote a lot of stuff and the code looks way nicer and it works fine, but it lags like crazy for some reason, it can only handle about fifty instances rather than the intended fifty thousand or so.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Octree {

    public static int octreesLoaded;

    static short minimumOctreeSize = 16;
    static short entityCountForSplit = 10;

    BoundingCube boundingCube;

    Octree parentOctree;

    Octree[] childOctrees;

    List<Entity> containedEntities = new List<Entity>();

    int Life { get; set; }

    public List<Entity> UnreservedEntities
    {
        get
        {
            return UnreservedEntities1;
        }
        set
        {
            UnreservedEntities1 = value;
        }
    }

    public List<Entity> UnreservedEntities1 { get; set; }

    public Octree(Octree parentOctree, BoundingCube boundingCube)
    {
        this.parentOctree = parentOctree;
        this.boundingCube = boundingCube;
        childOctrees = new Octree[8];
        octreesLoaded++;
    }

    public void UpdateOctreeWith(List<Entity> givenEntities)
    {
        //Check if any work needs to be done, if so, then life will be set to full.
        if (givenEntities.Count > 1)
            Life = 60;
        {
            containedEntities = givenEntities;
            UnreservedEntities1 = David.CloneList(containedEntities);

            //Create or update children.
            UpdateChildren();

            //Deal with any remainder entities.
            CheckForCollisions();
            int childCount = 0;
            for (int i = 0; i < 8; i++)
            {
                if (childOctrees[i] != null)
                {
                    childCount++;
                }
            }
            return;
        }
    }

    void CheckForCollisions()
        //Checks for any collisions between anyn entities not taken by children and all the entities in this octree
    {
        for (int i = 0; i < UnreservedEntities1.Count; i++)
        {
            for (int j = 0; j < containedEntities.Count; j++)
            {
                if (containedEntities[i] != containedEntities[j])
                {
                    if (World.IntersectsWith(containedEntities[j].posdim, UnreservedEntities1[i].posdim))
                    {
                        containedEntities[i].RunCollision(containedEntities[j]);
                    }
                }
            }
        }
    }

    void UpdateChildren()
    {
        //Update children and create them if they are needed
        List<Entity>[] entityLists = new List<Entity>[8];
        for (int i = entityLists.Length - 1; i > -1; i--)
        {
            entityLists[i] = new List<Entity>();
            for (int j = UnreservedEntities1.Count - 1; j > -1; j--)
            {
                if (boundingCube.GetSectionByIndex(i).InBounds(UnreservedEntities1[j].posdim))
                {
                    entityLists[i].Add(UnreservedEntities1[j]);
                    UnreservedEntities1.Remove(UnreservedEntities1[j]);
                }
            }
        }

        for (int i = 0; i < childOctrees.Length; i++)
        {
            if (childOctrees[i] != null)
            {
                childOctrees[i].UpdateOctreeWith(entityLists[i]);
            }
            else if(boundingCube.size > minimumOctreeSize && containedEntities.Count >= entityCountForSplit)
            {
                if (entityLists[i].Count > 0)
                {
                    childOctrees[i] = new Octree(this, boundingCube.GetSectionByIndex(i));
                    childOctrees[i].UpdateOctreeWith(entityLists[i]);
                }
            }
        }
    }
}
4

Well, that is definitely bad :wink:
In contrast I had 500k cubes on octree with ECS. For which FPS drop was contributed by rendering.
** Octree in Pure ECS : Raycast Stress Test of 500k Cubes V3 **

Instead of reinventing weel, I suggest you look at
Nition/UnityOctree

Is not ECS but works well with OOP

1 Like