Hi Everyone !
I’m creating a FPS (not COD but almost !), and i need to handle players collisions with the objects on the map, terrain etc…
I chose to use an Octree because of the good performance it offers.
In fact, each time i open my game, i generate an octree based on the map and its childs
Then i manage all the collisions with the octree and a capsule for each player which handles their position
I’m checking the intersections between the capsule and the octree on each frame.
Everything works great, but the problem is the time it takes to generate the octree.
I have a large map (a city), and the octree’s generation takes at least 30 secs.
The map is static so it’s kind of stupid to generate it again and again, because it will always remains the same.
That’s why i was wondering if it was possible to store it somewhere.
I’ve tried to store it as a JSON but it doesn’t work.
As i’m building a multiplayer game, i tried to calculate it in the back, and send it to the front with a websocket, or a basic http request, but the octree is too heavy for that.
Someone knows a way to do this operation ?
Yeah i can try it but i need to recode everything
Just for your information, i’m not reinventing the wheel as i’m just following the three js official example :
Okay, it wasn’t that hard finally.
Now my game loads with less than 2 secs
Thats perfect !
How did you solve you problem?!
Did you get the JSON export to work? curious…
Nah finally i gave up on the octrees as their construction was too long.
Now i’m using three-mesh-bvh which is much faster for detecting collisions, and also for generating decals on surfaces thanks to its raycast system.
You can try it if you want :
EDIT : Note it still takes a few seconds to load, but it’s only due to assets in the game (png, gltf etc…)
Before that, i needed to wait a 30s more only for the octree to be generated
I recommend storing an octree in a cool dry place, out of reach of children.
Sometimes it makes sense to store a spatial index, but in most cases like games - it’s typically faster to just rebuild it from scratch. Something like a morton code (spatial hash) bottom-up tree build is going to be ridiculously fast. That’s generally how raytracing GPU APIs do it.
However, if you are pressed to store a tree-like structure that references some objects. I recommend converting these references to integer IDs. In case of three.js - you already have an
id field on
Object3D that carries a unique integer value. So that might be a good start.
The tree itself can be stored in many different ways, one is to store a it as a flat list of nodes like so:
"children": [2,3], // references indices of other nodes in this list
"data":  // references IDs of objects stored in the tree
This is somewhat similar to how GLTF stores its data. For those curious, see spec.
I happen to have a need to store BVH data on occasion, when I do - I tend to go with binary serialization. My current BVH implementations ( yes, plural ) also work on binary data directly (
ArrayBuffer) so serialization and deserialization is as simple as just reading/writing an
ArrayBuffer and you’re done.
The advantage is obvious - you don’t need to copy data into a different format, you don’t need to “build” a new object structure etc. You just reference that binary data directly and use it, no parsing or any other complex logic required.