Octree implementation for triangular mesh and particles
c++, collision, octree, particles, space-partitioning
Solution
Inserting triangles into an existing Octree should not be too different than creating a new Octree and inserting them into it. The only thing which is critical here is to make sure that your existing Octree covers a 3D space which is guaranteed to include all the triangles.
Other than that, regarding the insertion itself, basically I would recommend implementing a two-step insertion where in the first step you use some quick test to see whether a triangle may be contained in a certain cube, and in the second phase (in case the first has passed) you actually do a proper calculation to see this.
One such of quick test is getting the bounding box of the triangle (from the minimum x,y,z of all points to the maximum x,y,z of all the points) and comparing that box with the one of the octree (if both coordinates of the triangle box on the same axis are not inside the range defined by the octree box and are both on the same side (both below or both above), then it's definitely outside).
Obviously, once you discovered an intersection between a triangle and an Octree box, you should repeat this test for all of it's child boxes.
There are also other places in the algorithm to make this more efficient (such as sorting boxes and triangles by x,y,z and then doing a check which only considers relelvant boxes), but it depends on the level in which you wish to optimize.
Problem
I am currently working in an efficient calculation engine for particle simulation both in CPU and GPU. I have been working lately in octrees and I managed to write a working version of octree for particles in space and also efficiently handled their collisions. Now I have to insert the triangular mesh(STL object) in my octree so that I can handle collision between particles and triangles of object too. I am confused how shall I insert the triangles to my already created octree in an efficient way? Please suggest methods to achieve this. If this helps, I am working with C++. Thanks already.