[fearAR]

Ok, my problem is the following, I can't found the way to know if a point is inside a cube defined by 8 points ( each corner is a point ), at the same time the cube is conformed by 6 faces, and each face contains 2 meshes.

I can't use the verification through sizes, because the cube has the property of turn in its euclidean axis, pitch/yaw/roll.

Therefore it isn't convenient to me, as there are cases where the points is outside the cube, and it will return me a wrong result, like it is inside.

For solve this problem, I'm using the way "intersection straight/plane", in fact it isn't a straight, it is a segment, which has a start and an end. Anyway, the rules are the following:

* If the straight cut the cube's faces in an odd number of times, it implies that the final point is inside the cube.

* If the straight cut the cube's faces in an even number of times, it implies that the final point crossed the cube and continued.

* If the straight didn't cut any face, it never passes throw the cube, therefore it is discarded.

Illustrative picture:
[IMG]http://img717.**************/img717/7564/cuboy.png[/IMG]

For doing this I need a calculation, where I obtain the normal vector to the plane, and then, I clear it.

For give an example I guide myself with this video, but It doesn't work well, or I didn't applied it well.
http://www.youtube.com/watch?v=3pj3vwpeFro

Finishing it, I'm giving you the function that I recreated, and the determination of the calculation.

U = direction vector ( End - Start )
Xo, Yo, Zo = starting vector
a,b,c = normal vector to the plane

aX + bY + cZ + D = 0

Vo = Starting vector
U = Direction vector
t = Direction vector's scalar
X, Y, Z = Vo + U*t

Replacing...

a * ( Xo + Ux * t ) + b * ( Yo + Uy * t ) + c * ( Zo + Uz * t ) + D = 0

Separating the terms...

aXo + aUxt + bYo + bUyt + cZo + cUzt + D = 0

Move the values with t to the other hand.

aXo + bYo + cZo + D = -( aUxt ) -( bUyt ) - ( cUzt )

aXo + bYo + cZo + D = t( -aUx - bUy - cUz )

t = ( aXo + bYo + cZo + D ) / ( -aUx - bUy - cUz )

In fact, in programming language...

PHP Code:

/* I go around the bucle, and takes the corners and his 2 adjacent points for shape the plane */

/*And then I apply this results to the following STOCK:*/

stock intersection_lineplane( const Float:fLinePoints[ 2 ][ 3 ], Float:fPlanePoints[ 3 ][ 3 ], &Float:d, &Float:t )
{
    new Float:f_vDirection[ 3 ], Float:f_vPlane[ 2 ][ 3 ], Float:f_vNormal[ 3 ];
    
    f_vDirection[ 0 ] = fLinePoints[ 1 ][ 0 ] - fLinePoints[ 0 ][ 0 ];
    f_vDirection[ 1 ] = fLinePoints[ 1 ][ 1 ] - fLinePoints[ 0 ][ 1 ];
    f_vDirection[ 2 ] = fLinePoints[ 1 ][ 2 ] - fLinePoints[ 0 ][ 2 ];
    
    f_vPlane[ 0 ][ 0 ] = fPlanePoints[ 0 ][ 0 ] - fPlanePoints[ 1 ][ 0 ];
    f_vPlane[ 0 ][ 1 ] = fPlanePoints[ 0 ][ 1 ] - fPlanePoints[ 1 ][ 1 ];
    f_vPlane[ 0 ][ 2 ] = fPlanePoints[ 0 ][ 2 ] - fPlanePoints[ 1 ][ 2 ];
    
    f_vPlane[ 1 ][ 0 ] = fPlanePoints[ 2 ][ 0 ] - fPlanePoints[ 1 ][ 0 ];
    f_vPlane[ 1 ][ 1 ] = fPlanePoints[ 2 ][ 1 ] - fPlanePoints[ 1 ][ 1 ];
    f_vPlane[ 1 ][ 2 ] = fPlanePoints[ 2 ][ 2 ] - fPlanePoints[ 1 ][ 2 ];
    
    f_vNormal[ 0 ] = ( f_vPlane[ 0 ][ 1 ] * f_vPlane[ 1 ][ 2 ] ) - ( f_vPlane[ 0 ][ 2 ] * f_vPlane[ 1 ][ 1 ] ); 
    f_vNormal[ 1 ] = -1 * ( ( f_vPlane[ 0 ][ 0 ] * f_vPlane[ 1 ][ 2 ] ) - ( f_vPlane[ 0 ][ 2 ] * f_vPlane[ 1 ][ 0 ] ) ); 
    f_vNormal[ 2 ] = ( f_vPlane[ 0 ][ 0 ] * f_vPlane[ 1 ][ 1 ] ) - ( f_vPlane[ 0 ][ 1 ] * f_vPlane[ 1 ][ 0 ] ); 
        
    d =     - ( f_vNormal[ 0 ] * fPlanePoints[ 0 ][ 0 ] )      
        - ( f_vNormal[ 1 ] * fPlanePoints[ 0 ][ 1 ] )     
        - ( f_vNormal[ 2 ] * fPlanePoints[ 0 ][ 2 ] );
                    
    t =     ( ( f_vNormal[ 0 ] * fLinePoints[ 0 ][ 0 ] ) + ( f_vNormal[ 1 ] * fLinePoints[ 0 ][ 1 ] ) + ( f_vNormal[ 2 ] * fLinePoints[ 0 ][ 2 ] ) + d ) 
        / ( - ( f_vNormal[ 0 ] * f_vDirection[ 0 ] ) - ( f_vNormal[ 1 ] * f_vDirection[ 1 ] ) - ( f_vNormal[ 2 ] * f_vDirection[ 2 ] ) );
    
        /* This conditional is to know if the results is in the range of the segment and now the straight */
    if( 0.0 < t < 1.0 ) return 1;
    
    return 0;
} 


Greetings! I expect for your replies.

PD: the calculation of the normal vector ( cross product ) to the plane is perfect, because I represented it with a Temp Entity TE_BEAMPOINTS, and it is perfect.
The problem can proceed from D to T, and I can't found the solution.

[AngeIII]

just for more information to sum up all of your said:
you have three vectors of the BOX
and you have X,Y,Z coordinates of point, and you want to know if this point is inside BOX (including border-vectors)?



or you have three vectors of BOX and one other vector, and you want to know if the other vectors have intersection with BOX? but in this case point can be outside too and answer will be true.

PHP Code:

stock intersection_lineplane( const Float:flp[ 2 ][ 3 ], Float:fpp[ 3 ][ 3 ]/*, &Float:d, &Float:t*/ )
{
    new Float:vd[ 3 ], Float:pv[ 2 ][ 3 ], Float:nv[ 3 ];
    
    vd[ 0 ] = flp[ 1 ][ 0 ] - flp[ 0 ][ 0 ];
    vd[ 1 ] = flp[ 1 ][ 1 ] - flp[ 0 ][ 1 ];
    vd[ 2 ] = flp[ 1 ][ 2 ] - flp[ 0 ][ 2 ];
    
    pv[ 0 ][ 0 ] = fpp[ 0 ][ 0 ] - fpp[ 1 ][ 0 ];
    pv[ 0 ][ 1 ] = fpp[ 0 ][ 1 ] - fpp[ 1 ][ 1 ];
    pv[ 0 ][ 2 ] = fpp[ 0 ][ 2 ] - fpp[ 1 ][ 2 ];
    
    pv[ 1 ][ 0 ] = fpp[ 2 ][ 0 ] - fpp[ 1 ][ 0 ];
    pv[ 1 ][ 1 ] = fpp[ 2 ][ 1 ] - fpp[ 1 ][ 1 ];
    pv[ 1 ][ 2 ] = fpp[ 2 ][ 2 ] - fpp[ 1 ][ 2 ];
    
    /* correct */
    nv[ 0 ] = ( pv[ 0 ][ 1 ] * pv[ 1 ][ 2 ] ) - ( pv[ 0 ][ 2 ] * pv[ 1 ][ 1 ] ); 
    nv[ 1 ] = -1 * ( ( pv[ 0 ][ 0 ] * pv[ 1 ][ 2 ] ) - ( pv[ 0 ][ 2 ] * pv[ 1 ][ 0 ] ) ); 
    nv[ 2 ] = ( pv[ 0 ][ 0 ] * pv[ 1 ][ 1 ] ) - ( pv[ 0 ][ 1 ] * pv[ 1 ][ 0 ] ); 
        
    /* in this stage you have normalvector(A;B;C) FOR PLANE, direction vector(l;m;n) FOR LINE, two points X,Y,Z,  two plane vectors, three points of plane with [x,y,z] 
    * and your task to find if LINE is intersection WITH PLANE. (crossing)
    * way to do this: 
    * LINE and PLANE intersect if scalar sumproduct of normalvector and directionvector not equals to 0.
    * nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2] != 0   ->  direction and normal vector not perpendiculars => line intersect the plane 
    * if  nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2] == 0, And nv[0]*flp[0][0]+nv[1]*flp[0][1]+nv[2]*flp[0][2]=0  -> line is inside plane and point flp[0] is inside plane. direction vector and normal vector are perpendiculars 
    * if  nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2] == 0, And nv[0]*flp[0][0]+nv[1]*flp[0][1]+nv[2]*flp[0][2]!=0 -> line is parallel plane and point flp[0] is outside plane. direction vector and normal vector are perpendiculars 
    */

    /* if you need only INTERSECTION  just use this: */
    if((nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2]) != 0) return 1;

    /* if you need intersection and also if line is inside use this:*/
   //if( (nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2]) != 0) || ( (nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2]) == 0 && (nv[0]*flp[0][0]+nv[1]*flp[0][1]+nv[2]*flp[0][2])==0) ) return 1;


    return 0;
} 


