qemLOSS2

Lightwave Object Surface Simplification
using Quadric Error Metrics

Version 2


Introduction

Downloading and Installing qemLOSS2

Using qemLOSS2 (Quick Reference)

Tutorial and Hints


Summary: This Lightwave Modeler plugin uses a surface simplification algorithm in an attempt to reduce the number of polygons in a Lightwave object. The plugin allows the user to rapidly produce good quality approximations of excessively detailed polygonal models.

This is a new version of the qemLOSS plugin, which handles multiple surface objects MUCH better than the first version. Surfaces are no longer separated into individual objects prior to the surface simplification, allowing for much better global simplification throughout the entire object.

This plugin uses routines adapted from Michael Garland's public domain QSlim Simplification Software. The algorithms used in this software are described in the papers written by Michael Garland and Paul S. Heckbert: "Surface Simplification Using Quadric Error Metrics", SIGGRAPH 97, and "Simplifying Surfaces with Color and Texture using Quadric Error Metrics", IEEE Visualization 98.



Introduction

Many 3D models contain a large number of polygons, especially algorithmically created models (such as those created by implicit surface construction techniques) and models created with 3D scanners and digitizers. Polygon reduction in these types of models is currently a very active research area in computer graphics. Obviously, rendering 3D scenes is much faster when the models contain a minimum number of polygons. Also with the current trend towards sharing 3D worlds over the internet using VRML, level of detail models (LOD) are becoming absolutely necessary for creating worlds in which the user can browse and interact in a reasonable manner.

This plugin provides polygon reduction on objects within the Lightwave Modeler environment. Only one parameter, the reduction Goal, must be set by the user, the remaining default values should provide good reduction for many objects with a high polygon count. However, to get the best results from this plugin, the user will need to understand some of the basic concepts behind the algorithm. A little terminology along with some simplified illustrations will be presented in the remainder of this introduction. These terms will be reinforced by the short examples in the Tutorial section.


Terminology

The simplification algorithm is based on contractions of vertex pairs. It supports two types of contractions: edge and non-edge contractions. An Edge contraction occurs when the vertex pair shares an edge. This is the primary type of contraction that occurs during the reduction stage (in fact, non-edge contractions are turned off by the default parameters). The following figure shows an example of an edge contraction where vertex v1, and vertex v2 are joined to form a new vertex v3. Since v1 and v2 share an edge (marked in orange), one or more triangles will always be removed during this contraction. In this example, 2 triangles are eliminated from the mesh.

Edge Contraction


Non-edge contractions allow the algorithm to join unconnected areas of the object together. The next figure shows an example of a non-edge contraction (also called aggregation).

Non-edge Contractions

In fact, there are 2 non-edge contractions taking place: v1 and v2 contract to form v5; v3 and v4 contract to form v6. Since by definition the vertices in the contraction pairs do not share an edge (there is no edge between v1 and v2, or the v3,v4 pair), there is no actual reduction in the polygon count of the object. However, since this feature joins previously unconnected areas of the object together, the potential exists for future reductions. Many times this can also provide a better low resolution approximation of an object that has many disconnected regions.

As the algorithm proceeds through each iteration, a geometric error approximation is accumulated at each vertex of the object. If this geometric error is less than the user defined maximum error threshold, the vertex is marked as a viable candidate for another contraction. Once the geometric error for a vertex becomes greater than the maximum threshold value, it will no longer be considered in any more contractions. During each iteration, the vertex pair with the smallest combined geometric error will be chosen for the current contraction.

The algorithm will proceed until the simplified object is reduced to the user's targetted Goal (number of polygons) or until all the vertex errors have become greater than the Maximum Error Threshold. These two parameters control how much reduction will take place, the remainder of the parameters control various aspects of the vertex contractions.

There are 2 types of vertices that receive special consideration by this plugin: surface border and boundary vertices. Parameters are provided for the user to weight the geometric error for these 2 special types of vertices.

This simplified 2D grid shows examples of both types of vertices. The colored triangles represent the different surfaces assigned to the object.


Red - Surface Border vertices

Green - Boundary vertices

Blue - both types


In this example, obviously there are boundary edges all along the perimeter of the grid, but notice that any hole in the grid also defines several boundary edges.

The Surface Border Weight and Boundary Preservation Weight parameters allows the user to weigh the geometric error at these points. The higher the weight, the less likely the vertex is going to be replaced. Clever use of these parameters (along with some equally clever surfacing) can provide quite a bit of control over the contraction process. The Enable Area Weighting parameter, causes every vertex's geometric error to be weighted by the area of the polygons that contain the vertex. Once again causing larger values (triangles with larger areas) to be less likely to be removed.

Surface Border Weight is a new parameter that did not exist in the first version of qemLOSS. The first version treated each surface's polygons as a completely separate object: copy the polygons for one surface into a new layer, reduce those polyons, then repeat the process for the next surface. The main drawback to the old method was that surfaces were now separated from each other, and even if two or more surfaces shared the same vertex in the original object, the vertex was duplicated in each surface group. During the reduction process, probably at least one of the cloned vertices would move, resulting in small holes that appeared along the border the two surfaces previously shared. qemLOSS2 solves this by NOT seperating connected surfaces at anytime. The main problem with this method was the inability to preserve the shape of the borders between surfaces (see the image titled "Surface border weight set to 0" in the Tutorial section below). So, to help preserve the shape of these shared borders, weighting of the surface border vertices has been added to the algorithm to help restrict movement/replacement of those vertices.

The remainder of the parameters (Pair Selection Tolerance, Vertex Placement Policy, and Preserve Mesh Quality) are discussed in either the Tutorial section or the Quick Reference section.


I have greatly simplified the description of this algorithm in an attempt to provide the Lightwave user with enough information to take advantage of some of the features found in this plugin, without boring the reader with all the very specific details. For a complete description of this algorithm and its parameters, check out the paper "Surface Simplification Using Quadric Error Metrics" by Michael Garland and Paul S. Heckbert.

If you are interested in another polygon reduction plugin, check out Decimate. It uses a completely different technique known as triangle decimation to attempt to reduce the number of polygons in an object. There are many differences between the Decimate and the qemLOSS2 algorithms, and one of them may be better suited to reducing the number of polygons in your particular object.



Downloading and Installing qemLOSS2

The qemLOSS2 plugin is currently available on the SGI and Intel platforms. Ports to other platforms are in progress, and I hope to make them available soon. The qemLOSS2 interface uses only the standard Modeler dynamic requesters, so it should run on all versions of Lightwave Modeler that supports plugins (all versions greater than Lightwave 4.5 I believe).

To install qemLOSS2, just copy the qemloss2.p file into your Lightwave Modeler plugins directory. Run the Lightwave Modeler and choose Objects->Custom->Add Plugin (LW 5.0) or Objects->Prefs->Add Plugin (LW 5.5 and 5.6). After you select the qemloss2.p plugin from the file requester, you should now find a qemLOSS2 entry in the Objects->Custom pulldown menu.



Using qemLOSS2

ALWAYS save your objects before you run qemLOSS2! This software is provided as-is, and although it is fairly stable, it will probably crash at the most critical moment. You can prevent any permanent loss of your hard work by assuring that you have saved all objects before running the plugin!

Make sure you have an object in the current foreground layer(s) of Modeller. You will also need to have at least one empty layer, because the existing object remains unchanged, and the reduced object will be placed in the first available empty layer. Choose Objects->Custom->qemLOSS2 and you will be presented with the following information requester.




Quick Reference

Here is a brief description of each parameter in the qemLOSS2 Options requester. Please refer to the Terminology section of this document if you have any questions about the highlighted words in these descriptions.


