Gamestudio Links
Zorro Links
Newest Posts
AlpacaZorroPlugin v1.3.0 Released
by kzhao. 05/19/24 18:45
Free Live Data for Zorro with Paper Trading?
by AbrahamR. 05/18/24 13:28
Change chart colours
by 7th_zorro. 05/11/24 09:25
Data from CSV not parsed correctly
by dr_panther. 05/06/24 18:50
AUM Magazine
Latest Screens
The Bible Game
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Who's Online Now
3 registered members (AndrewAMD, Ayumi, kzhao), 722 guests, and 7 spiders.
Key: Admin, Global Mod, Mod
Newest Members
Hanky27, firatv, wandaluciaia, Mega_Rod, EternallyCurious
19051 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Line/Plane Intersection #414867
01/09/13 15:30
01/09/13 15:30
Joined: Oct 2008
Posts: 513
Carlos3DGS Offline OP
User
Carlos3DGS  Offline OP
User

Joined: Oct 2008
Posts: 513
Nothing big, just a function that gives you the point of intersection between a line and a plane.
Usefull to use instead of c_trace in many situations.

1. The lines and planes are infinite in every direction, no need to worry about how far something is. If you trace from (0,0,0) to (1,0,0) it automatically extends your line infinitely! These example "start" and "end" points of the line would actually trace from (-inf,0,0) to (+inf,0,0). The same goes for the plane, it automatically extends the plane's surface infinitely in all directions!
2. The distance of the trace to the intersection has no effect on the function's speed. Searching for an intersection on the other side of your level/world? No problem! Just as fast as doing an intersection 1 cm in front of you.
3. The number of objects in your level has no effect on the function's speed. If you just want the point of intersection with the surface of a wall/floor/whatever that you know the coordinates of you don't have to worry about telling it what objects to ignore in it's path and which not to (it ignores all objects in your way to the "plane of intersection").
4. If you want to find an intersection with irregular objects or any objects in it's path like a traditional c_trace would... it is easy to use in combination with c_trace. Tired of giving large values to c_trace just to make sure you go past any distant object? I sometimes use this to optimize a normal c_trace's "start" and/or "end" coordinates to make sure the c_trace is as short as possible while making sure it will actually be able to hit what I am looking for. You decide when it is optimal to use c_trace, this function, or both (c_trace with this function's results as parameters).
5. Since the function dosn't use engine objects, the object/surface dosn't even have to "phisically" exist! Pass it the values of any imaginary plane you wish to get the intersection of!

Quote:
BOOL Line_Plane_Intersection(VECTOR* RESULT, VECTOR* line_p0, VECTOR* line_p1, VECTOR* plane_p0, VECTOR* plane_N);


PARAMETERS:
-RESULT: vector where the intersection's coordinates will be stored
-line_p0: any point on your line (dosn't matter what points are given as long as they are on your line, the line will extend infinately in both directions)
-line_p1: any point on your line (must be different from "line_p0")
-plane_p0: any point on your plane to intersect with (dosn't matter what point it is as long as it is on your plane, the plane will extend infinitely)
-plane_N: normal of your plane (does not matter which side it is facing, the plane's surface will be "double sidded") both front and back sides of the plane can be hit. Cannot be a nullvector (0,0,0).

RETURNS:
0 if the line is parallel to your plane (if it is parallel there are 2 options, either there is no intersection, or if the line is contained in the plane there are an infinite number of intersection points). Either way the "RESULT" vector will not be modified. 0 is also returned if any of the inputs were not valid.
1 if the line and the plane are not parallel (there is a unique intersection point). The "RESULT" vector will be set to the intersection point.

MODIFIES:
-RESULT: This vector will contain the point of intersection if the function returned 1 (not parallel)

CODE:
Code:
BOOL Line_Plane_Intersection(VECTOR* RESULT, VECTOR* line_p0, VECTOR* line_p1, VECTOR* plane_p0, VECTOR* plane_N)
{
	if(vec_dist(line_p0,line_p1)==0||vec_dist(nullvector,plane_N)==0)
	{
		return(0);
	}
	VECTOR line_indeps;
	VECTOR line_coefs;
	vec_set(line_indeps,line_p0);
	vec_set(line_coefs,line_p1);
	vec_sub(line_coefs,line_p0);
	if((plane_N.x*line_coefs.x)+(plane_N.y*line_coefs.y)+(plane_N.z*line_coefs.z)==0)
	{
		return(0);
	}
	var plane_indep;
	VECTOR plane_coefs;
	plane_indep=-(plane_N.x*plane_p0.x)-(plane_N.y*plane_p0.y)-(plane_N.z*plane_p0.z);
	vec_set(plane_coefs,plane_N);
	vec_mul(line_indeps,plane_coefs);
	vec_mul(line_coefs,plane_coefs);
	var T;
	T=(-plane_indep-(line_indeps.x+line_indeps.y+line_indeps.z))/(line_coefs.x+line_coefs.y+line_coefs.z);
	RESULT.x=line_p0.x+T*(line_p1.x-line_p0.x);
	RESULT.y=line_p0.y+T*(line_p1.y-line_p0.y);
	RESULT.z=line_p0.z+T*(line_p1.z-line_p0.z);
	return(1);
}



LINK TO THE CONFERENCE I USED TO LEARN THE MATH BEHIND THIS:
www.youtube.com/watch?v=Q0gnrV699GQ

Heavily commented version of the code to understand everything it does:
Click to reveal..
Code:
BOOL Line_Plane_Intersection(VECTOR* RESULT, VECTOR* line_p0, VECTOR* line_p1, VECTOR* plane_p0, VECTOR* plane_N)
{
   //CHECK THAT THE "SENSITIVE" INPUTS ARE VALID
   //the two points on the line must be different
   //the plane's normal cannot be null
   if(vec_dist(line_p0,line_p1)==0||vec_dist(nullvector,plane_N)==0)
	{
		return(0);
	}
	//GET PARAMETRIC EQUATIONS OF THE LINE
	//F(t)= (x0,y0,z0) + t(x1-x0,y1-y0,z1-z0)
	//resolving the above formula for each component, the resulting equations would be
	//X=x0+t(x1-x0)
	//Y=y0+t(y1-y0)
	//Z=z0+t(z1-z0)
	//programming-wise we cant store the formulas with "t" since we still don't know it's value
	//so we will temporarily store the independant terms and t's coeficients separately
	//and for the time being we ignore the "t"s
	VECTOR line_indeps;//independant terms (origin point)
	VECTOR line_coefs;//t's coeficients (direction vector)
	vec_set(line_indeps,line_p0);
	vec_set(line_coefs,line_p1);
	vec_sub(line_coefs,line_p0);
	
	//CHECK IF THE LINE IS PARALLEL TO THE PLANE
	//if the line is parallel we stop the function because we won't be able to return a point
	//when it is paralel either there is no point from the line matching any point on the plane
	//or if the line is parallel and on the plane there are an infinite amount of matching points
	//calculate if dot product (n1·v)==0?
	//n1 is the plane's normal and v is the line's direction vector (t's coeficients above)
	if((plane_N.x*line_coefs.x)+(plane_N.y*line_coefs.y)+(plane_N.z*line_coefs.z)==0)
	{
		return(0);
	}
	
	//GET PARAMETRIC EQUATION OF THE PLANE (Ax+By+Cz+D=0)
	//we use the plane's normal vector, a known point from the plane, and a second unknown point on the plane
	//pN=(A,B,C)
	//p0=(x0,y0,z0)
	//p1=(X,Y,Z)
	//get the vector formed by the two points on the plane
	//(X-x0,Y-y0,Z-z0)
	//dot product this vector and the plane's normal
	//(X-x0,Y-y0,Z-z0)·(A,B,C) = (AX-Ax0+BY-By0+CZ-Cz0)
	//group the known terms (-Ax0-By0-Cz0) as a number (D)
	//D=-Ax0-By0-Cz0
	//equate everything to zero and you have the plane's equation
	//Ax+By+Cz+D=0
	var plane_indep;//independant terms grouped as "D"
	VECTOR plane_coefs;//coeficients A,B,C
	plane_indep=-(plane_N.x*plane_p0.x)-(plane_N.y*plane_p0.y)-(plane_N.z*plane_p0.z);//D=-(Ax0)-(By0)-(Cz0)
	vec_set(plane_coefs,plane_N);
	
	//PLUG ECUATIONS OF OUR LINE INTO EQUATION OF THE PLANE
	//Ax+By+Cz+D=0 ->
	//A(x0+t(x1-x0))+B(y0+t(y1-y0))+C(z0+t(z1-z0))+D=0 ->
	//Ax0+At(x1-x0)+By0+Bt(y1-y0)+Cz0+Ct(z1-z0))+D=0
	vec_mul(line_indeps,plane_coefs);
	vec_mul(line_coefs,plane_coefs);
	
	//SOLVE FOR "t" IN OUR "LINE PLUGGED" VERSION OF THE EQUATION OF THE PLANE
	//Ax0+At(x1-x0)+By0+Bt(y1-y0)+Cz0+Ct(z1-z0))+D=0 ->
	//At(x1-x0)+Bt(y1-y0)+Ct(z1-z0) +(Ax0+By0+Cz0) +D = 0 ->
	//t(A(x1-x0)+B(y1-y0)+C(z1-z0)) +(Ax0+By0+Cz0) +D = 0 ->
	//t(A(x1-x0)+B(y1-y0)+C(z1-z0)) +(Ax0+By0+Cz0) = -D ->
	//t(A(x1-x0)+B(y1-y0)+C(z1-z0)) = -D-(Ax0+By0+Cz0) ->
	//t = (-D-(Ax0+By0+Cz0)) / (A(x1-x0)+B(y1-y0)+C(z1-z0)) ->
	var T;
	T=(-plane_indep-(line_indeps.x+line_indeps.y+line_indeps.z))/(line_coefs.x+line_coefs.y+line_coefs.z);
	
	//PLUG "t" BACK INTO EACH EQUATION OF OUR LINE TO GET THE INTERSECTION POINT'S COORDINATES
        //F(t)= (x0,y0,z0) + t(x1-x0,y1-y0,z1-z0)
	//resolving the above formula for each component, the resulting equations would be
	//X=x0+t(x1-x0)
	//Y=y0+t(y1-y0)
	//Z=z0+t(z1-z0)
	RESULT.x=line_p0.x+T*(line_p1.x-line_p0.x);
	RESULT.y=line_p0.y+T*(line_p1.y-line_p0.y);
	RESULT.z=line_p0.z+T*(line_p1.z-line_p0.z);
	//indicate that the line was not parallel to the plane and that
	//we found a unique intersection point that we stored in "RESULT"
	return(1);
}


I hope this was usefull for some of you!
Happy new year!


"The more you know, the more you realize how little you know..."

I <3 HORUS
http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=401929&page=1
Re: Line/Plane Intersection [Re: Carlos3DGS] #414870
01/09/13 16:02
01/09/13 16:02
Joined: Mar 2011
Posts: 3,150
Budapest
sivan Offline
Expert
sivan  Offline
Expert

Joined: Mar 2011
Posts: 3,150
Budapest
wow. thanks! this is exactly what I need very soon to exclude expensive c_traces on building and ladder surfaces! even very short rays can slow down my fps in case of hundreds of moving units, and fortunately building and ladder surface planes are stored in each tile, I'll need to add only normals. cool!


Free world editor for 3D Gamestudio: MapBuilder Editor
Re: Line/Plane Intersection [Re: sivan] #414874
01/09/13 16:33
01/09/13 16:33
Joined: Oct 2008
Posts: 513
Carlos3DGS Offline OP
User
Carlos3DGS  Offline OP
User

Joined: Oct 2008
Posts: 513
Your welcome! I'm glad it has already helped someone soo soon after posting!

If you want more speed you can remove the first "if". You just have to be carefull yourself with two of the parameters line_p1 and plane_N (line_p1 is never the same line_p0) and (plane_N is never (0,0,0)).
If your calls are correct this should never happen anyway (that first "if" was just a "newbie safeguard" I placed in there before posting that I dont actually have in my code, just in case someone tried to use this withought understanding what the function is meant for).
Nobody that knows what they are doing would ever do this anyway, the idea of a plane with no normal is silly at best, and defining a line with only one point is just plain stupid...
Code:
BOOL Line_Plane_Intersection(VECTOR* RESULT, VECTOR* line_p0, VECTOR* line_p1, VECTOR* plane_p0, VECTOR* plane_N)
{
	VECTOR line_indeps;
	VECTOR line_coefs;
	vec_set(line_indeps,line_p0);
	vec_set(line_coefs,line_p1);
	vec_sub(line_coefs,line_p0);
	if((plane_N.x*line_coefs.x)+(plane_N.y*line_coefs.y)+(plane_N.z*line_coefs.z)==0)
	{
		return(0);
	}
	var plane_indep;
	VECTOR plane_coefs;
	plane_indep=-(plane_N.x*plane_p0.x)-(plane_N.y*plane_p0.y)-(plane_N.z*plane_p0.z);
	vec_set(plane_coefs,plane_N);
	vec_mul(line_indeps,plane_coefs);
	vec_mul(line_coefs,plane_coefs);
	var T;
	T=(-plane_indep-(line_indeps.x+line_indeps.y+line_indeps.z))/(line_coefs.x+line_coefs.y+line_coefs.z);
	RESULT.x=line_p0.x+T*(line_p1.x-line_p0.x);
	RESULT.y=line_p0.y+T*(line_p1.y-line_p0.y);
	RESULT.z=line_p0.z+T*(line_p1.z-line_p0.z);
	return(1);
}



NOTE: You could also remove the second "if", the last "return(1)", and set the initialization to void, for even more speed as it is not necessary if you always make sure you never pass it a line parallel to the plane (but I don't recommend it as it is usually un-predictable and it would be harder to make sure yourself that they are never parallel).
There are only very specific cases where I would feel comfortable removing that second "if" myself.
For example if I was only using this to get an intersection from the camera to the floor and my camera was always slanted looking at it (a view that could never be at floor level with no tilt). Another safe case would be if it was only for straight angle walls (0,90,180,270,360) and the camera's pan could never be at a straight angle.

Happy new year present for you! wink


"The more you know, the more you realize how little you know..."

I <3 HORUS
http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=401929&page=1
Re: Line/Plane Intersection [Re: Carlos3DGS] #414876
01/09/13 17:09
01/09/13 17:09
Joined: Mar 2011
Posts: 3,150
Budapest
sivan Offline
Expert
sivan  Offline
Expert

Joined: Mar 2011
Posts: 3,150
Budapest
thanks for the further info, I will try it without the if-s, because I need only to check a vertical line vs. non-vertical surface plane, and speed is essential. I just have to redesign my database now laugh
the best would be for me to use 2 points vs. 3 points check as they in theory can define a line and a plane exactly. maybe it's not impossible to do as fast...

Last edited by sivan; 01/09/13 17:13.

Free world editor for 3D Gamestudio: MapBuilder Editor
Re: Line/Plane Intersection [Re: sivan] #414877
01/09/13 17:20
01/09/13 17:20
Joined: Oct 2008
Posts: 513
Carlos3DGS Offline OP
User
Carlos3DGS  Offline OP
User

Joined: Oct 2008
Posts: 513
I already have that done also, I did it on the bus earlier today. Just give me few mins to get on my laptop and search through my prototype code and I'll post the 3 point plane version for you.


"The more you know, the more you realize how little you know..."

I <3 HORUS
http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=401929&page=1
Re: Line/Plane Intersection [Re: sivan] #414879
01/09/13 17:35
01/09/13 17:35
Joined: Oct 2008
Posts: 513
Carlos3DGS Offline OP
User
Carlos3DGS  Offline OP
User

Joined: Oct 2008
Posts: 513
-line is defined by 2 points
-plane is defined by 3 points
-removed all if's and returns

Code:
void Line_Plane_Intersection(VECTOR* RESULT, VECTOR* line_p0, VECTOR* line_p1, VECTOR* plane_p0, VECTOR* plane_p1, VECTOR* plane_p2)
{
	VECTOR line_indeps;
	VECTOR line_coefs;
	vec_set(line_indeps,line_p0);
	vec_set(line_coefs,line_p1);
	vec_sub(line_coefs,line_p0);
	VECTOR plane_N;
	vec_cross(plane_N,vec_diff(NULL,plane_p1,plane_p0),vec_diff(NULL,plane_p2,plane_p0));
	var plane_indep;
	VECTOR plane_coefs;
	plane_indep=-(plane_N.x*plane_p0.x)-(plane_N.y*plane_p0.y)-(plane_N.z*plane_p0.z);
	vec_set(plane_coefs,plane_N);
	vec_mul(line_indeps,plane_coefs);
	vec_mul(line_coefs,plane_coefs);
	var T;
	T=(-plane_indep-(line_indeps.x+line_indeps.y+line_indeps.z))/(line_coefs.x+line_coefs.y+line_coefs.z);
	RESULT.x=line_p0.x+T*(line_p1.x-line_p0.x);
	RESULT.y=line_p0.y+T*(line_p1.y-line_p0.y);
	RESULT.z=line_p0.z+T*(line_p1.z-line_p0.z);
}


Is this what you wanted?
This code is un-tested, but should work as my new function was based on this. (This was done on the bus and my mini-laptop cannot run 3DGS, I just use it to write code and test later at home)

EDIT: Keep in mind this assumes an infinite plane in all directions! If you want it specific to a tile I could modify it to limit the planes. (and if you are working with terrains I already have a more specific version for that too that I worked on some time ago)

Last edited by Carlos3DGS; 01/09/13 18:12.

"The more you know, the more you realize how little you know..."

I <3 HORUS
http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=401929&page=1
Re: Line/Plane Intersection [Re: Carlos3DGS] #414882
01/09/13 18:36
01/09/13 18:36
Joined: Mar 2011
Posts: 3,150
Budapest
sivan Offline
Expert
sivan  Offline
Expert

Joined: Mar 2011
Posts: 3,150
Budapest
yes, this is what I mentioned. I think I won't have problem with tiles and this solution, because the line always vertical, and the plane never.
for terrain I do not need so exact values, I just store and use their middle pixel simply. maybe later if my code performance will be better... I just have to store additionally xy coords corresponding to the already stored maxz and minz values, and the middle coord is also already stored. but if the 3 points are producing a line, they do not determine a plane exactly, it could cause errors...
in case of buildings, more exactly mainly stairs and ladders, your code is required to replace the current c_tracings, but it will be also relatively easy to integrate it into my codes, by storing 3 tile corner values.


Free world editor for 3D Gamestudio: MapBuilder Editor

Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1