Terrain woes
Author
I am trying to make a "simple" program that will
1. load and display a terrain
2. load, displays, and move a person around the terrain; currently a box
I have hit a few bumps though. first is there a better way to figure out how to get the players to follow the terrain without scanning through the vertexes of the terrain, determining which 3 are closes to the player, and then calculating the height based on that. right now my map is small with only a few vertexes and this works but i imaging on a larger terrain this would be horrible.
Second, does anyone have any tips for making good but simple terrain. my journey into making terrain is make a few triangles then merge their edges together. looks kinda goofy but it works.
Any help would be great, thanks.
I recommend looking into quadtrees. There are some articles here on GameDev that deal with it, and you'll find quite a few just with a google search.
Heightmap terrains are uniform. As a result you can determine the polygon that your model is on by its x and y coordinates allowing you to forgo expensive distance calculations. Lookup your polygon's normal (you sent it to the graphics card, so it must be stored somewhere) and determine your model's z coordinate from its x and y coordinates.
But this probably only applies if you're using a heightmap terrain.
But this probably only applies if you're using a heightmap terrain.
Author
thanks, I dug through some articles on the quadtrees and I think they will help.
just as a side question, do they use this method in games or is there another approach that is more commonly used. I love games and learning how they accomplish some really neat things, for example how some game have absolutely huge zones and do not need portals or loading screens.
thanks again
just as a side question, do they use this method in games or is there another approach that is more commonly used. I love games and learning how they accomplish some really neat things, for example how some game have absolutely huge zones and do not need portals or loading screens.
thanks again
A quad-tree is simply a spatial partitioning system that is well-suited for many two-dimensional sorted data structures. It is compatible, but not synonymous with the notion of a heightmap, which is what you really want to look into.
By far and away, heightmaps are the favoured structure for storing terrain data. Rather than having an orderless set of polygons (commonly referred to as 'polygon soup'), the uniform and 'well-defined' arrangement of overhang-free terrain allows us to arrange the terrain as a two-dimensional array. This way, to determine the height, y, of the land at a point (x, z), we need only consider the four surrounding points (with positions [floor(x), floor(z)]×[ceil(x), ceil(z)]) and bilinearly interpolate their positions. This O(1) algorithm leaves your O(n) one in the dirt [razz].
If the terrain gets very big, some kind of partitioning (often a quad-tree) will probably become desirable, but it's not necessary.
As for the dynamic, seamless loading of vast terrains, the approach is simple in theory but slightly trickier in practice. We consider the height-map as a two-dimensional array of 'patches', each of which is a two-dimensional array of vertices. The aim is to keep as few patches in memory as possible while maintaining the illusion of infinite range. Using fog (for example) we can produce the effect of terrain that extends far into the distance without actually needing to render that much. For example, if our fog is set to be fully opaque at a distance of one patch's length away, then we only need to render the patch on which the player is standing and its eight neighbours. Any other patches will be invisible, due to the limited visibility range. So in this way, we can maintain the illusion by dynamically and incrementally 'paging in' new patches of land as they come into range and freeing up those that go out of range. A well-designed algorithm will need no more than nine patches resident in memory at any time but will allow the player to roam the entire land freely without any loading pauses.
Admiral
By far and away, heightmaps are the favoured structure for storing terrain data. Rather than having an orderless set of polygons (commonly referred to as 'polygon soup'), the uniform and 'well-defined' arrangement of overhang-free terrain allows us to arrange the terrain as a two-dimensional array. This way, to determine the height, y, of the land at a point (x, z), we need only consider the four surrounding points (with positions [floor(x), floor(z)]×[ceil(x), ceil(z)]) and bilinearly interpolate their positions. This O(1) algorithm leaves your O(n) one in the dirt [razz].
If the terrain gets very big, some kind of partitioning (often a quad-tree) will probably become desirable, but it's not necessary.
As for the dynamic, seamless loading of vast terrains, the approach is simple in theory but slightly trickier in practice. We consider the height-map as a two-dimensional array of 'patches', each of which is a two-dimensional array of vertices. The aim is to keep as few patches in memory as possible while maintaining the illusion of infinite range. Using fog (for example) we can produce the effect of terrain that extends far into the distance without actually needing to render that much. For example, if our fog is set to be fully opaque at a distance of one patch's length away, then we only need to render the patch on which the player is standing and its eight neighbours. Any other patches will be invisible, due to the limited visibility range. So in this way, we can maintain the illusion by dynamically and incrementally 'paging in' new patches of land as they come into range and freeing up those that go out of range. A well-designed algorithm will need no more than nine patches resident in memory at any time but will allow the player to roam the entire land freely without any loading pauses.
Admiral
Author
ah ha, i can see now how finding height at a point would be very simple with the heightmap approach, anything running in O(1) makes me happy. i think the combination of the heightmap patches and the quad-tree will work great.
the only hiccup i can foresee down the road is if i wanted to make a cave or an overhang of some sorts. i knew of heightmaps before but i was never sure how to handle layers of terrain thats why i tried the "polygon soup" method you mentioned, and caused me repeatedly beat my head against the wall.
thanks for the help TheAdmiral, you cleared up a lot of questions i had.
the only hiccup i can foresee down the road is if i wanted to make a cave or an overhang of some sorts. i knew of heightmaps before but i was never sure how to handle layers of terrain thats why i tried the "polygon soup" method you mentioned, and caused me repeatedly beat my head against the wall.
thanks for the help TheAdmiral, you cleared up a lot of questions i had.
If you want two seperate levels, you can just implement multiple patches.
First, have an entry for "nothing here".[1]
Second, each Patch can consist of layers of SubPatches. Most Patches have one SubPatch.
If you have a bridge above a road, you would have a SubPatch that contains the Bridge surface, and a SubPatch that contains the road under the Bridge.
The mobile object can be either on the bridge, or on the surface under the bridge. The mobile object can even from the surface under the bridge up onto the bridge by moving to where they intersect.
Now, when moving, you have to do an intersection test with all SubPatches to make sure the player never "slides through" any SubPatch surfaces. Be careful with floating point error here: it is easy to screw up.
Walls, Barriers, and the "underside" of caves are also a different problem. :)
You could represent the "underside" of caves by SubRoofPatches that you can't go through from the bottom. This has the nice property that everything will have to be a complete surface.
You could store Walls & Barriers and other terrain "decals" in the patches that they are sitting on. This could also be used to create extra details where you need it (so your terrain doesn't look like it is built on a grid).
Footnotes:
[1] "nothing here" is distinct from negative infinity: going from a finite value to negative infinity would represent a vetical wall, while going from a finite value to "nothing here" would represent the lip of a cave.
First, have an entry for "nothing here".[1]
Second, each Patch can consist of layers of SubPatches. Most Patches have one SubPatch.
If you have a bridge above a road, you would have a SubPatch that contains the Bridge surface, and a SubPatch that contains the road under the Bridge.
The mobile object can be either on the bridge, or on the surface under the bridge. The mobile object can even from the surface under the bridge up onto the bridge by moving to where they intersect.
Now, when moving, you have to do an intersection test with all SubPatches to make sure the player never "slides through" any SubPatch surfaces. Be careful with floating point error here: it is easy to screw up.
Walls, Barriers, and the "underside" of caves are also a different problem. :)
You could represent the "underside" of caves by SubRoofPatches that you can't go through from the bottom. This has the nice property that everything will have to be a complete surface.
You could store Walls & Barriers and other terrain "decals" in the patches that they are sitting on. This could also be used to create extra details where you need it (so your terrain doesn't look like it is built on a grid).
Footnotes:
[1] "nothing here" is distinct from negative infinity: going from a finite value to negative infinity would represent a vetical wall, while going from a finite value to "nothing here" would represent the lip of a cave.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
