Triangulated irregular network (TIN)

Code Snippets
1

Here is another piece of code I have wrapped up. This time it is the terra algorithm by Michael Garland (PhD at Carnegie Mellon University if I have seen right on his home page :-). Terra takes a regular grid of height samples and creates a mesh containing an approximation of this data.

http://graphics.cs.uiuc.edu/~garland/software/terra.html

The approximation is done by triangulation using a greedy insertion algorithm described in this paper:

http://graphics.cs.uiuc.edu/~garland/papers/scape.pdf

In short, the algorithm starts with an empty mesh and inserts single vertices until a criterion is met. The vertex that gets inserted at each loop is the one with the biggest error (difference in height between original data and current approximation). The criterion can be either that the vertex budget is reached, or that the current error is smaller than a given threshold.

The result is a triangulated irregular network (TIN), with much less vertices than the original heightfield. Some screenshots:

Screenshot (textured):
http://www.dachau.net/users/pfrogner/tin1.jpg

Screenshot (wireframe):
http://www.dachau.net/users/pfrogner/tin2.jpg

Screenshot (untextured):
http://www.dachau.net/users/pfrogner/tin3.jpg

Demo (source and win32 binaries):
http://www.dachau.net/users/pfrogner/Demo-TIN.zip

Usage is quite simple, just set some parameters and then call decimate with the target filename (32 bit grayscale image recommended) and the destination filename (the egg file to be created). The main parameters are the point limit and the maximum error, as described above.

import tin

# Parameters for decimation
tin.setPointLimit( 10000 )
tin.setMaxError( 0.0 )

# Scale
tin.setVerticalScale( 60.0 )
tin.setHorizontalScale( 1.0 )

# Additional data to be created
tin.createTexcoords( True )
tin.createFaceNormals( False )
tin.createVertexNormals( True )
tin.createBinormals( False )

# Run
tin.decimate( 'models/elevation.png', 'models/elevation.egg' )

I didn’t change Michael Garlands code a lot, just remove a few parts, port some vector math to Panda classes, and change input and output. Input now uses the PNMImage class, so it can read virtually all images. Output creates a Panda EGG file (y-up coordinate system).

I don’t know if this wrapper might be usefull for anybody, and I don’t recommend to use it for game applications, but I still want to share it. It is quite old, and reducing the vertex count is no longer as important as it used to be some years ago, on the other hand I was impressed by the fact that good looking results can be achieved at using only one or two percent of the original vertices.

PS: For those who want to tinker with the code: It is easy to pre-insert vertices along the edges of the terrain, for building skirts that connect several patches of terrain at different resolution levels.

enn0x

2

wow this one looks really intresting =) did you already checked out multitexturing/popping (side wouldnt open for me so i couldnt read about it)?
in fact it’s looking really nice… but does it take the camears viewpoint into calculation? the terrain in the distance seems about the same level of detail as the one in front.
also vertex normals might cause glitches.
on the other hand it’s nice to be able to insert vertices in case of tiling terrains. can you define the vertex-normals of those vertices too?

3

Thank you for your interest, but I don’t think TIN is suitable for usage in a game. It was intended as a proof of concept, and perhaps an example on how to wrap existing C/C++ code.

The mesh creation is an offline tool. Feed in an image, and get out a model (EGG file). That’s it. You can load this model just like any other model, and do whatever shading you want to do with the model (multitexturing, shaders, splatter maps). Camera viewpoint and distance are not considered, obviously. And popping doesn’t happen since it is a static mesh.

Because it is just one static mesh there are several drawbacks:
(1) Bad performance when doing collision detection.
(2) No viewport culling possible.
(3) No LOD.

Michal Garland has also written an algorithm (QSlim) for reducing arbitrary models. The examples (especially the cow) on his home page look very interesting. So creating lower resolution models for environment objects or actors is another application of these algorithms.

