An Octree Algorithm For Point-based Surface Matching

Three dimensional surface matching is of great importance in a variety of areas, such asthe reverse engineering, the virtual reality, the medical image registration,the robot, theautomatic control fields, and molecules structure design of drug and so on, which is animportant task in computational geometry.The key of the 3d objects' matching is the surface's matching, whose basic problem is todefine and compute the difference of the two surfaces (which are always surfaces of 3dgeometric objects). The difference is completely decided by the inherent quality, which isindependent of other factors. For example, a surface should be the same as the image thesurface forms by translation and revolution. The surface matching includes the rigid surfacematching and the flexible surface matching. Their difference is that the rigid surface is onlythe same as its image in the rigid movement, but the flexible surface in larger movementgroup. The rigid is an especial example to the flexible. To research the rigid surface'smatching is the basic as the flexible surface's. The surface matching algorithms depend on thesurface's expression methods in a large degree. In computer graphics, the most commondiscrete surface's expression includes the points cloud and the triangular mesh. The originaldata gotten by the 3d scanner is the points cloud, whose structure is easy and which can betreated in kinds of means.The main work of the article brings forward a universal matching method to the rigidsurface based on the points cloud. The algorithm don't need any reference points and labelpoints in measured objects and is independent on the position. In the algorithm the pointscloud realizes partial and whole matching by the octree built by the estimating the curvatureand SEPMap. The algorithm doesn't need the character, and so is independent of thecurvature extremum.Just because of these, the body of the article is as follows:In the first chapter, the popular work in the world is summarized, mainly about thecharacter's research;In the second chapter, the points cloud research is summarized, including commonmethods dealing with the points;In the third chapter, the information about the octree is summarized, which is theimportant tool in our algorithm; In the fourth chapter, we bring forward an octree algorithm of the surface matchingbased on the points cloud. And we analyze the algorithm's feasibility from the point of theexperiment and the theory.In the final, the result and the future work about the algorithm bringing forward in thisarticle is given.