[2D]Line-Line Collision detect

[Farabi]

Code Select Expand



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

Code Select Expand


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.

[Evan_]

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.

[johnsa]

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:

Code Select Expand



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


[dedndave]

2 lines are parallel if and only if their slopes are identical
m₁ = m₂

[MichaelW]

2 lines are parallel if and only if their slopes are identical

...and they lie in a single plane.

[Farabi]

honestly i dont understand how it work but it worked. im no expert at math.

[dedndave]

thatnks Michael   :t

Dr Emmett Brown: "You're not thinking four dimensionally!"

[Farabi]

I found this formula for the 3D version one but I dont know how to calculate t value

Kita mulai dari rumus berikut


pertama cari dulu invers dari matrix bujur sangkar 3x3 di atas.

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


where the determinant of A can be computed by applying the rule of Sarrus as follows:


If the determinant is non-zero, the matrix is invertible, with the elements of the above matrix on the right side given by


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

xp=xa+(xb-xa).t
yp=ya+(yb-ya).t
zp=za+(zb-za).t

[KeepingRealBusy]

I hate to tell you this, but Sedgewick gives a simple algo in his Algorithms book.

Dave.

[dedndave]

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

[FORTRANS]

I found this formula for the 3D version one but I dont know how to calculate t value

[Snip]

Here is the formula

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

[Farabi]

Hi,
Thanks but I still dont get it. I think I digg more on this subject.