Визуализация заполненных сложных многоугольников с большим количеством вершин с помощью OpenGL

карта статическая или динамическая?

Для статических карт

почему бы не хранить тесселатированные полигоны в каком-то файле и не тесселять их снова …

Для динамических карт

будет быстрее, если использовать другой подход рендеринга, который не требует тесселяции для выпуклых многоугольников:

1. чистый экран с островным цветом

2. сделать острова очертаниями

   не заполненные примитивы типа GL_LINE_LOOP не нужно тесселят вообще.

3. залить воду

   просто начните с точки вне любого многоугольника и залейте карту водой. Если заливка запрограммирована правильно (без рекурсии и заполнения линиями вместо пикселей), это займет всего несколько [мс]. Проблема этого подхода заключается в том, что вам нужен доступ к отрендеренному материалу, поэтому вам нужно как минимум 2 прохода рендеринга. Также осуществляем заливку на GPU нелегко.

   Есть также альтернативы, такие как хранение точек на ЦПУ сторона и предварительно вычислить заполнение воды на ЦПУ боковая сторона. В этом случае вам нужно иметь список x координаты для каждого y отсканируйте линию изображения, которая будет содержать начальную и конечную точки для каждой земли. затем просто заполните пробелы в одном проходе рендера …

   Это должно быть представлено в RT без труда

[Править] Демо-тест Grow Fill

Провел тестирование с многократным заполнением ваших данных. Существуют некоторые проблемы с набором данных, например, перекрытие полигонов, возможно, это просто дыры, но у меня нет информации о цвете заполнения, а просто объект Я БЫ вместо этого так трудно сказать. В любом случае, это тоже можно починить. Здесь маленькая победа 32 VCL / OpenGL / SW демо с подходом, о котором я упоминал выше (Динамические карты):

• Win32 Demo используйте медленную загрузку, которая бесплатна и не требует регистрации, просто введите код.

Это Win32 автономно без установки с использованием OpenGL + VCL

• колесо мыши увеличивает
• Shift + колесо мыши выбирает другой многоугольник
• мышь + левая кнопка

Есть несколько проблем, которые можно исправить, но в качестве доказательства концепции это работает хорошо. Я скомпилировал вашу карту ASCII в двоичную форму (поэтому она загружается быстрее, но форма такая же, как и количество полигонов, а затем число точек на многоугольник и количество точек x, y как 64-битных двойных. Число 32-битных целых)

Я использую свой собственный движок OpenGL (которым я не могу поделиться), поэтому вам нужно будет кодировать вещи (например, OpenGL,FBO и текстура инициализация / установка / использование). Во всяком случае здесь C ++ код для этого VCL приложение:

//$$---- 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 Предметы

Если вам нужна помощь с матричными и векторными математическими процедурами, посмотрите это:

• Понимание 4×4 однородных матриц преобразования

В связанных ответах внизу вы можете найти даже реализации C ++, которые я использую …

Вы можете игнорировать VCL набить приложение просто таймером с интервалом 40 ms перекрасить, если нужно, и извлечь измеренное время GL, если готово …

Важная вещь для вас это просто draw() рутина.

Это работает так:

1. привязывать FBO включить рендеринг в texture
2. очистить это с land color

3. сделать контуры полигонов с edge color

   если у вас есть отверстия, сделайте их watter color и после заполнения отрендерить их снова edge color

4. отрисовывать начальные точки с помощью watter color

   в первом кадре изображение должно быть увеличено, чтобы вся земля была окружена водой. Итак, первые точки смачивания — это прямоугольник текстуры.

5. развязывать FBO и скопировать пиксельные данные текстуры в ЦПУ боковая память

6. расти заполнить всю воду, чтобы land color пикселей (остановка на edge color или любой другой)

   Вы можете использовать любую заливку, такую ​​как заливка потока, заполнение сегментированной строки и т. Д., Но остерегайтесь переполнения стека для рекурсивного подхода. Я решил использовать:

   • расти заполнить

   Как это итеративно. Это не так быстро (следовательно, большая загрузка ЦП, но большая часть времени ЦП обусловлена ​​синхронизацией при передаче текстуры между GPU / ЦП), но может быть значительно ускорена путем разделения изображения на «квадратные» области и распространения заполнения, если это необходимо ,

7. создать начальные точки из этого изображения

   так сканируйте все изображение (с некоторым шагом не нужно сканировать всю точку) и, если найдено, добавьте его в качестве начальной точки. watter для следующего кадра (в мировых координатах). Это работает хорошо, пока ваш вид не будет слишком сильно меняться от кадра к кадру, поэтому ограничьте изменение масштаба и шаг панорамирования …

   Здесь возникает проблема gfx, когда новый фрейм содержит воду без каких-либо начальных точек и недоступен для другой воды. Это требует некоторого размышления / тестирования, но я думаю, что это должно быть решено некоторыми статическими предопределенными начальными точками воды (несколько для каждого многоугольника), полученными из первого кадра.

8. оказывать ЦПУ боковое изображение напрямую или передать его обратно GL текстуры и визуализации.

Вот предварительный просмотр: