nition/unityoctree

A dynamic, loose octree implementation for Unity written in C#

unityoctree's Issues

Index Out of Range in "ShrinkIfPossible"

// We have children. Use the appropriate child as the new root node return children[bestFit];

I'm hitting a case where "bestFit" can still be -1 at this line. The culprit appears to be this case:

objects.Count = 0
children.Length = 8

Null Reference Error in "ShrinkIfPossible"

I am sometimes getting a null reference error in the function
public PointOctreeNode<T> ShrinkIfPossible(float minLength)

on the first line of this block
if (objects.Count == 0 && children.Length == 0) { return this; }

after calling PointOctree.Remove().

Attached is a screen of MonoDevelop hitting a break point in a test block I added. It appears that "objects" can have a count of 0 and "children" can be null at the same time. Note also that inserting this block appears to prevent the issue, but I'm concerned about what side effects it might have as I don't really have a good grasp of the inner workings here.

This occurs often but not always in my scenario (perhaps 30% of the time), and usually throws null reference errors for a number of frames before stopping. This is a somewhat elaborate project with a strong possibility of timing and chance influencing the scenario here.

I regret that I don't have a clean reproduction case for you :(

Main difference

Hello, thanks a lot for your example!

I have a question. What's the main difference between bound or point-based octree? I've read your documentation (and it's great) and code (sorry, I'm not good in C# so much) but I can't see the purpose...

Point-based octree seems better to me but what are the restrictions?

Thanks for your reply. Good work!

Possible bug with maxDistance

   bounds.Expand(new Vector3(maxDistance, maxDistance, maxDistance));

Shouldn't these be maxDistance*2, since Expand increases the size, but only 1/2 in each of 6 directions?

I noticed this while implementing a GetNearby(Vector3 point) version, not actually seeing a bug from it.

Nodes who have children shouldn't contain any OctreeObject

Hi Nition,
If I understand the code correctly, when adding an object into the octree, if the current node contains enough object, we create children and move all the objects a level deeper. But in "GetNearby" function, I found that if a node has children, it STILL contains all the objects. Its children will have copies of the same objects. Could you please look into this? Or am I misunderstanding anything here?

Getting started resoruces?

Hello, im interested in this repo. Can you provide some getting started scene or script where everything is setup for us newbros to just see setup. I need to crate octree that will dynamically update as objects are going through zones. I see this is possible with this but I'm unable to wrap my head around it. Thank you.

Update Position

No way to update the position of an octree, has an initial position but no way to change once set?

Performance Upgrades

• - Combine point and bounds logic
• - Object add method.
• - Object remove method.
• - Object move method.
• - Node splitting on-demand.
• - Branch based object count tracking.
• - Automatic merging of branches/leaves.
• - Custom intersection tests to avoid unity internal calls.
• - Get rid of dependence on unity's Bounds struct internally.
• - Instance pooling.
• - O(1) Object removal.
• - Implement queries into tree.
• - Implement queries from objects.
• - Eliminate recursive methods where plausible.
• - Documentation.
• - Clean up/write summaries.
• - Add queries to testing scene
• - Add queries to tree visualization

Scrapped:
Linear. Actually proved to be slower with current implementation.
Directional tree growth. Not really necessary. Proper implementation avoids this need.
Tree shrinking. As above.

ShrinkIfPossible bug

Hi,

the ShrinkIfPossible method is called and possibly a child node becomes root
because all the node's objects can fit the child octant.
Where the objects of the previous root go?
Shouldn't they be added to the child node in the ShrinkIfPossible method?

Feature Request - GetNearby(Vector3 point, int requestedResults)

Using the PointTree, would like a T[] GetNearby(Vector3 point, int requestedResults) method. This would return the requestedResults closest items to point in the tree.

I am going to take a crack at implementing this, but would also appreciate any suggestions/pointers for how one might go about doing this... (i have a "bad" version which simply calls GetNearby with increasing sized maxDistance values until you get the # of results you want)...

BoundsOctreeNode.GetColliding can be faster

When I was experimenting with the Octree I was able to get the search performance down by factor 10 when fiddling with the BoundsOctreeNode.GetColliding() internals.

Specifically:

• manually doing the bounds check (Unity Bounds allocates and is slow)
• caching the bound vectors in the node itself (Bounds.max and min are always created in the getter)
• and working with a pre-allocated list to fill in return objects.

Maybe this helps. Cheers, Jonas

public void GetColliding(ref Bounds checkBounds, List<T> result) {
    // Are the input bounds at least partially in this node?
    if (!bounds.Intersects(checkBounds)) {
        return;
    // ...
}

public void GetCollidingOptimized(Vector3 positionMin, Vector3 positionMax, ref int[] resultList, ref int resultIndex) {
    if (positionMax.x < BoundsMin.x || positionMin.x > BoundsMax.x) return;
    if (positionMax.y < BoundsMin.y || positionMin.y > BoundsMax.y) return;
    if (positionMax.z < BoundsMin.z || positionMin.z > BoundsMax.z) return;
    // ....
}

public struct BoundsOctreeNodeStruct<T> {
  public struct OctreeObject {
    public Vector3 BoundsMin;
    public Vector3 BoundsMax;
    // ...

How to initiate it?

Hello, I'm having trouble with initiating it and would appreciate some help with the first steps. I suppose this isn't easy stuff for newbies, but I still would like to give it a try if I could just get as far as adding objects (or vertices to be precise) to a boundsTree / pointTree.

I have created an octree:

Renderer rendy = gObject.GetComponent< Renderer>();
Vector3 rCenter = rendy.bounds.center;					
// Initial size (metres), initial centre position, minimum node size (metres), looseness
boundsTree = new BoundsOctree<Vector3>(15, rCenter, 1, 1.25f);
// Initial size (metres), initial centre position, minimum node size (metres)
pointTree = new PointOctree<Vector3>(15, rCenter, 1);

I just want to add the vertices of a gameobject's mesh to an octree. I'm not sure what values I need to use when adding/removing as presented here:

boundsTree.Add(myObject, myBounds);
boundsTree.Remove(myObject);

pointTree.Add(myObject, myVector3);
boundsTree.Remove(myObject);

I'm assuming I need to iterate through the mesh's vertices and then add them to the octree, but I'm confused about object type and "The bounds or point determine where it's inserted":

Vector3[] vx = myMesh.vertices;

for (int i = 0; i < vx.Length; i++)
{
    boundsTree.Add(objectType?, vx[i]); // Argument 2: cannot convert from 'UnityEngine.Vector3' to 'UnityEngine.Bounds'
    pointsTree.Add(objectType?, vx[i]); // 
}

Another thing is the OnDrawGizmos(): Must all octree references be made within the gizmos script? As I can't seem to figure out how to get the references to the boundsTree / pointTree otherwise.

• Erlend

ShrinkIfPossible method bug

The implementation of ShrinkIfPossible(float minLength) requires that there is only 1 child in the node, as mentioned in the documentation. However, the current implementation makes no such check and in some instances of node removal, some nodes that shouldn't be removed end of getting implicitly removed (this is basically a memory leak).

The fix is simple:

public BoundsOctreeNode<T> ShrinkIfPossible(float minLength) {
	// NEW CODE
	if (objects.Count >= 2) {
		return this;
	}
	// END NEW CODE

	if (BaseLength < (2 * minLength)) {
		return this;
	}
	if (objects.Count == 0 && (children == null || children.Length == 0)) {
		return this;
	}
//.... the rest of the code

Shrink Problem

When remove an object, my excute Shrink,
Shink will change the root node, but the objects in the old root losted.

has a fast way to update a Object?

Hello!if I want to update an object in octree,for example the object Bounds has update,maybe it should go to another octreeNode. I must call remove function and add function again? or another fast way to do this.

Point.Normalize is giving stack overflow

Hello.

Thank you very much for the code. In the "Pure C# Implementation" I am getting stack overflow issue when I just ask for Normalised vector (Point) of a Point.

I am missing something ?

Thanks in advance.

Create unit tests

Add example project

Does growing actually work?

If my initialWorldSize was not large enough to include all the points I added, the resulting Octree did not appear to always correctly store the points. Calling GetNearby with a ray at the position of the point and a small maxDistance did not always find that point.