I have a huge number of static triangles forming the collision mesh of the world. I’m currently using a quad tree here, but it’s very slow. There are two main problems I want to solve right now:
- Using a quad tree means that it works the best for flat levels, but we’re planing on making levels with more vertical movement. Therefore, an actual 3D structure would be preferable.
- The current quad tree is slow as hell. In some extreme cases the quad tree query takes up 80% of the CPU time of the game since Kai helped optimize JOML for the actual collision response for the triangles (thanks Kai!).
It seems like the biggest problem right now is that simply traversing the quad tree is very slow. Finding an alternative data structure sounds like a good idea.
- Octree: Well, supports 3D but will be even slower to traverse.
- 2D grid: Still “flattens” the data structure, won’t work well with vertical levels. Also, the triangles are arbitrarily big and should preferably not have to be split up.
- 3D grid: Sounds like a great idea, but the triangles are arbitrarily big and should preferably not have to be split up.
- BSP tree: Not entirely sure how this would work, but I get the feeling that the “linked list” of nodes in this case would be even higher than for a quad tree, reducing performance even more.
- ???
Fixing a 3D grid to work with arbitrarily large triangles sounds like the absolute best solution here, but I can’t figure out how to make it work. Duplicating triangles into all grid cells they overlap wouldn’t work unless there’s a way to avoid processing the same triangle once (randomly doubling the collision response of one triangle would break physics). Marking triangles as processed would be hard to multithread, and keeping track of which triangles that have been processed is costly to check against.
Any ideas? :clue: