Best way to get triangle pick results from terrain

I'm fiddling around with dynamic loading of terrain blocks and as I need triangle precision pick results for controlling the characters movement, I use updateCollisionTree on each terrain block.

To save some time there are functions to read and write a terrain block serialized. Without a collision tree it's about 3.8M but with the tree it's 60M and takes quite some time to load (8-15sec). It's faster to build the collision tree after loading and keep it out of the object stream.

The bigger problem I have is the memory the OBBTree needs. I load the terrain block the character is on and four adjacent blocks one in each direction. Even with terrain blocks being destroyed that get out of range the memory usage is too high and sooner or later I run out of heap space even with -Xmx768M.

Without the collision tree it's very fast: five blocks loaded in 1.3 secs is just great.

The pick results is needed as you should be able to click on the ground and the character should walk to the intersection point of the camera direction ray and the terrain.

Any ideas how I can get the intersection point without keeping the memory consuming OBBTree?

I thought about testing intersection against all triangles in the blocks but that will be quite slow as each terrain block has 256x256 height points which gives ~130k triangles.

Couple of questions Galan

Are you using TerrainPage ( I switched to terrainpage as its designed to account for larger heightmaps ).

What spec PC

I use a SlidingTerrainPage ( with dynamic loading of terrain blocks) as I have quite big terrain of about 300000 to 500000 units. The grid size is 128 and I work with 117 terrain blocks - the rest is unreachable terrain. For the first approach I worked with a grid size of 32 but I dropped that for obvious reasons.

A TerrainPage would require a squared size terrain and having the terrain loaded at once which even on a high end PC would require a ridiculous amount of time and memory. My PC has 1GB  RAM, a 2400+ AMD Athlon and a Radeon 9600 XT with 256M GPU memory. With a collision tree one block needs ~64M so the whole world would need ~7.5GB RAM just for the terrain. Without the collision it's still ~440M.

As there are more things to keep in memory I have to reduce the memory foot print of the terrain to a minimum and only load the terrain that is visible, e.g. five out of the 117 blocks. That means that the loading has to be very fast to be less disturbing during game play. With the serialization this works fine except for the collision tree - it loads five blocks in about 1.3 seconds.

You see my problem is the huge virtual world which forces me to balance memory usage, loading time and precision. A typical character is 48 units high, so the world is about 18km x 12km and I tend to say this is not too big for a MMORPG.

How long does it take to build the OBBTree?  Maybe you could do border detection and then only add the OBBTree when needed, although that seems slow.

Maybe we can strip down OBBTree some, but I guess part of the size is just the sheer number of triangles in a TerrainBlock.  I'll take a look though here.

This is from a debug showing the timing:

INFO: TIMING: start checkTiles 1132598435240
INFO: TIMING: after setNeeded(false) 1132598435240
INFO: TIMING: restored terrain.21.19 in 330ms.
INFO: TIMING: updateCollisionTree for terrain.21.19 in 7341ms.
INFO: TIMING: after first checkTile 1132598442931
INFO: TIMING: restored terrain.22.19 in 140ms.
INFO: TIMING: updateCollisionTree for terrain.22.19 in 6449ms.
INFO: TIMING: after outer checkTile1 1132598449540
INFO: TIMING: restored terrain.20.19 in 100ms.
INFO: TIMING: updateCollisionTree for terrain.20.19 in 7461ms.
INFO: TIMING: after outer checkTile2 1132598457111
INFO: TIMING: restored terrain.21.20 in 100ms.
INFO: TIMING: updateCollisionTree for terrain.21.20 in 3175ms.
INFO: TIMING: after outer checkTile3 1132598460396
INFO: TIMING: restored terrain.21.18 in 90ms.
INFO: TIMING: updateCollisionTree for terrain.21.18 in 9373ms.
INFO: TIMING: after outer checkTile4 1132598469879
INFO: TIMING: before markForDestroy 1132598469879
INFO: TIMING: after markForDestroy 1132598469879

It takes 90-330ms to load from ObjectInputStream, average is 152ms and the updateCollisionTree takes 3175-9373ms, average is 6759ms.
Loading the OBBTree takes about the same as it's more than 60MB.

A TerrainBlock uses OrientedBoundingBoxes in an OBBTree as it's extending TriMesh.

What about that:

Create BoundingBoxes around a given number of height map points and store them in an OBBTree. That way we could adjust the size of the OBBTree by the number of grouped triangles.

On intersection test with triangle precision we would first have to find the BoundingBoxes that match and with a positive result test each triangle in the group. This might take more time than the current approach but it would save memory. By adjusting the group size one could find out the best value between performance and memory consumption.

Do you think that is feasible?

Definitely sounds interesting.  I also just picked up a really good book on real time intersections/collisions that I'll look through for good ideas.  For now, can you limp along with the slow times at all?

Or you could just load the OBBTree as you need it…

In your code examples, your characters are only on one piece of terrain at a time, and judging by the scale it seems like it would take awhile for a character to walk from one piece to the next. Therefore, you can load the OBBTree for the piece of terrain they are on and not for the others.

That is… if there isn't going to be any triangle picking for awhile, don't build the tree until it's needed.

Another way to go is to cast a ray from the camera to the terrain and test for height intersection with the heightmap(or with the terrainpage.getheight)…upon intersection you do a binary search for a more exact intersection point…