Geometric
LSL Portal  Functions  Events  Types  Operators  Constants  Flow Control  Script Library  Categorized Library  Tutorials 
Please vote for: https://jira.secondlife.com/browse/WEB235 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)
:Break it up so each major section has its own page... thats why hypertext was invented. Overbrain Unplugged 13:36, 10 October 2010 (UTC)
Geometric Library
Contents
 1 Geometric Library
 1.1 Line Functions
 1.1.1 Line and Point, Vector
 1.1.2 Line and Point, Distance
 1.1.3 Line Nearest Point, Nearest Point
 1.1.4 Line and Line, Vector
 1.1.5 Line and Line, Distance
 1.1.6 Line and Line, Nearest point
 1.1.7 Line and Line, intersection point
 1.1.8 Line and Line, two nearest points of lines
 1.1.9 Line and Line, nearest line
 1.1.10 Line and Line Segments, nearest line segment
 1.1.11 Line and Line, two nearest points with vector and distance
 1.1.12 Line and Point, Direction
 1.2 Plane Functions
 1.2.1 Plane and Point, Distance
 1.2.2 Plane and Point, Vector
 1.2.3 Plane and Point, Nearest point
 1.2.4 Plane and Ray, Intersection Distance
 1.2.5 Plane and Ray, Vector
 1.2.6 Plane and Ray, Intersection Point
 1.2.7 Plane and Line, Intersection Point
 1.2.8 Plane and Plane, Intersection Line
 1.2.9 Plane and Ray, Projection
 1.3 Sphere Functions
 1.4 Ray Functions
 1.5 Box Functions
 1.6 Cylinder
 1.7 Polygon
 1.8 Other Functions
 1.9 Glossary
 1.10 Licenses
 1.1 Line Functions
Line and Point, Vector  

Calculates the vector from a point 'to' the closest point on a line vector gLXdV(vector O,vector D,vector A){ return (OA)((OA)*D)*D;}
3D
By Nexii Malthus

Line and Point, Distance  

Calculates distance of line to point, same as measuring magnitude of Line and Point Vector, but faster on it's own float gLXdZ(vector O,vector D,vector A){ vector k = ( A  O ) % D; return llSqrt( k * k );}
3D
By Nexii Malthus

Line Nearest Point, Nearest Point  

Returns nearest point on line to given point vector gLXnX(vector O,vector D,vector A){ return gLXdV(O,D,A) + A;}
3D
By Nexii Malthus

Line and Line, Vector  

Shortest vector of two lines vector gLLdV(vector O1,vector D1,vector O2,vector D2){ vector A = O2  O1; vector B = D1 % D2; return B*( (A*B)/(B*B) );}
3D
By Nexii Malthus

Line and Line, Distance  

Returns the distance between two lines 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 (O2O1) * A;}
3D
By Nexii Malthus

Line and Line, Nearest point  

Closest point of two lines 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.xnO2.x)  nD2.x*(nO1.ynO2.y) ) / t; return O1 + D1*t;}
2D
By Nexii Malthus

Line and Line, intersection point  

Computes intersection point of two lines, if there is any, else <1,1,1> if none. vector gLLxX( vector A, vector B, vector C, vector D ){ vector b = BA; vector d = DC; float dotperp = b.x*d.y  b.y*d.x; if (dotperp == 0) return <1,1,1>; vector c = CA; float t = (c.x*d.y  c.y*d.x) / dotperp; return <A.x + t*b.x, A.y + t*b.y, 0>;}
2D
By Nexii Malthus

Line and Line, two nearest points of lines  

Two closest points of two lines on each line 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.xnO2.x)  nD2.x*(nO1.ynO2.y) ) / t; X1 = O1 + D1*t; X2 = X1 + nD1%nD2;}
2D
By Nexii Malthus

Line and Line, nearest line  

Input two lines, the function will return a list containing two vectors responding to the line nearest between them. As well as two floats corresponding to the scalar value on the two line of where the line has an end located at. list gLLnL( vector v0, vector v1, vector v2, vector v3 ) { float Eps = 0.000001; vector vx; vector vy; vector va; vector vb; vector vc; float x; float y; float d0; float d1; float d2; float d3; float d4; va = v0v2; vb = v3v2; if(llVecMag(vb)<Eps) return []; vc = v1v0; if(llVecMag(vc)<Eps) return []; d0 = va*vb; d1 = vb*vc; d2 = va*vc; d3 = vb*vb; d4 = vc*vc; float den = d4*d3d1*d1; if( llFabs(den) < Eps ) return []; float num = d0*d1d2*d3; x = num/den; y = (d0+d1*x)/d3; vx = v0+vc*x; vy = v2+vb*y; return [vx,vy,x,y]; }
3D
By Nexii Malthus

Line and Line Segments, nearest line segment  