this is the way how to find if line is intersect with plane.
in case if you need to find D (for plane formula) use your:
d = - ( f_vNormal[ 0 ] * fPlanePoints[ 0 ][ 0 ] )
- ( f_vNormal[ 1 ] * fPlanePoints[ 0 ][ 1 ] )
- ( f_vNormal[ 2 ] * fPlanePoints[ 0 ][ 2 ] );
it is correct.
but your t also correct but in this case you use one point in two cases and if you put all expression in one line it will be something like this:
Ax+By+Cz+D=0
where
A:B:C -> normal vector:
nv[ 0 ] = ( pv[ 0 ][ 1 ] * pv[ 1 ][ 2 ] ) - ( pv[ 0 ][ 2 ] * pv[ 1 ][ 1 ] );
nv[ 1 ] = -1 * ( ( pv[ 0 ][ 0 ] * pv[ 1 ][ 2 ] ) - ( pv[ 0 ][ 2 ] * pv[ 1 ][ 0 ] ) );
nv[ 2 ] = ( pv[ 0 ][ 0 ] * pv[ 1 ][ 1 ] ) - ( pv[ 0 ][ 1 ] * pv[ 1 ][ 0 ] );
and x,y,z is: Xo,Yo,Zo.
D=-A*Xo-B*Yo-C*Zo

A* ( Xo + Ux * t ) + B * ( Yo + Uy * t ) + C* ( Zo + Uz * t )-A*Xo-B*Yo-C*Zo=0
A*Xo+A*Ux*t+B*Yo+B*Uy*t+C*Zo+C*Uz*t-A*Xo-B*Yo-C*Zo=0
A*Ux*t+B*Uy*t+C*Uz*t=0
t(A*Ux+B*Uy+C*Uz)=0
so your t=0 any way.

[Sylwester]

You can rotate the cube (2 opposite corners are enough), so yaw, pitch, roll are all 0, and rotate the point (same center and angles as in cube rotation). Then you can use the verification through sizes.

[fearAR]

@AngeIII

I have a vector that is the origin of the box, the center...
Then, I have other eight points that are the offset of the corners in relation with the origin.

Example:

PHP Code:


new Float:fCube_origin[ 128 ][ 3 ]; // This is the origin ( 128, is a number for max cubes )

new Float:fCube_default[ Z_AXIS ][ 4 ][ 3 ] = /* This var saves the offset of the 8 corners
i said eight because Z_AXIS is UPPER and LOWER, so, its real value is 2 */
{
    {
        { -5.0, -5.0, -5.0 },
        { 5.0, -5.0, -5.0 },
        { 5.0, 5.0, -5.0 },
        { -5.0, 5.0, -5.0 }
    },
    {
        { -5.0, -5.0, 5.0 },
        { 5.0, -5.0, 5.0 },
        { 5.0, 5.0, 5.0 },
        { -5.0, 5.0, 5.0 }
    }
}; 


The values of each corner can change if I increase or decrease the value of pitch yaw roll, or if a change the value of height, width or profundity.

The origin of the cube doesnt change the offsets because the offset is in relation with this origin.

Then I go over the corners taking them like a face ( 3 points ) for shape a plane, so i have to make a loop for 2 planes per cube face.

I checked if I was taking wrong the values or making a mistake with the control of the origins, but it is ok because I drew each face taking 3 corners per face.

But the calculation didn't work fine, it returns me like the aiming origin is crossing the planes everytime.

I need only to know if the segment/line from player origin, to where he is aiming, is crossing each plane, so with this information I can solve the problem knowing if it crossed a odd or even number of planes.

@Sylwester.

I was thinking about that, that will work, but I want other way to do this before doing that.
If there is no solution I'll try doing that.

Greetings.

Edit:

I found the solution!

With the data obtained with the first equation, I use these two STOCK's for verify if the collision point in inside 3 vertex, so, if it is, the line in colliding with one box's face, then if the number of faces that collides with the line is an odd number, the end point is inside the box, else the end point is outside and it continued after colliding with the box.
But if the number of collisions is 0, the line never collisioned with the cube.

PHP Code:

stock Float:dot( Float:u[ 3 ], Float:v[ 3 ] )
{    
    return ( u[ 0 ] * v[ 0 ] + u[ 1 ] * v[ 1 ] + u[ 2 ] * v[ 2 ] );
}

stock in_triangle( Float:A[ 3 ], Float:B[ 3 ], Float:C[ 3 ], Float:P[ 3 ] )
{
    new Float:v0[ 3 ], Float:v1[ 3 ], Float:v2[ 3 ];
    
    xs_vec_sub( C, A, v0 );
    xs_vec_sub( B, A, v1 );
    xs_vec_sub( P, A, v2 );

    // Compute dot products
    new Float:dot00 = dot(v0, v0)
    new Float:dot01 = dot(v0, v1)
    new Float:dot02 = dot(v0, v2)
    new Float:dot11 = dot(v1, v1)
    new Float:dot12 = dot(v1, v2)

    // Compute barycentric coordinates
    new Float:invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
    new Float:u = (dot11 * dot02 - dot01 * dot12) * invDenom
    new Float:v = (dot00 * dot12 - dot01 * dot02) * invDenom

    // Check if point is in triangle
    return (u >= 0) && (v >= 0) && (u + v < 1);
} 


The STOCK is based in a C# function that uses the Baricentric Coordinates.

Bye.

[AngeIII]

brr.. more efficiten way something like this:

PHP Code:

stock intersection_lineplane( const Float:flp[ 2 ][ 3 ], Float:fpp[ 3 ][ 3 ]/*, &Float:d, &Float:t*/ )
{
    new Float:vd[ 3 ], Float:pv[ 2 ][ 3 ], Float:nv[ 3 ];
    
    vd[ 0 ] = flp[ 1 ][ 0 ] - flp[ 0 ][ 0 ];
    vd[ 1 ] = flp[ 1 ][ 1 ] - flp[ 0 ][ 1 ];
    vd[ 2 ] = flp[ 1 ][ 2 ] - flp[ 0 ][ 2 ];
    
    pv[ 0 ][ 0 ] = fpp[ 0 ][ 0 ] - fpp[ 1 ][ 0 ];
    pv[ 0 ][ 1 ] = fpp[ 0 ][ 1 ] - fpp[ 1 ][ 1 ];
    pv[ 0 ][ 2 ] = fpp[ 0 ][ 2 ] - fpp[ 1 ][ 2 ];
    
    pv[ 1 ][ 0 ] = fpp[ 2 ][ 0 ] - fpp[ 1 ][ 0 ];
    pv[ 1 ][ 1 ] = fpp[ 2 ][ 1 ] - fpp[ 1 ][ 1 ];
    pv[ 1 ][ 2 ] = fpp[ 2 ][ 2 ] - fpp[ 1 ][ 2 ];
    
    /* correct */
    nv[ 0 ] = ( pv[ 0 ][ 1 ] * pv[ 1 ][ 2 ] ) - ( pv[ 0 ][ 2 ] * pv[ 1 ][ 1 ] ); 
    nv[ 1 ] = -1 * ( ( pv[ 0 ][ 0 ] * pv[ 1 ][ 2 ] ) - ( pv[ 0 ][ 2 ] * pv[ 1 ][ 0 ] ) ); 
    nv[ 2 ] = ( pv[ 0 ][ 0 ] * pv[ 1 ][ 1 ] ) - ( pv[ 0 ][ 1 ] * pv[ 1 ][ 0 ] ); 
        
    /* in this stage you have normalvector(A;B;C) FOR PLANE, direction vector(l;m;n) FOR LINE, two points X,Y,Z,  two plane vectors, three points of plane with [x,y,z] 
    * and your task to find if LINE is intersection WITH PLANE. (crossing)
    * way to do this: 
    * LINE and PLANE intersect if scalar sumproduct of normalvector and directionvector not equals to 0.
    * nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2] != 0   ->  direction and normal vector not perpendiculars => line intersect the plane 
    * if  nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2] == 0, And nv[0]*flp[0][0]+nv[1]*flp[0][1]+nv[2]*flp[0][2]=0  -> line is inside plane and point flp[0] is inside plane. direction vector and normal vector are perpendiculars 
    * if  nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2] == 0, And nv[0]*flp[0][0]+nv[1]*flp[0][1]+nv[2]*flp[0][2]!=0 -> line is parallel plane and point flp[0] is outside plane. direction vector and normal vector are perpendiculars 
    */

    /* if you need only INTERSECTION  just use this: */
    if((nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2]) != 0)
    {
        // we have intersection with plane but whe also shoul check for ranges. this can be done if we found the intersection point coordiates and after that check the proections of upper or lower plane.
    // intersection coordinates
    /*
    * 1) To=(aXo+bYo+cZo+D)/(a*l+b*m+c*n)
    * 2) x=xo-lTo; y=yo-mTo; z=zo-nTo;
    
    */
    // we need D
    // for that we can use nv and some planepoint coordinates. e.g [0]
    new d=-nv[0]*fpp[0][0]-nv[1]*fpp[0][1]-nv[2]*fpp[0][2];
    // x0,y0,z0 it is some line point. flp[0] for example
    new Float:t=(nv[0]*flp[0][0]+nv[1]*flp[0][1]*nv[2]*flp[0][2]+d)/(nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2])
    new InterSectOrigin[2];
    InterSectOrigin[0]=floatround(fpp[0][0]-vd[0]*t);
    InterSectOrigin[1]=floatround(fpp[0][1]-vd[1]*t);
    //InterSectOrigin[2]=floatround(fpp[0][2]-vd[2]*t); // is not necessary cause we use only proection
    // last what you need -> check if intersection coordinates proection to upper or lower side is inside the interval
    //OnQuadre(p[4][2], v[2])
