Вычисление нормалей в треугольной сетке

Question

Я нарисовал треугольную сетку с 10000 вершинами (100x100), и это будет трава. Я использовал gldrawelements () для этого. Я смотрел весь день и до сих пор не могу понять, как рассчитать нормали для этого. Есть ли у каждой вершины свои нормали или у каждого треугольника есть свои нормали? Может ли кто-нибудь указать мне правильное направление, как отредактировать мой код для включения нормалей?

struct vertices {
    GLfloat x;
    GLfloat y;
    GLfloat z;
}vertices[10000];

GLuint indices[60000];

/*
99..9999
98..9998
........
01..9901
00..9900
*/

void CreateEnvironment() {
    int count=0;
    for (float x=0;x<10.0;x+=.1) {
        for (float z=0;z<10.0;z+=.1) {
            vertices[count].x=x;
            vertices[count].y=0;
            vertices[count].z=z;
            count++;
        }
    }
    count=0;
    for (GLuint a=0;a<99;a++){
        for (GLuint b=0;b<99;b++){
            GLuint v1=(a*100)+b;indices[count]=v1;count++;
            GLuint v2=(a*100)+b+1;indices[count]=v2;count++;
            GLuint v3=(a*100)+b+100;indices[count]=v3;count++;
        }
    }
    count=30000;
    for (GLuint a=0;a<99;a++){
        for (GLuint b=0;b<99;b++){
            indices[count]=(a*100)+b+100;count++;//9998
            indices[count]=(a*100)+b+1;count++;//9899
            indices[count]=(a*100)+b+101;count++;//9999
        }
    }
}

void ShowEnvironment(){
    //ground
    glPushMatrix();
    GLfloat GroundAmbient[]={0.0,0.5,0.0,1.0};
    glMaterialfv(GL_FRONT,GL_AMBIENT,GroundAmbient);
    glEnableClientState(GL_VERTEX_ARRAY);
    glIndexPointer( GL_UNSIGNED_BYTE, 0, indices );
    glVertexPointer(3,GL_FLOAT,0,vertices);
    glDrawElements(GL_TRIANGLES,60000,GL_UNSIGNED_INT,indices);
    glDisableClientState(GL_VERTEX_ARRAY);
    glPopMatrix();
}

РЕДАКТИРОВАТЬ 1 Вот код, который я выписал. Я просто использовал массивы вместо векторов и сохранил все нормали в структуре, называемой нормали. Это все еще не работает как бы то ни было. Я получаю необработанное исключение по * индексам.

struct Normals {
    GLfloat x;
    GLfloat y;
    GLfloat z;
}normals[20000];
Normals* normal = normals;
//***************************************ENVIRONMENT*************************************************************************
struct vertices {
    GLfloat x;
    GLfloat y;
    GLfloat z;
}vertices[10000];

GLuint indices[59403];

/*
99..9999
98..9998
........
01..9901
00..9900
*/

void CreateEnvironment() {
    int count=0;
    for (float x=0;x<10.0;x+=.1) {
        for (float z=0;z<10.0;z+=.1) {
            vertices[count].x=x;
            vertices[count].y=rand()%2-2;;
            vertices[count].z=z;
            count++;
        }
    }
    //calculate normals 
    GLfloat vector1[3];//XYZ
    GLfloat vector2[3];//XYZ
    count=0;
    for (int x=0;x<9900;x+=100){
        for (int z=0;z<99;z++){
            vector1[0]= vertices[x+z].x-vertices[x+z+1].x;//vector1x
            vector1[1]= vertices[x+z].y-vertices[x+z+1].y;//vector1y
            vector1[2]= vertices[x+z].z-vertices[x+z+1].z;//vector1z
            vector2[0]= vertices[x+z+1].x-vertices[x+z+100].x;//vector2x
            vector2[1]= vertices[x+z+1].y-vertices[x+z+100].y;//vector2y
            vector2[2]= vertices[x+z+1].z-vertices[x+z+100].z;//vector2z
            normals[count].x= vector1[1] * vector2[2]-vector1[2]*vector2[1];
            normals[count].y= vector1[2] * vector2[0] - vector1[0] * vector2[2];
            normals[count].z= vector1[0] * vector2[1] - vector1[1] * vector2[0];count++;
        }
    }
    count=10000;
    for (int x=100;x<10000;x+=100){
        for (int z=0;z<99;z++){
            vector1[0]= vertices[x+z].x-vertices[x+z+1].x;//vector1x -- JUST ARRAYS
            vector1[1]= vertices[x+z].y-vertices[x+z+1].y;//vector1y
            vector1[2]= vertices[x+z].z-vertices[x+z+1].z;//vector1z
            vector2[0]= vertices[x+z+1].x-vertices[x+z-100].x;//vector2x
            vector2[1]= vertices[x+z+1].y-vertices[x+z-100].y;//vector2y
            vector2[2]= vertices[x+z+1].z-vertices[x+z-100].z;//vector2z
            normals[count].x= vector1[1] * vector2[2]-vector1[2]*vector2[1];
            normals[count].y= vector1[2] * vector2[0] - vector1[0] * vector2[2];
            normals[count].z= vector1[0] * vector2[1] - vector1[1] * vector2[0];count++;
        }
    }

    count=0;
    for (GLuint a=0;a<99;a++){
        for (GLuint b=0;b<99;b++){
            GLuint v1=(a*100)+b;indices[count]=v1;count++;
            GLuint v2=(a*100)+b+1;indices[count]=v2;count++;
            GLuint v3=(a*100)+b+100;indices[count]=v3;count++;
        }
    }
    count=30000;
    for (GLuint a=0;a<99;a++){
        for (GLuint b=0;b<99;b++){
            indices[count]=(a*100)+b+100;count++;//9998
            indices[count]=(a*100)+b+1;count++;//9899
            indices[count]=(a*100)+b+101;count++;//9999
        }
    }
}

void ShowEnvironment(){
    //ground
    glPushMatrix();
    GLfloat GroundAmbient[]={0.0,0.5,0.0,1.0};
    GLfloat GroundDiffuse[]={1.0,0.0,0.0,1.0};
    glMaterialfv(GL_FRONT,GL_AMBIENT,GroundAmbient);
    glMaterialfv(GL_FRONT,GL_DIFFUSE,GroundDiffuse);
    glEnableClientState(GL_VERTEX_ARRAY);
    glEnableClientState(GL_NORMAL_ARRAY);
    glNormalPointer( GL_FLOAT, 0, normal);
    glVertexPointer(3,GL_FLOAT,0,vertices);
    glDrawElements(GL_TRIANGLES,60000,GL_UNSIGNED_INT,indices);
    glDisableClientState(GL_VERTEX_ARRAY);
    glDisableClientState(GL_NORMAL_ARRAY);
    glPopMatrix();
}
//***************************************************************************************************************************

Answer 1

Есть ли у каждой вершины свои нормали или у каждого треугольника свои нормали?

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

Скажем, у вас есть треугольник с точками A , B , C , тогда эти точки имеют векторы позиций ↑ A , ↑ B , ↑ C , а ребра имеют векторы ↑ B - ↑ A и ↑ C - ↑ A , поэтому вектор нормали лица N _f = (↑ B - ↑ A) × (↑ C - ↑ A)

Обратите внимание, что величина ↑ N _f , как указано выше, прямо пропорциональна площади лица.

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

↑ N _v = ∑ p ↑ N _f ; где p - взвешивание для каждого лица.

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

Теперь вспомните, что вы нормализуетесь по вектору ↑ v , масштабируя его с обратным расстоянием: ↑ v _i = ↑ v / | ↑ v |, Но, как уже говорилось, длина лица нормали уже зависит от площади лица. Таким образом, весовой коэффициент p , приведенный выше, уже содержится в самом векторе: его длина, или величина. Таким образом, мы можем получить вектор нормали вершины, просто суммируя все нормали лица.

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

Внимательный читатель, возможно, заметил, что я специально сказал, гладкие поверхности имеют общие вершины. И на самом деле, если у вас есть некоторые складки / жесткие края в вашей геометрии, то грани с обеих сторон не имеют общих вершин. В OpenGL вершина - это целое сочетание

• положение
• нормальный
• (цвет)
• N текстурных координат
• M других атрибутов

