Я очень долго пытался понять, как сделать детализацию ландшафта еще более гибкой. Посмотрите на эти 2 рисунка. На левом детализация меняется этапами - вокруг камеры воображаемое кольцо с высокой детализацией рельефа (область с бОльшим количеством полигонов). Следующий круг - детализация послабее и полигонов меньше. Чем дальше от камеры, тем меньше детализация. Это конечно хорошо. Но не во всем - посмотрите, сколько лишних полигонов уходит на отображение ровного "пола" долины на левом рисунке и как мало уходит полигонов на настоящие неровности, склоны гор? Ведь пол у нас ровный, на него нужно совсем мало полигонов, а вот на склоны много. Видите, как неразумно распределяется детализация и страдает реалистичность?

А теперь посмотрите на правый рисунок. Я долго пытался достичь именно такого результата, но у меня ничего не получалось. Как сделать такую детализацию?

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

distance = sysNorm(location_x+X, location_y-Height, location_z+Y);

Дальше, рассмотрим само выражение нахождения критерия деления, для того, чтобы иметь детализацию как на левом рисунке, это выражение должно выглядеть так

error=((float)Roughness(X,Y)*Side)/distance;

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

error=((float)(Roughness(X,Y)*Roughness(X,Y)*Roughness(X,Y))*Side)/distance;

Видите, в чем разница ?!!! В нашем случае мы в три раза увеличиваем значение фактора неровности Roughness. Заметте, не домножаем его на какую-то константу, а именно возводим его во вторую или третью степень! Смотрите наше выражение, разобьем его на 2 воображаемые половины.

error=((float)Roughness(X,Y)*Side)/distance;

Если увеличивать зеленую часть, то мы получим более качественное отображение ландшафта, как на правом скриншоте, но при этом детализация LOD будет меняться медленнее.
Если увеличивать красную часть, к примеру (Side*2), то мы получим картину, подобную левому скриншоту, где будет менее качественная детализация и неразумное распределение полигонов, но зато более динамически изменяющийся LOD. Но при сильноизменяющемся LOD будет эффект бряка вершин и у Вас появиться большая проблема - нужда в геоморфинге.

Какая детализация Вам больше нужна - решать Вам. Тут возможны всякие компромиссы.
И в завершении. Экспериментируйте, господа!

Дополнение от 24 декабря 2002

При рендеринге ландшафтов с использованием LOD есть один неудачный эффект – внезапно резкое появление или исчезновение целых областей вершин, когда перестраивается сетка (когда работает LOD). Это искажение может быть уменьшено до почти незначительных количеств методом "Vertex Morphing", также называемым GeoMorphing - плавное «поднятие» или «опускание» высоты вершины от положения ее высоты которая была до деления узла, до ее новой высоты, когда узел уже разбит на новые.

Теоретически геоморфинг прост, а практически очень сложен в реализации.

Большим плюсом алгоритма считается, когда ROAM умеет плавно менять детализацию без привлечения сложной технологии геоморфинга. Поверьте, такое возможно.
Это удалось сделать программисту David Dufke в его проекте Engine1

Метод Dufke заключается в применении очень "хитрой" функции нахождения дистанции между позицией камеры и узлом. Я позволил себе нагло передрать этот метод в свой движок для того, чтобы показать Вам как это делается. Обращу Ваше внимание на то, что у Dufke совсем другая ROAM технология и на его ROAM технологии этот метод работает еще более эффективно, чем на Rottger ROAM. Но и на Rottger ROAM все выглядит достаточно неплохо - применение метода Dufke позволяет полностью отказаться от сложного геоморфинга. При этом детализация меняется настолько плавно, что это трудно заметить невооруженным глазом.

И так, наша функция построения квадродерева.

void ROAM::QTreeSetup(int level, int X, int Y, int Side)
{
    float error;
     Height=(-hf(X,Y));
    // изменилась функция вычисления дистанции
    //distance=fabs(X-location_x)+(fabs(Height-location_y))+fabs(Y-location_z);
    distance = sysNorm(location_x-X, location_y-Height, location_z-Y);
     if(distance < 0.001) distance = 0.001f;

    //detailLevel = 0.041f;
     error=((float)Roughness(X,Y)*Side)/distance; if(error>detailLevel)
        {
         if (!FrustumWorking(X, Y, Side)) {QT(X,Y) = 255; return;}
          QT(X,Y)=NodePoint;

         if (Side>1)
          {
              int HSide = Side / 2;
               QTreeSetup(level+1, X-HSide, Y-HSide, HSide);
               QTreeSetup(level+1, X+HSide, Y-HSide, HSide);
               QTreeSetup(level+1, X-HSide, Y+HSide, HSide);
               QTreeSetup(level+1, X+HSide, Y+HSide, HSide);
          }
     else QT(X,Y)=EdgePoint;
     }

 else QT(X,Y)=EdgePoint;
}

