I would suggest... start with a new application. Push 100 points into a 100x100 byte[] at random. That array will be something like 10000 bytes.
Play with the Morton-ordered basic `Dictionary` or `unordered_map`. You can store the same points as in the array, but for just over 100 (300 if you use ushort keys) bytes. So this already shows you why spatial hashes are preferable to arrays.
I recommend these approaches to you (whether manual Morton index + `Dictionary<int, Vertex>` OR a 3rd party spatial hash lib) but I cannot _guarantee_ the performance impacts that it will have.
You need to know that hashmaps (all, whether spatial or normal ones) have something like O(1) access times, but you MUST do your own research on the one you choose.
I am only advising you with how I would do this - I cannot guarantee the performance.
Now, you talk. Tell me how you see yourself doing this, or problems you may have with it. (assume we have already found the right spatial map from some GIS libary, and you are ready to start using it.)
So in other words, you know what the octree looks like, but now you need to push ALL its relevant vertices into the hash.
This is easy to do, because even if you (tried to) push a vertex in 2x, 4x or 8x at the same location, the spatial hash would only store one (the last one) that wash pushed in. You already know this is how `map`s work.
But what this approach implies is that you will need to pre-calculate ALL vertices of the entire octree before you begin - and store them, by (x,y,z) key - in that spatial hash.
OR, you can possibly also pre-allocate a large hash of a certain number of bytes / megabytes, and then you can change it as your game makes modifications to the terrain etc. Of course, this will have a cost compared to a smaller, statically-allocated spatial hash.
...will all be stored either in the same bucket, or buckets that are located very close together in RAM (and in L3 cache, and maybe in L2 cache, and possible in L1 cache).
What it will do is look at the spatial key (made from x,y,z) and IF that key is near to another key in the spatial sense, then it will put them in buckets that are stored CLOSE together.
a normal unordered_map like we use above, has an internal bucket system that will actively try to distribute a, b, c VERY far away from one another. It actually WANTS them distributed far apart, as this makes the map's performance better for most common tasks like, say, a phonebook.
But in a spatial hash we are dealing with locations in space, and locality is very important to us (especially for collision detection), so our hash function will not change the distribution of the inputs."
"...for a normal hash table, a good hash function distributes keys as evenly as possible across the available buckets, in an effort to keep lookup time short. The result of this is that keys which are very close (lexicographically speaking) to each other, are likely to end up in distant buckets.
1. Struggle to get that cache working with a totally new kind of data structure (octree) 2. Use what I suggest which can work with ANY spatial data structure (BSP tree, quadtree, octree, KD-tree, uniform grid...)
OK - I don't - because I haven't worked with Transvoxel before. Maybe you can send me a screenshot - it would be interesting to see. But it's not important in terms of my answer that I wrote today.
Because this form of cache is not _necessary_. It is just one way to optimise the problem. Instead you can have a global spatial hash of all indices. This is how I do things in my projects.
Don't mistake me - the rolling cache is clever - but you are using a random-access octree now and it will be MUCH MUCH MUCH more difficult to make that rolling cache work with locales inside an octree.
