Ландшафты без quadtree и octree.

BOOL BR_Rotate(BR *br)
{
  int n,k;
  int x,y;
  int oldx,oldy;
  int sx,sy;
  int fx,fy;
  S32 ca, sa;
  ODPoint np1,np2,np3,np4;

  //1. Устанавливаем центр вращения
  ODPoint o= {br->masksize.x-br->centre.x, br->masksize.y-br->centre.y};

  //2. Для выбранного угла br->angle получаем значения cos и sin.
  ca=br->cos[br->angle&(BR_ANGLES-1)];
  sa=br->sin[br->angle&(BR_ANGLES-1)];

  //3. Устанавливаем точки по всем (четырем) углам маски:
  ODPoint p1={-o.x, -o.y};
  ODPoint p2={br->masksize.x-o.x, -o.y};
  ODPoint p3={0-o.x, br->masksize.y-o.y};
  ODPoint p4={br->masksize.x-o.x, br->masksize.y-o.y};

  //4. Поворачиваем маску по 4ем точкам на угол br->angle
  // Теперь, вы можете видеть, для чего нужно было умножать 
  // все табличные значения cos и sin на величину BR_MULT
  np1.x = ((p1.x*ca)>>BR_S) - ((p1.y*sa)>>BR_S);
  np1.y = ((p1.x*sa)>>BR_S) + ((p1.y*ca)>>BR_S);
  np2.x = ((p2.x*ca)>>BR_S) - ((p2.y*sa)>>BR_S);
  np2.y = ((p2.x*sa)>>BR_S) + ((p2.y*ca)>>BR_S);
  np3.x = ((p3.x*ca)>>BR_S) - ((p3.y*sa)>>BR_S);
  np3.y = ((p3.x*sa)>>BR_S) + ((p3.y*ca)>>BR_S);
  np4.x = ((p4.x*ca)>>BR_S) - ((p4.y*sa)>>BR_S);
  np4.y = ((p4.x*sa)>>BR_S) + ((p4.y*ca)>>BR_S);

  // Повернутое изображение будет всегда больше или равно 
  // (равно только при повороте на 0, 90, 180 и 270 градусов) width или height маски
  // Будем искать минимальные и максимальные значения, 
  // т.к. нам нужно узнать в какую область попадает повернутая маска.

  //5. находим верхний левый угол:
  sx= BR_MIN4(np1.x, np2.x, np3.x, np4.x);
  sy= BR_MIN4(np1.y, np2.y, np3.y, np4.y);

  // 6. находим нижний правый угол:
  fx = BR_MAX4(np1.x, np2.x, np3.x, np4.x)+2; 
  fy = BR_MAX4(np1.y, np2.y, np3.y, np4.y)+2; 
  // Вы заметили “+2”. Это не магическое число. 
  // Нам всего лишь нужно убедиться, что самые крайние правые и 
  // нижние точки на маске попадут в область. 
  // А необходимость обусловлена не точностью вычислений.

  // 7. А теперь нужно пробежать по области и найти точки 
  // на текстурной карте, куда попадает маска:
  for (y = sy; y <fy;  y++) {
    for (x = sx;  x<fx; x++) {

  // 8. вычисление координаты на маске точки карты (x,y):
      oldx = o.x+(((x*ca)>>BR_S) + ((y*sa)>>BR_S));
      oldy = o.y+(((y*ca)>>BR_S) - ((x*sa)>>BR_S));
  // 9. проверяем, попадает ли координата на маску. Если нет, то значит маска на 
  // эту точку (x,y) карты не попадает.
      if ((oldx>= 0) && (oldy >= 0) && (oldx < br->masksize.x) && ( oldy < br->masksize.y)) {
  //10. с этого момента мы знаем, что это та точка, куда маска попадает.
  // в примере только не реализована проверка: 
  // не пустое ли это место на самой маске в координате (oldx,oldy). 
  // Т.е. имеет ли смысл проводить операции по 
  //отображению ландшафта и объектов, находящихся в этом месте ландшафта 
  //или же это находится за пределами видимости камеры.
    br->map[BR_MAP(x+(S32)br->pos.x,y+(S32)br->pos.y)]= br->mask[BR_MASK(oldx,oldy)];
      }
    } 
  }

  return(TRUE);
}

