Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Library: Geometric Lib
Nexii Malthus
[Cubitar]Mothership
Join date: 24 Apr 2006
Posts: 400
05-07-2008 17:34
https://wiki.secondlife.com/wiki/Geometric

From: someone

//===================================================//
// Geometric Library 1.0 //
// "May 4 2008", "2:24:30" //
// Copyright (C) 2008, Nexii Malthus (cc-by) //
// http://creativecommons.org/licenses/by/3.0/ //
//===================================================//

vector CP(vector A,vector B){
return A % B;}

vector Project3D(vector A,vector B){
vector proj;
proj.x = ( (A*B) / (B.x*B.x + B.y*B.y + B.z*B.z) ) * B.x;
proj.y = ( (A*B) / (B.x*B.x + B.y*B.y + B.z*B.z) ) * B.y;
proj.z = ( (A*B) / (B.x*B.x + B.y*B.y + B.z*B.z) ) * B.z;
return proj;}

// POINT
float gXXdZ(vector A,vector B){
// Distance P2P.
return llVecDist(A,B);}

vector gXXdV(vector A,vector B){
// Vector to move from P2P.
return A-B;}

// LINE
vector gLXdV(vector O,vector D,vector A){
// Calculates the vector from a point to the closest point on a line
return (O-A)-((O-A)*D)*D;}

float gLXdZ(vector O,vector D,vector A){
// Calculates distance of this vector, but faster on it's own
return llSqrt(CP((A-O),D)*CP((A-O),D));}

vector gLLdV(vector O1,vector D1,vector O2,vector D2){
// Shortest vector of two lines
return Project3D( (O2-O1), CP(D1,D2) );}

float gLLdZ(vector O1,vector D1,vector O2,vector D2){
// Returns the distance between two lines
vector A = CP(D1,D2);float B = llVecMag(A);A = <A.x/B,A.y/B,A.z/B>;
return (O2-O1) * A;}

vector gLLnX(vector O1,vector D1,vector O2,vector D2){
// Closest point of two lines
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;}

vector X1;vector X2;vector V1;float Z1;

gLLnnXX(vector O1,vector D1,vector O2,vector D2){
// Two closest points of two lines
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);}

gLLnnXXVZ(vector O1,vector D1,vector O2,vector D2){
// Computes two closest points of two lines, vector and distance
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 = CP(nD1,nD2);
Z1 = llVecMag(V1);}

// PLANE
float gPXdZ(vector Pn,float Pd,vector A){
// Finds distance of a point from a plane
return A * Pn + Pd;}

vector gPXdV(vector Pn,float Pd,vector A){
// Finds vector that points from point to nearest on plane
return -(Pn * A + Pd)*Pn;}

vector gPXnX(vector Pn,float Pd,vector A){
// Finds closest point on plane given point
return A - (Pn * A + Pd) * Pn;}

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

vector gPRdV(vector Pn,float Pd,vector O,vector D){
// Finds distance vector along a ray to a plane
return D * gPRxZ(Pn,Pd,O,D);}
//return -( (Pn*D)/(Pn*O+Pd) )*D;}

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

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

vector oO;vector oD;

gPPxL(vector Pn,float Pd,vector Qn,float Qd){
// Finds line of intersection of two planes
oD = CP(Pn,Qn)/llVecMag(CP(Pn,Qn));
vector Cross = CP(CP(Pn,Qn),Pn);
vector Bleh = (-Pd*Pn);
oO = Bleh - (Qn*Cross)/(Qn*Bleh+Qd)*Cross/llVecMag(Cross);}

float gRXpZ(vector O,vector D,vector A){
// Finds projected distance of a point along a ray
return (A-O)*D;}

gPRpR(vector Pn,float Pd,vector O,vector D){
// Projects a ray onto a plane
oO = O - (Pn * O + Pd) * Pn;
vector t = llVecNorm( D - Project3D(D,Pn) );t = <1.0/t.x,1.0/t.y,1.0/t.z>;
oD = CP(Pn,t);}

// SPHERE
vector gSRxX(vector Sp, float Sr, vector Ro, vector Rd){
float t;Ro = Ro - Sp;
//vector RayOrg = llDetectedPos(x) - llGetPos();
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);
}

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;
}

// Other
vector pN;float pD;
gTiP(vector p1,vector p2,vector p3){
pN = llVecNorm( CP((p2-p1),(p3-p1)) );
pD = -p1*pN;}

integer gTXcC(vector p1,vector p2,vector p3,vector x){
gTiP(p1,p2,p3);
vector Vn;vector En;
Vn = p1 - x;
En = CP((p2-p1),pN);
if( ((p1-x)*CP(p2-p1,pN) >= 0)&&;((p2-x)*CP(p3-p2,pN) >= 0)&&;((p3-x)*CP(p1-p3,pN) >= 0) ) return TRUE;
return FALSE;}

