使用OpenGL渲染具有大量顶点的填充多边形 [英] Render filled complex polygons with large number of vertices with OpenGL
问题描述
我使用OpenGL渲染2D地图，在此过程中，我需要渲染具有大量顶点(100,000+)的填充多边形.为此，我使用glu tessellator将多边形细分为三角形，并使用VBO渲染了三角形.
I use OpenGL to render 2D map and in the process I need to render filled polygons with large number of vertices(100,000+). To do this, I tessellated the polygons to triangles using glu tessellator and rendered the triangles with VBO.
多边形成功渲染. 问题在于，镶嵌过程非常缓慢.对于某些具有500,000顶点的图表，在我的笔记本电脑上将花费将近 2分钟(i5-3230M 2.6GHz，8G RAM).这对于我的应用程序是不可接受的.
The polygons are rendered successfully. The problem is that the tessellation process turns out to be extremely slow. For some charts with 500,000 vertices, it will take nearly 2 mins on my laptop(i5-3230M 2.6GHz, 8G RAM). This is unacceptable for my application.
还有没有其他比glu tessellator更快的细分算法?
Are there any other tessellation algorithm faster than glu tessellator?
还是我做错了?
以下两张图片是
glPolygonMode(GL_FRONT, GL_LINE)
:地图数据是静态的，原始多边形数据是经纬度格式.我已经将镶嵌多边形数据(那些三角形)保存在单独的文件中.
EDIT : The map data is static and the original polygon data is in latitude-longitude format. I've already saved the tessellated polygon data (those triangles) in separate file.
为了更加清晰(与问题没有直接关系)，为了在屏幕上渲染，需要进行投影以将LL格式转换为屏幕坐标.
To be more clear(Not directly related to the issue),for rendering on screen, a projection is needed to transform the LL format to screen coordinates.
问题在于用户可能要安装成千上万张图表(将在其中进行细分).尽管镶嵌将只运行一次，但仍然需要太长时间.
The problem is that the user may have thousands of charts to install(in which the tessellation will be done). Although the tessellation will be run only once, it still takes too long.
推荐答案
地图是静态的还是动态的?
is the map static or dynamic?
用于静态地图
为什么不将镶嵌化的多边形存储在某些文件中，而不再次镶嵌化呢……
why not store tesselated polygons in some file and not tesselate it again ...
用于动态地图
使用不需要像这样的凸多边形进行镶嵌的其他渲染方法可能会更快:
would be may be faster using different rendering approach that do not need tesselation to convex polygons like this:
- 具有岛色的清晰屏幕
-
渲染岛轮廓
未填充原语根本不需要镶嵌.
not filled primitives like GL_LINE_LOOP do not need to tesselate at all.
填入垃圾
简单地从任何多边形外部的点开始，然后用水淹没地图.如果洪水填充编码正确(没有递归并且用行而不是像素填充)，那么它应该只需要几[ms].这种方法的问题在于，您需要访问渲染的内容，因此您至少需要进行2次渲染.在 GPU 上实现泛洪填充也不容易.
simply start from point outside any polygon and flood fill the map with watter. If the flood fill is coded right (no recursion and fill with lines instead of pixels) then it should take just few [ms]. The problem with this approach is that you need to access the rendered stuff so you need at least 2 passes of rendering. Also implementing flood filling on GPU is not easy.
还有其他选择，例如将边缘点存储在 CPU 侧并在 CPU 侧预先计算填充量.在这种情况下，您需要为图像的每个y扫描线提供一个x坐标列表，该列表将保存每个平台的起点和终点.然后只需在单个渲染过程中填补空白...
There are also alternatives like storing edge points on CPU side and pre-compute the watter filling on CPU side. In that case you need to have list of x coordinates for every y scan line of image that will hold the start and end points for each land. then just fill in the gaps in single render pass...
应轻松在 RT 中呈现
填充测试演示
对数据进行了迭代增长填充的一些测试.数据集存在一些问题，例如多边形重叠可能只是孔，但由于我没有填充颜色信息，而只有对象 ID ，所以很难说.无论如何也可以修复.这是使用我上面提到的方法(动态地图)进行的小型Win 32 VCL/OpenGL/SW 演示:
Did some testing with iterative grow filling on your data. There are some problems with the dataset like your polygons overlap which is possibly just holes but as I do not have filling color info but just object ID instead so it is hard to say. Anyway that can be repaired too. Here small win 32 VCL/OpenGL/SW demo with approach I mentioned above (Dynamic maps):
- Win32演示使用慢速下载，免费且无需下载任何注册只需输入代码即可.
- Win32 Demo use Slow download which is free and no need for any registration just input the code.
这是Win32独立版本，无需使用OpenGL + VCL进行安装
It is Win32 stand alone no install using OpenGL+VCL
- 鼠标滚轮缩放
- Shift +鼠标滚轮选择不同的多边形
- 鼠标+左键平移
几乎没有可以修复的问题，但是作为概念证明，它可以很好地工作.我将ASCII映射图编译为二进制形式(因此加载速度更快，但形式只是多边形数相同，然后每个多边形的点数和x，y的点数都为64位双精度.计数为32位整数)
There are few issues which can be repaired but as proof of concept it works well. I compiled your ASCII map into binary form (so it loads faster but the form is the same just count of polygons, then count of points per polygon and the points x,y as 64 bit doubles. Counts are 32bit ints)
我使用的是我自己的OpenGL引擎(无法共享)，因此您需要对这些东西进行编码(例如OpenGL， FBO 和Texture init/set/usage).无论如何，此 VCL 应用程序的 C ++ 代码:
I am using my own OpenGL engine (which I can not share) so you would need to encode the stuff (like OpenGL,FBO and Texture init/set/usage). Anyway here the C++ code for this VCL app:
//$$---- 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
}
//---------------------------------------------------------------------------
我还使用了我的动态列表模板，所以:
I also use mine dynamic list template so:
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个项目预分配空间
List<double> xxx; is the same as double xxx[];
xxx.add(5); adds 5 to end of the list
xxx[7] access array element (safe)
xxx.dat[7] access array element (unsafe but fast direct access)
xxx.num is the actual used size of the array
xxx.reset() clears the array and set xxx.num=0
xxx.allocate(100) preallocate space for 100 items
如果您需要有关矩阵和矢量数学例程的帮助，请参见以下内容:
If you need help with the matrix and vector math routines see this:
在底部的链接的答案中，您甚至可以找到我使用的C ++实现...
In the linked answers at the bottom you can find even the C++ implementations I use...
您可以忽略 VCL 的内容，该应用仅在其上间隔时间为40 ms的单个Timer即可在需要时重新绘制，并在准备就绪时获取公制GL时间...
You can ignore the VCL stuff the app just have single Timer on it with interval 40 ms to repaint if needed and fetch measuret GL time if ready...
对您来说重要的只是draw()例程.
The important stuff for you is just the draw() routine.
它是这样的:
- 绑定 FBO 以允许渲染到
texture - 用
land color清除它
-
使用
edge color
- bind FBO to enable rendering to
texture - clear it with
land color render polygons outline with
edge color
如果有孔，请使用watter color渲染它们，并在填充后再次使用edge color
if you got holes render them with watter color and after filling render them again with edge color
使用watter color
在第一帧中，您应该不缩放视图，以便所有土地都被水淹没.因此，第一个watter点是纹理的边框矩形.
in the first frame you should have view un-zoomed so all land is surrounded with watter. So the first watter points are the border rectangle of texture.
解除绑定 FBO 并将纹理像素数据复制到 CPU 侧存储器
unbind FBO and copy texture pixeldata to CPU side memory
将所有垃圾增加到land color像素(在edge color或其他任何像素上停止)
grow fill all watter to land color pixels (stop on edge color or any other)
您可以使用任何填充(例如Flood填充，分段线填充等)，但请注意堆栈递归方法的溢出.我决定使用:
You can use any fill like Flood fill, segmented line fill etc but beware stack overflow for recursive approach. I decided to use:
因为它是迭代的.它的速度不那么快(因此，CPU时间较长，但是CPU时间的很大一部分是由于在GPU/CPU之间传输纹理时进行了同步)，但是可以通过将图像细分为正方形"区域并在需要时传播填充来显着提高速度.
As it is iterative. It is not as fast (hence the big CPU times but big portion of the CPU time is due to sync while transfering texture between GPU/CPU) but can be speed-up significantly by subdividing image into "square" areas and propagate filling if needed.
从该图像创建水位起点
因此扫描整个图像(某些步骤不需要扫描所有点)，如果找到了watter，则将其添加为下一帧的watter起点watter(在世界坐标系中).直到您的视图在各帧之间的变化不会太大时，这才可以正常工作，因此请限制缩放变化和平移步幅...
so scan whole image (with some step do not need to scan all point) and if found watter add it as watter start point watter for next frame (in world coordinates). This works well until your view will not change too much from frame to frame so limit zoom change and pan step ...
当新框架包含无任何起始点且其他watter无法访问的watter时，就会出现gfx问题.这需要一些思考/测试，但我认为应该可以从第一帧中获得一些静态的预定义watter起点(每个多边形很少)来解决.
Here comes an gfx issue when new frame contains watter without any start points and not accessible to other watter. This need some thinking/testing but I think it should be solvable by some static predefined watter start points (few for each polygon) obtained from the first frame.
直接渲染 CPU 侧面图像，或将其传回 GL 纹理并进行渲染.
render CPU side image directly or pass it back to GL texture and render it.
这里预览:
这篇关于使用OpenGL渲染具有大量顶点的填充多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
