Implementation

Standards

OpenGL[#!opengl!#,#!opengl_book!#]

We chose OpenGL for its wide availability and support. As the name implies, it is an open standard that is amended by a board of leading graphics industry professionals. We chose it partially because of the easy learning curve and because it is what the WPI graphics course used. We also partially chose it since any graphics hardware can run the program if the operating system supports the standard set of OpenGL calls. In this case the operating system calls the software implementation rather than passing it to the hardware. This method is slower and can result in poor performance, but most newer graphics cards have at least full OpenGL 1.1 compliance. We also chose it because we wanted it to run in Linux and did not want to write our own graphics functions.

OpenGL Utility Toolkit (GLUT)[#!opengl!#,#!glut!#]

The OpenGL Utility Toolkit (GLUT) is a standard that is used most often in educational settings or for prototyping, due to its very small list of features (no graphical user interface "widgets" like buttons, file menus, or dialog boxes) and relative slowness (direct window manager routine calls are faster than translation from GLUT calls at run time). For these reasons, it is not often used in industry. However, there are compelling reasons to use it in research. Programs written using GLUT have the ability to run on many different platforms without modification. The most important aspect of cross-platform design is that there is no dependency on a platform-specific toolkit like Windows's Microsoft Foundation Classes, the Gimp Tool Kit (used in GNOME-based window managers), the QT libraries (used in the KDE window manager), or any other graphical toolkit library. Also, GLUT allows for very rapid development of a user interface for OpenGL programs. GLUT is limited in that it recently dropped support for dialog boxes. This means that the functions for opening and saving VRML files under a file name that was input in the user interface are not supported in our program.

The limitations of GLUT are apparent in our GUI design. The lack of dialog boxes and text boxes in GLUT prevents our GUI design from having the option to decimate to a certain number of vertices. This is only caused by our own desires to make this program cross-platform. If we designed our interface for a specific platform, we could avoid this problem, but our program would not be immediately available to those who don't have specific platforms or compilers, such as those who use a Microsoft Windows[#!windows!#] based Operating System.

C++ and the Standard Template Library[#!cpp_stl!#]

We were determined to use the most compatible standards. In using C++ and the Standard Template Library (STL) we were able to port the code to Windows Visual C++ 6.0 with an addition of minimal code. This allowed the code to be used on virtually any configuration, with some given facts. The code should compile and run on any computer with a compiler implementation that conforms to the latest ISO C++ standard, has OpenGL and GLUT support, and contains a good STL implementation. OpenGL and GLUT have been included with many commercial systems.

VRML and Open Inventor[#!vrml!#]

Virtual Reality Markup Language (VRML) is a standard for highly portable modeling programs. It has been used for many web applications, and has been proven a successful standard. It also has the benefit of being in text format, so anyone with the desire to change, or read the model file can do so with ease. This standard has been heavily documented and is used in many professional modeling packages. Open Inventor is a format that evolved from VRML to meet more general purpose demands. It can handle much more modeling detail, such as environment mapping and bump mapping, and can be used in a compressed format that saves disk space and memory. We chose to support VRML 1.0 and 2.0 and the ASCII version of the Open Inventor standard (which is fundamentally similar to VRML 2.0) for input files because of the wide availability of good test data for our algorithm and the ease of development and human readable and editable data in case we wanted to "tweak" the models for our purposes in debugging the program.

Target Platforms

Linux

We chose to use the Linux[#!linux!#] operating system as our main development platform for many reasons. It is robust in development features such as version control with Revision Control System (RCS) and its front end Concurrent Versioning System (CVS). It runs on hardware that is available for our use, and it offers full memory protection, unlike Microsoft Windows 98[#!windows!#] and previous versions. It is more stable than other operating systems we tried while programs are under development. We are also familiar with its development features and debugging programs. Other benefits of using Linux as the main development platform is its ease of porting to other operating systems. Since we used open standards, free development environments that use the same tools we use (Makefiles, cvs, gcc and g++) are available for many operating systems, including the GNU tools for other Unix variants and Microsoft Windows through the Cygwin application[#!cygwin!#]. Linux and its GNU tools (including full-featured development programs, compilers, and debuggers) are also free - a major benefit. They are not only free in price, however; since the source code is available for Linux and all GNU tools, the user can be assured that the programs perform exactly as promised by the programs' authors, and they are extended further freedoms because of this. If anything does not work to the users' satisfaction, any of the programs can be altered directly. Finally, if the user wishes to understand more about how the implementations of the open standards they use work (such as STL containers), the source code for the implementations can be consulted directly to seek discrepancies or ambiguities in the standards' descriptions (such as whether those containers store references to or copies of the data passed into them).

Microsoft Windows

Microsoft Windows[#!windows!#] is the most often used platform for desktop and workstation computers. By ensuring that our program compiles and runs at full speed on this platform, we ensure that we can reach a larger audience than by only supporting Unix variants. We made sure that the source code for our program compiles in both Microsoft Visual C++ 6.0 and with Cygwin[#!cygwin!#] (an emulated Linux build environment which creates Win32 binaries) with the proper libraries installed (OpenGL[#!opengl!#] and its utilities, and a better STL than Visual C++ supplies).

Code Organization

We intended to organize the code in a logical manner. The classes we created have been structured as unique and individual entities. First we created the simple data structure classes: Color, Normal, Point, Vector, Vertex, and Light. These classes are simple in that they correlate directly to a simple graphical structure. These classes are also the most generic in that they can be reused in other applications. A possible application, like a graphing calculator, could use any one of those classes. Next we created the more complex data structure classes: Triangle, Model, Scene, Viewport and ViewportController. These classes are more specific to the task of our program (mesh decimation), but have the ability to be used in an application where similar concepts are needed, such as a rendering engine for an interactive entertainment application. Note that these classes are dependent on the implementation of the simple data structures. Finally, we created the single program code block 'main'. This code determines the function of the program as a whole; setting up instances of the VRML parser, setting up the user interface, and handing off control of that interface to GLUT.

Code Walk

Initialization

This decimation program is fairly complex, but it can be seen as a set of logical steps. This section is useful for anyone who has an interest in a more in-depth explanation than what has been previously been offered in this paper.

There are six main steps that occur when the program starts. The first step is the parameter check. Here, the program determines what it has been passed from the command line. There are several options that a user could specify through the command line. The term given to what parameters are acceptable for the program is "usage." The usage of our program is as follows:

.

2.0

The user must specify the filename that contains the VRML or Open Inventor ASCII code. This will launch the program in GUI mode using GLUT with interactive controls. If the user specifies to run in NoGUI mode, the program will decimate the model under the constraints given on the command line and output to a file, which can be given on the command line.

The second step in the process is to parse the VRML or Open Inventor file. Before the parsing takes place, we must first find the file, or at least see if it exists. Given that the file exists and follows one of the standards, the parsing process is simple and direct. The most important information in the file is the vertices and triangles. Any other information absent in the file is unimportant and is calculated by our program, with a set of defaults. For instance, if no vertex ordering is specified we assume counter-clockwise, or if no normals are given the program will calculate them in the next step.

The third step in the process is the creation of the model. When reading the input file, the previous step fills in temporary data structures that are used in this step. In this step anything missing in the file, such as vertex normals or colors, are calculated or given default values, so there is at least the minimal set of data for the model. In this process of "filling in the blanks," the data structures found in the Model class are created.

The fourth and fifth steps are simple but need to be done in order for GLUT to work. The fourth step is the creation of the user menus. The menus are the command interface for the user in GUI (interactive) mode. GLUT provides several functions to enable these menus directly. To create a menu, a programmer calls a combination of glutAddMenuEntry(), glutAddSubMenu(), and finally a call to glutAttachMenu(). The first two functions define the structure of the menu, while the last "attaches" the menu to a mouse button. For instance, if you made the call glutAttachMenu(RIGHT-BUTTON) the menu would pop-up when the right mouse button was clicked in the program window. This is what our program does.

The fifth step is the registering of callback functions. A callback function is a function that allows an external library, in this case GLUT, to link to functions in this program, so the library can control event handling. To use them you create a function with a special purpose, for instance rendering to the display. After creating this function you need to register it with GLUT to tell it that you have created a function for the specific purpose of rendering. The GLUT function that you call is glutDisplayFunc(myRenderFunction). There are several types of callback functions that GLUT provides. Some examples are: glutReshapeFunc() for when the program window is resized, glutKeyboardFunc() for when the user presses a keyboard button, and glutMouseFunc() for handling mouse events.

The sixth and last step is the most important when using GLUT. Without this step event handling would not occur. Simply put, this step gives the control to GLUT. This is accomplished by calling glutMainLoop. In our program we handle several events. Since our program can be controlled through the menu or keyboard, we have mouse and keyboard events. There are two not-so-obvious events that also need to be defined. They are the events for rendering. They are used in two different events. The first event is obvious: the graphics need to be displayed whenever the model is updated or moved, or when the window needs to be redrawn because, for instance, another window was dragged over it and off again. For this reason, GLUT has a callback for a display event. The other display-related event is the idle display event. The idle event occurs when no action is being performed in the program. Since our program does not animate of its own accord, only when a user is interacting with it or the same window needs to be redrawn, we do not need to handle this event in our program.

Event Handling

When the program runs in the default mode (GUI), control of the program is passed Now we will discuss haw we handle events, such as requests from the window manager to redraw the contents of the window, or user actions such as the choosing a menu option from the menus we set up. In the last section, we registered callback functions with GLUT. GLUT handles the operating system events and translates them into a common event system that works on any operating system. When a user performs an action such as pressing a key, GLUT calls the function we passed to it and passes parameters that help us handle the event, such as which key was pressed or how far the user dragged the model with the mouse cursor.

When the program starts, usage information is displayed on the console. We will not discuss the details of these callback functions here. They are described in the programmers' reference manual included in the source distribution and on the project homepage (see Deployment).

Decimation

The purpose of this project is to reduce the complexity of triangular meshes. We accomplish this by implementing a decimation algorithm that was described in the paper "Decimation of Polygon Meshes" by William Schroeder and his colleagues in 1992[#!shroeder!#]. In this section, we describe how our implementation of the algorithm works and why we made the choices we did.

First, the program receives instructions to decimate the scene in memory. This can be accomplished from the command line or from a GLUT callback from the menu. The user chooses to decimate either an exact number of vertices or a percentage of the original amount of vertices. If a percentage is chosen, we calculate immediately what exact number to remove to make our decimation loops execute identically in either case. When the program receives the message to begin decimation, it calls the decimateEvent function in ViewportController, passing it a number and a type of decimation, either PERCENTAGE or NUMBER. decimateEvent in turn calls the decimate function of the appropriate viewport (the one the event came from, currentViewport, since there may be more than one viewport open in the same window for visual comparison, for example).

The decimate function in Viewport creates an instance of the Decimate class and calculates the maximum number of vertices that it should remove, using a helper function in Viewport called getMax. getMax takes the number and type passed to the decimate function and returns a number of vertices to remove, making sure it does not exceed the number of valid candidate vertices (corners are invalid, and the four vertices with the highest distance-to-average-plane values are invalid, for example) to ensure that we are left with valid Models in the Scene when the decimation is complete. The decimate function then calls the remove function in the new Decimate object, passing it the Scene and the number of vertices to remove. We chose to create instances of the Decimate class rather than using static functions in the class in order to take advantage of memory cleanup when the object loses scope. We chose to calculate the maximum vertices here in order to keep the remove function in Decimate slim.

The remove function in Decimate contains a large loop exits on the condition that it has removed or failed to remove the number of vertices that it was told to remove. This loop starts by finding the vertex with the smallest d value. It does this by stepping through the Vertex set in Scene, looking for the smallest distance-to-average-plane. We must do this manually because every implementation of STL we use does not sort sets, which it should by the STL standard. If sets worked properly, we would simply remove from the front of the set. Next, the remove function calls the helper function removeVertex, passing it the Model that contains the Vertex and the Vertex itself. removeVertex (which we will describe later) tries to remove the Vertex and notifies the remove function of success or failure. The last thing the remove function does is check the number of vertices in the Model it removed the Vertex from. If it has less than four, the Model, and all its Vertex members, are removed from the Scene.

The removeVertex function first checks the number of neighboring vertices the Vertex has. If it only has one to three, removeVertex removes them from the Model and Scene and removes the Triangles that are involved. No hole results in this removal, so no retriangulation needs to be done. If there are at least three neighbors, it does not remove the Vertex. Instead, it immediately tries to retriangulate the hole that would result if the Vertex were removed. It does this using a replacement algorithm, replacing all occurrences of the removal candidate Vertex in the involved Triangles with one of its neighbors, called the head. It tries each neighbor as the new head and detects errors, such as overlapping triangles, that would result, and chooses a head that yields a good result. If it finds a good head, it removes the Vertex, performs the retriangulation, and returns control to the remove function, indicating that the removal was successful. Otherwise, it immediately returns control indicating failure.

A Vertex is removed by a call to the Model class's removeVertex function, passing the Vertex to remove. This function actually deletes the instance of the Vertex class in memory. When Decimate's removeVertex function removes a Triangle, it deletes it from memory immediately. When the retriangulation is performed, each neighbor is notified via a call to its removeNeighbor function, which Decimate's remove function passes the removal candidate Vertex to before the Vertex is removed. At the end of the removeNeighbor function, each neighbor recalculates its distance-to-average-plane value, thus ensuring that Decimate's remove function always chooses the Vertex with the smallest distance value, since the value may change when one of its neighbors is no longer considered in the calculation.

Output and Wrap-Up

The decimation program has two possible forms of output. The first form is a VRML V2.0 file of the Scene in memory (for the current Viewport if the program is running in GUI mode). This is either done on the command line in NoGUI mode with the -o <filename> argument, or by pressing the F3 key in GUI mode, which saves the file as out.wrl (we cannot gather a filename at runtime in GUI mode since GLUT does not support input text boxes in the most recent version). The resulting VRML files can be compared using a geometric error measuring utility such as Metro[#!metro!#]. The other form of output is the picture on screen of the Scenes in the Viewports themselves, when the program is running in GUI mode. The use of a screen capture utility can yield results for subjective, visual comparison.