gdalgorithms-list

[Algorithms] Terrain Organization

[Pai-Hung C. <pa...@ac...>]

Hi,

I have a terrain of 5000~6000 triangles (I would like to make it
higher) in my upcoming 3D RPG game (my master thesis).  (I am
using an ELSA Erazor X^2 GeForce card with Direct3D IM.)  I am
always wondering what is the best terrain orgnization algorithm to
organize and render my terrain.  Meanwhile I am planning to split
the terrain up to several _hierarchical_ chunks (with bounding
boxes) and, for each frame, I test each chunk against the current
viewing frustum (VF) to _recursively_ determine if it has to be
submitted to the transformation and rendering pipeline.  If an
_upper-level_ chunk is rejected, there is no need to go down to
the _lower-level_ chunks inside it, which can quickly reject a
huge amount of geometry.  This technique sounds extremely crude,
but, with its relatively low geometry management overhead, I think
it is very efficient, despite its "obviousness."  (Please correct
me if I am wrong.)  I know there are lots of other more
sophisticated/advanced techniques such as BSP and ROAM, but I
doubt if they are really worth their extra huge geometry
management cost in real-time 3D applications.  Here are my
opinions about the BSP and ROAM:  (Please correct me if I am
wrong.)

(1) BSP:
I think a basic BSP can only tell you what is _in front of_ you.
But most of the time you don't really want to draw everything that
is in front of you, but only those that are inside the current VF,
which still requires the VF testing.  Also, since BSP is in
triangle level, there will potentially be more texture stage
changes when rendered.

(2) ROAM:
This is way too complicated for my poor brain...  Tjhe idea of LOD
is great but I really doubt if ROAM is really worth its extra
management cost since you have to re-construct everything in each
frame.  This leads me to the thinking of whether ROAM has other
better targeted applications than real-time 3D games running on
PCs.

Apart from the three techniques mentioned above, are there other
universally agreed better ways to handle richly-textured terrain
in 3D game?  Any comments are highly appreciated!  (Relating to
D3D would be great!)

Thank you,

Pai-Hung Chen

Re: [Algorithms] Terrain Organization

[<fa...@no...>]

Hi,

I'm new to terrain rendering, but at this right moment I was reading an
article about ROAM ; looks very interesting and not so hard, when it's well
explained as it is on
http://www.psky.com/prog/terrain.htm
Have a look !
It seems that you do NOT have to reconstruct all the stuff for each frame,
and it's precisely one of the interests of ROAM.

Good luck.

Fred

----- Original Message -----
From: Pai-Hung Chen <pa...@ac...>
To: <gda...@li...>
Sent: Sunday, July 30, 2000 1:51 AM
Subject: [Algorithms] Terrain Organization



> (2) ROAM:
> This is way too complicated for my poor brain...  Tjhe idea of LOD
> is great but I really doubt if ROAM is really worth its extra
> management cost since you have to re-construct everything in each
> frame.  This leads me to the thinking of whether ROAM has other
> better targeted applications than real-time 3D games running on
> PCs.

Re: [Algorithms] Terrain Organization

[Pai-Hung C. <pa...@ac...>]

Fred wrote:

> Hi,
>
> I'm new to terrain rendering, but at this right moment I was
reading an
> article about ROAM ; looks very interesting and not so hard,
when it's well
> explained as it is on
> http://www.psky.com/prog/terrain.htm
> Have a look !
> It seems that you do NOT have to reconstruct all the stuff for
each frame,
> and it's precisely one of the interests of ROAM.

Actually I've read the original ROAM paper and another one on
Gamasutra, and was helplessly frustrated. :-(  I'll look at the
one you suggested to see if it makes any more sense to me.  Thanks
a lot!

Pai-Hung Chen

[Algorithms] Smooth movement of camera along a path

[Mark W. <mwi...@cy...>]

I'm trying to write a fly-by sequence (similar to the Unreal
intro) for my 3d engine.  Can anyone tell me how to smoothly
move the camera along a set of predefined 3d points?
Ideally,  I would like a system where I manually move the
camera around the environment and record keyframes at
certain positions/orientations.  Then I would like the
system to automatically move the camera along a path
interpolated from these keyframes.  I'm guessing I need some
sort of spline or other curve to do the job?

