Jump to content
  • Advertisement
Sign in to follow this  
Anfaenger

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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:

https://www.reddit.com/r/math/comments/1vfxk3/is_there_a_3_dimensional_space_filling_spiral/

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!