logo标签列表

使用C ++在规范化矩阵中通过任意3个点计算曲线

c++beziercurvesplines
3
如果我有一个简单的二维矩阵，其x轴上的标准化值在0到1之间，y轴上的标准化值也在0到1之间，并且在该矩阵中有3个点，例如P1（x=0.2，y=0.9），P2（x=0.5，y=0.1）和P3（x=0.9，y=0.4）。
那么如何简单地通过这些点计算曲线，即得到一个函数，可以为任何x给出y值呢？
我知道可能会有无数种曲线通过这3个点。但是，你知道我的意思：我希望得到一条平滑的曲线，适用于音频样本插值，适用于计算音量渐变曲线，适用于计算游戏中怪物行走路径。
现在我已经在网上寻找了3天，我不敢相信没有可用的解决方案来完成这个任务。所有涉及Catmull-rom样条、贝塞尔曲线和所有理论性内容的文本都至少有一个点使得对我来说不适用。例如，Catmull-Rom样条需要控制点之间具有固定的距离（我将使用此代码并将第4个点-y设置为第3个点y）：
void CatmullRomSpline(float *x,float *y,float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4,float u)
{
//x,y are calculated for x1,y1,x2,y2,x3,y3 and x4,y4 if u is the normalized distance (0-1) in relation to the distance between x2 and x3 for my whiched point

float u3,u2,f1,f2,f3,f4;

u3=u*u*u;
u2=u*u;
f1=-0.5f * u3 + u2 -0.5f *u;
f2= 1.5f * u3 -2.5f * u2+1.0f;
f3=-1.5f * u3 +2.0f * u2+0.5f*u;
f4=0.5f*u3-0.5f*u2;

*x=x1*f1+x2*f2+x3*f3+x4*f4;
*y=y1*f1+y2*f2+y3*f3+y4*f4;

}

但我没有看到x1到x4对y的计算有任何影响，所以我认为x1到x4必须具有相同的距离？
...
或者贝塞尔代码不会通过这些点计算曲线。这些点（至少第二个点）似乎只对直线产生了影响。
typedef struct Point2D
{
double x;
double y;
} Point2D;

class bezier
{
std::vector<Point2D> points;
bezier();
void PushPoint2D( Point2D point );
Point2D GetPoint( double time );
~bezier();
};

void bezier::PushPoint2D(Point2D point)
{
points.push_back(point);
}

Point2D bezier::GetPoint( double x )
{
int i;
Point2D p;

p.x=0;
p.y=0;

if( points.size() == 1 ) return points[0];
if( points.size() == 0 ) return p;

bezier b;
for (i=0;i<(int)points.size()-1;i++)
{
    p.x = ( points[i+1].x - points[i].x ) * x + points[i].x;
    p.y = ( points[i+1].y - points[i].y ) * x + points[i].y;
    if (points.size()<=2) return p;
    b.PushPoint2D(p);
}

return b.GetPoint(x);
}

double GetLogicalYAtX(double x)
{
bezier bz;
Point2D p;

p.x=0.2;
p.y=0.9;
bz.PushPoint2D(p);

p.x=0.5;
p.y=0.1;
bz.PushPoint2D(p);

p.x=0.9;
p.y=0.4;
bz.PushPoint2D(p);

p=bz.GetPoint(x);

return p.y;
}

虽然这比什么都没有要好，但是它有两个缺点：1.非常慢（递归）；2.正如我所说的那样，它并不能真正计算出通过第二个点的直线。

是否有数学方面的人能够帮助我呢？

https://dev59.com/F2w15IYBdhLWcg3wSJzQ - qPCR4vir
2个回答
0
static bezier From3Points(const Point2D &a, const Point2D &b, const Point2D &c)
{
    bezier result;
    result.PushPoint2D(a);

    Point2D middle;
    middle.x = 2*b.x - a.x/2 - c.x/2;
    middle.y = 2*b.y - a.y/2 - c.y/2;
    result.PushPoint2D(middle);

    result.PushPoint2D(c);
    return result;
}

未经测试，但应返回一条贝塞尔曲线，在t=0.5时曲线通过点'b'。

此外（以下是更多未经测试的代码），可以使用伯恩斯坦基多项式计算您的点，如下所示。

static int binomialcoefficient (int n, int k)
{
    if (k == 0)
        return 1;
    if (n == 0)
        return 0;

    int result = 0;
    for (int i = 1; i <= k; ++i)
    {
        result += (n - (k - i))/i;
    }
    return result;
}

static double bernstein (int v, int n, double t)
{
    return binomialcoefficient(v,n) * pow(t,v) * pow(1 - t,n - v);
}