Как вы видите, мы используем новую функцию sysNorm. Но для того, чтобы она успешно работала, нам нужно при инициализации один раз вызвать функцию sysBuildNormTable().
Ниже привожу текст этих функций

/*** sysNorm ***
 Find approx. length of 3D vector.
 WARNING: sysBuildNormTable MUST be called once
 before this function, or it will return b0rk. */
int Shots;
int sys_memUsed = 0;
static unsigned char sys_normTable[0xFF * 2];

float sysNorm(float x, float y, float z)
{
 float result;
 __asm
 {
  /* Sum squares */
  FLD  x
  FMUL ST(0), ST(0)
  FLD  y
  FMUL ST(0), ST(0)
  FADDP ST(1), ST(0)
  FLD  z
  FMUL ST(0), ST(0)
  FADDP ST(1), ST(0)
  FSTP result

  /* Find approx. root thru look-up table */
  MOV  eax, result
  MOV  ebx, eax
  AND  eax, 2139095040
  SHR  eax, 23
  SUB  eax, 127
  MOV  ecx, eax
  AND  ecx, 1
  SHR  eax, 1
  ADD  eax, 127
  SHL  eax, 23
  AND  ebx, 8388607 /* Sorry about the magic numbers. :-> */
  SHR  ebx, 15
  SHL  ebx, 1
  OR  ebx, ecx
  ADD  ebx, OFFSET sys_normTable
  MOVZX edx, BYTE PTR [ebx]
  SHL  edx, 15
  OR  edx, eax
  MOV  result, edx

 }
 return result;
}

/*** sysBuildNormTable *** Build look-up table for sysNorm(). */
void sysBuildNormTable()
{
 int m;
 unsigned int is, ir;
 float s, r;
 for(m = 0;m < 0xFF;m++)
 {
  is = ((127 << 23) | (m << 15));
  s = *((float *)(&is));
  r = sqrtf(s);
  ir = *((unsigned int *)(&r));
  sys_normTable[2*m] = (ir & (0xFF << 15)) >> 15;

  is = (((127+1) << 23) | (m << 15));
  s = *((float *)(&is));
  r = sqrtf(s);
  ir = *((unsigned int *)(&r));
  sys_normTable[2*m+1] = (ir & (0xFF << 15)) >> 15;
 }
}

Еще одно добавление. Ранее рендеринг происходил при одном вызове glVertex. Это затрудняло отлов всех трех вершин для той же проверки столкновений, например. Вот новый вариант функции рендеринга, где можно выловить все 3 вершины полигона (glVertex вызывается 3 раза - по разу для каждой вершины треугольника).

void ROAM::RenderMesh(void)
{
 if (!WorkWire) glBindTexture(GL_TEXTURE_2D,  ColorTexture);

 unsigned i;
 Vertex3D *pV = VertexBuffer;

 if (WorkWire) {
  glColor4f(0,0,0,0.5f); glDisable(GL_TEXTURE_2D); glPolygonMode(GL_FRONT,GL_LINE);
 }

 glBegin(GL_TRIANGLE_FAN);
 for (i=0; i<TotalVertex; i++)
 {
// первая вершина
label1:
  if (pV[i].Xp <= FANFinish) {
   i++;
   glEnd(); glBegin(GL_TRIANGLE_FAN);
   goto label1;
  }
  glTexCoord2f((pV[i].Yp/ScaleXZ)*TWrap, (pV[i].Xp/ScaleXZ)*TWrap);
  glVertex3f(pV[i].Xp*ScaleXZ, pV[i].Yp*ScaleXZ, pV[i].Zp*ScaleVert);

//вторая вершина
  i++;
label2:
  if (pV[i].Xp <= FANFinish) {
   i++;
   glEnd(); glBegin(GL_TRIANGLE_FAN);
   goto label2;
  }
  glTexCoord2f((pV[i].Yp/ScaleXZ)*TWrap, (pV[i].Xp/ScaleXZ)*TWrap);
  glVertex3f(pV[i].Xp*ScaleXZ, pV[i].Yp*ScaleXZ, pV[i].Zp*ScaleVert);

// третья вершина
  i++;
label3:
  if (pV[i].Xp <= FANFinish) {
   i++;
   glEnd(); glBegin(GL_TRIANGLE_FAN);
   goto label3;
  }
  glTexCoord2f((pV[i].Yp/ScaleXZ)*TWrap, (pV[i].Xp/ScaleXZ)*TWrap);
  glVertex3f(pV[i].Xp*ScaleXZ, pV[i].Yp*ScaleXZ, pV[i].Zp*ScaleVert);
 }

 glEnd();

 glEnable(GL_TEXTURE_2D);
 glPolygonMode(GL_FRONT,GL_FILL);

}
 

Дополнение от 10 декабря 2002

Предлагается несколько вариантов функции построения квадродерева.

