Geometric

Please vote for: https://jira.secondlife.com/browse/WEB-235 So that I can expand each function into deeper detail without the page starting to fail in readability. --Nexii Malthus 23:05, 24 October 2008 (UTC)

Geometric Library

Line Functions

Line Nearest Point
Calculates the vector from a point to the closest point on a line <lsl> vector gLXdV(vector O,vector D,vector A){ return (O-A)-((O-A)*D)*D;} </lsl> Input Description vector O Origin of Line vector D Direction of Line vector A Origin of Point Output Description return vector gLXdV Returns origin of closest point on Line to Point By Nexii Malthus

Line Nearest Point, Distance
Calculates distance of this vector, but faster on it's own <lsl> float gLXdZ(vector O,vector D,vector A){ vector k = ( A - O ) % D; return llSqrt( k * k );} </lsl> Input Description vector O Origin of Line vector D Direction of Line vector A Origin of Point Output Description return float gLXdZ Returns numerical distance from Line to Point By Nexii Malthus

Line Nearest Point, Nearest Point
Returns nearest point on line to given point <lsl> vector gLXnX(vector O,vector D,vector A){ return gLXdV(O,D,A) + A;} </lsl> Input Description vector O Origin of Line vector D Direction of Line vector A Origin of Point Output Description return vector gLXnX Returns nearest point on line given point Requirement function vector gLXdV(vector O,vector D,vector A) By Nexii Malthus

Line and Line, Vector
Shortest vector of two lines <lsl> vector gLLdV(vector O1,vector D1,vector O2,vector D2){ vector A = O2 - O1; vector B = D1 % D2; return B*( (A*B)/(B*B) );} </lsl> Input Description vector O1 Origin of Line 1 vector D1 Direction of Line 1 vector O2 Origin of Line 2 vector D2 Direction of Line 2 Output Description return vector gLLdV Returns shortest vector between the two lines By Nexii Malthus

Line and Line, Distance

Returns the distance between two lines <lsl> float gLLdZ(vector O1,vector D1,vector O2,vector D2){ vector A = D1%D2;float B = llVecMag(A);A = <A.x/B,A.y/B,A.z/B>; return (O2-O1) * A;} </lsl> Input Description vector O1 Origin of Line 1 vector D1 Direction of Line 1 vector O2 Origin of Line 2 vector D2 Direction of Line 2 Output Description return float gLLdZ Returns numerical distance between the two lines By Nexii Malthus

Line and Line, Nearest point

Closest point of two lines <lsl> vector gLLnX(vector O1,vector D1,vector O2,vector D2){ vector nO1 = < O1*D1, O1*D2, 0>; vector nO2 = < O2*D1, O2*D2, 0>; vector nD1 = < D1*D1, O1*D2, 0>; vector nD2 = < O2*D1, O2*D2, 0>; float t = ( nD2.x*nD1.y - nD1.x*nD2.y ); t = ( nD2.y*(nO1.x-nO2.x) - nD2.x*(nO1.y-nO2.y) ) / t; return O1 + D1*t;} </lsl> Input Description vector O1 Origin of Line 1 vector D1 Direction of Line 1 vector O2 Origin of Line 2 vector D2 Direction of Line 2 Output Description return vector gLLnX Returns closest point between the two lines By Nexii Malthus

Line and Line, intersection point

Computes intersection point of two lines, if there is any, else <-1,-1,-1> if none. <lsl> vector gLLxX( vector A, vector B, vector C, vector D ){ vector V = <-1,-1,-1>; if ( A == B || C == D ) return V; B -= A; C -= A; D -= A; float distAB = llSqrt( B.x*B.x + B.y*B.y ); float c = B.x / distAB;float s = B.y / distAB; float t = C.x * c + C.y * s; C.y = C.y * c - C.x * s; C.x = t; t = D.x * c + D.y * s; D.y = D.y * c - D.x * s; D.y = t; if( C.y == D.y ) return V; t = D.x + ( C.x - D.x ) * D.y / ( D.y - C.y ); return <A.x + t*c, A.y + t*s, A.y>;} </lsl> Input Description vector A Start of Line 1 vector B End of Line 1 vector C Start of Line 2 vector D End of Line 2 Output Description return vector gLLxX The intersection point of the two lines, else <-1,-1,-1> if none By Nexii Malthus

Line and Line, two nearest points along both lines

Two closest points of two lines on each line <lsl> vector X1;vector X2; gLLnnXX(vector O1,vector D1,vector O2,vector D2){ vector nO1 = < O1*D1, O1*D2, 0>; vector nO2 = < O2*D1, O2*D2, 0>; vector nD1 = < D1*D1, O1*D2, 0>; vector nD2 = < O2*D1, O2*D2, 0>; float t = ( nD2.x*nD1.y - nD1.x*nD2.y ); t = ( nD2.y*(nO1.x-nO2.x) - nD2.x*(nO1.y-nO2.y) ) / t; X1 = O1 + D1*t; X2 = X1 + nD1%nD2;} </lsl> Input Description vector O1 Origin of Line 1 vector D1 Direction of Line 1 vector O2 Origin of Line 2 vector D2 Direction of Line 2 Output Description vector X1 Closest point on line 1 to line 2 vector X2 Closest point on line 2 to line 1 Requirement global vector X1 global vector X2 By Nexii Malthus

Line and Line, two nearest points with vector and distance

Computes two closest points of two lines, vector and distance <lsl> vector X1;vector X2;vector V1;float Z1; gLLnnXXVZ(vector O1,vector D1,vector O2,vector D2){ vector nO1 = < O1*D1, O1*D2, 0>; vector nO2 = < O2*D1, O2*D2, 0>; vector nD1 = < D1*D1, O1*D2, 0>; vector nD2 = < O2*D1, O2*D2, 0>; float t = ( nD2.x*nD1.y - nD1.x*nD2.y ); t = ( nD2.y*(nO1.x-nO2.x) - nD2.x*(nO1.y-nO2.y) ) / t; X1 = O1 + D1*t; X2 = X1 + CP(nD1,nD2); V1 = nD1%nD2; Z1 = llVecMag(V1);} </lsl> Input Description vector O1 Origin of Line 1 vector D1 Direction of Line 1 vector O2 Origin of Line 2 vector D2 Direction of Line 2 Output Description vector X1 Closest point on line 1 to line 2 vector X2 Closest point on line 2 to line 1 vector V1 Direction vector of line 1 to line 2 float Z1 Numerical distance of line 1 to line 2 Requirement global vector X1 global vector X2 global vector V1 global float Z1 By Nexii Malthus

Plane Functions

Plane and Point, Distance
Finds distance of a point from a plane <lsl> float gPXdZ(vector Pn,float Pd,vector A){ return A * Pn + Pd;} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector A Origin of Point Output Description return float gPXdZ Returns Distance between plane and point By Nexii Malthus

Plane and Point, Vector
Finds vector that points from point to nearest on plane <lsl> vector gPXdV(vector Pn,float Pd,vector A){ return -(Pn * A + Pd)*Pn;} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector A Origin of Point Output Description return vector gPXdV Returns vector from point to closest point on plane By Nexii Malthus

Plane and Point, Nearest point
Finds closest point on plane given point <lsl> vector gPXnX(vector Pn,float Pd,vector A){ return A - (Pn * A + Pd) * Pn;} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector A Origin of Point Output Description return vector gPXnX Returns vector of a point from closest of point to plane By Nexii Malthus

Plane and Ray, Intersection Distance
Finds distance to intersection of plane along ray <lsl> float gPRxZ(vector Pn,float Pd,vector O,vector D){ return -((Pn*O+Pd)/(Pn*D));} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector O Origin of Ray vector D Direction of Ray Output Description return float gPRxZ Returns float distance of intersection between ray and plane By Nexii Malthus

Plane and Ray, Vector

Finds distance vector along a ray to a plane <lsl> vector gPRdV(vector Pn,float Pd,vector O,vector D){ return D * gPRxZ(Pn,Pd,O,D);} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector O Origin of Ray vector D Direction of Ray Output Description return vector gPRdV Returns vector along a ray to a plane Requirement function float gPRxZ(vector Pn,float Pd,vector O,vector D) By Nexii Malthus

Plane and Ray, Intersection Point

Finds intersection point along a ray to a plane <lsl> vector gPRxX(vector Pn,float Pd,vector O,vector D){ return O + gPRdV(Pn,Pd,O,D);} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector O Origin of Ray vector D Direction of Ray Output Description return vector gPRxX Returns vector point of intersection between ray and plane Requirement function vector gPRdV(vector Pn,float Pd,vector O,vector D) By Nexii Malthus

