Topic: How to know if a point is inside a hexahedron?

[SOFITO_SOFT]

Hello, all swamp people:
Assuming we have 8 points which are ordered vertices of a hexahedron ...style:

Code: [Select]

!           8----7
!          /|   /|
!         / 4--/-3
!        5----6 /
!        |/   |/
!        1----2

Anyone know if there is a quick way to know if the point is inside, outside or in a face? 
The method of analyzing the position of the point respect a each pair of oposed faces can be awfully slow.
Maybe adding spherical triangles from the point of each trio of vertices? 
Any input is welcome. 
Grettings.

[Lee Mac]

I would suggest retrieving the inward-pointing normal vector for each face, transform the point to be tested using trans to the coordinate system defined by each normal, and test for positive/negative or zero Z-Coord, all positive => point is inside.

eg:

Code: [Select]

(defun _pointaboveplane ( pt org normal )
  (< 0 (- (caddr (trans pt 0 normal)) (caddr (trans org 0 normal))))
)
Where 'pt' is the point to be tested, 'org' a point on the plane, and 'normal' the inward-point normal for the face.

[SOFITO_SOFT]

Hello all:
Lee: As always perfect ... and probably very quickly.
I had thought of using prior knowledge of the parallelepiped ...
Pre-calculate the centroid and from it, launching a "ray" to the point in question ... and see if the point lies between the 2 nearest intersection (one on each side of centroid ) with the 6 faces. Surely it is more confusing ... and slow 
Yours has the advantage that sometimes it can cut the loop ( for each face )  when the point is in a FACE  or is out ... no need to analyze the rest.
Is complex .... I must verify this for about 1E4 points in several "cubes" ... 
Thanks for your interest.
Greetings.

[SOFITO_SOFT]

Hello all.
A refinement of prior knowledge through the "cubes"  :
- calculate the minimum sphere that contains the 8 vertices, for each cube.
- calculate the envelope for each cube (Xmin Xmax Ymin ...)
And then
- A point discussed provided that its distance from the center of the sphere is equal to or less than the radius of it. (2 operations, distance calculation and comparison with radio)
- A point discussed whether their 3 coordinates are inside the envelope. (6 operations, comparison of X Y Z with Xmin Xmax Ymax  ...)
So I will have eliminated most of the 1e4 points for each 6, 8 o max 10 cubes and I could use the algorithm of "normal to 6 faces."
It contains no geometrical or computational barbarity. Right?
Greetings.

[SOFITO_SOFT]

Helo all:
0.01 seg for calculate the minimal sphere-bounday of each cube ( 8 vertices )....and I can begin eliminate 95% of the points for that cube (even iregular) 
Now...now the hard ... compare the normals to 6 faces and your address / direction ...

Greetings

[SOFITO_SOFT]

Hello everyone
More refinement on the first idea of Lee:
calculate the Cartesian equation of each face and make it unitaire.
The face is oriented out according to the situation of the centroid.
Solving the point in each equation we have 6 value quickly. The value tells us if the point is in the skin (0), outside (+) or inside (-). Analyzing the 6 values very quickly know the situation of the point on the 6 faces forming the hexahedron iregular!. the 6 faces can be any shape and be at any angle. It is only necessary to form a plane. It will be a step further handle warped faces
I send a Assistant coach and a simple base dwg to this process. The hexahedron has been outlined as a 3DPOLY (yellow) 8 vertices according to the scheme of the first post. Different red and green lines for training and 3 color point clouds according to 3 level  .
The LSP includes the algorithm of the minimum sphere that goes by 8 points, used to eliminate points quickly when you have to check thousands.
Everything is clearly for the better (Alpha version?).
I hope you find it useful.
A greeting from Madrid.

PS.:Different routines and sub-functions are downloaded from the forum and those of the authors. I just use them.