4

我只想通过片段着色器绘制贝塞尔曲线来连接编辑器中的节点。我知道定义贝塞尔曲线的所有 4 个点。并且为每个像素调用片段着色器，所以我可以检查：如果 gl_Coord.x 的“t”在 0 和 1 之间，则例如将 frag_color 设置为红色。我想避免着色器中效率低下的循环。我认为最好的方法是检查曲线上的点。但是如何为贝塞尔曲线做呢？

是否可以从三次贝塞尔方程表达“t”变量？

x = ((1-t)^3 * p0.x) + (3 * (1-t)^2 * t * p1.x) + (3 * (1 - t) * t^2 * p2.x) + (t^3 * p3.x);

t = ?

网站 Wolfram Aplha 给了我那个公式（在 GetBezierT 函数中）。但是公式给了我错误的“t”值，我有一半的抛物线而不是曲线：

#version 150
.....
layout (origin_upper_left, pixel_center_integer) in vec4 gl_FragCoord;
out vec4 frag_color;
.....
vec4 BackgroundColor = vec4(0.15, 0.15, 0.15, 1.0);
vec2 p0 = vec2(61.0f,87.0f);
vec2 p1 = vec2(181.0f, 39.0f);
vec2 p2 = vec2(283.0f, 178.0f);
vec2 p3 = vec2(416.0f, 132.0f);

float getBezierT(float x, float a, float b, float c, float d)
{
      return  float(sqrt(3) * 
          sqrt(-4 * b * d + 4 * b * x + 3 * c * c + 2 * c * d - 8 * c * x - d * d + 4 * d * x) 
            + 6 * b - 9 * c + 3 * d) 
            / (6 * (b - 2 * c + d));
}

void main() {  
    .....
    frag_color = BackgroundColor; 
    .....
    float tx = getBezierT(gl_FragCoord.x, p0.x, p1.x, p2.x, p3.x);
    float ty = getBezierT(gl_FragCoord.y, p0.y, p1.y, p2.y, p3.y);

    if (tx >= 0.0f && tx <= 1.0f && ty >= 0.0f && ty <= 1.0f)
    {
        if(abs(tx-ty) <  0.01f) // simple check is that one point with little bias
        frag_color = vec4(1.0f, 0.0f, 0.0f, 1.0f);
    }
}

更新

犯了个错误。我认为没有必要寻找t。我以为我会忍受它。但是在得到Salix albaand的答案后Stratubas，我意识到如果tX等于tY，这意味着该点将位于曲线上，因为在公式中，每个点的一个值t都代替了xand y。也许有些情况不同tX，tY也可以在这条曲线上给出一个点，但我们可以忽略它。构造贝塞尔曲线的算法意味着我们将其线性增加t并将其代入公式中，无论曲线扭曲多少，该算法都会沿曲线顺序返回每个下一个点的坐标。

因此，首先，我再次打开这个问题：如何从三次贝塞尔方程中表达变量 t？

试图表达 t，但这对我来说非常困难。有必要为“科学目的”评估这种方法的有效性=）。在这里问一个问题之前，我搜索了很多，但从未发现有人会尝试使用这种方法。我需要明白为什么。

更新 2

你做得很好！没想到会收到这么详细的回答。正是我需要的。给我时间检查一切=）

更新 3

t结论：来自三次贝塞尔方程的准确表达。耗时的任务，但近似值没有实际用途。为解决这一问题，需要对方程数据进行分析，寻找规律，开发新的贝塞尔曲线构造公式。有了变量之间的新关系，就可以t用不同的方式表达。x如果我们将三次贝塞尔公式表示为控制点坐标乘以四个系数（ v0- ）的乘积之和，这些系数v3由方程的四个部分中的函数根据t. 这给出了公式 x = ax * v0 + bx * v1 + cx * v2 + dx * v3。如果您查看下表，您会发现变量的表达式t是一个有四个未知数的方程。因为它们之间的一些V系数的值和关系在迭代之间以不可预测的方式变化。找到那个新的抽象公式超出了这个问题的范围和我的能力范围。

V0-V3 系数表

非常感谢大家的工作，特别是Spektre为优化渲染算法所做的独特开发和努力。你的方法对我来说是最好的选择=)

4

3 回答 3

7

你需要的是搜索你的立方路径并记住最近点。这可以通过增加精度递归地完成，这里的小C++ GL示例：

//---------------------------------------------------------------------------
double pnt[]=                   // cubic curve control points
    {
    -0.9,-0.8,0.0,
    -0.6,+0.8,0.0,
    +0.6,+0.8,0.0,
    +0.9,-0.8,0.0,
    };
const int pnts3=sizeof(pnt)/sizeof(pnt[0]);
const int pnts=pnts3/3;
//---------------------------------------------------------------------------
double cubic_a[4][3];           // cubic coefficients
void cubic_init(double *pnt)    // compute cubic coefficients
    {
    int i;
    double *p0=pnt,*p1=p0+3,*p2=p1+3,*p3=p2+3;
    for (i=0;i<3;i++)           // cubic BEZIER coefficients
        {
        cubic_a[0][i]=                                    (    p0[i]);
        cubic_a[1][i]=                        (3.0*p1[i])-(3.0*p0[i]);
        cubic_a[2][i]=            (3.0*p2[i])-(6.0*p1[i])+(3.0*p0[i]);
        cubic_a[3][i]=(    p3[i])-(3.0*p2[i])+(3.0*p1[i])-(    p0[i]);
        }
    }
//---------------------------------------------------------------------------
double* cubic(double t)         // return point on cubic from parameter
    {
    int i;
    static double p[3];
    double tt=t*t,ttt=tt*t;
    for (i=0;i<3;i++)
     p[i]=cubic_a[0][i]
        +(cubic_a[1][i]*t)
        +(cubic_a[2][i]*tt)
        +(cubic_a[3][i]*ttt);
    return p;
    }
//---------------------------------------------------------------------------
double cubic_d(double *p)       // return closest distance from point to cubic
    {
    int i,j;
    double t,tt,t0,t1,dt,
           l,ll,a,*q;
    tt=-1.0; ll=-1.0; t0=0.0; t1=1.001; dt=0.05;
    for (j=0;j<3;j++)
        {
        for (t=t0;t<=t1;t+=dt)
            {
            q=cubic(t);
            for (l=0.0,i=0;i<3;i++) l+=(p[i]-q[i])*(p[i]-q[i]);
            if ((ll<0.0)||(ll>l)){ ll=l; tt=t; }
            }
        t0=tt-dt; if (t0<0.0) t0=0.0;
        t1=tt+dt; if (t1>1.0) t1=1.0;
        dt*=0.2;
        }
    return sqrt(ll);
    }
//---------------------------------------------------------------------------
void gl_draw()
    {
    int i;
    double t,p[3],dp;
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glEnable(GL_CULL_FACE);

    // GL render
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glDisable(GL_DEPTH_TEST);

                    glColor3f(0.2,0.2,0.2); glBegin(GL_LINE_STRIP); for (i=0;i<pnts3;i+=3) glVertex3dv(pnt+i); glEnd();
    glPointSize(5); glColor3f(0.0,0.0,0.7); glBegin(GL_POINTS); for (i=0;i<pnts3;i+=3) glVertex3dv(pnt+i); glEnd(); glPointSize(1);
    cubic_init(pnt);glColor3f(0.2,0.7,0.7); glBegin(GL_LINE_STRIP); for (t=0.0;t<1.001;t+=0.025) glVertex3dv(cubic(t)); glEnd();

    glColor3f(0.0,0.7,0.0); glBegin(GL_POINTS);
    p[2]=0.0; dp=0.01;
    for (p[0]=-1.0;p[0]<1.001;p[0]+=dp)
     for (p[1]=-1.0;p[1]<1.001;p[1]+=dp)
      if (cubic_d(p)<0.05)
       glVertex3dv(p);
    glEnd();

    glFlush();
    SwapBuffers(hdc);
    }
//---------------------------------------------------------------------------

所以首先你调用cubic_init一次来计算系数，然后根据参数使用获得曲线上的点：

double pnt[3] = cubic(double t);

现在反过来（我返回最近的距离ll，但您可以轻松地将其更改为返回tt）

double dist = cubic_d(double pnt[3]);

现在您只需将其移植到着色器并确定片段是否足够接近以弯曲以渲染它（因此距离而不是t速度，您可以摆脱最后一个sqrt并使用后面的功率值）。

该gl_draw函数使用 GL 渲染控制点（蓝色）/线条（灰色）贝塞尔曲线（浅绿色），然后模拟片段着色器以渲染曲线2*0.05（绿色）...

预习：

预习

现在只需将其移植到 GLSL 中即可。为了使用 GLSL 原生方式传递顶点，您需要像这里一样放大区域：

但是您需要稍微更改几何以考虑 4 个控制点而不是 3 个。这些东西应该在几何着色器中......

所以在几何着色器中你应该做cubic_init，discard如果距离cubic_d大于厚度，在片段着色器中。

搜索基于：

我为这样的问题开发的。搜索循环本身可以进行一些调整以提高性能/精度......但要注意初始搜索应该将曲线采样到至少 4-5 个块，否则它可能会停止对某些形状正常工作。

[Edit1] 经过一番思考，这里是 GLSL 版本

顶点

// Vertex
#version 400 core
layout(location = 0) in vec2 pos;   // control points (QUADS)
layout(location = 3) in vec3 col;   // color

out vec2 vpos;
out vec3 vcol;

void main()
    {
    vpos=pos;
    vcol=col;
    gl_Position=vec4(pos,0.0,1.0);
    }

几何学：

//------------------------------------------------------------------------------
// Geometry
//------------------------------------------------------------------------------
#version 400 core
layout(lines_adjacency) in;
layout(triangle_strip, max_vertices = 4) out;

