(Yet another) Terrain Algorithm

Showcase
1

Since Version 1.3.0 Panda3d has a built-in terrain renderer, so another teerain algorithm is probably not needed. Anyway, ThomasEgi pointed me (https://discourse.panda3d.org/viewtopic.php?p=9875&highlight=#9875) to then Ranger MkII demo by Andras Balogh, which looks quite impressive (http://web.interware.hu/bandi/ranger.html).

Ranger MkII uses an improved SOAR (stateless one-pass adaptive refinement) algorithm. The complete terrain mesh is created new every frame, and high-resolution refinement is done only inside the camera frustum, while areas outside the frustum are left at low-resolution.

I have done a small python extension wrapping up code from the Ranger MkII algorithm and adapting it so it can be used from Panda3d. Most of the code is copied 1:1 from the original Ranger MkII sources. I’m not sure if there is need for such an extension, but I still want to share it.

The extension is compiled on WindowsXP using the VC Toolkit 2003 compiler (7.1) and having Platform SDK (R2) installed. It is linked against the official Panda3d 1.3.2 distribution and the downloaded thirdparty dependencies. The code is still alpha at best, and there are many rough edges. For example there are no checks for possible problems, like removing the terrain node path and then calling update again, or unloading in general.

Screenshot (wireframe mode): (240k)
http://www.dachau.net/users/pfrogner/soarx.jpg

Extension source code: (84k)
http://www.dachau.net/users/pfrogner/Source-SOARX.zip

Demo (win32 binaries): (2.8M)
http://www.dachau.net/users/pfrogner/Demo-SOARX.zip

Portability:
The extension is windows only for now. I have tried to move as much code as possible from proprietary libraries to Panda ( libpng -> Panda PNMImage, writing to OpenGL vertex/index buffers -> Panda GeomVertexData/GeomTristrips), but there is still one thing that is windows-only: The way memory mapped files are handled.

On linux using mmap( ) in <sys/mman.h> should do the same, and what I think is the right linux code is included in the sources ( switching with #ifdef WIN32 … #else between windows and linux ). But I don’t have a LINUX machine available, so I could not test if it works. I think someone with C++ knowledge on linux is able to fix this within one or two hours.

Usage and demo:
There is no documentation included either, so I give a very short overview here. For a working example please have a look at demo.py in the binary demo. The demo has two cameras and allows to switch between them using F4. Refinement is done for the refinement camera obviously, while the observer camera allows to have a look at the refinement result from another point of view.

import soarx

# setup
soarx.setMapBits( 10 )
soarx.setBaseBits( 6 )
soarx.setDetailBits( 6 )
soarx.setHorizontalResolution( 160.0 )
soarx.setVerticalResolution( 0.1 )
soarx.setVerticalBias( 0 )
soarx.setDetailVerticalResolution( 0.0012 )
soarx.setCameraNP( cameraNP )
soarx.setLens( lens )

soarx.init( terrainNP )
soarx.build( )
soarx.load( 'models/ranger/' )

# once a frame
soarx.update( )

Calling build( ) is required only once and takes a few moments before it returns. It will process the base elevation map and create a number of png images and two data files. The data files contain everything the SOARX algorithm needs to create a terrain mesh. The png images can be used for shading the terrain (normals, lighting, bump maps, …). The demo contains only a very simple shader.

MapBits, BaseBits, DetailBits:

  • BaseBits is the dimension of the heightmap. 10 means 1025x1025 pixels (2^10+1).
  • MapBits is the dimension of the effectively rendered terrain. The demo has 16 BaseBits, which is a map with about 65000 x 65000 vertices!
  • DetailBits is the dimension of a “detail” elevation map that fills the gaps between the base map vertices.

Feedback
I am quite new to C++ programming, and I would be interested in feedback if the extension runs on other windows machines (missing dll’s and so on), or if anybody is able to compile it on a linux box. Oh, and please don’t fall on your back and laugh if you see that I am using a batch file for the build process :slight_smile:

enn0x

2

if you want to use a new terrain algorithm with panda you should better try using geomippmapping, it’s less cpu-intensive and it’s easyer to use with paged terrains (which is pretty good for “endless huge worlds”.
anyway . great to see that people are workign on it :exclamation: =)
geomipmapping and my geomipmapping optimized multitexturing should do a fine job with panda =)
(up to 2147483648 texture layers can be blended into each other :smiley: … i’ll write a tech-doc about it,soon since there are quite a few people interested in it =)

3

Sounds great. Do you mind sharing the code?

4

i mentioned that i’ll write a techpaper on it^^ it’s pure theorey atm. although i tested a few thing to prove that the concept itself works it wasn’t coded so far.
actually it does the same with textures like a lod would do for terrain.
splitts the terrain in pieces (usualy already done by the terrain algo, in this case geomipmapping would be the one) and then render textures for it (not with multipass but simply a texture-rendering off-screen. a stack of 2d cardmaker objects are enough to put up the single textur “layers”. the resolution depends on the camera<->terrain patch distance.
usualy you wont use more than 5 or 6 textures per terrain patch(it’s possible to use as many as the zbuffer can sort :stuck_out_tongue: ).so rendering those images should be quite fast (and it’s an ortho camera so it might be faster ) . and it doesnt have to be done each frame, only if the camera moves and the detail level has to be changed. (usualy a threshold of half an terrain-patch)

this costs a little texture memory but i think it could be more effitient than multipass rendering AND you tweaking the quality is possible “on-the-fly”

well like i said . as soon as i have the time i’ll write a techpaper with some illustrations and some math 0) (unfortunately i’m currently busy with finishing up some hardware-development and projectmanagement, but i’ll answe your questions if you have some :slight_smile: )

well this should work well together with geomipmapping and paged terrain =)

5

Very cool to see SOARX in Panda3d. Well, I’m on Linux, so I didn’t actually see it :slight_smile: . I believe this is the same thing that is used in Delta3D.

IIRC Perlin noise is used in SOARX for the close up details. The other day I noticed in Panda’s documentation that it has a buildin class for Perlin noise. Did you use that?

Sadly my C++ is not good enough to quickly port memory mapping
:frowning: .

Question: mipmapping usually refers to creating lower resolution versions of something with high detail. The SOARX algorithm creates a higher resolution mesh than the terrain data. Does geomipmapping do that as well?

6

afaik SOAR doesnt create “higher” resoultion meshes. it just creates them on the fly with the highest resolution under your feed and lowest in the far distance…viewport depending.
well SOAR is a very nice thing but it’s not that optimized for today’s hardware.
and it does it really fit into “panda’s way” of handling object… hm… and it doesnt really work nicly together with my way of texturing :stuck_out_tongue:

but it’s very nice for flightsims.

btw enn0x:did you already try colission with the SOARX stuff?

7

@ThomasEgi: No, I did not try collision detection, and I would not advice to do so. SOAR creates one mesh, with a single primitive. If I understand Panda3d collision detection right it would be very slow to do so. But there are other ways. The refinement camera in the demo “walks” on the ground. The way Ranger MkII is implemented allows to query the terrain height, fast and computed from the true elevation data, not the current (optimised or not) mesh.

@Laurens: The “higher resolution” stuff is a bit complex. The heightmap (pudget sound) from the Ranger MkII demo is 1024x1024. The terrain that is rendered is 65k x 65k, that is 16 (2^16=65k) levels of refinement. The first 10 refinement level are computed from the heightmap data, the last 6 levels are random perlin noise. That’s what the detail elevation map is for.

This is just a trick to keep the disk size of the terrain data small and still have a nice looking terrain with lots of details. Anyway, the processed terrain data for a 1024x1024 heightfield is 16M. For performance testing I scaled the original 1024x1024 heightmap up to 4k x 4k, and the terrain data grew to about 260M. And 65k x 65k would be around 10G disk space. This is not surprising, since the Ranger MkII implementation of SOAR stores four 32bit floats per heightmap pixel (Not much, but I wonder what kind of terrain data representation games like Oblivion or Gothic 3 use, for storing their huge terrains, with certainly more than 4k x 4x).

Filling in perlin noise is fine for visualization or for flight simulators, but for a ground based game… I don’t know.

ThomasEgi is right. SOARX is an old algorithm, from pre-GPU time, when using CPU time for reducing the number of vertices was more efficient than sending great numbers of vertices to the GPU. Today’s graphics hardware allows other approaches, like Chunked LOD or geomipmapping. Still, it has been fun and a nice exercise to do this small wrapper :slight_smile:

8

hm… i think i saw some oblivion map data some time ago… i’f i’m not completely wrong they are aobut 21k x 21k …no real value but just to get an idea of the size. :slight_smile:

9

libpng is free software and opengl is an open specification. In fact, Panda3D has a more elaborate license which, until recently, wasn’t even free.

10

Ah, perhaps proprietary is not the right word. I didn’t mean in the sense of legal/copyrights. What I meant was

  • proprietary: non-Panda code
  • native: Panda code

Using libpng would restrict code to png Images, and Panda already uses another png library (libpandapng13.lib). Using libpng is just another dependency. Similar, writing code using OpenGL calls doesn’t allow to use DirectX.

Sorry if there have been misunderstandings.

11

I have updated the demo and source downloads. Main differences are:

  • Builing with a makefile now.
  • Accessing memory mapped files using either mmap (UNIX) or a wrapper for Win32.
  • All detail geometry stuff has been removed. So pure SOARX now.

Extension source code: (19k)
http://www.dachau.net/users/pfrogner/Source-SOARX.zip

Demo (win32 binaries, VC7.1): (1729k)
http://www.dachau.net/users/pfrogner/Demo-SOARX.zip

It should be possible to build this extension on UNIX, if you edit the makefile and exchange the compiler/linker and the options. The API has become more simple now:

import soarx

#setup
soarx.setMapBits( 10 )
soarx.setHorizontalResolution( 160.0 )
soarx.setVerticalResolution( 0.1 )
soarx.setVerticalBias( 0.0 ) 
soarx.setCameraNP( self.cameraNP )
soarx.setLens( self.lens )
soarx.setMagic( 60.0 )

soarx.init( self.terrainNP )
soarx.build( 'models/' ) # run only once
soarx.load( 'models/' )

# once a frame
soarx.update( )

# query
soarx.getElevation( x, y )

MapBits is the size of the terrain (10 = 2^10 = 1024x1024pixel)
Magic is a value for setting the refinement error. Play around until you are satisfied with the results. Smaller mean less quality, but faster. The effect is only very small.

It runs at about 120fps for the 1024x1024 demo terrain on my Nvidia 7800GTX.

enn0x

12

any way to let this thing generate the meshes from a texturebuffer so it could be used for streamed terrain? (puzzle your terrain together in an offscreenbuffer and feed soar with it)

13

No, sorry. The algorithm uses an array of internal index data structures stored in a file on disk. The “build” process (should be offline, since it takes some time) reads the elevation data and creates this binary terrain data, along with some other useful files like a gradient map.

At runtime the prepared terrain data is mapped into memory using, well, memory mapped files. This is fast, and the full terrain data does not have to be in memory.

By the way, Python has a mmap module too. A nice thing if you want to work with large data sets from Python.

Modifying the wrapper to support multiple terrain instances would be possible. So perhaps paging lager sectors of the terrain, each an instance of a soarx terrain object, could work. Cracks between the single sectors will be a problem though. I will think about it, and if I am successful I will post an update.

enn0x

14

Why was detail geometry removed, isn’t that what creates the nice illusion of detail…or was that to allow one to just use their own texturemaps ?

cheers
g.leej

15

Detail geometry has been removed for two reasons: speed and simplicity. It is an illusion of hight details, but an illusion that comes at a great cost (speed) and that is not suited for every kind of game. For example if you walk on the ground then you probably don’t want to have the same detail “hills” around you all the time, but you want to have a unique terrain.

16

Ralph is roaming again, and this time over SOARX terrain. I have updated the code and written a new demo, this time featuring Ralph (who else).

Some bugs have been fixed, and the API has been re-designed, and it is possible to split terrain into chunks. Also, some minor changes in the algorithm increase the performance. The new download (source complete with windows binaries) is:

http://www.dachau.net/users/pfrogner/soarx.zip

Two screenshots, one with pudget sound data, and one in a random noise land:

http://www.dachau.net/users/pfrogner/soarx1.jpg
http://www.dachau.net/users/pfrogner/soarx2.jpg

The module now provides two objects, TerrainBuilder and TerrainRenderer. Using the TerrainBuilder works like this:

import soarx

builder = soarx.TerrainBuilder( )
builder.setHorizontalResolution( hscale )
builder.setVerticalResolution( vscale )
builder.setVerticalBias( 0.0 )
builder.setMapBits( bits )
builder.buildTerrain( filenameSource, filenameDest )

#utils
builder.buildNoiseland( filenameDest, width, height )
builder.buildGradient( filenameSource, filenameDest, scale )

Setting horizontal scale, vertical scale and vertical bias just scales the terrain and shifts it up/down. Map bits tells the builder the size of the heightmap, which must be (2^bits) + 1, for example 1025 x 1025. Finally, buildTerrain reads the heightmap and pre-computes binary data. Arguments are the source filename (an 32bit grayscale image) and the filename of the binary data to create. Two utils are available: buildNoiseland create a perlin noise image of dimensions width x height, and saves it as filenameDest. buildGradient computes a normalmap for the heightfield.

Using the TerrainRenderer isn’t too complex either. Just make sure you set the same parameters for resolution and map bits that you have used to build the terrain:

import soarx

# initialize
o = soarx.TerrainRenderer( )
o.setMapBits( bits )
o.setHorizontalResolution( hscale )
o.setCameraNP( self.camera )
o.setLens( self.lens )
o.setMagic( 60.0 )
o.setNP( chunkNP )
o.load( filename )

