Formulation Significance
The significance of the new formulation is highlighted on this page.
Decreased Computational Complexity
Gradient-based optimizers evaluate the constraint function hundreds of times during optimization.
As a result, it is desired to decrease the computational cost of evaluating the constraint function.
Prior methods scale in computational complexity with the number of points representing the geometric shape \(\mathcal{O}(N_\Gamma)\).
Because the new formulation generates a B-spline level set function, the computational complexity is independent of \(N_\Gamma\).
The resultant computational complexity is \(\mathcal{O}(1)\) when considering higher and higher samplings of a geometric shape, unlocking the potential to use
very fine scans of objects.
The figure below shows the computational complexity of the new formulation versus the formulations of Hicken and Kaur [HK22] and Lin et al. [LGY+22].
Locally Approximates the Signed Distance
A distance to the geometric shape is desired for the geometric non-interference constraint.
If a desired proximity to the shape is needed for the optimization problem, then a distance-based non-interferenc constraint is desired.
The formulation presented locally approximates the signed distance for a small distance \(\epsilon\) from the surface \(\Gamma\).
As a result, the nonzero isocontours of the function will accurately represent an offset distance.
The figure below shows the point-wise signed distance error of the isocontours, normalized by the minimum bounding box diagonal.
Additionally, the accuracy of the signed distance approximation increases as more data from the point cloud is provided. The figure below shows the decreasing signed distance error as the number of points in the point cloud increases. Note, the explicit formulation by Hicken and Kaur [HK22] is an explicit method, and will always decrease in error, so long as the sampled point cloud is evenly sampled and is free of noise and outliers.
Zero level set error |
Nonzero level set error |
|---|---|
|
|
Smooth Function (Continuous and Differentiable)
The exact signed distance function (SDF) is continuous but non-differentiable.
By its nature, the B-spline representation will always be continuous and differentiable.
In addition, the regularization energy of the energy minimization formulation further smoothens the function to encode better second derivative information to the constraint function for the gradient-based optimizer.
The figure below indicates the locations of non-differentiability, and the resultant smooth function generated by the new formulation.
