Subject: PLG files

From: Wendell Joost <[email-masked]>
Date: Thu, 31 Dec 92 11:41:55 PST

I have an interesting algorithm problem.

I have a NASA Digital Terrain Model of a part of Valles Marineris 
(Mars).  This file is an array (200 x 90) of unsigned integers.  Each 
element in the array is an elevation point.  The points are 1 kilometer 
apart.  The file is effectively a digital topographic map with sampling 
points one kilometer apart.

I have written a program to take these 18,000 points and create a PLG 
file for use with REND386.  The problem is that I wind up with 36,000 
triangles.  REND386 doesn't do well with more than 1,000 polygons.

I have worked around this by subsampling the file, but I lose a lot of 
the terrain "texture".

Much of the area in this file is relatively flat.  What would be ideal 
is an algorithm which can determine the "flat" areas and will generate 
large polygons for those flat areas and use smaller polygons for the 
more "textured" areas.

Any hints or questions?

[email-masked]

---

From: Chris Hand <[email-masked]>
Date: Sat, 2 Jan 93 17:48:25 GMT

Wendell Joost said:
>  [ ... ]

I also did exactly this.  You can use other files with less samples
in, but you still get LARGE numbers of polygons.

> large polygons for those flat areas and use smaller polygons for the 

I've been mulling this over for a couple of months and have an algorithm
scribbled down somewhere (untested) for examining the polygons and
combining adjacent polys whose surface normals are "almost" parallel.
Especially with large "terrain" type objects it's possible to have
large areas that are flat, with bits of detail here and there.  Obviously
it's pointless having a large, flat area composed of 1000's of polys.

I wasn't sure if there was some classic algorithm that already does this
or not; I'm not an expert on graphics.

I haven't found time to do any coding or testing on this, and as several
people have pointed out, it's not necessarily a good idea to "do" terrains
by loading in one huge PLG since only a small amount of it will be visible at 
any one time -- some sort of caching scheme, or on-the-fly calculation
would be much more efficient on memory.  I believe Bernie is currently
working on some way of using extended memory with REND386, but you'd
have to ask him about that.

There were supposedly some articles in the SIGGRAPH 92 proceedings
about reducing the complexity of polygonal objects, although I haven't
managed to get hold of copies yet.  See Greg Turk's article on
re-tiling Polygonal Surfaces, pp55-64 and/or Schroder, Zarge &
Lorenson, "Decimation of Triangle Meshes" pp65-70.

Chris

-- 
Chris Hand, Lecturer                Internet mail: [email-masked]
Dept of Computing Science,          Voice: +44 533 551551 x8476
De Montfort University, The Gateway,  Fax: +44 533 541891  FIDOnet: 2:440/32.50
LEICESTER, UK   LE1 9BH             >> Linux: *free* unix for IBM PCs! <<