在三角形网格中计算法向量

57

我已经用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 这是我编写的代码。我只是使用了数组而不是向量,并将所有法线存储在名为normals的结构体中。然而,它仍然不起作用。我在*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();
}
//***************************************************************************************************************************

顶点不能有法线(除非它们是周围面的法线平均值)。我从未使用过openGL,所以不知道是否有简单的方法来获取它们。我想应该有,但如果你想自己做,你可以通过计算顶点的边向量并通过两个边的叉积计算法线(然后归一化到1的大小)来计算。 - Dan
我刚刚编辑了它。我对代码进行了一些更改,但它无法编译。 - Vince
glDrawElements(GL_TRIANGLES,60000,GL_UNSIGNED_INT,indices); 运行时将会超出您的包含59403个元素的 indices 数组的末尾。 - genpfault
1
使用10000个顶点来制作草地似乎有些太大了,除非它是一个非常大的区域,并且具有许多有趣的地形特征。您可以考虑使用粗网格进行纹理映射和法线贴图。这只是一个想法。 - emsr
6个回答

153
每个顶点是否拥有自己的法线向量,还是每个三角形都有自己的法线向量?
常见的答案是:“这要看情况”。因为法线向量被定义为垂直于给定平面(在N维空间中)内所有向量的向量,所以需要一个平面来计算法线向量。顶点位置只是一个点,因此需要一个面来计算法线向量。因此,天真地说,人们可以假设法线向量是按面数计算的,因为正常计算法线的第一步是通过计算面边缘的叉积来确定面法线。
如果你有一个由点A、B、C组成的三角形,则这些点具有位置向量上方的A、B、C向量,边缘具有向量B-A和C-A,因此面法线向量为 Nf=(B-A)×(C-A)。
请注意,如上所述的 Nf 的大小与面积成比例。
在光滑表面中,顶点在面之间共享(或者可以说那些面共享一个顶点)。在这种情况下,顶点的法线不是它所属面的面法线之一,而是它们的线性组合:
Nv = ∑ p Nf;其中p是每个面的权重。
可以假设参与面法线的权重相等。但是更合理的做法是认为面积越大,对法线的贡献越大。
现在回想一下,要缩放向量 v,需要将它与其倒数长度相乘:vi=v/|v |。但是如前所述,面法线的长度已经取决于面积。因此,给定的加权因子p已经包含在向量本身中:其长度(也称为大小)。因此,我们可以通过简单地求和所有面法线来得到顶点法线向量。
在光照计算中,法线向量必须是单位长度,即规范化后才能使用。因此,在求和之后,规范化新找到的顶点法线并使用它。
仔细的读者可能会注意到,我特别说了“光滑”表面共享顶点。事实上,如果您的几何体中有一些棱角/硬边,则两侧的面不共享顶点。在OpenGL中,一个顶点是:
- 位置 - 法线 - (颜色) - N个纹理坐标 - M个其他属性
改变其中任何一个都会得到完全不同的顶点。现在一些3D模型制作软件只将顶点视为点的位置,并将其余属性存储在每个面上(Blender就是这样的模型制作软件)。这可以节省一些内存(或者根据属性数量而言,节省相当多的内存)。但是OpenGL需要整个数据,因此如果使用这种混合范例文件,则必须首先将其分解为OpenGL兼容数据。可以查看Blender的导出脚本之一(如PLY导出器)来了解如何做到这一点。
现在来介绍一些其他事情。在你的代码中,有这样一个部分:
 glIndexPointer( GL_UNSIGNED_BYTE, 0, indices );

索引指针与顶点数组索引毫不相干!这是过时的概念,在图形仍然使用调色板而非真彩色的日子里出现。像素的颜色不是通过RGB值来设置的,而是通过一个单一的数字偏移来进入有限的调色板颜色中。调色板颜色仍然可以在几种图形文件格式中找到,但没有像样的硬件再使用它们了。

请把 glIndexPointer(和 glIndex)从你的记忆和代码中删除,它们并不是你所认为的那样操作。整个索引颜色模式很古怪,说实话,我不知道在1998年之后还有哪些硬件支持它。


p是每个面的权重,那么这个p从哪里来? - convert
1
@convert:在接下来的两段中描述。也就是说,您可以通过法线所属的面积隐含地获得p。由于法线的计算方式(叉积),因此该区域直接进入法线,无需进行任何额外的计算。它就在文字上: “因此,上述给定的加权因子p已经包含在向量本身中:其长度,也称为大小。” - datenwolf
那么在计算中我可以忽略p吗?或者如果面是三角形,它应该是0.5吗? - convert
1
@convert: 正如我所解释的,p是一个隐式参数,恰好也作为叉积的副作用计算出来。你不需要对此做任何事情。只需计算连接到顶点的边的叉积向量,但不要将结果向量缩放为单位长度(通过叉积获得的向量的长度就是 p)。把所有东西加起来,然后在之后将其缩放为单位长度。 - datenwolf
这就是我问的,只需忽略 p。 - convert

38

