计算三角形网格中的法线

发布于 2024-11-19 07:14:14 字数 5276 浏览 3 评论 0原文

我画了一个有 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 这是我写的代码。我只是使用数组而不是向量，并将所有法线存储在称为法线的结构中。然而它仍然不起作用。我在 *indices 处遇到未处理的异常。

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();
}
//***************************************************************************************************************************

原文

I have drawn a triangle mesh with 10000 vertices(100x100) and it will be a grass ground. I used gldrawelements() for it. I have looked all day and still can't understand how to calculate the normals for this. Does each vertex have its own normals or does each triangle have its own normals? Can someone point me in the right direction on how to edit my code to incorporate normals?

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();
}

EDIT 1
Here is the code I have written out. I just used arrays instead of vectors and I stored all of the normals in the struct called normals. It still doesn't work however. I get an unhandled exception at *indices.

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();
}
//***************************************************************************************************************************

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

记忆里有你的影子 2024-11-26 07:14:14

每个顶点都有自己的法线还是每个三角形都有自己的法线？

像往常一样，答案是：“这取决于”。由于法线被定义为垂直于给定平面（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 );

索引指针与顶点数组索引无关！这是一个时代错误，当时图形仍然使用调色板而不是真彩色。像素颜色不是通过给出其 RGB 值来设置的，而是通过偏移到有限调色板中的单个数字来设置的。调色板颜色仍然可以在多种图形文件格式中找到，但没有像样的硬件不再使用它们。

请从你的内存和代码中删除glIndexPointer（和glIndex），它们不会做你认为它们会做的事情整个索引颜色模式使用起来很神秘，坦率地说我不知道有什么1998 年之后构建的仍然支持它的硬件。

Does each vertex have its own normals or does each triangle have its own normals?

Like so often the answer is: "It depends". Since a normal is defined as being the vector perpendicular to all vectors within a given plane (in N dimensions), you need a plane to calculate a normal. A vertex position is just a point and thus singular, so you actually need a face to calculate the normal. Thus, naively, one could assume that normals are per face as the first step in normal calculation is determining the face normals, by evaluating the cross product of the faces edges.

Say you have a triangle with points A, B, C, then these points have position vectors ↑A, ↑B, ↑C and the edges have vectors ↑B - ↑A and ↑C - ↑A so the face normal vector is ↑N_f = (↑B - ↑A) × (↑C - ↑A)

Note that the magnitude of ↑N_f as it's stated above is directly proportional to the face's area.

In smooth surfaces vertices are shared between faces (or you could say those faces share a vertex). In that case the normal at the vertex is not one of the face normals of the faces it is part of, but a linear combination of them:

↑N_v = ∑ p ↑N_f ; where p is a weighting for each face.

One could either assume a equal weighting between the participating face normals. But it makes more sense to assume that the larger a face is, the more it contributes to the normal.

Now recall that you normalize by a vector ↑v by scaling it with it's recipocal length: ↑v_i = ↑v/|↑v|. But as already told the length of the face normals already depends on the face's area. So the weighting factor p given above is already contained in the vector itself: Its length, aka magnitude. So we can get the vertex normal vector by simply summing up all the face normals.

In lighting calculations the normal vector must be unit length, i.e. normalized to be useable. So after summing up, we normalize the newly found vertex normal and use that.

The carefull reader may have noticed I specifically said smooth surfaces share vertices. And in fact, if you have some creases / hard edges in your geometry, then the faces on either side don't share vertices. In OpenGL a vertex is the whole combination of

position
normal
(colour)
N texture coordinates
M further attributes

You change one of these and you got a completely different vertex. Now some 3D modelers see a vertex only as a point's position and store the rest of those attributes per face (Blender is such a modeler). This saves some memory (or considerable memory, depending on the number of attributes). But OpenGL needs the whole thing, so if working with such a mixed paradigm file you will have to decompose it into OpenGL compatible data first. Have a look at one of Blender's export scripts, like the PLY exporter to see how it's done.

