根據代表對象的二維距離場確定一個象素成分的反鋸齒強度的方法及裝置的製作方法

2023-12-06 16:15:51 2

專利名稱：根據代表對象的二維距離場確定一個象素成分的反鋸齒強度的方法及裝置的製作方法
技術領域：
本發明主要涉及計算機圖形學領域，並且尤其涉及由距離場表示的二維對象的渲染。
背景技術：
在計算機圖形學領域，二維對象的渲染(rendering)是十分重要的。二維對象，如字符形狀、企業標誌以及包含在文檔中的圖例元素，都是作為靜態圖像或是作為組成一個動畫的一系列幀進行渲染的。二維對象有多種表示方法，並且常常會出現這樣一種情況，即對於特定的操作如渲染與編輯，一種表示方法要優於其他的表示方法。在這種情況下，就要進行從一種形式到另一種形式的轉換。
儘管此處我們關注數字的字型(type)，這可能是最常見最重要的二維對象了，但是下列說明適用於所有類型的二維對象。
我們從數字字型的一些基礎背景開始。一種典型的拉丁字體族，如Times New Roman或Arial，包括一組字體(font)，比如常規、斜體、粗體或粗斜體。每種字體包括一組單獨的字符形狀，稱為字形(glyphs)。每種字形由它不同的設計風格來區分，比如基本的幾何形狀、筆畫濃度、襯線、連筆形式、布局以及輪廓、薄-厚筆畫的比例和尺寸的數值。
有多種方法可用來表示字體，包括位圖、輪廓線，比如Type1[Adobe Systems，Inc.1990]和Truetype[Apple Computer，Inc.1990]，以及過程字體，比如Knuth的Metafont，其中輪廓線起主導作用。基於輪廓線的表示方法被Mass.Cambridge的Bitstream Inc.、Calif.Mountain View的Adobe System，Inc.、Calif.Cupertino的AppleComputer，Inc.、Wash.Bellevue的Microsoft Corporation、德國Hamburg的URW以及Mass Wilmington的Agfa Compugraphic採用並推廣。
由Hersch所著並發表於Cambridge University Press，1993的「Visual and Technical Aspects of Type(字體的視覺與技術觀點)」以及由Knuth所著並發表於Digital Press，Bedford，MA 1979的「TEXand METAFONTNew Directions in Typesetting(TEX與元字形排版的新方向)」中，包含了大量關於字體的歷史與科學的評論。
具有特殊重要性的是兩類字型尺寸正文字型尺寸和顯示字型尺寸。正文字型的字體以相對較小的磅值渲染，如14磅或更小，並且被使用在一個文檔的主體(正文)部分中，就像在本段落中一樣。正文字型要求高質量的渲染，以獲得清晰度和閱讀舒適度。正文字型的尺寸、字樣以及基線方向在單篇文檔中很少改變。
顯示字型的字體以相對較大的磅值渲染，如36磅或更高，並且被用於標題、頭條、以及為表達情緒或引起注意的設計及廣告中。與正文字型不同，顯示字型注重美觀，缺少空域及時域上的鋸齒(aliasing)是重要的，而非清晰度，其中對比度比反鋸齒(antialising)更重要。用來表示及渲染字型的框架應該能夠處理好具有相互衝突的需求的這兩種類型，這一點是至關重要的。
字型可以以二值、灰度或彩色的形式被提供給一個輸出裝置，比如印表機或顯示器。某些渲染引擎為非常小的字型尺寸使用二值渲染，以達到較好的對比度。然而，具有良好提示的灰度字體是同樣清楚可辨別的。
「提示」是與每種字形存儲在一起的一組規則或工序，用以規定在渲染過程中如何修改字形的輪廓線，以保持對稱性、筆畫磅值之類的特性，以及一種字體中所有字形的統一外觀。
儘管人們已經嘗試設計自動和半自動的提示系統，但是提示過程仍然是新字體設計以及轉換現有字體以供低解析度顯示設備使用中的主要瓶頸。另外，解釋提示規則的複雜性導致不能運用硬體進行字體渲染。缺少硬體支持，就不得不在軟體光柵化的過程中作出折衷，比如每個象素使用較少的樣值，特別是在實時地生成動態字型(animatedtype)時。
灰度字體渲染通常包含某些形式的反鋸齒。反鋸齒(Antialising)是一種處理過程，它能消除二值字體中出現的鋸齒邊緣或階梯效應。儘管有多種字體渲染引擎都適合使用，但是大部分都會在網格裝配及提示之後以每象素4或16個採樣值進行過採樣，隨後分別以2×2或4×4的箱式濾波器進行下採樣。
基本的濾波，如箱式濾波(box filtering)，由渲染速度的需要來決定其必要性。但是，即使是那種方法，對於實時渲染(如動態字型所需的那樣)而言常常也是太慢的，從而經過渲染的字形會帶有空域或時域上的鋸齒。
印刷術的兩個重要發展趨勢揭示了現有技術的字體表示方法的某些固有局限性，由此提出了變革的需求。
第一種趨勢是越來越多地強調在屏幕上閱讀文本，這種趨勢是由計算機在辦公室中的主角地位、家庭網際網路瀏覽普及程度的提高以及PDA與其他手持電子設備的廣泛使用共同引起的。這些顯示設備通常具有每英寸72-100點的解析度，這種解析度顯著低於印刷設備的解析度。
在對字型進行光柵化時，這種低解析度需要特殊對待以保證閱讀舒適度和清晰度，比如Microsoft與Bitstream公司在他們各自的ClearType與FontFusion技術中投入使用的資源就證明了這一點。
第二種趨勢是動態字型或動態印刷術的使用。動態字型被用來表達情感、增添趣味性以及在視覺上吸引讀者的注意。動態字型的重要性由它在電視及網際網路廣告中的廣泛使用即可見一斑。
不幸的是，傳統的基於輪廓線的字體在這兩個領域內都有局限性。在低解析度顯示器上渲染字體需要仔細對待，以便平衡良好對比度以及降低空域和/或時域鋸齒的要求，前者是清晰度所需，後者則是閱讀舒適度所需。
如上所述，基於輪廓線的字體通常會被加入提示來向渲染引擎提供指示，從而獲得最佳外觀。字體提示是煞費勞力且成本高昂的。例如，為日文或中文字體開發一套具有完善提示的字體樣式可能要耗費數年時間，這兩種字體中可能包含了超過一萬種的字形。由於提示的焦點在於改善正文字型的渲染質量，因此這種提示對於放置在任意路徑上的字型以及對於動態字型來說將會是效果不佳的。
儘管高質量的濾波可以被用來反鋸齒靜態文檔中的灰度字型，這種文檔中只含有有限數量的字體尺寸和字體樣式，但是在動態字型中進行濾波往往會受到實時渲染要求的限制。

發明內容
本發明提供了根據代表對象的二維距離場確定一個象素成分的反鋸齒強度的方法及裝置。所述二維距離場中的一組樣點與所述的象素成分相關聯。根據所述的二維距離場以及所述的樣點組確定一個距離，並將該距離映射到所述象素成分的反鋸齒強度。
在本發明的一方面內容中，所述的二維距離場是一種規則採樣的距離場。
在本發明的另一方面內容中，所述的二維距離場是一種自適應採樣的距離場。
在本發明的另一方面內容中，所述的樣點組由一個單個採樣構成，以提供所述對象的高效高質量反鋸齒。
在本發明的另一方面內容中，基於距離的自適應過採樣提供了所述對象的最優、高效、高質量反鋸齒。
在本發明的另一方面內容中，基於距離的自動提示提供了所述對象的高質量反鋸齒。
在本發明的另一方面內容中，基於距離的網格裝配提供了所述對象的高質量反鋸齒。
在本發明的另一方面內容中，所述象素成分的獨立可尋址性被充分利用，以提供所述對象反鋸齒的有效解析度的提高。


