| Abstract | The need for the determination of Surface Intersection exists in many real-world applications. Such determination is based on a recurrent operation so that its computation should be fast, reliable and suitable for the surfaces involved. Two methods are applied and two new methods are proposed in this work for determining the intersection of two Bezjer Surfaces: Subdivision, Marching Methods, Polyhedron Intersection, and Hybrid between subdivision and polyhedron intersection. Since Bezier and two generalized Ball surfaces can be treated as polynomials, all these methods can be properly applied to the calculation of the intersection of two generalized Ball surfaces by converting them to the Bezier surfaces. However, the relationships between Bezier and Said-Ball (or Wang-Ball) surfaces must be explicitly defined. Using homogeneous coordinates in the de Casteljau algorithm for the points on an polynomial Bezier surface, the de Casteljau algorithm to compute the points on a rational Bezier surface is readily obtained. Modifying some parts of four methods, algorithms for determining the intersection of two rational Bezier surfaces are eventually achieved. Similar to the case of rational surfaces, the relationships between Bezier and Said-Ball ( or Wang-Ball ) surfaces must be appropriately introduced in order to make use of the intersection methods for Bezier surfaces. Subdivision methods reduce the problem of surface/surface intersection to the intersection of two planes by recursively subdividing two surfaces until they are relatively flat. Bounding boxes of the surfaces are used to coarsely locate the intersection parts. The irrelevant parts that do not participate in the intersection will be gradually eliminated. Only relevant pairs of subsurfaces will be subdivided until they meet a predetermined tolerance. Ultimately, the final result is a collection of line segments. An alternative method is to roughly locate the intersection part by the intersection of two polyhedra. Instead of directly calculating the intersection from the surfaces, the polyhedra with quadrilateral facets that are readily formed by the control nets are considered. By this approach, the problem of surface/surface intersection can be reduced to the problem of polyhedron/polyhedron intersection. Then the problem can be further simplified by triangle/triangle intersection. The result is one or more sets of consecutive line segments, which will be used as a starting set for further refinement to obtain the true intersection. Combining the two previous methods (Subdivision and polyhedron intersection), a hybrid method is obtained. It integrates the subdivision method with the intersection of two triangulated polyhedra. Thus, the final result is much more precise than that for plane/plane intersection. Consequently, it is closer to the exact result. Unfortunately, none of the three methods can produce the true intersection curves. Further refinement of the intermediate result needs to be performed. Two marching methods, using Tangential or Circular steps, are used to calculate exact intersection points. A major difference between the two techniques is the step size. In the method using tangential steps, the step size has to be fixed and predefined while that of the circular step is dynamic and automatically changed. The selection of which techniques to be used depends on the problem itself: if the result is crooked or winding, the circular step is recommended, otherwise it is sufficient to use the tangential step. In this study, all of the methods focus on the intersection of two Bezier surfaces. To make use of these methods for the Said-Ball and Wang-Ball surfaces, conversions frim these Ball surfaces into Bezier surfaces are necessary. This dissertation presents relationship among Bezier, Said-Ball and Wang-Ball curves. These are used ad the foundations for the relationships between Bezier and Ball surfaces. Using the relationships between Bezier and Ball surfaces, the intersection of two Ball surfaces is readily obtained by converting Ball surfaces into Bezier surfaces and determining the intersection of two Bezier surfaces. Thus, this is adequate for determining the intersection of two different kinds of surfaces. Furthermore, all these methods can be applied to the intersection of two rational Bezier surfaces. Using the de Casteljau algorithm for a rational Bezier surface, the proposed methods based on subdivision for Bezier surfaces can readily be extended to rational Bezier surfaces. The other methods can be readily adapted to the rational Bezier surfaces. Similarly, using the relationships between rational Bezier and rational Ball surfaces, the intersection of two rational Ball surfaces is readily obtained by converting rational Ball surfaces into rational Bezier surfaces and determining the intersection of the two resulting rational Bezier surfaces. |