void ROAM::QTreeSetup(int X, int Y, int Side)
{
     Height=(-hf(X,Y)); Height*=0.5f;
     distance=fabs(X-location_x)+(fabs(Height-location_y))+fabs(Y-location_z);

  //if(distance>400)distance=distance*3;if(distance<300)distance=distance/3;
        // для этого случая lodLevel = 42
    if (distance<(Side * detailLevel * Roughness(X,Y) ))
     {
      if (!FrustumWorking(X, Y, Side)) {QT(X,Y) = 255; return;}
          QT(X,Y)=NodePoint;

      if (Side>1) {
           int HSide = Side / 2;
               QTreeSetup(X-HSide, Y-HSide, HSide);
               QTreeSetup(X+HSide, Y-HSide, HSide);
               QTreeSetup(X-HSide, Y+HSide, HSide);
               QTreeSetup(X+HSide, Y+HSide, HSide);
          }
      else QT(X,Y)=EdgePoint;
     }

    else QT(X,Y)=EdgePoint;
}

Следующий вариант функции разбиения квадратов, он интересен тем, что в нем вообще не используется Roughness коофицент

void ROAM::QTreeSetup(int X, int Y, int Side)
{
 Height=(-hf(X,Y)); Height*=0.5f;
 distance=fabs(X-location_x)+(fabs(Height-location_y))+fabs(Y-location_z);

 // для этого случая lodLevel = 6

 if((Side>1) && (distance)<(Side*Side*detailLevel*detailLevel))
 {
  if (!FrustumWorking(X, Y, Side)) {QT(X,Y) = 255; return;}
  QT(X,Y)=NodePoint;

  if (Side>1) {
   int HSide = Side / 2;
   QTreeSetup(X-HSide, Y-HSide, HSide);
   QTreeSetup(X+HSide, Y-HSide, HSide);
   QTreeSetup(X-HSide, Y+HSide, HSide);
   QTreeSetup(X+HSide, Y+HSide, HSide);
  }
  else QT(X,Y)=EdgePoint;
 }

 else QT(X,Y)=EdgePoint;
}

Но при этом нужно не забыть под каждый вариант функции "подогнать" свое значение переменной detailLevel.
И последний, самый интерестный вариант.

void ROAM::QTreeSetup(int X, int Y, int Side)
{
 float error;
 Height=(-hf(X,Y));
 distance=fabs(X-location_x)+(fabs(Height-location_y))+fabs(Y-location_z);

 error=((float)Roughness(X,Y)*Side)/distance;
 if(error>lodLevel)//lodLevel=0.014f
 {
  if (!FrustumWorking(X, Y, Side)) {QT(X,Y) = 255; return;}
  QT(X,Y)=NodePoint;

  if (Side>1) {
   int HSide = Side / 2;
   QTreeSetup(X-HSide, Y-HSide, HSide);
   QTreeSetup(X+HSide, Y-HSide, HSide);
   QTreeSetup(X-HSide, Y+HSide, HSide);
   QTreeSetup(X+HSide, Y+HSide, HSide);
  }
  else QT(X,Y)=EdgePoint;
 }

 else QT(X,Y)=EdgePoint;
}

Еще одна хитрость. Если мы в оранжевом выражении не будем Roughness фактор умножать на Side, у нас получится следующая картина. Ландшафт будет отображаться еще более точно - на ровные области будет уходить совсем мало полигонов, в то же время на неровности будет затрачено еще больше полигонов. И детализация будет менятся более плавно и реалистично. Но при этом будут образовываться разрывы в mesh. Чтобы избежать разрывов мы и домножаем Roughness фактор на длину ребра каждого квадрата, чтобы "сгладить" разрывы. За это приходится расплачиваться качеством детализации. Можно пойти альтернативным путем - ввести "древовидные" структуры и при делении смотреть - если два соседних квадрата имеют одинаковый размер, то их можно делить (тогда не будет разрывов). Это подробно описано в статье (рисунок 8)
http://gamemaker.webservis.ru/articles/roam2/note.html
Называется этот метод "Forced Split". Таким образом, у нас 2 пути - или просто домножать коофицент неровности на длину ребра и принебречь точностью или пойти более сложным путем - смотреть, если 2 соседних квадрата имеют одинаковый размер - тогда делим. Иначе получаются разрывы - когда рядом находятся 2 квадрата разного размера.

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

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

Теперь, благодаря этой функции можно гораздо быстрее понять процесс построения квадродерева. Обратите внимание на закоментированную строку

//if(distance<300)distance=distance/3;

Она будет интерестна для любителей экспериментов и трактуется так - все квадраты, расположенные в расстоянии до 300 от камеры прорисовываются с увеличенной детализацией.

То же самое, если раскоментировать строку

//if(distance>400)distance=distance*3;

то квадраты, которые расположены от камеры на расстоянии 400 и больше прорисовываются с уменьшенной детализацией.

НАЗАД