/*
something like this:
if your box have origins: 100 100 100
new Float:fCube_default[ Z_AXIS ][ 4 ][ 3 ] = 
{
    {
        { -5.0, -5.0, -5.0 },
        { 5.0, -5.0, -5.0 },
        { 5.0, 5.0, -5.0 },
        { -5.0, 5.0, -5.0 }
    },
    {
        { -5.0, -5.0, 5.0 },
        { 5.0, -5.0, 5.0 },
        { 5.0, 5.0, 5.0 },
        { -5.0, 5.0, 5.0 }
    }
}; 
so the up plane is Z=5
lower plane Z=-5

so
// z is not necessary, we use proection
new Box_lowerside[4][2] =
{
    {fCube_origin[cube][0]+fCube_default[1][0][0],fCube_origin[cube][1]+fCube_default[1][0][1]},
    {fCube_origin[cube][0]+fCube_default[1][1][0],fCube_origin[cube][1]+fCube_default[1][1][1]},
    {fCube_origin[cube][0]+fCube_default[1][2][0],fCube_origin[cube][1]+fCube_default[1][2][1]},,
    {fCube_origin[cube][0]+fCube_default[1][3][0],fCube_origin[cube][1]+fCube_default[1][3][1]}
    
}
*/
    if(OnQuadre(Box_lowerside,InterSectOrigin)) return 1;
    
    }

    /* if you need intersection and also if line is inside use this:*/
   //if( (nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2]) != 0) || ( (nv[0]*vd[0]+nv[1]*vd[1]+nv[2]*vd[2]) == 0 && (nv[0]*flp[0][0]+nv[1]*flp[0][1]+nv[2]*flp[0][2])==0) ) return 1;


    return 0;
}  

bool:OnTriangle(p1[2], p2[2], p3[2], p[2])
{
new a1 = p2[0] - p1[0];
new b1 = p2[1] - p1[1];
new a2 = p3[0] - p2[0];
new b2 = p3[1] - p2[1];
new a3 = p1[0] - p3[0];
new b3 = p1[1] - p3[1];

new bool:Z[3], bool:T[3];

if(((p[0]-p1[0])*b1 + (p1[1]-p[1])*a1) >= 0) Z[0] = true; else Z[0] = false;
if(((p[0]-p2[0])*b2 + (p2[1]-p[1])*a2) >= 0) Z[1] = true; else Z[1] = false;
if(((p[0]-p3[0])*b3 + (p3[1]-p[1])*a3) >= 0) Z[2] = true; else Z[2] = false;

if((-a3*b1 + b3*a1) >= 0) T[0] = true; else T[0] = false;
if((-a1*b2 + b1*a2) >= 0) T[1] = true; else T[1] = false;
if((-a2*b3 + b2*a3) >= 0) T[2] = true; else T[2] = false;

for(new i=0; i<3; i++)
    if(Z[i] != T[i]) return false;

return true;
}

bool:OnQuadre(p[4][2], v[2])
{
if(OnTriangle(p[0],p[1],p[2],v)) return true;
if(OnTriangle(p[0],p[2],p[3],v)) return true;
return false;
} 


and also your error:
X, Y, Z = Vo + U*t

really X,Y,Z = Vo-U*t
for your if. // see my T calculation