Splines Over Iterated Voronoi Diagrams

【摘要】亚利桑那州立大学的杰拉尔德·法林（Gerald farin）：线条被用来描述几何物体，它被分解成一个个独立的部分，从而保证了这些部分的整体平滑度。样条广泛应用于汽车、航空航天和其他工程学科。当几何形状具有直线结构时（例如汽车的车顶），它们工作得非常好，但当不是这种情况时，则需要相当大的努力。由于这个原因，样条在生物或医学应用中很少使用，因为这些应用的形状往往是非常不规则的。本研究引入了一类新的样条曲线，它不仅具有标准样条曲线的所有平滑特性，而且能够处理复杂和非结构化的形状。本研究探索了一类新的样条曲线，这些样条曲线是在非结构化的2D点集上定义的-即，假设没有规则结构。b样条曲线理论中最基本的算法是递归de Boor算法。将该算法推广到平面上Voronoi图层次结构的递归算法。所得到的表面是任意度的，并且是分段光滑的。它们能够再现任何阶的多项式。由于de Boor算法是所有样条理论的基础，因此对非结构化点集的适当重新表述是一个重大突破，也是本研究的主要智力优点。定义在非结构化点集上的样条的存在为处理复杂形状提供了可能性。这对于有机形状尤其重要，因为有机形状往往是高度不规则的。因此，这项研究的更广泛的影响是有可能成功地描述非工程形状使用类似于标准样条的技术。

ABSTRACT 0306385Farin, Gerald Arizona State UniversitySplines are used to describe geometric objects by breaking down into individual parts such that the overall smoothness of thes pieces is guaranteed. Splines are widely used in the automotive, aerospace, and other engineering disciplines. They work very well when the geometry has a rectilinear struture (such as the roof of a car), but need considerable effort when this is not the case. For that reason, splines are not much used in biological or medical applications, where shapes tend to be highly irregular. This research introduces a new class of splines having all the smoothness properties of standard ones but also being able to cope with complex and unstructured shapes. This research explores a new class splines, those that are defined over an unstructured set of 2D points - i.e., no regular structure is assumed. The most fundamental algorithm in the theory of B-spline curves is the recursive de Boor algorithm. This algorithm is generalized to a recursive algorithm involving the construction of a hierarchy of Voronoi diagrams in the plane. The resulting surfaces are of arbitrary degree and are piecewise smooth. They are capable of reproducing polynomials of any order. Since the de Boor Algorithm is fundamental to all spline theory, a proper reformulation for unstructured point sets is a significant breakthrough and constitutes the main intellectual merit of this research. The existence of splines defined over unstructured point sets opens up the possibility of handling complex shapes. This is particularly important for organic shapes, which tend to be highly irregular. Thus the broader impact of this research is the possibility to successfully describe non-engineering shapes using techniques similar to standard splines.