<bdo id="4g88a"><xmp id="4g88a">
  • <legend id="4g88a"><code id="4g88a"></code></legend>

    貝塞爾曲線的切線及其AABB問題

    貝塞爾曲線的切線及其AABB問題

    先聊點別的

    2023 年抖音上居然還看到很多前端培訓

    各種直播前端教學(雖然是錄播)但看起來還是有大批前往前端卷啊

    說明了什么,很可能說明其它行業更難卷

    這不是行業不景氣業務下降了么..

    互聯網行業是肉眼可見的不景氣

    業務量也下降了,業務相關的工作也變的不再飽和

    我這 80 后的工作積極性降低了,啊..開始擺爛了

    我還好趕上了前端發展的草莽時期,否則估計也進不了這個行檔

    怎么形容我自己呢,對編程是又菜又愛

    可以將時間花一部分在自己感興趣的內容上了,想到哪里干到哪里

    而最近在翻譯文章時貝塞爾曲線又回顧了一下

    這讓我想起了 2020 年遇到過的一個技術問題:曲線的 AABB

    (另外還想到了兩個其它問題也需要攻克一下, 怎么莫名的想到了魯訊先生的朝花夕拾.. 果然是年紀大了..)

    AABB 即圖形界中常說的 AABB (axis-aligned bounding box) 包圍盒, 嚴格來說是未能實現 BB

    規則的圖形很容易通過頂點距離就可以計算出 BB, 但像貝塞爾曲線這樣的曲線就不太好算

    是時候解決一下了

    要實現的效果

    image

    image

    image

    2020 年寫微信小程序

    在當年寫了個簡單繪圖庫

    那是在 2020 年上一家公司,公司安排我負責微信小程序的開發

    其中經常要用微信小程序生成海報,保存在圖片用于在手機上的傳播

    單獨手工去拼接生成海報還是比較麻煩的, Canvas 提供的 api 相對比較低級,

    當時看到一些人開源出來的類似 json 配置形式生成海報圖

    這種配置類型的實現原理是大多是通過配置的坐標,大小,顏色,以及一些簡單的 CSS 樣式解析后在 canvas 上繪制

    相對于純手工去畫,確實簡單很多

    但我更喜歡 Pixi.js、EaseJs 這類圖形庫的風格

    當時就抽空寫了一個簡易的 Canvas 操作庫 DuduCanvas

    DuduCanvas 基本封裝實現了圖片,文本,形狀等相關對象的繪制

    調用的方式相比于配置要稍低級一點,擁有更大的自由度,例如添加一個圓形的頭像圖片:

    const avatar = new Image({
          image: loader.get('avatar'),
          width: 100, 
          height: 100,
    })
    
    // 將頭像變成圓形
    avatar.borderRadius = '100%'
    
    // 添加一個文本
    const t1 = new Text()
    t1.text = '你好世界Hello'
    t1.color = 'red'
    t1.x = 100
    t1.y = 300
    // 添加到舞臺
    stage.addChild(img, t1)
    
    

    至少對于當時的項目來講,DuduCanvas 運行的還不錯,畢竟不是用它做動畫或者游戲

    image

    image

    還好,我代碼存到了 github 上,在新公司臨時做項目時還派上了用場用它畫了個積分統計圖

    image

    但它有幾個缺點:

    1. 沒有實現事件系統,當然它大部分時間只是用于生成海報,用不到事件交互

    2. 繪制曲線圖形后的 BB 未能實現,需要自己手動指定

    3. 由于是 2020 年 當時微信小程序的 Canvas 2D 版本還牌測試版,所以使用的舊版 Canvas API

    4. graphics 實現過于簡單好多重復命令未去除

    5. 未能實現曲線的寬高計算(BB)

    沒過多久離職了,工作重心也從小程序轉到其它前端項目

    之后就沒再管它

    https://github.com/willian12345/DuduCanvas

    2023 年我嘗試著用微信開發者工具打開看了一下,還能運行

    三階貝塞爾曲線的 BB

    之前在翻譯 貝塞爾曲線文字路徑 一文中提到過三階貝塞爾曲線

    它是用 C# 偽代碼來講解的

    定義 4 個控制點:

    (x1, y1), (x2, y2), (x3, y3), (x4,y4)
    

    定義 A..H 系數

    A = x3 - 3 * x2 + 3 * x1 - x0
    B = 3 * x2 - 6 * x1 + 3 * x0
    C = 3 * x1 - 3 * x0
    D = x0
    
    E = y3 - 3 * y2 + 3 * y1 - y0
    F = 3 * y2 - 6 * y1 + 3 * y0
    G = 3 * y1 - 3 * y0
    H = y0
    

    得到多項式:

    x = At3 + Bt2 + Ct + D 
    y = Et3 + Ft2 + Gt + H 
    

    那么我們先用 Javascript 實現一下那篇文章中提到過的垂直于曲線的單位向量

    假設我們要繪制的三階貝塞爾曲線的四個控制點

    [
          { x: 120, y: 320 },
          { x: 135, y: 440 },
          { x: 320, y: 280 },
          { x: 480, y: 340 },
    ];
    

    下面是它三階貝塞爾曲線采樣點,t 取值 0-1 :

    // 用 t 獲取“樣條曲線” 采樣點
    let sx = A * Math.pow(t, 3) + B * Math.pow(t, 2) + C * t + D
    let sy = E * Math.pow(t, 3) + F * Math.pow(t, 2) + G * t + H
    

    sx, sy 就是 t 從 0 - 1 時算出的曲線上的每個點

    如果 t 取值足夠小,那么在 canvas 上畫出所有的點它就是一條貝塞爾曲線

    t 間隔為 0.1 時:

    image

    t 間隔為 0.001 時:
    image

    畫出垂直于曲線的向量關鍵, 在于對三階貝塞爾曲線多項式的求導

    如果你忘記了什么是求導(導函數), 沒關系, 直接用公式就完了

    我這個學渣都會用,你肯定也可以,

    當然最好是回去復習一下高中后期的導函數部分,有助于理解曲線切線的幾何意義

    求導后得到向量:

    // 求導前
    x = At3 + Bt2 + Ct + D 
    y = Et3 + Ft2 + Gt + H 
    
    // 求導后
    Vx = 3At2 + 2Bt + C 
    Vy = 3Et2 + 2Ft + G 
    

    用 Javascript 實現如下:

    // (求導)用于計算曲線上采樣點的切線向量
    let tx = 3 * A * Math.pow(t, 2) + 2 * B * t + C
    let ty = 3 * E * Math.pow(t, 2) + 2 * F * t + G
    
    // 旋轉 90 度或 270 度垂直于曲線采樣點
    let px = ty
    let py = -tx
    
    // 縮至單位向量
    let magnitude = Math.sqrt(px * px + py * py)
    px = px / magnitude
    py = py / magnitude
    
    // 為了向量可見,擴大 20 個單位
    px *= 20;
    py *= 20;
    
    // 從采樣點連接至切線向量偏移位置
    console.log(sx + px, sy + py);
    

    image

    源碼盡量平鋪直敘:...

    https://github.com/willian12345/blogpost/blob/main/curve/bezier/cubic-bezier-tangent-test.html

    如果你對貝塞爾曲線感興趣還可以看一下我翻譯的《曲線編程藝術》的 貝塞爾曲線 這一章

    把三階貝塞爾曲線包起來

    要實現三階貝塞爾曲線的AABB(包圍合)還是得從切線入手

    比如像下面這個曲線

    let points = [
          {x: 120, y: 160 }, 
          {x:  35, y: 200 }, 
          {x: 220, y: 260 }, 
          {x: 180, y:  40 }, 
    ];
    

    四個點得出的結果:

    image

    先把它的四個點用直線連接畫出來

    ctx.beginPath();
    ctx.lineWidth = 2;
    ctx.setLineDash([1, 2]);
    ctx.strokeStyle = '#076c75';
    ctx.moveTo(points[0].x, points[0].y);
    ctx.lineTo(points[1].x, points[1].y);
    ctx.stroke()
    
    ctx.beginPath();
    ctx.lineWidth = 1;
    ctx.moveTo(points[1].x, points[1].y);
    ctx.strokeStyle = 'black';
    ctx.lineTo(points[2].x, points[2].y);
    ctx.stroke()
    
    ctx.beginPath();
    ctx.lineWidth = 2;
    ctx.strokeStyle = '#076c75';
    ctx.moveTo(points[2].x, points[2].y);
    ctx.lineTo(points[3].x, points[3].y);
    ctx.stroke();
    

    image

    藍色的線就像是控制手柄

    點 points[1] 和 points[2] 分別就是控制手柄

    控制手柄就是 PS 內的鋼筆工具用過吧?就是這個,長短與位置調節就控制了曲線的形狀

    BB 包圍盒就是找到曲線所有轉折點中最小和最大的轉折點

    找轉折點,可理解為找到曲線上的斜率

    還是從公式入手

    在上一節中貝塞爾公式系數直接把 x, y 都用 A..H 表示出來了

    這次先簡化到一維比如 x , 系數用 A..D 表示

    x 坐標方程即(y 軸坐標方程其實是一樣的,只是算了兩遍):

    x = A (1-t)^3 +3 B t (1-t)^2 + 3 C t^2 (1-t) + D t^3
    

    對其求導,關于 t 的微分,得到微分方程

    dx/dt =  3 (B - A) (1-t)^2 + 6 (C - B) (1-t) t + 3 (D - C) t^2
          =  [3 (D - C) - 6 (C - B) + 3 (B - A)] t^2
          + [ -6 (B - A) - 6 (C - B)] t
          + 3 (B - A) 
          =  (3 D - 9 C + 9 B - 3 A) t^2 + (6 A - 12 B + 6 C) t + 3 (B - A)
    

    合并整理后是一個二次函數:

    dx/dt = (3 D - 9 C + 9 B - 3 A) t^2 + (6 A - 12 B + 6 C) t + 3 (B - A)
    

    用其 a, b, c 簡化系數代替后:

    dx/dt = a t^2 + b t + c
    

    我們要解決的是 dx/dt = 0

    "斜率為 0 可能意味著曲線在該點處有一個極小值或極大值,或者曲線在該點處是一個水平切線"

    反正我這個學渣是這么理解的

    那么就是對二交方程求解

    a t^2 + b t + c = 0

    可用求根公式

    - b +/- sqrt(b^2-4 a c)
    -----------------------
          2 a
    

    解方程可得 兩個解(根) t0, t1, 無解,或 1 個解

    這就有了四個點的極值,起點,終點,和兩個解

    系數 a, b, c 就是根據公式代入, 比如 x 的坐標代入后:

    let a = 3 * points[3].x - 9 * points[2].x + 9 * points[1].x - 3 * points[0].x;
    let b = 6 * points[0].x - 12 * points[1].x + 6 * points[2].x;
    let c = 3 * points[1].x - 3 * points[0].x;
    

    還記得初中數學如何判斷二次函數有幾個根吧?

    delta 即 b^2-4ac 判斷 大于等于 0 即為有解

    let delta = b * b - 4 * a * c;
    

    判斷有解后找到局部極限值 (local extreme)

    代入求根公式:

    t1 = (-b + Math.sqrt(delta)) / (2 * a);
    t2 = (-b - Math.sqrt(delta)) / (2 * a);
    

    我們只關心 0 <= t <= 1 的情況

    將得到和 t1, t2 分別代入貝塞爾曲線公式

    x = A (1-t)^3 +3 B t (1-t)^2 + 3 C t^2 (1-t) + D t^3
    

    得到的就是真實的 x 坐標值,

    所以需 x 要判斷

    if (x < xl) xl = x;
    if (x > xh) xh = x;
    

    記住是求出的二個根 t1, t2 分別代入判斷

    它有可能是最大值,也有可能是最小值 記作: xl, xh

    對 y 同樣進行一模一樣的計算,t3, t4 也可以得到一最大值與最小值 記作:yl, yh

    將它們從起點 左下,左上,右上,右下,左下終點 的順序連接起來就是我們要的 BB 包圍盒

    ctx.moveTo(xl, yl); // 起點,左下
    ctx.lineTo(xl, yh); // 左上
    ctx.lineTo(xh, yh); // 右上
    ctx.lineTo(xh, yl); // 右下
    ctx.lineTo(xl, yl); // 終點,左下
    

    image

    如上圖,包圍盒圍起來了,解決了計算貝塞爾曲線寬高計算的問題

    畫出切線驗證

    再把曲線的切線畫出來,這回我們不畫垂直向量,直接畫切線

    切線向量這道菜已經吃過了..

    將 t 步長設為 0.1, 進行曲線采樣, 畫出綠色的切線

    for( let t=0; t <=1; t += 0.1){
          // 繪制起點移動到對應的曲線點上
          const sx = calcBezierByT(pointXArray, t);
          const sy = calcBezierByT(pointYArray, t);
          ctx.moveTo(sx, sy)
    
          // a t^2 + b t + c 
          // 切線向量
          let vx = a1 * Math.pow(t,2) + b1 * t + c1
          let vy = a2 * Math.pow(t,2) + b2 * t + c2
          // 縮至單位向量
          let magnitude = Math.sqrt(vx * vx + vy * vy)
          // vx = -vx / magnitude;
          // vy = -vy / magnitude;
          vx = vx / magnitude;
          vy = vy / magnitude;
          // 向量長度變長 30 個單位
          vx *= 30
          vy *= 30
          ctx.strokeStyle = 'green';  
          ctx.lineTo(sx + vx,  sy + vy);
          }
          ctx.stroke();
    }
    
    

    image
    (綠色顏色有點兒淡了感覺...)

    代入上一節算出的 t1, t2, t3, t4 用紅色畫出局部極限值 (local extreme) 驗證

    注意 曲線不同,t1, t2, t3, t4 的值有可能有,有可能沒有,且我們需要的是 t1 >= 0

    需要這樣處理

    // 過濾
    const tArray = [t1, t2, t3, t4].filter((t)=> t >= 0);
    
    for( let i=0; i <= tArray.length; i++){
          ...與上面生成切線一樣,只是 t 值是從 tArray 獲取,而不是 0.1 步長
    }
    

    image

    可以看到,紅色標出的果然很 “極限”

    代入不同的坐標值看看

    const points = [
          { x: 20, y: 340 },
          { x: 50, y: 400 },
          { x: 320, y: 180 },
          { x: 480, y: 340 },
        ];
    

    image

    const points = [
    {x:  13, y: 224 }, 
    {x: 150, y: 100 },
    {x: 251, y:  93 }, 
    {x: 341, y: 224 }, 
    ];
    

    image
    (綠色顏色快看不出來了,PC上的微信截圖工具會模糊截圖...)

    可以看到,有些曲線極限值就不一定有四個

    https://github.com/willian12345/blogpost/blob/main/curve/bezier/aabb.html

    后續

    貝塞爾曲線雖然原理很簡單,但深入后就會特別復雜,你們好好深入,反正以我的能力是深入不了的

    作為一個打工人,就要有打工人的覺悟,主打一個隨意,沒必要在一個問題上死磕

    東看看,西看看,說不定回頭再來看問題,已具備足夠的知識與資料后就解決了

    創業公司麻,就是這么的不穩定,何況是在這樣一個環境下

    最近公司要讓我重新再接觸 unity ,這又繞回來了, c# 其實挺好的


    參考資料:

    https://developer.mozilla.org/zh-CN/docs/Web/API/CanvasRenderingContext2D/bezierCurveTo

    https://floris.briolas.nl/floris/2009/10/bounding-box-of-cubic-bezier/

    https://stackoverflow.com/questions/24809978/calculating-the-bounding-box-of-cubic-bezier-curve

    https://pomax.github.io/bezierinfo/#boundingbox


    博客園: http://cnblogs.com/willian/
    github: https://github.com/willian12345/

    posted @ 2023-09-26 13:53  池中物王二狗  閱讀(466)  評論(4編輯  收藏  舉報
    轉載入注明博客園 王二狗Sheldon Email: willian12345@126.com https://github.com/willian12345
    免费视频精品一区二区_日韩一区二区三区精品_aaa在线观看免费完整版_世界一级真人片
    <bdo id="4g88a"><xmp id="4g88a">
  • <legend id="4g88a"><code id="4g88a"></code></legend>