-Mark

Re: [Algorithms] Smooth movement of camera along a path

[Will P. <wi...@cs...>]

Catmull-Rom splines interpolate all control points, so they would be worth
checking out.  Look at:

http://graphics.cs.ucdavis.edu/CAGDNotes/Catmull-Rom-Spline/Catmull-Rom-Spline.html

The standard graphics textbooks have better expositions than this web page
if you have access to them.

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will

On Mon, 31 Jul 2000, Mark Wilczynski wrote:

> I'm trying to write a fly-by sequence (similar to the Unreal
> intro) for my 3d engine.  Can anyone tell me how to smoothly
> move the camera along a set of predefined 3d points?
> Ideally,  I would like a system where I manually move the
> camera around the environment and record keyframes at
> certain positions/orientations.  Then I would like the
> system to automatically move the camera along a path
> interpolated from these keyframes.  I'm guessing I need some
> sort of spline or other curve to do the job?
> 
> -Mark
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Smooth movement of camera along a path

[Jamie F. <j.f...@re...>]

Easiest spline to use for this is Catmull Rom, which if I remember
correctly allows you to keyframe the way you want to.

For a Java link, try

http://www.media.mit.edu/~rich/research/java/docs/acg.stuttgart.rich.spline.CatmullRomSplineLoop3D.html

I've no idea how good it is, I was only searching to remind myself of
the name :)

Jamie


Mark Wilczynski wrote:

> I'm trying to write a fly-by sequence (similar to the Unreal
> intro) for my 3d engine.  Can anyone tell me how to smoothly
> move the camera along a set of predefined 3d points?
> Ideally,  I would like a system where I manually move the
> camera around the environment and record keyframes at
> certain positions/orientations.  Then I would like the
> system to automatically move the camera along a path
> interpolated from these keyframes.  I'm guessing I need some
> sort of spline or other curve to do the job?
>
> -Mark
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Smooth movement of camera along a path

[Mark W. <mwi...@cy...>]

Will and Jamie,

Thanks for the help.  This was exactly what I needed.  The
info was right in front of me in one of my books.  I just
didn't realize what it was called.

-Mark

> Catmull-Rom splines interpolate all control points, so
they would be worth
> checking out.  Look at:
>
>
http://graphics.cs.ucdavis.edu/CAGDNotes/Catmull-Rom-Spline/
Catmull-Rom-Spline.html
>
> The standard graphics textbooks have better expositions
than this web page
> if you have access to them.
>
> Will
>
> ----
> Will Portnoy

> Easiest spline to use for this is Catmull Rom, which if I
remember
> correctly allows you to keyframe the way you want to.
>
> For a Java link, try
>
>
http://www.media.mit.edu/~rich/research/java/docs/acg.stuttg
art.rich.spline.CatmullRomSplineLoop3D.html
>
> I've no idea how good it is, I was only searching to
remind myself of
> the name :)
>
> Jamie
>
>
> Mark Wilczynski wrote:
>
> > I'm trying to write a fly-by sequence (similar to the
Unreal
> > intro) for my 3d engine.  Can anyone tell me how to
smoothly
> > move the camera along a set of predefined 3d points?
> > Ideally,  I would like a system where I manually move
the
> > camera around the environment and record keyframes at
> > certain positions/orientations.  Then I would like the
> > system to automatically move the camera along a path
> > interpolated from these keyframes.  I'm guessing I need
some
> > sort of spline or other curve to do the job?
> >
> > -Mark
> >

Re: [Algorithms] Terrain Organization

[Relja M. <re...@in...>]

Check the archives on this one, but I think someone (nVidia, perhaps?) said
once that on TnL type cards it is more efficient to pump the polygons at the
card than to spend too much time (ROAM) LODding on the CPU. If that is true
(I for one think it makes sense), the recursive quadtree you described would
work just fine. Apparently, terrain LOD has no future with TnL - unless you
want some extremely detailed stuff up front. Anyway, if your terrain has 5-10
K polys in an average scene, you could care less if you LOD it down to 2-5K
on a TnL card...

Relja

Re: [Algorithms] Terrain Organization