支持 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的法向量N是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----+--..
                                             |   /|\   |

这种方法更加优雅且计算速度更快。

希望这能够使一些网格更快。祝好!


我不明白为什么第一个三角形的法向量等于“N1 = up x left”。难道不应该通过对三角形的两条边进行叉积计算,这些边可以是E1 =(U-P)和E2 =(L-P),然后法向量应该等于“N1 =(U-P)x(L-P)”吗? - unlut
1
@unlut 你说得对,这个答案有误。所呈现的是一种非常复杂的方法来得出最后的公式,而实际上可以简单地推导出 N = (dP/dx) x (dP/dy)。对导数进行二阶近似:dP/dx = (R-L)/2axdP/dy = (U-D)/2ay,然后你就可以得到 N = (R-L)x(U-D)(经过缩放因子)。对于此项任务,无需处理三角形网格。事实上,应该避免使用第一个公式来计算 N,因为它取决于网格的选择,并且只是对平滑表面真实法线的一阶近似。 - Yakov Galka
1
@unlut 你说得对,这个答案有一个错误。所呈现的是一种非常复杂的方法来得到最后的公式,而实际上我们可以简单地推导出 N = (dP/dx) x (dP/dy)。对导数进行二阶近似:dP/dx = (R-L)/2axdP/dy = (U-D)/2ay,然后你就会得到 N = (R-L)x(U-D)(乘以一个比例因子)。对于这个问题,并不需要处理三角形网格。事实上,第一个公式中的 N 应该避免使用,因为它取决于网格的选择,并且只是对平滑曲面真实法线的一阶近似。 - Yakov Galka
算法非常好。我的问题是它是否可以由GPU计算?我的意思是它能够通过OpenGL的着色器来完成吗?谢谢。 - ollydbg23

28

每个顶点。

使用叉乘计算围绕给定顶点的三角形的面法线,将它们相加并进行归一化。


2
非常正确。 :-) 我不会添加自己的答案,而是在这个答案中添加一个关于计算法线的详细描述的评论。 - Wroclai
有没有更有效的方法来做这件事?对于简单模型来说它还可以,但是一旦我有大量的顶点,计算每个顶点的法线就需要很长时间。 - Mr. Shickadance
然后还有所有的边缘情况,例如面积为零或者很细的三角形会扭曲法线的权重——通过三角形面积加权法线(未归一化地求和叉乘,最后再进行归一化)是可行的,但并不总是能得到完美的结果。 - jozxyqk

6

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

// 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]);

非常感谢您。这让我免去了解密数学的麻烦。我可以确认这段代码是有效的。 - Dess

3
计算三角形法线似乎很简单,但这只是问题的一部分。在三角形情况下,多边形的两条边的叉积就足够了,除非三角形折叠并退化; 在这种情况下,不存在一个有效的法线,因此您可以根据自己的喜好选择一个。
那么为什么标准化的叉积只是问题的一部分呢?该多边形中顶点的“绕序”定义了法线的方向,即如果交换一对顶点的位置,则法线将指向相反的方向。因此,如果网格本身在这方面存在不一致性,即其某些部分假定一种排序方式,而其他部分假定不同的排序方式,则实际上可能会出现问题。一个著名的例子是原始的Stanford Bunny模型,其中表面的某些部分将指向内部,而其他部分则指向外部。其原因是该模型是使用扫描仪构建的,并且没有注意产生具有规则绕组模式的三角形。(显然,干净的兔子版本也存在)
多边形可能有多个顶点,这就使得缠绕问题更加突出,因为在这种情况下,您将平均半三角剖分的部分法线。考虑部分法线指向相反方向的情况,结果是取平均后的法向量长度为0!
同样地,由于不确定的缠绕数,断开的多边形集和点云也会对准确重建造成挑战。
解决此问题常用的一种潜在策略是从外部向每个半三角剖分的中心发射随机光线(即“射线刺穿”)。但如果多边形可以包含多个顶点,则不能假定三角化有效,因此光线可能会错过特定的子三角形。如果碰撞到了,那么与光线方向相反的法线,即满足点积(ray, n) < .5的法线,可以用作整个多边形的法线。显然,这相当耗费并且随着每个多边形的顶点数而扩展。
感谢有一篇优秀的新作品,描述了一种替代方法,不仅更快(对于大型和复杂的网格),而且还将'绕组顺序'概念推广到了构造超越多边形网格的对象上,例如点云和多边形汤、等值面和点集表面,甚至可能没有定义连通性!
正如论文所述,该方法构建了一个分层分割树表示,逐步细化,在每个分割操作中考虑父级“偶极子”的方向。然后,多边形法线将简单地是多极子(即点+法线对)的所有积分(平均)。
对于处理来自激光雷达扫描仪或其他来源的不干净的网格/ pcl数据的人来说,这可能会改变游戏规则。

0

简单地,我们可以将三角形(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

为了简单地可视化叉积和点积之间的差异。

将其中一个点移动到原点的操作基本上等同于沿着p1p2p2p3生成向量。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接