CN1698070A - 用于将二维对象转换成二维距离场的方法 - Google Patents

Abstract

将二维对象转换成二维距离场的方法。对象表示为边界描述符集合和填充规则。预处理边界描述符集合以及由预处理的边界描述符集合构成空间层次。初始化交点的高速缓存。查询一组位置处的空间层次以便确定所述位置处的距离集合。该查询调用在每个位置处的距离函数以便确定无符号距离。由交点的高速缓存、位置和填充规则，确定无符号距离的符号。距离集合用来构成二维距离场。

Description

用于将二维对象转换成二维距离场的方法

技术领域

本发明通常涉及计算机制图领域，以及更具体地说，涉及将二维对象转换成距离场(distance field)。

背景技术

在计算机制图领域中，绘制二维对象十分重要。将二维对象，诸如字符形状、公司标志以及包含在文档中示例说明的要素绘制成静态图象或包含动画的帧序列。有许多用于二维对象的表示，以及通常对于特定的操作，诸如绘制和编辑，一种表示优于另一种表示。在这些情况下，执行用于从一种形式到另一种的转换。

尽管现在集中在数字类型(可能是最普通和重要的二维对象)，但下述论述适用于所有类型的二维对象。

从数字类型的一些基本背景开始。典型的拉丁文字体体系，诸如Times New Roman或Arial，包括字体集，诸如常规、斜体、粗体和粗斜体。每种字体包括称为图示符的单个字符形状集合。每种图示符按其不同的设计特点，诸如基本几何结构、笔划粗度、衬线、接合度(joinery)、轮廓的位置和数量、淡与粗笔划的比率以及大小来区别。

有许多方法来表示字体，包括位图、轮廓，例如Type 1[AdobeSystem，Inc.1990]和TrueType[Apple Computer，Inc.1990]以及具有突出的轮廓的程序字体，例如Knuth的Metafont。已经由Cambridge，Mass.的Bitstream Inc.、Calif.，Mountain View的AdobeSystem，INc.、Calif.，Cupertino的Apple Computer，Inc.、Bellevue，Wash.的Microsoft Corportion、德国的Hamburg的URW以及Wilmington，Mass.的Agfa Compugraphic采用并普及基于轮廓的表示。

Hersch，“Visual and Technical Aspects of Type”，剑桥大学出版社，1993以及Knuth，“TEX and METAFONT：New Directions inTypesetting，”数字出版社，Bford，MA 1997，包含字体的历史和研究的综合回顾。

特别重要的是两类字号：体型大小和显示字号。以相对小的点大小，例如14pt或更小绘制体型中的字体，以及用在文档的主体中，如在本段中。体型要求用于清晰性和阅读舒适性的高质量绘制。体型的大小、字体以及基线方向在单个文档中很少变化。

以相对大的点大小，例如36pt或更高绘制显示类型中的字体，以及用于标题、大标题以及设计和广告中以便设置基调或引起注意。与体型相比，显示类型强调美学，其中缺少空间和时间走样(temporalaliasing)很重要而不是清晰度，其中对比度比反走样(antialiasing)更重要。用于表示和绘制类型的框架通过冲突需求很好地处理这两种是至关紧要的。

可将类型绘制到输出设备，诸如打印机或显示器上，作为双层(bilevel)、灰度级或彩色。一些绘制引擎使用用于非常小字号的双层绘制来实现更好的对比度。然而，非常微量的灰度级字体正好是清晰的。

微调(hint)是与每个图示符一起存储的一组规则或过程以便指定在绘制期间应当如何修改图示符的轮廓，从而保留特征，诸如字体中所有图示符上的对称、笔划粗细度以及统一外观。

当试图设计自动和半自动微调系统时，微调过程在设计用于低分辨率显示设备的新字体和现有字体的微调中仍然存在主要的瓶颈。另外，解释微调规则的复杂性排除用于字体绘制的硬件。缺少硬件支持迫使在软件光栅化，诸如每个像素使用更小的样本期间，特别是当实时动画类型时进行折衷。

灰度级字体绘制通常涉及一些形式的反走样。反走样是使在双层字体中出现的锯齿边缘或阶梯效应平滑的过程。尽管一些字体绘制引擎是专用的，但大多数使用超级采样(supersampling)，在格栅调整和微调后，在用2×2或4×4盒式滤波器(box filter)进行下采样(down-sampling)后，每个像素分别具有4或16个采样。

通过用于绘制速度的需要，调整基本滤波，诸如盒式滤波。然而，即使那个方法对于实时绘制(如动画类型所需要的)也太慢，且所绘制的图示符经受空间和时间走样。

印刷术中的两个重要趋势揭示了现有技术字体表示的一些固有局限，从而提供用于变化的需要。

第一种趋势是由于办公室中计算机的显著作用、在家Internet浏览的普及上升以及PDA和其他手持电子设备的激增，越来越强调阅读屏幕上的文本。这些显示器通常具有每英寸72-100点的分辨率，其显著地低于印刷设备的分辨率。

当光栅化类型以便确保阅读舒适和清晰度时，这种低分辨率要求特殊的处理，正如由公司诸如Microsoft和Bitstream在它们各自的ClearType和Font Fusion技术中投资的资源所证明的。

第二种趋势是使用动画类型，或动态印刷术。使用动画类型来传达感情、增加兴趣以及可视地吸引阅读者的注意。动画类型的重要性由其在电视和Internet广告中的广泛使用所论证。

不幸的是，传统的基于轮廓的字体在这些领域中都具有局限。在低分辨率显示器上的绘制类型要求仔细处理以便平衡用于清晰度的良好对比度的需要，以及降低用于阅读舒适的空间和/或时间走样。

如上所述，基于轮廓的字体通常微调以便向用于最佳外观的绘制引擎提供指示。字体微调是劳动密集的并且很昂贵。例如，开发用于可能具有大于上万图示符的日语或中文字体的微调良好的字体会花费很多年。因为微调的焦点在于改进字体的绘制质量，所以微调对沿任意路径放置的类型和用于动画类型易于低效。

尽管高质量滤波能用来对具有有限多个字体大小和字体的静态文档中的灰度级类型进行反走样，通常实时绘制需求限制在动画类型中使用滤波。

发明内容

