search

mrdoob / three.js

JavaScript 3D Library.
https://threejs.org/
MIT License
102.71k stars 35.38k forks source link

THREE Octree? #1711

Closed collinhover closed 12 years ago

collinhover commented 12 years ago

Hi guys!

I've been developing a game, which is going great thanks to the help of THREE, but for several months now I haven't been able to address a serious performance issue in the physics/ray-casting. I'm using a super simple ray-casting based physics system with a modified version of the old THREE.Collisions code which you all took out. I'm using the collisions code mostly for performance reasons, as using Ray's cast scene I can't go above 1 dynamic object at ~30 fps, vs at least 10 dynamic objects at ~60 fps with the collisions system. Regardless, because I have such a high geometry count (my fault), both methods are much slower than they could be. At the moment I've got a world mesh that is roughly 3000 - 6000 faces, where I believe (I may be reading the code wrong) that all of the faces in the mesh are checked every frame.

Do you all think I can use a dynamic octree, within the context of THREE, to improve performance? Before I create anything like that, does THREE have it already? I looked around, and I can't find any THREE classes that have similar functionality, though you all have mentioned it in a few other issues relating to particle systems. For reference:

libe commented 12 years ago

Hi,

I noticed too that ray picking code is not really optimized as it take a linear time with the number of triangles. I badly need a Octree or better a Kdtree...I am a bit lazy in porting a C++ one I have written before...:)

collinhover commented 12 years ago

Update! I am working on a Octree that utilizes THREE vectors and assumes objects with THREE object3D structure. After some research, I decided to go with Octree as it seemed that a dynamic Octree (i.e. constantly modifying and rebuilding subtrees) may be better for performance than a kdtree, but I could be wrong.

For now, it is partially reliant on modules within the game I'm working on, but once it is fully working I will edit a version to make it independent. The in-progress octree (dynamic splitting and merging work as of this writing, growing/shrinking coming next) can be found at: https://github.com/collinhover/kaiopua/blob/master/src/web/assets/modules/core/Octree.js, and if that link doesnt work, search through the source files at: https://github.com/collinhover/kaiopua

collinhover commented 12 years ago

creating new feature issue for finished version (see: https://github.com/collinhover/threeoctree )