[Mats L. <ma...@al...>]

I've also thought of something similiar to what you proposed...

 Meanwhile I am planning to split the terrain up to several _hierarchical_
 chunks (with bounding boxes) and, for each frame, I test each chunk
against the   current viewing frustum (VF) to _recursively_ determine if it
has to be
 submitted to the transformation and rendering pipeline.  If an
_upper-level_   chunk is rejected, there is no need to go down to the
_lower-level_ chunks   inside it, which can quickly reject a huge amount of
geometry.

I don't se anything wrong with it. No fancy geometry calc:s, just a simple
recursive function that goes through a quad tree. I mean, how much simpler
can you make it?? It maybe crude but hey, it works. Right?? 

Re: [Algorithms] Terrain Organization

[Pai-Hung C. <pa...@ac...>]

> I've also thought of something similiar to what you proposed...
>
>  Meanwhile I am planning to split the terrain up to several
_hierarchical_
>  chunks (with bounding boxes) and, for each frame, I test each
chunk
> against the   current viewing frustum (VF) to _recursively_
determine if it
> has to be
>  submitted to the transformation and rendering pipeline.  If an
> _upper-level_   chunk is rejected, there is no need to go down
to the
> _lower-level_ chunks   inside it, which can quickly reject a
huge amount of
> geometry.
>
> I don't se anything wrong with it. No fancy geometry calc:s,
just a simple
> recursive function that goes through a quad tree. I mean, how
much simpler
> can you make it?? It maybe crude but hey, it works. Right??

Yes, it's both simple and efficient, I think.  I am just wondering
how efficient it compares to other more sophisticated techniques
such as BSP and ROAM in a _general_ manner.  I haven't seen any
article that compares the "plain vanilla" approaches to the
"fancy" ones in this respect.

Any comments?

Pai-Hung Chen

Re: [Algorithms] Terrain Organization

[Jim O. <j.o...@in...>]

In addition, you might consider using a preprocessed RTIN version of your
landscape to remove some triangles from the flat areas of your terrain.

Jim Offerman

Innovade
- designing the designer
----- Original Message -----
From: "Mats Lundberg" <ma...@al...>
To: <gda...@li...>
Sent: Sunday, July 30, 2000 11:00 PM
Subject: Re: [Algorithms] Terrain Organization


> I've also thought of something similiar to what you proposed...
>
>  Meanwhile I am planning to split the terrain up to several _hierarchical_
>  chunks (with bounding boxes) and, for each frame, I test each chunk
> against the   current viewing frustum (VF) to _recursively_ determine if
it
> has to be
>  submitted to the transformation and rendering pipeline.  If an
> _upper-level_   chunk is rejected, there is no need to go down to the
> _lower-level_ chunks   inside it, which can quickly reject a huge amount
of
> geometry.
>
> I don't se anything wrong with it. No fancy geometry calc:s, just a simple
> recursive function that goes through a quad tree. I mean, how much simpler
> can you make it?? It maybe crude but hey, it works. Right??
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Terrain Organization

[Tom H. <to...@3d...>]

At 01:03 PM 7/30/2000 +0200, you wrote:
>Check the archives on this one, but I think someone (nVidia, perhaps?) said
>once that on TnL type cards it is more efficient to pump the polygons at the
>card than to spend too much time (ROAM) LODding on the CPU. If that is true
>(I for one think it makes sense), the recursive quadtree you described would
>work just fine. Apparently, terrain LOD has no future with TnL - unless you
>want some extremely detailed stuff up front. Anyway, if your terrain has 5-10
>K polys in an average scene, you could care less if you LOD it down to 2-5K
>on a TnL card...

I have a few problems with those assertions:

1. A terrain with 5-10k polys in the scene is pretty weak. To have good 
detail up close, and have a large view distance (10,000 meters is a goal 
for me, although infinite yon clip with a spherical world would be even 
better) you end up with 100s of thousands of triangles in a single scene at 
full tessellation.
2. Not everyone has TnL capable machines, and it is generally a "good 
thing" if your engine can scale across systems with different geometry 
performance.
3. You _can_ do continuous terrain LOD on a TnL card, but you are bound by 
the LOD calculation itself, and hence, CPU speed as you mention. However, 
things can and are being sped up greatly on this front, both with faster 
CPUs, and better split metrics.

