4

If all nodes of a polyhedron (may be non-convex) and their coordinates are known, the points of a face are given in order (anti-clockwise or clockwise around the outward normal), how do I obtain the outward normal vector of each face?

Here is a method for convex polyhedron: Computing face normals and winding

How about a general polyhedron that could be non-convex?

Y. Zhong
  • 33
  • 3
  • Without any research I'd guess the hard part is to calculate what vectors form a single face and not calculating the normal vector of a single face!? – xander Jan 04 '18 at 10:43
  • Possible duplicate of [How to calculate the normals of a box?](https://stackoverflow.com/questions/45603469/how-to-calculate-the-normals-of-a-box) – meowgoesthedog Jan 04 '18 at 14:13
  • @meowgoesthedog: Good find, but counting ray intersections (as suggested there) is quite a tricky computation, in my experience. – Joseph O'Rourke Jan 04 '18 at 18:13
  • @JosephO'Rourke true, but only if you intend to use an acceleration structure. A naive "loop through and check each" approach would be more or less trivial (since there are many code samples of Moller-Trumbore on the interwebs) – meowgoesthedog Jan 04 '18 at 21:11
  • @meowgoesthedog: One must be careful when the ray passes through a vertex, is collinear with an edge, coplanar with a face. Etc. Of course it can be done correctly. And there is existing code, you are right. – Joseph O'Rourke Jan 04 '18 at 21:16
  • If you have a manifold data structure where the faces can be extracted as a consistently anti-clockwise or clockwise sequence of edges, then this is a very well-studied problem. The classical solution is Newell's algorithm: https://www.khronos.org/opengl/wiki/Calculating_a_Surface_Normal – Gene Jan 12 '18 at 03:20

1 Answers1

2

Here is one method. Fix the orientation of one face F0 of your polyhedron P. You don't yet know if this is counterclockwise from the outside, so that the right-hand-rule gives an outward pointing normal from the cross product.

Now orient an adjacent face F1 to be compatible with F0's orientation, in that the shared edge is oriented → in F0 and ← in F1. Continue propagating the orientations of faces until every face of P is consistent with F0. So now all normals either point inward or all point outward.

Now compute the volume of P by summing signed tetrahedra volumes. The volume will be positive if all faces are oriented counterclockwise, and negative if all clockwise. If it comes out negative, reverse all face orientations.

Computing the signed volume is all over the web, including here: Computational Geometry in C.

Joseph O'Rourke
  • 4,346
  • 16
  • 25