Introduction

2.0

Computer graphics has become an important aspect of many different fields, ranging from medicine and engineering to marketing and entertainment. 3D computer graphics are created in many different ways and are used for a variety of purposes. Some 3D graphics are created with digital cameras or sonography equipment by utilizing the techniques of computer vision, while others are created by artists completely from their imagination. In medicine, 3D models of human organs are created using data collected from sonography and other medical imagery devices to aid in surgery[#!gvu!#]. In engineering, real-world objects that are yet to be created are modeled first on computers[#!nist!#]. The marketing and film industries create unique 3D models that do not exist and never will except on a computer screen[#!discreet!#].

In the field of computer graphics there is an ever-present concern for graphics professionals to give viewers the best representation of an object. Of course, the more detail a 3D model of an object has, the more information is needed to represent the object in a computer's memory, and the more time it will take the computer to process that information and create, or render, a 2D image that can be viewed. Examples of objects could be a model made from the torso of a real person (see Figure 1.1), a character in an animated movie (see Figure 1.2), or even a monster from a video game (see Figure 1.3). All of these examples were made to give the viewer the best visual appearance possible given the constraints under which the images need to be rendered.

Figure: This example is a torso of a person. This image was produced from a method from the field of medical imagery[#!pawasauskas!#].

Figure: This example is from the movie Final Fantasy: The Spirits Within. All the computer processing needed to make this movie was done before the movie was viewed, so the models were created with the highest feasible level of detail[#!ff!#].

Figure: This is a monster from the popular game Quake 2. Because the game is interactive, the computer must render 2D images from the 3D model in real time, so this model has less detail to make this possible[#!quake2!#].

3D computer graphics lends itself to a hierarchical approach. When viewing in 3D, what a computer program user is viewing is called a Scene, which defines the scope of what the user can view. A Scene is made up of one of more Models, which is a term professionals in the field use to refer to any discrete object in a Scene. Models are represented in most computer programs with Meshes of polygons, usually triangles. The more triangles that make up the surface of a mesh, the more realistic it appears to a user. A balance must be kept between realism and performance, however, because it takes the computer longer to render an image of a model that has more triangles in its mesh.

Figure: This figure shows a model of yoda on the left and a wireframe view of the same model, showing the model's mesh, on the right. The image was generated with our program. The model was retrieved from 3DCafe.com[#!3dcafe!#]

The goal of this project is to research, design, implement, and evaluate a non-trivial cross-platform program that reduces the polygon count of three-dimentional triangular meshes of all models in a scene. The program should be released to the public as an open-source program, and be easily extensible to include other mesh-altering or mesh-utilizing algorithms and to import and export various data formats. Lowering the polygonal count of meshes allows computers to render them faster, since fewer computations are needed. The method used to decrease the polygonal count is known as mesh simplification or decimation. An early article documenting a decimation algorithm was written by Schroeder, Zarge, and Lorensen in the July 1992 issue of Computer Graphics, a publication of ACM SIGGRAPH[#!shroeder!#]. This has been the basis for most of the work we have done in implementing a decimating program. Mesh simplification is defined in their paper as the problem of reducing the number of faces in a dense mesh while minimally perturbing the shape.

For our project we created an OpenGL[#!opengl!#] application that executes in Windows or Linux. The program has been released under the terms of the GNU General Public License[#!gpl!#]. The program is capable of rendering meshes in VRML or Inventor 2.x format.

.