uniform float d=0.05;   // half thickness

in vec2 vpos[];
in vec3 vcol[];

out vec2 a0,a1,a2,a3;   // cubic coefficients
out vec3 fcol;          // color
out vec2 fpos;          // position
//------------------------------------------------------------------------------
void main()
    {
    vec4 p0,p1,p2,p3,a,b;
    p0=gl_in[0].gl_Position;
    p1=gl_in[1].gl_Position;
    p2=gl_in[2].gl_Position;
    p3=gl_in[3].gl_Position;
    // compute BEZIER coefficients
    a0.x=                             (    p0.x);
    a1.x=                  (3.0*p1.x)-(3.0*p0.x);
    a2.x=       (3.0*p2.x)-(6.0*p1.x)+(3.0*p0.x);
    a3.x=(p3.x)-(3.0*p2.x)+(3.0*p1.x)-(    p0.x);
    a0.y=                             (    p0.y);
    a1.y=                  (3.0*p1.y)-(3.0*p0.y);
    a2.y=       (3.0*p2.y)-(6.0*p1.y)+(3.0*p0.y);
    a3.y=(p3.y)-(3.0*p2.y)+(3.0*p1.y)-(    p0.y);
    // compute BBOX
    a=p0;                     b=p0;
    if (a.x > p1.x) a.x=p1.x; if (b.x < p1.x) b.x=p1.x;
    if (a.x > p2.x) a.x=p2.x; if (b.x < p2.x) b.x=p2.x;
    if (a.x > p3.x) a.x=p3.x; if (b.x < p3.x) b.x=p3.x;
    if (a.y > p1.y) a.y=p1.y; if (b.y < p1.y) b.y=p1.y;
    if (a.y > p2.y) a.y=p2.y; if (b.y < p2.y) b.y=p2.y;
    if (a.y > p3.y) a.y=p3.y; if (b.y < p3.y) b.y=p3.y;
    // enlarge by d
    a.x-=d; a.y-=d;
    b.x+=d; b.y+=d;
    // pass it as QUAD
    fcol=vcol[0];
    fpos=vec2(a.x,a.y); gl_Position=vec4(a.x,a.y,0.0,1.0); EmitVertex();
    fpos=vec2(a.x,b.y); gl_Position=vec4(a.x,b.y,0.0,1.0); EmitVertex();
    fpos=vec2(b.x,a.y); gl_Position=vec4(b.x,a.y,0.0,1.0); EmitVertex();
    fpos=vec2(b.x,b.y); gl_Position=vec4(b.x,b.y,0.0,1.0); EmitVertex();
    EndPrimitive();
    }

//------------------------------------------------------------------------------

分段：

// Fragment
#version 400 core
uniform float d=0.05;   // half thickness

in vec2 fpos;           // fragment position
in vec3 fcol;           // fragment color
in vec2 a0,a1,a2,a3;    // cubic coefficients

out vec4 col;

vec2 cubic(float t)     // return point on cubic from parameter
    {
    float tt=t*t,ttt=tt*t;
    return a0+(a1*t)+(a2*tt)+(a3*ttt);
    }

void main()
    {
    vec2 p;
    int i;
    float t,tt,t0,t1,dt,l,ll;
    tt=-1.0; ll=-1.0; dt=0.05; t0=0.0; t1=1.0; l=0.0;
    for (i=0;i<3;i++)
        {
        for (t=t0;t<=t1;t+=dt)
            {
            p=cubic(t)-fpos;
            l=length(p);
            if ((ll<0.0)||(ll>l)){ ll=l; tt=t; }
            }
        t0=tt-dt; if (t0<0.0) t0=0.0;
        t1=tt+dt; if (t1>1.0) t1=1.0;
        dt*=0.2;
        }
    if (ll>d) discard;
    col=vec4(fcol,1.0); // ll,tt can be used for coloring or texturing
    }

它期望每个 CUBIC 有 4 个 BEZIER 控制点，GL_LINES_ADJACENCY因为GL_QUADS形式不再存在:(当我像这样使用它时（在 gl_draw 内部）：

glUseProgram(prog_id);               // use our shaders
i=glGetUniformLocation(prog_id,"d"); // set line half thickness
glUniform1f(i,0.02);
glColor3f(0.2,0.7,0.2);              // color
glBegin(GL_LINES_ADJACENCY); 
for (i=0;i<pnts3;i+=3)
 glVertex3dv(pnt+i);
glEnd();
glUseProgram(0);

结果如下所示：

着色器预览

和粗糙的比旧的 api 点着色器仿真快很多:)。我知道旧的 api 和新风格的 GLSL 着色器不应该混合，所以你应该创建VAO/VBO而不是使用glBegin/glEnd......我懒得这样做只是为了这个答案......

这里是非函数（每个 x 更多 y）示例（与 CPU 侧点相比）：

