Оптимизация

[heaven]

Занимаюсь оптимизацией видимых объектов в проге на движке (glscene)
И вот такая незадача выходит: надо сделать так, чтобы объекты, которые находятся вне радиуса обзора камера скрывались.

я попытался решить проблему "в лоб" - в реальном времени просчитывалось растояние до каждого предмета, и предметы растояние от камеры которых превышало предел скрывались - в итоге жуткие тормоза

когда я попробовал расчитывать растояние в каждую миллисекнду - каждую миллисекунду проверялось растояние до нового объекта - объекта стали исчезать и появляться прямо перед камерой...

мне кажется надо разбить общее кол-во объектов на группы и с группами оперировать, но этот способ тоже имеет ряд недостатков...

Может кто-нибудь подскажет альтернативный вариант оптимизации?

 

[metod]

а что ты понимаешь под радиусом обзора камеры? зачем выводить предметы, которые находятся "сзади" камеры? радиус, он же "круглый"

 

[Paha]

Вариант первый - вместо окружности, внутри которой объекты считаются видимыми, использовать квадрат. Т.е. вместо формулы
(xObj - xCam)^2 + (yObj - yCam)^2 < R^2
использовать Abs(xObj - xCam) < R "И" Abs(yObj - yCam) < R - избавляешься от двух умножений и сложения. Но всё равно приходится перебирать все объекты.
Отсюда вариант второй:
Местность бъётся регулярной сеткой. Каждая ячейка сетки хранит список объектов, которые в ней находятся. При отрисовке:
1) определяется, в какой ячейке находится камера.
2) берутся ячейки окружающие ячейку с камерой и выводятся объекты, которые хранятся в этих ячейках.
Плюсы:
Метод не зависит от кол-ва объектов
Можно держать список видимых объектов и обновлять его только при переходе камеры из одной ячейки в другую.

 

[heaven]

Вариант первый - вместо окружности, внутри которой объекты считаются видимыми, использовать квадрат. Т.е. вместо формулы
(xObj - xCam)^2 + (yObj - yCam)^2 < R^2
использовать Abs(xObj - xCam) < R "И" Abs(yObj - yCam) < R - избавляешься от двух умножений и сложения. Но всё равно приходится перебирать все объекты.
Отсюда вариант второй:
Местность бъётся регулярной сеткой. Каждая ячейка сетки хранит список объектов, которые в ней находятся. При отрисовке:
1) определяется, в какой ячейке находится камера.
2) берутся ячейки окружающие ячейку с камерой и выводятся объекты, которые хранятся в этих ячейках.
Плюсы:
Метод не зависит от кол-ва объектов
Можно держать список видимых объектов и обновлять его только при переходе камеры из одной ячейки в другую.

Второй способ более или мене реальный, но возникают некоторые вопросы...
1. Видимо прийдётся выводить объекты не только из яйчейки, в которой находится камера, но и из тех яйчеек, которые её окружают.
2. Так как размер рельефа не фиксированный появляется проблема расчёта длины \ ширины сетки, и размера одной яйчейки входящей в сетку.

 

[Paha]

Второй способ более или мене реальный, но возникают некоторые вопросы...
1. Видимо прийдётся выводить объекты не только из яйчейки, в которой находится камера, но и из тех яйчеек, которые её окружают.
2. Так как размер рельефа не фиксированный появляется проблема расчёта длины \ ширины сетки, и размера одной яйчейки входящей в сетку.

Размер одной ячейки можно задать равным радиусу видимости объектов. В этом случае нужно выводить только 6 ячеек, окружающих камеру.
Алгоритм у меня был бы такой (СПВО - список видимых объектов)
1) Добавить в СПВО объекты из ячейки с камерой
2) Добавить в СПВО объекты из 6 окружающих ячеек (по желанию можно не добавлять объекты из ячеек "СЗАДИ" камеры).
3) Дальше уже можно извращаться. Например, выкинуть из СПВО объекты не попадающие в FOV камеры.

 