Вы меняете один из них, и вы получаете совершенно другую вершину. Теперь некоторые 3D-моделисты видят вершину только как положение точки и сохраняют остальные эти атрибуты на грани (такой моделлер - Blender). Это экономит некоторую память (или значительную память, в зависимости от количества атрибутов). Но OpenGL нуждается во всем этом, поэтому при работе с таким смешанным файлом парадигмы вам придется сначала разбить его на OpenGL-совместимые данные. Взгляните на один из сценариев экспорта Blender, например, экспортер PLY, чтобы увидеть, как это делается.

---

Теперь, чтобы покрыть какую-то другую вещь. В вашем коде у вас есть это:

 glIndexPointer( GL_UNSIGNED_BYTE, 0, indices );

Указатель индекса не имеет ничего общего с индексами массива вершин 1086 *! Это анахроним из тех дней, когда графика все еще использовала палитры вместо истинного цвета. Цвет пикселей не устанавливался путем предоставления значений RGB, а с помощью смещения одного числа в ограниченную палитру цветов. Цвета палитры все еще можно найти в нескольких форматах графических файлов, но ни один из них не использует их больше.

Пожалуйста, удалите glIndexPointer (и glIndex) из вашей памяти и вашего кода, они не делают то, что вы думаете, что они делают Весь индексированный цветовой режим очень сложен в использовании, и, честно говоря, я не знаю ни одного оборудования, созданного после 1998 года, которое все еще поддерживало бы его.

Answer 2

Для каждой вершины.

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

Answer 3

Недурно для datenwolf! Я полностью согласен с его подходом. Добавление векторов нормалей соседних треугольников для каждой вершины, а затем нормализация - путь. Я просто хочу немного подтолкнуть ответ и поближе познакомиться с частным, но довольно распространенным случаем прямоугольной , гладкой сетки, которая имеет константу х / у шаг . Другими словами, прямоугольная x / y сетка с переменной высотой в каждой точке.

Такая сетка создается циклом по x и y и установкой значения для z и может представлять такие вещи, как поверхность холма. Таким образом, каждая точка сетки представлена ​​вектором

P = (x, y, f(x,y)) 

где f (x, y) - функция, задающая z каждой точки на сетке.

Обычно, чтобы нарисовать такую ​​сетку, мы используем TriangleStrip или TriangleFan, но любой метод должен давать похожую топографию для получающихся треугольников.

     |/   |/   |/   |/
...--+----U----UR---+--...
    /|   /| 2 /|   /|           Y
   / |  / |  / |  / |           ^
     | /  | /  | /  | /         |
     |/ 1 |/ 3 |/   |/          |
...--L----P----R----+--...      +-----> X
    /| 6 /| 4 /|   /|          
   / |  / |  / |  / |         
     | /5 | /  | /  | /      
     |/   |/   |/   |/
...--DL---D----+----+--...
    /|   /|   /|   /|

Для triangleStrip каждая вершина P = (x0, y0, z0) имеет 6 смежных вершин, обозначаемых

up       = (x0     , y0 + ay, Zup)
upright  = (x0 + ax, y0 + ay, Zupright) 
right    = (x0 + ax, y0     , Zright) 
down     = (x0     , y0 - ay, Zdown)
downleft = (x0 - ax, y0 - ay, Zdownleft) 
left     = (x0 - ax, y0     , Zleft)

где ax / ay - постоянный шаг сетки на оси x / y соответственно. На квадратной сетке топор = ау.

ax = width / (nColumns - 1)
ay = height / (nRows - 1)

Таким образом, каждая вершина имеет 6 смежных треугольников, каждый со своим собственным вектором нормалей (обозначается от N1 до N6). Их можно рассчитать, используя перекрестное произведение двух векторов, определяющих сторону треугольника, и внимательно следя за порядком, в котором мы делаем перекрестное произведение. Если нормальный вектор указывает в направлении Z к вам:

N1 = up x left =
   = (Yup*Zleft - Yleft*Zup, Xleft*Zup - Xup*ZLeft, Xleft*Yup - Yleft*Xup) 

   =( (y0 + ay)*Zleft - y0*Zup, 
      (x0 - ax)*Zup   - x0*Zleft, 
      x0*y0 - (y0 + ay)*(x0 - ax) ) 

N2 = upright  x up
N3 = right    x upright
N4 = down     x right
N5 = downleft x down
N6 = left     x downleft

