`
liyiwen007
  • 浏览: 107675 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

[翻译] AGG 之贝塞尔插值

阅读更多

原文地址:http://www.antigrain.com/research/
bezier_interpolation/index.html#PAGE_BEZIER_INTERPOLATION

Interpolation with Bezier Curves  贝塞尔插值

A very simple method of smoothing polygons 一种非常简单的多边形平滑方法

翻译:唐风

之前 comp.graphic.algorithms 上有一个讨论,是关于怎么样使用曲线对多边形进行插值处理,使得最终产生的曲线是光滑的而且能通过所有的顶点。Gernot Hoffmann 建议说使用著名的 B-Spline 来进行插值。这里有他当时的文章。B-Spline 在这里效果很好,它看起来就像是一个固定在多边形顶点上的橡皮尺(elastic ruler)。

spline_polygon1   spline_polygon2

 


 

bezier_interpolation但我有个大胆的推测,我觉得肯定还存在更简单的方法。比如,使用三次贝塞曲线(cubic Bezier)进行近似。贝塞尔曲线有两个固定点(起点和终点),另加两个决定曲线形状的控制点(CP)。关于贝塞尔曲线的更多知识可以在搜索引擎中找到,比如,你可以参考 Paul Bourke 的站点。现在给贝塞尔曲线的锚点(固定点),也就是多边形的某一对顶点,那么问题是,我们怎么计算控制点的位置?我运行 Xara X 然后画出了右边这个图形,这很简单,所以我决定尝试下计算出它们的坐标。很显然,多边形两条相邻边的两个控制点与这两个控制点之间的顶点应该在一条直线上,只有这样,两条相邻的插值曲线才能平滑地连接在一起。所以,这两个控制点应该是相对于顶点是对称的,不过,也不全是……,因为真正的对称就要求它们与中心点的距离应该是相等的,但对于我们的情况中并不完全是这样的。一开始,我试着先算出多边形两条边的角平分线,然后把控制点放在这条角平分线的垂直线上。但从图上可以看到,控制点的连线并不会总是垂直于角平分线的。

 


 

最终,我找到一个非常简单的办法,不需要任何复杂的数学计算。首先,我们计算出多边形所有边线的中点,Ai。

bezier_interpolation_s1

 


 

然后连接起相邻边中点,得到很多线段,记为 Ci 。并用图记的方法计算出 Bi 点。

bezier_interpolation_s2

 


 

最后一步,只需要简单地将 Ci 进行平移,平移的路径就是每条线段上 Bi 到对应顶点的路径。就这样,我们计算出了贝塞尔曲线的控制点,平滑的结果看起来也很棒。

bezier_interpolation_s3

 


 

这里还可以做一点小小的改进,因为我们已经得到了一条决定控制点的直线,所以,我们可以根据需要,使控制点在这条直线上移动,这样可以改变插值曲线的状态。我使用了一个与控制点和顶点初始距离相关的系数 K ,用来沿直线移动控制点。控制点离顶点越远,图形看起来就越锐利。

bezier_interpolation_s4

 


 

下面是用原始形状和系统K=1.0的贝塞尔插值两种方法来描画的 SVG 的狮子。

bezier_lion1  bezier_lion2

 


 

下面是放大图

bezier_lion3  bezier_lion4

 


 

这个方法对于自相关的多边形也适用,下面的例子可以看到,结果非常有意思:

bezier_self_intersecting1

 


 

bezier_self_intersecting2

 


 

bezier_self_intersecting3

 


 

这个方法只是探索和经验式的,如果从严格的数学模型的角度看它可能是错误的。但在实际使用中的效果已经足够好了,而且这个方法只需要最小的计算量。下面的代码就是用来画出上面狮子图像的。这些代码并没有进行优化,只是用来演示的。里面有些变量计算了两次,在实际程序中,如果连续的步骤中都用到同一个变量值,我们可以先缓存变量值进行复用(以避免重复的计算)。

// Assume we need to calculate the control
// points between (x1,y1) and (x2,y2).
// Then x0,y0 - the previous vertex,
//      x3,y3 - the next one. 
double xc1 = (x0 + x1) / 2.0;
double yc1 = (y0 + y1) / 2.0;
double xc2 = (x1 + x2) / 2.0;
double yc2 = (y1 + y2) / 2.0;
double xc3 = (x2 + x3) / 2.0;
double yc3 = (y2 + y3) / 2.0; 
double len1 = sqrt((x1-x0) * (x1-x0) + (y1-y0) * (y1-y0));
double len2 = sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
double len3 = sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2)); 
double k1 = len1 / (len1 + len2);
double k2 = len2 / (len2 + len3); 
double xm1 = xc1 + (xc2 - xc1) * k1;
double ym1 = yc1 + (yc2 - yc1) * k1; 
double xm2 = xc2 + (xc3 - xc2) * k2;
double ym2 = yc2 + (yc3 - yc2) * k2; 
// Resulting control points. Here smooth_value is mentioned
// above coefficient K whose value should be in range [0...1].
ctrl1_x = xm1 + (xc2 - xm1) * smooth_value + x1 - xm1;
ctrl1_y = ym1 + (yc2 - ym1) * smooth_value + y1 - ym1; 
ctrl2_x = xm2 + (xc2 - xm2) * smooth_value + x2 - xm2;
ctrl2_y = ym2 + (yc2 - ym2) * smooth_value + y2 - ym2; 

使用三次贝塞尔近似的代码:

// Number of intermediate points between two source ones,
// Actually, this value should be calculated in some way,
// Obviously, depending on the real length of the curve.
// But I don't know any elegant and fast solution for this
// problem.
#define NUM_STEPS 20 
void curve4(Polygon* p,
            double x1, double y1,   //Anchor1
            double x2, double y2,   //Control1
            double x3, double y3,   //Control2
            double x4, double y4)   //Anchor2
{
    double dx1 = x2 - x1;
    double dy1 = y2 - y1;
    double dx2 = x3 - x2;
    double dy2 = y3 - y2;
    double dx3 = x4 - x3;
    double dy3 = y4 - y3; 
    double subdiv_step  = 1.0 / (NUM_STEPS + 1);
    double subdiv_step2 = subdiv_step*subdiv_step;
    double subdiv_step3 = subdiv_step*subdiv_step*subdiv_step; 
    double pre1 = 3.0 * subdiv_step;
    double pre2 = 3.0 * subdiv_step2;
    double pre4 = 6.0 * subdiv_step2;
    double pre5 = 6.0 * subdiv_step3; 

    double tmp1x = x1 - x2 * 2.0 + x3;
    double tmp1y = y1 - y2 * 2.0 + y3; 
    double tmp2x = (x2 - x3)*3.0 - x1 + x4;
    double tmp2y = (y2 - y3)*3.0 - y1 + y4; 
    double fx = x1;
    double fy = y1; 
    double dfx = (x2 - x1)*pre1 + tmp1x*pre2 + tmp2x*subdiv_step3;
    double dfy = (y2 - y1)*pre1 + tmp1y*pre2 + tmp2y*subdiv_step3; 
    double ddfx = tmp1x*pre4 + tmp2x*pre5;
    double ddfy = tmp1y*pre4 + tmp2y*pre5; 
    double dddfx = tmp2x*pre5;
    double dddfy = tmp2y*pre5; 
    int step = NUM_STEPS; 
    // Suppose, we have some abstract object Polygon which
    // has method AddVertex(x, y), similar to LineTo in
    // many graphical APIs.
    // Note, that the loop has only operation add!
    while(step--)
    {
        fx   += dfx;
        fy   += dfy;
        dfx  += ddfx;
        dfy  += ddfy;
        ddfx += dddfx;
        ddfy += dddfy;
        p->AddVertex(fx, fy);
    }
    p->AddVertex(x4, y4); // Last step must go exactly to x4, y4
}

你可以下载一个能运行的画狮子的例子,对它进行旋转和缩放,也可以生成一些随机的多边形。点左键并拖动它可以围绕中心点旋转和缩放图像。点右键并从左向右拖动,可以改变系统数K。 K=1时大约是距窗口左边100像素处。每次双击会产生一个随机的多边形,对于这些多边形,也可以进行旋转、缩放以及改变K值的操作。

分享到:
评论
1 楼 westice 2010-08-23  
非常好!正苦于怎么确定贝塞尔曲线的控制点,很好的思路。

相关推荐

    一个AGG的测试事例

    3. **路径绘制**:AGG支持贝塞尔曲线、直线和其他几何形状的绘制,通过`Path`和`PathScanner`类来构建和解析图形路径。 4. **颜色管理**:AGG提供了丰富的颜色模型和色彩空间转换,包括线性RGB、SRGB、CMYK等,以及...

    agg-2.5 2D图形库

    此外,agg还提供了高级的绘图功能,如贝塞尔曲线、圆弧绘制、投影和光照效果。 **5. 示例代码** agg-2.5压缩包中包含了大量的示例代码,这些示例展示了如何使用agg库的各种功能。开发者可以通过这些示例快速上手,...

    agg二维开发入门例程

    3. **路径和路径操作**:AGG支持复杂的路径定义,包括直线、曲线、贝塞尔曲线等。你可以学习如何创建、修改和绘制路径,以及如何进行剪裁、平移、缩放等操作。 4. **颜色和渲染风格**:AGG提供了多种颜色模型和混合...

    2d图形开发库agg

    5. **路径算法**:AGG使用高效的算法处理复杂的路径数据,如贝塞尔曲线、样条曲线等,保证了在处理大量图形时的性能。 6. **混合模式**:AGG支持多种混合模式,可以实现复杂的效果,如叠加、差值、乘法等,这些在...

    AGG图形库资料

    AGG(Anti-Grain Geometry)是一个开源的2D图形渲染引擎,主要设计用于高性能的图形绘制和处理。这个图形库是由Evgeny Panasenkov开发,它以C++编写,提供了高度优化的算法来处理图形操作,如线条绘制、曲线绘制、...

    agg-2.5 AGG是一个开源、高效的跨平台2D图形库

    •如果要用AGG的控件和窗体,要加入[AGG]\src\ctrl\*.cpp和[AGG]\src\platform\<OS>\*.cpp,头文件在[AGG]\include\ctrl和[AGG]\include\platform里 •如果要用到TrueType字体显示,要加入[AGG]\font_win32_tt目录下...

    agg2.5源码+文档

    "agg2.5源码+文档" 是一个开源项目,主要提供了一个强大的、跨平台的2D图形库。这个库的名称"agg"是“Anti-Grain Geometry”的缩写,它是一个高度优化的C++库,专为高质量的矢量图形渲染而设计。这个库的版本号2.5...

    AGG是一个开源、高效的跨平台2D图形库 这是它的离线文档

    - **Path Processing**:处理图形路径,支持贝塞尔曲线、直线和其他几何形状的构建和操作。 - **Color Models and Blending**:提供了多种颜色模型(RGB、CMYK等)和混合模式,实现复杂的色彩效果。 - **Buffers ...

    agg在windows平台编译

    AGG(Anti-Grain Geometry)是一个开源的2D图形渲染引擎,主要用于生成高质量的矢量图形。在Windows平台上,如果你需要使用AGG库进行图形处理或开发项目,你可能会遇到如何在Visual Studio 2013环境下编译和集成AGG...

    AGG与GDI两种图形库在MFC下的图形绘制

    AGG库提供了一套高级的几何算法,支持贝塞尔曲线、路径剪裁和混合模式等功能。在MFC中使用AGG,我们需要创建自定义的设备上下文类,以便在AGG渲染器和MFC之间建立桥梁。AGG的优势在于其卓越的绘制质量和高效率,尤其...

    Agg的.NET移植Agg-Sharp.zip

    Agg-Sharp 是 Agg 的 .NET 移植。AGG 是一个开源的二维图形引擎。它提供一套结合了亚像素(subpixel accuracy)技术与反走样(anti-aliasing)技术的图形算法,实现高效率、高质量的二维图形处理功能。AGG 的另一个...

    用AGG实现高质量图形输出.pdf

    扫描线光栅化器是AGG中的核心组件之一,负责将图形数据转化为一组水平扫描线。 - **扫描线** (`Scanline`):表示图像中的每一行像素。 - **头文件**:`agg_scanline_u.h` - **类型**:`agg::scanline_u8` - **...

    Agg学习资料

    Agg(Anti-Grain Geometry)是一个开源的2D图形渲染引擎,主要由Alexander Romanov开发,用于创建高质量的矢量图形。这个库提供了一种高效且灵活的方式来处理图形,适用于各种应用程序,如图像处理软件、游戏开发、...

    agg 开源的、高效的2D图形库

    4、支持高质量的图形处理,支持反走样插值等高级功能; 5、支持任意方式的惭变色处理; 6、支持所有颜色格式; 7、支持对位图的多种处理; 8、支持直线的多种处理,类似于GDI+; 9、支持GPC,即通用...

    agg学习手册

    ### AGG学习手册知识点解析 #### 一、AGG简介 **AGG**(Anti-Grain Geometry)是一个开源的2D图形库,以其高效、跨平台的特点而著称。相较于GDI+(Graphics Device Interface Plus),AGG不仅提供了更为灵活的编程...

    agg2.zip_High Fidelity_agg_graphics engine

    3. **曲线拟合**:AGG采用高精度的贝塞尔曲线和样条曲线算法,确保曲线的精确绘制。 4. **颜色空间管理**:AGG支持多种颜色空间,如RGB、CMYK、HSV等,并可以进行色彩空间转换,以适应不同的显示设备和输出媒介。 ...

    用AGG实现高质量图形输出.zip

    AGG,全称为“Anti-Grain Geometry”,是一款开源的2D图形渲染库,专为生成高质量、抗锯齿的图像而设计。它提供了一种高效且灵活的方式来创建和操作图形,尤其适用于需要高精度和高性能的场景,比如专业级的图形设计...

    agg2_lite_agg_

    "AGG Lite",这个标题暗示我们关注的是一个轻量级的图形绘制库,可能是一个专为嵌入式系统或资源有限的环境设计的版本。AGG,全称Anti-Grain Geometry,是一个著名的C++矢量图形库,用于高质量的2D图形渲染。它以其...

    agg-2.5.zip

    一个很优秀的2D图形引擎. Anti-Grain Geometry (AGG) - Version 2.5 A high quality rendering engine for C++ Copyright (C) 2002-2006 Maxim Shemanarev

    详谈pandas中agg函数和apply函数的区别

    - `apply`: 相比之下,`apply`更加**通用**,它可以应用于整个DataFrame或其任何子部分,并执行任意的Python或NumPy函数,甚至用户自定义函数(UDF)。`apply`并不局限于聚合,它允许对数据进行更复杂的操作,如...

Global site tag (gtag.js) - Google Analytics