[heaven]

Размер одной ячейки можно задать равным радиусу видимости объектов. В этом случае нужно выводить только 6 ячеек, окружающих камеру.
Алгоритм у меня был бы такой (СПВО - список видимых объектов)
1) Добавить в СПВО объекты из ячейки с камерой
2) Добавить в СПВО объекты из 6 окружающих ячеек (по желанию можно не добавлять объекты из ячеек "СЗАДИ" камеры).
3) Дальше уже можно извращаться. Например, выкинуть из СПВО объекты не попадающие в FOV камеры.

спасибо, буду воплощать

 

[nit0shi]

Вай-вай Ребята, вот енто да... Я в графике полный ноль

 

[iGeL]

Вай-вай Ребята, вот енто да... Я в графике полный ноль

люди делом занимаются, а ты ту флудишь, а еще модером называешся :shure:

з.ы.люблю такие логические задачки, правдо кодить бывает влом, одно дело на словах, другое дело на с++ все записать, да еще что бы работало...хотя бы запускалось.

 

[Badger]

Есть еще идея, не знаю только вовремя ли заглянул сюда..

На карте есть m объектов n1, n2, .. nm
Если брать только два измерения, то у каждого объекта на карте будет две координаты x и y.
представим объект в виде записи:

Tn=record
  x,y:integer
end;

В начале действия надо построить два массива записей, в которых хранились бы координаты x и y для всех присутствующих объектов и номера этих самых объектов.

TCoord=record
  Coord,Num:integer;
end;
...
var
  XCoords,YCoords:array of TCoord;
  Objects:array of Tn;
  Camera:Tn;

Заполнить оба массива соответствующими координатами объектов:

setlength(XCoords,m);
setlength(YCoords,m);
for i:=0 to length(Objects)-1 do begin
  XCoords[i].Coord:=Objects[i].x;
  XCoords[i].Num:=i;
  YCoords[i].Coord:=Objects[i].y;
  YCoords[i].Num:=i;
end;

Упорядочить оба массива записей YCoords и XCoords по полю Coord.

Если представить, что камера - тоже объект, то у нее тоже есть x и y.
Пусть r - радиус видимости. Для простоты пусть поле обзора всеже будет квадратным )

Далее, при каждой прорисовке достаточно быстро можно сначала из упорядоченного массива координат x отобрать номера объектов для которых координата лежит в пределах от Camera.x-r до Camera.x+r. А затем из полученных номеров точно также из второго массива выбрать те, для которых y лежит в пределах от Camera.y-r до Camera.y+r.

Если все объекты всегда остаются на своих местах, то при каждом движении надо будет отбирать для прорисовки номера лишь видимых объектов и из массива объектов по этому номеру уже выуживать Objects[m];

Если же какой-то из объектов Objects[m] решит "ходить", то придется в списке объектов задать ему новые координаты, и изменить соответствующее ему элементы массивов для которых поле Num==m.
Тут, если объектов очень много, придется сначала упорядочить эти массивы по полю Num, чтобы получить возможность быстро найти нужный элемент, а установив его значение Coord, заново упорядочить массив по этому полю (Coord).

Возможно, будет разумным завести отдельные массивы координат для движущихся и статичных объектов. Тогда, при перемещениях первых, не придется перелопачивать все объекты, а разобраться внутри небольшого списка движущихся.

P.s. для простого варианта, где объектов немного наверное нет смысла парить алгоритмы быстрого поиска и быстрой сортировки, а ограничиться простым перебором. А вот с ростом количества объектов, думаю, такой алгоритм может оказаться оправданным.
P.p.s. прошу не ругать матом, если это все окажется глупостью. Всеже ускорение любой обработки данных связано с упорядочиванием обрабатываемых данных. В теории баз данных это даказано. А массивы координат в данном случае - аналог индексов.

 

[heaven]

