Low-Memory + High-Poly
cbloom@cbloom.com
Jun 23, 2000
--------------------------------------------------------------------

At 12:33 PM 6/23/2000 -0500, John Ratcliff wrote:
>I don't think there is really any decent solution to this problem, but it's
>going to become a major issue for a lot of games in the near future.  The
>issue is when we have 3d hardware which can push massively more mesh and
>texture data than you can feasibly hold in memory.  This applies to the
>PSX2, and to a lesser extent, the X-Box.  The X-Box 'only' has 64mb of
>memory, which sounds like a lot, until you hear the amount of geometry they
>claim can be run through the thing every frame.  Just, exactly, where is all
>that geometry supposed to fit??
>
>It's much worse on a PSX2 where there is only 32mb of system ram for
>operating system, program executable, textures, and geometry, and no virtual
>memory.  It's either in ram or on the CD, one or the other.
>
>You use that up on a single high resolution mesh, much less worlds composed
>of millions of polygons.
>
>Any thoughts, strategies?
>
>John
>

This is a topic I've been thinking about alot recently.  I think that
subdivision surfaces is probably not a great solution, because doing
subdivision at the PS2 graphics processor level is too much CPU work in
that stage, and too much memory touching.  You would also have to send
something like a winged-edge structure from the main CPU to the graphics
CPU so that it has all the neighbor information it needs; if you're going
to use all that memory, you might as well just send the triangles.

I think the best solutions are :

1. heightmaps can be turned into tri-strips quite easily. Eg. you can
store a 256x256 heightmap in just 64k of RAM (yielding 128k triangles).
The equivalent triangle mesh would be about 32 times larger (5*float +
6*short). So, rather than doing static-LOD or any kind of LOD for
terrain, just fire the whole heightmap!! This is great, except that for
truly large terrains, you'll still need to do some kind of LOD. That
could be done with a quad-tree structure where the heightmap chunks in
the distance got mip-mapped down. The problem now is, of course, joining
up the chunks, which is rather a bitch, imho. I think the coolest way to
join them up is whenever you have a heightmap of dimensions N bordering
one of dimensions 2N, you "blur" the boundary pixels of the higher
dimension map. I would imagine pushing this terrain system with a
largest size of 64x64, and aiming at about a 128k triangle total count
for the terrain, which would be 4 Million tris/sec at 30 fps, well
within the capacity of the PS2, since the memory bandwidth is so low.

addendum: the heightmaps of different resolutions could be explicitly
T-joint-fixed by giving the tesselator an explicit line of
intermediate verts for the seam between two chunks.  If you
constrained your quad-tree to only have a depth difference of
one across edges in the tree, then at a boundary between a
heightmap of dimension N and one of dimension 2N you would
simply have to send the additional N inter-elevel values with
the lower resolution map, and it would add an extra triangle at
each vert of that boundary.

2. low-poly surfaces with displacement maps is probably a good solution,
if you can figure out how to tesselate arbitary triangles into
displacements quickly. Obviously, you could just do a subdivision
surface to some depth, and move the vertex positions based on the
displacement map (after subdivision). If you don't do subdivision, then
you get funny-looking results. The uv look-ups for the displacement
mapping are probably quite expensive, but I think this may be the
rendering primitive of the future for console hardware. BTW I think that
Bezier triangles are probably better than subdivision surfaces, because
they are "inclusive", that is, you can tesselate a triangle without
looking at its neighbors. I would recommend using the recent Siggraph
techniques to find the bezier triangles which match the Catmull-Clark or
Butterly subdivision surfaces. The easiest way to do this is simply to
do the subdivision down to a few levels, and then use the location of
the verts to find the (order-4) bezier triangles that result in the same
vertex locations. Maybe we can have a race to the first implementation
of this in real-time, pushing 128k tri models :^) The papers from
Caltech on turning high-poly models into subdivision + displacement
clearly show us that you can make great models this way. There's a
potential problem in that you need rather high resolution displacement
maps in order to get nice looking results on character models. Of
course, you should use some sort of mip-mapping to get the memory use
down, but if all your characters have different high res displacement
maps, you're into the whole high memory-use soup again. If you can use
procedural displacement maps, that's fantastic, but I've seen very few
practical procedural displacement maps outside of eye-candy (eg. doing a
character's face with procedurals seems quite difficult).

addendum: procedural displacement maps would be fantastic for use with
subdivision of low poly models, but I think that procedural
displacement (and bump) maps are not really interesting for
anything but eye-candy on spheres on toruses (eg. doing the
scales of a snake, or the face of a human is quite difficult
with procedurals).

3. paged-in VIPMs. I discuss this in the VIPM tech doc on my page. Since
the VIPM is totally linear, you can keep only the amount you actually
need in memory, so that distant, low detail objects, only need the
memory to hold the verts that are visible. Also, the VIPM refinement
structure is very compact. You would use some sort of smart caching
system where you kept 4 megs of memory (or so) for all your VIPMs, and
you added verts to the objects that the viewer is moving towards, while
you took detail away from other objects. Of course, this doesn't
increase the total number of triangles you can push (roughly 128k
triangles/frame in those 4 megs of memory), but it makes the scene look
like it has 1 million + tris while only using 4 megs.

4. procedural stuff is great when you can use it, but of limited
practical value. Bezier curves are fantastic for cloth and hair and
such; do the physics on the control points, it's beautiful. You can send
a 3d sprite with just one vector for position. You could do spheres or
other primitives on the back-end, but that doesn't seem very useful to
me (could make for some interesting retro-looking games, though, made
entirely of platonic solids or something). You could do water waves with
functional heightmaps, made up of a bunch of sin's and cos's. etc.. I'm
sure there are lots of clever things here, but all are quite
application-specific. (you could do 3d perlin clouds, like Hugo Elias's,
but using polygons to give the clouds volume)

--------------------------------------------------------------------

(Read Tom Forsyth's powerpoint on displacement maps+subdivision+VIPM
at www.muckyfoot.com)

Displacement maps seem great, but to get good detail, you're
really looking at rather a large amount of memory, and bad
out-of-order fetching.  For example, to do bricks on a wall
or something like that could require a 256x256 map, which is 
a no-go.  If you can get good displacement out of a 16x16 map,
then that's golden.

Tom's trick for displacement is pretty cool.  If you ignore all
the authoring and VIPM bits, what he's doing is taking a triangle,
subdividing it up by edge-splits, and storing the displacement
of those verts.  Rather than use the barycentric coords, I would
just keep all the triangles and compute their bary-coords
implicitly by location in the triangle.  Then all you store is an
8-bit displacement which is fetched from a displacement map (the
disp-map can then be discarded) and an 8-bit compressed normal.
So, this is basically just a way of compressing geometry (a pretty
damn good way at that).  I think this is a bit better than displacement
maps for the case where you are generating fewer verts than the
map has pixels.

Curved surfaces seem to be the only thing that low-memory,
small-cache consoles can do *really* well.  You could take a
NURB with 256 control points or so, and generate 64k tris and
fire them in batches (one batch per patch), all quite easily.
You could do lighting only at the control points and interpolate
it for the points in between.  You could also do phong interpolation
instead of gouraud/linear at a pretty low cost (this is like 'dot3'
or bump-mapping, but on verts).  Unfortunately, the usefullness of
curves seems very low.  All I can imagine is maybe water, cloth, hair.

Perhaps traditionally geometry compression, combined with VIPM, is
the best way to go...

-------------------------------------------------------