Self-intersection computation for freeform surfaces based on a regional representation scheme for miter points

摘要

We present an efficient and robust algorithm for computing the self-intersection of a freeform surface, based on a special representation of miter points, using sufficiently small quadrangles in the parameter domain. A self-intersecting surface changes its normal direction quite dramatically around miter points, located at the open endpoints of the self-intersection curve. This undesirable behavior causes serious problems in the stability of geometric algorithms on the surface. To facilitate a stable detection of miter points, we employ osculating toroidal patches and their intersections, and consider a gradual change to degenerate intersections as a signal for the detection of miter points. The exact location of each miter point is bounded by a tiny ball in the Euclidean space and is also represented as a small quadrangle in the parameter space. The surface self-intersection curve is then constructed, using a hybrid Bounding Volume Hierarchy (BVH), where the leaf nodes contain osculating toroidal patches and miter quadrangles. We demonstrate the effectiveness of our approach by using test examples of computing the self-intersection of freeform surfaces.