Начиная с пункта 10, в функции BR_Rotate мы имеем представление о том, что нужно рендерить. А после выполнения всех циклов у нас будет полное представление о том, что должно рендериться на сцене. Именно в пункте 10 мы должны собирать все идентификаторы текстур и их координаты в таблицу. Там же мы собираем информацию о тех объектах, которые стояли на этом месте ландшафта.

После того, как выполнился цикл, проведем сортировку по текстурным идентификаторам, что бы оптимизировать переключение текстур. Вы прекрасно знаете как дороги вызовы DX API функций.

Работа вся проводилась с картой текстурных идентификаторов (TMAP), но рендерить нам нужно ландшафт карту высот HMAP. Каждую площадку 8x8 добавляем в вершинный буфер.

Итого, для размера маски 32x32, где максимум точек на TMAP лежит на границе 1100 (зависит от точности вычисления вращения маски) нам нужно заполнить буфер на 8*8*2*1100= 140800 полигонов. Только это на самом деле верно, если маска залита вся, а для FOV 90 около 50% площади не будет значимой. Таким образом, только около 70.000 полигонов потребуется выводить.

С ландшафтом теперь всё решено. Мы не сильно нагрузили процессор, но зато немножко нагрузили нашу видеокарту. Хотя, по сегодняшнему дню это уже и не нагрузка (Хотя бы для GF3 или Radeon 9600). Идея и задумывалась для тех карт, которые носят гордое имя Radeon и GeForce.

Теперь об объектах на сцене. Как правильно отображать объекты?
Во-первых, нужно отметить, что объекты, которые занимают площадь большую, чем одну точку на TMAP могут быть не отрендерены. Это происходит на границах маски.

Это есть минус метода, но при желании это можно обойти. Если же говорить о том, что происходит на краях маски, то неслучайно на рисунке 1 выбрана такая координата (15,30). Нужно взять центр вращения на 2 точки вверх от границы маски. Объяснять долго суть происходящего не имеет смысла. На простом языке: слева и справа экрана ландшафт будет отсекаться маской, а объекты могут исчезать в этих областях экрана.

Еще на рисунке 1 указаны зоны LOD0, LOD1 и LOD2. Это зоны, где должны быть разные уровни детализации (Level Of Details (LOD)).
Можно использовать это по-разному:
1. Сделать модели с 3мя уровнями детализации.
2. На LOD1 и LOD2 не рендерить мелкие объекты. В частности, billboard траву.
3. Сделать для карты высот несколько уровней детализации, как в mip-mapping-е. 4096x4096 для LOD0, 2048x2048 для LOD1, 1024x1024 для LOD2. Не стоит только забывать, что в этом случае придется объединять эти самые уровни, а также, в случае деформации ландшафта, нужно будет генерировать уровни снова и снова, что не приемлемо.

Важно отметить, что билборд упомянут, был не зря. Именно он должен на сцене отображаться в правильном порядке. От дальнего плана (far plane) к ближнему плану (near plane). Этот случай является исключением, поэтому сортировка по текстурам здесь не подходит. Если для решения использовать маску, изображенную на рисунке 1, то сортировку можно провести по значениям height маски.

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

1. Тени можно наносить по карте высот (по vertex-ам), но если вы хотите использовать карту тени, размер которой больше карты высот, то решение просто само напрашивается. См. способ 2.

2. Всё, что нам нужно – это скопировать квадрат из большой карты теней в локальную, размер которой больше, чем (fx – sx, fx - sy) (См. Функцию BR_Rotate). Желательно, если маска 32x32, то текстура тени должна быть хотя бы 128x128, иначе это всё равно, что наносить тени по вершинам карты высот.

Необходимо помнить, что, при повороте маски площадь становится больше чем 32x32, поэтому 128x128 – это один из первых размеров, при которым способ 2 перестает быть похожим на способ 1.

3. Не худшей идей будет сделать для каждой модели свою текстуру тени. В этом случае мы всегда её можем нанести на локальную текстуру тени (та, что строиться в области (fx – sx, fx - sy)), описанная в способе 2.

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

