Research On Point-sampled Model Representation And Space Deformation Algorithm Based On KD-tree

Point sampled model is primary element of geometric model representation and is widely employed to represent three-dimension model. Space deformation technology has been widely applied to geometric modeling and computer animation, how to implement space deformation on the point-sampled model is the important topic in space deformation research.With KD-tree as basis in this paper, point-sampled representation method of anisotropic quantization is proposed based on the property of equal space partitioning of midpoint-split KD-tree, multi-resolution storage structure of point-sampled model and the multi-resolution rendering are achieved by bread-first order traversal of this KD-tree. Secondly, a new space deformation method based on point-sampled model represented by the KD-tree is presented, this method prodigiously improves the efficiency of space deformation algorithm and increases the efficiency of real-time geometric model deformation, in addition, space position constrain, regularization and rotation also are proposed in this paper, then the resulting unconstrained nonlinear least-squares problem is solved by the iterative Gauss-Newton algorithm, all these strategies make deformation results more natural.