double pnt[]=                   // cubic curve control points
    {
    +0.9,-0.8,0.0,
    -2.5,+0.8,0.0,
    +2.5,+0.8,0.0,
    -0.9,-0.8,0.0,
    };

非功能

如您所见，这两种方法都匹配形状（点使用更大的厚度）。为了使它起作用，dt必须正确设置搜索系数 ( ) 以免错过解决方案...

PS用你的方式求解立方会导致以下两组：

分析溶液

我强烈怀疑它的计算速度比简单搜索要快得多。

[Edit2] 进一步改进

我只是更改了几何着色器，使其将曲线采样为 10 段，并为每个段分别发出 BBOX，从而消除了之前需要处理的大量空白空间。我稍微改变了颜色布局和渲染顺序。

这是新结果（与前一个结果相同，但由于较低的空白空间率而快了几倍）：

预习

这是现在的覆盖范围：

覆盖范围

在覆盖范围之前是控制点的 BBOX + 放大d，在这种情况下比曲线本身大得多（2 个控制点在视野外）。

这里更新了几何着色器：

//------------------------------------------------------------------------------
// Geometry
//------------------------------------------------------------------------------
#version 400 core
layout(lines_adjacency) in;
layout(triangle_strip, max_vertices = 40) out;  // 4*n <= 60

uniform float d=0.05;   // half thickness

in vec2 vpos[];
in vec3 vcol[];

out vec2 a0,a1,a2,a3;   // cubic coefficients
out vec3 fcol;          // color
out vec2 fpos;          // position
//------------------------------------------------------------------------------
vec2 cubic(float t)     // return point on cubic from parameter
    {
    float tt=t*t,ttt=tt*t;
    return a0+(a1*t)+(a2*tt)+(a3*ttt);
    }
//------------------------------------------------------------------------------
void main()
    {
    float t,dt=1.0/10.0;    // 1/n
    vec2 p0,p1,p2,p3,a,b;
    p0=gl_in[0].gl_Position.xy;
    p1=gl_in[1].gl_Position.xy;
    p2=gl_in[2].gl_Position.xy;
    p3=gl_in[3].gl_Position.xy;
    // compute BEZIER coefficients
    a0.x=                             (    p0.x);
    a1.x=                  (3.0*p1.x)-(3.0*p0.x);
    a2.x=       (3.0*p2.x)-(6.0*p1.x)+(3.0*p0.x);
    a3.x=(p3.x)-(3.0*p2.x)+(3.0*p1.x)-(    p0.x);
    a0.y=                             (    p0.y);
    a1.y=                  (3.0*p1.y)-(3.0*p0.y);
    a2.y=       (3.0*p2.y)-(6.0*p1.y)+(3.0*p0.y);
    a3.y=(p3.y)-(3.0*p2.y)+(3.0*p1.y)-(    p0.y);
    p1=cubic(0.0);
    for (t=dt;t < 1.001;t+=dt)
        {
        p0=p1; p1=cubic(t);
        // compute BBOX
        a=p0;                     b=p0;
        if (a.x > p1.x) a.x=p1.x; if (b.x < p1.x) b.x=p1.x;
        if (a.y > p1.y) a.y=p1.y; if (b.y < p1.y) b.y=p1.y;
        // enlarge by d
        a.x-=d; a.y-=d;
        b.x+=d; b.y+=d;
        // pass it as QUAD
        fcol=vcol[0];
        fpos=vec2(a.x,a.y); gl_Position=vec4(a.x,a.y,0.0,1.0); EmitVertex();
        fpos=vec2(a.x,b.y); gl_Position=vec4(a.x,b.y,0.0,1.0); EmitVertex();
        fpos=vec2(b.x,a.y); gl_Position=vec4(b.x,a.y,0.0,1.0); EmitVertex();
        fpos=vec2(b.x,b.y); gl_Position=vec4(b.x,b.y,0.0,1.0); EmitVertex();
        EndPrimitive();
        }
    }
//------------------------------------------------------------------------------

我的 gfx 卡有 60 个顶点限制，因此当我输出模拟 QUAD 的三角形条时，60/4 = 15我使用分段限制n=10来确保它在较低的硬件上运行。为了更改段数，请参见包含注释的 2 行n

[Edit3] 更好的覆盖有用/空白空间比率

我将 AABB BBOX 覆盖范围更改为 ~OOB BBOX，没有重叠。这也允许将实际范围传递t到片段中，从而加快搜索速度约 10 倍。更新的着色器：

顶点： 

// Vertex
#version 400 core
layout(location = 0) in vec2 pos;   // control points (QUADS)
layout(location = 3) in vec3 col;   // color

out vec2 vpos;
out vec3 vcol;

void main()
    {
    vpos=pos;
    vcol=col;
    gl_Position=vec4(pos,0.0,1.0);
    }

几何学： 

//------------------------------------------------------------------------------
// Geometry
//------------------------------------------------------------------------------
#version 400 core
layout(lines_adjacency) in;
layout(triangle_strip, max_vertices = 40) out;  // 4*n <= 60

