An optimization algorithm for free-form surface partitioning based on weighted gaussian image
Published in Graphical Models, 2005
Abstract: Partitioning free-form surfaces into sub-patches and finding optimal representative normal for each patch to maximize a global objective function is an important two-level operation in diverse industrial applications. In this paper, by solving a maximum hemispherical partition- ing problem raised from a weighted Gaussian image, an optimization algorithm is proposed to partition a free-form surface into two sub-patches and simultaneously report the optimal rep- resentative normals. By discretizing the free-form surface with W sample points and clustering normals on the surface with m distinct sample normals, the proposed algorithm is designed, in general, with $O(m^2W^2)$ time complexity and $O(W^2)$ space complexity, and in particular, if the surface is convex, in $O(m^2 \log m)$ time complexity. Case studies with four representative exam- ples are presented and a real world application is exploited to demonstrate the effectiveness and usefulness of the proposed algorithm.
Recommended citation: Kai Tang, Yong-Jin Liu (2005) An optimization algorithm for free-form surface partitioning based on weighted gaussian image. Graphical Models, Vol. 67, No. 1, pp. 17-42, 2005.