c++ - 使用OpenGL渲染具有大量顶点的填充多边形

Question

我使用OpenGL渲染2D map ，在此过程中，我需要渲染具有大量顶点的填充多边形(100,000+)。为此，我使用glu tessellator将多边形细分为三角形，并使用VBO渲染了三角形。

多边形成功渲染。 问题在于，镶嵌处理过程非常缓慢。 对于某些带有500,000顶点的图表，在我的笔记本电脑(i5-3230M 2.6GHz，8G RAM)上，将花费 2分钟。这对于我的应用程序是 Not Acceptable 。

是否有其他比glu tessellator更快的细分算法？

还是我做错了？

以下两张图片是渲染结果

glPolygonMode(GL_FRONT, GL_LINE)

编辑: map 数据是静态的，原始多边形数据是经纬度格式。我已经将镶嵌多边形数据(那些三角形)保存在单独的文件中。

为了更清楚(与问题不直接相关)，为了在屏幕上渲染，需要进行投影以将LL格式转换为屏幕坐标。

问题在于用户可能要安装成千上万个图表(将在其中进行细分)。尽管镶嵌将只运行一次，但仍然需要太长时间。

Answer 1

map 是静态的还是动态的？

对于静态 map

为什么不将经过镶嵌处理的多边形存储在某些文件中，而不再次对它进行镶嵌处理...

用于动态 map

使用不需要像这样的凸多边形进行镶嵌的其他渲染方法，可能会更快:

带有岛屿颜色的清晰屏幕

渲染岛轮廓

像GL_LINE_LOOP这样的未填充原语根本不需要进行镶嵌处理。

填写浪费

只需从任意多边形外部的点开始，然后用水淹没 map 即可。如果泛洪填充编码正确(没有递归并且用行而不是像素填充)，那么它应该只需要几[ms]。这种方法的问题在于，您需要访问渲染的内容，因此至少需要进行2次渲染。在 GPU上实现泛洪填充也不容易。

还有其他选择，例如将边缘点存储在 CPU 侧，并预先计算 CPU 侧的填充量。在这种情况下，您需要为图像的每个x扫描线提供y坐标列表，这些坐标线将保存每个区域的起点和终点。然后只需在单个渲染过程中填补空白...

这应该在 RT中渲染轻松

[编辑]增长填充测试演示

用迭代进行了一些测试，以填充您的数据。数据集存在一些问题，例如您的多边形重叠可能只是孔，但由于我没有填充颜色信息，而只是对象 ID ID ，因此很难说。无论如何也可以修复。这是上面我提到的方法的小胜32 VCL / OpenGL / SW 演示( 动态 map ):

Win32 Demo使用慢速下载，这是免费的，无需任何注册即可输入代码。

Win32独立版，无需使用OpenGL + VCL进行安装

鼠标滚轮缩放

Shift +鼠标轮选择不同的多边形

鼠标+左按钮平移

几乎没有可以修复的问题，但是作为概念证明，它很好用。我将ASCII映射图编译为二进制形式(因此加载速度更快，但形式只是多边形数相同，然后每个多边形的点数和x，y的点数都为64位 double 。计数为32位整数)

我使用的是我自己的OpenGL引擎(我无法共享)，因此您需要对内容进行编码(例如OpenGL， FBO和Texture init / set / usage)。无论如何，此 VCL 应用程序的 C++ 代码:

//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "win_main.h"
#include "gl/OpenGL3D_double.cpp"
#include "performance.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
// VCL
TMain *Main;
// OpenGL
OpenGLtime tim;
OpenGLscreen scr;
OpenGL_FBO fbo;
GLuint txr_map=-1;
// miscel
int pn=0;                       // vertex count
double px0,px1,py0,py1;         // bbox
double mx,my;                   // mouse
double view[16],iview[16];      // direct and inverse Modelview matrix
double zoom=1.0,dzoom=1.1,viewx=0.0,viewy=0.0;  // view
int index=0;                    // selected polygon
bool _redraw=true;
DWORD cl_water=0xFFEE9040;
DWORD cl_land =0xFF70A0B0;
DWORD cl_edge =0xFF000000;
DWORD cl_sel  =0xFF00FFFF;
AnsiString tcpu,tgpu;
// map
List< List<double> > polygon;   // loaded polygons
      List<double>   water;     // points with water from last frame
//---------------------------------------------------------------------------
void view_compute()
    {
    double x,y;
    glMatrixMode(GL_MODELVIEW);
    glPushMatrix();
    glLoadIdentity();
    x=divide(1.0,px1-px0)*scr.aspect;
    y=divide(1.0,py1-py0)*scr._aspect;
    if (x>y) x=y;
    x*=zoom;
    glTranslated(viewx,viewy,0.0);
    glScaled(x,x,1.0);
    glTranslated(-0.5*(px0+px1),-0.5*(py0+py1),0.0);
    glGetDoublev(GL_MODELVIEW_MATRIX,view);
    glPopMatrix();
    matrix_inv(iview,view);
    }
//---------------------------------------------------------------------------
void map_load_csv(AnsiString filename)
    {
    BYTE *dat;
    AnsiString lin,s,s0;
    int ix,i,l,hnd,siz,adr;
    double x,y;
    List< AnsiString > id;

         id.allocate(128);      id.num=0;
    polygon.allocate(128); polygon.num=0;

    hnd=FileOpen(filename,fmOpenRead); if (hnd<0) return;
    siz=FileSeek(hnd,0,2);
        FileSeek(hnd,0,0);
    dat=new BYTE[siz]; if (dat==NULL) { FileClose(hnd); return; }
    siz=FileRead(hnd,dat,siz);
    FileClose(hnd);

    adr=0; txt_load_lin(dat,siz,adr,true);
    for (ix=-1,s0="";adr<siz;)
        {
        lin=txt_load_lin(dat,siz,adr,true);
        if (lin=="") continue;
        i=1; l=lin.Length();
        s=str_load_str(lin,i,true); s=s.SubString(2,s.Length()-2);
        if (s0!=s)
            {
            for (ix=0;ix<id.num;ix++) if (id[ix]==s) break;
            if (ix>=id.num)
                {
                ix=id.num;
                id.add(s);
                polygon.add();
                polygon[ix].allocate(256);
                polygon[ix].num=0;
                }
            s0=s;
            }
        s=str_load_str(lin,i,true); s=s.SubString(2,s.Length()-2); x=str2flt(s);
        s=str_load_str(lin,i,true); s=s.SubString(2,s.Length()-2); y=str2flt(s);
        polygon[ix].add(x);
        polygon[ix].add(y);
        }
    }
//---------------------------------------------------------------------------
void map_save_bin(AnsiString filename)
    {
    int hnd,i;
    hnd=FileCreate(filename); if (hnd<0) return;
    FileWrite(hnd,&polygon.num,4);
    for (i=0;i<polygon.num;i++)
        {
        FileWrite(hnd,&polygon[i].num,4);
        FileWrite(hnd,polygon[i].dat,polygon[i].num*8);
        }
    FileClose(hnd);
    }
//---------------------------------------------------------------------------
void map_load_bin(AnsiString filename)
    {
    int hnd,i,n,m;
    hnd=FileOpen(filename,fmOpenRead); if (hnd<0) return;
    FileRead(hnd,&n,4);
    polygon.allocate(n); polygon.num=n;
    for (i=0;i<n;i++)
        {
        FileRead(hnd,&m,4);
        polygon[i].allocate(m); polygon[i].num=m;
        FileRead(hnd,polygon[i].dat,m*8);
        }
    FileClose(hnd);
    }
//---------------------------------------------------------------------------
void map_bbox()
    {
    int ix,i,n;
    double *p,a;
    pn=0;
    px0=px1=polygon[0][0];
    py0=py1=polygon[0][1];
    for (ix=0;ix<polygon.num;ix++)
        {
        p=polygon[ix].dat;
        n=polygon[ix].num; pn+=n>>1;
        for (i=0;i<n;i+=2)
            {
            a=*p; p++; if (px0>a) px0=a; if (px1<a) px1=a;
            a=*p; p++; if (py0>a) py0=a; if (py1<a) py1=a;
            }
        }
    }
//---------------------------------------------------------------------------
void map_draw()
    {
    int ix,i,n;
    double *p,a;
//  glLineWidth(2.0);
    for (ix=0;ix<polygon.num;ix++)
        {
        p=polygon[ix].dat;
        n=polygon[ix].num;
        if (ix==index) glColor4ubv((BYTE*)&cl_sel);
         else          glColor4ubv((BYTE*)&cl_edge);
        glBegin(GL_LINE_LOOP);
        for (i=0;i<n;i+=2,p+=2) glVertex2dv(p);
        glEnd();
        }
//  glLineWidth(1.0);
    }
//---------------------------------------------------------------------------
void TMain::draw()
    {
    tbeg();
    tim.tbeg();

    // [ render outline to texture ]
    fbo.bind(scr);
    glClearColor(divide((cl_land)&255,255),divide((cl_land>>8)&255,255),divide((cl_land>>16)&255,255),1.0);
    scr.cls();
    glMatrixMode(GL_MODELVIEW);
    glLoadMatrixd(view);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();

    if (water.num)  // water start points for grow fill
        {
        // add water around txr border
        glBegin(GL_POINTS);
        glColor4ubv((BYTE*)&cl_water);
        for (int i=0;i<water.num;i+=2)
         glVertex2dv(water.dat+i);
        glEnd();
        }

    map_draw();
    scr.exe();

    fbo.unbind(scr);

    // [ copy GL texture to CPU image ]
    scr.txrs.txr_ld(txr_map);
    // [ create ScanLines for direct pixel access pyx[y][x] ]
    int e,x,y,xs,ys; DWORD **pyx,*p,c0,c1; double a[3];
    xs=scr.txrs.txr.xs;                     // texture resolution (rounded up to power of 2)
    ys=scr.txrs.txr.ys;
    pyx=new DWORD*[ys];
    p=(DWORD*)scr.txrs.txr.txr;             // CPU image pixel data
    for (y=0;y<ys;y++,p+=xs) pyx[y]=p;      // scan line pointers

    // [ Grow Fill water ]
    c0=rgb2bgr(cl_land);
    c1=rgb2bgr(cl_water);
    if (water.num==0)   // first frame view must be set so water is on all borders
        {
        // add water around txr border
        for (x=   1,y=0;y<ys;y++) pyx[y][x]=c1;
        for (x=xs-2,y=0;y<ys;y++) pyx[y][x]=c1;
        for (y=   1,x=0;x<xs;x++) pyx[y][x]=c1;
        for (y=ys-2,x=0;x<xs;x++) pyx[y][x]=c1;
        }

    for (e=1;e;)                            // grow it
    for (e=0,y=1;y<ys-1;y++)
     for (   x=1;x<xs-1;x++)
      if (pyx[y][x]==c0)
       if ((pyx[y-1][x]==c1)
         ||(pyx[y+1][x]==c1)
         ||(pyx[y][x-1]==c1)
         ||(pyx[y][x+1]==c1)) { e=1; pyx[y][x]=c1; }

    // create water start points for next frame
    water.num=0;
    e=4;    // step
    for (y=1;y<ys-2;y+=e)
     for (x=1;x<xs-2;x+=e)
       if ((pyx[y-1][x-1]==c1) // enough water around (x,y)?
         &&(pyx[y-1][x  ]==c1)
         &&(pyx[y-1][x+1]==c1)
         &&(pyx[y  ][x-1]==c1)
         &&(pyx[y  ][x  ]==c1)
         &&(pyx[y  ][x+1]==c1)
         &&(pyx[y+1][x-1]==c1)
         &&(pyx[y+1][x  ]==c1)
         &&(pyx[y+1][x+1]==c1))
            {
            // convert pixel(x,y) -> World(x,y)
            a[0]=divide(2.0*x,xs)-1.0;
            a[1]=divide(2.0*y,ys)-1.0;
            a[2]=0.0;
            matrix_mul_vector(a,iview,a);
            water.add(a[0]);
            water.add(a[1]);
            }

    // [ copy CPU image back to GL texture ]
    delete[] pyx;                           // release ScanLines no need for them anymore
    scr.txrs.txr.rgb2bgr();                 // I got RGB/BGR mismatch somewhere
    scr.txrs.txr_st(txr_map);               // scr.txrs.txr.txr holds pointer to 32bit pixel data
    scr.exe();

    // [ render texture to screen ]
    scr.cls();
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    scr.txrs.bind(txr_map);
    glColor3f(1.0,1.0,1.0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0,0.0); glVertex2f(-1.0,-1.0);
    glTexCoord2f(1.0,0.0); glVertex2f(+1.0,-1.0);
    glTexCoord2f(1.0,1.0); glVertex2f(+1.0,+1.0);
    glTexCoord2f(0.0,1.0); glVertex2f(-1.0,+1.0);
    glEnd();
    scr.txrs.unbind();
    // [info]
    glColor3f(1.0,1.0,1.0);
    scr.text_init_pix(1.0);
    scr.text(tcpu);
    scr.text(tgpu);
    scr.text_exit();

    scr.exe();
    scr.rfs();

    tend(); tcpu=" CPU time: "+tstr(1);
    tim.tend();
    }
//---------------------------------------------------------------------------
void TMain::mouse(double x,double y,TShiftState sh)
    {
    x=divide(2.0*x,scr.xs)-1.0;
    y=1.0-divide(2.0*y,scr.ys);
    if (sh.Contains(ssLeft))
        {
        viewx+=x-mx;
        viewy+=y-my;
        view_compute();
        _redraw=true;
        }
    mx=x;
    my=y;
    }