uniform float d=0.05;   // half thickness

in vec2 vpos[];
in vec3 vcol[];

out vec2 a0,a1,a2,a3;   // cubic coefficients
out vec3 fcol;          // color
out vec2 fpos;          // position
out vec2 trange;        // t range of chunk
//------------------------------------------------------------------------------
vec2 cubic(float t)     // return point on cubic from parameter
    {
    float tt=t*t,ttt=tt*t;
    return a0+(a1*t)+(a2*tt)+(a3*ttt);
    }
//------------------------------------------------------------------------------
void main()
    {
    int i,j,n=10,m=10;              // n,m
    float t,dd,d0,d1,dt=1.0/10.0;   // 1/n
    float tt,dtt=1.0/100.0;         // 1/(n*m)
    vec2 p0,p1,p2,p3,u,v;
    vec2 q0,q1,q2,q3;
    p0=gl_in[0].gl_Position.xy;
    p1=gl_in[1].gl_Position.xy;
    p2=gl_in[2].gl_Position.xy;
    p3=gl_in[3].gl_Position.xy;
    // compute BEZIER coefficients
    a0.x=                             (    p0.x);
    a1.x=                  (3.0*p1.x)-(3.0*p0.x);
    a2.x=       (3.0*p2.x)-(6.0*p1.x)+(3.0*p0.x);
    a3.x=(p3.x)-(3.0*p2.x)+(3.0*p1.x)-(    p0.x);
    a0.y=                             (    p0.y);
    a1.y=                  (3.0*p1.y)-(3.0*p0.y);
    a2.y=       (3.0*p2.y)-(6.0*p1.y)+(3.0*p0.y);
    a3.y=(p3.y)-(3.0*p2.y)+(3.0*p1.y)-(    p0.y);
    q2=vec2(0.0,0.0);
    q3=vec2(0.0,0.0);
    // sample curve by chunks
    for (p1=cubic(0.0),i=0,t=dt;i<n;i++,t+=dt)
        {
        // sample point
        p0=p1; p1=cubic(t); q0=q2; q1=q3;
        // compute ~OBB enlarged by D
        u=normalize(p1-p0);
        v=vec2(u.y,-u.x);
        // resample chunk to compute enlargement
        for (d0=0.0,d1=0.0,tt=t-dtt,j=2;j<m;j++,tt-=dtt)
            {
            dd=dot(cubic(tt)-p0,v);
            d0=max(-dd,d0);
            d1=max(+dd,d1);
            }
        d0+=d; d1+=d; u*=d;
        d0*=1.25; d1*=1.25; // just to be sure
        // enlarge radial
        q2=p1+(v*d1);
        q3=p1-(v*d0);
        // enlarge axial
        if (i==0)
            {
            q0=p0+(v*d1)-u;
            q1=p0-(v*d0)-u;
            }
        if (i==n-1)
            {
            q2+=u;
            q3+=u;
            }
        // pass it as QUAD
        fcol=vcol[0]; trange=vec2(t-dt,t);
        fpos=q0; gl_Position=vec4(q0,0.0,1.0); EmitVertex();
        fpos=q1; gl_Position=vec4(q1,0.0,1.0); EmitVertex();
        fpos=q2; gl_Position=vec4(q2,0.0,1.0); EmitVertex();
        fpos=q3; gl_Position=vec4(q3,0.0,1.0); EmitVertex();
        EndPrimitive();
        }
    }
//------------------------------------------------------------------------------*

分段： 

// Fragment
#version 400 core

//#define show_coverage

uniform float d=0.05;   // half thickness

in vec2 fpos;           // fragment position
in vec3 fcol;           // fragment color
in vec2 a0,a1,a2,a3;    // cubic coefficients
in vec2 trange;         // t range of chunk

out vec4 col;

vec2 cubic(float t)     // return point on cubic from parameter
    {
    float tt=t*t,ttt=tt*t;
    return a0+(a1*t)+(a2*tt)+(a3*ttt);
    }

void main()
    {
    vec2 p;
    int i,n;
    float t,tt,t0,t1,dt,l,ll;
    tt=-1.0; ll=-1.0; l=0.0;
    #ifdef show_coverage
    t0=0.0; t1=1.0; dt=0.05; n=3;
    #else
    t0=trange.x; n=2;
    t1=trange.y;
    dt=(t1-t0)*0.1;
    #endif
    for (i=0;i<n;i++)
        {
        for (t=t0;t<=t1;t+=dt)
            {
            p=cubic(t)-fpos;
            l=length(p);
            if ((ll<0.0)||(ll>l)){ ll=l; tt=t; }
            }
        t0=tt-dt; if (t0<0.0) t0=0.0;
        t1=tt+dt; if (t1>1.0) t1=1.0;
        dt*=0.2;
        }
    #ifdef show_coverage
    if (ll>d) col=vec4(0.1,0.1,0.1,1.0); else
    #else
    if (ll>d) discard;
    #endif
    col=vec4(fcol,1.0);
    }

