Math/Geometry Help

Given a cube defined by two x-y-z points, how can I determine if another x-y-z point is within that area?

Assuming the cube is defined by any 2 diametrically opposite points, point p will be inside the cube if each of the x, y and z components are inbetween the relevant x, y and z components of the 2 corners. You will probably want to make sure that the actual corners used (of the 8 on a cube) don't matter, as long as they're opposite.

integer inside_cube (vector corner1, vector corner2, vector test_point)
{
    if (test_point.x <corner1.x && test_point.x <corner2.x)
        return FALSE;

    if (test_point.x >corner1.x && test_point.x >corner2.x)
        return FALSE;

    if (test_point.y <corner1.y && test_point.y <corner2.y)
        return FALSE;

    if (test_point.y >corner1.y && test_point.y >corner2.y)
        return FALSE;

    if (test_point.z <corner1.z && test_point.z <corner2.z)
        return FALSE;

    if (test_point.z >corner1.z && test_point.z >corner2.z)
        return FALSE;

    return TRUE;

}

should do it. There's lots of opportunity to optimise that by the way, I wanted to try and make it clear what it's doing.

you just need to test that the desired point, xt,yt,zt is between your extremes x1,y1,z1 and x2,y2,z2.

if (x1<=xt<=x2 or x2<=xt<=x1) and (y1<=yt<=y2 or y2<=yt<=y1) and (z1<=zt<=z2 or z2<=zt<=z1)

then you're within your bounding box.

So, turning that into code, instead of running two test for each component we'll find the reverse the order of variables where required.

vector test = <0,0,0>;
vector bound1 = <0,0,0>;
vector bound2 = <0,0,0>;

float x1 = bound1.x;
float x2 = bound2.x;
if (x1 > x2)
{
x2 = x1;
x1 = bound2.x;
}
if ((x1 <= test.x) && (test.x <= x2))
{
float y1 = bound1.y;
float y2 = bound2.y;
if (y1 > y2)
{
y2 = y1;
y1 = bound2.y;
}
if ((y1 <= test.y) && (test.y <= y2))
{
float z1 = bound1.z;
float z2 = bound2.z;
if (z1 > z2)
{
z2 = z1;
z1 = bound2.z;
}
if ((z1 <= test.z) && (test.z <= z2))
{
// Within bounds
}}}

Thanks, Nand. I was thinking there might be some mathematical formula, but your approach works.

gotta be an easier way....

what about
EDIT: Corrected per Deanna's post below =)

vector gPosition
vector gBOUNDS_MAX //-- end corner
vector gBOUNDS_MIN //-- origin corner

vector vTempA = gBOUNDS_MAX - gPosition;
vector vTempB = gPosition - gBONDS_MIN;

IS_INSIDE = FALSE;
if (vTempA.x * vTempB.x > 0){
if (vTempA.y * vTempB.y > 0){
if (vTempA.z * vTempB.z > 0){
IS_INSIDE = TRUE;
}}}

tested and works.

you can just as easily test IS_OUTSIDE by changeing > to < add = to include the boundry layer

I can hear your voice now..."Why would I *ever* need this geometry stuff in real life???"

for a spherical "area" you could use its center coordinates and llVectDist()

to get the radius.

The * operator between two vectors means to calculate the dot product, which is a float, not a vector. Were you thinking instead of a vector resulting from direct multiplication of the corresponding components? ( < v1.x * v2.x, v1.y * v2.y, v1.z * v2.z > ).

caught me sleeping... thank you, and yes.... essentiallly the idea is to simplfy the test, so that each direction test is + or -, instead of < or >... so that multiplying the results, if you recieve a 0 (surface) or negative (out of bound) it's not inside that dimmension....

editing the code now...

PS I'm curious how dot product would work... my math is weak especially in vectors... it's been a long time

vector C1 = <0,0,0>;
vector C2 = <10,10,10>;
vector Q1 = <5,5,10>;

integer InTheBox(vector Q)
{
integer Hit = FALSE;
if ((C1.x <= Q.x) && (Q.x <= C2.x))
{
if ((C1.y <= Q.y) && (Q.y <= C2.y))
{
if ((C1.y <= Q.y) && (Q.y <= C2.y))
{
Hit = TRUE;
}
}
}
return Hit;
}


and somewhere in a state...