Plane and Line, Intersection Point
Finds interesection point of a line and a plane <lsl> vector gPLxX(vector Pn,float Pd,vector O,vector D){ return O -( (Pn*D)/(Pn*O+Pd) )*D;} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector O Origin of Line vector D Direction of Line Output Description return vector gPLxX Returns vector point of intersection between line and plane By Nexii Malthus

Plane and Plane, Intersection Line

Finds line of intersection of two planes <lsl> vector oO;vector oD; gPPxL(vector Pn,float Pd,vector Qn,float Qd){ oD = (Pn%Qn)/llVecMag(Pn%Qn); vector Cross = (Pn%Qn)%Pn; vector Bleh = (-Pd*Pn); oO = Bleh - (Qn*Cross)/(Qn*Bleh+Qd)*Cross/llVecMag(Cross);} </lsl> Input Description vector Pn Normal of Plane 1 float Pd Distance of Plane 1 vector Qn Origin of Plane 2 float Qd Distance of Plane 2 Output Description vector oO Intersection Line's origin vector oD Intersection Line's direction Requirement global vector oO global vector oD By Nexii Malthus

Plane and Ray, Projection

Projects a ray onto a plane <lsl> vector oO;vector oD; gPRpR(vector Pn,float Pd,vector O,vector D){ oO = O - (Pn * O + Pd) * Pn; vector t = llVecNorm( D - (Pn*((D*Pn)/(Pn*Pn))) );t = <1.0/t.x,1.0/t.y,1.0/t.z>; oD = Pn%t;} </lsl> Input Description vector Pn Normal of Plane float Pd Distance of Plane vector O Origin of Ray vector D Direction of Ray Output Description vector oO Projected Ray Origin vector oD Projected Ray Direction Requirement global vector oO global vector oD By Nexii Malthus

Sphere Functions

Sphere and Ray, Intersection Point

Finds intersection point of sphere and ray <lsl> vector gSRxX(vector Sp, float Sr, vector Ro, vector Rd){ float t;Ro = Ro - Sp; if(Rd == ZERO_VECTOR) return ZERO_VECTOR; float a = Rd * Rd; float b = 2 * Rd * Ro; float c = (Ro * Ro) - (Sr * Sr); float disc = b * b - 4 * a * c; if(disc < 0) return ZERO_VECTOR; float distSqrt = llSqrt(disc); float q; if(b < 0) q = (-b - distSqrt)/2.0; else q = (-b + distSqrt)/2.0; float t0 = q / a; float t1 = c / q; if(t0 > t1){ float temp = t0; t0 = t1; t1 = temp; } if(t1 < 0) return ZERO_VECTOR; if(t0 < 0) t = t1; else t = t0; return Ro + (t * Rd); } </lsl> Input Description vector Sp Origin of Sphere float Sr Radius of Sphere vector Ro Origin of Ray vector Rd Direction of Ray Output Description vector gSRxX Returns intersection point of sphere and ray otherwise ZERO_VECTOR By Nexii Malthus

Sphere and Ray, Intersection Boolean

Finds if there is a intersection of sphere and ray <lsl> integer gSRx(vector Sp, float Sr, vector Ro, vector Rd){ float t;Ro = Ro - Sp; //vector RayOrg = llDetectedPos(x) - llGetPos(); if(Rd == ZERO_VECTOR) return FALSE; float a = Rd * Rd; float b = 2 * Rd * Ro; float c = (Ro * Ro) - (Sr * Sr); float disc = b * b - 4 * a * c; if(disc < 0) return FALSE; return TRUE; } </lsl> Input Description vector Sp Origin of Sphere float Sr Radius of Sphere vector Ro Origin of Ray vector Rd Direction of Ray Output Description integer gSRx Returns a boolean indicating if there is a valid intersection By Nexii Malthus

Ray Functions

Ray and Point, projected distance
Finds projected distance of a point along a ray <lsl> float gRXpZ(vector O,vector D,vector A){ return (A-O)*D;} </lsl> Input Description vector O Origin of Ray vector D Direction of Ray vector A Origin of Point Output Description float gRXpZ Returns projected distance of a point along a ray By Nexii Malthus

Box Functions

Box and Ray, Intersection Distance

Finds intersection of a Ray to a Box and returns intersection distance, otherwise -1 if there is no legal intersection. <lsl> float gBRxZ(vector Ro,vector Rd, vector Bo, vector Bs, rotation Br){ vector oB = (Ro-Bo)/Br; vector dB = Rd/Br; vector eB = 0.5*Bs; float mD = -1.0; float D; vector X; if(llFabs(dB.x) > 0.000001){ D = (-eB.x - oB.x ) / dB.x; if(D >= 0.0){ X = oB + D * dB; if(X.y >= -eB.y && X.y <= eB.y && X.z >= -eB.z && X.z <= eB.z) mD = D; } D = ( eB.x - oB.x ) / dB.x; if (D >= 0.0){ X = oB + D * dB; if(X.y >= -eB.y && X.y <= eB.y && X.z >= -eB.z && X.z <= eB.z) if (mD < 0.0 || mD > D) mD = D; } } if(llFabs(dB.y) > 0.000001){ D = (-eB.y - oB.y ) / dB.y; if(D >= 0.0){ X = oB + D * dB; if(X.x >= -eB.x && X.x <= eB.x && X.z >= -eB.z && X.z <= eB.z) if (mD < 0.0 || mD > D) mD = D; } D = ( eB.y - oB.y ) / dB.y; if (D >= 0.0){ X = oB + D * dB; if(X.x >= -eB.x && X.x <= eB.x && X.z >= -eB.z && X.z <= eB.z) if (mD < 0.0 || mD > D) mD = D; } } if(llFabs(dB.z) > 0.000001){ D = (-eB.z - oB.z ) / dB.z; if(D >= 0.0){ X = oB + D * dB; if(X.x >= -eB.x && X.x <= eB.x && X.y >= -eB.y && X.y <= eB.y) if (mD < 0.0 || mD > D) mD = D; } D = ( eB.z - oB.z ) / dB.z; if (D >= 0.0){ X = oB + D * dB; if(X.x >= -eB.x && X.x <= eB.x && X.y >= -eB.y && X.y <= eB.y) if (mD < 0.0 || mD > D) mD = D; } } return mD; } </lsl> Input Description vector Ro Origin of Ray vector Rd Direction of Ray vector Bo Origin of Box vector Bs Size of Box rotation Br Rotation of Box Output Description float gBRxZ Returns distance to intersection of a ray and a box By Hewee Zetkin

Box and Ray, Intersection Point

Finds intersection of a Ray to a Box and returns intersection point, otherwise ZERO_VECTOR if there is no legal intersection. <lsl> vector gBRxX( vector Ro, vector Rd, vector Bo, vector Bs, rotation Br){ float k = gBRxZ(Ro,Rd,Bo,Bs,Br); if( k != -1.0 ) return Ro + Rd * k; else return ZERO_VECTOR;} </lsl> Input Description vector Ro Origin of Ray vector Rd Direction of Ray vector Bo Origin of Box vector Bs Size of Box rotation Br Rotation of Box Output Description vector gBRxX Returns point of intersection of a ray and a box Requirement float gBRxZ(vector Ro,vector Rd, vector Bo, vector Bs, rotation Br) By Hewee Zetkin

Box and Point, Intersection Boolean

Finds if there is an intersection of a Point and a Box and returns boolean <lsl> integer gBXx(vector A, vector Bo, vector Bs, rotation Br){ vector eB = 0.5*Bs; vector rA = (A-Bo)/Br; if( rA.x < eB.x && rA.x > -eB.x && rA.y < eB.y && rA.y > -eB.y && rA.z < eB.z && rA.z > -eB.z ) return TRUE; else return FALSE;} </lsl> Input Description vector A Origin of Point vector Bo Origin of Box vector Bs Size of Box rotation Br Rotation of Box Output Description integer gBXx(vector A, vector Bo, vector Bs, rotation Br) Returns boolean check of intersection of a point and a box if there is one, otherwise FALSE By Nexii Malthus

Box and Point, Nearest Point on Edge

Processes point on nearest edge of box to given point <lsl> vector gBXnEX(vector A, vector Bo, vector Bs, rotation Br){ vector eB = 0.5*<llFabs(Bs.x),llFabs(Bs.y),llFabs(Bs.z)>; vector rA = (A-Bo)/Br; float mD = 3.402823466E+38; vector X; list EdgesX = [< 0, eB.y, eB.z>, < 0,-eB.y, eB.z>, < 0,-eB.y,-eB.z>, < 0, eB.y,-eB.z>]; list EdgesY = [< eB.x, 0, eB.z>, <-eB.x, 0, eB.z>, <-eB.x, 0,-eB.z>, < eB.x, 0,-eB.z>]; list EdgesZ = [< eB.x, eB.y, 0>, <-eB.x, eB.y, 0>, <-eB.x,-eB.y, 0>, < eB.x,-eB.y, 0>]; integer x = (EdgesX != []); while( --x + 1 ){ float y = gLXdZ( llList2Vector( EdgesX, x ), <1,0,0>, rA ); if( rA.x > eB.x ) y += rA.x - eB.x; else if( rA.x < -eB.x ) y -= rA.x - -eB.x; if( y < mD ){ mD = y; X = gLXnX( llList2Vector( EdgesX, x ), <1,0,0>, rA ); } } x = (EdgesY != []); while( --x + 1 ){ float y = gLXdZ( llList2Vector( EdgesY, x ), <0,1,0>, rA ); if( rA.y > eB.y ) y += rA.y - eB.y; else if( rA.y < -eB.y ) y -= rA.y - -eB.y; if( y < mD ){ mD = y; X = gLXnX( llList2Vector( EdgesY, x ), <0,1,0>, rA ); } } x = (EdgesZ != []); while( --x + 1 ){ float y = gLXdZ( llList2Vector( EdgesZ, x ), <0,0,1>, rA ); if( rA.z > eB.z ) y += rA.z - eB.z; else if( rA.z < -eB.z ) y -= rA.z - -eB.z; if( y < mD ){ mD = y; X = gLXnX( llList2Vector( EdgesZ, x ), <0,0,1>, rA ); } } if( mD < 0.000001 ) return <-1,-1,-1>; if( X.x > eB.x ) X.x = eB.x; else if( X.x < -eB.x ) X.x = -eB.x; if( X.y > eB.y ) X.y = eB.y; else if( X.y < -eB.y ) X.y = -eB.y; if( X.z > eB.z ) X.z = eB.z; else if( X.z < -eB.z ) X.z = -eB.z; return Bo + ( X * Br );} </lsl> Input Description vector A Origin of Point vector Bo Origin of Box vector Bs Size of Box rotation Br Rotation of Box Output Description vector gBXnEX(vector A, vector Bo, vector Bs, rotation Br) Returns nearest point on edge of box B closest to point A. Returns <-1,-1,-1> if already on closest point. Requirement float gLXdZ(vector O,vector D,vector A) vector gLXdV(vector O,vector D,vector A) vector gLXnX(vector O,vector D,vector A) By Nexii Malthus

Other Functions

3D Projection
Projects a vector A by vector B. <lsl> vector Project3D(vector A,vector B){ return B * ( ( A * B ) / ( B * B ) );} </lsl> Input Description vector A First Vector vector B Second Vector Output Description return Project3D(vector A, vector B) Returns result of projection By Nexii Malthus

Legend

For anyone curious to the shorthand used and who wish to use a lookup table can use this as a reference. Or anyone who wishes to add a new function to the library is welcome to but it would be recommended to keep consistency. I tried to minimize the script function names to be easily readable. All the geometric function names start with a g. Here is the legend:

Shorthand	Name	Description
Geometric Types
X	Point	vector defining a point in space
L	Line	A line has an origin and a direction and is infinitely long
LS	Line Segment	A line segment is a finite line and therefore consists of a start and end position
R	Ray	A ray is like a line, except it is more distinct as it defines wether it points forward or back
P	Plane	A 2D doubly ruled surface of infinite size
S	Sphere	A sphere is defined by origin and radius
B	Box	A box is six sided and defined by origin, size as well as a rotation.
What does it do?
d	Distance	Calculate distance
n	Nearest	Calculate nearest
p	Project	Calculates projection
x	Intersection	Calculates intersection
What kind of data do I get out of it?
Z	Float	Represents that a float is returned
V	Vector	Represents that a vector is returned
O	Origin	Represents the Origin of the ray or line
D	Direction	Direction from the Origin
E	Edge	Edge of a shape, such as an edge on a box, suffix may mark special case return type