|
Download program with PLY meshes and source code here. If you just want the executable, get it here. Some sample PLY models: cow, cat, apple, helicopter, car, huge bunny. These PLY models and many others can be found here: This program implements four different mesh simplification algorithms. After loading a mesh, the user can easily remove triangles from the mesh and the results are displayed in real time. The mesh can also be rotated and moved closer to or farther away from the viewer. The goal of mesh simplification is to display a 3D polygonal mesh with fewer triangles while retaining the same shape. In the example above, the original cow model (upper left) is made up of over 5800 triangles. We can easily remove thousands of triangles from this mesh and still display a very similar cow model. While the 500 triangle cow is a cruder representation, this may not make a difference if the cow is far away from the viewer: Far away cow with 5804 triangles:
Far away cow with 500 triangles:
Why is mesh simplification useful? In a game, you may want to display a herd of killer cows, but you find that showing hundreds of cows, each with thousands of triangles, may take too long to display. Displaying so many triangles at once can result in a game which looks more like a slide show than a fast-paced action game. Therefore, what you want is an automated way to take high-quality
models, and remove triangles from them without rendering the models unrecognizable.
When the mesh has been simplified, you will be able display your herd of
cows and not slow the computer to a crawl. Mesh Simplification Viewer Usage Open a mesh using the Open command on the File Menu. Algorithms In this program, triangles are removed via edge collapses. An edge collapse always collapses one vertex to another vertex on the same edge. No new vertices are created. This program implements Garland
& Heckbert's simplification algorithm. Two versions of the Quadrics algorithm are implemented: a version
weighted by the area of the triangles in the mesh and a version where the
triangle areas are not taken into account. This program also implements Stan Melax's Polygon Reduction algorithm. (A Simple, Fast, and Effective Polygon Reduction Algorithm, November 98 Game Developer Magazine) The final mesh simplification algorithm implemented is shortest edge first. The shortest edges within the mesh are the first ones to be removed. This is not a particularly good algorithm. It's just here for comparison's sake. Some of the OpenGL code is based on Jeff Molofee's OpenGL tutorials. For more information Mesh Simplification algorithms, as implemented here, are also known as Level of Detail (LOD) or View Independent Progressive Mesh (VIPM) algorithms. (It's "view independent" because the point-of-view is irrelevant to how the mesh is simplified. Some mesh simplification algorithms take the viewer's location into account, and simplify the features farther away from the viewer before simplifying the features closer to the viewer). Academic Researchers Michael
Garland, University of Illinois at Urbana-Champaign Game Programmers Charles Bloom has articles on VIPM. He's a lead programmer at Oddworld Inhabitants (developer of Munch's Oddysee for the X-Box). Jan Svarovsky has worked for both Muckyfoot and Lost Toys, which are British game companies founded by ex-Bullfrog folk. His article on Extreme Detail Graphics describes how progressive meshes and other level of detail techniques can be used in a game engine. Tom Forsyth works for Muckyfoot. He has slides on his site from his talk on Subdivision surfaces, bumpmaps, displacement maps, and VIPM. Additional VIPM papers can be found here. Both Svarovsky and Forsyth have written articles on mesh simplification
in Game Programming
Gems and Game Programming
Gems II. return to my programming demos page.
|
