# Space filling curves for 'concentric' flood filling?

This topic is 907 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm writing a chunk-based voxel engine and I need to gradually load and grow the area around the player.

My chunks are organized in a 3D 'matrix' ('rolling' array with toroidal ('modulo') addressing) representing the visible (rectangular) region of chunks.

The 'matrix' is stored as a 1D array of chunks, each chunk contains its status, the mesh pointer, etc.

I decided to use a simple flood-fill algorithm for determining which chunks to load first after an empty world is created.

But a (non-recursive) flood-fill relies on a queue (for storing the next chunks to process) and performs 8 steps in each direction (with ugly checks, and most of them fail).

Is there a neat space-filling curve for linearizing the 3D 'matrix' which allows to visit chunks in a closest-to-far manner, starting from any given player position inside the cube? The curve should be reasonably simple and quick, and (of course) not 'intersect' already visited elements. Is there anything more efficient (or elegant) than hardcoded 'spiral curve'?

The advantage of using a space-filling curve is that instead of storing an array of chunks to be processed you could store a single value (e.g. the position of the last processed chunk encoded in an int).

(and I have trouble figuring out on paper how to code even the simplest 3D 'cubic spiral' curve.)

Edited by Anfaenger

##### Share on other sites

You might want to look into n-ary Gray codes  https://en.wikipedia.org/wiki/Gray_code#Special_types_of_Gray_codes

They define a hamiltonian path, which is what you are looking for

(3 bit binary gray code is a hamiltonian path of a cube, but if you want to fill further, you need 3 digits with higher values)

Edited by Olof Hedman

##### Share on other sites

If I understood correctly, Gray codes allow to visit vertices of the cube once,

but I need to walk over the whole surface of the cube.

I'm looking for a (bijective) mapping from integer points on the cube surface to single integers and vice versa (not necessarily a space-filling curve).

btw, it seems in 3D there are no space-filling spiral curves:

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013166
×