integer gTVXcC(vector p1,vector p2,vector p3,vector v,vector x){
if( ((p1-x)*CP(p2-p1,v) >= 0)&&;((p2-x)*CP(p3-p2,v) >= 0)&&;((p3-x)*CP(p1-p3,v) >= 0) ) return TRUE;
return FALSE;}

integer gTRcC(vector p1,vector p2,vector p3,vector O,vector D){
return gTVXcC(p1,p2,p3,O,D);}

vector gRZiX(vector O,vector D,float z){
return O+z*D;}

default{state_entry(){}}

_____________________

Geometric Library, for all your 3D maths needs.
https://wiki.secondlife.com/wiki/Geometric

Creator of the Vertical Life Client
Nada Epoch
The Librarian
Join date: 4 Nov 2002
Posts: 1,423
Library bump
05-11-2008 11:31
:)
_____________________
i've got nothing. ;)
Django Yifu
Beat Island Gaffer
Join date: 7 May 2007
Posts: 189
05-12-2008 04:01
This looks ineteresting but how do I use it?
_____________________
Tread softly upon the Earth for you walk on my face.
Kidd Krasner
Registered User
Join date: 1 Jan 2007
Posts: 1,938
05-12-2008 07:53
If you're looking for comments, I'd start with some meaningful names. I saw the comment on the wiki that equates 'short' with 'easy to read'. While there's an element of truth to that, this has taken it way too far. The name llVecDist makes much more sense than gXXdZ (which looks like it came out of Zork). Single letter codes (including Hungarian notation) have long fallen out of favor. Remember that the names themselves don't consume run time memory.

This applies to parameters as well as function names. Thus something like
CODE

vector Point2Line(vector point, 
                  vector lineOrigin, 
                  vector lineDirection)

is easier than
CODE

vector gLXdV(vector O,vector D,vector A)

It's still not totally obvious. Point2NearestPointOnLine feels too long, but it's still better than gLXdV.

While we're at it, 'g' is an unfortunate choice of package prefix, simply because it's already popular to indicate global variables. Personally, I'd prefer Geom, e.g. GeomPoint2Line (though I'd be much happier if LSL had package namespaces).
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
05-12-2008 10:59
And there aren't any comments telling you about restrictions on the function parameters. :(

I didn't mind the obtuse function names so much but the parameter names were a sticking point for me. The lack of optimization really kinda annoys me (which is why I wrote the ESL version).

Makes me sad when I see stuff like this:

vector A = CP(D1,D2);float B = llVecMag(A);A = <A.x/B,A.y/B,A.z/B>;
_____________________
Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river.
- Cyril Connolly

Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence.
- James Nachtwey
Nexii Malthus
[Cubitar]Mothership
Join date: 24 Apr 2006
Posts: 400
05-14-2008 09:49
Yeah, I am sorry, but I didn't design it for mass use or user-friendliness yet. I am just really busy at the moment with RL and thought that a few individuals might be quite happy just having the basic stuff.

I will optimize it at a later date, or over a period and equip it more meaningful names. But I personally thought people might be more interested in getting a result than the core mathematics behind it. I will leave the inner variables for now and change the function names instead.
_____________________

Geometric Library, for all your 3D maths needs.
https://wiki.secondlife.com/wiki/Geometric

Creator of the Vertical Life Client
Kidd Krasner
Registered User
Join date: 1 Jan 2007
Posts: 1,938
05-14-2008 09:54
From: Nexii Malthus
Yeah, I am sorry, but I didn't design it for mass use or user-friendliness yet. I am just really busy at the moment with RL and thought that a few individuals might be quite happy just having the basic stuff.

I will optimize it at a later date, or over a period and equip it more meaningful names. But I personally thought people might be more interested in getting a result than the core mathematics behind it. I will leave the inner variables for now and change the function names instead.

You're right, I am more interested in the result than the mathematics. The problem is that the only way I can figure out how to use it is to reverse engineer the math.
Barrington John
Yorkshire guy
Join date: 17 Nov 2007
Posts: 119
05-15-2008 06:10
While I agree about the naming strategy, and have the expected moan about lack of documentatio, it's worth saying that this looks to be extremely useful. Like many, I find geometrical maths a real PITA, and yet it's often crucial.
Nexii Malthus
[Cubitar]Mothership
Join date: 24 Apr 2006
Posts: 400
05-23-2008 13:24
Documentation is going live on the LSL Portal page for the library. It will give a better explanation of input and output.
_____________________

Geometric Library, for all your 3D maths needs.
https://wiki.secondlife.com/wiki/Geometric

Creator of the Vertical Life Client
Talarus Luan
Ancient Archaean Dragon
Join date: 18 Mar 2006
Posts: 4,831
05-23-2008 16:49
From: Kidd Krasner
Single letter codes (including Hungarian notation) have long fallen out of favor.


Speak for yourself. :P Hungarian notation is alive and well. :)

The rest, agreed.

Seems to me to be a waste of code to repackage existing functions as user functions, too.
Nexii Malthus
[Cubitar]Mothership
Join date: 24 Apr 2006
Posts: 400
06-07-2008 15:27
Any comments on the new documentation?
(Also a cheap bump for the thread to go up and get noticed.)
_____________________

Geometric Library, for all your 3D maths needs.
https://wiki.secondlife.com/wiki/Geometric

Creator of the Vertical Life Client
Anthony Hocken
Registered User
Join date: 16 Apr 2006
Posts: 121
06-08-2008 07:08
From: Kidd Krasner
Single letter codes (including Hungarian notation) have long fallen out of favor.



Wow, that stopped me in my tracks. By Hungarian notation you mean prefixing variable names with a letter indicating their type, right? I must be behind the times then. I've been doing this for years. I actually cringe when I see code that doesn't use it.
_____________________
Nexii Malthus
[Cubitar]Mothership
Join date: 24 Apr 2006
Posts: 400
09-26-2008 12:21
Updates so far on the wiki page of this script have included a new area for Box related functions;

From: someone
Box and Ray, Intersection Distance

and,
From: someone
Box and Ray, Intersection Point

by Hewee Zetkin

I also threw in
From: someone
Box and Point, Intersection Boolean

and a rather interesting one being the result of a commission by a good friend of mine, who has been working on highly experimental weaponry back on the Teen Grid,
From: someone
Box and Point, Nearest Point on Edge


Finally I threw in this missing basic geometric function,
From: someone
Line and Line, intersection point


Have fun :D
_____________________

Geometric Library, for all your 3D maths needs.
https://wiki.secondlife.com/wiki/Geometric

Creator of the Vertical Life Client
Seifert Surface
Mathematician
Join date: 14 Jun 2005
Posts: 912
09-26-2008 20:23
Why isn't Project3D(vector A,vector B) just:
return B*((A*B)/(B*B)); ?
_____________________
-Seifert Surface
2G!tGLf 2nLt9cG
Triple Peccable
Registered User
Join date: 7 Jul 2007
Posts: 70
09-27-2008 22:51
I'm having a problem with getting reliable data from the line to line intersect function.

If the input to the function is the beginnings and ends of 2 lines, it should not matter which line is sent as line 1 (A and B) and which line is sent as line 2 (C and D), should it? In my case it does seem to change the output.

Also, this seems to imply it is using the lines as segments, instead of infinite length, but the results seem to indicate infinite length. Can I get a clarification on that?

Thanks.

EDIT: No need to hurry looking into this, I just realized I was using complicated 3D math to do something I was able to do with simple 2D math. So I am over my problem, and for all I know there may not be any issues with this function.
Nexii Malthus
[Cubitar]Mothership
Join date: 24 Apr 2006
Posts: 400
09-30-2008 20:04
@Seifert, ah forgot that, I actually didn't remember that I could have done it that simple because my brain was still fried from all the maths involved as it doesn't seem to like it. I was going to replace it appriopriately later after noticing it but I lost memory of that.

@Tripe, I should probably have mentioned it, the line and line intersection function is explicitly for 2D lines. So the Z component is completely ignored.
_____________________

Geometric Library, for all your 3D maths needs.
https://wiki.secondlife.com/wiki/Geometric

Creator of the Vertical Life Client
Hewee Zetkin
Registered User
Join date: 20 Jul 2006
Posts: 2,702
10-01-2008 22:39
This function should give you the "intersection" of two lines in 3D. What it actually does is find the shortest line segment between a point on the first line a point on the second line, then returns the midpoint of that line segment.

(Warning: Not yet compiled or tested, so may require a couple minor fixes. Will revisit post after testing.)
CODE

float EPSILON = 0.0001;

// Returns the midpoint of the shortest line segment between two lines.
// Tangent vectors are assumed to be normalized; no checking is done.
//    param p1 - A point on the first line.
//    param u1 - A unit tangent vector in the direction of the first line.
//    param p2 - A point on the second line.
//    param u2 - A unit tangent vector in the direction of the second line.
vector midpointBetweenLines(vector p1, vector u1, vector p2, vector u2)
{
   vector r = p2-p1;
   float r1 = r*u1;
   float r2 = r*u2;
   float a = u1*u2;
   float divisor = 1.0-a*a;

   if (llFabs(divisor) < EPSILON)
   {
      // Lines are parallel
      return 0.5*(p1+p2);
   }

   // Distances along each line
   float t1 = (r1-a*r2)/divisor;
   float t2 = (a*r1-r2)/divisor;

   // Ends of shortest line segment
   vector q1 = p1+t1*u1;
   vector q2 = p2+t2*u2;

   return 0.5*(q1+q2);
}