一区卡通不卡在线,亚洲综合9

計(jì)算機(jī)中繪制曲線，通過貝塞爾曲線已經(jīng)滿足了我們大部分需求，但是其存在某些缺點(diǎn)，比如移動(dòng)某一個(gè)控制點(diǎn)會(huì)導(dǎo)致整個(gè)曲線發(fā)生變化，即無法局部控制曲線的走向。所以 B 樣條曲線(B-Spline)為了解決貝塞爾曲線的缺陷應(yīng)運(yùn)而生。

什么是 B 樣條曲線？
解釋 B 樣條曲線之前，首先要解釋一下什么是樣條。樣條是通過一組指定點(diǎn)集而生成平滑曲線的柔性帶。簡(jiǎn)單地說，B 樣條曲線就是通過控制點(diǎn)局部控制形狀的曲線。不太理解的同學(xué)可以通過本文底部的 demo 查看 B 樣條曲線中，控制點(diǎn)對(duì)曲線繪制的影響。

????最近工作要用B樣條曲線，就花時(shí)間研究了下。
????生成B樣條曲線 $C$ 首先需要有一系列控制點(diǎn) $p_i(i = 0, \cdots, n-1)$ ，然后在B樣條曲線看來，繪制主要就是插值。整體思想是按照一定的順序把控制點(diǎn)投影到一個(gè)一維區(qū)間，控制點(diǎn)投影到一維區(qū)域所在的位置叫做節(jié)點(diǎn) $knot_i$ ，和 $p_i$ 一一對(duì)應(yīng)。在這個(gè)一維區(qū)間上均勻取值，然后計(jì)算出在原空間對(duì)應(yīng)的位置即可得到 $C$ 。

控制點(diǎn)和節(jié)點(diǎn)對(duì)應(yīng)關(guān)系

????現(xiàn)在有一系列高維空間控制點(diǎn) $p_0, p_1, \cdots, p_{n - 1}$ ，一種很顯然的方式是將他們按照順序?qū)?yīng)為一維空間的 $0, \frac{1}{n - 1}, \frac{2}{n - 1}, \cdots, \frac{n - 2}{n- 1}, 1$ ，考慮到 $m$ 階B樣條插值每個(gè)點(diǎn)需要 $m + 1$ 個(gè)節(jié)點(diǎn)來控制生成，因此為了生成頭尾兩個(gè)控制點(diǎn)，節(jié)點(diǎn)的數(shù)量為 $n + m + 1$ ，一般節(jié)點(diǎn)的生成方法有均勻法，這里為了過頭尾兩個(gè)控制點(diǎn)，將節(jié)點(diǎn)設(shè)置成 $knot: \bigg\{ 0, \cdots, 0, \frac{1}{n - m}, \frac{2}{n - m}, \cdots, \frac{n - m - 1}{n - m}, 1,\cdots, 1 \bigg\}$ ，前后各有 $m + 1$ 個(gè) $0$ 和 $1$ ，分別用來生成第一個(gè)控制點(diǎn)和最后一個(gè)控制點(diǎn)。
????然后從區(qū)間 $[0, 1]$ 里面均勻采樣，比如采樣到 $t$ 的位置，該位置對(duì)應(yīng)的高維空間點(diǎn)為
$C_{deg}(t) = \sum_{0}^{n - 1} B_{i, deg}(t)p_i$

????可以看到其中的關(guān)鍵是求解控制點(diǎn)對(duì)應(yīng)的貢獻(xiàn)或者說是權(quán)重 $B_{i, deg}(t)$ 。這里首先來看0階的權(quán)重，如下所示
$B_{i, 0}(t) = \begin{cases} 1 & {knot_i \leq t < knot_{i + 1}} \\ 0 &\text{otherwise} \end{cases}$ 這可以認(rèn)為是一個(gè)最近鄰插值，實(shí)現(xiàn)后的效果類似信號(hào)處理里面0階保持。
????高階的權(quán)重通過如下的遞推式子得到
$B_{i, deg}(t) = \frac{t - knot_i}{knot_{i + deg} - kont_i} B_{i, deg - 1}(t) + \frac{kont_{i + deg + 1} - t}{knot_{i+deg+1} - knot_{i +1}} B_{i + 1, deg - 1}(t)$

????如果把 $knot_i$ 簡(jiǎn)寫成 $k_i$ ，則有
$B_{i, deg}(t) = \frac{t - k_i}{k_{i + deg} - k_i} B_{i, deg - 1}(t) + \frac{k_{i + deg + 1} - t}{k_{i+deg+1} - k_{i +1}} B_{i + 1, deg - 1}(t)$

????按照上面的公式得到的C++程序如下所示

void BSpline(vector<double> &point_x, vector<double> &point_y,
    vector<double> &plan_path_x, vector<double> &plan_path_y, int order = 3) {
    int knot_parameter = point_x.size() + order;
    vector<double> knot(knot_parameter + 1, 0.0);
    vector<double> b(knot_parameter * (order + 1), 0.0);

    for (int i = order; i < knot.size(); ++i) 
        knot[i] = (min((double)point_x.size(), i + 0.0) - order) / ((double)point_x.size() - order);
    
    for (int i = 0; i + 1 < plan_path_x.size(); ++i) {
        double t = i / (plan_path_x.size() - 0.0);

        for (int j = 0; j < knot_parameter; ++j) {
            if (knot[j] <= t && knot[j + 1] > t) b[j] = 1.0;
            else b[j] = 0.0;
        }

        for (int deg = 1; deg <= order; ++deg) {
            for (int j = 0; j + deg < knot_parameter; ++j) {
                b[deg * knot_parameter + j] = 0.0;
                if (knot[j + deg] != knot[j]) 
                    b[deg * knot_parameter + j] += 
                    (t - knot[j]) / (knot[j + deg] - knot[j]) * b[(deg - 1) * knot_parameter + j];
                if (knot[j + deg + 1] != knot[j + 1]) 
                    b[deg * knot_parameter + j] += 
                    (knot[j + deg + 1] - t) / (knot[j + deg + 1] - knot[j + 1]) * b[(deg - 1) * knot_parameter + j + 1];
            }
        }

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = 0; j < point_x.size(); ++j) {
            plan_path_x[i] += point_x[j] * b[order * knot_parameter + j];
            plan_path_y[i] += point_y[j] * b[order * knot_parameter + j];
        }
    }

    plan_path_x.back() = point_x.back();
    plan_path_y.back() = point_y.back();
}

????注意到系數(shù)矩陣b當(dāng)前 $deg$ 的值只取決于 $deg - 1$ 的值和前面更前面的值無關(guān)，按照動(dòng)態(tài)規(guī)劃的常規(guī)套路可以將系數(shù)矩陣進(jìn)行壓縮，優(yōu)化后的代碼如下所示

void BSpline(vector<double> &point_x, vector<double> &point_y,
    vector<double> &plan_path_x, vector<double> &plan_path_y, int order = 3) {
    int knot_parameter = point_x.size() + order;
    vector<double> knot(knot_parameter + 1, 0.0);
    vector<double> b(knot_parameter, 0.0);

    for (int i = order; i < knot.size(); ++i)
        knot[i] = (min((double)point_x.size(), i + 0.0) - order) / ((double)point_x.size() - order);

    for (int i = 0; i + 1 < plan_path_x.size(); ++i) {
        double t = i / (plan_path_x.size() - 0.0);

        for (int j = 0; j < knot_parameter; ++j) {
            if (knot[j] <= t && knot[j + 1] > t) b[j] = 1.0;
            else b[j] = 0.0;
        }

        for (int deg = 1; deg <= order; ++deg) {
            for (int j = 0; j + deg < knot_parameter; ++j) {
                if (knot[j + deg] != knot[j])
                    b[j] = (t - knot[j]) / (knot[j + deg] - knot[j]) * b[j];
                else b[j] = 0.0;
                if (knot[j + deg + 1] != knot[j + 1])
                    b[j] += (knot[j + deg + 1] - t) / (knot[j + deg + 1] - knot[j + 1]) * b[j + 1];
            }
        }

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = 0; j < point_x.size(); ++j) {
            plan_path_x[i] += point_x[j] * b[j];
            plan_path_y[i] += point_y[j] * b[j];
        }
    }

    plan_path_x.back() = point_x.back();
    plan_path_y.back() = point_y.back();
}

