Использование порталов в indoor-сценах.

Автор: Джо

Общая идея алгоритма

Ты когда-нибудь стоял и смотрел на это, Морфеус?
Поражённый её красотой. Её гениальностью. Миллиарды людей
живут своей жизнью... без подозрений.

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

С ростом сложности геометрии и размера сцены перед разработчиками игры становится горой сложный вопрос - рендеринг только видимой геометрии. Задача эта нетривиальная и в разных играх решается по-разному. На разработку эффективных алгоритмов тратится много усилий и времени. Насколько мне известно, полностью эта задача так и не решена. Отдельные методики могут превосходно работать для выбранной ситуации, но нет ни одной, удовлетворительно работающей для всех ситуаций. Здесь я рассмотрю наиболее простое решение задачи - то, которое применяется для закрытых помещений.

Сюжет большинства трёхмерных боевиков вроде Quake или DOOM развивается преимущественно в закрытых (indoor) помещениях, т.е. комнатах, ограниченных со всех сторон стенами. Находясь в таком помещении, игрок если и может что-то видеть в соседних комнатах, так только через порталы - окна и двери, которыми соединяются помещения. Геометрия вне поля зрения портала видна быть не может по причине скрытости стенами. Вот рисунок, который поясняет ситуацию:

Рис. 1. Общий принцип

Как видно, объект a в комнате 2 легко наблюдается через портал (например, пусть это будет дверь), а вот объекты б и в из точки, где находится в данный момент наблюдатель, никак видны быть не могут. Полностью же механизм рендеринга примерно такой: заранее, на этапе препроцессирования мы составляем список всех видимых для каждой комнаты примитивов (например, с помощью октарного дерева, см. ниже). Рендеринг начинается с вывода геометрии той комнаты, в которой находится игрок. При этом может применяться отбрасывание невидимой геометрии (за спиной игрока) при помощи viewing frustum или любого другого метода. После этого определяются видимые порталы текущей комнаты. Если все порталы скрыты (например, находятся позади игрока), то рендеринг прекращается. Если же нет, то определяются смежные по порталам комнаты. Геометрия смежных комнат выводится не вся, а только та, что видна через портал. Затем определяются порталы смежных комнат, и если таковые не видны, рендеринг прекращается. Если же нет, алгоритм рекурсивно повторяется и продолжает работу до тех пор, пока не будет произведён обход всех видимых порталов и не отрисована все объекты, наблюдаемые через них. Время работы алгоритма прямо зависит от характера расположения порталов. Вот пример:

Рис. 2. Пример расположения порталов

Как видно, порталы а и б не участвуют в обработке, т. к. не попадают во viewing frustum (тонкая красная граница). Портал в попадает, поэтому из комнаты 2 рисуются те объекты, которые видны через него. Портал г не участвует в обработке, т. к. невидим через портал в. Зато портал д виден (частично), поэтому из комнаты 3 рисуются те объекты, которые видны через портал д. Портал е также не участвует в обработке. Он вообще особенный, т. к. при любых позициях наблюдателя в комнате 1 этот портал увидеть невозможно, а значит, можно исключить его из списка потенциально видимых ещё на этапе моделирования сцены.

Некоторые практические моменты

Знаешь ли ты, что первая Матрица была разработана как
идеальный людской мир, где не было страданий, где каждый был
счастлив. Это была катастрофа. Никто не воспринял программу.
Был потерян целый урожай.

Как узнать, виден ли примитив через портал или нет? Самый быстрый и одновременно простой метод - это построить для данного портала пирамиду отсечения (этакий portal frustum). Вершиной пирамиды будет служить позиция игрока (глаза), а её "опорой"  - сам портал:

Рис. 3. Portal frustum

Для правильного построения портала необходимо, чтобы он являлся выпуклым (convex) многоугольником, иначе ничего не получится. Так как стенами пирамиды являются бесконечные плоскости, это исключает НЕвыпуклость портала. Впрочем, ограничение это не очень серьёзное.

Реально (если такое понятие вообще применимо в программировании и моделировании) портал представляет собой обыкновенный полигон. Таким полигоном моделеры как бы "затягивают" проёмы в моделируемой сцене - окна, двери и вообще всякие проходы. Такие полигоны могут помечаться в редакторе как порталы или сохраняться как отдельная модель и потом отдаваться на растерзание графическому движку. Желательно, чтобы портал содержал как можно меньше рёбер и одновременно как можно точнее описывал реальный проём в сцене. В то же время он, как было сказано, должен быть выпуклым многоугольником.

Portal frustum строится в каждом кадре. При условии, что игрок с прошлого кадра не сдвинулся с места, а только повернул голову, пирамиду для данного портала можно заново не строить, а взять из предыдущего кадра. Построение такой пирамиды происходит очень быстро. Как я уже говорил, её стенами являются бесконечные плоскости. Уравнение плоскости имеет вид:

Ax + By + Cz + D = 0,

