Research And Implementation On Bézier Surface/ Surface Intersection Algorithm Based On Hierarchical Bounding Box

Freedom Surface/Surface Intersection is the most complex and important problem in the area of CAGD/CAM. It has widely applications in many algorithms, such as Surface Trim, Tool-path Calculation and Geometric Modeling Connection. Although Freedom Surface/Surface Intersection is an active research all along, there's not efficient method to solve it. Because freedom Surfaces are generally high-order parametric surfaces, which their intersection curves can't be got by using pure mathematic methods. However, there also have problems of precision and efficiency by using geometric methods or non-pure mathematic methods.Bézier surface is one of the basic molding tools in CAGD. For using Bernstein polynomial basis function to represent itself, Bézier surface has many advantages such as easy to subdivide, strong convex hull character, fewer calculation in surface operations and so on. Therefore, Bézier surface is widely paid attentions in the area of Industry and CAGD, it also has important applications in Computer Graphics and Geometry molding. Therefore, the research of Bézier Surface/Surface intersection algorithm has theoretical and actual significance.Based on Surface Divide and Conquer method and collision of Hierarchical Bounding Boxes, this paper makes full use of the advantages of convex hull character and easy to subdivide to study Bézier Surface/Surface intersection algorithm. The efficiency of overlapping test is improved by using two kinds of Hierarchical Bounding Boxes: Axis-aligned Bounding Box(AABB) and Oriented Bounding Box(OBB). The stability and efficiency of the algorithm is compared separately under situations of Axis-aligned Bounding Box(AABB) and Oriented Bounding Box(OBB).The algorithm utilizes the Quad-tree data structure to build recursive subdivision of Bézier surface. Hierarchic Bounding Boxes are constructed by the control points which obtain from upper surface subdivision. The Intersection of hierarchical bounding Boxes is tested and the resulting sub-surfces are triangulated. Utilizing the triangle/triangle intersection method evaluates the intersection points. The intersection curve is refined by using B-spline Curve. The article compares Axis-aligned Bounding Box(AABB) and Oriented Bounding Box(OBB) separately under situations of Finite depth Subdivison and adaptive depth subdivsion. OBB is shown to give more efficient and stabile results.