????注意到根據(jù)前面的0階表達(dá)式，每個(gè) $t$ 只有一個(gè) $B_{i, 0}$ 不為0，剩下的均為0，因此在階數(shù)較小的情況下可以考慮直接寫出表達(dá)式，注意到下面表達(dá)式中的 $i$ 均滿足 $k_i \leq t < k_{i + 1}$ 。
????考慮到 $B_{i, 0}(t) = 1$ ，因此0階情況下的表達(dá)式為
$\begin{aligned} C_0(t) &= B_{i, 0}(t)p_i\\ &= p_i \end{aligned}$

????考慮到 $B_{i, 1}(t) = \frac{t - k_i}{k_{i + 1} - k_i} B_{i, 0}(t) + \frac{k_{i + 2} - t}{k_{i+2} - k_{i +1}} B_{i + 1, 0}(t)$ ，因此1階情況下的表達(dá)式為
$\begin{aligned} C_1(t) &= B_{i-1, 1}(t)p_{i-1} + B_{i, 1}(t)p_{i}\\ &= \frac{k_{i+1} - t}{k_{i + 1} - k_i} p_{i - 1} + \frac{t - k_i}{k_{i + 1} - k_i}p_i \end{aligned}$

????考慮到 $B_{i, 2}(t) = \frac{t - k_i}{k_{i + 2} - k_i} B_{i, 1}(t) + \frac{k_{i + 3} - t}{k_{i+3} - k_{i +1}} B_{i+1, 1}(t)$ ，因此2階情況下的表達(dá)式為
$\begin{aligned} C_2(t) &= B_{i - 2, 2}(t)p_{i - 2} + B_{i-1, 2}(t)p_{i-1} + B_{i, 2}(t)p_{i}\\ &= \frac{k_{i+1} - t}{k_{i + 1} - k_{i - 1}} B_{i-1, 1}(t)p_{i - 2} + \\ &\frac{t - k_{i - 1}}{k_{i + 1} - k_{i - 1}}B_{i - 1,1}(t)p_{i - 1} + \frac{k_{i +2} - t}{k_{i +2} - k_i}B_{i,1}(t)p_{i -1}+\\ &\frac{t - k_i}{k_{i+2} - k_i}B_{i,1}(t)p_i\\ &= \frac{k_{i+1} - t}{k_{i + 1} - k_{i - 1}} \frac{k_{i+1} - t}{k_{i+1} - k_i}p_{i - 2} +\\ &\frac{t - k_{i - 1}}{k_{i + 1} - k_{i - 1}}\frac{k_{i+1} - t}{k_{i+1}-k_i}p_{i -1} + \frac{k_{i +2} - t}{k_{i +2} - k_i}\frac{t - k_i}{k_{i+1} - k_i}p_{i -1} +\\ &\frac{t - k_i}{k_{i+2} - k_i}\frac{t - k_i}{k_{i +1}-k_i}p_i \end{aligned}$

????考慮到 $B_{i, 3}(t) = \frac{t - k_i}{k_{i + 3} - k_i} B_{i, 2}(t) + \frac{k_{i + 4} - t}{k_{i+4} - k_{i +1}} B_{i + 1, 2}(t)$ ，因此3階情況下的表達(dá)式為
$\begin{aligned} C_3(t) &= B_{i - 3, 3}(t)p_{i - 3} + B_{i-2, 3}(t)p_{i-2} + B_{i - 1, 3}(t)p_{i - 1} + B_{i, 3}(t)p_{i}\\ \end{aligned}$

