• Create Account

# Voxel terrain move

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

### #1Str3jda  Members   -  Reputation: 249

Like
1Likes
Like

Posted 25 February 2014 - 02:43 AM

Hi,

I know there's already plenty of tutorials how to implement voxel terrain, but afaik none of them properly explains how to update lods during camera movement. If anything, they only tell about octree and thats it. But how? If I were to have each lod as depth level in this octree, how do I avoid having low-res lod rendered at camera position? Or am I missing something? I wonder if there's some simple solution.

I'm already able to render terrain quite nicely, but before I get into "transition cells", I'd like to tackle with this first and I can't seem to find any usable resource on this topic:(

Thanks

System programmer at 2K Games

### #2Hawkblood  Members   -  Reputation: 723

Like
0Likes
Like

Posted 25 February 2014 - 08:44 AM

I'll be watching this post. I want to know the same thing. I have some ideas, but emplementing them just to find out they are wrong would be a waste of my time. *here's me hoping someone will respond*

### #3slayemin  Members   -  Reputation: 2430

Like
2Likes
Like

Posted 25 February 2014 - 04:48 PM

Let's say you've got millions of voxels in your terrain environment. You realize that there's a performance issue with rendering them at a high level of detail, so you want to render the nearby voxels at a lower level of detail if they're far away from the camera. This is the gist of what we're trying to do. But we don't want to spend a huge amount of CPU time trying to figure out which level of detail we want to use for a voxel either! In the most brute force method for the algorithm, we'd calculate the distance from the camera position to the voxel position. If that distance exceeds a set threshold, you drop the LOD by one. However, if we used the brute force method, we'd be calculating the distance between the camera and all million voxels (which comes with an expensive square root) and any performance gains in switching to another LOD would be much lower. So, we want to keep the same idea for calculating distances with voxels, but try to use fewer distance computations.

Here's where Octrees come in handy, and that's why you are reading about them. You can divide your terrain into chunks of blocks, say, 16x16x16 (use powers of 2 if you can). Each chunk can be inserted into your octree. When you're going to calculate the camera distance, you could instead calculate the camera distance to the octree bounding regions and set the LOD of all contained objects to a preset value. This would help you reduce the number of distance checks, and would also scale very well with any number of game world objects (I assume you're going to have more than just terrain).

I don't know if its relevant to you or not, but there was a white paper a while back on rendering terrain using geomipmaps. The author had an interesting technique for deciding when to switch to a different LOD which was not based on camera distance, but rather on how much the terrain would pop if you transitioned it to a lower LOD (2.3.1). He basically measures the vertical change in "pop" between one LOD and another in screen space according to the camera viewing angle, and then switches the terrain LOD if the pop is below some acceptable threshold (ie, 2 pixels). I implemented a variation of this myself and I like the results.

Here is my code for that:

/// <summary>
/// This calculates the maximum amount of vertical error when switching from one level of detail to another.
/// </summary>
private void CalcError()
{
for (int LoD = 0; LoD < 4; LoD++)
{
int stepSize = (int)Math.Pow(2, LoD + 1);
float d_max = 0;

//traverse horizontally
for (int z = 0; z < m_settings.TileCount; z++)
{
for (int x = 0; x < m_settings.TileCount; x += stepSize)
{
Vector3 p0 = m_verts[x + (z * (m_settings.TileCount + 1))].Position;
Vector3 p1 = m_verts[(x + (stepSize / 2)) + (z * (m_settings.TileCount + 1))].Position;
Vector3 p2 = m_verts[x + stepSize + (z * (m_settings.TileCount + 1))].Position;

Vector3 P = (p0 + p2) / 2.0f;        //the phantom position of p1 is just the average of P0 and P2
float d = (p1 - P).Length();         //find the error difference between p1 and the phantom point
if (d > d_max)
d_max = d;
}
}
m_max_dy[LoD + 1] = d_max;            //this is the most error we'd get if we switched from LODX -> LODX+1
}
}


On screen and in the game, what ends up happening is that we try to use the lowest possible LOD we can get away with without getting unwanted popping artifacts. So, if you're pointing your camera straight down and you're viewing the terrain from above, the very bottom terrain chunk will be at a very low LOD, but you can't really tell since the vertical portions are not really coming into play based on your viewing angle.

Eric Nevala

Indie Developer | Dev blog

### #4Str3jda  Members   -  Reputation: 249

Like
0Likes
Like

Posted 25 February 2014 - 05:40 PM

Ok, seems reasonable, but I'm not sure if it's applicable to my problem. I'd like my terrain to be infinite (to some reasonable extent), therefore I have to work only with camera position a viewing distance when building octree (which I presume have to rebuild every time I move enough). This wouldn't work that well with your approach I think:(

I understand with static octree, deeper we get in the tree when rendering, smaller real world sized chunks are rendered as higher-res lod (I presume blocks 16x16x16 are local size, which scales up with lower-res lod right?)

Btw. geomipmaps seem interesting, I will definitely read the article and see If I can use it somehow;)

My initial idea was to somehow enhance geometry clipmaps, but making this algorithm work with voxels made my head hurt Maybe it's not possible, I don't know, it just seemed like exactly what I'd like to have.

System programmer at 2K Games

### #5slayemin  Members   -  Reputation: 2430

Like
0Likes
Like

Posted 25 February 2014 - 07:12 PM

So, you're procedurally creating your terrain... I think you could still get away with using an octree. The benefits of being able to use a O(LogN) search algorithm are too high to discount it too readily. If the camera moves and you have to update the octree, you don't necessarily have to rebuild the whole entire tree. You just have to add in the new section of terrain which was created and remove the section of terrain which is no longer visible. This may be a bit unconventional, but it could be worked out. The idea is that the octree gets populated with the new chunks which are procedurally generated and it dumps the chunks which are no longer needed. You *could* even do this by reusing existing memory by recycling allocated tree branches (like memory pools), but that may add a bit too much complexity without enough of a performance pay off to be worth the effort.

The other big pay off with Octrees is that view frustum culling becomes very fast and easy.

I like that article you linked. I hadn't thought of storing LOD in various levels of the octree -- I'll have to think about that a bit more. I was storing LOD in the chunk itself and letting the chunk decide what LOD it should set itself to based on vertical error. Specifically, I'm using the "Tiled Blocks" technique they're referencing and the code I posted above does the calculation for the screen-space geometric error they're talking about.

Anyways, these articles are talking about terrain being rendered with tesselated triangle meshes. Making it work with voxels shouldn't be too much of an extra step (I've even been considering this for my own terrain system). I think the approach I'd take is making cubic "chunks" of 16x16x16 (or some other number) and figuring out how to render the visible faces on that chunk of voxels. The general principle remains the same. I suspect that it could be done very fast with some sort of ray casting technique in HLSL, but I'd have to do a lot of R&D on that.

Eric Nevala

Indie Developer | Dev blog

### #6Hawkblood  Members   -  Reputation: 723

Like
2Likes
Like

Posted 25 February 2014 - 07:20 PM

(I presume blocks 16x16x16 are local size, which scales up with lower-res lod right?)

The idea behind octtree/quadtree is to have a varied size (scale) not vary the number of vertices. For instance, up close the 16x16x16 could represent a block that is 16meterX16metersX16meters in size and a lower level of detail the same 16x16x16 would represent a larger area like 32metersX32metersX32meters-- this is double the size in each direction. For a map (terrain) the expansion of the vertical axis wouldn't be needed as much as the horizontal axis' unless you have a volumetric approach to your terrain where even the empty areas of the sky are represented.....

The "geometry clipmaps" is not voxel, or do you mean to modify it into something "voxel"?

### #7Str3jda  Members   -  Reputation: 249

Like
0Likes
Like

Posted 09 March 2014 - 04:17 PM

What I still don't understand is how do you handle differently sized lod chunks when camera moves. If only higher-res chunk moves, then this chunks overlaps with lower-res chunk. At least, I don't expect you regenerate all the lods each move. Octree is nice to have to determine in what lod each block can be, but i still don't understand in what way it helps when moving. When there are 16x16x16 chunks for hi-res and 32x32x32 for lower-res chunks, how and when you move them? I presume regenerating chunks takes some time, it doesn't happen in on frame, so what exactly is happening during this transition, when chunks are somehow regerating and updating terrain. I don't want to see reapperaing large blocks of terrain all over the place:(

I understand how you build all lods on given position, but that's what I consider as "loading time specific", not what I want to do every camera move.

System programmer at 2K Games

### #8Hawkblood  Members   -  Reputation: 723

Like
0Likes
Like

Posted 11 March 2014 - 08:39 AM

http://www.brandonpelfrey.com/blog/coding-a-simple-octree/

Hopefully this will give you an idea of how it works.
You don't need two different resolutions (number of verts), you only need one. The idea is that the farther away the "cube" is from the camera, the larger in scale the mesh is-- with the same number of verts as all the other cubes.
Doing this on the GPU is still magic to me, so I'm still waiting for someone to illustrate "how" to do it.

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS