# Automatic terrain following data structure in CVS

jmetest.terrain.TestTerrainFollower

The data structure takes a TriMesh (or a node of TriMesh children) and creates a data structure where approximate Y values above the terrain can be computed in O(1) time. The algorithm I didn’t read anywhere, I just thought up on my own. It runs pretty darn fast 8) Check it out and let me know.

Update: Didn’t know this was already in. It’s gone now.

its cool.

But this functionality has been accomplished ages ago in a different manner.

``` TerrainPage tb; CameraNode camNode; public void simpleInit() {   .... create terrain here   .... create cameraNode here } public void simpleUpdate() {   float height = tb.getHeight(camNode.getLocalTranslation().x, camNode.getLocalTranslation().z);   if (!Float.isNaN(height) {     camNode.getLocalTranslation().y = height + 9;   } } ```

Which method uses less memory and gives the best FPS?

DP

lol mmmm I didn’t see that function. I had wrote TerrainFollower to work on any TriMesh not just jME terrain builds, but it’s not really usefull with that function inside TerrainBlock. I’ll go ahead and remove it and just archive it for myself. It did give me some ideas though for OctTree splitting a TriMesh for fast, exact collision detection (unless that’s already in as well)

u can safely assume that the collision detection system isn’t in. So your idea would be quite nice.

Btw, can you please explain what does O(1) mean? ://

DP

For a more layman definition, it is a mathimatical way to “prove” your method for doing something is better than someone elses.

Quicksort is better than bubble sort because quicksort is O(N * lg N) and bubble sort is O(N * N), and the graph of Y=xlgX is smaller than the graph of Y=XX. For similar reasons, binary search O(lg n) is faster than linear search O(n) because the graph of Y=lg x is smaller than the graph of Y=x. A running time of O(1) means that it finishes execution in a constant amount of time regardless of the input, and is the smallest posible graph in Big-Oh notation.

In short, big oh notation is a good estimate of the worse case running time of an algorithm.

wow, thx cep.

You can fined it in the Attic folder in the CVS Repository from the home page.

My algorithm was to take the trimesh, and create a float[500][500]. Then I would store in the value float[X][Z] where a segment from x=X,y=0,z=Z to x=X,y=1,z=Z would intersect the trimesh. Polled values would be simple interpolation from the float[][]. A speedup I did during the algorithm was to match triangles to [][] positions (which is pretty fast) , not [][] positions to triangles (which would take forever).