3D space

I have a problem which I dont know how to solve it. I have a close surface in 3D space that divides the space into two parts: inside and outside of the surface. The mesh is unstructured triangular mesh, one array of integers stores the three vertices belong to each of the triangles, I have another array of real numbers which have a positions of vertices. I wish to compute the unit normal vectors uniformly towards inside or outside for each of the triangles with minimum cost. I do not know how to reorganize the data in order to get the correct uniform in/outside normal vectors through the surface. what is the pseudo code to do that? how should I reorganize the data?

So I think you'll need to compute the vector normal by, for each triangle with points A, B and C, taking the cross product of (A-B)x(C-B). You probably already knew that though...

The tricky part is figuring out whether or not the resultant vector is outward or inward-facing. There is a forum post describing how to test if a voxel is inside or outside of a mesh (see link), but I think you can use a simplified strategy. For your normal vector calculate how many times a ray emanating from the triangle (where I'm not sure -- the corners?) intersects with any other triangles in the mesh. If that number is even, I think you have the outward normal vector. Otherwise, return -1*normal to get the outward normal.

No proof is offered though. Just a best guess. Worst case you could just use the voxel method described and test it on a point just barely next to the triangle in the direction of the surface normal.

There is also another forum post asking a similar question that may be of use: http://www.devmaster.net/forums/showthread.php?t=10030

the easiest way of encoding a face normal given your data structure is by the ordering of vertex ids: conventionally, if by looking at a triangle its verteces are ordered counter clockwise then its normal is directed towards you, and vice versa in the clockwise case.

now, if your mesh really satisfy the property of "dividing the space into two parts: inside and outside of the surface" ( and note that this is a global non trivial property; in particular, it's not sufficient that the surface has no "holes" because there exist non orientable closed two dimensional surfaces ), you should be able to choose such vertex orderings in such a way that given any two triangles sharing an edge, the vertex ids of the verteces of the edge have reversed ordering.

so, your algorithm could consist in 1) extracting the set of edges along with pointers to the pair of triangles sharing it and 2) for each edge check if edge vertex ordering are reversed; if this is the case, set a flag in both triangles "fixing" their orientation; otherwise, reverse any of them ( not having the flag set ). If any of these step is not possible then your surface doesn't satisfy the property of being orientable; otherwise, you'll end up with an oriented surface with normals all pointing outside or inside; in the latter case you simply reverse all triangle orderings simultaneously to get the desired normals ...

Hi,

for the non-orientable surface, you should look for "Klein Bottle". During my studying the books of Felix Klein have been one of my favourite. So I reccomend to read about higher geometry, a subject almost forgotten in these days.


GMarco