Line struct
X1 POINT <0>
X2 POINT <0>
Line ends
f2DLineCollisionDetect proc uses esi edi lpLine:dword,lpLine2:dword,lpPointResult:Dword
LOCAL dX1,dX2,dY1,dY2:dword
LOCAL C1,C2,M1,M2:real4
LOCAL tmpM,tmpC,tmp:real4
; m=dY/dX
; C=y-(m*x1)
; x=(C2-C1)/m1-m2 y=(m1*x)+c1
mov esi,lpLine
mov edi,lpLine2
mov ecx,[esi].Line.X2.x
mov eax,[esi].Line.X1.x
sub ecx,eax
mov dX1,ecx
mov esi,lpLine
mov edi,lpLine2
mov ecx,[esi].Line.X2.y
mov eax,[esi].Line.X1.y
sub ecx,eax
mov dY1,ecx
mov esi,lpLine
mov edi,lpLine2
mov ecx,[edi].Line.X2.x
mov eax,[edi].Line.X1.x
sub ecx,eax
mov dX2,ecx
mov esi,lpLine
mov edi,lpLine2
mov ecx,[edi].Line.X2.y
mov eax,[edi].Line.X1.y
sub ecx,eax
mov dY2,ecx
;M1
;m=dY/dX
fild dY1
fidiv dX1
fstp M1
;M2
fild dY2
fidiv dX2
fstp M2
;C1
;C=y1-(m*x1)
fld M1
fimul [esi].Line.X1.x
fstp tmp
fild [esi].Line.X1.y
fsub tmp
fstp C1
;C2
fld M2
fimul [edi].Line.X1.x
fstp tmp
fild [edi].Line.X1.y
fsub tmp
fstp C2
mov edx,lpPointResult
;x=(C2-C1)/m1-m2
fld C2
fsub C1
fstp tmpC
fld M1
fsub M2
fstp tmpM
fld tmpC
fdiv tmpM
fistp [edx].POINT.x
;y=(m1*x)+c1
fld M1
fimul [edx].POINT.x
fadd C1
fistp [edx].POINT.y
ret
f2DLineCollisionDetect endp
Test Case
mov L1.X1.x,50
mov L1.X1.y,70
mov L1.X2.x,200
mov L1.X2.y,250
mov L2.X1.x,250
mov L2.X1.y,50
mov L2.X2.x,50
mov L2.X2.y,350
invoke glEnable,GL_COLOR_MATERIAL
; invoke Enter_2D_Mode,FP4(640.),FP4(480.)
invoke glBegin,GL_LINES
invoke glColor3f,FP4(0.),FP4(0.),FP4(1.)
invoke glVertex2iv,addr L1.X1
invoke glVertex2iv,addr L1.X2
invoke glColor3f,FP4(0.),FP4(1.),FP4(0.)
invoke glVertex2iv,addr L2.X1
invoke glVertex2iv,addr L2.X2
invoke glEnd
; invoke Leave_2d_Mode
invoke f2DLineCollisionDetect,addr L1,addr L2,addr Result
invoke glBegin,GL_LINES
invoke glColor3f,FP4(1.),FP4(0.),FP4(0.)
invoke glVertex2iv,addr L1.X2
invoke glVertex2iv,addr Result
invoke glEnd
Correction and suggestion are welcome.
Yeah looks complicated.
I would be sure you know where your points are.
Maybe you should connect the dots and not read the screen's pixels instead read the imaginary ones your project I hope uses.
There are many exceptions with 2 lines.
They can be parallel.
They can intercept at their starts/ends technically.
I hope these lines you speak of have length.
They do have to be drawn somehow.
If they have shorter lengths they ought to intercept less.
Hey,
Just quickly skimmed your code, it appears you're trying to find the y-intercept of the 2 lines from their slope-intercept equation form y=mx+c?
The first thing to note is that there is a difference between knowing if two "lines" intersect or if two "line segments" intersect. In the first case any 2 lines will intersect if they're not parallel. I assume for practicality sake it is the later that you're interested in IE: 2 line segments.
Usually the best way to test for this is to first check if the 2 lines are co-linear (will be parallel but essentially the same line so will intersect if there is an overlap) then check if they're parallel (cross product = 0) in which case they don't intersect. From there you use the lines in a parametric form of P(t) = P0 + t*(P1-P2) with 0 <= t >= 1.0. Then you find the intersection point derive t1 and t2 from that and check to make sure its between 0 and 1 for both line segments.
Once again I would use SIMD for this if you're planning on testing multiple intersections rather than the slower (albeit more precise) FPU.
some sample code in javascript:
function SegIntersects(x1,y1,x2,y2,x3,y3,x4,y4)
{
var CmP = new vector2d(x3 - x1, y3 - y1);
var r = new vector2d(x2 - x1, y2 - y1);
var s = new vector2d(x4 - x3, y4 - y3);
var CmPxr = crossProduct(CmP,r);
var CmPxs = crossProduct(CmP,s);
var rxs = crossProduct(r,s);
if (Math.abs(CmPxr) < 0.00001)
{
// Lines are collinear, and so intersect if they have any overlap
return ((x3 - x1 < 0) != (x3 - x2 < 0)) || ((y3 - y1 < 0) != (y3 - y2 < 0));
}
if (Math.abs(rxs) < 0.00001)
return false; // Lines are parallel.
var rxsr = 1.0 / rxs;
var t = CmPxs * rxsr;
var u = CmPxr * rxsr;
return (t >= 0) && (t <= 1) && (u >= 0) && (u <= 1);
}
2 lines are parallel if and only if their slopes are identical
m1 = m2
Quote from: dedndave on January 08, 2014, 09:52:01 PM
2 lines are parallel if and only if their slopes are identical
...and they lie in a single plane.
honestly i dont understand how it work but it worked. im no expert at math.
thatnks Michael :t
Dr Emmett Brown: "You're not thinking four dimensionally!"
I found this formula for the 3D version one but I dont know how to calculate t value
Quote from: mhyworld on January 14, 2014, 06:25:08 PM
Kita mulai dari rumus berikut
(http://upload.wikimedia.org/math/b/4/d/b4d9132cf7ad93d5d3f11a81089fad69.png)
pertama cari dulu invers dari matrix bujur sangkar 3x3 di atas.
http://en.wikipedia.org/wiki/Matrix_inverse#Inversion_of_3.C3.973_matrices (http://en.wikipedia.org/wiki/Matrix_inverse#Inversion_of_3.C3.973_matrices)
Inversion of 3×3 matrices
A computationally efficient 3x3 matrix inversion is given by
(http://upload.wikimedia.org/math/a/e/4/ae4b131d68af9eb132ee40d05bc13292.png)
where the determinant of A can be computed by applying the rule of Sarrus as follows:
(http://upload.wikimedia.org/math/9/4/0/94053567c5d54e9ff2e7a4520fd667c5.png)
If the determinant is non-zero, the matrix is invertible, with the elements of the above matrix on the right side given by
(http://upload.wikimedia.org/math/b/d/d/bddd8fa7c35f9286e37802e8e40fdbd8.png)
tinggal dimasukkan
a=xa-xb, b=x1-x0, c=x2-x0
d=ya-yb, e=y1-y0, f=y2-y0
g=za-zb, h=z1-z0, i=z2-z0
dari situ akan diperoleh invers matrix yang dicari. Memang akan melelahkan jika dikerjakan secara manual, namun jika menggunakan pemrograman komputer tidak terlalu sulit, tinggal mendefinisikan variabel dan memasukkan persamaan-persamaan di atas.
misalkan hasil invers matrix di atas adalah
J K L
M N O
P Q R
nilai t dapat dihitung dengan rumus perkalian matrix dot product, t=J(xa-x0)+K(ya-y0)+L(za-z0).
Here is the formula
Quote
xp=xa+(xb-xa).t
yp=ya+(yb-ya).t
zp=za+(zb-za).t
I hate to tell you this, but Sedgewick gives a simple algo in his Algorithms book.
Dave.
solving a matrix is fairly basic, by itself
but, i quickly learned that it's important to know the rules and identities
they can make for faster code - sometimes, much faster
so - i have to do a bit of review on this subject, myself :P
Quote from: Farabi on January 16, 2014, 03:09:03 PM
I found this formula for the 3D version one but I dont know how to calculate t value
[Snip]
Here is the formula
Quote
xp=xa+(xb-xa).t
yp=ya+(yb-ya).t
zp=za+(zb-za).t
Hi,
That formula is a linear interpolation with '?p' going from '?a' at
t = 0.0, to '?b' at t = 1.0. So xp at t = 0.5, would be (xa + xb)/2.0.
Or the equivalent xp = xa + (xb - xa) * 0.5.
Cheers,
Steve
Hi,
Thanks but I still dont get it. I think I digg more on this subject.