No abstract uploaded!

No abstract uploaded!

The medial axis transform (MAT) is an important shape representation for shape approximation, shape recognition, and shape retrieval. Despite years of research, there is still a lack of effective methods for efficient, robust and accurate computation of the MAT. We present an efficient method, called {\em Q-MAT}, that uses quadratic error minimization to compute a structurally simple, geometrically accurate, and compact representation of the MAT. We introduce a new error metric for approximation and a new quantitative characterization of unstable branches of the MAT, and integrate them in an extension of the well-known quadric error metric (QEM) framework for mesh decimation. Q-MAT is fast, removes insignificant unstable branches effectively, and produces a simple and accurate piecewise linear approximation of the MAT. The method is thoroughly validated and compared with existing methods for MAT computation.

In this paper, we introduce a novel method that can generate a sequence of physical transformations between 3D models with different shape and topology. Feasible transformations are realized on a chain structure with connected components that are 3D printed. Collision-free motions are computed to transform between different configurations of the 3D printed chain structure. To realize the transformation between different 3D models, we first voxelize these input models into similar number of voxels. The challenging part of our approach is to generate a simple path --- as a chain configuration to connect most voxels. A layer-based algorithm is developed with theoretical guarantee of the existence and the path length. We find that collision-free motion sequence can always be generated when using a straight line as the intermediate configuration of transformation. The effectiveness of our method is demonstrated by both the simulation and the experimental tests taken on 3D printed chains.

The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. In $R^2$, the cone intersection method (CIM) is one of the most eÆcient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) under $L_2$ norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. An approximation algorithm is also presented, which takes $O(n^2)$ time and $O(n)$ space. Results of some examples are given to illustrate the eÆciency of these algorithms.