readme.txt

国外游戏开发者杂志2003年第七期配套代码

Okay, here we are with the last installment of this series
(for now!), "unified_lod_5".  This code demonstrates the
LOD system running on a 3D mesh of arbitrary topology.


Sample Data and Caveats
-----------------------

My goal was to try out the algorithm on real-world game
data, so I used a Quake 3: Team Arena map as the data.
There is a problem with this, though.  It turns out that 
Quake 3 maps tend not to be very LOD'able due to the
way they are composed and textured.  [Just look at one
of the staircases to see what I mean.]  (Quake 3 does 
have a native form of LOD, but that has to do with tessellation
of curved surfaces, and does not extend to handling an
entire map, including floors, ornaments, etc).  This
inappropriateness of the source data was unfortunate,
but I discovered it too late in the project and had to
go with what was available.  

The input geometry just doesn't want to go below 
a certain level of detail.  Since the code forces it 
below that level, some breakdowns in visual quality 
occur.  Mainly, the texture mapping gets screwy, as 
the LOD system becomes unable to combine vertices 
without disrupting the uv parameterization.  The resulting
scene quality is definitely lower than I had hoped
to produce in this demo.  Sometime in the future I
hope to do a version with better source data (or with
more powerful means of massaging the source data).


The Quake 3 map included here is hal9000_b_ta.bsp, 
"An Iteration of TA Hell", by John "Hal9000" Schuch,
[e-mail].
The original textures have been substituted, to minimize
the amount of data appropriated from Quake 3.  The result
is that the rendered map will be textured in a somewhat
goofy way.  As an alternative, I could have taken out the
textures altogether, and let the map be a bunch of 
untextured surfaces.  However, I feel the textures are
a large part of what makes this useful, real-world
data; removing them would make the problem of LODing the
level a lot simpler, and also less relevant to work that
people are doing.  

On cards with 16-bit z-buffers, you will see
z-figting as you move far away from the level.  Much of this
isn't due to the alpha blending, but just because some
surfaces in the level are very close together.  The z-fighting
is exacerbated by the newly-clashing texture maps.  Also,
the occasional screwy texture parameterization makes the
alpha-blending-related z-fighting much more obvious; that
is really a source data problem, not an alpha blending problem.

You will also notice, from a distance, that there are some
lone triangles around the outside of the level that look
wrong.  If you approach these, you will find that they actually
exist in the highest detail level.  Either they were
erroneously generated by the quake3-map-loading code I
borrowed, or else quake3 actually instantiates these itself
(they are all outside the level, facing outward, so you 
would not actually see them during gameplay).

Given the nature of the data set and the parameters I set
when building the LODs, you'll often get results wherein
the number of triangles being drawn on the screen is
about 1/2 the total triangle count.  From a modern detail
reduction system in a high-detail environment, we would
expect to do much better than this.  The current LOD
ratio is mainly due to the nature of the source data,
and the lack of texture reparameterization (as explained
in the "Future Work" section of these notes).

As a result of all these factors, this is not a
dazzling demo that one would use to evangelize the concept
of soup chunked LOD.  Rather, it serves as verification
that the basic concept works: you can take something
like a Quake 3 level, and you can chop it up into pieces,
and hey look, you can hit this key to push the pieces
apart and verify that the seams between them are all
intact; and you can render a scene using pieces at
a mixture of resolutions, using static meshes and vertex
buffers.


Running the Code
----------------
As before, there are two executables, "preprocess_world.exe"
and "unified_lod_5.exe".  You run "preprocess_world" on
a quake3 bsp, and it generates an output file with the
extension ".world_lod".  You then run "unified_lod_5"
on this .world_lod file.

To keep the size of the download small, I did not include
the preprocessed version of the map.  So you will definitely
need to generate it with "preprocess_world" before you can
see anything.

The preprocessor is hardcoded to load the appropriate quake3
map file.  You can easily change this.  But I wanted to make 
it clear that this code is meant to be an example, and is not 
meant to be a general-use tool.  One good way to do that is to
make it not appear to be a general-use tool (in terms of
being able to run it on whatever files).

All the keyboard commands are documented on-screen.

There's an extra program provided, "figure1.exe", which
draws Figure 1 from the article.  The code provides
a stripped-down example of measuring the mass distribution
of some geometry, then splitting the geometry based on
that distribution.  (This technique is also used in the
full program, but in 3D instead of 2D, which makes it
a little more involved).


Code Notes
----------
I finally got around to using the OpenGL ARB_vertex_buffer_object
extension.  Because OpenGL has been riding the short bus
for a while, vertex buffers only became standardized in
February 2003.  As a result, you may need relatively new
graphics drivers to use vertex buffers.  If the code is
unable to initialize the vertex buffer extension, it will
fall back to using glVertex() 3 times per triangle.  This
of course means rendering will happen more slowly, and
a corresponding warning will be drawn on the screen.

The way I output vertex normals may confuse some people.
You'll see that I don't store a surface normal at every
vertex in the mesh data structure; instead, I store a
tangent frame, represented as a quaternion.  This
quaternion contains all the information you need to 
compute the normal, tangent, and binormal vectors. 
I use quaternions because they are small, they are nice
to interpolate, and they can be used directly in high-end
shaders to produce anisotropic lighting effects.  For
now though, because we're only doing DX8-level stuff,
I extract the vertex normal manually, by rotating the
Z-axis (0, 0, 1) by the quaternion.  I talk
about the math behind all this in my Game Developer article
"Inverse Kinematics with Joint Limits" [basically, write
out the algebra for (q)z(q*) and simplify]. 

When I build the vertex buffers, I allocate an array
of normals on the mesh, as mesh->normals.  These normals
are basically redundant with the tangent frames, and in
a real application you wouldn't want to store both.
Since this is a demo, and it was convenient, I let the
redundancy go.

I originally wrote this code in my personal game engine.
To port this into an OpenGL-based open source app,
I extracted some of my game engine source, simplified it
some, and put it in the subdirectories 'framework'
and 'mesh'.  'framework' is basically all supporting code 
that doesn't have much to do with the basic algorithm.  
'mesh' is supporting code that *does* have to do with the
basic algorithm (for example, it contains the mesh
simplification code).


Future Work
-----------
I will be using this system in a game I'm working on.
Thus, I will be improving the system.  At some point
I will make public an improved version, hopefully with
some more-appropriate source data.  I am interested
in contacting developers who have a lot of map data,
and who would like to see the results of LOD experiments
on that data. 

Certainly, data can be authored in ways that are more conducive
to LOD, or less conducive.  But eventually, we always reach
a point where we start messing up the texture parametizations,
as happens here in the quake3 example.  There does exist
a solution to this problem: combine the texture maps for
all the geometry in the block into a new texture.  To build
this new texture, you can generate a parametization using
a technique like Least Squares Conformal Mapping, then
resample the old textures into the new parameterization.
This solves a number of problems; for example, the number of 
rendering context switches for distant blocks of geometry, 
due to material swaps, is significantly reduced. This would
be a good subject for a future series of articles, and I
may follow up on that.

    Jonathan Blow ([e-mail])
    July 13, 2003 (I have been a slacker!)
    Flight Path Cafe and Mojo's Coffee House, Austin, Texas, USA