????注意到每個(gè)點(diǎn)只由 $m +1$ 個(gè)控制點(diǎn)生成，計(jì)算系數(shù)的時(shí)候不需要遍歷整個(gè)節(jié)點(diǎn)和控制點(diǎn)，只需要遍歷你所需要的那幾個(gè)即可，因此前面的代碼可以優(yōu)化為

void BSpline(vector<double> &point_x, vector<double> &point_y,
    vector<double> &plan_path_x, vector<double> &plan_path_y, int order = 3) {
    int cur_index = 0;
    int knot_parameter = point_x.size() + order;
    vector<double> knot(knot_parameter + 1, 0.0);
    vector<double> b(knot_parameter, 0.0);

    for (int i = order; i < knot.size(); ++i) 
        knot[i] = (min((double)point_x.size(), i + 0.0) - order) / ((double)point_x.size() - order);
    
    for (int i = 0; i + 1 < plan_path_x.size(); ++i) {
        double t = i / (plan_path_x.size() - 0.0);

        while (knot[cur_index] <= t) ++cur_index;
        b[cur_index - 1] = 1.0;

        for (int deg = 1; deg <= order; ++deg) {
            for (int j = cur_index - deg - 1; j < cur_index; ++j) {
                if (knot[j + deg] != knot[j]) 
                    b[j] = (t - knot[j]) / (knot[j + deg] - knot[j]) * b[j];
                else b[j] = 0.0;
                if (knot[j + deg + 1] != knot[j + 1]) 
                    b[j] += (knot[j + deg + 1] - t) / (knot[j + deg + 1] - knot[j + 1]) * b[j + 1];
            }
        }

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = cur_index - order - 1; j < cur_index; ++j) {
            plan_path_x[i] += point_x[j] * b[j];
            plan_path_y[i] += point_y[j] * b[j];
            b[j] = 0.0;
        }
    }

    plan_path_x.back() = point_x.back();
    plan_path_y.back() = point_y.back();
}

????前面的公式
$B_{i, deg}(t) = \frac{t - k_i}{k_{i + deg} - k_i} B_{i, deg - 1}(t) + \frac{k_{i + deg + 1} - t}{k_{i+deg+1} - k_{i +1}} B_{i + 1, deg - 1}(t)$

????從數(shù)學(xué)上來看，系數(shù) $(i, deg)$ 是由上一層 $(i, deg - 1)$ 和 $(i + 1, deg - 1)$ 兩者共同組成，從另一個(gè)角度來看 $(i, deg)$ 的系數(shù)支持了下一層的 $(i - 1, deg + 1)$ 和 $(i, deg + 1)$ 兩者。前面的兩段代碼采用的是前者的寫法，考慮到整個(gè)數(shù)據(jù)最開始只有一個(gè)地方為1，因此采用后者寫法可以進(jìn)一步減少計(jì)算量，只計(jì)算已知非0值的位置。后一種寫法的數(shù)學(xué)公式表達(dá)如下
$\begin{aligned} \frac{k_{i + deg + 1} - t}{k_{i + deg + 1} - k_i} B_{i, deg}(t) &\to B_{i - 1, deg + 1}(t)\\ \frac{t - k_i}{k_{i+deg+1} - k_{i}} B_{i, deg}(t) &\to B_{i, deg + 1}(t) \end{aligned}$

????注意到上式中的系數(shù)滿足 $\frac{k_{i + deg + 1} - t}{k_{i + deg + 1} - k_i} +\frac{t - k_i}{k_{i+deg+1} - k_{i}} = 1$ ，在計(jì)算時(shí)可以利用該性質(zhì)，減少計(jì)算量。
????進(jìn)一步優(yōu)化過后的代碼如下