Well, that's it! If you have made it this far, qemLOSS2 is probably showing you a progress monitor while it creates the reduced object in the first available empty layer of Modeler.

Here is what is happening. First, the object in the foreground layer(s) is copied to the first available empty layer, then all its polygons are converted to triangles using Modeler's Triple function. Next all vertices and polygons are converted into the necessary data structures needed for the simplification routines, and the copied object is subsequently removed. Once the simplification routine is finished, the reduced polygon object is placed in the previously empty layer.

I am very interested in seeing how this plugin can be used. If you use it, send me some e-mail and let me know what kind of success or failure you achieved.



Tutorial and Hints

Many of the features found in qemLOSS2 can be seen by playing with the standard Lightwave Cow object (Objects/Animals/Cow.lwo). The Triceratops object in the same directory, also has many of the same types of reduction and surface problems, so if you prefer the dinosaur to the over-used bovine, please feel free to try it :-). There are 4 short sections in the following tutorial, and I don't imagine it will take you very long to run through it. But I do think it reinforces some of the terminology, and provides some helpful things to watch out for and try when you are reducing your high polygon count objects.

One other note of importance before getting started. ALWAYS save your objects before you run qemLOSS2! This is free software, and will probably crash at your most critical moment (sorry, but that's the way free software is required to work ;-). You can prevent any permanent loss by assuring that you have saved any work before running the plugin!


We'll start by comparing what makes qemLOSS2 different from the first version of qemLOSS. So, download and install the qemLOSS2 plugin, then load the Cow object into the first layer of Modeler. If you had installed the first version of qemLOSS in the past, it will still be available as well, since the plugin server names are different. Once you decide that qemLOSS2 is what qemLOSS should have been in the first place ;-), you will have to manually delete the qemLOSS entry from your Modeler config file.

Verify that the CowHide, CowUdder, and CowNose surfaces share some of the same vertices by selecting a polygon in one of those surfaces, then choosing Display->Sel Conn. The entire main body of the cow appears selected, and the selected polygon total equals the sum of the polygon counts in the 3 surfaces (Display->Statistics in Modeler's Polygon mode). If you have the first version installed, choose qemLOSS (not qemLOSS2) from the Objects->Custom menu and just accept the defaults in the requester by clicking OK.

After reducing the number of polygons in the cow with the first version of qemLOSS, the two surfaces are no longer joined and small holes have appeared where they originally shared a border. The separation between the 2 surfaces can clearly be seen in the second image below. But qemLOSS2 no longer treats each surface as a separate object, so there is no more "tearing" between surfaces. Switch back to layer 1, and now choose qemLOSS2 from the same menu. The reduced object in layer 3 The CowHide and CowUdder surfaces are still connected, just as they were in the original object!

Original object Surface separation
with qemLOSS
Problem solved
with qemLOSS2

(NOTE: currently both versions, qemLOSS and qemLOSS2, ignore any polygon selections the user has made, they will only work on the entire object in the foreground layer, including any hidden polygons. Selective polygon reduction will be in the next version.)


However, if you browse around to the front side (whew! what a way to have started a tutorial, by observing the rear end of a cow :-) of the qemLOSS2 reduced cow in layer 3, you will still find some surfaces that appear to have separated. It's not real easy to see, but the first image below shows separation between the CowEyes surface and the head, and if you look even closer there is some separation between the head and the CowHorns surface.

But it is not a surface border problem because those surfaces DID NOT share the vertices along their borders. The vertices along the edges of these surfaces in the original object are duplicated, and therefore the edges around these surfaces are not considered surface borders. You can verify this in the same way manner we did earlier, switch back to the original object in layer 1, select all the CowHorns (334 polygons) or the CowEyes (34 polygons), and then choose Display->Sel Conn. These surfaces are not connected to any others. The edges where the horns and eyes touch (but don't connect to) the head, are considered boundary edges (review the Terminology section for complete definitions and differences between "surface borders" and "boundaries").

Looks like a
surface border problem
But it's not!
It was a boundary problem

Obviously, the default value for the Boundary Preservation Weight does not restrict those boundaries enough to prevent these seams. If you want those surfaces in the original object to remain unconnected, you can try to preserve those boundaries by increasing the Boundary Preservation Weight, but I find in most cases I prefer the following technique. Make sure you are in layer 1 with the original Cow object, Unselect All of the polygons, and choose Tools->Merge->Automatic. This results in a message stating that 87 points have been eliminated, which were those duplicate points that lied along the boundary edges between the CowEyes, CowHorns, and CowHooves surfaces. This merging process has converted the boundary edges into surface borders that are shared with the CowHide surface. Confirm that all surfaces have been connected, except the CowTail object (which continues to be stubborn :-), but we'll deal with it in another manner shortly. Now run qemLOSS2 on the merged, near-seamless object. The newly reduced cow in layer 4 is shown in the second image above, and you can see the surface borders are preserved, and the separation in the first image no longer exists. If you want any of the surfaces to be disconnected again, just select all the polygons that use that surface, Cut, then Paste. Neighboring surfaces will have been reduced together, but following the cut and paste, are no longer connected.

The Boundary Preservation Weight existed in the first version of qemLOSS, and the Surface Border Weight was added in qemLOSS2. I find that I can control the edges of surface borders better than boundary edges with the weighting parameters provided (that's why it was added :-). So if at all possible, I prefer to merge as many points as possible in my original object, then separate them by surface name using the Cut and Paste technique following the reduction. A little more experimenting with the Surface Border Weight parameter is discussed in the next portion of the tutorial.


The Surface Border Weight in qemLOSS2 provides a little control over how the vertices and polygons that share surface borders will be reduced. Border vertices in the entire object can be weighted so they are less likely to be re-located very far from the original vertices, thereby preserving the shape of the surface borders. The surface borders between the CowHorns and the head in the 3 images below, show how this weighting works.

Go back to layer 1, and run the qemLOSS2 plugin again. Change the Surface Border Weight to 0, and click on OK. This should leave you in layer 5, and an overhead view of the cow's head should look like the second image below. When the surface border weight is 0, border vertices are completely free to move to the most optimum location for preserving the quality of the shape throughout the entire object, just like any other vertex in the object. But any shapes defined by the border vertices will possibly be destroyed. It's evident by looking at the rear portion of the horns in the second image below, the 0 weighted border in the second image does not preserve the shape of the border edge at all. The default weight of 100 (third image, or layer 4 if you have been following along closely :-), the border edge shape more closely matches the original.

Original object Surface border weight
set to 0
Surface border weight
set to 100

The surface border between the CowHide and the CowUdder, underneath the cow also show the effects of the weighting parameter. I'll spare everyone from more pictures of the cow's udder :-), but turn the cow over and flip back and forth between layers 4, 5, and 1. The "straight" front portion of the border between the 2 surfaces demonstrate the effects of the parameter as well.

But as most things in life, there are trade-offs. If a large number is used for the Surface Border Weight parameter, more triangles will be needed along every surface border in able to preserve the border shapes. This means that other portions of your object may suffer because so many of the triangles are being used to preserve surface borders, leaving fewer triangles for the non-border areas. So you will probably want to experiment with the weight parameters, hopefully finding a nice compromise between overall quality of the reduction process and the preservation of your border shapes.

OK, time for a quick quiz before we finish the last portion of the tutorial. The first 3 people that send me a correct answer will receive a free copy of qemLOSS3 (lwpanels interface with OpenGL preview, selective reduction, individual surface border weighting, and more) when and IF it is ever released. Of course it's still in its early stages, so it may never happen, and I may give it away to everyone else even if it does happen (and I might not ;-). You'll need to understand the description of the reduction algorithm and the terminology found in the Introduction. But I'll just be impressed if anyone reads this much of the document :-), so here is the question.

Which parameters would need to be changed from their defaults, to completely lock all surface border vertices in place, no matter how much other reduction is done on the object? Give me at least one example of parameter settings that would cause locked surface border positions.


This last portion of the tutorial will discuss the Pair Selection Tolerance parameter, which is used to control non-edge contractions. I don't like using this feature of the reduction algorithm, because it is slow and can possibly be very memory intensive. But since the parameter exists, I want to demonstrate the safest way to experiment with it. But you should take great care with your objects and save all your work before you change this parameter to something else besides its default value of 0.

Go back to layer 1 for the last time, and refresh your memory (no, not your computer's memory, your memory :-). After loading this object, we did an automatic merge on the points, and we were left with this object. All the surfaces in this object are connected to each other, except for the CowTail surface. By allowing the algorithm to perform non-edge contractions on this object, we can have vertices in the tail contract with vertices in the main body. If the tolerance parameter is chosen correctly, the reduction will result in a completely connected object.

The recommended value for the Pair Selection Tolerance parameter is 5% of the radius of the object's bounding sphere. To approximate the radius of the bounding sphere, we can run the Objects->Custom->LW_BoundingBox plugin and choose the largest number on the "Extent:" line. For my cow, that is 2.618 which is the Z-length of the object. Half of this value approximates the radius of the sphere, and mutiplying that by 5% results in:

2.618 * .5 * .05 = .06545

This is the value we'll use for the tolerance parameter. Now that we've calculated that I will tell you there is a shortcut that allows you to let the computer do the calculation. If you enter a -1 for this parameter, qemLOSS2 will calculate this recommended value for you automatically. But currently it doesn't show you the result of the calculation, so if you want to experiment with other values in the same range, you need to know how to calculate it yourself.

Run the qemLOSS2 plugin, and enter either .06545 or -1 for the Pair Selection Tolerance parameter. The resulting object will now have all its surfaces connected, because vertices from the CowTail surface have been connected to vertices of other surfaces using non-edge contractions. However, as you may have guessed by now, this feature doesn't work as perfectly as we would have liked. In a perfect reduction, the CowTail would have only been joined to the tail portion of the main body. But since the CowTail surface is close to (and sometimes overlaps) the CowHide and CowUdder surfaces, some of those polyons are joined as well. Select the CowTail polygons, and move them around a little to verify that this cow is going have real problems swatting flies with its tail :-).

This Pair Selection Tolerance technique could have been used on the original object as well (before automatically merging the points), and all the boundary edge vertices would have been joined without the need to automatically merge the points. You can try this by re-loading the original model from Objects/Animals/Cow.lwo, and running qemLOSS2 with the Pair Selection Tolerance set to -1. I like to compare reductions like this to the ones done earlier, by displaying one in the foreground layer, and another in the background layer.

But I want to stress again, I recommend using the Pair Selection Tolerance as little as possible. I strongly recommend leaving it at 0 for all complex, very high polygon count models. If you must use this, reduce the model to a fairly small polygon count with it turned off (=0), then reduce it again with a carefully chosen value, or preferably a negative number. It is a very memory intensive operation, and will probably crash or freeze your computer if you insist on playing with it. You have been warned!!


This concludes the Tutorial section of this document, and I hope you understand enough about the main parameters to achieve satisfactory reduction results. The Quick Reference section of this document can be referred to for a quick reminder about the various parameters. There are a couple of parameters that were not covered in this tutorial, and information about those parameters can be found there as well.

Hints from users

Here are some hints and tips from users of qemLOSS and qemLOSS2. If you have had some success using these polygon reduction plugins in a project, and would like to share your own ideas, please send me the tip or hint, and I will be glad to add it to this list. The reason I make these plugins available for free, is to receive feedback from the users, so any thoughts you might have are definitely welcome!



Last Modification Date: August 05, 2001
marvinl@amber.rc.arizona.edu