Есть еще идея, не знаю только вовремя ли заглянул сюда..

На карте есть m объектов n1, n2, .. nm
Если брать только два измерения, то у каждого объекта на карте будет две координаты x и y.
представим объект в виде записи:

Tn=record
  x,y:integer
end;

В начале действия надо построить два массива записей, в которых хранились бы координаты x и y для всех присутствующих объектов и номера этих самых объектов.

TCoord=record
  Coord,Num:integer;
end;
...
var
  XCoords,YCoords:array of TCoord;
  Objects:array of Tn;
  Camera:Tn;

Заполнить оба массива соответствующими координатами объектов:

setlength(XCoords,m);
setlength(YCoords,m);
for i:=0 to length(Objects)-1 do begin
  XCoords[i].Coord:=Objects[i].x;
  XCoords[i].Num:=i;
  YCoords[i].Coord:=Objects[i].y;
  YCoords[i].Num:=i;
end;

Упорядочить оба массива записей YCoords и XCoords по полю Coord.

Если представить, что камера - тоже объект, то у нее тоже есть x и y.
Пусть r - радиус видимости. Для простоты пусть поле обзора всеже будет квадратным )

Далее, при каждой прорисовке достаточно быстро можно сначала из упорядоченного массива координат x отобрать номера объектов для которых координата лежит в пределах от Camera.x-r до Camera.x+r. А затем из полученных номеров точно также из второго массива выбрать те, для которых y лежит в пределах от Camera.y-r до Camera.y+r.

Если все объекты всегда остаются на своих местах, то при каждом движении надо будет отбирать для прорисовки номера лишь видимых объектов и из массива объектов по этому номеру уже выуживать Objects[m];

Если же какой-то из объектов Objects[m] решит "ходить", то придется в списке объектов задать ему новые координаты, и изменить соответствующее ему элементы массивов для которых поле Num==m.
Тут, если объектов очень много, придется сначала упорядочить эти массивы по полю Num, чтобы получить возможность быстро найти нужный элемент, а установив его значение Coord, заново упорядочить массив по этому полю (Coord).

Возможно, будет разумным завести отдельные массивы координат для движущихся и статичных объектов. Тогда, при перемещениях первых, не придется перелопачивать все объекты, а разобраться внутри небольшого списка движущихся.

P.s. для простого варианта, где объектов немного наверное нет смысла парить алгоритмы быстрого поиска и быстрой сортировки, а ограничиться простым перебором. А вот с ростом количества объектов, думаю, такой алгоритм может оказаться оправданным.
P.p.s. прошу не ругать матом, если это все окажется глупостью. Всеже ускорение любой обработки данных связано с упорядочиванием обрабатываемых данных. В теории баз данных это даказано. А массивы координат в данном случае - аналог индексов.

Интересная идея
Допишу текущий алгоритм (с разделением на сектора) и попробую воплотить твой, потом сравню производительность

 

[Badger]

Интересная идея
Допишу текущий алгоритм (с разделением на сектора) и попробую воплотить твой, потом сравню производительность

Ну, вижу энтузиазма тебе не занимать!.. Пингвин в помощь!)) Если сделаешь - расскажи, интересно.

 

[Mr.Ban]

Ну, вижу энтузиазма тебе не занимать!.. Пингвин в помощь!)) Если сделаешь - расскажи, интересно.

Да...Venom-герой. Будем ждать.

 

[heaven]

вот бета алгоритмичек рабочий родился, разбивающий ландшафт на секции, и группирующий объекты по этим секциям:

var

i, xs, ys : integer;
XSecCount : single;
YSecCount : single;
XSecWidth : single;
YSecWidth : single;
ObjectsCount : integer;
CurrentX, CurrentY : single;
xvar, yvar : integer;
SecSaveName : string;

begin

 if not assigned(LoadForm) then LoadForm := TLoadForm.Create(Self);
 LoadForm.Show;
 Application.ProcessMessages;
 Screen.Cursor := crHourGlass;