void BSpline(vector<double> &point_x, vector<double> &point_y,
    vector<double> &plan_path_x, vector<double> &plan_path_y, int order = 3) {
    int cur_index = 0;
    int knot_parameter = point_x.size() + order;
    vector<double> knot(knot_parameter + 1, 0.0);
    vector<double> b(knot_parameter, 0.0);

    for (int i = order; i < knot.size(); ++i) 
        knot[i] = (min((double)point_x.size(), i + 0.0) - order) / ((double)point_x.size() - order);
    
    for (int i = 0; i + 1 < plan_path_x.size(); ++i) {
        double t = i / (plan_path_x.size() - 0.0);

        while (knot[cur_index] <= t) ++cur_index;
        b[cur_index - 1] = 1.0;

        for (int deg = 0; deg < order; ++deg) {
            for (int j = cur_index - deg - 1; j < cur_index; ++j) {
                double p = 0.0;
                if (knot[j + deg + 1] != knot[j])
                    p = (knot[j + deg + 1] - t) / (knot[j + deg + 1] - knot[j]);

                b[j - 1] += p * b[j];
                b[j] *= (1.0 - p);
            }
        }

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = cur_index - order - 1; j < cur_index; ++j) {
            plan_path_x[i] += point_x[j] * b[j];
            plan_path_y[i] += point_y[j] * b[j];
            b[j] = 0.0;
        }
    }

    plan_path_x.back() = point_x.back();
    plan_path_y.back() = point_y.back();
}

????繼續(xù)優(yōu)化得到代碼

void BSpline(vector<double>& point_x, vector<double>& point_y,
    vector<double>& plan_path_x, vector<double>& plan_path_y, int order = 3) {
    int cur_index = 0;
    double step = (point_x.size() - order + 0.0) / plan_path_x.size();
    int knot_parameter = point_x.size() + order;
    vector<int> knot(knot_parameter + 1, 0.0);
    vector<double> b(knot_parameter, 0.0);

    for (int i = order; i < knot.size(); ++i) knot[i] = min(i, (int)point_x.size()) - order;

    for (int i = 0; i + 1 < plan_path_x.size(); ++i) {
        double t = i * step;

        while (knot[cur_index] <= t) ++cur_index;
        b[cur_index - 1] = 1.0;

        for (int deg = 0; deg < order; ++deg) {
            for (int j = cur_index - deg - 1; j < cur_index; ++j) {
                int knot_temp = knot[j + deg + 1];
                double p = knot_temp - knot[j];
                if (p) p = (knot_temp - t) / p;

                b[j - 1] += p * b[j];
                b[j] *= (1.0 - p);
            }
        }

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = cur_index - order - 1; j < cur_index; ++j) {
            plan_path_x[i] += point_x[j] * b[j];
            plan_path_y[i] += point_y[j] * b[j];
            b[j] = 0.0;
        }
    }

    plan_path_x.back() = point_x.back();
    plan_path_y.back() = point_y.back();
}

????注意到設(shè)置 $knot$ 的時(shí)候，除了頭尾添加的0和1以外，節(jié)點(diǎn) $knot$ 等分了區(qū)間 $[0,1]$ ，利用該性質(zhì)對(duì)前面的遞推公式做變換可以得到
$\begin{aligned} B_{i, deg}(t) &= \frac{t - k_i}{k_{i + deg} - k_i} B_{i, deg - 1}(t) + \frac{k_{i + deg + 1} - t}{k_{i+deg+1} - k_{i +1}} B_{i + 1, deg - 1}(t) \\ &= \frac{t - k_i}{k_{i + 1} - k_i}\frac{k_{i + 1} - k_i}{k_{i + deg} - k_i}B_{i, deg - 1}(t) + \\ & \bigg(1 + \frac{k_{i + 1} - t}{k_{i+deg+1} - k_{i +1}} \bigg) B_{i + 1, deg - 1}(t) \\ &= \frac{t - k_i}{k_{i + 1} - k_i}\frac{k_{i + 1} - k_i}{k_{i + deg} - k_i}B_{i, deg - 1}(t) + \\ & \bigg(1 + \frac{k_{i + 1} - t}{k_{i + 1} - k_i}\frac{k_{i + 1} - k_i}{k_{i+deg+1} - k_{i +1}} \bigg) B_{i + 1, deg - 1}(t) \\ &= \frac{t - k_i}{k_{i + 1} - k_i}\frac{1}{deg}B_{i, deg - 1}(t) + \bigg(1 + \frac{k_{i + 1} - t}{k_{i + 1} - k_i}\frac{1}{deg} \bigg) B_{i + 1, deg - 1}(t) \end{aligned}$
????令$$

