如何计算一个盒子的法线？ [英] How to calculate the normals of a box?

问题描述

我试图创建一个计算模型/网格法线的算法。人们一直告诉我要使用这两种媒介之间的交叉产品，最初看起来似乎是一个好主意，直​​到我发现它可能并不总能奏效。例如，想象一个盒子，它的前脸坐在原点，背面朝下Z轴。这是一张图片：

我道歉对于不好的手写，但这应该没有任何意义。正如你所看到的，我交叉v和u得到正向指向正z轴。但是，如果我使用相同的计算来计算背面的法线，那么很显然，法线将是一个指向该形状的矢量。结果是我有不准确的法线来计算光线的亮度。我希望法线在任何时候都能远离模型。

我知道有一种更好的方法来计算正常值，但我不知道它是什么是。任何人都可以向我建议另一种算法来计算可以摆脱这个问题的正常吗？如果不是，则必须有方法来检查法线是否面向对象/模型内部。如果是这样，那么你可以在答案中提出它，并在那里找到解释，因为我很乐意直观地了解这些方法的工作原理。

解决方案

大多数软件包遵循可配置的循环顺序用于三角形索引 - 顺时针或逆时针。因此，它们导出的所有网格都具有自定义排序，并且只要程序使用相同的约定，就不必担心。

---

话虽如此，我想你想知道在索引排序不一致的假设（？）情况下要做什么。

一种方法我们可以使用 ray-intersection 。重要的定理是，一个射线源于网格外的源只会与网格相交偶数次，如果在里面，则奇数。

<要做到这一点，我们可以做到以下几点：

• 使用上述交叉产品计算正常（并对其进行归一化） => N


• 取三角形上的任意点（最好是中点）
  
• 增量这一点沿着正常的一些小的epsilon值（取决于你的浮点格式和模型的大小 - 我会说 1e-4 为single和 1e-8 用于双精度）=> P


• 相交这条射线在网格中具有所有三角形（一个很好的算法是Möller-Trumbore ）


• 如果交叉点的数量是偶数，那么射线从网格外面开始;这意味着来自网格的正常点向外（因为您从表面上的点增加了它的源）。 - 当然，反之亦然。
  

---

）digression ：对上面的一个幼稚的方法，循环遍历网格中的所有三角形，将是 O（n） - 因此整个过程将会有二次时间复杂度。对于〜20个三角形（例如一个盒子）的 小网格，这是非常好的，但对于任何更大的三角形都不是理想选择！您可以使用空间细分技术来降低这个相交步骤的成本：

• KD trees / Octrees ：这些要求 O（n log n）（对于最佳算法，即 - 参见 Ingo Wald 的论文）来构建，但交叉点保证为 O（ log n）如果正确完成。总体复杂性将会是 O（n log n），这几乎是您可以获得的最好的结果。


• 网格：这简单地将搜索空间和三角形分割成较小的框。构造是 O（n）并且更高效的内存。相交时间仍然 O（n），但常数因子比天真方法小很多

I am trying to create an algorithm that calculate the normals of a model/ mesh. People have been telling me to use the cross products between the two vectors which at first seem like a good idea until I discovered that it might not always work. For instance just imagine a box with its front face sitting at the origin and its back face down the Z axis. Here is an image:

I do apologize for bad hand writing but that shouldn't be of any significance. As you can see,I cross v and u to get the normal pointing toward the positive z axis. However, If I use that same calculation to calculate the normal for the back face then obviously the normal will then be a vector directing inside the shape. The result is that I have inaccurate normals to calculate the brightness of a light. I want the normal to be facing away from the model at all time.

I know there gotta be a better way to calculate the normal but I don't know what it is. Can anyone suggests to me another algorithm to calculate the normal that would get rid of this problem? If not then there has to be a way to check whether or not a normal is facing inside the object / model. If so then can you suggests it in the answer and where I would find an explanation about it because I would love to have an intuition on how these methodologies work.

解决方案

Most software packages obey a configurable cyclic ordering for triangle indices - clockwise or anti-clockwise. Thus all meshes they export have self-consistent ordering, and as long as your program uses the same convention, you should have nothing to worry about.

---

Having said that, I imagine you want to know what to do in the hypothetical (?) situation where the index ordering is inconsistent.

One method we could use is ray-intersection. The important theorem is that a ray with its source outside the mesh will only intersect the mesh an even number of times, and if inside, odd.

To do this, we can do the following:

• Calculate the "normal" using the cross product as above (and normalize it) => N
• Take any point on the triangle (preferably the midpoint)
• Increment this point along the normal by some small epsilon value (depends on your floating point format and size of model - I'd say 1e-4 for single and 1e-8 for double precision) => P
• Intersect this ray [dir = N, src = P] with all triangles in the mesh (a good algorithm for this would be Möller–Trumbore)
• If the number of intersections is even, then the ray started from outside of the mesh; this means that the normal points outwards from the mesh (because you incremented its source from a point on the surface). - and of course, vice versa.

---

Minor (-ish ?) digression: a naive approach to the above, of looping through all triangles in the mesh, would be O(n) - and hence the whole procedure would have quadratic time complexity. This is perfectly fine for very small meshes of ~20 triangles (e.g. a box), but not ideal for any larger!

You can use spatial sub-division techniques to lower the cost of this intersection step:

• K-D trees / Octrees: These require O(n log n) (for the best algorithm, that is - see Ingo Wald's paper) to construct, but intersections are guaranteed to be O(log n) if done properly. The overall complexity would then be O(n log n), which is pretty much the best you can get
• Grid: This simply partitions the search space and triangles into smaller boxes. Construction is O(n) and much more memory-efficient. Intersection time is still O(n), but the constant factor is much smaller than that of the naive approach.

这篇关于如何计算一个盒子的法线？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！