# once a frame
o.update( )

It is now possible to have several terrain chunks at the same time. Just edit the demo (both build.py and render.py) and change nx,ny and chunkbits. For example nx=3, ny=2, chunkbits=9. This will create 3x2 chunks, each 2^9+1 -> 513x513 pixels in size. The chunks will fit together without cracks :slight_smile: This way you could implement a paging landscape (The demo just loads the chunks at startup, it doesn’t load/unload them depending on Ralph’s position). Loading terrain is quite fast, since no terrain data is loaded actually, only a filemapping is created.

Now the bad news:
The demo runs at 130fps on my PC, which is above average. Not really hight-end, but certainly above average. This is nice, but it is just the terrain, without vegetation, objects, actors, and so on. The built-in HeightfieldTesselator is much slower when updating the terrain every frame, but if you use it is a sensible way (update only if the camera position has changed significant) then it is about twice as fast for medium sized terrains. And HeightfieldTesselator has normals and texture coordinates assigned to the vertices, and collision detection is fast.

So feel free to try out the SOARX extension, especially for huge terrains (4k x 4k), or have a look at how the wrapping is done. But keep in mind that the HeightfieldTesselator that comes with Panda3d might be a better choice.

enn0x

17

Hi, does this still work? I have the Windows and not the Linox.
Mostly I’m interested in this for the 3 camera viewpoints!
Well done, if it does indeed work!
I believe if thomas egi says this works then it probably does :wink:
So if you use height maps, how would you, say,
place trees or castles and such? with the xyz…I guess you can
have it so if height map #1 is used then tree#5 and castle #8 is placed.
this way there’s no floating castles or just a little tree branch poking
out of the mountains. Or easier would be the setpos with varying
xyz for the trees.
I don’t know though because I cant get this linox demo to work.
I suppose its not random the pattern?
On a side note, how would i run this on windows?
I pasted the dll into the ‘bin’, but i notice the c++ :open_mouth:

18

If there is no particular reason for you to use SOAR terrain, then you are far better off with either

Anyway, about your questions:

No. Last time I compiled this has been for Panda3D 1.3.2. So you have to compile and link against the current version of Panda3D if you want to use it.

I never compiled for Linux. Only for Windows. See the first post in this thread.

(1) Make up your mind where (horizontally) you want to place the object ==> x,y
(2) Find out the terrain height at this position ==> z
(3) Place the object at (x,y,z)
(4) You might consider placing the object a little bit lower (z - delta), to compensate for slopes.

I don’t understand this one. Please explain some more.

A Python C++ extension is used like every other module. Place it somewhere in your Python search path and the simply import the module. Until you know what you are doing: place the .dll in the same directory like the Python code which uses it.

enn0x

19

Thanks , that makes things a little clearer.
As for the random pattern i was thinking if you
have multiple height maps, that it would ‘chunk’ seamless tile
them in a random order, for really big random terrains.
Then you can have preassigned compatible xyz locations,
for objects, for each of the different height maps.
I don’t really know what I’m talking about, as I haven’t
tried the heightmap system yet, and this is probably already implemented.
Mainly i was interested in your three point camera system,
and I should have asked you about that! I spent about two hours
trying to pull it apart yesterday, :open_mouth: <<too much looking at code eyes.
Thanks for the explanations, I’m going to try it again,
I loaded my panda with PYPE and I’m constantly cursing it
because i think thats why half the demos I try don’t work.

20

About tiles/chunks: All (TerrainTesselaotr, PGMM, SORAX) do only render the terrain. That means, take a function height( x, y ) as input, usually in form of a greyscale image, and produce a mesh as output. Nothing else. The big trick is to create terrain with few vertices and triangles, to have better performance (FPS).

It is up to you to prepare heightmaps (images) which fit together. Usually you don’t paint such a heightmap directly with e.g. a paint program, but you use so called “terrain editors” to interactively model your terrain. Some of them can produce tiling terrain, others not.

The most easy way to create tiles which fit together is to first create a single heightmap of all the terrain, and then cut this heightmap in pieces, usually with an overlap of one pixel. There is no randomness in such a tiling process.

The only part where random comes into play is that some terrain editors/generators use various random-based algorithms to create a first draft of the terrain (diamond-square, perlin, …). For a game you might want to edit this terrain, lower it in some places, flatten it somewhere else to place buildings, dig rivers, erode mountains, and so on…

About camera stuff: do you mean the code to switch between different cameras (if I remember right: distant observer and tracking camera), or do you mean the code that implements a third-person tracking camera?

enn0x