[ROAM Algorithm Homepage] [ROAM Algorithm Version 2 work in progress]
[Edited a bit to remove email addresses and for formatting]
Subject: Re: [Algorithms] Current state of Terrain Generation
Date: Mon, 06 Jan 2003 17:18:50 -0800
From: Mark Duchaineau
To: xxxxxxxxxxxxxxxxxxxxxxxxx
Hi Tony,
I'm not currently working on this, I was just offering suggestions.
I have been thinking about this for many years though, and implemented
a lot of related things a while back. I recall a nice siggraph
paper on procedural river basins perhaps ten years ago (my memory
is really vague--I don't even recall the authors, just the images).
I'd be really interested in any results you get. Seems fairly
straightforward to just create a random tree that refines as the
triangle mesh refines, and enforces monotonicity along drainage lines.
At any step you would have edges in the tree being a subset of all
edges in the triangulation (either the edges in the triangulation
graph or the dual graph). In the primal scheme, edges can be introduced
into the interior (at most one) or "kinked" in from the boundaries,
or "slid in" from one of the corners with a spoke going out. ASCII
art of these cases:
Solid lines are rivers, dotted lines are not, o's are the current vertices
| |
o o
... .|.
. . . . | .
. . . . | .
-o . o- -> -o...o...o- (similar cases if any of four
. . . . . . boundary edges is solid)
. . . . . .
... ...
o o
| |
o o
/.. ...
/ . . . . .c (similar if edges a,b or c are
/ . . . . . solid)
-o . o- -> -o---o...o-
. . . . . .
. . . a. . .b
... ...
o o
| |
o o
/.. .|.
/ . . . | .
/ . . . | .
-o . o -> -o---o...o (same additional cases as above)
. . . . . .
. . . . . .
... ...
o o
o o
/.\ .|.
/ . \ . | .
/ . \ . | .
-o . o- -> -o---o---o-
. . . . . .
. . . . . .
... ...
o o
| |
| |
o o
.|. .|.
. | . . | .
. | . . | .
-o | o- -> -o...o...o-
. | . . | .
. | . . | .
.|. .|.
o o
| |
| |
o o
/|\ .|.
/ | \ . | .
/ | \ . | .
-o | o- -> -o---o---o-
. | . . | .
. | . . | .
.|. .|.
o o
| |
...etc...etc...
This comes down to finding a complete set of cases, which if randomly
invoked can produce any river tree in the limit as you refine indefinitely.
This gives a structural framework, then the heuristics come in for
deciding the actual heights and probabilities for the various cases
that are available. This is one approach that is arguably general, but there
are certainly many others one could imagine. The nice property of this
method is that it is strictly local, coarse-to-fine, general, and
a natural match for a real-time view-dependent display algorithm.
p.s. feel free to post this to the list if you like. I notice you
replied privately to me.
Cheers,
--Mark
VRBones wrote:
>
> Hi, I have been developing a river basin bifurcation method recently and was
> not aware of other attempts along these lines. I would be very interested in
> any references you have on the subject ...
>
> Thanx in advance
> Tony Bowes
>
> > That answers part of your question. The part about getting cliffs
> > and features other than "melted ice cream" is a good one. This has
> > been studied a lot, and I think there are simple variations on the
> > framework of midpoint displacements that can get you these things.
> > Example: you can randomly toss in "cliff curves" (midpoint displaced
> > parametric curves in the X-Y plane) as you subdivide, and then
> > modify the displacement probabilities in the vicinity of these curves
> > for the terrain to create ridges, cliffs, etc. You can "grow" more
> > complex river basin trees coarse-to-fine in a similar way. I didn't
> > bother to put this in because I was focusing on the ROAM more than
> > the procedural terrain quality.
> >
> > Others have procedural planets that look quite impressive.
> > Dave Hill has done extensive work with good results.
> >
> > Cheers,
> >
> > --Mark D.
> >
> > > Chris Brodie wrote:
> > >
> > > I'm an independent developer. In the past I thought about using
> heightfields
> > > to define my terrains as they are flexible enough to allow me to modify
> the
> > > terrain to place roads \ bases etc, however my game will need to be
> > > downloaded to be played and I don't see the large detailed environments
> I
> > > envisage to be able to be supported by a minimal download over the
> > > internet(especially if the user just wants to try the game out).
> > >
> > > So, I turn to terrain generation. I read a few Gems I articles and
> looked
> > > around the net a little and found that :
> > >
> > > -all the generated terrains I find look like melted ice-cream. Rolling
> hills
> > > are nice for a while but I'm looking for cliffs canyons and valleys,
> with
> > > terrain interesting enough to allow players to use it for hiding \
> dodging
> > > (Think Battlezone style of play)
> > >
> > > -If my terrains are large enough I might not be able to store the verts
> in
> > > memory. I don't see many cases of paging + terrain generation.
> > >
> > > -Will my solution lie in the middle. Perhaps a pre-process that runs on
> > > install of the app and generates heighmaps on the destination PC?
> > >
> > > Advice appreciated...
> > >
> > > Chris
> > >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDAlgorithms-list@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_id=6188
> >
> >
[Note: Tony suggested in a subsequent email to me that another rule is needed: add a new island or lake -- thanks tony!]
-- Mark Duchaineau
Updated 2003-02-20 -- duchaine@llnl.gov