和预览（曲线+覆盖）：

更好的覆盖范围

只是曲线：

曲线

如您所见，交叉口处的接缝覆盖率是由于覆盖率渲染而没有混合。曲线本身没问题。

d0,d1参数是与实际块 OBB 轴 (u) 的最大垂直距离，放大并按d比例放大 25% 以确保确定。看起来它非常适合。我怀疑进一步优化会带来很多好处，因为这个结果非常接近覆盖范围的完美拟合......

#define show_coverage只是可以查看传递给片段着色器的几何图形...

于 2020-02-07T12:33:36.810 回答
4

看看这个棘手的贝塞尔曲线：

棘手的贝塞尔曲线

没有一个解决方案t，有（最多）3 个解决方案。

（edit1：正如 Salix alba 的回答中所述，这并不意味着您找不到它们。当您认为只有 onetx和 onety时，您检查它们是否（几乎）相等。转到 3 个解决方案，您可以找到tx's 和's 并检查是否存在（几乎）共同的实际值，但我认为检查是否（几乎）等于anyty应该足够（并且更快）而不计算 any 。对每个具有相同像素的像素来说都是相同的，看看你是否只能为每个唯一的像素计算一次。bezierY(tx)glFragCoord.ytxtytxxx）

我没有过多地使用贝塞尔曲线，也从未使用过 glsl，所以这里有一个可能不好的想法：

每次您的控制点发生变化时，执行t循环以生成{x,y}点列表，并可能将它们存储在某种无序地图中。然后，在您的着色器中，对于每个像素，如果该像素存在于该贴图中，则应用所需的效果。

您也可以添加附近的点，并将与曲线的距离存储为地图中的值，因此您可以根据需要进行某种抗锯齿。

循环中的步长t必须足够小，以便不会遗漏任何点，但要足够大，以便快速。t您可以通过检查下一点与上一点的接近程度来实现动态步骤。如果太近，增加步长。如果太远，请减小步长。

您也可以尝试使用二维数组而不是地图，例如 512x512 布尔值。用 初始化每个元素，并将循环中生成的点false的值更改为 。同时，存储当前为 的数组索引列表，因此您只能初始化 2d 数组一次，当曲线发生变化时，将每一次翻转回，清空索引列表，然后重复循环等。truettruetruefalset

（edit2，更新后）

无需搜索“如何从三次贝塞尔方程中表达变量 t”，您通常可以搜索“三次方程解”。如果我没记错的话，贝塞尔方程（x 或 y）可以写成

(-a + 3b - 3c + d) t^3 + (3a - 6b + 3c) t^2 + (-3a + 3b) t + (a - x) = 0

其中a、b和是控制点的 x（或 y）分量，c并且是曲线的 x（或 y）分量，因此它们只是三次方程。看到它只出现在最后一个系数中，当你需要解决很多问题时，这可能会让事情变得更容易，它们唯一的区别是 的值。dxxx

应该有更简单的解决方案，但是如果您可以访问复杂的算术（或者愿意使用 vec2 自己编写，请参阅Spektre 的回答“如何计算离散傅里叶变换”），您可以尝试这 3 个解决方案，因为t我从 Mathematica 获得（I是虚数单位）：

(-2*(a - 2*b + c) + (2*2^(1/3)*(b^2 + c^2 + a*(-c + d) - b*(c + d)))/(-2*b^3 + 3*a*b*c + 3*b^2*c - 6*a*c^2 + 3*b*c^2 - 2*c^3 - a^2*d + 3*a*b*d - 6*b^2*d + 3*a*c*d + 3*b*c*d - a*d^2 + a^2*x - 6*a*b*x + 9*b^2*x + 6*a*c*x - 18*b*c*x + 9*c^2*x - 2*a*d*x + 6*b*d*x - 6*c*d*x + d^2*x + Sqrt[(a - 3*b + 3*c - d)^2*(4*b^3*(d - x) + a^2*(d - x)^2 + x*(-4*c^3 + 9*c^2*x - 6*c*d*x + d^2*x) - 3*b^2*(c^2 - 2*c*x + (4*d - 3*x)*x) + 2*a*(2*c^3 - 6*c^2*x + 3*c*x*(d + x) - d*x*(d + x)) + 6*b*(a*(c - x)*(-d + x) + x*(c^2 + c*d - 3*c*x + d*x)))])^(1/3) + 2^(2/3)*(-2*b^3 + 3*a*b*c + 3*b^2*c - 6*a*c^2 + 3*b*c^2 - 2*c^3 - a^2*d + 3*a*b*d - 6*b^2*d + 3*a*c*d + 3*b*c*d - a*d^2 + a^2*x - 6*a*b*x + 9*b^2*x + 6*a*c*x - 18*b*c*x + 9*c^2*x - 2*a*d*x + 6*b*d*x - 6*c*d*x + d^2*x + Sqrt[(a - 3*b + 3*c - d)^2*(4*b^3*(d - x) + a^2*(d - x)^2 + x*(-4*c^3 + 9*c^2*x - 6*c*d*x + d^2*x) - 3*b^2*(c^2 - 2*c*x + (4*d - 3*x)*x) + 2*a*(2*c^3 - 6*c^2*x + 3*c*x*(d + x) - d*x*(d + x)) + 6*b*(a*(c - x)*(-d + x) + x*(c^2 + c*d - 3*c*x + d*x)))])^(1/3))/(2*(-a + 3*b - 3*c + d))

