Strategies for Dealing with Large, Complex Terrain

Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Strategies for Dealing with Large, Complex Terrain

Post by Marius »

I'm trying to do real time simulation with a small number of rigid bodies, but with a very large terrain (in terms of vertex count). I've looked into using a heightfieldTerrainShape, but I'm not sure it'll work due to the odd shape of how the terrain is subdivided.

My terrain is generated from a "quadcube", similar to what's explained here (with some enhancements to minimize distortion): https://acko.net/blog/making-worlds-1-o ... and-cubes/
The surfaces of the six sides of the "planet" are curved in 3 dimensions, and not square when looking straight down. So I've been trying out a btBvhTriangleMeshShape.

This works great at low levels of detail, but the numbers get punishing very quickly. I still have optimizations I can do, but currently I have a 4096x4096 vertex mesh for each side (x6). Doesn't sound big, but that comes to 16,777,216 vertices... far too much. The most I've been able to get acceptable initialization time with is 262,144 vertices, or at most 1,048,576 (with lots of serializing to disk and still an overall crummy ten second load time). After initial load, there isn't any performance issue at runtime at all. I believe building the initial tree is what's taking forever (73 seconds with that larger set of vertices). And even then, it's nowhere near the effective level of detail I'm shooting for.

I've considered breaking the physics meshes up into smaller chunks, but then I'll be in a situation where I need to be able to initialize new ones in real time as things move across the terrain. Even with tiny parts I'm not sure it'll be fast enough. (Maybe much smaller btConvexTriangleMeshShapes would be fast enough?) Even a small-ish 128x128 BvhTriangleMeshShape looks like it's taking 310ms to initialize. Not sure if doing it in a thread is an option due to the library/engine I'm using.

I still have some things to try, not to mention optimizations to reduce triangle count, but I'm starting to run out of ideas for where I should go from here. Should I try and build oversized heightfields which attempt to match these crazy curved surfaces? (They would have to overlap, and match up edges perfectly!) Experiment with mesh shapes more? My instinct is to break down the problem or reduce the workload (ignore the 99% of surface that doesn't matter), but how exactly?
Attachments
planet1.png
planet1.png (207.84 KiB) Viewed 30102 times
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Strategies for Dealing with Large, Complex Terrain

Post by drleviathan »

The first question that comes to mind is: Do you really need to simulate the entire planet at once? Maybe you could break it up into smaller chunks and only load the nearby parts?

At GDC-2017 the studio that build "No Man's Sky" gave a talk about how the generate and store the procedural terrain for their planets. The talk would be of interest to you. It should be up on the GDC-Vault in a few weeks, but dunno if it will be free to watch or not. Some of the vault is definitely publicly available but I hear not all of it and I don't know the pattern. It may be that the 2017 talks will be kept private to Vault members (e.g. GDC attendees) for one year.

What I recall in summary:

(1) They generate their data in spherical coordinates but store to disk using the "quadcube" structure.

(2) They start with a noise field to generate the mountains and valleys and then they cover that with one layer of 32x32x32 voxel cubes for the terrain detail. In order to handle matching up the boundary conditions these chunks were actually 36x36x36.

(3) The used the dual-contour method to generate the mesh shapes after their proceedural algorithm had carved out the basic voxels. This mesh, of course, was added on top of the general terrain noise function.

(4) The terrain must be procedurally generated on the fly, so each chunk is prioritized out to worker threads and loaded into their render engine when done.

(5) They only generate the chunks that are visible, but can generate lower LOD representation of farther chunks.
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

I most definitely don't need to simulate the whole planet at once. The problem then becomes initializing the chunks fast enough (loading new mesh shapes), and making sure they're always initialized when stuff is landed or near the surface.

I'm not sure if it'll break things, but next I'm going to try initializing smaller chunks in background threads. Since they take 100-200ms to init, it has been a problem - it's blocking the main rendering loop for the engine I'm using and causing stuttering. If that works, hopefully this also plays nice with vehicles driving on the surface.

1) Sounds like I might be doing something similar, although not saving that structure to disk - I'm sure mine are less detailed, and I'm able to create terrain from a heightmap at startup with no problem.
2-4) Planning on using heightmaps so I can control terrain shape. Seems to work pretty well, main issue is sealing up cracks.
5) Yeah, I'm only rendering what's visible for the most part. I wish rendering was the issue--much easier to find optimizations for! That particular screencap is misleading, yeah.
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

