README for NvTriStrip v1.1
~~~~~~~~~~~~~~~~~~~~~~~

Welcome to the NvTriStrip v1.1!  This program loads meshes from disk (currently supports only .m format files), optimizes them (see below), allows you to visualize the optimization, and outputs an optimized file to disk.

NEW FEATURES:
-Allows you to specify a "minimum strip size".  All generated strips which are below this size (in triangles) will be dumped into a triangle list.  Note that if you specify 0 for this, it will behave much like the previous version of NvTriStrip.
-Allows you to specify whether or not you want the strips concatenated into one huge strip (recommended for D3D, debatable for OpenGL)
-Considerably less finicky about which .m files it can load.
-Faces which could not be stripped and were added to the face list at the end are visualized as transparent faces with an outline.
-Duplicate triangles (tris with the exact same vertices) are now removed.
-Strips which turn over on to themselves are now handled correctly.

BUG FIXES:
-Several subtle bugs in strip generation have been fixed.  If you noticed that extra triangles were being added to your output mesh, this should now be fixed.
-A couple memory leaks were fixed.
-Fixed bug where stripifying multiple times in a row without saving would cause slightly different output meshes to be generated.
-Several minor bugs were fixed.

The new features above have required a new .STRIP file format.  Here's the spec:

.STRIP File Format:
~~~~~~~~~~~~~~~~~~~
This is the file format the stripifier outputs.  It's binary, in the following format:

 Number of vertices: 4 bytes
 Vertices, x, y, z, nx, ny, nz components, each a 4-byte float
 Number of strips: 4 bytes
 For each strip:
   Number of strip indices: 4 bytes
   Indices, each a 2-byte WORD

 Number of list indices: 4 bytes
 Indices, each a 2-byte WORD

The indices index into the vertex list.

So, in general, the stripifier generates an optimized vertex list, a number of strips, and a list of left over faces.
Note that the list at the end is also optimized for the vertex cache.

Optimization:
-Generates strips, by creating the longest strips it possibly can in groups, then as a post-process splitting them up into vertex cache-friendly pieces and arranging them to maximize cache hits.
-Optimizes the arrangement of the vertices in the VB so that vertices are accessed in a linear way, minimizing memory paging issues.
-Stitches together the strips into one huge uber-strip using degenerate triangles.  
It might be a better technique to dump really small strips into a triangle list and stitch together 
only the bigger strips, but the algorithm above doesn't generate an enormous number of tiny strips, 
and cache-optimality could be sacrificed if smaller strips were batched.

Note that if you're compiling this yourself, it's a good idea to compile with full speed optimizations (release build), 
since the stripification step uses an enormous amount of CPU.

Relevant parts:
~~~~~~~~~~~~~~~

Since this is an MFC app, a bunch of the code is there just to support the interface.  These are the relevant bits:

NvStripifierObjects.cpp: 
	this file implements the stripifier (class NvStripifier), 
	specifically the function FindAllStrips().  
	The function SplitUpStripsAndOptimize() takes the strips generated by FindAllStrips() and splits them up 
	based on the cache size, and rearranges them to optimize hits in the cache.

NvStripifierDlg.cpp: 
	much of this file is interface bits, but two functions perform important functions:

	CreateStrips() -- takes the strips generated by the stripifier, 
	which are actually lists in strip order, and makes true strips out of them by removing shared vertices and ensuring CW/CCW ordering.

	OptimizeVertices() -- optimizes the order of the vertices to minimize DRAM page misses.

Note that these can (and probably should) be moved into the main stripifier class...they're included here to simplify 
	displaying of the geometry.  They are both invoked when the file is saved to disk.


Legend for Visualizing Cache Misses:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Green means zero cache misses for this face.
Yellow means one cache miss for this face.
Blue/Grey means two cache misses for this face.
Red means three cache misses for this face.

Transparent faces are faces that haven't been stripified because they generated strips that were too small.
These are added as a list at the end.

The visualization is based on the current cache size, and is not reflective of the current video card or anything like that.
For GeForce/2/MX class video cards, this value should be 16.

Credit goes to Curtis Beeson and Joe Demers for the basis for this stripifier and to Jason Regier and Jon Stone at Blizzard for providing a much cleaner version of CreateStrips().

Send comments/questions/bug reports to [email protected].


Copyright (C) 1999, 2000 NVIDIA Corporation
This file is provided without support, instruction, or implied warranty of any
kind.  NVIDIA makes no guarantee of its fitness for a particular purpose and is
not liable under any circumstances for any damages or loss whatsoever arising
from the use or inability to use this file or items derived from it.