是否可以从三次贝塞尔曲线方程中表达“t”变量？
Rya*_*ane 4 algorithm math glsl cubic-bezier
我只想通过片段着色器绘制贝塞尔曲线以连接编辑器中的节点。我知道定义贝塞尔曲线的所有 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都被x和替代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系数的值和关系在迭代之间以不可预测的方式发生变化。找到新的抽象公式超出了这个问题和我的能力范围。
非常感谢大家的工作，特别是Spektre为优化渲染算法所做的独特开发和努力。你的方法对我来说是最好的选择=)
你需要的是搜索你的立方路径并记住最近的点。这可以通过增加精度以递归方式完成，这里有一个小的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大于厚度，则应该执行cubic_init。
搜索基于：
我是为了解决这样的问题而开发的。搜索循环本身可以稍微调整以提高性能/精度...但请注意，初始搜索应将曲线采样到至少 4-5 个块，否则对于某些形状可能会停止正常工作。
[Edit1] 经过一番思考后，这里是 GLSL 版本
顶点
double pnt[3] = cubic(double t);
几何学：
double dist = cubic_d(double pnt[3]);
分段：
// 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);
}
它期望每个 CUBIC 有 4 个 BEZIER 控制点，因为GL_LINES_ADJACENCY不再GL_QUADS是这样了:( 当我像这样使用它时（在 gl_draw 内部）：
//------------------------------------------------------------------------------
// 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();
}
//------------------------------------------------------------------------------
结果如下：
和粗略比旧的 api 点着色器模拟快很多:)。我知道旧的 api 和新风格的 GLSL 着色器不应该混合使用，所以你应该创建VAO/VBO而不是使用glBegin/glEnd...我懒得这样做只是为了这个答案的目的...
这里是非函数（每个 x 更多 y）示例（与 CPU 侧点相比）：
// 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
}
正如您所看到的，两种方法都与形状相匹配（点使用更大的厚度）。为了使其发挥作用，dt必须正确设置搜索系数 ( )，以免错过解决方案......
PS 以您的方式求解三次方程会得到 2 组：
我强烈怀疑它的计算速度是否比简单搜索快得多。
[编辑2]进一步改进
我只是简单地更改了几何着色器，以便将曲线采样为 10 段，并为每个段分别发出 BBOX，从而消除了之前需要处理的大量空白空间。我稍微改变了颜色布局和渲染顺序。
这是新结果（与前一个结果相同，但由于空白空间比率较低，速度快了几倍）：
现在的覆盖范围是这样的：
之前的覆盖范围是控制点的 BBOX + 放大，d在这种情况下比曲线本身大得多（2 个控制点在外部视图）。
这里更新了几何着色器：
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);
60/4 = 15我的 gfx 卡有 60 个顶点限制，因此当我输出模拟 QUAD 的三角形条时，我使用段限制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查看传递给片段着色器的几何图形...
| 归档时间： |
|
| 查看次数： |
1155 次 |
| 最近记录： |