Archived

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

SoaringTortoise

Help with a cliff-face algorythm. PLEASE!

Recommended Posts

I''m having a hard time getting to grips with how to start with a cliff-face generating algorythm. My situation is pretty simple: 1) I have a height-mapped terrain. 2) Each point on a height-map has a height property and a cliff-height value (0-10). 2.1) For each tile (2x2 collection of points) on the height-map that has the same cliff-height value, the geometry is created as a normal quad. 2.2) For each tile that has differing cliff-heights, I need to create cliff faces. So, the following area 00 00 would be a normal quad with vertices generated by the height-field. This area 01 00 would be created as a flatish bit at the bottom and a cliff segment in the top-right corner. My problem is that I have no idea how to go about actually creating the cliff-face. My general algorythm goes something like this: :Assume we are here because we have a cliff: 1) Check all four points to find the lowest cliff-height 2) With the lowest cliff-height, generate a standard quad using either the height of the point if it is at the lowest cliffheight, or the Height - (MyCliffHeight - LowestCliffHeight) if you are any other height. (This gives me a base quad) 3) Find the next highest group of cliff-heights and create a cliff-face for them as well as a cliff-top for that area. The problem is, how can I figure out the outline for the continuous cliff area? View from above, 01 00 Would be something like a box |_ (a single continuous edge) 01 10 would be more like // (two edges) At the moment I am hard-coding the 12 possible patterns and then using pattern-matching to find out which is the appropriate cliff-face to use, but this is nasty and inflexible. Anyone have any ideas?

Share this post


Link to post
Share on other sites
I could be wrong but this is what I would do:

First, because you are dealing with quads (ie. tiles) with (I assume (2 faces), the minimum number of vertices required to define a difference in height would be 2. 2 being the vertices of the edge that will be your cliff.

So, I would have:

0----1----2----3
| | | |
| | | |
4----5----6----7

I''m not considering 2 trianglelists but complete quads here. Consider quad 0145 being at an elevated height. Quad 2367 will be ground level. Therefore quad 1256 will be my cliff, and I will render it with my cliff texture.

Hope this helps,
Ivan

Share this post


Link to post
Share on other sites
OK, but the problem with that is that the cliff is forced to have an incline -> you can not do sheer cliff faces.

For example

0----1-2----3
| | | |
| | | |
4----5-6----7

where the cliff between 1-2, 5-6 becomes near-vertical because the horizontal distance is contracted.

So, my plan is to work on adding geometric complexity to a single tile, therebye giving me far more control (my cliff can take on different characteristics other than just texture). If I define the control points for a cliff tile like this (all other tiles being just two polys):

0-------a------1--------------2--------------3
|              |              |              |
|       b      |              |              |
d     c   e    f              |              |
|       g      |              |              |
|              |              |              |
4-------d------5--------------6--------------7

the lettered points give me additional control points from which I can draw vertical cliffs. A corner cliff would be
0-------a------1--------------2--------------3
|=======|      |              |              |
|=======b      |              |              |
d=====c/  e    f              |              |
|       g      |              |              |
|              |              |              |
4-------d------5--------------6--------------7

A top cliff

0-------a------1--------------2--------------3
|==============|              |              |
|=======b======|              |              |
d-----c/ \e----f              |              |
|       g      |              |              |
|              |              |              |
4-------d------5--------------6--------------7

and a diagonal cliff would be

0-------a------1--------------2--------------3
|=======|      |              |              |
|=======b      |              |              |
d-----c =\e----f              |              |
|      \g======|              |              |
|       |======|              |              |
4-------d------5--------------6--------------7

If I introduce a randomness factor to the location of the control points, I can do walls (rand=0) or craggy chalk cliffs (rand=1). 

I'm only showing a single cliff tile here. Obviously, all the adjacent tiles with differing cliff heights would also have cliff faces, like this:

0-------a------1--------------2--------------3
|=======|      |              |              |
|=======b      |              |              |
d-----c =\e----f------\       |              |
|      \g======|======|       |              |
|       |======|======|       |              |
4-------d------5--------------6--------------7
0-------a------1--------------2--------------3
|       |======|======|       |              |
|       b======|======|       |              |
d       \e----f------/       |              |
|              |              |              |
|       |      |              |              |
4-------d------5--------------6--------------7


[edited by - SoaringTortoise on October 15, 2003 8:01:51 AM]

Share this post


Link to post
Share on other sites
So basically what you are doing is subdividing your original 2-face quad into a 4-face quad (or to whatever detail needed)?

Share this post


Link to post
Share on other sites
Yah. I''ve been using the Warcraft III editor as a reference project, and they seem to be using mesh tiles for their cliffs (with some fancy coding to pin them to the terrain VB). I tried going the same way and couldn''t get the alignment to work right, so I switched to the sub-division method which works quite well.

By being able to effectively cover a cliff-height using a horizontal distance 1/4 the length of a normal tile, the cliff faces appear far more vertical.
[from side]
Normal
\
o\
oo\
ooo\
oooo\

Subdivided
__
00|
00|
000|
000|_

Plus, by assigning weights to each vertex in the subdivided tile I can get different characteristics -- Convex, concave, linear and near-vertical -- by simply changing a couple of a parameters. Another parameter can control "vertex zones" to introduce a degree of randomness to the cliff. That is, instead of saying point is at 0,0 you can say point is in the range of -0.1,-0.1 and 0.1,0.1.

All in all, a pretty neat solution. Of course, it does end up using 32 polys instead of 2, but since cliff faces are comparatively rare it''s an acceptable performance hit.

Share this post


Link to post
Share on other sites
Yah sounds like a good implementation. As you said, cliff faces would be rare, even in a huge terrain so it won''t increase your vertexcount drastically.

I don''t know how blizzard are doing it. Either meshes for individual tiles or a standard vertex buffer. If they use meshes, then they would have the different cliff meshes combinations. If not, they''ll have to use some kind of algorithm like you''re implementing.

I would assume that you will use the same technique for doing depressions then.

Do you have some screenshots of this editor of yours? I''m really interested in it

Ivan

Share this post


Link to post
Share on other sites