本发明提供一种用于将二维对象转换成二维距离场的方法。对象表示为边界描述符集合和填充规则。预处理边界描述符集合以及由预处理的边界描述符集合构成空间层次。初始化各交点的高速缓存。查询一组位置处的空间层次以便确定各位置处的距离集合。该查询调用在每个位置处的距离函数以便确定无符号距离。根据各交点的高速缓存、位置和填充规则来确定无符号距离的符号。使用距离集合来构成二维距离场。

附图说明

图1A和1B是用于图示符的现有技术距离场表示的框图；

图2A和2B是根据本发明的一个优选实施例的距离场表示的框图；

图3是根据本发明的一个优选实施例的距离场的双二次单元的框图；

图4是根据本发明，用于按图象顺序反走样对象的方法的流程图；

图5是由本发明使用的线性滤波器的图；

图6A、6B和6C是接近像素分量的各采样的图；

图7是根据本发明，用于按对象顺序反走样对象的方法的流程图；

图8是根据本发明，用于基于距离的自动微调的方法的流程图；

图9是根据本发明，用于将笔划转换成距离场的方法的流程图；

图10是根据本发明，用于将二维对象转换成距离场的方法的流程图；

图11是根据本发明，用于将距离场转换成边界描述符的方法的流程图；

图12是根据本发明，用于动画制作对象的方法的流程图；以及

图13是根据本发明，用于在包围二维对象的角的单元内，生成二维距离场的方法的流程图。

具体实施方式

图示符的距离场表示

本发明将封闭的二维形状S，诸如图示符、公司标志或对象的任何数字化表示，表示为二维标记的距离场D。为描述目的，使用图示符。

非正式地，图示符的距离场测量从场中的任何一个点到图示符的边缘的最小距离，其中如果该点在图示符外，距离的符号为负，以及如果该点在图示符内则为正。边缘上的点具有零距离。

正式地，距离场是对所有p∈R²的映射D：R²→R，以便D(p)＝sign(p)·min{‖p-q‖：对S的零值等值表面上，即边缘上的所有点q}，sign(p)＝{-1，如果p在S外，+1，如果p在S内}，以及‖·‖为欧几里得范数。

使用用于每个像素的单个离散样本的现有技术的基于覆盖的绘制方法可能完全遗漏图示符，即使当样本任意接近轮廓时。所绘制的图示符具有锯齿状边缘并且遗失信息，这是空间走样的两种形式。如果动画图示符，那么时间走样在运动期间导致好像“图象抖动”的闪烁轮廓和锯齿状边缘。取每个像素的另外的样本以便产生反走样绘制能降低这些走样效应，但对可接受的结果，需要许多样本。

与此相反，根据本发明的连续采样的距离值表示图示符的邻近，即使当样本在形状之外时。事实上，能使用单个样本值来估计有多少图示符处于位于每个像素中央的滤波器覆盖区(filter footprint)内。

此外，因为距离场平滑地改变，即，它是C⁰连续，采样值随图示符移动而缓慢改变，这降低了空间走样假象。

距离场具有其他优点。因为它们是隐式表示，所以它们共享隐函数的好处。特别地，距离场允许用于设计字体的直观界面。例如，能单独地设计图示符的单个分量，诸如词干、条、圆形和衬线。在设计后，使用隐式混合方法来将这些分量混合在一起以便组成相同字体的不同图示符。

距离场还具有许多优点以便在动态印刷术或动画类型中提供，因为距离场提供对模拟对象间的相互作用很重要的信息。

在优选实施例中，使用自适应样本距离场，即ADF，见U.S.专利No.6,396,492，“Detail-directed hierarchical distance fields”，Frisken，Perry以及Jones，在此引用以供参考。

ADF是距离场的有效数字表示。ADF使用针对细节(detaildirected)的采样以便降低表示场所需的样本数量。将样本存储在单元的空间层次，例如四叉树中，用于有效处理。另外，ADF提供用于由采样值重新构造距离场的方法。

针对细节或自适应采样根据场中的局部偏差(local variance)来采样距离场：当局部偏差高时，使用越多样本，以及当局部偏差低时，使用越少样本。自适应采样显著地降低在整个场中以统一速率采样的规律采样距离场，以及在边缘附近总是以最大速率采样的3色四叉树的存储需求。

图1A-1B将用于Times Roman“a”和“D”的3色四叉树所需的单元的数量与在相同精确度的图2A-2B中的双二次ADF所需的单元的数量进行比较。单元的数量与存储需求直接相关。四叉树都具有等于512×512图象的距离值的分辨率。用于“a”和“D”的3色四叉树分别具有17,393和20,813个单元，而它们相应的双二次ADF具有457和399个单元。双二次ADF通常要求少于Frisken等的现有技术的双线性表示(“Adaptively Sampled Distance Fields：a General Representaion ofShape for Computer Graphics”，论文集ACM SIGGRAPH2000，pp.249-254，2000)5-20倍的单元。

双二次重构方法

Frisken等使用用于ADF空间层次的四叉树，以及根据经双线性内插在每个单元的四个角处采样的距离来重构每个单元内的距离和梯度。他们建议“可以采用更高次重构方法以便进一步增加压缩，但大多数已经建议减少用于额外努力的回报的观点”。

然而，根据本发明，双线性ADF对表示、绘制、编辑和动画制作字符图示符是不够的。特别地，它们要求太多存储器，数量太多以致于处理低效，以及在非边缘单元中重构的场的质量不足以操作诸如动态模拟。

“有界表面”方法通过要求在离表面，即边缘的有界距离内的非边缘单元通过误差谓项(error predicate)测试，能迫使进一步在非边缘单元中细分，见Perry等的“Kizamu：A System for Sculpting DigitalCharacters”，论文集ACM SIGGRAPH 2001，pp.47-56，2001。尽管那降低了这一有界区域内距离场中的误差，已经发现对双线性ADF来说，那个方法导致单元数量不可接受的增加。

为解决那些局限，用双二次重构方法替代双线性重构方法。典型的图示符的双二次ADF易于要求比双线性ADF少5-20倍的单元。当要求非边缘单元中的精确距离场用于操作，诸如动态模拟和动画制作类型时，所需单元数减少越多。

这一显著的存储减少允许用于典型动画所需的图示符适合现代CPU的芯片上高速缓存。这对处理时间具有显著的效果，因为主要消除了系统存储器存取，易于补偿由较高次重构方法所需的另外的计算。