if (InTheBox(Q1) == TRUE)
{
llOwnerSay("We gots something in da box";
}
else
{
llOwnerSay("Nope. Dis is not inside da box!";
}

Thanks, Void and Deanna. That is a cleaner solution. Thanks for the response, Squirrel, but I need it to be a cube, not a sphere.

Two end points does not define a cube, it defines a set of cubes. You need to add a rotation value to get a specific cube.

huh?
computes space:
var x defines a line...
add y to define a square
add z to define a cube


given a start point of 0 on each axis,
and an end point of 255

that defines a sim (actually z can be MUCH bigger, but we're simplifying)

rez box with center @ 128,128,128, and size of <2,2,2>

any thing between <127,127,127> and <129,129,129> on ALL 3 axis, is in the cube.... so those two sets define the cube

now technically this area descibes a rectangular space... but since all the axis have the same offset (2) it's cubic

you can even simplify by geting an origin point, and adding a size metric... for instance, <127,127,127> and <2,2,2>

heavens what would you do with a rotation?!?

EDIT: ok, I see what you are meaning.... non grid alined (as ralph pointed out below) .... well the OP did place the assumption at grid aligned (a zero_rotation cube is aligned, and therefore only needs origin and oppposite, corners to define) I'll leave the description in there though.... as it led to my next post

Well, I imagine what Lee is talking about is that you can rotate the cube between those points. Imagine a cube with pins at the defined corners, now spin it, rotating around the axis connecting the diagonal corners.

However, the assumption in this entire discussion seems to be that the cubes are aligned with the grid.

thanks to the exercise above I thought of a better IS_INSIDE function

vector gCUBE_CENTER = //--cubes location
vector gCUBE_SIZE = //-- cubes size
vector gTEST_POS = //-- point to test

vector vTemp = gTEST_POS - gCUBE_CENTER;

IS_INSIDE = FALSE;
if ( llFabs( vTemp.x ) < (.5 * gCUBE_SIZE.x){
if ( llFabs( vTemp.x ) < (.5 * gCUBE_SIZE.y){
if ( llFabs( vTemp.x ) < (.5 * gCUBE_SIZE.z){
IS_INSIDE = FALSE;
}}}

of course it's all moot if the cube size is 10m or less since volume detect would work just as well, and faster I imagine

Lee: Good point. Rotation is not a concern in this case, however.

Void: this is an arbitrary space, defined by the points. I want the user to select two points, then find out if an object, which is relaying its position, is within that space. Thus, I don't know center or size.

Unfortunately, your earlier formula won't work either, as the points can be set arbitrarily; thus there's no assurance that P2 is in a positive direction from P1 on any or all axes. That is, X1 may or may not be less than X2, etc.

Hmm. Time to go stare at my script some more.

You need a Between() function. it takes 3 values, and returns true if the first is between the other two. Then you can write

if( between(xt,x1,x2) && between( yt, y1, y2) && between( zt, z1,z2) )
{
/// t is in the box.
}

This assumes that the box is lined up perfectly with world/sim coordinates.

The between() function can deal with the problems of ordering of point 1 and point 2.

integer between( float a,float b,float c)
{
return b<a && a<c || c<a && a<b ;
}

Do you need to know if the object is entirely inside the cube? Or just that the center of the object is in the cube? Or if any part of the object is inside the cube.

By the way, this is the kind of problem that the SL physics engine has to solve about 8 bazillion times per second. Every time yo bump into a wall or a chair, it is doing this kind of calculation.

See a good 3D graphics book for more details and optimal code, or google for it. Like this one...

http://www.realtimerendering.com/int/

Thanks, Lee. I guess I was hoping there'd be some neat, tidy mathematical formula that would do it, but your solution looks good.

And yes, it just needs to know if the center is within the space, hence the single coordinate. God help me if I had to do it for the whole bounding box!

Note, the expression in the function must be parenthesized:

return (b<=a && a<=c) || (c<=a && a<=b);

Apparently, || has higher precedence than &&. This expression evaluates as FALSE:

(TRUE && TRUE || FALSE && FALSE)

as it gets reduced to:

(TRUE && TRUE && FALSE)

Oh no, this isn't good! Boolean operator precedence is inconsistent!

I ran into this when I decided to make one long expression, rather than using a function:

if (
(vecPoint1.x <= vecPos.x && vecPos.x <= vecPoint2.x) || (vecPoint2.x <= vecPos.x && vecPos.x <= vecPoint1.x)
&& (vecPoint1.y <= vecPos.y && vecPos.y <= vecPoint2.y) || (vecPoint2.y <= vecPos.y && vecPos.y <= vecPoint1.y)
&& (vecPoint1.z <= vecPos.z && vecPos.z <= vecPoint2.z) || (vecPoint2.z <= vecPos.z && vecPos.z <= vecPoint1.z)
) { // inside the space }

This evaluates TRUE for both the TRUE and FALSE cases, and only worked when I further parenthesized each axis component:

((vecPoint1.x <= vecPos.x && vecPos.x <= vecPoint2.x) || (vecPoint2.x <= vecPos.x && vecPos.x <= vecPoint1.x))
&& ((vecPoint1.y <= vecPos.y && vecPos.y <= vecPoint2.y) || (vecPoint2.y <= vecPos.y && vecPos.y <= vecPoint1.y))
&& ((vecPoint1.z <= vecPos.z && vecPos.z <= vecPoint2.z) || (vecPoint2.z <= vecPos.z && vecPos.z <= vecPoint1.z))

I've filed a bug report on it: http://jira.secondlife.com/browse/SVC-779 I went over it pretty thoroughly, but if someone could check my work, I'd appreciate it.

Could || and && have equal precedence?

BTW, if you pre-sort the coordinates of the points such that P1 < P2 for all three axes, you can halve the number of comparisons, and you won't need any ||'s. E.g. (UNTESTED CODE)

if ( p1.x < t.x && t.x < p2.x
&& p1.y < t.y && t.y < p2.y
&& p1.z < t.z && t.z < p2.z ) {
...
}

> Could || and && have equal precedence?

Hmm, it could be. If I evaluate the expressions I used in the bug report using equal precedence for the operators, it does give the same result. I've just never heard of equal precedence of boolean operators! It sure would be nice to have some official documentation.

> BTW, if you pre-sort the coordinates of the points such that P1 < P2 for all three
> axes, you can halve the number of comparisons, and you won't need any ||'s

I'm not sure what you mean. I can't swap axis values between the points, or they won't be the same points.

For example, if the original points are q1=<0,7,5> and q2=<3,3,3>, then use p1=<0,3,3> and p2=<3,7,5> instead. They will indeed be different points than originally entered, but they are still opposite corners of the same box.

heh actually the problem of arbitray points is easy to solve....

if origin > end, swap
continue as normal