An object has been approximated by a lot of triangles. Given the vertex positions of these triangles, how can I compute the normal of these vertices which pointing outside of the object.
I know the cross-product of two edges gives the normal, but how can I know it's pointing towards the outside of the object.
On
Facing the same problem, I found the general solution here:
It is for 2-D but generalizes to 3-D as well. Also, it does not suffer from non-convexity.
The first step is the same as PolyMesh suggested. All the normals have to face the same direction. This can be done by fixing the normal of one face, and then traversing the triangles using BFS search and setting their normals the same as their neighbour which has already been visited using BFS.
The second step, however, is not only easier, but also works for both convex and non-convex geometries. Evaluate the sum $$ I = \sum_{i=1}^{N_\text{triangles}} x_i n_{xi} \text{Area}_i, $$ where $x_i$ is the x coordinate of each triangle midpoint, $n_{xi}$ is the x entry of the normal vector at the triangle midpoint, and $\text{Area}$ is the area of the triangle. The normals point outward iff I > 0, and they point inward otherwise. The reason is that $\int_\text{Area} xn_xdA = \int_\text{Area} yn_ydA = \text{Volume}$ iff normals are pointing outwards. This property can be proved using the divergence theorem.
For a convex object, add up all the vertices to get a center representation. Take the dot product of the normal you obtain with the vector joining the vertex to this center. If this is negative the normal is pointing outward. (For non-convex object this won't work though)