Quadtree LOD terrain

[Dal]

I can't figure out how to get this to work in the playground, there's too many dependencies, but I've put a playable demo online at:

https://www.loudened.com/terrain/

I will probably only leave it there for a few days though so test it while you can

 

To be honest, I am starting to feel as though I will never be able to achieve the results I want in Babylon... I'm really struggling with the performance issues and it doesn't look like anyone is going to be able to offer any help any time soon, so I might just move to an engine with a working terrain solution already. :I

[Dal]

1 hour ago, jerome said:

Not sure I understand all your code. What is the main principle behind the hood ?

Do you create new chunkq of terrain on the fly ? how do you dispose the useless ones ? or do you re-use them ?

 

I would have used a different approach :

- to have a huge logical terrain, whatever its source : heightmap, perlin noise computation, etc... well something too big to be rendered with vertices but easily defined by a set of vertices (x, y, z), well like ribbon paths or arrays

- to have an updatable renderable mesh designed by a pool of different LOD stripes : imagine, say, three concentric squares (BJS grounds), the farthest with the lowest LOD, the closest with the highest LOD

- to shift the mesh vertex values along the logical terrain array according to the camera position in the World : the farthest square would be defined for example with 1 logical coordinate set every 100 ones, the middle one with 1 on 20, the closest with all logical coordinates (not pertinent values)

Just to say that each stripe picks its part of logical coordinates but not with the same density.

 

This would be some kind of "moving mesh" in the logical array, although immobile in the World, according to the cam moves and the mesh would be updated by the current logical coordinates.

So only a pre-defined updatable mesh, no allocation, no destruction, just vertex position updates (maybe uvs also) what is really fast

 

not sure I'm very clear

That was my first approach, but I couldn't get it quite working and since it was mostly on the GPU I couldn't figure out how to get collisions working either:

Then my second approach I tried a voxel terrain, but that one I couldn't solve the seams problem or decent painting:

Then this is my last approach, I decided to go back to the "basic" approach of simply using terrain quads and LODing them. which makes the seams problems easier to solve and makes it easier to use high quality texturing and normal maps.. but still, the performance just SUCKS.

I am really thinking I should give up on this stuff now... it seems I am not smart enough to solve this problem alone and there's not enough interest here to help with it. Unless anyone thinks they can assist I think I will just have to investigate other engines that already have good terrain implementations.

 

[jerome]

Actuallu I think there's a big interest here, but maybe we miss some information about the approach, some comments about what the code does exactly, how it is archtitured, etc

Not that easy to discover at once such a big feature ;-D

[Dal]

27 minutes ago, jerome said:

Actuallu I think there's a big interest here, but maybe we miss some information about the approach, some comments about what the code does exactly, how it is archtitured, etc

Not that easy to discover at once such a big feature ;-D

The approach is based on this XNA tutorial (although it's a bit different now):
http://www.dustinhorne.com/post/2011/08/24/XNA-QuadTree-Terrain-with-LOD-Part-1-Introduction

Some of the links on that site are broken but you usually just need to delete the ".aspx" extension from the URL to make it work.

 

A good start might be for you to follow that tutorial with my code, and see the differences I have made in the process... maybe you will also see what I did wrong

[jerome]

I'd like to try something, but I don't have much time these days :-(

[Dal]

I'm porting it to Haxe at the moment.... perhaps in the process it might end up running faster and I can also see how fast it runs under a C++ target for comparison.

 

 

[jerome]

my idea (quickly) would be to define such a mesh : http://www.babylonjs-playground.com/#24A3NV

with a better function on each circle radius : the radius should increase quick for the greatest circles

this mesh would be a immobile ground, updated with the logical ground height according the camera position

[TheDude]

Well it works great on a 2012 iMac anyways and they have core i5 which is closer to an average home computer at least, which is good. I guess?

[Dal]

1 hour ago, jerome said:

my idea (quickly) would be to define such a mesh : http://www.babylonjs-playground.com/#24A3NV

with a better function on each circle radius : the radius should increase quick for the greatest circles

this mesh would be a immobile ground, updated with the logical ground height according the camera position

Interesting approach.. I haven't seen that done before.  It would be tricky to page in the data though... with the approach I am using, it loads in new squares of terrain as you move around, and it will load in splat maps for each region in the same way. With your approach it would be hard to split out the heightmap/splatmap textures into distinct tiles, so you'd have to do something like work out which squares your circle covers and then load multiple textures and pick some of the data from each... might end up being more heavy.

[jerome]

Actually I'm thinking about a pre-computation of all the logical height and uv formulas like I did in getHeightAtCoordinates() with computeQuads under the hood, that stores some math function to return the height at any coordinate (x,z). I guess it would be possible to do the same, so to return a formula to return the UV at any coordinate (x, z) from the UV of the vertices fo the current facet (triangle). Not sure though

If not possible, I could then make concentric squares (aligned to the logical terrain quads) and the uvs handling will be then easy.

In my approach, the logical terrain is just a series (or array) of vertices (and uvs if any) whatever its size.. or even computed (perlin noise)

It's pre-processed (or dynamically) so the vertices are turned to facets and so some height (and uv) math function is associated to each triangular facet. Then we can get the height or uv for any (x,z) values. These returned values updates the circular ribbon what is the renderable terrain mesh 

 

[EDIT] another (bad) attempt : http://www.babylonjs-playground.com/#24A3NV#1

close to the center, there are small facets, so a big  LOD, far from the center, there are only large facets, so small LOD

[EDIT 2] this one is better : http://www.babylonjs-playground.com/#24A3NV#2

 

[Dal]

16 hours ago, jerome said:

Actually I'm thinking about a pre-computation of all the logical height and uv formulas like I did in getHeightAtCoordinates() with computeQuads under the hood, that stores some math function to return the height at any coordinate (x,z). I guess it would be possible to do the same, so to return a formula to return the UV at any coordinate (x, z) from the UV of the vertices fo the current facet (triangle). Not sure though

If not possible, I could then make concentric squares (aligned to the logical terrain quads) and the uvs handling will be then easy.

In my approach, the logical terrain is just a series (or array) of vertices (and uvs if any) whatever its size.. or even computed (perlin noise)

It's pre-processed (or dynamically) so the vertices are turned to facets and so some height (and uv) math function is associated to each triangular facet. Then we can get the height or uv for any (x,z) values. These returned values updates the circular ribbon what is the renderable terrain mesh 

 

[EDIT] another (bad) attempt : http://www.babylonjs-playground.com/#24A3NV#1

close to the center, there are small facets, so a big  LOD, far from the center, there are only large facets, so small LOD

[EDIT 2] this one is better : http://www.babylonjs-playground.com/#24A3NV#2

 

That's kinda what I have... but with squares not circles. All the possible verts and heights are precomputed and it just calcs which indices are used based on the distance...

The thing is, the size of the data is too large to store the large terrain all in memory at the same time... so I page in chunks of terrain as we move around, allowing practically infinite size. The big problem is that even just calculating the indices interating a quadtree seems too slow in my implementation.

I don't really want to start again at this stage - the theory for this one seems solid enough and is widely used in games out in the wild, I think there's just some inefficiency in the implementation that needs solving.

[jerome]

Quote

The thing is, the size of the data is too large to store the large terrain all in memory at the same time... so I page in chunks of terrain as we move around, allowing practically infinite size. The big problem is that even just calculating the indices interating a quadtree seems too slow in my implementation.

My idea is this one :

- decouple the logical terrain from the renderable mesh.

- the mesh (whatever squared or circular) is just updated on this positions (and/or uvs), not indices... always the same morphable geometry

- the logical terrain and the mesh share a coordinate reference, so the mesh can "slide" on the logical terrain, although immobile in the 3D World

- the logical terrain can be updated live, by downloading on the fly new parts of data, or by computation

Well, the idea is to NOT add or remove vertices/indices from the mesh, to keep it constant, just to morph it by updating its positions and to add/remove/compute data only the logical terrain

[Dal]

1 hour ago, jerome said:

My idea is this one :

- decouple the logical terrain from the renderable mesh.

- the mesh (whatever squared or circular) is just updated on this positions (and/or uvs), not indices... always the same morphable geometry

- the logical terrain and the mesh share a coordinate reference, so the mesh can "slide" on the logical terrain, although immobile in the 3D World

- the logical terrain can be updated live, by downloading on the fly new parts of data, or by computation

Well, the idea is to NOT add or remove vertices/indices from the mesh, to keep it constant, just to morph it by updating its positions and to add/remove/compute data only the logical terrain

Yeah that's roughly how my first approach worked... but I couldn't get it right. How would you texture it? You'd need a "logical" texture as well... so perhaps that means having a huge texture in memory, or you split it into smaller ones, but then when you "slide" between 2 different textures you need to load in 2 textures and pick some data from each... and maybe you could be on the border between 4 different textures at once, so you need to load and sample 4 textures....
The height data could be a similar issue... you have to fit the entire world into memory, even if you don't render all of it.

For my first try, I was keeping the mesh static and setting the vertices in the shader. It runs fast, but then the positions aren't stored in the mesh itself, so it starts getting tricky for physics and height picking and doing stuff like placing trees only where it is not too steep etc... really that calculation needs to be done in JS side I think, which is why I ended up coming back to the quadtree concept.

My latest approach loads a large amount of data but doesn't render all of it, it misses out more triangles the further away you get. That lets me have fairly big terrains, but I still can't load a really huge world into memory at once. A terrain that is 2km big, say 2048 x 2048, with vertex per metre, that's still 4.2 million vertices. Even if I don't triangulate them all, its still a heck of a lot of verts to load in, and they have to be updated as you move around.
I've tried to reduce it so it uses a quadtree to only update the needed verts, but its still not efficient enough - that's the bit I guess I need help with. We need to do some low-level stuff there to do better culling and use of buffers to do only the very minimum of recalculation of LOD each frame.

 

 

[Dal]

Well... Haxe port is now complete. Initial indications are that it DOES run faster... although i'm not sure it's working exactly as intended at the moment.

@babylonhx Am I right in saying there's no debug layer available in BabylonHx yet?

[jerome]

what platform/language/OS did you target to have a faster implementation than JS ?

[Dal]

55 minutes ago, jerome said:

what platform/language/OS did you target to have a faster implementation than JS ?

Actually I am only guessing that it's faster - I can't figure out how to display the FPS in @babylonhx

[jerome]

no idea

but if you use chrome, you can display the browser FPS (not applicative), you could go in the web console, then "more tools / rendering settings", then check in "show FPS meter" and you'll see the browser FPS meter

but if you use Chrome, this supposes that you're just using some JS/WebGL... so the same than BJS

[Dal]

1 hour ago, jerome said:

no idea

but if you use chrome, you can display the browser FPS (not applicative), you could go in the web console, then "more tools / rendering settings", then check in "show FPS meter" and you'll see the browser FPS meter

but if you use Chrome, this supposes that you're just using some JS/WebGL... so the same than BJS

Hmmm, yep, seems with the JS target the performance is about the same. 
I don't get what is sucking up all the performance. What I need is someone who's really good at profiling... who is best at that on this forum?

[Dal]

OK, I've got the CPP target running quite fast

Still lots of bugs though with the Haxe version.

 

 

[Dal]

Ok the good news is I've just made a major performance breakthrough and backported the change to webgl and it works much better now. The bad news is that it's introduced holes in the terrain, but I have a rough idea how to solve that... fingers crossed.

[Boz]

Hey ! I've tested your code at https://www.loudened.com/terrain/

It runs at 35 fps on my computer with CPU i7-4720

The "freeze" could be a bit annoying when a new chunk loads, what do you think is the best compromise between chunk size and loading time ?

Keep going, nice to see good news here !

[Dal]

Just in case anyone is testing/thinking of testing this, the version in git is a bit broken now because I am working on some breaking changes at the moment to hopefully address performance issues.

[Dal]

Gah... I can't seem to solve the loading lag... even with threading and everything it just seems to take too long to add the children, I wish it was possible to see exactly which line is causing the issue  

[gamestudiohx]

http://hxscout.com/ can help you with profiling c++ target

[Pryme8]

you might get something out of this:http://pryme8.github.io/TERIABLE/
It would not take much to convert this to a Infinite terrain generator.