圖1A與1B示出了現有技術下字形的距離場表示的框圖；圖2A與2B根據本發明的優選實施例示出了距離場表示的框圖；圖3根據本發明的優選實施例示出了距離場的一個雙二次單元的框圖；圖4根據本發明示出了一種用來按圖像順序反鋸齒一個對象的方法的流程圖；圖5示出了本發明所使用的一種線性濾波器的圖；圖6A、6B及6C示出了一個象素成分附近的採樣的示意圖；圖7根據本發明示出了一種用來按對象順序反鋸齒一個對象的方法的流程圖；圖8根據本發明示出了一種用於基於距離的自動提示的方法的流程圖；圖9根據本發明示出了一種用來將一個筆畫轉換成一個距離場的方法的流程圖；圖10根據本發明示出了用來將一個二維對象轉換成一個距離場的方法的流程圖；圖11根據本發明示出了用來將一個距離場轉換成邊界描述符的方法的流程圖；圖12根據本發明示出了用來動態化一個對象的方法的流程圖；以及圖13根據本發明示出了用來生成一個包含有一個二維對象的一角的單元中的二維距離場的方法的流程圖。
具體實施例方式
字形的距離場表示我們的發明將一個閉合的二維形狀S——如字形、企業標誌或一個對象的任何數位化表示形式——表示為一個二維的有符號距離場D。為了我們的說明目的，我們藉助於字形。
通俗地說，一種字形的距離場度量了從場中任意一點到字形邊緣的最短距離，其中如果所述點位於所述字形之外，那麼所述距離的符號就是負的，而如果所述點位於字形之內，則所述距離的符號就是正的。邊緣上的點距離為零。
正式地說，距離場是作用於所有p∈R2的一種映射DR2→R，從而使得D(p)＝sign(p)·min{‖p-q‖對於所有位於零等值面上的點q，即S的邊緣}，sign(p)＝{-1，如果p在S之外；+1，如果p在S之內}，並且‖·‖為歐幾裡得範數。
現有技術基於覆蓋的渲染方法使用單個離散的樣點來表示每個象素，即使在所述的樣點充分靠近輪廓線時，這種方法也可能完全弄錯字形。被渲染的字形有鋸齒狀邊緣以及漏失的部分，這兩者都是空域鋸齒的表現形式。如果所述的字形被動態化，那麼時域鋸齒就會導致閃爍的輪廓和鋸齒狀的邊緣，它們在運動期間就像「蠕動」一樣。對每個象素採用額外的樣點以形成一種反鋸齒的渲染，這樣做可以消除這些鋸齒效應，但是要達到可接受的結果需要許多樣點。
相反，即使當樣點位於形狀之外時，根據我們的發明的連續採樣距離值也能表示出字形的相似性。實際上，單個樣點值可以被用來估算有多少字形位於以各個象素為中心的濾波器覆蓋範圍之內。
另外，由於距離場變化平緩，即它是C0連續的，因此採樣值會隨字形運動而緩慢變化，從而減少了時域鋸齒成分。
距離場還擁有其他優點。由於它們是一種隱式的表示方法，因此它們享有隱函數的好處。具體地說，距離場提供了一種用於設計字體的直觀界面。例如，字形的個別部分，如直筆、橫筆、弧形筆畫或襯線可以分別獨立設計。在設計之後，所述的部分就可以利用隱式組合方法組合在一起，以構成相同字體樣式的不同字形。
距離場在動態排版術或動態字型領域還能提供許多(好處)，因為距離場所提供的信息對於模擬對象間的互動是非常重要的。
在一種優選實施例中，我們採用自適應採樣的距離場，即ADF，參見美國專利6396492號，「Detail-directed hierarchical distance fields(面向細節的分級距離場)」，該專利由Frisken、Perry及Jones提交，此處通過引用包含進來。
ADF是距離場的有效數字表示法。ADF運用面向細節的採樣以減少表示距離場所需的樣點數。所述的樣點被存儲在單元的空域分級結構如四叉樹中，以便進行高效的處理。另外，ADF還提供了用來根據採樣值重建距離場的方法。
面向細節的或自適應的採樣根據場內的局部變化對距離場採樣當局部變動大時使用更多的樣點，而在局部變動小時使用較少的樣點。與常規採樣的距離場以及三色四叉樹相比，自適應採樣顯著降低了對存儲器的需求，常規採樣以均勻的速率採樣整個距離場，而三色四叉樹則總是在邊緣附近以最高速率採樣。
圖1A-1B對用三色四叉樹表示Times Roman的『a』和『D』所需的單元數量以及用圖2A-2B中的雙二次ADF表示相同精度所需的單元數量進行了比較。單元數量與存儲需求直接相關。兩種四叉樹都具有相當於512×512的距離值圖像的解析度。用於表示『a』和『D』的三色四叉樹分別具有17393和20813個單元，而相應的雙二次ADF只有457和399個單元。雙二次ADF通常所需的單元數比Frisken等人提出的現有技術的雙線性表示方法少5-20倍，這一點在「AdaptivelySampled Distance Fieldsa General Representation of Shape forComputer Graphics(自適應採樣的距離場用於計算機圖形學的通用圖形表示法)」中有所說明，該文發表於Proceedings ACM SIGGRAPH2000，pp.249-254，2000。
雙二次重建方法Frisken等人利用四叉樹作為ADF空域分級結構，並根據在每個單元的四個角上採樣的距離、通過雙線性內插在每個單元內重建距離及梯度。他們提出「更高階的重建方法可以被用來進一步提高壓縮率，但是數字已經表明額外努力所換得的回報開始減小」。
然而，雙線性ADF對於本發明所述的表現、渲染、編輯以及動態化字符字形而言還是不夠用的。具體地說，它們需要過多的存儲器，處理效率太低，並且在非邊緣單元中的重建場的質量對動態模擬之類的操作來說是不夠的。
一種「有界表面」方法可以強制在非邊緣單元中進行進一步的細分，它要求處在離所述表面(即邊緣)有界距離內的非邊緣單元通過一項誤差判定測試，參見Perry等人所著的「KizamuA System forSculpting Digital Characters(Kizamu一種用於塑造數字字符的系統)」，該文發表於Proceedings ACM SIGGRAPH 2001，pp.47-56，2001。儘管上述方法減少了該有界區域內距離場的誤差，但我們發現對於雙線性ADF來說，那種方法會導致無法容忍的單元數量增加。
為了應對那些局限性，我們用雙二次重建方法替代了雙線性重建方法。典型字形的雙二次ADF所需要的單元比雙線性ADF少5-20倍。當我們要求在非邊緣單元中得到精確的距離場以便進行動態模擬和動態化字型這樣的操作時，所需單元數就出現了更高的減少量。
這種顯著的存儲量減少使得一個典型動畫所需的字形能夠被存入現代CPU的片上高速緩存中。這對處理時間有著驚人的影響，因為對系統存儲器的訪問基本上被排除了，這樣就輕易地補償了高階重建方法所需的額外計算。
圖3根據我們的優選實施例示出了一個雙二次ADF單元300。雙二次ADF中的每個單元包含9個距離值301。點(x，y)302處的距離與梯度都可以根據下列方程1-3由這9個距離值重建出來。
有多種雙二次重建方法可供使用。我們採用二變量內插多項式，它能保證沿同樣大小的相鄰單元的公共邊緣的C0連續性。與使用雙線性方法一樣，不同大小的相鄰單元之間距離場的連續性是利用誤差判定來維持在一個規定容限內的。所述的誤差判定在ADF生成期間控制單元的細分，參見上述Perry等人的著作。
點(x，y)302處的距離與梯度如下確定，其中x和y都是用單元坐標表示的，即(x，y)∈
×令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·yv1dist＝by1·(bx1·d1+bx2·d2+bx3·d3)+by2·(bx1·d4+bx2·d5+bx3·d6)+ (1)by3·(bx1·d7+bx2·d8+bx3·d9)gradx＝-[by1·(4x·(d1-2d2+d3)-3d1-d3+4d2)+by2·(4x·(d4-2d5+d6)-3d4-d6+4d5)+ (2)by3·(4x·(d7-2d8+d9)-3d7-d9+4d8)]grady＝-[(4y-3)·(bx1·d1+bx2·d2+bx3·d3)-(8y-4)·(bx1·d4+bx2·d5+bx3·d6)+ (3)(4y-1)·(bx1·d7+bx2·d8+bx3·d9)]利用浮點運算重建一個距離可能需要約35次浮點操作(flops)，而利用浮點運算重建一個梯度則需要約70flops。由於我們的重建方法不包含分支，並且字形可以完全存放在一個片上高速緩存中，因此我們就可以通過利用特殊的CPU指令以及現代CPU的深指令流水線來進一步優化這些重建方法。另外，我們還可以利用定點運算來重建距離與梯度。
用於傳輸及存儲的壓縮線性四叉樹ADF四叉樹的空域分級結構是某些處理過程(如衝突檢測)所需要的，但是對於其他處理-比如下文中將要說明的基於單元的渲染來說卻不是必要的。
要為ADF字形的傳輸及存儲提供壓縮，我們採用一種線性四叉樹結構，該結構將我們的雙四叉樹ADF存儲為一個葉單元列表。該樹狀結構可以根據需要由所述的葉單元恢復出來。
線性ADF四叉樹中的每個葉單元中包括該單元的x和y坐標，每個坐標用2個字節表示，該單元的級別，用1個字節表示，單元中心處的距離值，用2個字節表示，以及8個離開中心的距離偏移量，各用1個字節表示，每個單元總共15個字節。
各個距離偏移量是通過從中心距離值中減去其對應樣點的距離值、用單元大小進行比例縮放以減小量化誤差、再截取成8個比特，從而得到的。表示每個單元位置的兩個字節以及表示單元級別的一個字節可以以高達216×216的解析度表示ADF。這對於表示在顯示屏解析度下渲染的字形來說是足夠了。
字形可以用16比特的距離值精確表示。將8個距離值編碼成8比特的距離偏移量比各用兩個字節存儲這些值要節省的多。儘管在理論上，這樣做可能會導致大單元的距離場中出現一些誤差，但我們還未發現任何視覺效果上的退化。
一個高解析度的字形通常需要500-1000個葉單元。無損熵編碼可以額外得到35-50％的壓縮。因此，高解析度ADF的整個字體樣式可以用300-500Kbytes表示出來。如果只需要正文字型或者目標解析度比較粗糙，就像用於行動電話的情況，那麼就可以使用僅需1/4至1/2單元數的低解析度ADF。
這些存儲量顯著小於灰度位圖字體，並且與帶有良好提示的基於輪廓線的字體的存儲量相當，所述灰度位圖字體的每種字體樣式的每個點尺寸需要約0.5Mbyes。TrueType字體的存儲量從數十Kbytes到數十Mbytes不等，取決於字形數量以及提示方法的數量。Arial和Times New Roman是Monotype Corporation的兩種具有良好提示的字體，它們分別需要266Kbytes和316Kbytes。
根據輪廓線實時生成根據我們的發明，ADF可以根據已有的輪廓線或邊界描述符(比如Bezier曲線)利用Perry等人所述的平鋪生成器快速地生成，下文中將對此進行詳細的說明。到字形輪廓線或邊界的最小距離可以利用Bezier曲線高效地計算出來，參見Sederberg等人所著的「GeometricHermite Approximation of Surface Patch Intersection Curves(曲面交線的幾何赫爾米特近似)」，該文發表於CAGD，8(2)，pp.97-114，1991。
在2GHz Pentium IV處理器上生成每個字形需要0.04-0.08秒。整套字體樣式可以在大約4秒內生成。由於不需要傳統的提示，生成ADF所需的邊界描述符遠遠小於它們相應的有提示的對應物。
因此，我們可以存儲這些最小輪廓線，並根據需要由這些輪廓線動態地生成ADF字形，而不是存儲ADF。這些最小輪廓線的小尺寸對於存儲空間有限的設備以及在有限帶寬的網絡上傳輸字形的應用來說是很重要的。
圖10示出了用於將二維對象(比如字形)轉換成二維距離場的方法1000。對象1001被表示成一組邊界描述符(比如曲線spline)和一個填充規則(比如一種奇偶規則或非零環繞規則)。
所述的一組邊界描述符首先經過預處理1010。該預處理過程對邊界描述符進行細分以減小它們的空間跨度。所述的邊界描述符還可以被接合起來以減小邊界描述符組的基數。該預處理過程使得我們可以在確定無符號距離時減少每個位置所需查詢的邊界描述符數量，這將在下文中說明。
根據經過預處理的邊界描述符組1011構建1020一個空域分級結構1021，比如一棵四叉樹。交點(intersections)的高速緩存1031被初始化1030。交點的高速緩存1031中儲存邊界描述符與一組直線(比如距離場的水平線、垂直線、對角線等等)相交的位置，以及相交的方向。這樣做能夠去除決定無符號距離的符號時的冗餘計算。這些相交點可以間隔存儲。
然後在一組位置上查詢1040所述的空域分級結構1021，以確定那些位置處的一組距離。該組距離被用來構建一個二維距離場1041。所述的查詢在每個位置上調用一個距離函數，比如Bezier裁剪，以測定一個無符號的距離。交點的高速緩存、所述的位置以及填充規則都被用來為該距離決定一個符號。
藉助基於組件的字體的壓縮適用於中文、日文以及韓文字體的有效壓縮可以通過使用FontFusion中所用的基於組件的表示法來實現，所述的這些字體中可能包含10000或更多的字形。所述的表示法將字形分解成通用的筆畫和部首，即多種字形共用的複雜形狀，將這些筆畫和部首存儲到一個字體庫中，然後在字體渲染引擎中重新組合它們。
由於距離場是隱式表示法，因此可以利用混合或CSG操作輕易地組合ADF，由此也可見ADF是非常適合用基於組件的方法進行壓縮的。
在二維距離場中表示拐角雙線性或雙二次重建方法所用的面向細節的採樣允許ADF用較少數量的距離值來表示一個二維對象相對反鋸齒的部分。然而，在拐角附近，距離場有較大的變化，這些重建方法就不能很好地近似了。為了精確地表示拐角附近的距離場，這些ADF要求包含拐角的單元被高度細分，從而顯著提高了存儲器需求。另外，ADF的最大細分層次限制了用雙線性及雙二次ADF單元表示拐角所能達到的精度，如Perry等人所述，其中最大細分層次是在ADF生成期間施加的。
為了應對這個問題，我們的發明提供了一種方法1300，該方法可以在含有二維對象(如字形)的拐角的單元內生成一個二維距離場。
方法1300根據二維對象確定1310一個邊界描述符的有序集合1311，並根據邊界描述符1311的有序集合識別出1320一個單元內的拐角點1321。然後該單元被劃分1330成兩個區域，最接近拐角的第一區域和最接近對象邊界的第二區域。方法1300還規定了1340一種重建方法以及一組採樣距離值1371，用於重建所述單元內的距離場，並且該方法將拐角點1321、界定區域的線條、重建方法以及採樣距離值集合1371儲存1380在一個存儲器中。
所述的重建方法根據點所在的區域來決定單元內某點處的距離。第一區域內一個查詢點的距離被定為從該查詢點到拐角點的距離。
為了確定第二區域內的距離，我們將邊界描述符的有序集合1311劃分1350成兩個子集，一個子集中包含拐角點1321之前的邊界描述符，一個子集中包含拐角點1321之後的邊界描述符。然後，邊界描述符的每個子集被擴充1360以形成一條將所述單元劃分成內部與外部兩個部分的延長曲線。對於每個部分來說，所述單元內的距離場可以根據採樣距離值1371重建，所述的採樣距離值是根據相應的延長曲線確定的1370。雙二次重建方法可能需要為所述的兩個部分各存儲9個距離值。
注意，所述的兩個內部部分的相交處形成了所述對象的拐角。因此，可以通過重建到第一內部部分的距離以及到第二內部部分的距離，然後再選取兩個確定距離中的較小者，來重建第二區域內的距離。
所述的兩個區域可以根據通過拐角點的兩條有向直線來指定，所述的兩條直線各垂直於兩個邊界描述符子集之一。每條直線都可以由拐角點以及在該拐角點處對應的邊界描述符子集的外向法線決定。當一條直線被如此定義後，我們就可以通過求出從查詢點到拐角點的向量與外向法線兩者的向量積來確定查詢點位於該直線的哪一側。位於兩條線外側的點處在第一區域內，而位於任何一條線內側的點則處在第二區域內。
字體渲染在當今的字體渲染引擎中，字體主要被表示為輪廓線，這些輪廓線可按需要被縮放以匹配所需的輸出尺寸。儘管大多數高解析度印表機使用兩級渲染，但是現代顯示設備更多地在小點陣尺寸上使用灰度渲染或是灰度與兩級渲染的組合形式。
用於光柵化灰度字形的常見方法涉及縮放及提示它們的輪廓線。經過縮放及提示的輪廓線被掃描轉換為高解析度的圖像，通常比所需的解析度高4或16倍。然後，通過施用一種濾波方法(比如箱式濾波器)來對該高解析度圖像進行下採樣，以產生最終的灰度圖像。
對於正文字型來說，單獨的字形可以被光柵化一次並作為一幅灰度位圖存儲在高速緩存中，以便在預處理步驟中再使用。對字形的子象素布局需要可能要求對每個字形的幾個版本進行光柵化。為正文字型使用高速緩存就可以在某些任務期間進行短延時(如1/2秒)的更高質量渲染，所述的任務可以是例如翻閱一份Adobe Acrobat PDF文檔。
然而，在任意路徑上渲染的字型以及動態化的字形不允許使用高速緩存，因此必須根據需要來產生。實時渲染的需要要求必須使用解析度較低的濾波，通常為每象素四個採樣點以及箱式濾波。這可能引起空域及時域的鋸齒。這種鋸齒可以利用系統存儲器中具有提示的設備字體來消除。然而，維持實時幀率對於如何使用具有提示的設備字體提出了嚴格的限制，比如說，具有提示的設備字體不能被動態縮放或旋轉。
Microsoft最近在ClearType上的工作帶來了用於LCD彩色顯示器的特殊處理方法，在這種顯示器中含有重複樣式的可尋址彩色子象素，即成分(component)。Platt在「Optimal Filtering for PatternedDisplays(用於樣式化顯示器的最優濾波)」一文中描述了一組用於各個顏色成分的感觀最優濾波器，該文發表於IEEE Signal ProcessingLetters，7(7)，pp.179-180，2000。在實際應用中，所述的最優濾波器被實現為一組三個移位箱式濾波器，每個濾波器用於一種顏色。
ClearType使用現有技術的基於覆蓋的反鋸齒方法，來決定每個象素的各個成分的強度。與此相對，我們的基於距離場的方法使用距離場來決定每個象素的各個成分的強度，並且使用了較少的樣點。下文中所述的ADF反鋸齒方法可以取代箱式濾波器，來提供每象素樣點數較少的更好的最優濾波器的模擬。
反鋸齒(Antialiasing)理解經過渲染的字體中的外表成分需要對鋸齒有所認識。通常，一個象素由離散的成分組成，比如彩色印表機或顯示器中的紅色、綠色及藍色成分。在一個灰度設備中，象素是單個離散成分。由於象素是離散的，因此將其呈現給輸出設備本質上就是一個採樣過程。採樣率取決於設備的解析度。採樣率至少是源信號中最高(奈奎斯特)頻率的兩倍，否則採樣信號就會出現鋸齒。
邊緣(比如字形輪廓線)具有無限的頻率分量。因此，邊緣不能由採樣數據準確地表示出來。邊緣的採樣不足會導致鋸齒狀圖形，這種鋸齒狀會在運動圖像的採樣邊緣上蔓延。如果源信號也含有一種空域樣式，比如『m』的重複垂直線或是『i』的單根垂直線，其頻率成分對於採樣率來說太高了，那麼採樣數據就會出現信號丟失、波紋樣式以及時域閃爍。
為了避免鋸齒，輸入信號必須經過預濾波以去除超過採樣率所允許範圍的頻率成分。通常，有兩種方法進行預濾波。
第一種稱為解析濾波。它在採樣前對源信號的連續表示形式進行某種形式的空域平均。不幸的是，解析濾波常常是不可行的，或是因為源數據不是以連續信號的形式提供，在圖像處理中這是很正常的情況，或是因為確定信號在濾波器作用範圍內的解析表示太複雜了。對於計算機圖形學中所有除了簡單幾何圖形外的幾何形狀都會出現這種情況，當然對基於樣條線的輪廓線來說也會同樣出現這種情況。
第二種方法稱為離散濾波。在那種方法中，通常以高於目標速率的速率採樣源信號，以獲得一幅過採樣圖像。然後，在將圖像下採樣到目標速率之前，使用一個離散濾波器來減少過採樣圖像中的高頻成分。該離散方法在計算機圖形學中被稱為常規過採樣。
根據處理預算、硬體考慮以及個人對輸出圖像中對比度與反鋸齒度的偏好，可以使用各種不同的離散濾波器。通常被用來渲染字型的箱式濾波器用一個過採樣值方陣的算術平均來替代這個過採樣值方陣，這種方法在信號處理界通常被認為是比較低級的。
在另一種方法中，自適應過採樣將可用於採樣及濾波的資源集中用於具有較高的局部頻率分量的圖像區域。最優自適應採樣可以根據圖像中的局部變化性來確定。然而，這種技術的實用性會受到估算圖像局部變化的需要的限制，這種估算過程可能是計算代價高昂的。
由於對高頻樣式的常規採樣不足而引起的波紋樣式，是人類視覺系統尤其反感的。在一般的圖像處理中，隨機或跳動採樣被用來解決這一問題。對於隨機採樣，採樣點會隨機地略微偏離它們的指定位置。隨機採樣會用高頻噪聲替代波紋鋸齒，並且已經被證實在減少時域鋸齒中特別有效。
使用基於距離的反鋸齒的渲染在現有技術的字體渲染中，由字形邊緣引入的無限頻率分量是鋸齒的主要成分。與之相對，通過利用2D距離場來表示2D對象，並根據本發明採樣2D距離場，我們就能避開這些邊緣，因為所述的表示方法是C0連續的。最高頻率取決於字形本身的空域樣式，比如『m』的重複垂直線或是『i』的單根垂直線。
通過用字形的2D距離場表示字形，我們就能有效地對該字形使用解析預濾波器。下文中所述的我們用於渲染距離場的反鋸齒方法所產生的輸出與傳統解析預濾波器的輸出不同。
利用距離場進行反鋸齒圖4示出了用來按圖像順序反鋸齒一個對象401(如一種字形)的方法400，所述的對象被表示410成一個二維距離場411。每個象素402中可以包括一個或多個成分404，通常是用於『RGB』類型輸出設備的紅、藍或綠色成分。該方法可以為每個象素402的各個成分404使用一個或多個採樣點。方法400提供自適應的基於距離的過採樣、基於距離的自動提示以及基於距離的柵格裝配。結果得到的反鋸齒象素強度可以被作為一幅圖像的一部分呈現在CRT以及類似LCD的顯示器上。該方法對於渲染運動模糊特別有用。
表示對象401的二維距離場411的採樣點407的一個集合403與每個象素402的各個成分404相關聯420。根據二維距離場411以及採樣點403的集合來確定403一個距離(D)405。然後，距離405被映射440為象素402的成分404的反鋸齒強度(I)406。
在優選實施例中，字形401由雙二次ADF 411表示，如上文所述。這樣就使得在字體渲染過程中使用基於距離的反鋸齒方法效率很高。其他的表示方法，比如二維距離圖、二維距離殼以及程序性距離場，也都可以被採用。
對於一幅圖像中每個象素402的各個成分404，都要利用四叉樹遍歷方法來定位一個含有成分404的單元，比如葉單元，所述的遍歷方法在美國專利申請10/209302中有所說明，該專利於2002年7月31日提交，題為「Method for Traversing Quatrees，Octrees，andN-Dimensional Bitrees(用於遍歷四叉樹、八叉樹以及N維二叉樹的方法)」，本文通過引用將該專利申請完全包含進來。儘管本技術領域內其他已知的方法也可以被用於我們的發明，但是上述方法是無需進行比較的，因此執行效率更高。成分404處的距離根據單元的距離值重建出來，並被映射440為反鋸齒強度(I)406。
可以使用不同的映射，包括線性、高斯以及S形函數。最佳映射函數的選擇是主觀的。在一個實施例中，我們的映射是兩個函數的組合。第一個函數如上所述，第二個函數是對比度增強函數。這兩個函數被組合起來以便將距離場(D)405映射440為成分404的反鋸齒強度(I)406。
圖5以距離502的函數形式示出了強度501的線性映射500，比如
。該映射為象素的各個成分把距離轉換成反鋸齒圖像強度。距離在對象內部是正的，在對象外部則是負的。不同的截止值503和504會影響邊緣對比度以及筆畫濃度。我們為顯示字型採用(-0.75，0.75)象素的外部503及內部504濾波器截止值，為正文字型採用(-0.5，0.625)象素的濾波器截止值，達到了良好的效果。
基於距離的最優自適應過採樣上述基於距離的反鋸齒方法減少了字形邊緣引起的鋸齒。然而，當筆畫寬度或是字形各部分之間的距離對於顯示器採樣率來說太小時，鋸齒成分仍會出現。在這種情況下，我們就要使用下文中將要說明的基於距離的自適應過採樣，以進一步減少空域及時域的鋸齒。
在優選實施例中，我們使用帶有我們獨創的基於距離的自適應過採樣的雙二次ADF，相對現有技術的基於輪廓線的表示法以及基於覆蓋的自適應過採樣方法而言，該方法具有顯著的優勢。由於ADF採用面向細節的採樣，因此局部變化性較強的距離場區域可由較小的葉細胞表示。由此，ADF四叉樹的結構提供了實現基於距離的最優自適應採樣所需的局部變化映象，從而克服了上文中所述的現有技術自適應過採樣反鋸齒方法中確定局部變化性的困難。
對於圖像中每個象素402的各個成分404，都要定位含有成分404的單元，並且要將位於該成分的濾波器工作半徑r以內的一組403採樣點407與該象素成分404關聯起來420。每個成分(spc)中的採樣點407的數量取決於單元尺寸(cellSize)對r的相對大小。採樣點407處的採樣距離經過濾波，以確定430一個單個加權平均距離405，然後該距離被映射440成象素404的成分404的反鋸齒強度406。
有多種不同的濾波器及採樣策略可以使用。在優選實施例中，我們使用一種普通形式的高斯濾波器，用W-12-3(d/r)2對各個距離採樣值加權，其中d是該採樣點到象素成分的距離，W則是用於那個成分的權重總和。類似的結果也可以用箱式濾波器、漏鬥形濾波器、負瓣濾波器以及其他形式的高斯濾波器得到。
圖6A-C示出了我們的採樣策略。採樣點407被定在成分601附近的同心圓610上，以便高效地計算權重及權重總和。我們使用象素間距的1.3倍作為濾波器半徑r602，並在cellSize＞r(圖6A)時採樣1個spc，在r/2＜cellSize≤r(圖6B)時採樣5個spc，在cellSize≤r/2(圖6C)時採樣13個spc。
除了同心圓之外，本發明還可以使用多種其他策略來關聯採樣點407與象素成分404。我們的方法對具體的採樣策略並不特別敏感。
下文中所述的另一種自適應採樣策略，將採樣點定在濾波器半徑r以內所包含的所有單元的中心。該策略能得到同樣良好的結果。
基於單元的反鋸齒上述的距離場反鋸齒方法可以利用基於掃描線的光柵化方法在軟體中實現。或者，被劃分成單元的距離場也可以一個單元接一個單元地反鋸齒，即按對象順序反鋸齒。基於單元的渲染消除了為定位含有採樣點的單元而進行的樹遍歷，消除了用於計算單個單元內距離以及梯度的冗餘設置，並且減少了單元數據的重複檢索，即內存讀取。
另外，由於渲染所需的單元可以被表示為固定大小的自包含的單元的順序模塊，即單元內的點的距離及梯度可以根據單元的距離值確定，因此我們的基於單元的方法容易用硬體實現，從而使得實時渲染成為可能。
圖7示出了一種用來按對象順序渲染對象701(例如一個字形)的方法700，所述的對象被表示710為一個二維距離場711。方法700提供了基於距離的自適應過採樣，基於距離的自動提示以及基於距離的網格裝配。最終得到的經過反鋸齒的象素強度可以作為一幅圖像的一部分被呈現在CRT以及LCD類的顯示器上。該方法對於渲染運動模糊特別有用。當二維距離場711的單元被安排在一個空域分級結構中時，我們可以利用MIP映射(mipmapping)來減少所需的距離採樣點數量。
二維距離場711被劃分成單元712。在一個優選實施例中我們使用雙二次自適應採樣的距離場，其中每個單元的大小取決於二維距離場的局部變化性。每個單元都包括一種方法(M)713，用於重建該單元內的二維距離場。一組含有待渲染的距離場區域(虛線)722的單元721被識別720出來。
區域722被用來定位730一組與該區域有關的象素731。對應於象素731集合中的各個象素的一組成分741被指定740。然後，根據單元集合中的距離為每個象素的各個成分決定反鋸齒強度751。這裡，所述的距離是根據單元集合重建的。然後所述的距離就被映射為反鋸齒強度，如上所述。
在一個實施例中，我們可以通過定位單元集合中靠近象素成分的一個單個採樣點、並重建該單個採樣點到單元集合的距離，來確定距離。在我們的優選實施例中使用了雙二次自適應採樣的距離場，我們通過對小於濾波器半徑的單元進行特殊處理而增強了該方法，其用於基於距離的自適應過採樣。由於小單元出現在距離場中變化性較強的位置，因此可以在將距離映射為強度前，對靠近這些單元的象素距離進行預濾波。
我們對元素的合成緩存器進行初始化，其中的每個元素對應於所述象素集合中各個象素的一個成分。單元集合中的每個單元都可以被獨立地處理。在優選實施例中，每個單元包括一個加權距離以及一個累計權重，兩者都被初始化為零。在一個單元被處理時，這些加權距離以及累計權重在緩衝器元素中被遞增，所述的緩衝器元素與位於所述單元內或是位於所述單元中心的濾波器半徑內的象素成分相對應。
在處理了所有的單元之後，用累計權重對每個象素的各個成分的加權距離歸一化，以產生接著將被映射為反鋸齒成分強度的距離。在優選實施例中，我們使用與上文所述相同的高斯加權和濾波器半徑。
至此所述的基於單元的渲染總是要處理單元集合中的每個葉單元，而不管每個單元對濾波器半徑的相對大小。理論上，這樣做提供了最優的基於距離的自適應過採樣。而實際上，ADF四叉樹可以被用作MIP映射以減少單元數量。
ADF四叉樹結構使得我們可以用小的葉單元的前輩來替代小的葉單元，從而有效地裁剪了某預定單元尺寸的四叉樹。只要該單元尺寸小於或等於象素間間隔的1/4，那麼在基於距離的自適應過採樣結果中就不會存在視覺效果上的退化。這樣做減少了渲染該區域所需的單元數。
處理象素成分一個象素包括一個或多個成分。例如，典型的CRT或LCD彩色顯示器上的象素包括紅色、綠色以及藍色的成分。在我們的發明中，當象素包括多個成分時，它們就會被單獨地處理，如上文中所述，或是被當作一個單個成分處理。當多個成分被當作單個成分處理時，就可以根據單個成分的反鋸齒強度來確定該象素的彩色或灰度值。
將多個成分當作一個單個成分處理有兩個原因。首先，它能減少渲染時間。其次，當多個成分不能被單獨尋址，或是當諸單個成分的相對位置未知時，對每個成分進行個別處理就是不可能的。
當顯示設備，如LCD，具有可尋址的象素成分時，單獨地處理多個成分能夠提高顯示設備的有效解析度，這一點在現有技術中是已知的。我們的發明可以充分利用這類設備的這一特性，來提供質量優於現有技術的基於距離的反鋸齒。
動態化二維對象圖12示出了方法1200的流程圖，該方法根據動畫腳本1202將對象1201動態化成為一系列的幀。動畫腳本1202為所述幀序列中的每一幀指示出對象的條件，例如對象的位置、大小、方向以及變形。該對象被表示為一個二維距離場。根據動畫腳本1202，為幀1221序列中的每一幀更新1210對象1201的形態1211。利用經過更新的形態1211以及基於距離的反鋸齒渲染方法1212來渲染對象1201。
表示對象1201的二維距離場可以從不同的對象表示法中得到，例如對象的輪廓線描述或是對象的位圖描述。
為特定對象1201進行形態1211的更新1210，可以通過對該對象進行各種不同的操作來實現，其中包括剛體變換、自由形態變形、軟體衝擊變形、水平級方法、顆粒模擬以及改變其渲染屬性。
在渲染1220所述的對象時，我們將表示對象的二維距離場中的一組採樣點與幀1221序列中的一個幀內的一個象素成分關聯起來。通過由所述的二維距離場以及採樣點組來確定距離，我們就可以將距離映射成所述象素成分的反鋸齒強度。
在一個優選實施例中，我們將表示對象1201的二維距離場劃分成單元，每個單元中都包括了用於重建該單元內的二維距離場的方法。為了在該例中進行渲染1220，我們要在表示對象1201的二維距離場中識別出一組單元，其含有待渲染的二維距離場區域，還要定位與該區域相關的一組象素。指定對應於該組象素中各個象素的一組成分。根據該組單元為象素的各個成分確定一個距離，並將該距離映射為該象素成分的反鋸齒強度，從而為該組象素中每個象素的各個成分確定一個反鋸齒強度。
基於距離的自動提示標準字體表示法中的提示是一種耗時的手工過程，其中字型設計人員以及提示專家要生成一組規則，以便更好地將字形個體匹配到象素網格中。良好的提示有助於在小字型尺寸下產生間隔合適、具有良好對比度且外表均勻的字形。
這些規則提供具有相同對比度分配的垂線，其左邊與底部邊緣具有可能實現的最銳利的對比度；字形的對角線條以及纖細圓滑的部分具有足夠的對比度，以便向眼睛傳遞視覺結構；以及襯線，這些襯線結合在一起並提供足以被人眼捕獲的強化突出，參見Hersch等人所著的「Perceptually Tuned Generation of Grayscale Fonts(灰度字體的感觀調節生成)」，該文發表於IEEE CGA，Nov，pp.78-89，1995。
注意，現有技術的濾波方法會產生模糊的字符，並向不同的字符部分指定不同的對比度方案，從而違反了字型設計的重要原則。為了克服這些局限性，就要為每種字體的每個字形開發提示。現有技術的提示方法存在許多問題它們的開發耗費勞力，而且非常複雜以至於不能用硬體實現。
對基於輪廓線的字體而言，用提示進行渲染是一個三步驟的過程。首先，所述字形的輪廓線被縮放並與象素網格對齊。其次，輪廓線被修改以控制縱線、橫線以及襯線的對比度，並提高非常纖細部分以及弧線的濃度。第三，對經過修改的輪廓線進行過採樣，隨後進行帶有濾波的下採樣。
儘管上文中所述的我們未經提示的基於距離的反鋸齒渲染方法比現有技術的字體渲染方法更為有利，但是眾所周知，感觀提示可以提高小字型尺寸下的閱讀舒適度。
因此，如圖8中所示，我們充分利用距離場來提供基於距離的自動提示，以便進行小點尺寸下的字形渲染。提示中的第一步810是縮放距離場並將其與象素網格對齊。這一步可根據給定的或推導出的字體規格自動完成，比如蓋帽高度、x高度以及基線的位置。
在應用了這種網格裝配的形式之後，我們就可以利用距離場及其梯度場來提供感觀提示。
在一個實施例中，距離場梯度的方向被用來檢測820對象左邊與底部邊緣上的象素。通過暗化830這些象素並亮化840對面邊緣上的象素，我們就可以實現左邊與底部邊緣上較高的對比度，而無需改變明顯的筆畫濃度。這可以通過降低或提高相應的象素強度來完成。
在另一個實施例中，梯度場被用來為對角線條及細弧線提供更好的對比度。我們注意到，如果一個象素位於或靠近字形的狹窄區域，那麼該象素兩側的相鄰象素就會具有相反的梯度方向，即，它們的點積為負數。通過檢測梯度方向的突變，我們就可以暗化850這些狹窄區域上的象素。
這些只是如何利用距離場來自動提供感觀提示的兩個實例。所述的距離場也可以被用來提供最佳的字符間距以及均勻的筆畫濃度。
生成與編輯字體有兩種設計字體的基本方法。第一種是手工。其中，字形靠手繪製、數位化，然後將輪廓線匹配到數位化的位圖中。第二種方法則是由計算機完成。
在後一種情況下，有三類工具可供使用。直接的視覺工具可被用於曲線處理。程序設計工具通過執行一個程序的指令來創建字形的形狀。該程序或是定義一個形狀的輪廓並填充它，或是定義一條由筆尖繪出的路徑，該路徑有多種屬性，其中包括幾何形狀及方向。基於組件的設計工具允許設計者們創建基本的組件，如直線、弧線以及其他重複出現的形狀，然後組合這些組件以產生字形。
我們使用造型編輯器來提供基於筆畫的設計。這是與3D雕刻相對的一項技術，後者在美國專利申請09/810261中有所說明，該專利申請題為「System and Method for Sculpting Digital Models(用於塑造數字模型的系統與方法)」，於2001年3月16日提交，此處通過引用包含進來。筆畫描繪可以被交互地完成，或者也可以編寫腳本令其模擬可編程的設計工具。
也可以採用基於弧線的設計，這種設計方法利用了Bezier曲線處理工具，該工具與Adobe Illustrator中所用的工具相似。基於弧線的設計方法可以與用來將輪廓線轉換成距離場以及將距離場轉換為輪廓線的方法組合起來，以提供設計規範間的無縫接口。
基於組件的設計方法在隱式距離場使用CSG以及混合操作。這樣就使得組件可以被單獨設計，並在編輯或渲染期間組合起來。
我們還提供了一種由模擬及數字字體模板自動生成ADF的方法。
對於基於組件的設計方法，我們的字體編輯器提供了利用四叉樹操作來有效反射及旋轉ADF的能力，用以塑造字形中常見的對稱性。其他的特性包括ADF縮放、平移以及組合多個ADF的操作，比如CSG與混合。
對於基於筆畫的設計方法，我們提供了刻圖工具，該工具具有幾何輪廓以模擬筆尖。模擬筆尖的方向及尺寸可以沿筆畫變化，以模仿書法筆跡。
圖9示出了用來由一個筆畫生成一個二維距離場931的方法900。我們在筆繪期間採樣筆的狀態，該筆狀態包括筆繪期間該筆的位置。該筆狀態還可以包括方向與幾何形狀。根據筆狀態採樣點901，我們可以沿筆畫生成910筆狀態的有序列表911。然後，由筆狀態的有序列表生成920一組邊界描述符921。最後，我們由該組邊界描述符921生成930一個二維距離場931。
在優選實施例中，邊界描述符921是三次Bezier曲線之類的曲線。
在優選實施例中，我們運用曲線匹配程序來將G2連續曲線的一個最小集合匹配到筆的路徑上，其精度由用戶指定。我們還利用工具尺寸與方向生成離開該條路徑的偏移點的兩個額外的有序列表，並將曲線匹配到這些偏移點上，以產生筆畫輪廓線。輪廓曲線被放置在一個空域分級結構中，以便有效地處理。我們利用平鋪生成器由該分級結構生成一個二維ADF，參見美國專利申請09/810983號，該專利申請於2001年3月16日提交，此處通過引用包括進來。
到輪廓線的最小距離可以利用Bezier裁剪來有效地計算。筆畫被轉換成ADF，對於用戶來說沒有感觀上的延時。為了進行曲線操作，我們提供了Bezier曲線編輯器。
如圖11中所示，我們還提供了將距離場轉換為邊界描述符-如Bezier曲線-的能力，以提供三種設計規範間的無縫接口。
在優選實施例中，我們使用雙二次ADF，其中該轉換過程利用ADF分級結構遍歷葉單元，以便進行快速的相鄰搜索，生成沿ADF零等值線上的點的有序列表，然後如下文中參照圖11所述的那樣匹配曲線以生成邊界描述符。
在現有技術中，邊界描述符誤差是根據點列表計算得出，與之相對，我們直接由距離場計算出邊界描述符誤差。我們特別注意了尖銳的稜角。我們的方法快得足以讓用戶在範例間無縫切換，而不會引起明顯的延時。
圖11示出了用來將二維距離場1101轉換成一組邊界描述符1131的方法1100。首先，我們選取1110二維距離場1101的等值輪廓線1111，比如距離為零或其他偏移量的。
其次，我們由等值輪廓線1111及二維距離場1101生成1120點1121的有序列表。在我們使用了雙二次自適應採樣距離場的優選實施例中，該步驟利用相鄰搜索技術遍歷了自適應採樣距離場1101的相鄰單元。該搜索技術充分利用了自適應採樣距離場1101的空域分級結構，以便沿著等值輪廓線1111有效地定位下一個相鄰的單元。
在另一個實施例中，我們通過選取ADF 1101中的邊界單元，以各個邊界單元為種子生成一組有序點，並利用ADF 1101的距離場和梯度場將各個點移動到ADF 1101的等值線1111上，以此來生成1120點1121的有序列表。
然後，我們初始化1130一組邊界描述符1131，以匹配點1121的有序列表。邊界描述符1131的初始化1130是通過將點1121的有序列表中的相鄰點結合來完成的，以此形成一組線段，這些線段構成了最初的邊界描述符1131。
在另一個實施例中，我們通過定位拐角點、將所述的點的有序列表劃分成由這些拐角點界定的片段、並確定片段邊界描述符以匹配各個片段，從而初始化130一組邊界描述符1131。片段邊界描述符的組合形成了最初的邊界描述符1131。
拐角點可以通過測量由距離場求得的曲率來定位。在優選實施例中，距離場是雙二次ADF，其中高曲率的區域由ADF中的小單元表示，從而可以利用ADF的單元尺寸來定位拐角點。
一旦邊界描述符1131被初始化1130，邊界描述符1131就會被更新1140。更新1140通過重建距離場並測量邊界描述符離開等值輪廓線的平均或最大偏差，來為每個邊界描述符求出一個誤差。
邊界描述符1131被持續更新1140，直到每個邊界描述符的誤差令人滿意、或是過了預定時間、或是邊界描述符1131的集合的基數最小為止。
為了把以非數字形式-即模擬模板-或以位圖之類的數字形式-即數字模板-儲存的現有傳統字體合併進來，我們的編輯系統提供了用來從高解析度兩級位圖生成ADF的方法。
模擬模板首先被掃描來產生某個解析度下的兩級數字模板，該解析度至少要比目標ADF解析度高4倍，比如說，4096×4096的數字模板對與現代的顯示解析度及顯示尺寸來說就足夠了。然後，對位圖進行準確的歐幾裡德距離變換，以生成表示字形的規則採樣距離場。
然後，我們利用平鋪生成器由該規則採樣的距離場生成一個ADF。在2GHzPentium IV處理器上，每個字形的位圖到ADF的轉換需要約10秒鐘。
為了從現有技術的字形描述符轉換到距離場，我們應用了參照圖10說明的方法，其中在所述的距離場中字形由一組邊界描述符表示。
用於動態版式的計算底版我們ADF字形框架的距離場以及空域分級結構屬性也可以被用於2D對象的計算機模擬，比如字形、企業標誌或是任何2D形狀。例如，上述的兩種屬性都可以被用在衝突檢測與避免中，用於計算互相穿過的實體間的作用力，以及用於模擬軟體形變。
級設置方法利用了有符號的距離場，該方法可被用來模擬許多效應，比如熔化與流體動力學。ADF是緊湊的隱式表示法，它可被有效地查詢以計算距離值和梯度，這是上述方法所需的兩種重要計算。
與此相對，由移動或變形的輪廓線來求出距離值和梯度在用於實時互動的軟體中是不實用的，參見Hoff等人所著的「Fast andSimple 2D Geometric Proximity Queries Using Graphics Hardware(利用圖形硬體進行快速簡單的2D幾何近似查詢)」，該文發表於Proc.Interactive 3D Graphics』01，2001。Hoff等人利用圖形硬體來為變形曲線實時生成規則採樣的2D距離場，其中所述的變形曲線由線段近似。
距離場的隱式本質允許複雜的拓撲變化，比如表面偏移，這類變化很難用基於輪廓線的字體來模擬。另外，距離場還可以被用來提供動態化對象的非光學現實主義渲染，以添加藝術效果。
本發明的作用本發明提供了一種新穎的框架，用於表示、渲染、編輯以及動態化字符字形、企業標誌或是任意二維對象。在一種優選實施例中，本發明利用二維雙二次ADF來表示二維對象。該雙二次重建方法提供了存儲器使用與計算負荷間的最佳平衡。
本發明包括一種方法，用來在一個含有二維對象拐角的單元內生成一個二維距離場。相比現有技術，該方法提供了對存儲器需求的顯著減少，以及精度的明顯改善。
我們基於距離的反鋸齒渲染方法利用每象素一個單個未經提示的距離採樣點提供了比現有技術中所用的過採樣方法更好的反鋸齒。
我們基於距離的方法充分利用了ADF的空域分級結構，來提供高效最優的基於距離的自適應過採樣，從而實現了出色的空域與時域反鋸齒。我們的方法還為基於距離的自動提示、為基於距離的網格裝配、為聯合三種常用的數字字體設計規範以及為動態字體樣式產生多種特殊效果，提供了計算基礎。
儘管本文中已經通過優選實施例的方式對本發明進行了說明，但是應該明白，在本發明的指導思想及範圍內還可以作出多種其他的變化與改進。因此，附屬權利要求的目的就是要涵蓋所有這些包含在本發明的真正指導思想與範圍內的變化及改進。
權利要求
1.一種根據代表一個對象的二維距離場確定一個象素的一個成分的反鋸齒強度的方法，包括將代表一個對象的二維距離場中的一個採樣點集合與一個象素的一個成分關聯起來；根據所述的二維距離場以及所述採樣點集合確定一個距離；以及將所述的距離映射成所述象素的所述成分的反鋸齒強度。
2.根據權利要求1所述的方法，其中所述的二維距離場是一幅二維距離圖。
3.根據權利要求1所述的方法，其中所述的二維距離場是一個二維距離殼。
4.根據權利要求1所述的方法，其中所述的二維距離場包括一組儲存在存儲器中的距離。
5.根據權利要求1所述的方法，其中所述的二維距離場是一個被分成多個單元的二維的自適應採樣的距離場。
6.根據權利要求1所述的方法，其中所述的二維距離場由一個程序表示。
7.根據權利要求1所述的方法，其中所述象素是一幅二維圖像的一部分。
8.根據權利要求7所述的方法，其中所述二維圖像的尺寸是通過將二維距離場的一個區域變換為象素坐標而確定的。
9.根據權利要求8所述的方法，其中所述區域是一個有界的框。
10.根據權利要求1所述的方法，其中與所述象素成分相關聯的所述採樣點集合是位於所述象素成分附近的一個單個採樣點。
11.根據權利要求10所述的方法，其中所述單個採樣點的距離是根據二維距離場重建的。
12.根據權利要求1所述的方法，其中確定所述距離還包括根據所述象素成分附近的二維距離場的局部變化決定所述採樣點集合的一個基數N；將所述採樣點集合中的N個採樣點設置在所述象素成分的附近，以便將該採樣點集合與所述象素成分關聯起來；根據所述的二維距離場為N個採樣點的每一個重建一個採樣距離；根據所述N個採樣點的每一個的位置確定一個權重；以及組合所述N個採樣點的權重與採樣距離來確定所述距離。
13.根據權利要求12所述的方法，其中當所述象素成分附近的二維距離場的局部變化高時，基數N提高，而當所述象素成分附近的二維距離場的局部變化低時，基數N降低。
14.根據權利要求12所述的方法，其中所述二維距離場的局部變化是通過根據所述象素成分附近的二維距離場的多個採樣距離的變化確定的。
15.根據權利要求12所述的方法，其中所述二維距離場的局部變化是通過所述象素成分附近的二維距離場的採樣梯度的變化確定的。
16.根據權利要求5所述的方法，其中與所述象素成分相關聯的採樣點集合由位於所述象素成分附近的一個單個採樣點構成，該方法還包括定位所述二維自適應採樣距離場的一個單元集合，該單元集合是重建所述單個採樣點處的一個採樣距離所需的；以及根據所述的單元集合重建所述單個採樣點處的採樣距離，以確定所述距離。
17.根據權利要求16所述的方法，其中所述的單元集合由一個單個單元構成，該單元中含有所述的單個採樣點。
18.根據權利要求17所述的方法，其中所述的單個單元是一個葉單元。
19.根據權利要求5所述的方法，其中確定所述距離還包括根據所述象素成分附近的二維自適應採樣距離場的局部變化決定所述採樣點集合的一個基數N；將所述採樣點集合中的N個採樣點設置在所述象素成分的附近，以便將該採樣點集合與該象素成分關聯起來；根據所述的二維自適應採樣距離場為N個採樣點的每一個重建一個採樣距離；根據所述N個採樣點每一個的位置確定一個權重；以及組合所述N個採樣點的權重與採樣距離，來確定所述距離。
20.根據權利要求19所述的方法，其中當所述象素成分附近的二維自適應採樣距離場的局部變化高時，基數N提高，而當所述象素成分附近的二維自適應採樣距離場的局部變化低時，基數N降低。
21.根據權利要求19所述的方法，其中所述的局部變化是根據所述象素成分附近的二維自適應採樣距離場的一個單元的尺寸確定的。
22.根據權利要求21所述的方法，其中當所述的二維自適應採樣距離場的單元尺寸小時，基數N提高，而當所述的二維自適應採樣距離場的單元尺寸大時，基數N降低。
23.根據權利要求19所述的方法，其中所述的局部變化性是通過根據所述象素成分附近的二維自適應採樣距離場的多個採樣距離的變化確定的。
24.根據權利要求19所述的方法，其中所述的局部變化是通過所述象素成分附近的二維自適應採樣距離場的採樣梯度的變化確定的。
25.根據權利要求12或19所述的方法，其中所述權重對N個採樣點每一個都是常數。
26.根據權利要求12或19所述的方法，其中所述N個採樣點每一個的權重是根據第二距離確定的，該第二距離是從所述採樣點的位置以及所述象素成分的位置求得的。
27.根據權利要求26所述的方法，其中所述的每個採樣點的權重是第二距離的線性函數。
28.根據權利要求26所述的方法，其中所述的每個採樣點的權重是第二距離的高斯函數。
29.根據權利要求26所述的方法，其中所述的組合是所述採樣點的第二距離的加權平均，以確定所述距離。
30.根據權利要求1所述的方法，其中所述的確定距離是在所述象素成分附近的二維距離場的一個區域上進行一個解析函數的估算。
31.根據權利要求30所述的方法，其中所述的解析函數是在所述象素成分附近的二維距離場的所述區域上的積分。
32.根據權利要求1所述的方法，其中所述的映射是將所述距離與反鋸齒強度相關聯的一維函數。
33.根據權利要求32所述的方法，其中所述的一維函數是第一函數與第二函數的組合。
34.根據權利要求33所述的方法，其中所述的第二函數是一個對比度增強函數。
35.根據權利要求32所述的方法，其中所述的一維函數是線性的。
36.根據權利要求32所述的方法，其中所述的一維函數是高斯的。
37.根據權利要求1所述的方法，其中所述的映射是一個將所述距離與反鋸齒強度相關聯的一維查找表。
38.根據權利要求37所述的方法，其中所述一維查找表中的每個反鋸齒強度值是所述距離的線性函數。
39.根據權利要求37所述的方法，其中所述一維查找表中的每個反鋸齒強度值是所述距離的高斯函數。
40.根據權利要求1所述的方法，其中所述的映射是將所述距離與反鋸齒強度相關聯的N維函數。
41.根據權利要求40所述的方法，其中所述的N維函數的一個變量是根據所述象素成分的位置確定的。
42.根據權利要求40所述的方法，其中所述的N維函數的一個變量是根據所述象素成分附近的二維距離場的一個梯度場確定的。
43.根據權利要求1所述的方法，其中所述的映射是將所述距離與反鋸齒強度相關聯的N維查找表。
44.根據權利要求43所述的方法，其中所述N維查找表的一個變量是根據所述象素成分的位置確定的。
45.根據權利要求43所述的方法，其中所述N維查找表的一個變量是根據所述象素成分附近的二維距離場的一個梯度場確定的。
46.根據權利要求1所述的方法，其中所述的象素由一個單個成分構成。
47.根據權利要求46所述的方法，其中所述象素的一種顏色是根據所述象素的單個成分的反鋸齒強度決定的。
48.根據權利要求46所述的方法，其中所述象素的一個阿爾法通道是根據所述象素的單個成分的反鋸齒強度決定的。
49.根據權利要求1所述的方法，其中所述的象素由M個成分構成。
50.根據權利要求49所述的方法，其中所述的M個成分被當作一個單個成分處理。
51.根據權利要求49所述的方法，其中所述的M個成分的位置是預先確定的，並且該M個成分的集合是被獨立地處理的。
52.根據權利要求49所述的方法，其中所述的M個成分包括一個紅色、一個綠色以及一個藍色成分。
53.根據權利要求49所述的方法，其中所述的M個成分包括一個青色、一個品紅色、一個黃色以及一個黑色成分。
54.根據權利要求51所述的方法，其中所述象素的一種顏色是根據所述M個成分的集合中的諸個成分的反鋸齒強度確定的。
55.根據權利要求51所述的方法，其中所述象素的一個阿爾法通道是根據所述M個成分的集合中的諸個成分的反鋸齒強度確定的。
56.根據權利要求1所述的方法，其中所述的距離是通過一個N維函數修改的，其中該函數的一個變量是所述象素成分附近的二維距離場的一個梯度場。
57.根據權利要求1所述的方法，其中所述象素成分的反鋸齒強度是通過一個N維函數修改的，其中該函數的一個變量是所述象素成分附近的二維距離場的一個梯度場。
58.根據權利要求42、45、56或57所述的方法，其中所述梯度場提供所述對象的自動提示。
59.根據權利要求58所述的方法，其中所述的對象是一個字符字形。
60.根據權利要求58所述的方法，其中所述的對象是一個標誌。
61.根據權利要求58所述的方法，其中所述梯度場的方向被用來提高所述對象的選定邊緣上的對比度。
62.根據權利要求61所述的方法，其中所述選定邊緣是所述對象的左側及底部邊緣。
63.根據權利要求58所述的方法，其中所述梯度場被用來減少所述對象的狹窄區域附近的丟失。
64.根據權利要求63所述的方法，其中所述梯度場方向上的突變被用來檢測所述對象的狹窄區域。
65.根據權利要求1所述的方法，其中所述的對象是一個二維字符字形，該方法包括為所述的二維距離場增加一組屬性；以及根據所述一組屬性修改所述的二維距離場。
66.根據權利要求65所述的方法，其中所述的一組屬性中的一個屬性是所述二維字符字形的筆畫濃度。
67.根據權利要求65所述的方法，其中所述的一組屬性中的一個屬性是所述二維字符字形的一個基線。
68.根據權利要求65所述的方法，其中所述修改對所述的二維距離場進行縮放。
69.根據權利要求65所述的方法，其中所述修改平移所述的二維距離場。
70.根據權利要求65所述的方法，其中所述修改變形所述的二維距離場。
71.根據權利要求65所述的方法，其中用一組屬性補充代表多個二維字符字形的多個二維距離場。
72.根據權利要求42、45、56或57所述的方法，其中所述的梯度場被用來渲染對象的運動模糊。
73.根據權利要求72所述的方法，其中所述梯度場的方向與所述對象的運動方向之間的相似性被用來渲染對象的運動模糊。
74.根據權利要求1所述的方法，其中所述的二維距離場包括多個單元，每個單元包括多個距離，並且每個單元的尺寸取決於所述二維距離場的局部變化。
75.一種根據代表一個對象的二維距離場確定一個象素的一個成分的反鋸齒強度的裝置，包括將代表一個對象的二維距離場中的一個採樣點集合與一個象素的一個成分關聯起來的裝置；根據所述的二維距離場以及所述採樣點集合確定一個距離的裝置；將所述的距離映射成所述象素的成分的反鋸齒強度的裝置；以及用來顯示所述象素的成分的反鋸齒強度的顯示裝置。
76.根據權利要求75所述的裝置，其中所述的顯示裝置是一臺CRT顯示器。
77.根據權利要求75所述的裝置，其中所述的顯示裝置是一臺LCD顯示器。
78.根據權利要求75所述的裝置，其中所述的顯示裝置是個人數字助理的一個部件。
79.根據權利要求75所述的裝置，其中所述的顯示裝置是一臺通信設備的一個部件。
80.根據權利要求75所述的裝置，其中所述的顯示裝置是一臺遊戲設備的一個部件。
81.根據權利要求75所述的裝置，其中所述的顯示裝置是一臺醫療器械的一個部件。
82.根據權利要求75所述的裝置，其中所述的顯示裝置是一臺電子設備的一個部件。
全文摘要
根據代表一個對象的二維距離場確定一個象素的一個成分的反鋸齒強度的方法及裝置。所述二維距離場中的一個採樣點集合與所述的象素的成分相關聯。根據所述的二維距離場以及採樣點集合確定一個距離，並將該距離映射為所述象素成分的反鋸齒強度。
文檔編號G06T11/00GK1698093SQ20048000005
公開日2005年11月16日 申請日期2004年3月22日 優先權日2003年3月25日
發明者羅納德·N.·佩利, 莎拉·F.·弗裡斯肯 申請人:三菱電機株式會社