P OLY M E C O — A Polygonal Mesh Comparison Tool Samuel Silva, Joaquim Madeira, Beatriz Sousa Santos IEETA – UA, IEETA/DET – UA, IEETA/DET – UA
[email protected],
[email protected],
[email protected]
Abstract Polygonal meshes are used in many areas to model different objects and structures. Depending on their applications, they sometimes have to be processed to, for instance, reduce their complexity (simplification). This mesh processing introduces error, whose evaluation is important when choosing the kind of processing that is to be done for a particular application. Although some mesh comparison tools are described in the literature, little attention has been given to the way results are presented. A tool is presented which enhances the way users perform mesh analysis and comparison, by providing an environment where several visualization options are available and can be used in a coordinated way.
1. Introduction In data visualization, as scientists are able to generate ever increasing data sets, it becomes necessary to somehow reduce data complexity [8]. In many applications, mesh processing is necessary to allow, for example, smoother surfaces or less complex models that can be easily manipulated, transmitted or stored in devices such as a PDA. But this kind of processing introduces differences (errors), between the original and the processed mesh, whose impact on the quality of the information provided has to be clearly understood. This is crucial in, for example, scientific visualization. Besides computing the associated error values, it is also important to depict how they are distributed across the surface of a processed model. So, visualization techniques can be used in order to enhance the way this information is provided. There are several software packages [1, 3, 6, 9] that allow the comparison of polygonal meshes, providing numerical data (minimum, maximum and mean error, variance; Hausdorff distance) and representing error distribution by coloring a model according to the amount of error present at each vertex. In [9] attention is also paid to how error information can be viewed and some visualization alternatives are proposed.
The Polygonal Mesh Comparison Tool, P OLY M E C O, has the following innovative features: 1. Integrated environment where several models and comparison results (e.g., error distributions) are handled simultaneously. 2. Comparison of results using: a) colored models with the possibility of using a common color scale; b) statistical data representations as boxplots. 3. Color scale adjustment in order to encompass a specific range of values (e.g., rejecting outliers). 4. Probe tool to obtain the error (or another feature) value associated with mesh vertices or faces. We start by describing the software’s architecture, the available figures of merit and representations. The visualization and interaction options available are then presented. Finally, some conclusions and ideas for further work are mentioned.
2. P OLY M E C O P OLY M E C O is a tool developed using C++ and the Fox Toolkit to allow polygonal mesh analysis and comparison. The process of analysing and comparing meshes can be described by the pipeline presented in figure 1. Starting from mesh models, some of their features are described by figures of merit. Then the figures of merit are mapped to a suitable representation. After this mapping has been made, the chosen representations are rendered. The user may change parameters along the pipeline in order to, for example, choose another figure of merit, or the representation mapping used. Having this in mind, P OLY M E C O has three main modules: 1. Figures of Merit (FOMs) – supports the calculation of several figures of merit, i.e., several ways of measuring and/or comparing mesh properties. 2. Representation – provides ways of representing the computed figures of merit. 3. Presentation and Interaction – allows viewing and interacting with the several representations available.
Figure 1. Mesh analysis/comparison pipeline
Figure 2. P OLY M E C O’s interface With P OLY M E C O it is possible to handle several models and results simultaneously. To illustrate this feature lets consider the following example: we want to compare several simplified versions of a model with their original version. First, we load the original model. Then, we load all the simplified models, associating them with the original model, i.e., they will all be compared with it. Finally, we can compute several FOMs on the simplified models and the results will appear associated with them. A tree list (figure 3a) is available that allows the user to navigate along models and results. If we want to compute the same type of FOM for all the simplified models, P OLY M E C O provides a way of doing this with just one operation. On the following sections the FOMs, representations, visualization and interaction options available in PolyMeCo will be described.
3. Figures of Merit
PolyMeCo provides two types of figures of merit: intrinsic properties and difference (error) measures. While intrinsic properties are directly computed from a mesh, difference measures can only be obtained by comparing two meshes. In many situations, difference measures are computed by comparing intrinsic properties between meshes.
3.1. Intrinsic Properties The following intrinsic properties are available in P OLYM E C O: Triangle Quality – Triangle quality is analysed by measuring the minimum angle value (between 0 and 60 degrees) for each triangle that composes the mesh. We believe this measure can give a good general idea about the shape of the triangles. If the minimum angle is close to 60 degrees a triangle is close to equilateral. When the minimum angle is small, it is not possible, only by its value, to know if it belongs to a flat or needle triangle. In these cases a more elaborate analysis can be done using the metrics analysed in [5]. Mesh Curvature – P OLY M E C O allows the calculation of Gaussian and mean curvatures. Curvature is a good analysis metric, as it is related to the shape of a mesh. Some methods have been proposed to allow the curvature calculation on a polygonal mesh [4, 7, 9]. The curvature is approximated by calculating curvature values at the vertices. The method in [9] seems to provide a good “curvature impression” when the model is colored according to the curvature values found, but, unfortunately, it did not seem to provide curvature values close to the theoretical ones. This characteristic led to the implementation of the method described in [4], which provided accurate curvature values.
(a)
(b)
Figure 3. Interface details: (a) tree list where the loaded models and FOM results can be selected; (b) numerical data shown regarding model data and results obtained with a particular FOM.
3.2. Difference Measures
numerical descriptors. The following numerical values are available:
Difference measures are obtained by comparing properties of two meshes. Usually one of them is considered the reference and the other is a processed version of it. Geometric Deviation – This FOM allows the comparison of two meshes by measuring local geometric differences between their surfaces. When comparing meshes with different number of vertices (e.g., due to a simplification), it is necessary to somehow sample the surface of the processed mesh to allow common points of comparison. This kind of sampling process is already implemented in MeshDev [6]. For this reason, the version of this test available in P OLYM E C O is largely based on the one provided in MeshDev. Normal Deviation – This FOM allows measuring how much the normals to the vertices change from one model to another. The implementation of this FOM is also largely based on the one provided in MeshDev, due to the reasons stated above. Curvature Deviation – This FOM allows the comparison of mean and Gaussian curvature between two meshes.
Mesh Features – To characterize each mesh, the number of vertices, number of faces, surface area and bounding box diagonal (figure 3b) are presented.
4. Representations There are several ways of representing data sets for analysis. P OLY M E C O supports three kinds of representation: 1. Numerical values 2. 3D model 3. Statistical representations The representations available are described next.
4.1. Numerical Values One way of presenting the information regarding the meshes or the computed FOMs is simply by showing some
FOM Features – Regarding the chosen FOM, its minimum, mean, maximum and variance values (figure 3b) are presented.
4.2. 3D Model The analysis and comparison of mesh properties can be done with the help of 3D models: either by a simple geometric model representation or by a superposition of any FOM distribution along the model’s surface. All rendered models are presented using a parallel orthogonal projection. Model Rendering – A possible way of analysing a model is by simply inspecting its surface. Models can be viewed on screen using flat or smooth shading. The user can also select a wireframe rendering of the models in order, for example, to inspect vertex distribution. Colored Model – Understanding, for any FOM, how its values are distributed across the mesh is important, since it is then possible to judge its local significance. This is accomplished by coloring a model according to the calculated values for the selected FOM. Models are colored using a rainbow color scale, mapping 0 to blue and the maximum value obtained to red. Although, the rainbow color map is not perceived as being linear [2], which means that mapping values linearly to it is not very correct, we use it because we are focusing on giving, basically, qualitative information through the colored models. If the mapped distribution corresponds to an intrinsic property, it is superimposed on the 3D model for which it was computed. If it is a difference measure, it is represented on the reference model.
Figure 4. From left to right: original model, processed model and colored model representing data obtained by using the Geometric Deviation FOM.
4.3. Statistical Representations
5. Visualization and Interaction
Although coloring gives a good idea of a FOM’s values distribution along a model, showing where they occur, it can be difficult to obtain a global idea, due to the impossibility of viewing all the model’s surface simultaneously. The provided statistical representations may help to better understand and compare the obtained results. Histograms – By presenting the obtained FOM values using a histogram, it is possible to have a complementary view of the one given by a colored model, as it summarizes the FOMs distribution. One problem of representing the FOM values (or any other type of data) using a color scale is that the presence of outliers may stretch the scale too much, not allowing a perceptible difference among close values. With this in mind, a feature was added to allow a variation of the range of values represented by the histogram and color scale used. It is possible, using two sliders, to set lower and upper saturation values (thresholds). Values below the lower threshold are represented in blue and values above the upper threshold are represented in red, leaving the entire color scale (and all bars of the histogram, except the first and the last, which contain the saturated values) to represent the values in between. This allows to more clearly view the FOMs distribution, on the histogram and on the colored model, which is re-colored according to the color scale changes. With this feature, it is also possible to clearly identify all the surface areas where the FOM value is greater or smaller than a specific value. Figure 6 shows a histogram and associated colored model. Boxplots – Boxplots are most useful when comparing two or more sets of sample data. Through a boxplot, differences in location, range and asymmetries are clearly made visible. A boxplot also gives a picture of the symmetry of a dataset, and shows outliers very clearly. So, boxplots are made available when viewing data concerning the FOMs. The detection of outliers can also give a hint about how the sliders associated with the histogram can be adjusted to better use the color scale.
In P OLY M E C O an attempt was made to provide the user with several ways of changing among representations, or viewing several of them simultaneously, which makes easier the comparison of results. Regarding the interaction options, it is possible to manipulate all the presented models by changing their position, orientation and size. Moreover, when several models are being viewed simultaneously, it is possible to manipulate them in a synchronized way, i.e., manipulating one of the models will result in that same transformation being automatically applied to all other visible models. When a colored model is viewed, it is possible to activate a probe tool that will allow the user to obtain the FOM value for a particular point on the mesh. Because FOMs are only measured for particular sample points (generally vertices, except for triangle quality), only FOM values associated with vertices or faces will be given.
5.1. Colored Model In this visualization mode, test results are shown using a model, colored according to the values of the selected FOM. If the user chooses to view the reference model, or the one for which the FOM was computed, they will appear with the same position, orientation and size as the colored model. Figure 2 shows this visualization mode.
5.2. Original vs. Model
Processed vs.
Colored
This visualization mode presents the reference model, the processed model and the colored model according to the results obtained using a FOM. This allows to visually compare the original and processed models focusing, for example, on areas where the error incidence (observed in the colored model) is higher. Although the colored model is
Figure 5. Several models are compared side-by-side: (top) using individual color scales; (bottom) using a common color scale. similar to the original model (when a difference measure is used), the presence of color can mask some features, which is the reason why the original model is also presented. Figure 4 shows this visualization mode.
5.3. Side-by-Side Results Viewing In this visualization mode, it is possible to view, side-byside, all the FOMs computed for a processed model . For example, one can view the results obtained with Geometric Deviation and Gaussian Curvature FOMs at the same time and see if, for example, the geometric deviation is higher when the curvature is also higher. So, this can help to identify similar behaviors among the FOMs and to have a global idea of the results.
5.4. Side-by-Side Results Comparison When several processed versions of a model are tested, it can be useful to view all the results for a same FOM side-byside (e.g., the Geometric Deviation results for all the simplified versions of a model), in order to compare, for example, the distributions that result from each kind of processing. But, care has to be taken in order to only compare data that can be safely compared. First, the results must all come from the same FOM having the same model as reference (only applicable to difference measures). Second, we cannot forget that all the colored models use the same color scale, mapping 0 to blue and the maximum computed FOM value to red. Consequently, a direct comparison of the colored models can only give information about the FOM values incidence along them, but it cannot be used to decide which is the model having the greatest FOM value. While numerical data can be used for this purpose, a comparison
of the FOM’s distributions won’t be easy to perform. Thus, one must use a common color scale where the 0 value of a FOM is still mapped to blue, but red represents, now, the maximum computed FOM value among all models. Figure 5 (top) shows three colored models being compared using individual color scales and (bottom) the same models compared using a common color scale. Notice that without a common color scale some surface areas in different models seem to have the same FOM value. On the other hand, with a common color scale, it is clear that higher FOM values were computed for the center model. Comparison is also possible using histograms, viewed sideby-side, and once again care has to be taken in order to realize that direct comparison among them can only be made when they are being drawn for the same range of values. This kind of comparison can get handy, for example, when comparing triangle quality between meshes, as it can clearly show if triangle quality drifted up or down. Finally, the comparison can be made using boxplots (figure 7). This shows clearly the differences between data sets. The numerical data that characterizes each boxplot (first and second quartiles, median, etc.) is also shown.
6. Conclusions and Further Work A software tool is presented which allows analysis and comparison of polygonal meshes. This tool provides an environment where it is possible to work with multiple models and computed FOMs at the same time, and where several representations are available. It is also possible to choose among several view modes which allow, for example, the simultaneous use of several representations and the com-
Figure 6. Colored model and corresponding histogram.
Figure 7. Comparison using boxplots. parison among results. When comparing results using colored models (or histograms), the option of using a common color scale (value range) is, we believe, very important. A probe tool is also available which allows knowing the FOM’s value associated with a specific point on a colored model. All presented models can be manipulated in order to change their position, orientation and size. This can be done synchronously between models presented on screen, and facilitates their inspection. Much work can still be done to improve P OLY M E C O. One of our objectives is to add more FOMs in order to allow measuring other mesh properties. We also intend to add other representations in order to enhance the way information is presented. The use of other color scales, namely to represent signed FOMs, is also an objective. Apart from that, an option to save the computed FOM data for future analysis would be of great interest, namely when dealing with large models or a large number of computed FOMs.
7. Acknowledgements The authors would like to thank Micha¨el Roy for providing the source code for MeshDev. The first author would like to thank the research unit 127/94 IEETA, of the University of Aveiro, for the grant that supports his work.
References [1] N. Aspert, D. Santa-Cruz, and T. Ebrahimi. Mesh: Measuring errors between surfaces using the hausdorff distance. In Proc. IEEE Inter. Conf. in Multimedia and Expo 2002, volume 1, pages 705–708, Lausanne, Switzerland, 2002. [2] L. D. Bergman, B. E. Rogowitz, and L. A. Treimish. A rulebased tool for assisting color map selection. In Proc. IEEE Visualization ’95, pages 118–125, 1995. [3] P. Cignoni, C. Rocchini, and R. Scopigno. Metro: measuring error on simplified surfaces. Computer Graphics Forum, 17(2):167–174, 1998. [4] M. Meyer, M. Desbrun, P. Schr¨oder, and A. H. Barr. Discrete differential-geometry operators for triangulated 2-manifolds. In H. Hege and K. Polthier, editors, Visualization and Mathematics III, pages 35–58. Springer-Verlag, 2003. [5] P. P. P´ebay and T. J. Baker. Analysis of triangle quality measures. Math. of Comput., 72(244):1817–1839, 2003. [6] M. Roy, S. Foufou, and F. Truchetet. Mesh comparison using attribute deviation metric. Int. Journal of Image and Graphics, 4(1):1–14, 2004. [7] S. Rusinkiewicz. Estimating curvatures and their derivatives on triangle meshes. In Proc. 2nd Inter. Symp. on 3D Data Proc., Vis., and Transm., pages 486–493, 2004. [8] V. Verma and A. Pang. Comparative flow visualization. IEEE Trans. on Vis. and Comp. Graphics, 10(6):609–624, 2004. [9] L. Zhou and A. Pang. Metrics and visualization tools for surface mesh comparison. In Proc. SPIE 2001, vol 4302, 2001.
