Publications
Main
Variational Implicit Surfaces
Modeling
Rendering
Shape Transformations
Reconstruction
Reconstruction from Range Data: Search Space for Lambda, Phi, and Delta | |
|
The above figures are a visual comparison of our reconstruction of the toy dinosaur (lower right) with the original data (upper left), with the Crust reconstruction (upper right), and with the variational implicits reconstruction using the thin-plate radial basis function (lower left). In our reconstruction algorithm, three control parameters need to be set. Our results show, however, that appropriate values for these parameters are limited. Consequently, selection of these parameters does not become an extra burden on the user. Selecting LambdaRecall from the section on Interpolation vs. Approximation that lambda controls the trade-off between fitness to the data points and the smoothness assumption. The following measures of fitness and curvature corroborate this fact, as well as help guide the selection of appropriate values for lambda.Fitness ErrorFitness error is the aggregate distance between the original constraint points and the reconstructed surface. We measure this distance by first constructing a polygonal model from the implicit function using Marching Cubes [Lore 87], and then finding the closest vertex of the polygonal model to a given constraint point. This vertex is an intial starting point on the surface from which we can then search for even closer surface locations to the given constraint point. A closer surface point is found by crawling along the surface in small increments until a small increment in any four directions along the surface does not yield a location that is closer to the constraint. When this stopping location is found, the Euclidean distance is calculated and accumulated. The figure below shows a plot of the total fitness error, average curvature, and total surface area for the dinosaur reconstructions. The plot on the left compares the total error in fitness to the data for the dinosaur reconstructions using the thin-plate (o) and multi- order (*) radial basis functions, for lambda = 0.0003, 0.001, 0.003, 0.01, 0.03, and 0.1. The center plot compares the total curvature for both basis functions at the same values of lambda. The plot on the right compares the total surface area for both basis functions at the same values of lambda. The vertical dotted line in all three plots mark the location of lambda = 0.003.
As expected, small values of lambda correspond to less error in data
fitness. Note that the error is an accumulation of the Euclidean distance
measured at all the data points, not just those used in the
reconstruction. Consequently, the error is not zero even when lambda = 0,
corresponding to exact interpolation. Error in fitness rises more sharply
for the multi-order radial basis function as lambda is increased than for
the thin-plate basis function. At lower values of lambda (0.003 or less),
the aggregate error for both basis are comparable. The sharp rise in
fitness error for the multi-order basis provides an upper bound of 0.003
for lambda. Measure of CurvatureWe measure curvature by accumulating an approximate curvature at every vertex of the polygonal model extracted from the implicit function using Marching Cubes [Lore 87]. We use a curvature approximation that was developed for the smoothing operator in [Desb 99]. This measure is based on the normal directions of triangles adjacent to each vertex and normalized by the total area of the triangles. High curvature is associated with sharp features in the surface, while low curvature is associated with overshoots and blobby surfaces. The center plot in the above figure shows the total curvature for the thin-plate and multi-order radial basis functions at varying values of lambda. As expected, the curvature drops at large lambda values since the constraints are no longer interpolated and the influence of the smoothness model is stronger. The plot reveals that the curvature of the surface generated by the multi- order basis is higher than that generated by the thin-plate basis at values of lambda less than or equal to 0.003. The thin-plate surface exhibits less curvature at lambda values of 0.003 or less, corresponding to the blobbiness seen in the reconstructions. When lambda is greater than 0.003, however, the surface generated by the multi-order basis exhibits lower curvature than that of the thin-plate basis. This is further evidence that lambda should be kept at 0.003 or less. A measure of the surface area shown in the plot on the right reveals that the thin- plate basis tends to produce larger surfaces (an indication of overshooting surfaces) across all values of lambda. The multi-order basis function achieves a good balance between a tight fit and a smooth surface because they generate surfaces with high curvature and equivalent fitness error in comparison to the thin-plate basis. We have found that lambda values between 0.001 and 0.003 work well in practice, and this is consistent with the plots in the figure above.Selecting delta and tauRecall from the section on A Radial Basis Function for Multiple Orders of Smoothness that delta controls the amount of first order smoothness, while tau controls the amount of third order smoothness. Initial attempts at reconstruction using the multi- order basis function showed that a delta value of 0.25 and below and tau values of 0.01 and above produce reconstructions which are far too smooth and blobby. Consequently, we constrained our search space to be more along the delta axis than along the tau axis. The figure below shows the limiting values for delta and tau in order to avoid imaginary values from occuring in equations for the multi-order basis function. The blue line in the graph indicates the limiting values, and the red stars are the parameter values we tested. Within our selected search space, delta becomes a course adjuster, while tau is a fine adjuster for fitness and curvature. We show in the following sections that selection of the delta and tau values is not an extra burden on the user because there is a limited space of values which produce locally detailed and globally smooth surfaces with low fitness error.
Fitness ErrorThe figure below is a plot of the average fitness error for the toy dinosaur reconstructions using various values of delta and tau. Fitness error was measured for delta values of 1.0, 5.0, 10.0, 15.0, 20.0, 30.0, and 40.0, and tau values of 0.0005, 0.001, 0.005, 0.01, and 0.05 (different values were used for this last tau value due to the imaginary value limitation. Delta is 40.0 at the near corner of the graph and 1.0 at the leftmost corner along the delta axis. tau is 0.0005 at the near corner and 0.05 at the rightmost corner along the tau axis. The plot shows that delta has a greater influence on fitness to the data since changes in delta cause greater changes in fitness error than changes in tau. delta can be regarded as a course level adjuster, while tau is a fine level adjuster within this search space. In general, larger delta values produce a tighter fit, corroborating the fact that delta controls first order smoothness. Note, however, that at the largest value of delta in the plot (delta = 40.0), changes in tau cause jumps in the fitness error. A delta value of 50.0 was found to result in even greater fitness error. This indicates that 40.0 is the upper bound for appropriate delta values for this data set. We have found by visual inspection that values of 30.0 and 40.0 for delta produced the most detailed, yet smooth surfaces. At such values, the average fitness error is below 0.5 in euclidean distance. This corresponds exactly with the data set in that the range resolution is 0.5, which means that the surface may exist anywhere within a radius of 0.25 from the data points. A value of 0.01 or 0.005 for tau was found to consistently produce the smallest fitness error across all values of delta. These values correspond to the third and fourth gridlines along the tau axis.
Measure of CurvatureThe figure below is a plot of the average curvature of the reconstructions using the same values of delta and tau as that of the fitness plot above. Although a pattern is not as apparent here as in the fitness plot, the plot supports the fact that delta controls first order smoothness, while tau controls third order smoothness. High curvature is maintained at large values of delta and small values of tau, while low curvature is prevalent at large values of tau (values at the far right side of the graph). Low curvature is associated with overshooting surfaces that tend to be blobby. delta values of 30.0 or 40.0 (second and first grid lines along the delta axis) and tau values of 0.005 or 0.01 (third and fourth grid lines along the tau axis) generate surfaces which exhibit relatively high curvature compared to the other values.
| |
| back | next |