Где N(A, B, C) - это нормаль к плоскости, v(x, y, z) - это координаты произвольной точки, D - расстояние от плоскости до начала системы координат. Уравнение верно, если точка v принадлежит плоскости.

Следовательно, для построения плоскости нам нужно вычислить её нормаль и коэффициент D. Нормаль к плоскости можно вычислить, взяв любые три точки, принадлежащие плоскости. Две из них у нас есть - это вершины очередного ребра портала. Третьей точкой будет служить позиция глаза (eye). Получив нормаль, можно легко вычислить и коэффициент D. Вот функция, которая это делает (Object Pascal):

procedure GetPolyFrustum( const poly: array of vec3_t; num_verts: uint;
                          var frustum: array of plane_t; eye: vec3_t );
var
  v1, v2: vec3_t;
  i: integer;
begin
  for i := 0 to num_verts - 1 do
  begin
    v1 := poly[(i + 1) mod num_verts];
    v2 := poly[i];

    frustum[i].normal := Normal( eye, v1, v2 );
    frustum[i].dist   := -Dot3( frustum[i].normal, eye );
  end;
end;

Как видите, объём вычислений минимален. Количество плоскостей в пирамиде равно количеству рёбер портала. Построив portal frustum, можно начать делать проверки - попадает ли очередной примитив в эту пирамиду, и если попадает - мы отрисовываем его. Но это самый простой метод, так сказать "в лоб" и для сложного рендеринга не годится. Необходимо сделать несколько оптимизаций.

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

Для отсечения произвольного многоугольника по границе заданного выпуклого многоугольника можно воспользоваться алгоритмом Сазерленда-Ходжмана (Sutherland-Hodgman algorithm). Алгоритм сводит исходную задачу к серии более простых задач об отсечении многоугольника вдоль плоскости, проходящей через одно из рёбер отсекающего многоугольника. Что важно, такое отсечение всегда даст выпуклый многоугольник. Вот функция, которая выполняет отсечение произвольного многоугольника плоскостью по упомянутому алгоритму (отдельное спасибо IronPeter'у за предоставленный оптимизированный код):

function ClipPlane( var dst: array of vec3_t; const src: array of vec3_t;
                    num_verts: uint; const plane: plane_t ): uint;
var
  v1, v2: vec3_t; // вершины очередного ребра
  t1, t2: single;
  k1, k2: single;

  num: uint;

  i: integer;
begin
  num := 0; // кол-во вершин в dst
  for i := 0 to num_verts - 1 do
  begin
    v1 := src[i];
    v2 := src[(i + 1) mod num_verts];

    t1 := Dot3( v1, plane.normal ) + plane.dist;
    t2 := Dot3( v2, plane.normal ) + plane.dist;

    if t1 >= 0 then
    begin
      dst[num] := v1;
      inc( num );
    end;

    if t1 * t2 < 0 then
    begin
      k1 :=  t2 / (t2 - t1);
      k2 := -t1 / (t2 - t1);

      dst[num].x := v1.x * k1 + v2.x * k2;
      dst[num].y := v1.y * k1 + v2.y * k2;
      dst[num].z := v1.z * k1 + v2.z * k2;

      inc( num );
    end;
  end;

  result := num;
end;

Тоже очень быстрая функция. А вот функция, которая производит полное отсечение многоугольника, вызывая ClipPlane() несколько раз:

function ClipPolygon( var dst: array of vec3_t; const src: array of vec3_t;
                    num_verts: uint; planes: array of plane_t; num_planes: uint ):uint;
var
  swap: array of vec3_t;
  num:  uint;
  i:    integer;
begin
  setlength( swap, num_verts * 2 );

  num := ClipPlane( dst, src, num_verts, planes[0] );
  for i := 1 to num_planes - 1 do
  begin
    if i mod 2 <> 0 then // проверка на чётность
       num := ClipPlane( swap, dst, num, planes[i] )
    else
       num := ClipPlane( dst, swap, num, planes[i] );
  end;

  if num_planes mod 2 = 0 then // swap->dest
     CopyMemory( @dst, swap, num * sizeof( vec3_t ) );
  swap := nil;

  result := num; // кол-во вершин в dst
end;

Здесь я использовал копирование данных, если результат "застрял" во временном массиве, хотя правильнее было бы менять указатель на массив. Но так как в Object Pascal с этим связаны кое-какие трудности и учитывая малый размер массива, я прибегнул к простому копированию.

Вторая оптимизация

Некоторые полагали, что мы испытывали недостаток в языке программирования,
способном описать ваш идеальный мир.
Но я верю, что как вид, люди определяют свою реальность через страдание и нищету.
Ваш примитивный мозг пытался очнуться от идеального мира.
Поэтому мы перестроили Матрицу в это: пик вашей цивилизации.

Вторая оптимизация связана с тем, чтобы эффективно отбрасывать примитивы, не попадающие в portal frustum. Делать это по одному полигону крайне неэффективно. Естественное решение - группировка примитивов, например, с помощью октарного дерева (см. Разбиение объектного пространства сцены путём построения octree-дерева.). Произведя такую группировку, можно очень быстро отсекать сложнейшую геометрию ценой всего нескольких проверок. Как и любой другой алгоритм приближённого описания исходных данных, октарное дерево страдает неточностью при определении видимости тех или иных объектов. Как результат - определение некоторой части скрытой геометрии как видимой. Впрочем, преимуществ от данного механизма больше, чем недостатков. Просто нужно смириться с мыслью, что данный алгоритм рендерит всю видимую геометрию + какое-то непостоянное кол-во скрытой. Вот, например, как можно представить себе комбинацию portal-octree:

Рис. 4. Portal-Octree

Как видно, часть кубиков входит в область portal frustum, а часть - нет. Пользуясь этим принципом, можно легко и быстро отсекать большую часть невидимой геометрии, причём скорость отсечения мало зависит от размера комнат, т.к. октарное дерево имеет иерархическую структуру, т.е. тенденцию к последовательному ветвлению, от корня к листьям.

Можно применить разные варианты дерева. Например, построить одно гигантское дерево для всей сцены и распределить его узлы и листья по отдельным комнатам, при этом составив список узлов, попадающих сразу в оба помещения. А можно построить отдельное дерево для каждого помещения - тогда комнату можно представить как структуру (или класс, это уж как кому нравится), одним из полей которой будет указатель на корень уникального octree-дерева. Первый вариант проще, второй - интереснее и сложнее (и, возможно, эффективнее).

Воплощение идей

Я говорю "ваша цивилизация" потому что вскоре, как мы начали думать за вас,
это в действительности стала наша цивилизация. Эволюция, мой друг, эволюция.
Как динозавры. Посмотри в окно.
Ваше время уже давно прошло. Будущее твоего
мира, Морфеус. Будущее наше время.
Агент Смит. Матрица.

Наконец, реальная программа. Я написал её в IDE Delphi 5. Суть такова - загружается простой металлический «мешок», в котором имеется одно окошко, оно затянуто порталами с двух сторон Через это окошко игрок может видеть высокополигональную сферу (а может и не видеть). Задача алгоритма - определение этого маленького факта, а практически определения, попадает ли в portal frustum куб, описывающий сферу. Сфера взята достаточно точной, чтобы было заметно падение fps при попадании её в поле зрения (это не отностися к GeForce 4 :). Вот основной код проверки:

eye := Camera_GetPos();

  // отсекаем ближний портал границами viewing frustum
  num_verts := ClipPolygon( g_clipped_near, g_near_portal, 4, g_frustum, 4 );
  if num_verts > 0 then // ближний портал в поле зрения камеры
  begin
     // получаем пирамиду видимости ближнего портала
     GetPolyFrustum( g_clipped_near, num_verts, g_portal_frustum, eye );

     // отсекаем дальний портал плосокстями portal frustum
     num_verts:=ClipPolygon( g_clipped_far, g_far_portal, 4, g_portal_frustum, num_verts);
     if num_verts > 0 then // дальний портал виден весь или частично
     begin
       // получаем пирамиду видимости дальнего портала
       GetPolyFrustum( g_clipped_far, num_verts, g_portal_frustum, eye );

       if g_control[2] then DrawEdges( g_clipped_far, num_verts );

       if InFrustum( box, 8, g_portal_frustum, num_verts ) then
       begin
         // рисуем высокополигональную сферу
         glColor3ub( 128, 128, 128 );
         glTranslatef( 20.0, 50.0, 400.0 );
         gluSphere( g_gluobj, SPHERE_RADIUS, 130, 130 );

         str := 'bbox in camera';
       end
       else str := 'near / far portal in camera, bbox invisible';
     end
     else str := 'near portal in camera / far portal invisible';
  end
  else str := 'near portal invisible';

Модель была сделана в 3D Studio MAX 4.0, а затем конвертирована из .max в простой формат вершина-нормаль-текстурные координаты. Порталы были "натянуты" с обеих сторон окошка в редакторе, затем также записаны в отдельный файл, но потом я перенёс данные в код программы, чтобы дополнительно не усложнять её процедурами загрузки и т. д. Для смакования работы алгоритма Сазерленда-Ходжмана предусмотрен wireframe-режим, в котором можно увидеть границы результирующего портала после всех проведенных отсечений (выделяются жёлтой рамкой):

Нужно добавить, что попадание описывающего куба в portal frustum неточно - чётко видно, что он "недотягивая" до границ портала уже считается видимым. Наверное, это связано с накоплением погрешности в типе single (float) на всех стадиях, начиная с отсечения портала и заканчивая проверкой попадания куба в пирамиду. Возможно, придётся применить тип double. Напоследок хочется заметить, что нужно быть осторожным при задании ориентации портала (front or back) на наблюдателя и при построении нормалей к плоскостям portal frustum, т. к. их направление влияет на знак сравнения при проверке попадания куба в пирамиду.

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

Исходный и исполняемый код: 20030521.rar.

#indoor, #порталы

20 мая 2003 (Обновление: 6 июля 2009)