Input two line segments, the function will return a list containing two vectors responding to the line segment nearest between them. As well as two floats corresponding to the scalar value on the two line segments of where the line segment has an end located at. list gLSLSnLS( vector v0, vector v1, vector v2, vector v3 ) { float Eps = 0.000001; vector vx; vector vy; vector va; vector vb; vector vc; float x; float y; float d0; float d1; float d2; float d3; float d4; va = v0v2; vb = v3v2; if(llVecMag(vb)<Eps) return []; vc = v1v0; if(llVecMag(vc)<Eps) return []; if( llFabs(vc.x + vc.y + vc.z) < Eps ) return []; d0 = va*vb; d1 = vb*vc; d2 = va*vc; d3 = vb*vb; d4 = vc*vc; float den = d4*d3d1*d1; if( llFabs(den) < Eps ) return []; float num = d0*d1d2*d3; x = num/den; y = (d0+d1*x)/d3; if(x<0)x=0; else if(x>1)x=1; if(y<0)y=0; else if(y>1)y=1; vx = v0+vc*x; vy = v2+vb*y; return [vx,vy,x,y]; }
3D
By Nexii Malthus

Line and Line, two nearest points with vector and distance  

Computes two closest points of two lines, vector and distance 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.xnO2.x)  nD2.x*(nO1.ynO2.y) ) / t; X1 = O1 + D1*t; X2 = X1 + CP(nD1,nD2); V1 = nD1%nD2; Z1 = llVecMag(V1);}
2D
By Nexii Malthus

Line and Point, Direction  

Works out where point (X) is relative to the line of the segment (L0, L1). float gLSPdir( vector L0, vector L1, vector X ){ return (L1.x  L0.x)*(X.y  L0.y)  (X.x  L0.x)*(L1.y  L0.y); }
2D
Copyright 2001, softSurfer (www.softsurfer.com) (Must accept License #2), LSLPort By Nexii Malthus

Plane and Point, Distance  

Finds distance of a point from a plane float gPXdZ(vector Pn,float Pd,vector A){ return A * Pn + Pd;}
3D
By Nexii Malthus

Plane and Point, Vector  

Finds vector that points from point to nearest on plane vector gPXdV(vector Pn,float Pd,vector A){ return (Pn * A + Pd)*Pn;}
3D
By Nexii Malthus

Plane and Point, Nearest point  

Finds closest point on plane given point vector gPXnX(vector Pn,float Pd,vector A){ return A  (Pn * A + Pd) * Pn;}
3D
By Nexii Malthus

Plane and Ray, Intersection Distance  

Finds distance to intersection of plane along ray float gPRxZ(vector Pn,float Pd,vector O,vector D){ return ((Pn*O+Pd)/(Pn*D));}
3D
By Nexii Malthus

Plane and Ray, Vector  

Finds distance vector along a ray to a plane vector gPRdV(vector Pn,float Pd,vector O,vector D){ return D * gPRxZ(Pn,Pd,O,D);}
3D
By Nexii Malthus

Plane and Ray, Intersection Point  

Finds intersection point along a ray to a plane vector gPRxX(vector Pn,float Pd,vector O,vector D){ return O + gPRdV(Pn,Pd,O,D);}
3D
By Nexii Malthus

Plane and Line, Intersection Point  

Finds interesection point of a line and a plane vector gPLxX(vector Pn,float Pd,vector O,vector D){ return O + D*( (Pn*OPd)/(Pn*D) );}
3D
By Nexii Malthus

Plane and Plane, Intersection Line  

Finds line of intersection of two planes 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);}
3D
By Nexii Malthus

Plane and Ray, Projection  

Projects a ray onto a plane 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;}
3D
By Nexii Malthus

Sphere and Ray, Intersection Point  

Finds intersection point of sphere and ray vector gSRxX(vector Sp, float Sr, vector Ro, vector Rd){ float t; 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 Sp + Ro + (t * Rd); }
3D
By Nexii Malthus

Sphere and Ray, Intersection Boolean  

Finds if there is a intersection of sphere and ray 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; }
3D
By Nexii Malthus

Ray and Point, projected distance  

Finds projected distance of a point along a ray float gRXpZ(vector O,vector D,vector A){ return (AO)*D;}
3D
By Nexii Malthus

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. float gBRxZ(vector Ro,vector Rd, vector Bo, vector Bs, rotation Br){ vector oB = (RoBo)/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; }
3D
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. 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;}
3D
By Hewee Zetkin

Box and Point, Intersection Boolean  

Finds if there is an intersection of a Point and a Box and returns boolean integer gBXx(vector A, vector Bo, vector Bs, rotation Br){ vector eB = 0.5*Bs; vector rA = (ABo)/Br; return (rA.x<eB.x && rA.x>eB.x && rA.y<eB.y && rA.y>eB.y && rA.z<eB.z && rA.z>eB.z); }
3D
By Nexii Malthus

Box and Point, Nearest Point on Edge  

Processes point on nearest edge of box to given point 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 = (ABo)/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 ){ 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 ){ 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 ){ 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 );}
3D
By Nexii Malthus