И результирующий вектор нормали для каждой точки P является суммой от N1 до N6. Нормализуем после суммирования. Очень просто создать цикл, вычислить значения каждого вектора нормалей, добавить их и затем нормализовать. Однако, как указал г-н Шикаданс, это может занять довольно много времени, особенно для больших сеток и / или на встроенных устройствах.

Если мы посмотрим поближе и выполним вычисления вручную, мы обнаружим, что большинство слагаемых взаимно компенсируют друг друга, что дает нам очень элегантное и простое для вычисления окончательное решение для результирующего вектора N. Точка здесь необходимо ускорить вычисления, избегая вычисления координат от N1 до N6, выполняя 6 перекрестных произведений и 6 сложений для каждой точки. Алгебра помогает нам перейти к решению, использовать меньше памяти и меньше процессорного времени.

Я не буду показывать детали вычислений, так как они длинные, но прямолинейные, и я перейду к окончательному выражению вектора Normal для любой точки сетки. Для ясности разложен только N1, остальные векторы выглядят одинаково. После суммирования получаем N, которое еще не нормализовано:

N = N1 + N2 + ... + N6

  = .... (long but easy algebra) ...

  = ( (2*(Zleft - Zright) - Zupright + Zdownleft + Zup - Zdown) / ax,
      (2*(Zdown - Zup)    + Zupright + Zdownleft - Zup - Zleft) / ay,
       6 )

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

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

Вы даже можете упростить его, приняв во внимание только значения Z четырех окружающих точек (вверх, вниз, влево и вправо). В этом случае вы получите:

                                             |   \|/   |
N = N1 + N2 + N3 + N4                    ..--+----U----+--..
  = ( (Zleft - Zright) / ax,                 |   /|\   |
      (Zdown -  Zup  ) / ay,                 |  / | \  |
       2 )                                 \ | / 1|2 \ | /
                                            \|/   |   \|/
                                         ..--L----P----R--...
                                            /|\   |   /|\
                                           / | \ 4|3 / | \
                                             |  \ | /  |
                                             |   \|/   |
                                         ..--+----D----+--..
                                             |   /|\   |

, что еще более элегантно и еще быстрее вычислить.

Надеюсь, это сделает несколько мешей быстрее. Приветствия

Answer 4

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

Так почему нормализованный перекрестный продукт является лишь частью проблемы?Порядок намотки вершин в этом многоугольнике определяет направление нормали , т. Е. Если одна пара вершин поменяется местами, нормаль будет указывать в противоположном направлении.Таким образом, на самом деле это может быть проблематично, если сама сетка содержит несоответствия в этом отношении, то есть ее части принимают одно упорядочение, в то время как другие части принимают другое упорядочение.Один известный пример - оригинальная модель Stanford Bunny , где некоторые части поверхности будут направлены внутрь, а другие - наружу.Причина этого заключается в том, что модель была построена с использованием сканера, и не было предпринято никаких усилий для получения треугольников с регулярными рисунками намотки.(очевидно, чистые версии кролика также существуют)

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

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

Одна потенциальная стратегия, которая часто используется для решения этой проблемы, состоит в том, чтобы стрелять случайными лучами наружу к центру каждой полутриангуляции (то есть нанесение луча ).Но нельзя предполагать, что триангуляция верна, если многоугольники могут содержать несколько вершин, поэтому лучи могут пропустить этот конкретный подтреугольник.Если луч попадает, то нормаль, противоположная направлению луча, то есть с удовлетворением точка (луч, n) <.5 </em>), может использоваться как нормаль для всего многоугольника.Очевидно, что это довольно дорого и масштабируется с количеством вершин на многоугольник.

К счастью, есть отличная новая работа , которая описывает альтернативный метод, который не только быстрее (для больших и сложных сеток), но также обобщает «порядок намотки» для конструкций за пределами многоугольных сеток , таких как облака точек исупы многоугольников, изо-поверхности и поверхности с точечными наборами, где связность может даже не быть определена!

Как описано в статье, метод создает представление иерархического расщепления дерева , которое уточняетсяпостепенно, принимая во внимание родительскую «дипольную» ориентацию при каждой операции разделения.Тогда нормаль многоугольника будет просто интегрированием (средним) по всем диполям (т. Е. Парам точки + нормали) многоугольника.

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