Now to cover some other thing. In your code you have this:

 glIndexPointer( GL_UNSIGNED_BYTE, 0, indices );

The index pointer has nothing to do with vertex array indices! This is an anachronsim from the days, when graphics still used palettes instead of true color. A pixels colour wasn't set by giving it's RGB values, but by a single number offsetting into a limited palette of colours. Palette colours can still be found in several graphics file formats, but no decent piece of hardware uses them anymore.

Please erase glIndexPointer (and glIndex) from your memory and your code, they don't do what you think they do The whole indexed color mode is arcane to used, and frankly I don't know of any hardware built after 1998 that still supported it.

回复收藏 0 原文

各空 2024-11-26 07:14:14

为datenwolf点赞！我完全同意他的做法。将每个顶点的相邻三角形的法向量相加，然后进行归一化是可行的方法。我只是想稍微推动一下答案，并仔细看看矩形、平滑网格的特定但相当常见的情况，它具有常数 x /y 步骤。换句话说，每个点高度可变的矩形 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 = ay。

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 的总和。求和后我们进行归一化。创建循环、计算每个法线向量的值、将它们相加然后标准化是非常容易的。然而，正如 Shickadance 先生所指出的，这可能需要相当长的时间，特别是对于大型网格和/或嵌入式设备。

如果我们仔细观察并手动执行计算，我们会发现大多数项相互抵消，从而为结果向量 N 留下一个非常优雅且易于计算的最终解决方案。这里的要点是通过避免计算 N1 到 N6 的坐标，对每个点进行 6 次叉积和 6 次加法来加速计算。代数帮助我们直接跳到解决方案，使用更少的内存和更少的 CPU 时间。

我不会显示计算的细节，因为它很长但很简单，并且会跳转到网格上任何点的法线向量的最终表达式。为了清楚起见，仅分解了 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----+--..
                                             |   /|\   |

，这更优雅，计算速度更快。

希望这会让一些网格更快。
干杯

Thumbs up for datenwolf! I completely agree with his approach. Adding the normal vectors of the adjacent triangles for each vertex and then normalising is the way to go. I just want to push the answer a little bit and have a closer look at the particular but quite common case of a rectangular, smooth mesh that has a constant x/y step. In other words, a rectangular x/y grid with a variable height at each point.

Such a mesh is created by looping over x and y and setting a value for z and can represent things like the surface of a hill. So each point of the mesh is represented by a vector

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

where f(x,y) is a function giving the z of each point on the grid.

Usually to draw such a mesh we use a TriangleStrip or a TriangleFan but any technique should give a similar topography for the resulting triangles.

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

For a triangleStrip each vertex P=(x0, y0, z0) has 6 adjacent vertices denoted

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)

where ax/ay is the constant grid step on the x/y axis respectively. On a square grid ax = ay.

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

Thus each vertex has 6 adjacent triangles each one with its own normal vector (denoted N1 to N6). These can be calculated using the cross product of the two vectors defining the side of the triangle and being careful on the order in which we do the cross product. If the normal vector points in the Z direction towards you :

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

And the resulting normal vector for each point P is the sum of N1 to N6. We normalise after summing. It's very easy to create a loop, calculate the values of each normal vector, add them and then normalise. However, as pointed out by Mr. Shickadance, this can take quite a while, especially for large meshes and/or on embedded devices.

If we have a closer look and perform the calculations by hand, we will find out that most of the terms cancel out each other, leaving us with a very elegant and easy to calculate final solution for the resulting vector N. The point here is to speed up calculations by avoiding calculating the coordinates of N1 to N6, doing 6 cross-products and 6 additions for each point. Algebra helps us to jump straight to the solution, use less memory and less CPU time.

I will not show the details of the calculations as it is long but straight-forward and will jump to the final expression of the Normal vector for any point on the grid. Only N1 is decomposed for the sake of clarity, the other vectors look alike. After summing we obtain N which is not yet normalized :

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 )

There you go! Just normalise this vector and you have the normal vector for any point on the grid, provided you know the Z values of its surrounding points and the horizontal/vertical step of your grid.

