devNotes 4-23-16 hex alignment and placement






Spatial culling


Spatial culling might help you out here. There are many ways of doing this, but one of the more popular ones is probably the Octree. The idea is to store information in the tree about which triangles belong to which nodes. This obviously has a setup phase, but once the Octree is populated, getting the actual nearby triangles is much easier. Say you have triangle #379, and you want to find triangles that are close to it; you’d check which nodes that #379 is overlapping and you’ll find all potential matches. So you’ll get a subset of the triangles to work with, probably a few orders of magnitude less, which should quicken up your neighbor tests considerably.

Well if the triangles move around too much, then the cost of building the Octree might weigh out the benefits of fast lookup. But look at it this way. Say you have 1000 triangles and need to check them against each other in your current solution. That’s 1000*999 tests. Almost a million tests. With an octree, you’d probably do 2-3 tests per triangle to build the tree. That’s 1000*3, 3000 tests. Then during the lookup, you’d have to access nodes, so that’s another 3000 tests, and maybe inside each node there are 15-20 triangles so that’s another 20000 tests. From a rough guesstimate, you’re down from 1000k to 26k tests. But it’s also a lot of memory management since you have to move around elements…


Initial Generation using ICO_TREE_GENERATOR