Fast Volume-Preserviing Free Form Deformation Using Multi-Level Optimization

摘要

We present an efficient algorithm for rpeservign the total volume of a solids undergoing free-form deformation usign discrete level-of-detail representations. Given the boundary representation of a solid and user-specified deformation, the algorithm computes the new node positions of hte deformation lattice, while minimizing the elastic energy subject to the volume-preserving criterion. During each iteration, a non-linear optimizer computes the volume deviation and its derivatives based on a triangular approximation, which requires a finely tessellated mesh to achieve the desired accuracy. To reduce the computational cost, we exploit the multi-level representations of the boundary surfaces to greatly accelerate the performance of the non-linear optimizer. This technique also provides interactive response by progressively refining the solution. Furthermore, it is generally applicable to lattice-based free-form deformation and its variants. Our implementation has been applied to several complex solids. We have been able to achieve an order of magnitude performance improvement over the conventional methods.