Two things should be said to preface this topic:

1. This question really pertains to any spatial partitioning data structure I can think of using, but currently it is the octree that's giving me trouble so I'll just go with that.

2. This is NOT a question about how octrees are implemented in order to achieve collision detection. It is about types stored in the octree and resolving collisions after the fact. I saw similar questions while googling and the answers deteriorate to that. All functionality regarding that is all right in my implementation (minus some needed optimization).

My current setup and issues:
Octree stores "SphereHull*", pointers to a culling data structure I use most often. This sphere hull is a member of any actor that wants to use the octree. Sphere hulls only are inserted into the octree, with their own transforms (that update when parents move) and they signal the parent if collision moved them, making the parent GameObject move accordingly. This is a lot of back and forth copying and is error prone if you forget to do it. Seems inelegant to me.
This is the first issue - I was squeamish about virtual functions in an octree itself so I went and made it SphereHull only which is ok for now but I'm not sure it will hold up, for reasons explained below. Actor itself CAN store any hull (using base pointer to Hull* class) but I can't use anything else with my octree yet. :(

Motivation to change it:

Octree then goes through all that jazz every frame, finds matching pairs and executes a fixed, static function on both (moves them apart). It is very rudimentary because it was tacked on as an afterthought when the primary challenge was to get the octree working. Basically - it's good that it's type agnostic but also it's really “stupid” and can't do anything yet but move items apart if they collide.

Now I wanted to start using it for light-to-object assignment, by intersecting light volumes with drawable items. Obviously, I do NOT want to collide lights in the same way… I must have a way to resolve different types of collisions (not just this, also projectiles, non-blocking trigger zones etc…) with different callbacks. It seems that virtual functions (or similar mechanisms) are the best way.

Proposed resolution:
I saw another implementation where every type that we want to insert into the octree has a function to resolve it's insertion into a node that it can override (base class OctreeMember ). This would let me basically use any of the hulls I want instead of sphere hulls only, big plus. It would also let me implement resolution callbacks on each type (also override OnCollide(HitResult)). It also doesn't require the often cumbersome updates of hull and parent transforms separately, it's all in one place.

The “please hep” section:
Is this how one would approach it? Use an OctreeMember interface (or whatever you would name it). I can then override this for every hull type quite easily as I have all the intersection tests programmed already, and use virtual calls to insert anything.

Also, should the stored type, whatever it is, contain the pointer to it's parent spatial node for easy removal? Right now I'm doing a search from _root for it first which is really wasteful and I think the node pointer is the right way.

J. Rakocevic said:
Now I wanted to start using it for light-to-object assignment, by intersecting light volumes with drawable items. Obviously, I do NOT want to collide lights in the same way… I must have a way to resolve different types of collisions (not just this, also projectiles, non-blocking trigger zones etc…) with different callbacks. It seems that virtual functions (or similar mechanisms) are the best way.

Taking lights or bullets as example, why would you want to insert them into the tree at all?
I would only do a bounding box query per light, and a point (or line) query fro bullet (trajectories). This way the tree has less nodes and is faster to update. But i may miss something…

About your question (which may eventually become obsolete if you consider the above), i would tend to have one more layer of abstraction. So the objects in the tree are just bounding boxes (or spheres), and store userdata which the suer code can interpret as a pinter to a base class object, or Entity ID, etc. The user code is then responsible to work from there. (Does not answer your question, but having a tree class independent from application is nice to have.)

Thanks for that suggestion. I have something similar in place right now for finding neighbours within a certain distance (for keeping distance between units while flocking) and it indeed works.

It inserts a sphere hull into the tree at the position of the unit, with radius equal to the distance at which units want to start moving away from each other. Vectors are created moving these units away from each other as a result. Run of the mill separation. This works similarly for tower range queries - find units withing range of tower (TD game).

The problem that I noticed is the following:
Every time I want to do this, a new sphere hull is created , inserted into the tree (traversal from root… I don't have instant insertion octree yet), and then existing members are collided against it, repeat as many times as there are units. If I created these sphere hulls before hand, they would collide as if they were physical objects during the per-frame collision check.

This is decently fast despite the traversal every time for now but I have a 100 units in the octree, plus some number of buildings. I fear it won't scale too well because octrees aren't really all that cache friendly upon traversal, and I have to make a “pass” through it every time. If instead everything was present at once it would resolve all nodes in one fell swoop, making up for less overhead.

Example (of what I think would fix the overhead, and why I asked initially):
Insert them all before hand (be it flocking ranges, as above, or lights, or triggers).
Do a pass through the tree once per frame, but enable different behaviour for different collided pair.

If I understand your advice - I introduce some extra user data that can indicate to my code what to do with the generated list of collided pairs later to resolve different type collisions? I already have pointers to owners in sphere hulls, I could extend it to something like that.

And then use the octree only to intersect bounding hulls, but separate the collision response to other code? Am I understanding this right?

You could store an array of stored types/spatial nodes, rather than searching from root, you could search the arr for results that were stored. I am not sure about the potential upkeep and the amount of searching that might go on from root, but it seems that moving the results away from the root might provide the benefit you are looking for?

If you are accessing the spatial nodes at the time of collision and need data right before them then get the parent node pointer for sure, but if you are looking to batch and apply functions to the set of spatial nodes obtained by the collisions then I think you would want that?

Best effort here, hope that provokes thought. I am personally very new to this topic.

J. Rakocevic said:
I fear it won't scale too well because octrees aren't really all that cache friendly upon traversal, and I have to make a “pass” through it every time. If instead everything was present at once it would resolve all nodes in one fell swoop, making up for less overhead.

Pretty much what i expected i had missed :) Too much time has passed since i have implemented finding colliding pairs myself, but i see you may be right. Just…

J. Rakocevic said:
Thanks for that suggestion. I have something similar in place right now for finding neighbours within a certain distance (for keeping distance between units while flocking) and it indeed works. It inserts a sphere hull into the tree at the position of the unit, with radius equal to the distance at which units want to start moving away from each other.

… this sounds like you insert a sphere just for the reason to find all objects it intersects. This is not necessary - you can just traverse the tree but skip nodes outside the sphere, and make a list of objects while doing so. That's what i mean with range query. Just to make sure you know this.

However, if the number of queries becomes large, inserting all queries and then a single ‘swoop’ to find all pairs should be faster. And as you already have this, why not using it.

J. Rakocevic said:
If I understand your advice - I introduce some extra user data that can indicate to my code what to do with the generated list of collided pairs later to resolve different type collisions? I already have pointers to owners in sphere hulls, I could extend it to something like that. And then use the octree only to intersect bounding hulls, but separate the collision response to other code? Am I understanding this right?

Yeah, but my point is only about abstraction nothing else. Pretty low priority goal for now and if at all, considering the complexity of your problem.

Likely the main question becomes how to avoid recording pairs you are not interested in.
There was a thread recently about this: https://www.gamedev.net/forums/topic/705878-understanding-how-a-collision-detection-system-should-work/
It has a link to some post introducing usage of bitmasks to make groups of objects that should collide or not. So you could make lights collide with scene but not with other lights, without resolving indirections or virtual functions already at this point.

…hopefully at least this is helpfull ;)