My motivation for playing around with the terra algorithm has been that I like the way Gothic (I-III) does terrain/environment. Lots of overhangs, caves you can walk in, and nice textured vertical cliffs. Things you can’t do with a pure heightmap based algorithms. Here are some thoughts about what COULD be done (without having though about details yet):

(1) Create a huge heightmap (e.g. EarthSculptor)
(2) Create several levels of detail for this heightmap (e.g. this algorithm)
(3) Insert additional vertices along the lines where you want to split the terrain into smaller chunks, say 64x64 pixels, to avoid cracks.
(4) Split the LOD meshes into chunks along these lines, and write EGG files for each chunk.
(5) Hand edit the chunks to add fancy geometry like overhangs, caves etc. (e.g. Blender)
(6) Compute PVS (possible visible sets) offline and store the results.
(7) Write an algorithm that loads/unloads chunks that can be seen from the current camera/player position, with the right LOD.
(8) Avoid popping by geomorphing algorithm (hardware geomorphing anybody?)

Well, just rumblings so far. And I didn’t think about details yet.

By the way: I didn’t forget about geomipmapping. I have some research going on myself, and perhaps I find enough time to do a simple implementation one of the next month.

enn0x

4

gothic I and II uses small hand-made world-blocks (no heigfield at all if i’m not wrong) and i dont think there is an LOD either so no popping.
since i’m writing on my mmorpg i modified the chicken exporter to pack mesh objects in blender single world blocks and export them as seperate egg files with propper naming.
i also wrote a egg->bam batch converter using panda model write to disk stuff. and i just finished a the part of my pycode which loads and unloads those chunks depending on the player’s position (well this parts isnt tested that well but it seems to work quite well).
interested?
:wink:

5

Seems we had about the same idea.

Of course I am interested. Are you using an own thread to load/unload chunks in the background? I have seen there is a TaskThreaded class in Panda, which could be useful for this. And do you have a way to determine potentially visible set (PVS), to cull away unnecessary chunks?

At least Gothic III uses some kind of LOD (not sure about I and II), since they have a (one) low-poly version of the terrain and (one) high-poly. But I never have seen popping between the two LOD’s, not even in wireframe mode. What they are really good is hiding terrain parts that are not visible from the current position, so I think this will be one of next things I try to figure out. Well, actually QSlim will be the next thing I do.

enn0x

6

i have no PVS in my code, its pretty much forced loading of models. since my world blocks are pretty huge and the viewing distance is not all too high there arent many unneccessary blocks to cull away, especially since the geometry inside the block can reach far out of its virtual block-size.
still lots of space for optimizations but it works for now. performance is ok if your visibility is not too high and if your chunksize is well chosen.
atm i’m loading the models within a normal task. but panda indeed seems to have some secial kind of task which runs in the background and could be prefectly suited for this sort of jobs.
unloading the world is another pretty brute-force method. it unloads a “hollow cube” around the player.
well all the searching the scenegraph for nodes stuff takes pretty much time. might be faster to directly name the nodes and access them.
well it’s just the basic idea. i still have to add some lines which re-center the world if the player moved a certain distance ( to minimize numerical errors).
well long speech short content:
http://home.arcor.de/positiveelectron/files/project-files/ff8online.py-backup5
and the blender exporter :
http://home.arcor.de/positiveelectron/files/project-files/chicken_export1.0-mmorpg-2.py
and the small script which takes the egg files and outputs optimized bam files

-perhaps one note, texture path names seems to be absolut, if you want them relative you might need to change the chicken exporter a little

for the chunksize, our character is 1.8 blender unints (and therefore 1.8 panda units) heigh and our chunksize will be 32 units, most likely.
aahmm the code is… not … so… well. documented… aaahm. but… i hope you still able to get what you want =)
the blockDelta and blockUpdate functions should be of intrest for youhttp://home.arcor.de/positiveelectron/files/project-files/optimizer.py