Transvoxel (trshmanx)

Engineer

16:00

Hi @trashmanx. Some questions to save some time:

1. Are you adapting someone else's code or are you writing a fresh implementation of Transvoxel?
2. Why do _you_ think I'm recommending a spatial hash as an alternative?

trshmanx

1. Partly mine, partly adapting

2. No idea right now.

Engineer

OK. Let's talk about the rolling cache in your question.

Just explain to me briefly how you see that working, so that we're on the same page, then I'll explain some things to you further.

*explain in a geometric / spatial sense what the cache is doing

trshmanx

Rolling cache Reuses vertices from previous cell(s), by reusing indices

Engineer

...which previous cells?

..where are they?

trshmanx

When you iterate like this

```

for (uint64 z = 0; z < config.size/config.maxResolution; z++)
{
for (uint64 y = 0; y < config.size/config.maxResolution; y++)
{
for (uint64 x = 0; x < config.size/config.maxResolution; x++)
{

Previous cell is -1

Engineer

16:08

-1 in which axis

all of them? one of them?

trshmanx

It comes from lookup tables

First they get edge code ushort edgeCode = Tables.RegularVertexData[caseCode][i];

Engineer

Alright, wait. Let's skip this question and go up and out to concepts.

For WHAT are they using a small, rolling cache? To store what?

(I'm asking you these questions so that we can be clearly on the same page and work from there. So I'm now going up to a higher, conceptual level. Why do we use caches?)

trshmanx

In the cache Indices are stored

Engineer

indices to... what

trshmanx

To vertices

Engineer

16:13

OK. And why are we using a CACHE for this, not just, say, a 3D array?

by which I mean - a 3D array storing all of the octree's vertices?

trshmanx

Memory

Engineer

Memory is one reason, probably the lesser one.

SPEED is actually the reason.

trshmanx

ALso

Engineer

That is also why CPU Caches and GPU caches exist. SPEED.

OK, so the definition of a cache is like this...

"A small subset of the overall data, which allows us to work on that subset QUICKLY"

Now here's the thing about Transvoxel. The cache was only an improvement for speed purposes.

But somewhere in Transvoxel's code there must be a list / array / collection of ALL the vertices contained in that octree? Not just a subset? But ALL?

Or is that not so? Are we calculating the vertices on the fly?

If there is NOT a collection - then the sparse spatial hash will be that collection.

ALSO, the sparse spatial hash will improve access speed to get those vertices and work with them.

trshmanx

The basic examples I a saw do not use a tree. They just loop over a regular gird

What makes their cache work

Because every next next cell is close to previous ones and can barrow Indice

Engineer

16:21

Right. And by borrowing the index we save time to get the SAME vertex.

But there is another way.

trshmanx

Its not just processing speed

Engineer

Correct.

trshmanx

You also have less Vertices

As you reuse them

Engineer

But if you didn't have the cache, you wouldn't have vertices AT ALL. Right?

Because there is no master collection of all vertices?

Only the cache

The cache is having the values calculated into it, as we move forward during the algorithm. Next step, new values in the cache... etc. etc. etc.

Right?

trshmanx

its like if(cache){ take indice from cache }: else { calculate&insert new vertice+indice }

Engineer

16:24

Right. So again - there is no global list or collection of ALL the vertices in the world / octree / uniform grid

trshmanx

New but, in same location

Engineer

OK, do you know how that data access pattern looks, spatially speaking?

Do you know how the cache looks if you were to highlight everything that it contains at a given time, and were to render that in 3D on your screen?

trshmanx

Yes I feed the final vertices and indices to arrays, that are later pushed to mesh object that creates the geometry on GPU

Engineer

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.

Even if you get the cache working, it may be sub-optimal in terms of your CPU cache - which is MUCH more important for performance.

...unlikely that it will be, since I'm sure the Transvoxel guys knew what they were doing.

So your choice:

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...)

???

trshmanx

github.com/BinaryConstruct/Transvoxel-XNA/blob/…

Here is some old implemntation

Very relaying on original doc

But I agree, using this Local cache with octree is almost impossible

Engineer

16:32

OK, let me know if / when you have further questions on the spatial hash structure.

trshmanx

"global spatial hash of all indices" > what is that?

Like in code?

Engineer

OK let's start with a naive example of a spatial hash...

This is something I sometimes do when I don't worry about memory use but NOT CPU cache performance.

We can create a key into a standard unordered_map like this (sorry, C++ is not my first language, I am more with C, C#, and JS these days).

uint32 key = (z << 20) | (y << 10) | x;

...or change the order as you see fit.

`map[key] = vertex;`
...where those x,y,z used to create the key are `vertex.x` etc.

Is this pattern familiar to you so far?

trshmanx

There is a lib (libmorton). It pretty fast converts 3D coordinates into a Morton code

Engineer

Please - remain focused. Is this pattern familiar to you?

trshmanx

Yes. I used it until I read that hashMap lookups and inserts are slow

Engineer

16:37

Right. Access will be slow, because the buckets in which the vertices are stored, are not near to each other in memory.

This means the CPU cache has to keep refreshing during long sequential reads, AKA "cache miss"

trshmanx

hmm makes sense

Engineer

So let me just clarify that from the article which I linked in my answer...

"...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.

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."

So let me give you a simple example of this...

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.

It will do the same with j,k,l

or p,q,r

or x,y,z

If those are used as the KEY

BUT...

A properly implemented spatial hash is implemented differently under the hood.

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.

So for example, for 3 points / vertices

0,3,1
1,3,1
0,2,1

...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).

trshmanx

Ahh, makes sense

So how do I start implementing proper spatial hash?

That works good with Morton codes, for example

Engineer

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.

"before you begin" might simply mean "before you render, but after the game logic of the first frame of your game is run"

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.

trshmanx

Hmm, ok

Engineer

16:48

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.)

Questions time :)

trshmanx

Well by converting all octree calculated vertices to Morton code and storing in map?

ANd that makes it spatial?

Engineer

OK, not as such, no. You _may not need_ to do the morton ordering yourself.

Whatever spatial map implementation you choose, will have its own way of taking in the (x,y,z), e.g.

map(x,y,z)
OR
map(vector3)

etc.

The spatial map should handle that side for you.

So you will just say something like... and I will write this in C# style...

trshmanx

AH, so I have to search for some lib

Engineer

`var map = new SpatialHashMap<Vertex>();`
OR
`var map = new SpatialHashMap<SpatialKey, Vertex>();`

something like this.

And then your assignments and retrievals as usual. But all the difficult stuff, it SHOULD do inside that class.

Correct, yes, you should.

You can start with the morton-ordered approach I give you above - if you like. It is quite easy to do.

But the performance may be poor (I don't know how many thousands or millions of vertices in your octree)

And so this brings me to something else...

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.

O(1) amortised - that means almost always O(1) but there are cases where it can be much worse (rare cases usually).

https://cs.stackexchange.com/questions/249/when-is-hash-table-lookup-o1
https://stackoverflow.com/questions/16068151/c-stl-map-is-access-time-o1
https://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1

...there are countless discussions about this online.

If you can find a "perfect spatial hash" (google) that will be best for you, I think.

trshmanx

Ok, will try to dig into this

Tnx

Engineer

17:05

You're welcome. Couple of final things:

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.

Just the size of that array makes the access time much slower.

Have a good one and hit me up here if you have further questions.

P.S. for 3D array, that would 100x100x100 = 1M bytes just to store 100 points.

trshmanx

Ok

Transcript for

Transvoxel (trshmanx)