Analyzing Geometric Error

Metro: Measuring Error on Simplified Surfaces

P. Cignoni, C. Rocchhini, and R. Scopigno[#!metro!#]

Metro is a tool that compares two levels of detail of a mesh by calculating the volume between the two meshes. The need for this tool is stated by the authors: "The field of surface simplification still lacks a formal and universally acknowledged definition of error." The paper gives an overview of the reasoning behind this tool, and it details the ideas employed to create this tool.

Metro is a necessity for authors of simplification algorithms. The ultimate reason for proclaiming this tool a necessity is that it produces visual and numerical output that describes comprehensible differences between an original and simplified mesh. Metro compares the output from a simplification program to the original mesh, not taking into account the type of algorithm the program uses. Thus, the use of the Metro tool can help to eliminate bias about which simplification method was used[#!lindstrom!#].

Metro uses approximate distance to evaluate the difference between two meshes, which is defined as

where is a point on the mesh, is the surface of the mesh, and is the distance between two points. To find the approximate distance, Metro takes a user-specified sampling step, which produces a number of sample points on the surface of the original mesh which are either uniformly using scan conversion of the triangular faces, or randomly distributed among the surface to produce a mean result with Monte Carlo integration, at the user's option (yielding similar results in most cases). These points are used to get a precise approximation of the original mesh surface. The approximate distance is the distance from one of these sampled points to the closest face on the simplified mesh. This distance is minimal in respect to the original mesh.

The program outputs two values. The first value is the maximum distance which is defined a

the maximum value out of all the calculated distances between each point and the approximated surface. The second value is the mean distance, which is defined as the surface integral of the distance divided by the area of the original surface:

Metro also uses the approximate distance to calculate several important characteristics of a mesh that numerically show differences in a simplified meshes topology, its handling of boundaries by comparing boundary edge totals between the two meshes, and total volume between the two meshes.

Evaluation of Memoryless Simplification

Peter Lindstrom and Greg Turk, Georgia Institute of Technology, Atlanta[#!evaluation!#]

This paper compares the results of the memoryless simplification algorithm developed by its authors in [#!lindstrom!#] with five other simplification methods that retain geometric history. Memoryless simplification makes no comparisons between the partially simplified model and the original model while simplification is ensuing. The authors have demonstrated that geometric history (the original model) need not be retained in memory to deliver good approximations (a philosophy we adopted in our algorithm). The advantages over the more complicated approaches are smaller memory requirements and (generally) faster simplification.

To compare the results of their algorithm to the algorithms of their peers, they adopted to use the Metro[#!metro!#] tool and public-domain implementations of the other algorithms (rather than writing their own implementations). They hoped to remove some bias by using tools and programs they did not write, so that the evaluation tool was written by authors who are not counted in the evaluation, and the other programs have been (hopefully) optimized by their authors better than the memoryless simplification authors would. Also, they point out that by using a tool in the public domain, others can compare their own programs to these results.

In their comparison, they created eight levels of detail of four models with each of the six programs. Two models were completely closed (a horse model and a sphere), and two contained boundaries (the Stanford bunny and a portion of the sphere). Next, they ran the Metro program to compare the original model to each level of detail for each of the four models, for each of the six programs. Finally, they compared the results of this Metro evaluation using line graphs with a logarithmic scale along the widely-varying errors. We ran the Metro program on the bunny model for eight levels of detail using our own program (see the Results chapter) and borrowed the data from this reviewed paper for use in our own evaluation (see the Analysis chapter).

.