Note that this is the weighed average of the surrounding triangles' normal vectors. The weight is the area of the triangles and is already included in the cross product.

You can even simplify it more by only taking into account the Z values of four surrounding points (up,down,left and right). In that case you get :

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

which is even more elegant and even faster to calculate.

Hope this will make some meshes faster.
Cheers

回复收藏 0 原文

夏有森光若流苏 2024-11-26 07:14:14

每个顶点。

使用叉积计算给定顶点周围三角形的面法线，将它们加在一起并标准化。

回复收藏 0 原文

墟烟 2024-11-26 07:14:14

对于像我这样遇到这个问题的人，你的答案可能是这样的：

// Compute Vertex Normals
std::vector<sf::Glsl::Vec3> verticesNormal;
verticesNormal.resize(verticesCount);

for (i = 0; i < indices.size(); i += 3)
{
    // Get the face normal
    auto vector1 = verticesPos[indices[(size_t)i + 1]] - verticesPos[indices[i]];
    auto vector2 = verticesPos[indices[(size_t)i + 2]] - verticesPos[indices[i]];
    auto faceNormal = sf::VectorCross(vector1, vector2);
    sf::Normalize(faceNormal);

    // Add the face normal to the 3 vertices normal touching this face
    verticesNormal[indices[i]] += faceNormal;
    verticesNormal[indices[(size_t)i + 1]] += faceNormal;
    verticesNormal[indices[(size_t)i + 2]] += faceNormal;
}

// Normalize vertices normal
for (i = 0; i < verticesNormal.size(); i++)
    sf::Normalize(verticesNormal[i]);

For those like me who came across this question, your answer might be this :

// Compute Vertex Normals
std::vector<sf::Glsl::Vec3> verticesNormal;
verticesNormal.resize(verticesCount);

for (i = 0; i < indices.size(); i += 3)
{
    // Get the face normal
    auto vector1 = verticesPos[indices[(size_t)i + 1]] - verticesPos[indices[i]];
    auto vector2 = verticesPos[indices[(size_t)i + 2]] - verticesPos[indices[i]];
    auto faceNormal = sf::VectorCross(vector1, vector2);
    sf::Normalize(faceNormal);

    // Add the face normal to the 3 vertices normal touching this face
    verticesNormal[indices[i]] += faceNormal;
    verticesNormal[indices[(size_t)i + 1]] += faceNormal;
    verticesNormal[indices[(size_t)i + 2]] += faceNormal;
}

// Normalize vertices normal
for (i = 0; i < verticesNormal.size(); i++)
    sf::Normalize(verticesNormal[i]);

回复收藏 0 原文

那些过往 2024-11-26 07:14:14

尽管看起来很简单，计算三角形的法线只是问题的一部分。在三角形情况下，多边形 2 条边的叉积就足够了，除非三角形自身塌陷并退化；在这种情况下，没有一种有效的法线，因此您可以根据自己的喜好选择一种。

那么为什么归一化叉积只是问题的一部分呢？该多边形中顶点的缠绕顺序定义了法线的方向，即，如果一对顶点交换到位，则法线将指向相反的方向。因此，事实上，如果网格本身在这方面存在不一致，即部分网格采用一种排序，而其他部分采用不同的排序，则这可能会出现问题。一个著名的例子是原始的 Stanford Bunny 模型，其中表面的某些部分将指向内，而其他人则指向外面。原因是该模型是使用扫描仪构建的，并且没有注意生成具有规则缠绕图案的三角形。（显然，干净版本的兔子也存在）

如果多边形可以有多个顶点，则缠绕问题会更加突出，因为在这种情况下，您将对该多边形的半三角剖分的部分法线进行平均。考虑部分法线指向相反方向的情况，导致取平均值时法线向量的长度为 0！

同样的意义，由于不明确的缠绕数，断开的多边形汤和点云对精确重建提出了挑战。