Now, that isn't to say that CLOD terrain is for everyone. Far from it. For 
small view areas and rather coarse tessellation of static terrain, just 
drawing a static LOD works quite well.

Tom

Re: [Algorithms] Terrain Organization

[Relja M. <re...@in...>]

Tom, you are right about LOD being useful at 100K triangles. I thought the
original poster was talking about smaller terrains. 10K viewable triangles is
good enough for me, but everybody has different tastes, right...

As for not everyone having TnL cards, well, I thought that any game which is
*now* in development will probably run on fast systems. By fast I mean either
TnL, or on CPUs which are fast enough that regular cards don't suffer too
much. Anyway, this is up to you, it depends on you budget and a lot of other
things.

Greetings,
Relja Markovic

From: "Tom Hubina" <to...@3d...>
> At 01:03 PM 7/30/2000 +0200, you wrote:
> >want some extremely detailed stuff up front. Anyway, if your terrain has
5-10
> >K polys in an average scene, you could care less if you LOD it down to
2-5K
> >on a TnL card...
>
> I have a few problems with those assertions:
>
> 1. A terrain with 5-10k polys in the scene is pretty weak. To have good
> detail up close, and have a large view distance (10,000 meters is a goal

> 2. Not everyone has TnL capable machines, and it is generally a "good
> thing" if your engine can scale across systems with different geometry
> performance.

Re: [Algorithms] Terrain Organization

[Jim O. <j.o...@in...>]

> As for not everyone having TnL cards, well, I thought that any game which
is
> *now* in development will probably run on fast systems. By fast I mean
either
> TnL, or on CPUs which are fast enough that regular cards don't suffer too
> much. Anyway, this is up to you, it depends on you budget and a lot of
other
> things.

If you are going to implement some form of CLOD (this is where Tom Forsyth
would promote using VIPM - which is not a bad idea at all), I think you
should couple the runtime error calculations to your fps... i.e. if your fps
drops, crank down all lod levels in the game until the fps reaches an
acceptable level. Your gime might be spitting out 100K tris per second on a
souped up PIII with GeForce2 GTS and pump through a humble 15K on a PII with
TNT PCI.

And, since you have tied your CLOD calculations to the fps you could
(theoratically) also truly design your game for the future - i.e. use models
which by todays standards contain far to many triangles, the CLOD will keep
performance acceptable on today's high end hardware and increase detail on
tomorrow's hardware. Imagine playing Half-Life again, finding that the
overall detail has increased by a factor ten.

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] Terrain Organization

[<Lea...@en...>]

> 1. A terrain with 5-10k polys in the scene is pretty weak. To have good
> detail up close, and have a large view distance (10,000 meters is a goal
> for me, although infinite yon clip with a spherical world would be even
> better) you end up with 100s of thousands of triangles in a single scene at
> full tessellation.

You can have a lot of detail up close, but you can quickly reduce the
amount of geometry sent to the card with things like basic lumigraphs,
reduced quad texture based geometry visualisation, etc... I've had our
terrain engine running at 35 km view distance and it looks nice... but
I haven't done any terrain stuff for a while now.

> 2. Not everyone has TnL capable machines, and it is generally a "good
> thing" if your engine can scale across systems with different geometry
> performance.

This is the difference -- we require TnL HW. I honestly believe that
ROAM is the way to go for CPU transformation engines, but not so for
HW TnL based engines... the best thing for people trying to support
both would be implement both -- but that's a lot more development.

> 3. You _can_ do continuous terrain LOD on a TnL card, but you are bound by
> the LOD calculation itself, and hence, CPU speed as you mention. However,
> things can and are being sped up greatly on this front, both with faster
> CPUs, and better split metrics.

As are expectations with 3D audio, physics, and in our case, AI... :)
 
> Now, that isn't to say that CLOD terrain is for everyone. Far from it. For
> small view areas and rather coarse tessellation of static terrain, just
> drawing a static LOD works quite well.

I agree that both methods have their benefits and audiences... it's a
matter of deciding at the start which suits your particular purpose.

Leathal.