News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

[2D]Line-Line Collision detect

Started by Farabi, December 18, 2013, 05:35:11 PM

Previous topic - Next topic

Farabi



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.
http://farabidatacenter.url.ph/MySoftware/
My 3D Game Engine Demo.

Contact me at Whatsapp: 6283818314165

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:



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
m1 = m2

MichaelW

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.
Well Microsoft, here's another nice mess you've gotten us into.

Farabi

honestly i dont understand how it work but it worked. im no expert at math.
http://farabidatacenter.url.ph/MySoftware/
My 3D Game Engine Demo.

Contact me at Whatsapp: 6283818314165

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

Quote from: mhyworld on January 14, 2014, 06:25:08 PM
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
Quote
xp=xa+(xb-xa).t
yp=ya+(yb-ya).t
zp=za+(zb-za).t
http://farabidatacenter.url.ph/MySoftware/
My 3D Game Engine Demo.

Contact me at Whatsapp: 6283818314165

KeepingRealBusy

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

Dave.

dedndave

#9
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

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

Farabi

Hi,
Thanks but I still dont get it. I think I digg more on this subject.
http://farabidatacenter.url.ph/MySoftware/
My 3D Game Engine Demo.

Contact me at Whatsapp: 6283818314165