Point2D GetPoint (double t)
{
    Point2D result;
    result.x = 0;
    result.y = 0;

    for (int i = 0; i < points.size(); ++i)
    {
        double coeff = bernstein (i,points.size(),t);
        result.x += coeff * points[i].x;
        result.y += coeff * points[i].y;
    }

    return result;
}
你不应该在那里再加一个 PushPoint2D 吗？贝塞尔曲线需要4个点，除非你使用的是比较少见的二次形式而不是三次。 - Mark Ransom
贝塞尔曲线只是递归定义的吗？我不明白为什么需要4个点。只要提供正确的伯恩斯坦基多项式，就不应该有问题。二次贝塞尔曲线是(1-t)^2P0 + 2(1-t)tP1 + t^2P2如果你看一下伯恩斯坦多项式 B0,2 = (1 - x)^2 B1,2 = 2(1-x)x 和 B2,2 = x^2它们匹配，所以无论点数如何都不应该有问题。然而，Op似乎正在使用递归定义，他会受益于切换到更直接的求和定义。 - Tocs
@infact，理论上贝塞尔曲线可以用任意多的点来定义。然而，最常用的形式是四个点的三次贝塞尔曲线；如果需要超过四个点，则将曲线分成多个独立的段，其中一个段的终点定义下一个段的起点。 - Mark Ransom
@Tocs Adobe的所有东西都是这样工作的，比如Postscript/PDF和Photoshop。通过确保端点两侧的控制点相互间隔180度，并且最好距离相等，可以获得平滑的曲线。我所知道的Quadratic Bezier的唯一真实世界例子是TrueType字体。 - Mark Ransom
@Tocs 你好，我想尝试Bernstein代码，但是不知道你怎么使用它。我尝试了以下代码： double curve::GetBernsteinPoint(double x) { Point2D result; result.x = 0; result.y = 0;for (int i = 0; i < (int)points.size(); ++i) { double coeff = bernstein (i,points.size(),x); result.x += coeff * points[i].x; result.y += coeff * points[i].y; } return result.y;} 然后调用函数 GetLogicalYAtX(double x) ,但是它只给我一些直线而不是曲线。 - Tobias Findeisen
显示剩余2条评论
0

感谢TOCS（Scott）提供您的代码，如果我有时间，我也会尝试它。但是我现在测试的是INFACT（答案3）给出的提示：这些“拉格朗日多项式”非常接近我正在寻找的内容：

我已将我的类bezier重命名为curve，因为我添加了一些用于拉格朗日插值的代码。我还添加了三张图形演示代码计算的内容。

在图片1中，您可以看到旧bezier函数的松散中间点。

在图片2中，您现在可以看到拉格朗日插值穿过所有点的结果。

在图片3中，您可以看到唯一的问题，或者我应该说“我也需要解决的事情”（无论如何，这是迄今为止最好的解决方案）：如果我移动中间点，曲线会太快地向上或向下边界移动。我希望它能更平滑地向上和向下移动，以便看起来更像对数函数。这样它就不会太快地超过0和1之间的y边界。

现在我的代码看起来像这样：

curve::curve(void)
{
}

void curve::PushPoint2D(Point2D point)
{
    points.push_back(point);
}

Point2D curve::GetPoint( double x )
{
//GetPoint y for x with bezier-mathematics...

//was the only calculating function in old class "bezier"
//now the class is renamed "curve"
int i;
Point2D p;

p.x=0;
p.y=0;

if( points.size() == 1 ) return points[0];
if( points.size() == 0 ) return p;

curve b;
for (i=0;i<(int)points.size()-1;i++)
{
    p.x = ( points[i+1].x - points[i].x ) * x + points[i].x;
    p.y = ( points[i+1].y - points[i].y ) * x + points[i].y;
    if (points.size()<=2) return p;
    b.PushPoint2D(p);
}

return b.GetPoint(x);
}

//THIS IS NEW AND VERY VERY COOL
double curve::LagrangeInterpolation(double x)
{
double y = 0;

for (int i = 0; i <= (int)points.size()-1; i++)
{
    double numerator = 1;
    double denominator = 1;

    for (int c = 0; c <= (int)points.size()-1; c++)
    {
        if (c != i)
        {
            numerator *= (x - points[c].x);
            denominator *= (points[i].x - points[c].x);
        }
    }

    y += (points[i].y * (numerator / denominator));

}

return y;
}

curve::~curve(void)
{
}


double GetLogicalYAtX(double x)
{
curve cv;
Point2D p;

p.x=0; //always left edge
p.y=y1; //now by var
cv.PushPoint2D(p);

p.x=x2; //now by var
p.y=y2; //now by var
cv.PushPoint2D(p);

p.x=1; //always right edge
p.y=y3; //now by var
cv.PushPoint2D(p);

//p=cv.GetPoint(x);

//return p.y;

return cv.LagrangeInterpolation(x);
}

Old bezier curve Lagrange, cool but... ...clipping so soon...

你有什么想法可以让新的解决方案更加“柔和”吗？这样我就可以在更大的区域内移动第二个点，而曲线不会超出边界。谢谢。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接