Does anyone has an algorithm as to how to verify the presence of a point inside or on the surface of hexahedron. I have the following data 1. Coordinates of the point 2. coordinates of the vertices of hexahedron. Regards

I don't remember exactly, but maybe this helps you to find the solution.

I think you have to do that by comparing volumes.

If your hexahedron has the corners A,B,C,D, E,F,G,H (with E above A) and your point is at point P you may compute the volume of all piramides: PABCD, PCDHG, PDAEH, PABFE, PCBFG, PEFGH and sum them.

If this happens to be equal to the volume of the hexahedron, P must be inside, if it happens to be bigger than the volume of the hexa P must be outside.

Maybe someone can give you a more general formula with vector products that actually compute the same. These must then be made from P to some triangular surface, like ABC, BCD, etc.

Anyway, it may not be the exact general solution, but I think it can be done in this way.

The problem would be calculating the volume of irregular hexahedron. First place i need to map that to a regular geometry and then calculate the volume, which will not give me an exact volume but an approximate volume. I guess this idea will work for a regular shaped geometry like cube or so but becomes complicated for irregular shaped geometries.

No, it should work for ANY geometry and you don't need to do any strange mapping or whasoever (if not I would never do it)

If you divide every side of your hexa into two triangles and calculate the volume of the paralelpiped shape, the volume of the pyramide, with a triangular shape, should be something like (1/6)*det(matrix(v1,v2,v3)) (see wolfram web page) where v1, v2 and v3 go from p to point 1,2 and 3 from your triangle. Actually with the determinant you're doing a dot and a vector product.

So you could even do this for a whole aeroplane.

I guess gama's point was that the tetrahedron method is not necessarily exact. If you triangulate an arbitrary quadrilateral side A-B-C-D of the hexahedron, you are assuming it is piece-wise planar (consisting of two triangles), which doesn't have to be the case.

Anyway, that method will be good enough for most applications (i.e. if the hexahedron is not too irregular). Accuracy will be a concern if the point is very close to a surface or right on the surface.

Then again, you can always define your element as having a piece-wise planar surface (a quadrilateral surface is not uniquely described by four points). Just make sure the surface definition is consistent between neighboring elements. So, triangulation may well be exact, if you define it that way.

Calculate 2 volumes of tetrahedron: Vol1=det|v1,v2,v3|. Then calculate vilumes of tetrahedron through the desired point (Vol2) and other points. CMP. If Vol1<Vol2, then it's outside.

I have a different idea. You can transform the general hexahedron to a standard hex ( e.g. -1<=x,y,z<=1 ). Then apply this transformation to the point. If its transformed coordinates are between -1 and 1 then the point belongs to the hexahedron.

I hope I helped.