(-36*(a - 2*b + c) - ((18*I)*2^(1/3)*(-I + Sqrt[3])*(b^2 + c^2 + a*(-c + d) - b*(c + d)))/(-2*b^3 + 3*a*b*c + 3*b^2*c - 6*a*c^2 + 3*b*c^2 - 2*c^3 - a^2*d + 3*a*b*d - 6*b^2*d + 3*a*c*d + 3*b*c*d - a*d^2 + a^2*x - 6*a*b*x + 9*b^2*x + 6*a*c*x - 18*b*c*x + 9*c^2*x - 2*a*d*x + 6*b*d*x - 6*c*d*x + d^2*x + Sqrt[(a - 3*b + 3*c - d)^2*(4*b^3*(d - x) + a^2*(d - x)^2 + x*(-4*c^3 + 9*c^2*x - 6*c*d*x + d^2*x) - 3*b^2*(c^2 - 2*c*x + (4*d - 3*x)*x) + 2*a*(2*c^3 - 6*c^2*x + 3*c*x*(d + x) - d*x*(d + x)) + 6*b*(a*(c - x)*(-d + x) + x*(c^2 + c*d - 3*c*x + d*x)))])^(1/3) + (9*I)*2^(2/3)*(I + Sqrt[3])*(-2*b^3 + 3*a*b*c + 3*b^2*c - 6*a*c^2 + 3*b*c^2 - 2*c^3 - a^2*d + 3*a*b*d - 6*b^2*d + 3*a*c*d + 3*b*c*d - a*d^2 + a^2*x - 6*a*b*x + 9*b^2*x + 6*a*c*x - 18*b*c*x + 9*c^2*x - 2*a*d*x + 6*b*d*x - 6*c*d*x + d^2*x + Sqrt[(a - 3*b + 3*c - d)^2*(4*b^3*(d - x) + a^2*(d - x)^2 + x*(-4*c^3 + 9*c^2*x - 6*c*d*x + d^2*x) - 3*b^2*(c^2 - 2*c*x + (4*d - 3*x)*x) + 2*a*(2*c^3 - 6*c^2*x + 3*c*x*(d + x) - d*x*(d + x)) + 6*b*(a*(c - x)*(-d + x) + x*(c^2 + c*d - 3*c*x + d*x)))])^(1/3))/(36*(-a + 3*b - 3*c + d))

(-36*(a - 2*b + c) + ((18*I)*2^(1/3)*(I + Sqrt[3])*(b^2 + c^2 + a*(-c + d) - b*(c + d)))/(-2*b^3 + 3*a*b*c + 3*b^2*c - 6*a*c^2 + 3*b*c^2 - 2*c^3 - a^2*d + 3*a*b*d - 6*b^2*d + 3*a*c*d + 3*b*c*d - a*d^2 + a^2*x - 6*a*b*x + 9*b^2*x + 6*a*c*x - 18*b*c*x + 9*c^2*x - 2*a*d*x + 6*b*d*x - 6*c*d*x + d^2*x + Sqrt[(a - 3*b + 3*c - d)^2*(4*b^3*(d - x) + a^2*(d - x)^2 + x*(-4*c^3 + 9*c^2*x - 6*c*d*x + d^2*x) - 3*b^2*(c^2 - 2*c*x + (4*d - 3*x)*x) + 2*a*(2*c^3 - 6*c^2*x + 3*c*x*(d + x) - d*x*(d + x)) + 6*b*(a*(c - x)*(-d + x) + x*(c^2 + c*d - 3*c*x + d*x)))])^(1/3) - 9*2^(2/3)*(1 + I*Sqrt[3])*(-2*b^3 + 3*a*b*c + 3*b^2*c - 6*a*c^2 + 3*b*c^2 - 2*c^3 - a^2*d + 3*a*b*d - 6*b^2*d + 3*a*c*d + 3*b*c*d - a*d^2 + a^2*x - 6*a*b*x + 9*b^2*x + 6*a*c*x - 18*b*c*x + 9*c^2*x - 2*a*d*x + 6*b*d*x - 6*c*d*x + d^2*x + Sqrt[(a - 3*b + 3*c - d)^2*(4*b^3*(d - x) + a^2*(d - x)^2 + x*(-4*c^3 + 9*c^2*x - 6*c*d*x + d^2*x) - 3*b^2*(c^2 - 2*c*x + (4*d - 3*x)*x) + 2*a*(2*c^3 - 6*c^2*x + 3*c*x*(d + x) - d*x*(d + x)) + 6*b*(a*(c - x)*(-d + x) + x*(c^2 + c*d - 3*c*x + d*x)))])^(1/3))/(36*(-a + 3*b - 3*c + d))