沒時(shí)間寫了，先放上程序再說

void BSpline(vector<double>& point_x, vector<double>& point_y,
    vector<double>& plan_path_x, vector<double>& plan_path_y, int order = 3) {
    int cur_index = 0;
    double step = (point_x.size() - 1.0) / (plan_path_x.size() - 1.0);
    vector<int> knot(point_x.size() + 2 * order, 0.0);
    vector<double> b(point_x.size() + order, 0.0);

    for (int i = 0; i < knot.size(); ++i) knot[i] = i + 1 - order;

    for (int i = 1; i + 1 < plan_path_x.size(); ++i) {
        double t = i * step;

        while (knot[cur_index] <= t) ++cur_index;
        b[cur_index] = 1.0;

        for (int deg = 0; deg < order; ++deg) {
            for (int j = cur_index - deg; j <= cur_index; ++j) {
                int knot_temp = knot[j + deg];
                double p = (knot_temp - t) / (knot_temp - knot[j - 1]);

                b[j - 1] += p * b[j];
                b[j] *= (1.0 - p);
            }
        }

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = cur_index - order; j <= cur_index; ++j) {
            int point_index = min(max(j - order / 2, 0), (int)point_x.size() - 1);
            plan_path_x[i] += point_x[point_index] * b[j];
            plan_path_y[i] += point_y[point_index] * b[j];
            b[j] = 0.0;
        }
    }

    plan_path_x[0] = point_x[0];
    plan_path_y[0] = point_y[0];

    plan_path_x.back() = point_x.back();
    plan_path_y.back() = point_y.back();
}

void BSpline3(vector<double>& point_x, vector<double>& point_y,
    vector<double>& plan_path_x, vector<double>& plan_path_y, int order = 3) {
    int cur_index = 0;
    double step = (point_x.size() - 1.0) / (plan_path_x.size() - 1.0);
    vector<double> point_x_extended(point_x.size() + order, 0.0);
    vector<double> point_y_extended(point_y.size() + order, 0.0);
    vector<int> knot(point_x.size() + order, 0.0);
    vector<double> b(order + 1, 0.0);

    for (int i = 0; i < knot.size(); ++i) knot[i] = i + 1 - order;

    for (int i = 0; i < point_x_extended.size(); ++i) {
        int ii = i - order / 2;

        if (ii < 0) {
            point_x_extended[i] = 2 * point_x[0] - point_x[1];
            point_y_extended[i] = 2 * point_y[0] - point_y[1];
            continue;
        }

        if (ii >= point_x.size()) {
            point_x_extended[i] = 2 * point_x[point_x.size() - 1] - point_x[point_x.size() - 2];
            point_y_extended[i] = 2 * point_y[point_x.size() - 1] - point_y[point_x.size() - 2];
            continue;
        }

        point_x_extended[i] = point_x[ii];
        point_y_extended[i] = point_y[ii];
    }

    for (int i = 0; i < plan_path_x.size(); ++i) {
        double t = i * step;

        while (knot[cur_index] <= t) ++cur_index;

        t = t - knot[cur_index - 1];

        b[0] = (-t * t * t + 3 * t * t - 3 * t + 1) / 6.0;
        b[1] = (3 * t * t * t - 6 * t * t + 4) / 6.0;
        b[2] = (-3 * t * t * t + 3 * t * t + 3 * t + 1) / 6.0;
        b[3] = t * t * t / 6.0;

        plan_path_x[i] = 0.0;
        plan_path_y[i] = 0.0;
        for (int j = 0; j <= order; ++j) {
            plan_path_x[i] += point_x_extended[cur_index - order + j] * b[j];
            plan_path_y[i] += point_y_extended[cur_index - order + j] * b[j];
        }
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

B樣條曲線繪制

B樣條曲線繪制

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

B樣條曲線繪制

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av