Thoughts bout BSPs and large terrain

Hi there!

It’s been so much time since my last CVS version build, that I don’t even know if this is my first post… :smiley: I’ve reinstalled all the Java thingies because I (have to) work with .Net ( }:-@ shame on them), and I was missing Java badly, so I’m back here.

First of all, great work has been done here. Really neat. Some works are really impressive. Even my hardcore “Java-is-too-slow” mates are impressed.

I’m working (again) in my never-ending fantasy MMORPG. Don’t have much spare time (work, new house…), but it keeps my mind busy, and my Java skills Sharp (pun here  XD). Now I’m trying to get FenGUI (great work, BTW) to work with the rest of the scene/input. I have already an ok looking theme running in a sample app, and I’m trying to get it inside a modified FlagRush tutorial (not easy task…). Designing the game database, the server… etc.

Well, I’ve been lately thinking about the design of the node graph for the terrain. I worked in a tank simulator for the army. That is, laaarge terrains. I was long time ago, and the tools and technology have evolved a lot. But being since ever a game-creator-wannabe, I liked some of the ideas that the company that provided the rendering engine had implemented (these guys, btw: We just made the hardware, the models and the terrain (me and my team), the shooting phisics…

I want to implement something like those, so It would be great to hear your opinions, suggestions, “noob-don’t-do-that”, “that’s-already-done-here-this-way” and the like. Maybe someone (hopefully) will find something useful.

= enter the boring part =

The whole scene was as huge BSP tree (z-buffering was slow at the time). The terrain was split into square tiles, of different resolutions-sizes for LOD. The hardware had a limit of about 5000-8000 (:|) tris for the terrain. The tree had to be made by hand, in this way:

We used DTED (kinda DEM, 10 m resolution) for heightmaps, aerial photos for reference, and DFAD (Digital Feature <something> Data) for position referenced rivers, woods, buildings… The elevation was converted to triangles, and was split into squares, in a grid.

Number are BS Planes, and letters are cells. Only a LOD Shown.
|a    | b    | c    | d    |
|     |      |      |      |
|     |      |      |      |
|e    |f     |g     |h     |
|     |      |      |      |
|     |      |      |      |
|i    |j     |k     |l     |
|     |      |      |      |
|     |      |      |      |
|m    |n     |o     |p     |
|     |      |      |      |
|     |      |      |      |

Which resulted into a tree like

           1   3                      
          / /                       
         5   [...]
       4  6
       |  |
       a  i

This tree was used (by vector math between the normal of each plane, and the camera look vector) to determine what is in front of what. The drawing was done from back to front. No need of Z-buffering. The triangles were drawn in order (back-faced ignored).

The tree, besides these "a" is "to the left" of "b", had another node types, for LOD calculation. Cells (EG: a+b+e+f = A) were joined into a lower polygonal mesh for higher distances. The distance from the center of A to the camera was obtained, and used for LOD determination (EG: if > X, go to "5" in the tree, else go to "5'").

In the terminal nodes, there was a list of poligons, sorted by drawing order.

The cells, where not empty (static things), were further BSPed:

       /_ /|     /   __
      |__|/    /   (  ) tree
     house    /     ||
           /  0(-(
          /      dead ork

Where (again) the normals were used again for getting drawing order. These planes were placed by hand. The model editor used the same algorithm for drawing. For example, in modelling a house, the triangles of the walls are to be drawn on screen in arbitrary order. The roof was separated from the walls with a plane (or two, non-vertical this time) from the walls, and the chimney with another from the roof. The house as a whole is grouped. Another plane is placed between the tree (trunk and leaves separated too) and the house-group. The plane had to cut through any poly (no intersections plane-triangle allowed). Something like a dead ork would have been a hell to model... but it was easier than it sounds, using an appropriate editor. The model's allowed polyconunt was really sad, too.

This whole model was separated from the ground with another plane. No need to say that no model used more of one triangle of the terrain... we had to enlarge (less detail) some triangles in the terrain mesh for bigger models.

For things like groups of trees, the system used the position in X/Y to automatically place the planes (luckily).

The performance was great with this system, and a bunch Sun Blades did show really big terrains (taking into account restrictions).

The models of moving things (other tanks, troops) where rendered using z-buffering, though (I never really understood how  ://)

= end of the boring part =

Leaving appart the buildings BSPs (can be Z-buffered now), I plan to make something like this just for the terrain. I plan to have huge terrain, in far distances (who doesn't...  :'(). For the farthest terrain tiles, I was thinking of using imposters (automatically generated only when needed, or stored... dunno) if they leave no holes among them. Probably the lightning of these is going to be though... but maybe a constant haze will do.

For terrain (heightmap + non-detail texture + normal map) generation I've seen Works really good. After getting heightmaps, I plan to triangulate the meshes (I'ts done somewhere?), optimize them (any ideas about triangle decimation?) and generate lower res ones for far LODs. Chop the textures to the same sizes. Build the BSP tree... and get it to work (using the normal maps for light?). Probably its no more neeed to skip using Zbuffering, but hope this will work for LOD calculation.

Each of the buildings, trees, etc, will hang from the appropriate leave of the BSP tree (rendered in their right LOD too). For trees far away, I thought it could be replaced with camera-facing quads with texture (Imposters, maybe). Higher LODs will be loaded in backgound, when getting close. Hopefully, will fade-in into view, when required, replacing the low res meshes.

Generating big bounding boxes for terrain blocks (to determine if they are visible or not), I would like to get rid of parts that are, for example, behind high mountains.

BTW... one noob question... Only tris that are in the view fustrum are processed... no? So, I can have "active" the whole terrain in my tree, all around the player, and only the things that are really seen are processed, right?

For things like buildings, this will be mixed with a little "portals" (a special node in the tree). I want the player to enter the cities-buildings without "loading" screens, so walls ALA "World of Warcraft" will be used in front of the doors. If the player reaches (read: collides) a certain point, entering the building, the terrain will be not shown, and the previously-in-background-loaded building interior will take its place in the tree.

Other thing that came into my mind was using the GIS capabilities of MySQL... huh? And has someone used Sounds good... but I'm too old to belive everything I read...

I know that I will never end something like that... It's a huge task. Bigger than my available time. I just delivered a project at work (testing-correcting now), so I will have more spare time for this... but the customers never sleep for long :D

I hate .Net. I's being 2 years from now with it... and every day I found another glich :'( This will keep me alive.

Before starting, and taking the wrong path, it would be great to hear your opinions. Anybody into rendering big terrains, or BSPing things? Something really stoopid above?

Thanks for your time, and sorry if it's too long/boring... and for my long forgotten English :D

Don’t have much to time to read through your entire post, but we already have a great solution for streaming large terrains provided by our very own llama. Check out this post.