Также важно понимать, что работать это будет действительно быстро, пока используем размеры текстур 256x256, 512x512. С текстурами большего размера может не очень хорошо получится. Традиционно, ATI Radeon Series быстрей работает с большими текстурами, нежели nVidia GeForce. Поэтому, есть шанс, что использование больших текстур может только ухудшить положение и проблема минимизации переключений текстур оказаться на втором плане.

Можно сделать несколько текстур (оптимальный размер: 512x512), где объединено по 4 (2x2) или 16 (4x4) изображений.

Если HMAP (height map) имеет приличные размеры (4096x4096) не лишним было бы показать на нем неровность текстур. Возьмем на вооружение карту высот для текстур, как продемонстрировано на рисунке 3.

Рисунок 3. Height map текстуры, изображенной на рисунке 2.

На рисунке 3 показана карта высот текстуры. Как вы помните, в одной точке на карте TMAP находиться 8x8 вершин ландшафта. Так как мы решили объединять текстуры в доску 4x4, то размер карты высот на рисунке 3 имеет размер 32x32.

Достаточно при загрузке карты складывать значения высоты HMAP со значением высоты на карте высот текстуры. Так будет немного лучше выглядеть поверхность, особенно, если до этого над HMAP выполнялись операции, описанные в начале статьи (Blur и Scaling).

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

Представьте, что у нас есть модель дерева. Когда мы подходим к нему, то столкнуться можем только со стволом. И на ландшафте карта столкновений для дерева будет выглядеть как круг. Так вот поэтому мы на каждую 3D модель можем нанести карту collision detection. Скажем такую, которая будет накладываться на карту высот 8 к 1-ому. Пусть, для модели дерева, её размер будет 64x64. Т.к. в одной точке TMAP размер площадки на карте высот равен площади 8x8, то карта столкновений как раз займет площадь одной точки на TMAP.

И теперь, мы генерируем локальную карту столкновений. Так мы её назовем и, кстати, вращать её не требуется. Генерируем её на основе карт столкновений лежащих по близости объектов (видимых). Камера в локальной карте столкновений должна находится по центру. Размер этой карты будет зависеть прямо пропорционально от максимальной скорости перемещения по карте. И нужно не забыть учитывать, что если интервал времени между кадрами большой, то мы можем не правильно провести прямую, по которой движется камера, и, следовательно, неверно определить столкновение.

Как видите, даже вычисления по Collision detection можно проводить без использования FPU.

Минусы:
1. Полет над ландшафтом невозможен
2. Около 5-20% маски может рендериться вхолостую
3. Изменение FOV в процессе игры должно сопровождаться заменой маски
4. Маски столкновений и теней должны быть сгенерированы для каждой модели, но это только в том случае если следовать тому, что написано выше.
5. Объект отображается, даже если не виден из-за ландшафта, т.к. всё вычисляется по маске.
6. Большие объекты могут не попадать на маску и для использования их нужно немножко продуманней действовать.
7. Collision Detection, описанная выше может устроить далеко не всех.
8. для shadow и collision detection нужно генерировать (рисовать) карты.

Плюсы:
1. Simplicity! Т.е. простота.
2. Не очень много вычислений. Почти не используются вычисления с FPU в решении задачи обнаружения видимой области на карте, collision detection и shadows. Это очень спорный плюс, т.к. очень много зависит от того, каким компилятором пользовались, под какой процессор оптимизировали, на каком процессоре запускали, на какой OS и еще множество других условий.
3. Ландшафт зациклен, т.е. бесконечен. Это то, что очень редко встречается в сегодняшних играх.
4. Отображение ландшафта (только ландшафта) может сопровождаться всего одним, двумя переключениями текстур и одним, двумя вызовами рисования примитивов.
5. Для сортировки билборда почти ничего не нужно делать. Маска сама по себе “сортирует”
6. для Level of Details не нужно выполнять почти никаких вычислений.
7. Простая реализация Collision Detection.
8. Быстрый старт для тех, кто не разбирался с Quadtree, Octree.
9. Бонусный плюс: использовать то, что написано в статье можно в shareware играх