Archived

This topic is now archived and is closed to further replies.

Crispy

The Serious Terrain Thread (TM)

Recommended Posts

Crispy    556
I had a hard time thinking of a decent and at the same time humanely short title for this thread, so I apologise if it turns out to be way too vague or deceptively inaccurate. A short description of what I want to do would go like this: in a terrain editor, when the user clicks on the originally blank terrain canvas, a pin is added (the term ''pin'' is pretty much the shortes ad hoc word I could come up with to describe a control point). The pin is given an absolute height value, which determines the height of the terrain at that point, and a strength value, which determines the relative radius of effect for that pin. As a combination of randomly placed pins, a solid terrain is interpolated between them. I haven''t got to actually implementing this, but here are some initial thoughts I''m having: 1) the upside is the low consuption of hard disk space should the terrain be saved to a file 2) downside #1 is the (to me) undeterminable time it will take to generate the actual terrain data based on pin locations 3) downside #2 is the complete rigidness of the terrain and lack of response to localized manipulation (which is not too much of an issue in this case) Here''s what I want to get out of the terrain: 1) variable level of detail (not by traditional means such as ROAM; I only want to control the overall LOD) 2) ease of editing for the map designer 3) minimized disk requirements to allow for large terrains 4) the ability to slightly change the localized structural geometry of the terrain dynamically 5) non-linear features, which include nigh leaning slopes (cliffs that are almost vertical) 6) speed (both load time and realtime computational speed) 7) simplicity as far as implementation goes Here''s what I gather: 1) I can have relative simplicity, low disk space requirements, non-linear features, easy editing and very good control over LOD, but I am totally abhorred at the computational amount that is behind it all 2) I haven''t the slightest clue what method to use to create the terrain if the pins aren''t evenly distributed 3) too many pins will choke any computer alive What I''d like is for people with superior mathematical knowledge (which isn''t hard to come by) to comment on this and possibly assess the feasibility of such a method. Suggestions, naturally, are more than welcome!

"Finishing in second place, simply means you are the first loser." - PouyaCat

Share this post


Link to post
Share on other sites
sadwanmage    122
This seems a reasonable idea to me, but a few points come to mind:
1. Near vertical cliffs will be very difficult to do. Under your current system, you would need a pin at the top, and at the bottom. And along the edge of the cliff, you would need many pins before the cliff does not "wave" alot. There is no way of expressing a crease with your pins, just approximating it. (so likewise, a straight river would also be difficult).

2. It is easy to generate the terrain. You could always just convert it into a heightmap, as the pins allow you to calculate the height of any point. Then you could insert more triangles into steep points. There is also an algorithm for calculating an "irregular triangle network", that would probably be a good method. Google for that.

3. A few improvements that I suggest. You could have each pin store the normal to surface at that point. This would not be hard in an editor (you see the pin sticking out of the rock, and you drag the top of it). I think that would be worth the computational effort for the decreased number of pins, and increase in control over the landscape. You might also want pins to have an eliptical area of effect rather than circular. I am not sure how useful this would be...

Share this post


Link to post
Share on other sites
Crispy    556
sadwanmage:

I really like your suggestion to add normals to the pins! Didn''t think of this myself, but this further allows to play around with localized features on the terrain. I can''t see how an ellipical area of effect would improve things, but if I ever get far enough to actually have implemented the basics, I''ll be sure to give it a try.

I also had a look at TIN (the irregular triangle network model). While this is useful to know about, it actually sprung another idea in me: based on your suggesting that a straight river isn''t a realistically obtainable goal (which seems true enough, without having to set up too many pins).

The idea I had would be something like this: initially there are NxM pins laid out on the terrain in a regular grid (just like triangle intersection points). Each of the pins has a surrounding box, which borders on its neighboring pins'' surrounding boxes:


_|_____|_____|_
| | |
| . | . |
_|_____|_____|_
| | |


The pin (dot) can be moved around within its enveloping box (this distorts the terrain by stretching it). Each of the boxes can also be tessellated into four smaller boxes, each with their own pin.

This is basically the concept of LOD applied to easy terrain editing: by splitting a small area of pins many times, it is possible to arrange them so that vertical cliffs become a possiblity (since you can also move the pins around to accentuate certain features).

If some of the more ordinary pin placement structures (cliffs, hills, etc) are described with scripts/prebuilt funtions, this could lead to very simple terrain editing and possibly ultra-compressed terrain data. I haven''t really thoght this through yet - I guess I''ll just start tinkering with code and see what problems spring up since there''s most likely much more to this than meets the (my) eye.

One thing, however, that is really tempting about this method, is the fact that most likely no expensive 2D interpolation has to be done, which would otherwise make make the generation of the actual heightmap data very costly.




"Finishing in second place, simply means you are the first loser." - PouyaCat

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
For what its worth TINs are heavily used in the civil engineering sector for modelling ground (for example to predict the extents of expected flooding). The package most use for this is ESRI ArcView (with the 3d Analyst toolbox). The usual solution to the problem features such as a river is that you can define lines to be taken into account whilst generating the TIN, meaning that your rivers come out all nicely (of course you can use it for embankments etc. too - also highly important for flooding!). Try looking at some of the free GIS packages, they _might_ offer an implementation of the triangulation algorithm.