经常用于解决此问题的一种潜在策略是从每个半三角剖分的中心向外发射随机射线（即射线刺穿）。但是，如果多边形可以包含多个顶点，则不能假设三角剖分是有效的，因此光线可能会错过该特定的子三角形。如果光线击中，则法线方向与光线方向相反，即 dot(ray, n) .5 满足，可以作为整个多边形的法线。显然，这是相当昂贵的，并且随着每个多边形的顶点数量而变化。

值得庆幸的是，有很棒的新工作，描述了一种替代方法，该方法不仅更快（对于大型和复杂的网格），而且概括“缠绕顺序”构造的概念超越多边形网格，例如点云和多边形汤，iso -曲面和点集曲面，甚至可能无法定义连通性！

正如本文所述，该方法构建了一个逐步细化的分层分裂树表示，在每次分裂操作时都考虑到父“偶极子”方向。多边形法线将简单地是多边形的所有偶极子（即点+法线对）的积分（平均值）。

对于处理来自激光雷达扫描仪或其他来源的不干净网格/pcl 数据的人来说，这可能是肯定的。成为游戏规则的改变者。

As simple as it may seem, calculating the normal of a triangle is only part of the problem. The cross product of 2 sides of the polygon is sufficient in triangular cases, unless the triangle is collapsed onto itself and degenerate; in that case there is no one valid normal, so you can select one to your liking.

So why is the normalized cross product only part of the problem? The winding order of the vertices in that polygon defines the direction of the normal, i.e. if one pair of vertices is swapped in place, the normal will point in the opposite direction. So in fact this can be problematic if the mesh itself contains inconsistencies in that regard, i.e. parts of it assume one ordering, while other parts assume different orderings. One famous example is the original Stanford Bunny model, where some parts of the surface will point inwards, while others point outwards. The reason for that is because the model was constructed using a scanner, and no care was taken to produce triangles with regular winding patterns. (obviously, clean versions of the bunny also exist)

The winding problem is even more prominent if polygons can have multiple vertices, because in that case you would be averaging partial normals of the semi-triangulation of that polygon. Consider the case where partial normals are pointing in opposite directions, resulting in normal vectors of length 0 when taking the mean!

In the same sense, disconnected polygon soups and point clouds present challenges for accurate reconstruction due to the ill-defined winding number.

One potential strategy that is often used to solve this problem is to shoot random rays from outward to the center of each semi-triangulation (i.e. ray-stabbing). But one cannot assume that the triangulation is valid if polygons can contain multiple vertices, so rays may miss that particular sub-triangle. If a ray hits, then normal opposite to the ray direction, i.e. with dot(ray, n) < .5 satisfied, can be used as the normal for the entire polygon. Obviously this is rather expensive and scales with the number of vertices per polygon.

Thankfully, there's great new work that describes an alternative method that is not only faster (for large and complex meshes) but also generalizes the 'winding order' concept for constructions beyond polygon meshes, such as point clouds and polygon soups, iso-surfaces, and point-set surfaces, where connectivity may not even be defined!

As outlined in the paper, the method constructs a hierarchical splitting tree representation that is refined progressively, taking the parent 'dipole' orientation into account at every split operation. A polygon normal would then simply be an integration (mean) over all di-poles (i.e. point+normal pairs) of the polygon.

For people who are dealing with unclean mesh/pcl data from Lidar scanners or other sources, this could def. be a game-changer.

回复收藏 0 原文

惜醉颜 2024-11-26 07:14:14

最简单的方法是将三角形 (p1,p2,p3) 点之一（例如 p1）转换为 (0,0,0)，这意味着 (x2,y2,z2)->(x2-x1,y2-y1,z2-z1) 和(x3,y3,z3)->(x3-x1,y3-y1,z3-z1)。然后，对变换点执行点积以获得平面斜率，或执行叉积以获得外向法线< /强>。

请参阅：

https://en.wikipedia.org/wiki/Cross_product #/media/File:Cross_product_vector.svg

用于叉积和点积之间差异的简单直观表示。

将其中一个点移动到原点基本上相当于沿着p1p2和p2p3生成向量。