|
原文地址：http://www./research/
bezier_interpolation/index.html#PAGE_BEZIER_INTERPOLATION
Interpolation with Bezier Curves 貝塞爾插值
A very simple method of smoothing polygons 一種非常簡單的多邊形平滑方法
翻譯：唐風(fēng)
之前 comp.graphic.algorithms 上有一個(gè)討論，是關(guān)于怎么樣使用曲線對多邊形進(jìn)行插值處理，使得最終產(chǎn)生的曲線是光滑的而且能通過所有的頂點(diǎn)。Gernot Hoffmann 建議說使用著名的 B-Spline 來進(jìn)行插值。這里有他當(dāng)時(shí)的文章。B-Spline 在這里效果很好，它看起來就像是一個(gè)固定在多邊形頂點(diǎn)上的橡皮尺（elastic ruler）。
 
 但我有個(gè)大膽的推測，我覺得肯定還存在更簡單的方法。比如，使用三次貝塞曲線(cubic Bezier)進(jìn)行近似。貝塞爾曲線有兩個(gè)固定點(diǎn)（起點(diǎn)和終點(diǎn)），另加兩個(gè)決定曲線形狀的控制點(diǎn)(CP）。關(guān)于貝塞爾曲線的更多知識(shí)可以在搜索引擎中找到，比如，你可以參考 Paul Bourke 的站點(diǎn) 。 現(xiàn)在給貝塞爾曲線的錨點(diǎn)（固定點(diǎn)），也就是多邊形的某一對頂點(diǎn)，那么問題是，我們怎么計(jì)算控制點(diǎn)的位置？我運(yùn)行 Xara X 然后畫出了右邊這個(gè)圖形，這很簡單，所以我決定嘗試下計(jì)算出它們的坐標(biāo)。很顯然，多邊形兩條相鄰邊的兩個(gè)控制點(diǎn)與這兩個(gè)控制點(diǎn)之間的頂點(diǎn)應(yīng)該在一條直線 上，只有這樣，兩條相鄰的插值曲線才能平滑地連接在一起。所以，這兩個(gè)控制點(diǎn)應(yīng)該是相對于頂點(diǎn)是對稱的，不過，也不全是……，因?yàn)檎嬲膶ΨQ就要求它們與 中心點(diǎn)的距離應(yīng)該是相等的，但對于我們的情況中并不完全是這樣的。一開始，我試著先算出多邊形兩條邊的角平分線，然后把控制點(diǎn)放在這條角平分線的垂直線 上。但從圖上可以看到，控制點(diǎn)的連線并不會(huì)總是垂直于角平分線的。
最終，我找到一個(gè)非常簡單的辦法，不需要任何復(fù)雜的數(shù)學(xué)計(jì)算。首先，我們計(jì)算出多邊形所有邊線的中點(diǎn)，Ai。
然后連接起相鄰邊中點(diǎn)，得到很多線段，記為 Ci 。并用圖記的方法計(jì)算出 Bi 點(diǎn)。
最后一步，只需要簡單地將 Ci 進(jìn)行平移，平移的路徑就是每條線段上 Bi 到對應(yīng)頂點(diǎn)的路徑。就這樣，我們計(jì)算出了貝塞爾曲線的控制點(diǎn)，平滑的結(jié)果看起來也很棒。
這里還可以做一點(diǎn)小小的改進(jìn)，因?yàn)槲覀円呀?jīng)得到了一條決定控制點(diǎn)的直線，所以，我們可以根據(jù)需要，使控制點(diǎn)在這條直線上移動(dòng)，這樣可以改變插值曲線 的狀態(tài)。我使用了一個(gè)與控制點(diǎn)和頂點(diǎn)初始距離相關(guān)的系數(shù) K ，用來沿直線移動(dòng)控制點(diǎn)?？刂泣c(diǎn)離頂點(diǎn)越遠(yuǎn)，圖形看起來就越銳利。
下面是用原始形狀和系統(tǒng)K=1.0的貝塞爾插值兩種方法來描畫的 SVG 的獅子。
 
下面是放大圖
 