图3示例说明根据本发明的优选实施例的双二次ADF单元300。双二次ADF中的每个单元包含九个距离值301。根据下面的等式1-3，由这九个距离值重构在点(x，y)302处的距离和梯度。

有多个双二次重构方法变量可用。我们使用沿相同大小的相邻单元的共享边缘，保证C⁰连续性的多变量内插多项式。通过双线性方法，使用误差谓项，能将不同大小的相邻单元之间的距离场的连续性维持到特定的容差。在ADF生成期间，误差谓项控制单元细分，见上述Perry等的论文。

如下确定在点(x，y)302处的距离和梯度，其中在单元坐标中表示x和y，即(x，y)∈[0，1]×[0，1]：

令xv1＝x-0.5以及xv2＝x-1

令yv1＝y-0.5以及yv2＝y-1

令bx1＝2xv1·xv2，bx2＝-4x·xv2以及bx3＝2x·xv1

令by1＝2yv1·yv2，by2＝-4y·yv2以及by3＝2y·yv1

dist＝by1·(bx1·d1+bx2·d2·+bx3·d3)+by2·(bx1·d4+bx2·d5·+bx3·

d6)+by3·(bx1·d7+bx2·d8·+bx3·d9)               (1)

gradx＝-[by1·(4x·(d1-2d2+d3)-3d1-d3+4d2)+by2·(4x·(d4-2d5+d6)-3d4-d6+4d5)+by3·(4x·(d7-2d8+d9)-3d7-d9+4d8)]     (2)

grady＝-[(4y-3)·(bx1·d1+bx2·d2+bx3·d3)-(8y-4)·(bx1·d4+bx2·d5+bx3·d6)+(4y-1)·(bx1·d7+bx2·d8+bx3·d9)]         (3)

使用浮点算法重构距离可能需要～35浮点运算(浮点运算率(flops))，以及使用浮点算法重构梯度可能要求～70浮点运算率。因为本发明的重构方法不包含分支以及图示符能完全驻留在芯片上的高速缓存中，能通过利用专用的CPU指令以及现代CPU的高深的指令流水线，进一步优化这些重构方法。另外，可使用定点算法重构距离和梯度。

用于传输和存储的压缩

线性四叉树

对一些处理，例如冲突检测，要求ADF四叉树的空间层次，但对其他的处理例如基于单元的绘制则不需要，如下所述。

为提供用于ADF图示符的传输和存储的压缩，使用线性四叉树结构，其将双二次ADF存储为叶单元(leaf cell)列表。根据需要，能由叶单元重新生成树结构。

对总共每个单元15个字节，线性ADF四叉树中的每个叶单元包括分别为二字节的单元的x和y位置、一个字节的单元等级、两个字节的单元中央处的距离值、以及分别为一个字节的离中央距离值的八个距离偏差值。

通过从中央距离值减去其相应的样本距离值、按单元大小缩放以便降低量化误差以及截取到八位，从而确定每个距离偏差。每个单元位置的两个字节以及用于单元等级的一个字节在分辨率方面能表示达到2¹⁶×2¹⁶的ADF。这对于表示将以显示器屏幕分辨率绘制的图示符来说不只是适当而已。

通过16位距离值能精确地表示图示符。将八个距离值编码成8位距离偏差比存储这些2字节值的每一个上提供实质的节省。尽管在理论上，这可能导致大的单元的距离场的一些误差，但我们未观测到任何可视恶化。

高分辨率图示符通常要求500-1000个叶单元。无损熵编码能获得另外的35-50％压缩。因此，高分辨率ADF的整个字体能用300-500K字节表示。如果仅要求体型或目标分辨率非常粗糙，例如就蜂窝电话来说，那么能使用要求1/4至1/2的单元的较低分辨率ADF。

这些大小显著地小于灰度级位图字体(其对每个点大小要求每个字体～0.5M字节)，以及在大小上可与微调很好的基于轮廓的字体相比。用于True Type字体的大小的范围从10K字节到10M字节，根据图示符的数量和微调的总量以及微调方法而定。来自MonotypeCorportion的两种微调良好的字体，Arial以及Times New Roman分别要求266K字节和316K字节。

根据轮廓的运动时间生成

根据本发明，以及如下面详细所述，由现有的轮廓或边界描述符，例如Bezier曲线，使用由Perry等的论文所述的平铺生成器(tiledgenerator)，能快速地生成ADF。使用Bezier剪取，能有效地计算到图示符的轮廓或边界的最小距离，见Sederberg等的“GeometricHermite Approximation of Surface Patch Intersecion Curves”，CAGD8(2)，pp.97-144，1991。

在2GHz Pentium IV处理器上，每个图示符生成需要0.04-0.08秒。在约四秒内生成全部字体。因为不需要传统的微调，生成ADF所需的边界描述符基本上小于它们相应的微调对等物。

因此，存储这些最小的轮廓，并根据需求由这些轮廓动态地生成ADF图示符，而不是存储ADF。这些最小轮廓的降低的大小对具有有限存储器的设备以及对在带宽有限的网络上传送图示符的应用来说非常重要。

图10表示用于将二维对象，诸如图示符转换成二维距离场的方法1000。对象1001表示为边界描述符，例如样条的集合，以及填充规则，例如奇-偶规则或非零绕组(non-zero winding)规则。

首先预处理边界描述符集合1010。该预处理细分边界描述符以便降低它们的空间度。还可合并边界描述符以便降低边界描述符集合的基数。当确定无符号的距离时，预处理允许降低对每个位置需要查询的边界描述符的数量，如下所述。

由预处理的边界描述符集合1011重构1020空间层次1021，例如四叉树。初始化1030交点(intersection)1031的高速缓存。交点1031的高速缓存存储边界描述符与距离场的线集，例如水平、垂直和对角线等相交的位置以及交点的方向。这消除了当确定无符号的距离的符号时的冗余计算。通过间隔能对交点排序。

然后，在位置集合处查询1040空间层次1021以便确定在那些位置处的距离集合。使用该距离集合来构造二维距离场1041。查询在每个位置调用距离函数，例如Bezier剪取，以便确定无符号的距离。交点的高速缓存、位置和填充规则能用来确定用于该距离的符号。

经基于分量的字体压缩

通过使用如在字形中的基于分量的表示，能实现用于能包含10,0000或更多图示符的汉字、日语和朝鲜语字体的显著压缩。那种表示将图示符分解成通用的笔划以及字根，即对多个图示符共用的复杂形状，将笔划和字根存储在字体库中，然后在字体绘制引擎中重新组合它们。

因为距离场是隐式表示，使用混合或CSG操作，能容易地组合ADF，从而非常适合经过那种基于分量的方法来压缩。

表示二维距离场中的角

通过双线性或双二次重构方法的针对细节的采样允许ADF表示具有少量距离值的二维对象的边界的相对平滑的部分。然而，在角的附近，距离场具有通过这些重构方法难以很好近似的高的偏差。为精确地表示角附近的距离场，这些ADF需要包含被高度细划分的角的单元，这显著地增加了存储需求。另外，如在Perry等的论文中所述，在ADF生成期间强加的ADF的最大细分度限制了可使用双线性和双二次ADF单元来表示角的精度。

为解决这一问题，本发明提供用于在封闭二维对象，诸如图示符的角的单元内，生成二维距离场的方法1300。

方法1300由二维对象确定边界描述符1311的有序集合1310，以及由边界描述符1311的有序集合识别1320单元内的角点1321。然后，将单元分成两个区1330，第一区最接近角以及第二区最接近对象的边界。方法1300还指定1340重构方法以及采样距离值集合1371，用于重构单元内的距离以及将角点1321、用于为区域定界的线、重构方法以及采样距离值集合1371存储在存储器中1380。

该重构方法根据点所处的区域，确定单元内的该点处的距离。将第一区中用于查询点的距离确定为从该查询点到角点的距离。

为确定第二区中的距离，将边界描述符1311的有序集合分成两个子集，一个包括角点1321前的边界描述符，一个包括在角点1321后的边界描述符。然后扩展1360每个边界描述符的子集以便形成将单元划分成内部和外部部分的扩展曲线。对每个部分，能由从相应的扩展曲线确定1370的采样距离值集合1371重构单元内的距离场。双二次重构方法要求对两个部分的每一个存储九个距离值。

注意两个内部部分的交点形成对象的角。因此，可通过重构到第一内部部分的距离和到第二内部部分的距离，然后选择两个确定的距离的最小值，从而确定第二区中的距离。

能从通过角点的两条定向线来规定这两个区，每条线垂直于边界描述符的两个子集的一个。能通过角点和在角点处相应的边界描述符的相应子集的面向外的法线来指定每条线。当由此定义线时，能通过确定从查询点到角点的矢量的叉积以及面向外的法线，来确定查询点位于线条的哪一侧。位于两条线的外侧上的各点处于第一区中，而位于任一线条的内侧的各点处于第二区中。

字体绘制

在当今的字体绘制引擎中，字体主要表示为轮廓，根据需要缩放轮廓以便匹配所需输出大小。尽管大多数高分辨率打印机使用双层绘制，现代的显示器设备更通用地使用按小的点大小的灰度级绘制或灰度级和双层绘制的组合。

用于光栅化灰度级图示符的通用方法包含缩放和微调它们的轮廓。能将缩放和微调轮廓扫描转换成高分辨率图象，通常大于所需分辨率的4或16倍。然后，通过应用滤波方法，例如盒式滤波，对高分辨率图象进行下采样，以便产生最终灰度级图象。

对于体型，能一次光栅化单个图示符并存储在高速缓存中，作为在预处理步骤中重新使用的灰度级位图。对于图示符的子像素布局的需要可能要求将被光栅化的每个图示符的几个版本。使用用于体型的高速缓存允许在任务，诸如通过Adobe Acrobat PDF文档进行分页(paging)期间，用短的延迟，例如1/2秒进行更高质量的绘制。

然而，在任意路径和动画类型上绘制的类型消除了使用高速缓存，因此，必须根据需要产生。实时绘制需求迫使使用较低分辨率滤波，通常每个像素四个样本以及盒式滤波。这可能导致空间和时间走样。使用驻留在系统存储器中的微调设备字体能降低走样。然而，维持实时帧率对如何使用微调设备字体产生严重约束，例如，不能动态缩放或旋转微调设备字体。

Microsoft有关ClearType的最近研究已经产生用于LCD彩色显示器的特殊处理，包含可寻址彩色子像素，即分量的重复模型，Platt在“Optimal Filtering for Patterned Displays，”IEEE Signal ProcessingLatters，7(7)，pp，179-180，2000描述了用于每个彩色分量的一组感性的最佳滤波器。实际上，最佳滤波器实现为一组三移位盒式滤波器，每个用于一种颜色。

ClearType使用现有技术的基于覆盖的反走样方法以便确定每个像素的每个分量的强度。相比而言，本发明的基于距离场的方法使用距离场来确定每个像素的每个分量的强度，以及使用更少样本来完成它。下文描述的本发明的ADF反走样方法能代替盒式滤波器以便通过对每个像素更少样本来提供更好的最佳滤波器的模拟。

反走样

理解绘制字体中的外观假象需要理解走样。通常，像素由离散分量组成，例如彩色打印机或显示器中的红、绿和蓝分量。在灰度级设备中，像素是单个离散分量。因为像素是离散的，所以绘制到输出设备自然是采样处理。采样率由设备的分辨率而定。除非采样率至少是源信号中的最高(尼奎斯特)频率的两倍，否则采样信号显示出走样。

边缘例如图示符轮廓具有无穷多个频率分量。因此，不能由采样数据精确地表示边缘。边缘的不充分采样导致锯齿状图形，这导致沿运动图象中的采样边缘的蠕动现象。如果源信号也包含空间模型，例如“m”的重复垂直词干或“i”的单个垂直词干，它们的频率分量对采样率来说太高，那么采样数据可显示出漏失、波纹模型以及时间闪烁(temporal flicker)。

为避免走样，必须预先滤波输入信号以便去除采样率所允许的那些频率以上的频率分量。通常，有两种方法来预先滤波。

第一种方法称为分析滤波。在采样前，将空间平均值的一些形式应用于源信号的连续表示。不幸的是，分析滤波通常是不可能的，因为源数据不提供作为用于图象处理的正常情形的连续信号，或因为在滤波器覆盖内确定信号的分析描述太复杂。这是用于除计算机制图中的简单几何形状以外的情形，当然也是用于基于样条的轮廓的情形。

第二种方法称为离散滤波。在这种方法中，通常以高于目标速率的速率采样源信号以便获得超级采样图象。然后，应用离散滤波器以便在下采样图象之前将超极采样图象中的高频降低到目标速率。离散方法称为计算机图形中的常规超级采样。

根据处理预算、硬件考虑和用于输出图象中对比度与平滑度的个人喜好，可以应用各种离散滤波器。通常用来绘制类型的盒式滤波器简单地用它们的算术平均值代替超级采样值的矩阵列并且通常认为在信号处理领域中是低级的。

在另一种方法中，自适应超级采样将用于采样和滤波的可用资源集中在具有较高局部频率分量的图象的区域上。由图象中的局部可变性确定最佳自适应采样。然而，这一技术的有效性受估计图象的局部偏差计算上很昂贵的过程的需要的限制。

由于高频模型的不充分的规则采样，波纹模型对人的视觉系统来说特别令人不愉快。在一般的图象处理中，已经使用随机或抖动采样来解决这一问题。通过随机采样，将样本随机地放在稍微离开它们额定位置。随机采样易于用高频噪声代替波纹模型走样，因此在降低时间走样方面显示出特别有效。

通过基于距离的反走样绘制

由图示符的边缘引起的无穷多频率分量是现有技术字体绘制中导致走样的主要原因。相比而言，根据本发明通过使用2D距离场来表示2D对象，然后采样2D距离场，因为表示C⁰是连续的，所以避免了这种边缘。相反，最大频率取决于图示符本身的空间模型，例如“m”的重复垂直词干或“i”的单个垂直词干。

通过按其2D距离场表示图示符，将分析预滤波有效地应用于图示符。如下所述的用于绘制距离场的反走样方法产生不同于传统的分析预滤波的输出的输出。

通过距离场反走样

图4表示用于按图象序列反走样对象401，例如表示为二维距离场411的图示符410的方法400。每个像素402能包括一个或多个分量404，通常是用于输出设备的“RGB”类型的红、绿和蓝分量。这一方法能使用用于每个像素402的每个分量404的一个或多个样本。该方法400提供基于距离的自适应超级采样、基于距离的自动微调以及基于距离的格栅调整。能在CRT或类似LCD的显示器上将得到的反走样的像素强度绘制为图象的一部分。该方法对绘制运动模糊特别有用。

表示对象401的二维距离场411中的采样点407集合403与每个像素402的每个分量404相关402。由二维距离场411和采样点集合403来确定430距离(D)405。然后，将距离405映射到440像素402的分量404的反走样强度(I)406。

在优选实施例中，用双二次ADF 411表示410图示符401，如上所述。这使得在字体绘制期间应用基于距离的反走样很有效。也能使用其他表示，诸如二维距离图、二维距离对象以及过程距离场。

对图象中的每个像素402的每个分量404，使用如2001年7月31日申请的，名为“Method for Traversing Quadtrees，Octrees andN-Dimensional Bi-trees”的U.S.专利申请号10/209,302中所述的四叉树遍历方法，定位包含分量404的单元，例如叶单元，其内容在此引入以供参考。尽管能与本发明一起使用在现有技术中所知的其他遍历方法，但上述方法无需比较，因此能有效执行。由单元距离值重构分量404的距离并映射440到反走样强度(I)406。

能使用不同映射，包括线性、高斯和∑形函数。选择最佳映射函数是主观的。在一个实施例中，我们的映射是两个函数的组合。第一函数描述如上，第二函数是对比度增强函数。合成这两个函数以便将距离场(D)405映射440到分量404的反走样强度(I)406。

图5将强度501，例如[0，1]的线性映射500表示为距离502的函数。该映射将距离转换成用于像素的每个分量的反走样图象强度。距离在对象内为正以及在对象外为负。不同截止值503和504影响边缘对比度和笔画加权。通过用于显示类型的(-0.75，0.75)和用于本体类型的(-0.5，0.625)的外侧503和内侧504滤波器截止值实现良好结果。

基于最佳距离的自适应超级采样

上述的基于距离的反走样方法由于图示符边缘而减少走样。然而，当图示符分量间的词干宽度或间隔对显示的采样率来说太小时，也会出现走样假象。在这些情况下，应用如下所述的基于距离的自适应超级采样来进一步减少空间和时间走样。

在最佳实施例中，通过本发明的新颖的基于距离的自适应超级采样，使用双二次ADF来提供比现有技术的基于轮廓的表示和基于覆盖的自适应超级采样方法更显著的优点。因为ADF使用针对细节的采样，用较小的叶单元表示具有较高局部偏差的距离场的区域。因此，ADF四叉树的结构提供实现基于最佳距离的自适应采样所需的局部偏差的映射，克服了现有技术中如上所述用于确定局部偏差的自适应超级采样反走样方法中的困难。

对图象中的每个像素402的每个分量404来说，定位包含分量404的单元，以及将分量的滤波半径r内的采样点407的集合403与像素分量404关联420。每个分量的采样点407的数量(spc)由单元到r的相对大小(cellSize)而定。滤波在采样点407处的采样距离以便确定430单个加权平均距离405，然后，将其映射440到像素402的分量404的反走样强度406。

各种滤波器和采样策略都是可能的。在优选实施例中，使用高斯滤波器的通用形式，按W^-12^-3(d/r)2加权每个距离样本，其中d是从采样点到像素的分量的距离，以及W是用于该分量的加权和。通过盒式滤波器、锥形滤波器、负波瓣滤波器以及其他形式的滤波器也能实现类似的结果。

图6A-C表示本发明的采样策略。将样本407放在靠近分量601的同心圆610中，用于有效计算加权以及加权和。使用像素间隔1.3倍的滤波器半径r602以及当cellSize＞r(图6A)时，用1spc采样，当r/2＜cellSize≤r(图6B)时，用5spc采样，以及当cellSize≤r/2(图6C)时，用13spc采样。

除同心圆外，本发明还能使用许多其他的策略来将采样点407与像素分量404关联。本发明的方法对精确采样策略不是特别灵敏。

如下所述的另一自适应采样策略将采样点放在包含于滤波器半径r内的所有单元上。这一策略具有同样良好的结果。

基于单元的反走样

能用软件，使用基于扫描线的光栅化来实现如上所述的距离场反走样方法。另外，能逐个单元，即按对象顺序反走样分成各单元的距离场。基于单元的绘制消除了用于定位包含采样点的单元的树遍历，消除了用于计算单个单元内的距离和梯度的冗余设置，以及减少了单元数据的重复检索，即存储器提取。

另外，因为绘制所需的单元能表示为固定大小、自包含单元的顺序框，即，用于单元内的点的距离和梯度由单元的距离值确定，因此本发明的基于单元的方法能用硬件实现，允许实时绘制。

图7表示用于反走样目标701的方法700，例如按对象顺序表示为二维距离场711的图示符710。方法700提供自适应的基于距离的超级采样，基于距离的自动微调，以及基于距离的格栅调整。能在类似CRT和LCD显示器上将合成的反走样的像素强度显示为图象的一部分。该方法对绘制运动模糊特别有用。当按空间层次组织二维距离场711的各单元时，能使用MIP映射以便减少所需的距离采样的数量。

将二维距离场711分成各单元712。在优选实施例中，使用双二次、自适应采样距离场，每个单元的大小由二维距离场的局部偏差而定。每个单元包括用于在单元内重构二维距离场的方法(M)713。识别将要绘制的包含距离场的区域(虚线)722的单元集合721。

使用区域722来定位730与该区域有关的像素731的集合。指定740在像素集合731内用于每个像素的分量集合741。然后，通过单元集合中的距离，确定用于每个像素的每个分量的反走样强度751。在这里，由单元集合重构距离。然后，将距离映射到反走样强度，如上所述。

在一个实施例中，能通过定位单元集合内接近像素的分量的单个采样点，以及在单个采样点处由单元集合重构距离来确定距离。在优选实施例中，使用二次自适应采样距离场，通过小于用于基于距离的自适应超级采样的滤波半径的单元的特殊处理，扩充该方法。因为在距离场中有高的偏差的地方出现小单元，在将距离映射到强度前，可预先滤波接近这些单元的像素中的距离。

初始化元素的合成缓冲器，其中每个元素对应于像素集合的每个像素的分量。可独立地处理单元集合中每个单元。在优选实施例中，每个元素包含均初始化为零的加权距离和累积加权。当处理一个单元时，按对应于存在于单元内或单元中心的滤波半径内的像素分量的缓冲器元件递增这些加权距离和累积加权。

在处理所有单元后，按用于每个像素的每个分量的累积加权，规格化加权距离以便产生距离，然后将距离映射到反走样分量强度。在优选实施例中，使用如上所述，同样的高斯加权和滤波半径。

迄今，所述本发明的基于单元的绘制总是处理单元集合中的每个叶单元，而与每个单元到滤波半径的相对大小无关。理论上，这提供了基于距离的最佳自适应的超级采样。实际上，能将ADF四叉树用作MIP映射以便减少单元的数量。

ADF四叉树结构允许用它们的祖先替换小的叶单元，按一些预定的单元大小有效地截取四叉树。只要这一单元大小小于或等于像素间间隔的1/4，在基于距离的自适应超级采样结果中没有视觉恶化。这减少了绘制区域的单元数。

处理像素分量

像素包括一个或多个分量。例如，有关典型的CRT或LCD彩色监视器的像素包含红、绿和蓝分量。在本发明中，当像素包含多个分量时，如上所述，能单独地处理它们，或作为单个分量处理。当将多个分量作为单个分量处理时，能由单个分量的反走样强度确定像素的颜色和α值。

将多个分量作为单个分量处理有两个原因。首先，它减少了绘制次数。第二，当不能单独地寻址多个分量时或当各个分量的相对位置未知时，各个分量的单独处理是不可能的。

当显示设备，诸如LCD具有可寻址像素分量时，在现有技术中，单独地处理多个分量能增加设备的有效分辨率是公知的。本发明能使用这些设备的这一特征来提供具有比现有技术更高质量的基于距离的反走样。

动画制作二维对象

图12表示根据动画脚本1202，将对象1201动画制作为帧序列的方法1200的流程图。动画脚本1202控制帧序列中每个帧的对象的状态，例如对象的位置、大小、方向和变形。对象表示为二维距离场。根据动画脚本1202，更新1210用于帧序列1221中的每个帧的对象1201的姿势1211。使用更新的姿势1211和基于距离的反走样绘制方法1212绘制对象1201。

能从对象的不同表示，例如对象的轮廓描述或对象的位图描述来获得表示对象1201的二维距离场。

通过将不同操作应用于对象，包括刚体变换、自由形状变形、软体冲击变形、阶层集合方法、微粒模拟以及改变其绘制属性，可执行用于特定对象1201的姿势1211的更新1210。

当绘制1220对象时，将表示对象的二维距离场中的采样点集合与帧序列1221中的帧中的像素的分量相关联。通过由二维距离场和采样点集合来确定距离，能将距离映射到像素的分量的反走样强度上。

在优选实施例中，将表示对象1201的二维距离场划分成各单元，每个单元包括用于在单元内重构二维距离场的方法。为在这一实例中绘制1220，识别表示包含有将绘制的二维距离场的区域的对象1201的二维距离场的单元集合，以及定位与该区域相关的像素集合。指定用于像素集合中每个像素的分量集合。由单元集合确定用于像素的每个分量的距离，以及将距离映射到像素的分量的反走样强度，以便确定用于像素集合中的每个像素的每个分量的反走样强度。

基于距离的自动微调

标准字体表示中的微调是耗时的手动处理，其中，类型设计者和微调专家产生用于使各个图示符更好地适应于像素格栅的一套规则。良好的微调以良好间隔的、具有很好对比度并且在外观上统一的小字号产生图示符。

这些规则提供：具有相同对比度分布的垂直词干，具有最高可能对比度的左和底边缘、对话框和图示符的淡圆部分的图示符具有用于将可视结构传送到眼睛的充分的对比度，以及绑在一起并提供由人眼俘获到的足够加重的衬线，见Hersch等“Perceptually TunedGeneration of Grayscale Fonts”，IEEE CG&A，Nov，pp 78-89，1995。

注意，现有技术滤波方法产生模糊字符以及将不同对比度配置文件指定到不同字符部分，从而违反类型设计的重要规则。为克服这些限制，对每个字体的每个图示符开发了微调。现有技术微调方法存在许多问题：它们的开发是劳动密集的、绘制慢并且复杂，从而排除了硬件实现方式。