它们很大，但它们包含许多常见的子表达式（如(a - 2*b + c)），您可以评估一次并重用它们，以提高性能（如果所有这些都有效的话）。

对于我发布的棘手的贝塞尔曲线，这里有 3 个解决方案：

red = (6 + (4*2^(1/3))/(-9 + 49*x + 7*Sqrt[1 + x*(-18 + 49*x)])^(1/3) + 2^(2/3)*(-9 + 49*x + 7*Sqrt[1 + x*(-18 + 49*x)])^(1/3))/14
green = (12 - ((4*I)*2^(1/3)*(-I + Sqrt[3]))/(-9 + 49*x + 7*Sqrt[1 - 18*x + 49*x^2])^(1/3) + I*2^(2/3)*(I + Sqrt[3])*(-9 + 49*x + 7*Sqrt[1 - 18*x + 49*x^2])^(1/3))/28
blue = (12 + ((4*I)*2^(1/3)*(I + Sqrt[3]))/(-9 + 49*x + 7*Sqrt[1 - 18*x + 49*x^2])^(1/3) - 2^(2/3)*(1 + I*Sqrt[3])*(-9 + 49*x + 7*Sqrt[1 - 18*x + 49*x^2])^(1/3))/28

t-vs-x 用于棘手的贝塞尔曲线

（edit3）按照Spektre的建议，直接使用三次系数

x = a*t^3 + b*t^2 + c*t + d

（而不是使用控制点的坐标）给出更清晰的表达式：

1st(red) = (-2*b + (2*2^(1/3)*(b^2 - 3*a*c))/(-2*b^3 + 9*a*b*c - 27*a^2*d + Sqrt[-4*(b^2 - 3*a*c)^3 + (2*b^3 - 9*a*b*c + 27*a^2*(d - x))^2] + 27*a^2*x)^(1/3) + 2^(2/3)*(-2*b^3 + 9*a*b*c - 27*a^2*d + Sqrt[-4*(b^2 - 3*a*c)^3 + (2*b^3 - 9*a*b*c + 27*a^2*(d - x))^2] + 27*a^2*x)^(1/3))/(6*a)
2nd(green) = (-4*b + (2*2^(1/3)*(1 + I*Sqrt[3])*(-b^2 + 3*a*c))/(-2*b^3 + 9*a*b*c - 27*a^2*d + Sqrt[-4*(b^2 - 3*a*c)^3 + (2*b^3 - 9*a*b*c + 27*a^2*(d - x))^2] + 27*a^2*x)^(1/3) + I*2^(2/3)*(I + Sqrt[3])*(-2*b^3 + 9*a*b*c - 27*a^2*d + Sqrt[-4*(b^2 - 3*a*c)^3 + (2*b^3 - 9*a*b*c + 27*a^2*(d - x))^2] + 27*a^2*x)^(1/3))/(12*a)
3rd(blue) = -(4*b - ((2*I)*2^(1/3)*(I + Sqrt[3])*(b^2 - 3*a*c))/(-2*b^3 + 9*a*b*c - 27*a^2*d + Sqrt[-4*(b^2 - 3*a*c)^3 + (2*b^3 - 9*a*b*c + 27*a^2*(d - x))^2] + 27*a^2*x)^(1/3) + 2^(2/3)*(1 + I*Sqrt[3])*(-2*b^3 + 9*a*b*c - 27*a^2*d + Sqrt[-4*(b^2 - 3*a*c)^3 + (2*b^3 - 9*a*b*c + 27*a^2*(d - x))^2] + 27*a^2*x)^(1/3))/(12*a)

您可以轻松地将控制点的坐标转换为这些坐标：

direct a = control (-a + 3 b - 3 c + d)
direct b = control (3 a - 6 b + 3 c)
direct c = control (-3 a + 3 b)
direct d = control a
于 2020-02-05T12:42:37.957 回答
2

贝塞尔曲线基本上是三次方，有一个公式可以得到三次方的结果，您可以通过查看Wikipedia上的三次方程来查看。它非常复杂，但您可以按照该方法进行操作。与使用公式相比，更容易遵循方法的步骤。这个 Quora 问题如何求解三次方程？有详细讨论各种方法的答案。

另一个答案提到解决方案并不总是唯一的，因为给定的值x可能有一个、两个或三个可能的值t。当您使用该算法时，有几次您需要计算一个数字的平方根，这将有两种解决方案：+sqrt(...) 或 -sqrt(...)。遵循每个值的算法将为您提供解决方案。

我还应该提到，只要计算负数的平方根，算法的中间部分就会涉及复数。同样，您需要考虑一对将是复共轭的解决方案。

于 2020-02-06T18:16:05.697 回答