@JoeJ I just took a quick look at bitmasks but it looks like a fast way to do a lot of matching interesting types! Great, will try that.

As for the range query, it actually works like that (not really an insert) I just didn't really explain it well. It works like this, ran from the _root node, where sp is the “inserted but not really” sphere to check within, the list is populated on the run, and isEmpty() also checks if child nodes have anything (it's a recursive check which I should probably not do like this but instead run once per tree). I guess I could actually insert all then check if there are many, seems faster now that you said it I just never thought of that…

template<typename NeighbourType>
void findInNode(OctNode* pNode, const SphereHull& sp, std::list<NeighbourType*>& neighbours) const
{
	if (isEmpty(pNode))
		return;

	if(!Col::AABBSphereSimpleIntersection(pNode->bBox, sp))
		return;

	for (SphereHull* curHull : pNode->hulls)
		if ((curHull->getPosition() - sp.ctr).LengthSquared() < (sq(sp.r + curHull->r)))
			neighbours.push_back(curHull->_collider->parent);

	for (int i = 0; i < 8; i++)
		if (pNode->children[i])
			findInNode(pNode->children[i], sp, neighbours);
}

I guess a std::vector for the neighbours would do, and a real list is not necessary? Could be a lot faster, and reserving for, say 20 items could eliminate dynamic allocation during traversal.

Question: Do you implement finding pairs in a similar way?

I can think of two options: The easy one is doing just one traversal as above for each node that has content, so multiple traversals. (Optimization would be to search only left neighbours, because the right node cares to find the current already, and so forth)

The potentially faster one is very complex. Some kind of merged or parallel traversal of the tree just once (don't know if there is a proper word).
I have done this many years ago, and remember a bit better now. I used a loose octree and each node had pointers to it's equally sized or larger neighbour-node. That's 26 pointers, and likely total overkill. Complex to maintain when updating the tree.
The searching of pairs also was very complex, and i concluded all this complexity just to share traversal work is probably not worth it. But i never made a comparison.

So i wonder how you do it. I guess if there are no neighbour-node pointers any algorithm boils down to the same work than using just the easy option, because of constantly searching for neighbour-nodes?

Sorry for slipping to discussing ‘collision detection implentation’, but i got curious. It's the one application of trees i have the least experience with.

I was going to pool allocate all of that tbh (or use a vector with max size preallocated as you suggest) but it took a back seat to the stuff going on right now.

However I don't need to do any neighbour checks. I use Christer Erickson's book and his straddling setup where each object is inserted into the highest fully containing node. Although the tree can be top heavy, in practice it generally won't be and it tends to be quick for insertion, deletion and removal as objects only exist in one node at most. Also easier to think of than loose trees (I am a big fan of grid simplicity, this is more like it) and can be sped up by not storing AABB sizes which helps caching and tree size (apparently recalculating them is so simple that it's faster than fetching more data as cache gains win?). I still store the node AABBs for now but it might go away.

I was wondering why the functions were const void instead of const bool. Is this an optimization detail or security issue I am overlooking? I thought the best practice was to short circuit functions with true/false values? @
J. Rakocevic

I am a little lost on the current status of problem, the goal is optimize the findNode function within the OctoTree correct? Any other current goals or questions I am missing?

This function above simply looks for neighbours of a provided entity (aka anything withing the sphere hull parameter) and adds them to the list. It doesn't actually search for THE entity (I know it's named badly but this is a protected func so I didn't care too much, public functions have nice names and just call these on _root node for most of the functionality).

JoeJ and I wandered into something else over time so it's not really related to the original question, sorry if became confusing to follow for that reason.

Initially, the goal was to know what to do with collided pairs once we introduce different things such as trigger boxes into the octree, the above function is just an example of how to do it “by hand” - make a query and then work on the results later. I was originally asking if people rather do it by just colliding everything and resolving based on types like so:
if light + drawable → apply light to drawable (for passing to shaders later)
if rigidBody + rigid body → bump into eachother (block movement or similar)
if triggerBox + player → start cutscene
if projectile + actor → damage
etc. etc.
using double dispatch / function pointer maps etc.