[發明專利]一種基于像素精度的代數曲線光柵化方法

有效

• 申請號: 201210094451.7
• 申請日: 2012-04-01
• 公開（公告）號: CN102651137A
• 公開（公告）日: 2012-08-29
• 發明（設計）人: 馮結青;黃錦基
• 申請（專利權）人: 浙江大學
• 主分類號: G06T11/00
• 分類號: G06T11/00
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明涉及計算機代數曲線曲面造型技術，特別涉及一種基于像素精度的代數曲線光柵化方法。?

背景技術

代數曲線曲面在幾何造型中的表示能力很強，比參數曲線曲面更能表示具有任意拓撲的復雜曲線曲面。但是由于它在直觀控制方面遠不如參數曲線，并且控制系數數目較多，所以對代數曲線曲面的研究并不多。代數B-樣條曲線在幾何直觀性上彌補了冪基代數曲線的編輯不直觀的缺點，具有分段光滑、可局部編輯、幾何編輯直觀、可表示復雜拓撲形態等優點。?

在平面代數曲線的繪制研究方面，主要面臨困難是求解曲線的拓撲信息的問題。對于二次的平面代數曲線就有拋物線、橢圓、雙曲線、交叉直線四種拓撲結構，隨著曲線次數的增加，曲線的拓撲形態會迅速增多，這給求解曲線的拓撲結構帶來極大的挑戰。在求解曲線拓撲的過程中，還必要面臨精確求解曲線的奇異點(尖點、自相交點、孤立點)。對于曲線的奇異點，求解奇異點的拓撲信息也是在數值計算中的難題，其最終歸結為求解帶有重根的線性方程求解。對于帶有重根的線性方程求解，現在還沒有能夠在計算時間和精度上取得很好的平衡。?

對于已經給出的拓撲結構，并不等于能夠完整的刻畫代數曲線。在代數曲線的光柵化過程中，即使得到了代數曲線的分段線性拓撲同構體，由于代數曲線光柵化算法一般采用像素采樣點跟蹤算法，對于相互靠近的曲線有可能出現跟蹤錯誤的結果。這樣導致從一個種子點出發，不能準確地到達分段曲線的終點。改進的算法是在需要的像素位置做子像素跟蹤，但是這個過程需要更多的計算。?

在代數曲線可視化過程中，如何實現代數曲線快速光柵化是代數曲線曲面造型技術發展的重要研究課題。?

現有技術中，代數曲線的繪制方法可以分為兩類：物體空間算法和圖像空間算法。?

在物體空間算法中，采用大量的直線段逼近代數曲線，然后利用已有的圖形繪制方法顯示這些逼近的直線段集合。在逼近過程中，核心是計算曲線上特征點，使得逼近直線段集合和原始曲線的拓撲一致。在計算代數曲線上的特征點時，最常用的方法是柱形代數分解。該方法的主要瓶頸在于柱形代數分解過程中需要消耗比較大的時間，不能達到實時繪制的要求。?

在圖像空間算法中，算法確定曲線通過的像素或者子像素，然后對該像素進行著色。兩類算法各有優缺點。對于給定的圖像空間區域，檢測曲線是否通過該區域。排除曲線沒有通過的區域，對于有曲線通過的區域，運用細分或者跟蹤的方式，直到每個區域只有像素或子像素大小。該方法缺乏對曲線的精確計算，不能準確計算曲線上的采樣點。?

發明內容

本發明提供了一種基于像素精度的代數曲線光柵化方法，克服了現有技術的代數曲線繪制方法繪制效率較低以及繪制曲線精度不高的問題。?

一種基于像素精度的代數曲線光柵化方法，包括以下步驟：?

(1)輸入待繪制的代數曲線及其相關信息；?

(2)將該曲線的特征點限制在一個像素范圍內，得到若干包含曲線特征點的特征區域；

如沒有特殊說明，本文中的曲線即指待繪制的代數曲線。?

(3)求得曲線與所述特征區域邊界的交點，通過所述的交點構建曲線在特征區域的拓撲連接信息；?

(4)根據特征區域邊界的交點確定曲線的走向，利用直線段連接相鄰的特征區域，得到直線段擬合曲線；所述的直線段通過特征區域邊界的交點；?

(5)對所述的直線段擬合曲線進行優化，繪制并顯示曲線。?

在本發明中，所述的特征區域定義為描述在像素精度內的刻畫曲線特征點的區域，特征區域通常包含特征點，但在具體實施過程中也有可能是包含曲線上非?？拷姆种€段。所述的特征點為曲線上的奇異點和曲線上切向垂直或者水平的點。?

下面結合附圖詳細介紹本發明的具體實施方式。?

優選地，步驟(2)中，所述的將該曲線的特征點限制在一個像素范圍內，得到若干包含曲線特征點的特征區域，包括步驟：?

(2.1)均勻細分該曲線的區域，得到細分后的子區域；?

(2.2)利用區間分析的方法確定每個子區域的值域范圍；判斷每個子區域內是否存在該曲線的特征點，若存在則繼續細分該子區域；?

(2.3)重復步驟(2.2)，直到包含特征點的子區域的區域面積小于一個像素；將該子區域作為所述的特征區域。?

優選地，步驟(3)中，所述的求得曲線與所述特征區域邊界的交點，包括步驟：?

(3.1)以所述的特征區域為中心，用若干像素面積已知的包圍盒包圍每個特征區域；?