基于距离场的二维偏移曲线快速生成方法

Fast construction of 2D offset curve based on distance field

提出了一种快速生成二维偏移曲线的方法.对于无自相交的二维多边形曲线,该方法能构造无自相交、保留准确尖锐特征的二维等距偏移曲线.算法的基本思想:先在一个均匀网格上根据给定的曲线采样一个局部有向距离场,然后使用等值线抽取方法从有向距离场中获取偏移曲线.在构造局部距离场时引入3个过滤器,在远离偏移曲线的区域消除大量冗余计算.采用经典MS(marching square)方法抽取初始多边形偏移曲线,通过一个混合解析解和二分搜索方法,快速计算得到偏移曲线与网格边的准确交点.根据最近点位置信息对初始多边形偏移曲线进行简化和特征重构(如尖角和圆弧),构造无自相交、顶点数少、具有尖锐特征、含混合直线和圆弧段的准确偏移曲线.大量数据实例说明该方法性能良好.

A fast approach of generating a 2D offset curve from any polygonal curve is presented, which preserves sharp features and is self-intersection free. The basic idea is first to establish a local signed distance field on a uni- form grid according to the input curve and then employ a contouring algorithm to extract the offset curve from the distance field. Three filters are conducted to generate a narrowband signed distance field around the offset curve in a very efficient way to reduce computation redundancies in regions far from the offset curves. The initial offset curve is derived by a traditional MS （Marching Square） method, the accurate intersections between the grid edges and the offset curve are computed quickly by a hybrid method employing the analytical solutions and the bisection search. Based on these closest points, an exact offset curve composed of line and arc segments is constructed by merging short line segments and reconstructing sharp features. The derived offset curve is intersection free and retains the sharp features. The quality and performance of this approach are demonstrated by a number of experimental tests on various examples.