对基于轮廓的字体，通过微调绘制是三步处理。第一，缩放图示符的轮廓并与像素格栅对准。第二，修改轮廓以便控制词干、条和衬线的对比度以及增加非常淡的部分和弧的厚度。第三，在通过滤波进行下采样后，进行对修改的轮廓超级采样。

尽管如上所述的本发明的未微调的基于距离的反走样绘制方法与使用微调的现有技术的字体绘制方法具有相当可比性，已知感性微调能以小字号提高阅读舒适。

因此，如图8所示，本发明利用距离场来提供用于以小的点大小绘制图示符的基于距离的自动微调。微调中的第一步810是缩放距离场并将其与像素格栅对齐。这能由指定或导出的字体规格，例如帽高、X高以及基线的位置来自动完成。

在应用格栅调整的这一形式后，使用距离场以及其梯度场来提供感性微调。

在一个实施例中，使用距离场的梯度的方向来检测820对象的左和底边缘上的像素。通过使这些像素变暗830以及使相反边缘上的像素变亮840，实现左和底边缘上的更高对比度，而不改变外在的笔画加权。这能通过减少和增加相应的像素强度来实现。

在另一实施例中，使用梯度场来提供用于对话词干和淡弧的更好对比度。我们注意到当像素位于图示符的淡区域上或其附近时，在像素的任何一侧上的相邻元素具有相反的梯度方向，即，它们的点乘积为负。通过检测梯度方向中的突然变化，可使这些淡区域上的像素变暗850。

这些仅是如何使用距离场来自动提供感性微调的两个例子。还能使用距离场来提供最佳字符间隔和均匀笔画加权。

产生和编辑字体

存在用于设计字体的两个基本方法。第一是手动。在这里，用手画出图示符、数字化，然后将轮廓调整成数字化位图。第二是通过计算机。

在后一情况下，有三种工具可用。能将直接可视工具用于曲线操作。过程设计工具通过执行过程指令构成图示符的形状。过程定义形状的轮廓并填充它，或通过许多属性，包括几何结构和方位来定义用笔尖划出的路径。基于分量的设计工具允许设计者构建基本分量，诸如词干、弧以及其他循环形状，然后将这些分量组合以便产生图示符。

本发明使用造型编辑器来提供基于笔画的设计。这是2D副本到3D雕刻，如在2001年3月16日提交的U.S.专利申请号09/810,261，“System and Method for Sculpting Digital Models”中所述，其内容在此引入以供参考。能交互地实现笔划或能手写以便模拟可编程设计工具。

也能利用使用了与在Adobe Illustrator中类似的Bezier曲线操作工具的基于曲线的设计。基于曲线的设计能与用于将轮廓转换成距离场以及将距离场转换成轮廓的方法相结合以便提供设计范例之间的无缝接口。

基于分量的设计使用隐式距离场上的CSG和混合操作。这允许单独地设计分量以及在编辑期间或在绘制期间相组合。

本发明还提供用于由模拟和数字字体正本自动地生成ADF的方法。

对基于分量的设计，本发明的字体编辑器使用四叉树操作提供有效地反映和旋转ADF的能力，以便模型化图示符所共有的对称性。另外的特征包括ADF缩放、变换以及操作以便组合多个ADF，例如CSG和混合。

对基于笔画的设计，本发明提供具有几何配置文件的雕刻工具以便模拟笔尖。所模拟的笔尖的方位和大小能沿笔画改变以便模仿书法。

图9表示用于由笔画生成二维距离场931的方法900。在笔划期间采样笔状态，笔状态包括在笔划期间的笔的位置。这一笔状态也可以包括方向和几何结构。从笔状态样本901，沿笔划生成910笔状态的顺序列表911。然后，由笔状态的有序列表产生920边界描述符921集合。最后，由边界描述符集合921生成二维距离场931。

在优选实施例中，边界描述符921是诸如立方Bezier曲线的曲线。

在优选实施例中，应用曲线拟合过程以便通过用户规定的精确度来将最小G2连续曲线集合拟合到笔的路径。还使用工具大小和方向，由这一路径生成另外两个偏移点的有序列表，以及将曲线拟合到这些偏移点以便生成笔划轮廓。轮廓曲线处于空间层次，用于有效处理。使用平铺生成器，由这一层次生成二维ADF，见2001年3月16日提交的U.S.专利申请No.09/810,983，其内容在此引入以供参考。

使用Bezier剪取有效地计算到轮廓的最小距离。将笔划转换成ADF，而对用户没有感性延迟。对于曲线操作，本发明提供Bezier曲线编辑器。

如图11所示，本发明还提供将距离场转换成边界描述符，例如Bezier曲线的能力，以便提供所有三个设计范例之间的无缝接口。

在优选实施例中，使用双二次ADF，其中这一转换使用用于快速邻近搜索的ADF层次来遍历各叶单元，沿ADF的0值等值线生成各点的有序列表，然后如下参考图11所述，拟合曲线以便生成边界描述符。

与现有技术(其中，由点的列表计算边界描述符误差)相比，本发明直接由距离场计算计算边界描述符误差。本发明特别注意到锐角转角。本发明的方法快到足以允许用户在范例之间无缝切换，而没有可觉察到的延迟。

图11表示用于将二维距离场1101转换成边界描述符集1131的方法1100。首先，选择1110二维距离场1101的等值线1111，例如具有零值的距离或一些偏移量。

接着，由等值线1111和二维距离场1101生成1120点的有序列表1121。在优选实施例中，使用二次自适应采样距离场，这一步骤使用邻近搜索技术，顺序地访问自适应采样距离场1101的相邻各单元。该搜索技术利用自适应采样距离场1101的空间层次以便沿等值线1111有效地定位下一邻近值。

在另一实施例中，通过选择ADF 1101中的边界单元，用有序点集合播种(seeding)每个边界单元，以及使用ADF 1101的距离场和梯度场，将每个点移动到ADF 1101的等值线1111，从而生成1120点的有序集合1121。

然后，初始化1130边界描述符集合1131以便调整有序点列表1121。通过结合有序点列表1121的相邻点，初始化边界描述符1131以便形成构成初始边界描述符1131的线段集合。