XSecCount := Int(SpinEdit10.Value / Camera.DepthOfView * 2);
YSecCount := Int(SpinEdit11.Value / Camera.DepthOfView * 2);
XSecWidth := Int(SpinEdit10.Value / XSecCount);
YSecWidth := Int(SpinEdit11.Value / YSecCount);
CurrentY := 0;
CurrentX := 0;          

ObjectsCount := MapFile.ReadInteger('Map Objects', 'Static Mesh Count', 0);
if FileExists(Optimization.FileName) then DeleteFile(Optimization.FileName);

Optimization.WriteFloat('Format', 'XSecCount', XSecCount);
Optimization.WriteFloat('Format', 'YSecCount', YSecCount);

Optimization.WriteFloat('Format', 'XSecWidth', XSecWidth);
Optimization.WriteFloat('Format', 'YSecWidth', YSecWidth);


//====1. Sections Checking======================================================
//====SAMPLE: "for i:=0 to 3 do for j:=0 to 3 do begin"=========================

LoadForm.ProgressBar1.MaxValue := ObjectsCount;
LoadForm.ProgressBar1.Progress := 0;

xvar :=0;
yvar:=0;

for xs :=0 to StrToInt(FloatToStr(XSecCount)) do for ys:=0 to StrToInt(FloatToStr(YSecCount)) do begin

if xs=(xvar+1) then CurrentX := CurrentX+XSecWidth;
if ys=(yvar+1) then CurrentY := CurrentY+YSecWidth;
if ys=0 then CurrentY := 0;

//====2. Static Mesh Checking===================================================
//====WARNING! abciss "z" = "y" and xcoords changed to -xcoords=================

  for i:=1 to ObjectsCount do
    BEGIN

LoadForm.ProgressBar1.Progress := i;
LoadForm.Label1.Caption := 'StaticMesh_'+IntToStr(i)+': x sec = '+IntTosTR(xs)+' y sec = '+IntTosTR(ys);
Application.ProcessMessages;

if MapFile.ReadFloat('StaticMesh_'+IntToStr(i), 'Position X', 0) >= -(CurrentX+XSecWidth) then
if MapFile.ReadFloat('StaticMesh_'+IntToStr(i), 'Position X', 0) <= -CurrentX then
if MapFile.ReadFloat('StaticMesh_'+IntToStr(i), 'Position Z', 0) <= CurrentY+YSecWidth then
if MapFile.ReadFloat('StaticMesh_'+IntToStr(i), 'Position Z', 0) >= CurrentY then

begin
secsavename := 'Section|'+FloatToStr(-(CurrentX))+'|'+FloatToStr(-(CurrentX+XSecWidth))+'|'+FloatToStr(CurrentY)+'|'+FloatToStr(CurrentY+YSecWidth);
Optimization.WriteString('Sections', 'Section_'+IntToStr(xs)+'_'+IntToStr(ys), secsavename);
Optimization.WriteInteger(secsavename, 'Objects Count', Optimization.ReadInteger(secsavename, 'Objects Count', 0)+1);
Optimization.WriteString(secsavename, 'Object'+IntToStr(Optimization.ReadInteger(secsavename, 'Objects Count', 0)), 'StaticMesh_'+IntToStr(i));
end;

    END;

//====Display===================================================================

xvar := xs; yvar := ys;

end;

Label33.Caption := 'XSecCont = '+FloatTostr(XSecCount);
Label34.Caption := 'YSecCont = '+FloatTostr(XSecCount);
Label35.Caption := 'XSecWidth = '+FloatTostr(XSecWidth);
Label36.Caption := 'YSecWidth = '+FloatTostr(YSecWidth);

 LoadForm.Close;
 Screen.Cursor := crDefault;

Memo1.Lines.Clear;

returndir;
Optimization.UpdateFile;
returndir;
Memo1.Lines.LoadFromFile(Optimization.FileName);

end;