Cylinder and Point, Intersection Boolean  

Finds if there is an intersection of a Point and a Cylinder and returns boolean integer gCXx( vector A, vector O, rotation R, vector S ) { A = ( A  O ) / R;// Converts to local object frame return (llPow(A.x/S.x*2,2) + llPow(A.y/S.y*2,2)) <= 1. // Test radius && llFabs(A.z/S.z*2) <= 1.;// Test top/bottom }
3D
By Nexii Malthus

Polygon and Point, Intersection Boolean  

Figures out if point is inside of polygon or otherwise. integer gCPXx( list CP, vector X ) {//Copyright (c) 19702003, Wm. Randolph Franklin; 2008, Strife Onizuka integer i = ~(CP != []); integer c = 0; if(i < 2){ vector vi = llList2Vector(CP, 1); do { vector vj = vi; vi = llList2Vector(CP, i); if((vi.y > X.y) ^ (vj.y > X.y)){ if(vj.y != vi.y) c = c ^ (X.x < (((vj.x  vi.x) * (X.y  vi.y) / (vj.y  vi.y)) + vi.x)); else c = c ^ (0 < ((vj.xvi.x) * (X.yvi.y))); } } while (++i); } return c; }
2D
Copyright (c) 19702003, Wm. Randolph Franklin (Must accept License #1), LSLPort By Strife Onizuka

Polygon and Line Segment, Intersection Boolean  

Figures out if line segment intersects with polygon. integer gVPLSx( vector P0, vector P1, list VP ){ //Copyright 2001, softSurfer (www.softsurfer.com); 2008, Nexii Malthus if( P0 == P1 ) return gCPXx( VP, P0 ); float tE = 0; float tL = 1; float t; float N; float D; vector dS = P1  P0; vector e; integer x; integer y = VP!=[]; @start; for( x = 0; x < y; ++x ){ e = llList2Vector( VP, x+1 )  llList2Vector( VP, x ); N = Perp( e, P0  llList2Vector( VP, x ) ); D = Perp( e, dS ); if( llFabs(D) < 0.00000001 ) if( N < 0 ) return FALSE; else jump start; t = N / D; if( D < 0 ){ if( t > tE ){ tE = t; if( tE > tL ) return FALSE; } } else { if( t < tL ){ tL = t; if( tL < tE ) return FALSE; } } } // PointOfEntrance = P0 + tE * dS; // PointOfExit = P0 + tL * dS; return TRUE; }
2D
Copyright 2001, softSurfer (www.softsurfer.com) (Must accept License #2), LSLPort By Nexii Malthus

3D Projection  

Projects a vector A by vector B. vector Project3D(vector A,vector B){ return B * ( ( A * B ) / ( B * B ) );}
3D
By Nexii Malthus

Reflection  

Reflects Ray R with surface normal N vector Reflect(vector R,vector N){ return R  2 * N * ( R * N );}
3D
By Nexii Malthus

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.
g (Shape1) (Shape2) (Process) (Return (Only needed if other than integer))
Here is the legend:
Shorthand  Name  Description 

Geometric Types, all the shapes in the library  
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 (No ellipsoid functions available yet) 
B  Box  A box primitive is six sided and defined by origin, size as well as a rotation. 
C  Cylinder  An elliptic cylinder primitive . 
VP  Convex Polygon  Convex Polygon defined by list of vertices. 
CP  Concave Polygon  Concave Polygon defined by list of vertices. Automatic backward compatibility with Convex Polygons. 
The Process, What does it do?  
d  distance  Calculate distance 
n  nearest  Calculate nearest 
p  project  Calculates projection 
x  Intersection  Calculates intersection 
dir  direction  Calculates direction 
Return, 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 
#1
//Copyright (c) 19702003, Wm. Randolph Franklin //Copyright (c) 2008, Strife Onizuka (porting to LSL) // //Permission is hereby granted, free of charge, to any person obtaining a copy //of this software and associated documentation files (the "Software"), to deal //in the Software without restriction, including without limitation the rights //to use, copy, modify, merge, publish, distribute, sublicense, and/or sell //copies of the Software, and to permit persons to whom the Software is //furnished to do so, subject to the following conditions: // // 1. Redistributions of source code must retain the above copyright notice, // this list of conditions and the following disclaimers. // 2. Redistributions in binary form must reproduce the above copyright // notice in the documentation and/or other materials provided with the // distribution. // 3. The name of W. Randolph Franklin may not be used to endorse or promote // products derived from this Software without specific prior written // permission. //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR //IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, //FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE //AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER //LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, //OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE //SOFTWARE.
#2
// Copyright 2001, softSurfer (www.softsurfer.com); 2008, LSLport by Nexii Malthus // This code may be freely used and modified for any purpose // providing that this copyright notice is included with it. // SoftSurfer makes no warranty for this code, and cannot be held // liable for any real or imagined damage resulting from its use. // Users of this code must verify correctness for their application.