這個(gè)方法對于自相關(guān)的多邊形也適用，下面的例子可以看到，結(jié)果非常有意思：
這個(gè)方法只是探索和經(jīng)驗(yàn)式的，如果從嚴(yán)格的數(shù)學(xué)模型的角度看它可能是錯(cuò)誤的。但在實(shí)際使用中的效果已經(jīng)足夠好了，而 且這個(gè)方法只需要最小的計(jì)算量。下面的代碼就是用來畫出上面獅子圖像的。這些代碼并沒有進(jìn)行優(yōu)化，只是用來演示的。里面有些變量計(jì)算了兩次，在實(shí)際程序 中，如果連續(xù)的步驟中都用到同一個(gè)變量值，我們可以先緩存變量值進(jìn)行復(fù)用（以避免重復(fù)的計(jì)算）。
This method is pure heuristic and empiric. It probably gives
a wrong result from the point of view of strict mathematical
modeling. But in practice the result is good enough and it
requires absolute minimum of calculations. Below is the source code
that has been used to generate the lions shown above. It's
not optimal and just an illustration. It calculates some variables
twice, while in real programs we can store and reuse them in the
- // Assume we need to calculate the control
- // points between (x1,y1) and (x2,y2).
- // Then x0,y0 - the previous vertex,
- // x3,y3 - the next one.
-
- double xc1 = (x0 + x1) / 2.0;
- double yc1 = (y0 + y1) / 2.0;
- double xc2 = (x1 + x2) / 2.0;
- double yc2 = (y1 + y2) / 2.0;
- double xc3 = (x2 + x3) / 2.0;
- double yc3 = (y2 + y3) / 2.0;
-
- double len1 = sqrt((x1-x0) * (x1-x0) + (y1-y0) * (y1-y0));
- double len2 = sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
- double len3 = sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2));
-
- double k1 = len1 / (len1 + len2);
- double k2 = len2 / (len2 + len3);
-
- double xm1 = xc1 + (xc2 - xc1) * k1;
- double ym1 = yc1 + (yc2 - yc1) * k1;
-
- double xm2 = xc2 + (xc3 - xc2) * k2;
- double ym2 = yc2 + (yc3 - yc2) * k2;
-
- // Resulting control points. Here smooth_value is mentioned
- // above coefficient K whose value should be in range [0...1].
- ctrl1_x = xm1 + (xc2 - xm1) * smooth_value + x1 - xm1;
- ctrl1_y = ym1 + (yc2 - ym1) * smooth_value + y1 - ym1;
-
- ctrl2_x = xm2 + (xc2 - xm2) * smooth_value + x2 - xm2;
- ctrl2_y = ym2 + (yc2 - ym2) * smooth_value + y2 - ym2;
consecutive steps.
使用三次貝塞爾近似的代碼：
- // Number of intermediate points between two source ones,
- // Actually, this value should be calculated in some way,
- // Obviously, depending on the real length of the curve.
- // But I don't know any elegant and fast solution for this
- // problem.
- #define NUM_STEPS 20
-
- void curve4(Polygon* p,
- double x1, double y1, //Anchor1
- double x2, double y2, //Control1
- double x3, double y3, //Control2
- double x4, double y4) //Anchor2
- {
- double dx1 = x2 - x1;
- double dy1 = y2 - y1;
- double dx2 = x3 - x2;
- double dy2 = y3 - y2;
- double dx3 = x4 - x3;
- double dy3 = y4 - y3;
-
- double subdiv_step = 1.0 / (NUM_STEPS + 1);
- double subdiv_step2 = subdiv_step*subdiv_step;
- double subdiv_step3 = subdiv_step*subdiv_step*subdiv_step;
-
- double pre1 = 3.0 * subdiv_step;
- double pre2 = 3.0 * subdiv_step2;
- double pre4 = 6.0 * subdiv_step2;
- double pre5 = 6.0 * subdiv_step3;
-
- double tmp1x = x1 - x2 * 2.0 + x3;
- double tmp1y = y1 - y2 * 2.0 + y3;
-
- double tmp2x = (x2 - x3)*3.0 - x1 + x4;
- double tmp2y = (y2 - y3)*3.0 - y1 + y4;
-
- double fx = x1;
- double fy = y1;
-
- double dfx = (x2 - x1)*pre1 + tmp1x*pre2 + tmp2x*subdiv_step3;
- double dfy = (y2 - y1)*pre1 + tmp1y*pre2 + tmp2y*subdiv_step3;
-
- double ddfx = tmp1x*pre4 + tmp2x*pre5;
- double ddfy = tmp1y*pre4 + tmp2y*pre5;
-
- double dddfx = tmp2x*pre5;
- double dddfy = tmp2y*pre5;
-
- int step = NUM_STEPS;
-
- // Suppose, we have some abstract object Polygon which
- // has method AddVertex(x, y), similar to LineTo in
- // many graphical APIs.
- // Note, that the loop has only operation add!
- while(step--)
- {
- fx += dfx;
- fy += dfy;
- dfx += ddfx;
- dfy += ddfy;
- ddfx += dddfx;
- ddfy += dddfy;
- p->AddVertex(fx, fy);
- }
- p->AddVertex(x4, y4); // Last step must go exactly to x4, y4
- }
你可以下載一個(gè)能運(yùn)行的畫獅子的例子，對它進(jìn)行旋轉(zhuǎn)和縮放，也可以生成一些隨機(jī)的多邊形。點(diǎn)左鍵并拖動(dòng)它可以圍繞中 心點(diǎn)旋轉(zhuǎn)和縮放圖像。點(diǎn)右鍵并從左向右拖動(dòng)，可以改變系統(tǒng)數(shù)K。 K＝1時(shí)大約是距窗口左邊100像素處。每次雙擊會(huì)產(chǎn)生一個(gè)隨機(jī)的多邊形，對于這些多邊形，也可以進(jìn)行旋轉(zhuǎn)、縮放以及改變K值的操作。
|
