一種基于de Casteljau算法的Bezier曲線插補方法

宋健+桑運曉+劉同壯

摘 要：為了克服數據采樣法插補Bezier曲線必然會產生軌跡誤差而且運算量大、實時性不好的問題，以Paul de Casteljau在1959年提出的de Casteljau算法為理論依據，研究出了一種用DDA直線插補器級聯的方式遞推出任意階Bezier曲線的新方法。該方法用多個DDA直線插補器分級同時進行插補，前一級的輸出脈沖用來修正相鄰后一級的被積函數寄存器，最后一級輸出用來驅動進給。最后用Visual Studio 2010編寫了仿真程序進行了模擬插補，證實了其正確性。這個全新的加工Bezier曲線的方法更加準確、實時性更好，同時也為B樣條、NURBS等曲線的加工提供了嶄新的思路。

關鍵詞：Bezier曲線；直接插補；de Casteljau算法；DDA法

DOI：10.16640/j.cnki.37-1222/t.2017.12.220

0 引言

目前的CNC系統，對于直線和圓弧可以采用脈沖增量插補原理直接進行插補。而對于Bezier曲線、樣條曲線等的插補只能采用數據采樣插補原理，先進行粗插補，然后再用脈沖增量插補法對微小的直線段進行精插補。數據采樣法在原理上決定了其逼近的過程中肯定會產生軌跡誤差，而且插補程序比較復雜。為了避免數據采樣插補法所帶來的問題，在de Casteljau算法的幾何模型的啟發下，提出了用DDA法遞推插補出Bezier曲線的基本思想。

1 de Casteljau算法

de Casteljau算法最基本的過程就是在向量上取一個點C，使得C分向量為（即）。下文中稱此過程為在某線段（這里為）上取Bezier點。給定端點A和B的坐標以及的值，點C的坐標便為：。

當Bezier曲線階數大于等于2時，即可利用上述過程進行迭代，具體步驟如下。定義Bezier曲線的控制點編號為ij，其中i表示迭代次數，j表示每次迭代中的控制點序號。為了計算n階貝塞爾曲線（控制點個數為n+1）上的點C（），，首先將控制點依次連接形成一條折線00-01-02-……-0（n-1）-0n。按上述過程，在構成折線的每條線段上取Bezier點，總共有n個，記為10、11、12、……、1（n-2）、1（n-1），然后再把這些點依次連成一條折線10-11-12-……-1（n-2）-1（n-1），再在此折線的每條線段上取Bezier點，總共有n-1個，以此類推。

2 利用DDA法對Bezier曲線進行直接插補

在上述de Casteljau算法的理論基礎上，研究出了直接用直線插補迭代遞推出Bezier曲線的方法。

2.1 二階及以上Bezier曲線插補

由de Casteljau算法可知，二階Bezier曲線上的點可以按如下方法獲取：把控制點依次連成一條折線，在折線的每條線段上取Bezier點，再把兩個Bezier點連起來，在此連線上取Bezier點即為二階Bezier曲線上的點。要插補的線段是不斷變化的，線段的起點和終點要根據前一級插補的驅動脈沖進行修正。在所有的線段上用同一個插補控制脈沖進行插補即可插補出任意階Bezier曲線。

如圖1所示為DDA法直接插補二階Bezier曲線的原理框圖：

圖中和分別為三個控制點的橫坐標和縱坐標，和為最終驅動相應坐標軸的進給脈沖，為插補迭代控制脈沖。此處，需要強調的是三個插補脈沖為同一個，每來一個脈沖，三個插補器同時進行插補，六個被積函數寄存器中的值都要送往相應的積分累加器中相加一次。第一級的兩個插補器的溢出脈沖用來修正后一級插補器的被積函數寄存器的值。在第一級的第一個插補器中，當（或）時，（或）的溢出脈沖（或）為正，每輸出一個脈沖，第二級插補器對應的起點坐標就加一，即；當（或）時，（或）的溢出脈沖（或）為負，每輸出一個脈沖，第二級插補器對應的起點坐標就減一。同樣，第一級的第二個插補器每輸出一個脈沖，第二級插補器對應的終點坐標就加一或減一。第二級插補器的輸出脈沖用來驅動進給。更高階的Bezier曲線可以用上述同樣的方法進行推廣。

2.2 軟件模擬

最后，按照上述原理用微軟的托管C++語言——C++/CLI在Visual Studio 2010中編寫了模擬插補程序，在屏幕上畫線模擬機床的走刀路徑符合我們預期的設計， 此方法基本可以控制刀具插補出理論輪廓。

3 結論

此方法創新性的把de Casteljau算法運用到數控機床的插補過程中，研究出了用DDA法迭代遞推出Bezier曲線的理論，為Bezier曲線的加工提供了全新的、更加準確、實時性更好的方法，甚至也為B樣條、NURBS等曲線的加工提供了嶄新的思路。此類非圓曲線在實際中應用非常廣泛，尤其是在復雜輪廓的零件中，幾乎所有的專業建模軟件都提供了此類曲線建模工具，因此該方法將會對數控加工技術產生重要的影響。

參考文獻：

[1]SUH SH，KANG SK，CHUNG DH，et al.Theory and Design of CNC Systems[M].London：Springer-Verlag，2008：73-79.

[2]孫家廣.計算機圖形學3版[M].北京：清華大學出版社，1998： 301-326.

[3]Hearn D，Baker M P著，蔡士杰等譯.Computer Graphics with OpenGL 3rd ed[M].北京：電子工業出版社，2005：355-372.

[4]Boehm M，Müller A.On de Casteljau's algorithm[J].Computer Aided Geometric Design，1999，16（07）：587-605.

作者簡介：宋健（1991-），男，安徽亳州人，碩士研究生，主要研究方向：計算機控制技術。