Geometric
LSL Portal | Functions | Events | Types | Operators | Constants | Flow Control | Script Library | Categorized Library | Tutorials |
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
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. <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>
2D
By Nexii Malthus
|
Line and Line, two nearest points of 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>
2D
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>
2D
By Nexii Malthus
|
Line and Point, Direction | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
Works out where point (X) is relative to the line of the segment (L0, L1). <lsl> 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); } </lsl>
2D
Copyright 2001, softSurfer (www.softsurfer.com) (Must accept License #2), LSL-Port 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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
3D
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>
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. <lsl> vector gBRxX( vector Ro, vector Rd, vector Bo, vector Bs, rotation Br){ float k = gBRxZ(Ro,Rd,Bo,Bs,Br); if( ~k ) return Ro + Rd * k; else return ZERO_VECTOR;} </lsl>
3D
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>
3D
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>
3D
By Nexii Malthus
|
Polygon
Polygon and Point, Intersection Boolean | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
Figures out if point is inside of polygon or otherwise. <lsl> integer gCPXx( list CP, vector X ) {//Copyright (c) 1970-2003, 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.x-vi.x) * (X.y-vi.y))); } } while (++i); } return c; } </lsl>
2D
Copyright (c) 1970-2003, Wm. Randolph Franklin (Must accept License #1), LSL-Port By Strife Onizuka
|
Polygon and Line Segment, Intersection Boolean | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Figures out if line segment intersects with polygon. <lsl> 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; } </lsl>
2D
Copyright 2001, softSurfer (www.softsurfer.com) (Must accept License #2), LSL-Port 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>
3D
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.
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 |
B | Box | A box is six sided and defined by origin, size as well as a rotation. |
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 |
Licenses
#1
<lsl> //Copyright (c) 1970-2003, 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. </lsl>
#2
<lsl> // Copyright 2001, softSurfer (www.softsurfer.com); 2008, LSL-port 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. </lsl>