BTW its a Delaunay triangulation that you want to look into (this is the algorithm used to generate the TIN surface - IIRC I''ve seen it used in structural & fluid FEA/FEM tools too for triangulating surfaces)

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
There may be some useful info over at the Virtual Terrain Project page:

Virtual Terrain Project

Also, Jonathan Blow may have had some mention of editing/inserting points in his generalized LOD articles in Game Developer Magazine last year. Unfortunately, these articles don''t seem to be online at gamasutra..

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Charles B    863
My terrain technology does or will answer to any of your points from 1) to 7). I try to merge all the techniques known yet plus many things I suppose are currently unique. To get an idea my demo is 75K (.exe, no data), draws a 128*128kms terrain, has a zfar of 32kms, shows near details like rock shadows of 1cm. My ambition next is to merge various procedural/fractal generation techniques with various forms of compact data.

The main benefits being reduced load/download time and ease of use for level designers. I would put your more particular issue under the chapter :

"Terrain modelling : unevenly distributed LOD techniques".

The various TIN techniques fall into this chapter. But today we can consider more powerful mathematical objects than simple triangles. The goal is too have more detailed data, possibly handcrafted by a level designer where the action is. Elsewhere, further from the gamer, geometry can be smoother, or handled by pseudo random procedural techniques.

Your base idea is close to the simple Hills algorithm. Surf and start at the VTP home page and I guess you''ll find it. Each of your pin is a hill. It''s easy to convert a set of pins (absolute heights) to a set of hills (additive heights). I suppose the first pass of the algo is to order the pins by their radius and then define the relative height (h) of each hill by a formula like : hill.z = pin.z - EvalHeight(prevTerrain, pin.x, pin.y).

I suppose this would give decent results. I have tested Hills and improved the look of it (with continuous quartic shapes). This worked rather well. But maybe a simplified version of nurbs could also be found. Then it would be easy to take splines or nurbs that define cliffs or caves and merge them with a more classical height based system. Well I have some ideas oinb how to handle accurate dune creasts for instance. Height based means optimal rendering speed. Nurbs means generality. Hybrid systems mean best of both worlds ... as always. It would be too long to discuss here.


Share this post


Link to post
Share on other sites
Crispy    556
I apologise for a complete lack of reponse on my side in this thread - however, I was determined to get some code down before posting anything - if only to avoid excessive hypothesizing.

Anyway - here is the system that I have so far devised, that seems the most flexible, fast and simplistic to me:

the terrain is initially divided into N x M pins that are the leaf nodes of a simple quadtree. When a pin is shifted in any direction, it becomes a control pin, that has a relevant radius of effect and tension, which defines the nature of the slope the pin''s area of effect has. The tiles affected by the control pins are cumulative, allowing for extreme changes in the environment, up to nigh verical cliffs, as well as smooth, low hills. I have this down in code and it works just fine - the ability to further tessellate each leaf node into four child nodes, allows even better control over the level of detail in certain areas.


The problem at this point is rendering. Namely, rendering a simple quadtree is not so much of an issue, as is being able to properly, and quickly calculate the corners of each node. I do not have a normal-based system devised, that would allow me to calculate the orthogonal surface to the normal to specify a node''s corners. What''s more - I don''t want a normal-based system, at least not at this stage, since it eats up tremendously more resources (forcing me to call sqrt per pin), as well as introducing additional complexity, which I do not want.

Another problem is that of LOD - since different nodes can have different base depth in the quadtree, the issue of alignment becomes a problem. Without being able to calculate the corners of one node, I do not see a way to efficiently build a system that would render the entire quadtree. Here''s an ascii art example of the problem:
    
N
__.__
./ n3 \.
__.__ / n2 n4 \ _._._
n1 n5 n6


The dots (n1 through n6) are pins and N is a control pin (the lines are imaginary!). I know the depth of the quadtree at a specific pin (the diagonal and edge lengths of the tile the pin is centered on) and that is about it.

To demonstrate the situation more wholly, n5 and n6 are leaves of depth Q + 1, while n1 ... n4 are of depth Q.

What I need, is to render triangles around (not between - the pin is the center point of a tile) each pin in a 3D version of the drawing. Mind you that n1 and n2 may belong in completely different nodes and quite honestly I have no idea how to make the lookup of this adjacency fast.

If anyone can suggest a neato solution to the problem, it''d be just super.



For people that find this stuff interesting: what I also considered, but rejected.

1) Only adding control pins to an empty terrain

Pros:

  • no intermediate pins
  • can potentially consume almost no HDD space


Cons

  • need a lot of pins to achieve even moderate resolution - this amounts to unexpected HDD space consumption (that is, while few pins are needed to describe the environment, many are needed to do it well)
  • editing is a real pain
  • requires an implementation of either the Voronoi or Delaunay trianglation/tessellation method (increases complexity)
  • precalculation time is potentially huge


2) Using the current system, but interpolating bewteen pins instead of additively blending

Pros:

  • potentially very nice terrain features (very smooth)
  • no "cuts" at hill transitions


Cons:

  • poor control over sharp edges and steep cliffs
  • hard to control resolution (LOD) during editing
  • computationally prohibitive
  • overly complex (for me at least)






"Finishing in second place, simply means you are the first loser." - PouyaCat

Share this post


Link to post
Share on other sites