在另一实施例中，通过定位拐角点、将有序点列表细分成由拐角点定界的各段、以及确定段边界描述符以便调整每个段，从而初始化1130边界描述符集合1131。段边界描述符的并集形成初始边界描述符1131。

通过测量由距离场确定的曲率可定位拐角点。在优选实施例中(其中距离场是双二次ADF)，用ADF中的小单元表示高曲率的区域，因此，通过使用ADF单元大小来定位拐角点。

只要初始化1130边界描述符1131，更新1140边界描述符1131。更新1140通过由等值线重构距离场和测量边界描述符的平均或最大偏差，从而确定用于每个边界描述符的误差。

更新1140边界描述符1131，直到用于每个边界描述符的误差可接受，或预定时间已过去，或边界描述符集合1131的基数最小为止。

为了包含以非数字形式(即作为模拟原图)，或以作为位图的数字形式(即作为数字原图)存储的字体的当前遗产(legacy)，本发明的编辑系统提供用于由高分辨率二值位图生成ADF的方法。

首先扫描模拟原图以便以高于目标ADF分辨率至少四倍的分辨率产生二值数字原图，例如4096×4096数字原图适合于当前的显示分辨率以及显示大小。然后将精确的欧几里德距离变换应用于位图以便生成表示图示符的规则采样场。

然后，使用平铺生成器，由这一规则采样距离场生成ADF。在2GHz Pentium IV处理器上，由位图到ADF的转换每个图示符需要～10秒。

为从现有技术图示符的描述符变换成距离场(其中用边界描述符集合描述图示符)，应用参考图10所述的方法。

用于动态印刷术的计算衬底

还能将本发明的ADF图示符框架的距离场和空间层次属性用于2D对象，例如图示符、公司徽标，或任何2D形状的计算机模拟。例如，两种属性能用在冲突检测和避免中，用于计算互相贯穿体之间的力，以及用于模拟软体变形。

可利用使用有符号的距离场的阶层集合(level set)方法来模拟许多效果，诸如熔化和流体动力。ADF是能被有效地查询以便计算距离值和梯度、用于上述列出的方法所需的两个重要计算的简洁的隐式表示。

比较起来，由正运动或变形的轮廓确定距离值和梯度对于实时交互作用的软件是不实际的，见Hoff等，“Fast and Simple 2D GeometricProximity Queries Using Graphics Hardware”Proc.Interactive 3DGraphics′01，2001。Hoff等的论文使用图形硬件在飞行中产生规则的采样2D距离场，用于变形按线段接近的曲线。

距离场的隐式特性允许复杂的拓扑改变，诸如很难通过基于轮廓的字体模拟的表面偏移。另外，能使用距离场来提供动画对象的非写实(photorealistic)绘制以便增加艺术效果。

本发明的效果

本发明提供用于表示、绘制、编辑和动画制作字符图示符、公司标志或任何其他二维对象的新颖框架。在优选实施例中，本发明使用二维双二次ADF来表示二维对象。该双二次重构方法提供存储器使用和计算负担之间的最佳平衡。

本发明包括用于在包围二维对象的拐角的单元内生成二维距离场的方法。该方法比现有技术提供存储器需求的显著降低以及精确度的显著改进。

本发明的基于距离的反走样绘制方法使用每个像素的单个未微调距离样本，提供比用在现有技术中的超级采样方法更好的反走样。

本发明的基于距离的方法利用ADF的空间层次来提供导致超级空间和时间反走样的有效的最佳基于距离的自适应超级采样。本发明的方法还提供用于基于距离的自动微调、用于基于距离的格栅调整、用于统一三个通用数字字体设计范例、以及用于生成用于动态印刷术的多种特殊效果的计算衬底。

尽管已经通过优选实施例的例子描述了本发明，将理解到能在本发明的精神和范围内做出各种其他适应变化和改进。因此，附后权利要求的目的是覆盖落在本发明的真实精神和范围内的所有这些变化和改进。

Claims (16)

1.一种用于将二维对象转换成二维距离场的方法，所述对象表示为边界描述符的集合和填充规则，该方法包括：

预处理边界描述符集合；

由预处理的边界描述符集合构成空间层次；

初始化交点的高速缓存；以及

查询一组位置处的空间层次以便确定所述位置处的距离集合，所述距离集合用来构成二维距离场，所述查询进一步包括：

调用在每个位置处的距离函数以便确定无符号距离；以及

使用所述交点的高速缓存、所述位置和所述填充规则，确定所述无符号距离的符号。

2.如权利要求1所述的方法，其中，所述边界描述符集合是样条集合。

3.如权利要求1所述的方法，其中，所述填充规则是偶-奇规则。

4.如权利要求1所述的方法，其中，所述填充规则是非零绕组规则。

5.如权利要求1所述的方法，其中，所述预处理进一步包括：

细分所述边界描述符以便减少它们的空间广度。

6.如权利要求1所述的方法，其中，所述预处理进一步包括：

合并所述边界描述符以便减少所述边界描述符集合的基数。

7.如权利要求1所述的方法，其中，所述空间层次是四叉树。

8.如权利要求1所述的方法，其中，所述空间层次是kd-树。

9.如权利要求1所述的方法，其中，所述距离函数使用Bezier剪取来确定最小无符号距离。

10.如权利要求1所述的方法，其中，所述交点的高速缓存用于存储所述边界描述符与线集合相交的位置。

11.如权利要求10所述的方法，其中，所述线集合的方向为水平。

12.如权利要求10所述的方法，其中，所述线集合的方向为垂直。

13.如权利要求10所述的方法，其中，所述二维距离场是自适应采样距离场，以及所述线集合位于所述自适应采样距离场的格栅线上。

14.如权利要求1所述的方法，其中，确定所述无符号距离的符号进一步包括：

选择通过所述位置的线；

如果所述线在所述高速缓存中，则检索用于该线的线交点；

确定用于所述线与所述边界描述符集合的线交点，以及，如果所述线不在所述高速缓存中，则将用于所述线的线交点存储在所述高速缓存中；以及

使用用于所述线的线交点、位置和填充规则来确定无符号距离的符号。

15.如权利要求14所述的方法，其中，用于所述线的线交点包括所述线与所述边界描述符集合的交点的排序的间隔。

16.如权利要求14所述的方法，其中，用于所述线的线交点包括用于每个交点的方向。

Images