Parametric Surfaces Intersection Algorithm Based On Discrete Surfels

This thesis proposes a novel parametric surfaces intersection algorithm based on discrete surfels. The intersection algorithm of parametric surface/surface is one of the fundamental problems in computer aided geometric design. In recent years, the point-based modeling and rendering techniques have been paid much attention in computer graphics community. In this work, we integrate the subdivision algorithms for the parametric surfaces intersection with the advantages of the point-based modeling techniques.First, the parametric surfaces are sampled into the point sampled surfaces. The sample points are called surfels with geometric information attached. Adaptive octree is built to accelerate the intersection tests. Then the surfels near to the intersection curves are re-sampled adaptively according to the error analysis. The intersection points are found out based on the intersection between the surfels in the overlapped leaf-nodes of the octrees. Finally, the intersection segments are resulted after sorting these discrete intersection points.In the regions that the surfaces are possible to be tangential, the algorithm requires more accurate sampling. To find out these regions, the varying ranges of the normals are analysed as the supplement to the position information of the surfels.Compared to the traditional subdivision algorithms for the intersection of parametric surfaces, our algorithm does not need to maintain with the topology of meshes. So the adaptively resampling is more efficient and easier. Our algorithm can be applied to get the intersection between the parametric surface and point sample geometry. Experiments show that our algorithm is effective, easy to implement and the precision of the intersection lines is controllable.