Hmm... it still noticeably stutters (barely) even when adding 1024 vertex meshes. But it seems they only take 5-7ms to create! I think the stuttering might be multiple max depth quadtree nodes initializing at once when moving quickly (I'm adding the collision meshes for max depth tree nodes where the LOD is highest). 5-7ms seems reasonable though, so I'm going to try queuing up these things and spreading out their initialization over multiple loops.

If I have to break it down further, I could be adding and removing quite a few tiny collision meshes - I wonder if that could be an issue? If I go down to say, 8x8 vertex meshes--64 vertices--that's a lot of adding and removing shapes to the physics space. I guess the only way to know how it works is to try?
Attachments
planet3.png
planet3.png (161.5 KiB) Viewed 30052 times
ktfh
Posts: 44
Joined: Thu Apr 14, 2016 3:44 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by ktfh »

A bvh seems more suited for architecture, I bet something like a planet could be more efficiently solved by creating a btConcaveShape sub class. Collision seems to be entirely resolved with the btConcaveShape::processAllTriangles function taking a callback and an aabb, all triangles overlapping the aabb are fed into the callback. You just need a way to project the 3d aabb volume into 2d then pass the overlapping map area as triangles to the callback, skip the bvh generation.
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

Problem with subclassing is that I'm accessing Bullet from a Java API, and my C++ days are way behind me now. It might be significant work to resolve (but could be worth it anyway), and I might need a little extra guidance if I tried to tackle that - not sure what processAllTriangles or the callback are doing/for.

I've actually switched to a collision shape that I don't believe uses a bvh (not certain yet), which has been faster to create and get into the physics space. But, apparently not fast enough - and kicking off threads to initialize new shapes has (somewhat expectedly) been causing crashes, so that's a no-go zone.

Edit: Looks like I've switched to btGImpactMeshShape, which inits faster but still not fast enough.
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

ktfh wrote:I bet something like a planet could be more efficiently solved by creating a btConcaveShape sub class. Collision seems to be entirely resolved with the btConcaveShape::processAllTriangles function taking a callback and an aabb, all triangles overlapping the aabb are fed into the callback. You just need a way to project the 3d aabb volume into 2d then pass the overlapping map area as triangles to the callback, skip the bvh generation.
Was considering giving something like this a try, but if it means I need to make frequent JNI calls back to Java, that sounds like a performance killer.

On using btGImpactMeshShapes created and adding/removing to the physics space on the fly, I've re-looked at creating them in a thread and corrected what I think would have been a potential issue. I was unable to get the most recent version of this to crash... and it was colliding fine. It might be a workable solution after doing some mesh complexity reduction (definitely could cut back on triangle count).

Still interested in suggestions or elaborations on what was suggested above - it would be much cooler to have a more efficient/simpler solution like that.
Jez Hammond
Posts: 7
Joined: Tue Apr 12, 2016 12:53 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Jez Hammond »

Might be worth considering heightfield patches for this. There are options for diamond subdivision and zigzag subdivision, though they appear to be named transposed?
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

Not sure what those options do (at least, I didn't see anything in the docs I found). If it's faster to initialize those than the meshes, that could work maybe. A brief initial test indicated that with a very large heightfield, there was still a significant creation time delay (probably a smaller one), but I never tried with smaller ones like I'm doing now for the meshes. So it could work better.

The main issue with heightfields for me has always been the constraints it imposes. With these meshes, I can just create them wherever (as long as we're still reasonably close to 0,0,0 for float accuracy) without worrying about a bounding box positioning, or which direction is "up", or how the more-diagonally oriented sub-sections might behave.
Jez Hammond
Posts: 7
Joined: Tue Apr 12, 2016 12:53 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Jez Hammond »

Your screenshots look like 'zig-zag' to me. I used 'diamond' but I think zig-zag offers better coverage for less vertices (at least for graphics LODs, not really sure regarding physics quality), plus is better suited to very steep terrain, though I haven't tested behaviour except for (actual?) diamond and standard.

My chunks are small (128 + 1 vertices) and load extremely fast when optimizations are enabled (release build, only on main thread when ready to add to Bullet). A large planet would be noticable, I suggest you spiral out from the camera's position generating chunks in the background, while any rigids etc. sleep until their chunk is ready to simulate (depends on game, but you say the entire planet is awake!).

I don't think any of your mentioned concerns with heightfields should be an issue, though agreed on constraints coming to mind each time I considered using them. The main one for me was no way of having caves (not that libnoise generates them directly), but it's easy to add meshes if required, even replacing an entire heightfield chunk for access.

For me it was a clear choice to go with heightfields; they're deformable.

'Diamond' to clarify:

x-x-x
|\|/|
x-x-x
|/|\|
x-x-x

...repeated looks like diamonds to me, though I guess your screenshots are diamond after all, and not zig-zag?! The SDK has a comment in there somewhere.


edit: just noticed you're using domestic/standard layout, somehow the orange coloured set looked non-standard at first.
ktfh
Posts: 44
Joined: Thu Apr 14, 2016 3:44 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by ktfh »

Your planet mesh is in some kind of quad tree of LODs for rendering? you could assign each node a normal and bounding radius, then map the collision aabb into a normal and bounding radius descend the tree for all overlapping nodes and then pass their verts to the callback.

Code: Select all

class planetCollisionShape : public btConcaveShape {
	btVector planetCenter;
	btScalar planetRadius;

	btScalar arcDist(btVector3 n0, btVector3 n1, btScalar r)  { 
		return r * btAcos(n0.dot(n1));
	}

	virtual void processAllTriangles(btTriangleCallback *callback, const btVector3 &aabbMin, const btVector3 &aabbMax)
	{
		btVector3 norm = (aabbMin+aabbMax) * 0.5 - planetCenter;
		norm.normalize();
		// find most distant aabb corner to use as radius
		btScalar r = 0;
		r = max(r,arcDist(norm,btVector3(aabbMin - planetCenter).normalize(),planetRadius));
		r = max(r,arcDist(norm,btVector3(aabbMax - planetCenter).normalize(),planetRadius));
		// etc
		
		// for each quad tree node create a normal from center and bounding radius
		// then decend into child nodes if their within bounding radius of aabb
		// feed each triangle into the callback
		QuadNodeType node;
		if(r > arcDist(norm,node.norm,planetRadius) - node.radius) {
			for(triangle in node) {
				btVector3 t[3] = triangle;
				int part = 0;
				int index = 0;
				callback->processTriangle(t, part, index);
			}
		}
	}
};
The requirements for creating your own concave shape are pretty minimal you just need to figure out what data overlaps the aabb and send it as triangles to a callback.
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

I also have 128+1 verts meshes (in one dimension). They start out as square two-tri quads, but after some math those squares end up making some quads into what I'd call a slight diamond shape, with some quads remaining somewhat square. Imagine a cube which is "inflated" into a sphere, and then vertex locations are tweaked slightly to reduce resulting distortion. And yes this is my own custom quadtree implementation for LOD.

Can't remember if I explain this above but basically the way it works now, it's coupled to my quadtree rendering algorithm. So that's a bit lame, but it was easy and seems to work fine. Any time a max-depth leaf in the quadtree (maximum detail) becomes visible, we init physics for that leaf. I'm feeding a 128x128 quad-face mesh to Bullet (adding it to physics world) on another thread. When moving very fast over the surface (faster than I really care to support), the max simultaneous active threads seem to cap out at around 6-10. That's probably pushing it, but when I limit surface travel speed that should cut way back (plus I need to tweak my quadtree visibility formula some), and we're only talking very momentary time periods where the threads exist (milliseconds).

In testing I've been unable to get it to break, even when moving at high velocity (there is the expected tunneling issue at high velocities, but I'll solve that as a separate issue - anything hitting at high velocity isn't going to "exist" after that anyway). So it seems at least fast enough on my PC, I believe my bottleneck is still in rendering where I've yet to do a lot of improvements and optimizations. Part of that might drastically speed up physics, I think I can cut way back on the number of vertices and triangles when I optimize for large "flat" regions. So I think I have a feasible solution for now, although I admit there's room for improvement which I'll re-evaluate later on.

Thanks for the specific code example (might be awhile but I do plan to look into that solution some day since it's much more ideal) and the brainstorming ideas.
Sorry if I confused with screwed up or mis-recalled any terminology above, feeling cruddy/tired and I've been sidetracked on a different project for the last week or two, so memory is getting a bit stale.
ktfh
Posts: 44
Joined: Thu Apr 14, 2016 3:44 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by ktfh »

The design thus far sounds really interesting, I'd like to hear more as it progresses.
Marius wrote:I need to tweak my quadtree visibility formula some
you might find inigo quilez website useful/inspirational, all sorts of articles on rendering, frustums and distance functions. Sphere visibility seems relevant.
Marius
Posts: 10
Joined: Fri Nov 11, 2016 11:34 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by Marius »

Been working more on other areas (mesh and rendering optimizations among other things) but here's a little demo of how things are working with Bullet.
You can see some extra triangles rendered behind other terrain, but this is a full sphere and at least half or more isn't being rendered so it's not too bad.

https://vimeo.com/211785328
ktfh
Posts: 44
Joined: Thu Apr 14, 2016 3:44 pm

Re: Strategies for Dealing with Large, Complex Terrain

Post by ktfh »

Really cool seeing the terrain rendering in action. I am curious whats the scale of your planet? I thought jittery floating point accuracy problems become apparent after a few dozen km, assuming 1.f = 1 meter.
Post Reply