Some questions about octrees & collision detection

[Raswr]

Hello again 

I've been playing with collision detection octrees lately, they are quite interesting structures. This is going to be more of a learning thread, not a technical question. I have a big terrain (2500 triangles) and asigned a 10 depth octree to it (collision mode only). I was amazed at how fast it tests collision using sphere collision on my character. When I get close to that terrain, fps only fall from 57/58 to around 54 or 56 with such a big structure, especially on a phone!. It would be nice to know how this works a bit more (maybe not a completely jpct-ae related question, if it doesn't belong here, i'm sorry, just delete it).

I've been reading about octrees and they recursively subdivide a bigger space in the shape of 8 cubes/bounding boxes. But how can the collision detection system calculate this so fast? I mean, a 10depth octree can get really complex and testing against 8 nodes at every tree level should damage performance by a lot. I guess there are some optimizations but still, I can't believe that these sphere vs triangle collisions are calculating so fast on such a big mesh. Also, given a certain mesh, is there a method to know the optimal depth/max polys for the octree?  I would appreciate any insight on this topic, I'm really curious at how this works

[EgonOlsen]

Testing against the nodes is almost trivial. It's a simple primitive (sphere, ellipsoid, ray...) against axis aligned bounding box test, which is pretty fast. It's not much slower than testing against a single polygon, so even at a depth of 10, it's not such a big deal compared to the alternative (testing agains all polygons in the mesh). BTW: In jPCT, the nodes are overlapping if needed to avoid polygon splitting.
There's no method to tell the optimal depth/polygon count for a tree/node. It's a matter of trial and error to find that out for your particular mesh. I tend to keep the polygon count in each node at around 500-1000. Anything lower usually doesn't help performance wise because (as you've mentioned), there is an overhead in traversing the tree and if it becomes too high, it might eat up the benefits of the tree.
Using the tree for rendering is another story, because it increases the number of draw calls and that will eat up the performance gain pretty quickly.

[Raswr]

Thanks Egon, I think I finally found good values for my mesh, by trial and error as you said, it's really really fast.

Thanks again