//---------------------------------------------------------------------------
__fastcall TMain::TMain(TComponent* Owner) : TForm(Owner)
    {
    scr.init(this);
    txr_map=fbo.add(scr);
//  map_load_csv("map.csv");
//  map_save_bin("map.bin");
    map_load_bin("map.bin");
    map_bbox();
    view_compute();
    draw();
    _redraw=true;
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormDestroy(TObject *Sender)
    {
    scr.exit();
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormPaint(TObject *Sender)
    {
    _redraw=true;
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormResize(TObject *Sender)
    {
    scr.resize();
    fbo.resize(scr);
    _redraw=true;
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormMouseWheel(TObject *Sender, TShiftState Shift, int WheelDelta, TPoint &MousePos, bool &Handled)
    {
    if (Shift.Contains(ssShift))
        {
        if (WheelDelta>0) index++; else index--;
        if (index>=polygon.num) index=polygon.num-1;
        if (index<0) index=0;
        _redraw=true;
        }
    else{
        double p[3]={ mx,my,0.0 };
        view_compute();
        matrix_mul_vector(p,iview,p);
        if (WheelDelta>0) zoom*=dzoom; else zoom/=dzoom;
        view_compute();
        matrix_mul_vector(p,view,p);
        viewx-=p[0]-mx;
        viewy-=p[1]-my;
        view_compute();
        _redraw=true;
        }
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormMouseMove(TObject *Sender, TShiftState Shift, int X,int Y) { mouse(X,Y,Shift); }
void __fastcall TMain::FormMouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y) { mouse(X,Y,Shift); }
void __fastcall TMain::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y) { mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
void __fastcall TMain::Timer1Timer(TObject *Sender)
    {
    tgpu=AnsiString().sprintf(" GPU time: [%8.3lf ms]",tim.time());
    if (_redraw) { draw(); _redraw=false; }
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormDblClick(TObject *Sender)
    {
    Width+=10; // ignore this had some bug in resize FBO texture and this was for debugging it
    }
//---------------------------------------------------------------------------

我还使用了我的动态列表模板，因此:
List<double> xxx;与 double xxx[];相同 xxx.add(5);将 5添加到列表的末尾 xxx[7]访问数组元素(安全) xxx.dat[7]访问数组元素(不安全但快速的直接访问) xxx.num是数组的实际使用大小 xxx.reset()清除数组并设置 xxx.num=0 xxx.allocate(100)为 100项目预分配空间

如果您需要有关矩阵和 vector 数学例程的帮助，请参见以下内容:

Understanding 4x4 homogenous transform matrices

在底部的链接的答案中，您甚至可以找到我使用的C++实现...

您可以忽略 VCL 东西，该应用仅在其上带有一个计时器，间隔 40 ms即可重绘(如果需要)并获取小节GL时间(如果已准备好...)

对您来说重要的只是 draw()例程。

它是这样的:

绑定(bind) FBO 以启用对texture的渲染

用land color清除它

使用edge color渲染多边形轮廓

如果有孔，请使用watter color渲染它们，并在填充后再次使用edge color渲染它们

使用watter color渲染watter起点

在第一帧中，您应该不缩放 View ，以便所有土地都被水淹没。因此，第一个摆动点是纹理的边界矩形。

取消绑定(bind) FBO 并将纹理像素数据复制到 CPU 侧存储器

增长填充所有填充到land color像素(停止edge color或其他任何像素)

您可以使用任何填充(例如“洪水填充”，“分段线填充”等)，但请注意递归方法的堆栈溢出。我决定使用:

grow fill

由于它是迭代的。它的速度不那么快(因此，CPU时间很大，但是CPU时间的很大一部分是由于在GPU / CPU之间传输纹理时进行了同步)，但是可以通过将图像细分为“正方形”区域并在需要时传播填充来显着提高速度。

从该图像创建水位起点

因此，扫描整个图像(无需执行任何步骤即可扫描所有点)，如果找到了watter，则将其添加为下一帧的watter起始点watter(在世界坐标系中)。直到您的 View 在每一帧之间的变化不会太大时，这才可以正常工作，因此请限制缩放变化和平移步幅。

当新框架包含没有任何起点的垃圾桶并且其他垃圾桶无法访问时，就会出现gfx问题。这需要一些思考/测试，但我认为应该可以从第一帧获得的一些静态预定义的初始起点(每个多边形很少)可以解决。

直接渲染 CPU 侧面图像，或将其传递回 GL 纹理并进行渲染。

这里预览: