Qbasicnews.com

QBasic => QB Discussion & Programming Help => Topic started by: relsoft on July 05, 2004, 11:25:16 PM



Title: 2d pixel-Triangle collision?
Post by: relsoft on July 05, 2004, 11:25:16 PM
can anyone point me to an article or tel me a fat algo?

Thanks!!!!


Title: 2d pixel-Triangle collision?
Post by: webberboy on July 05, 2004, 11:35:29 PM
well, i don't know, but my idea for the algorithm would have to do with the slopes of the lines in the triangle.  Dunno.  try it.


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 05, 2004, 11:38:52 PM
I have that idea also, but if there's a faster way....

Slope would mean checking which side of the line the point lies(- ot +)

Ax+by+c = sign


Title: 2d pixel-Triangle collision?
Post by: DrV on July 06, 2004, 10:44:12 AM
I had an old DDJ mag (ca. 2000) with an article about 2d point to triangle intersection or something like that... I'll see if I can find it again if that would be helpful

Edit:  Dr. Dobbs Journal, Aug. 2000, "Triangle Intersection Tests" by Tomas Möller.  But you need to pay to get the article. :(  Maybe I can type it in at home if I get some time. :)


Title: 2d pixel-Triangle collision?
Post by: Rhiannon on July 06, 2004, 02:34:33 PM
Scanning it would probably be faster if you have access to one.


Title: 2d pixel-Triangle collision?
Post by: DrV on July 06, 2004, 02:40:51 PM
Ingenious!  Boy, am I dumb... I have a scanner, but I don't have OCR software, so it'll be an image (prolly JPEG). Oh well; diagrams are better that way, anyhow.  No ascii art for me!


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 06, 2004, 10:53:29 PM
Url?

Thanks!!!


Title: 2d pixel-Triangle collision?
Post by: Mango on July 06, 2004, 11:48:27 PM
Quote from: "DrV"
Ingenious!  Boy, am I dumb... I have a scanner, but I don't have OCR software, so it'll be an image (prolly JPEG). Oh well; diagrams are better that way, anyhow.  No ascii art for me!


If the original is b&w, and if you have access to good image-editing software, it is often better (more readable/higher compression) to use a GIF or TIFF-LZW or PNG using 2 or 4 color palette, imo.

FWIW

Mango


Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 07, 2004, 02:57:57 AM
Yes rel I can. A guy (named Azuroth aka asmodeus) taught me this. It uses a WhichSide algo which determines what side of a line a 2d coordinate is. For a triangle collision, you see what sides of each 3 lines the centre of the triangle is in, and compare those sides with the testing 2d coordinate. If they all match, your inside the triangle.

This is because the centre of a triangle is always inside the triangle.

I have a sample program (http://hybd.net/~mms/Temp/PIX-TRI.BAS) and heres the algo:

Code:

'returns true if the (x!, y!) coordinate is inside the triangle
FUNCTION insidetri% (x!, y!, x1!, y1!, x2!, y2!, x3!, y3!)
 cx! = (x1! + x2! + x3!) / 3
 cy! = (y1! + y2! + y3!) / 3

 sideA1 = whichside(cx!, cy!, x1!, y1!, x2!, y2!)
 sideA2 = whichside(cx!, cy!, x1!, y1!, x3!, y3!)
 sideA3 = whichside(cx!, cy!, x2!, y2!, x3!, y3!)

 sideB1 = whichside(x!, y!, x1!, y1!, x2!, y2!)
 sideB2 = whichside(x!, y!, x1!, y1!, x3!, y3!)
 sideB3 = whichside(x!, y!, x2!, y2!, x3!, y3!)

 insidetri% = (sideA1 = sideB1) AND (sideA2 = sideB2) AND (sideA3 = sideB3)
END FUNCTION

'checks what side of a line a pixel is
'(returns true or false for different sides)
'(x!, y!) are coordinates of 2d pixel
'(x1!, y1!) -> (x2!, y2!) are coordinates of a line
FUNCTION whichside% (x!, y!, x1!, y1!, x2!, y2!)
        dx! = x2! - x1!
        dy! = y2! - y1!

        IF dx! = 0 THEN
                whichside = x! < dx!
        ELSEIF dy! = 0 THEN
                whichside = y! < dy!
        ELSE
                Vg! = dy! / dx!
                cy! = Vg! * (x! - x1!) + y1!
                whichside = y! < cy!
        END IF
END FUNCTION


Title: 2d pixel-Triangle collision?
Post by: DrV on July 07, 2004, 02:30:29 PM
http://quickhost.qbtk.com/download.php?id=100


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 09, 2004, 02:42:12 AM
drV: thanks!!!

Nex: Thanks too!!! I've used the same algo. Ax+by+c = sign to test which side a pixel is. Sadly, it's not fast enough. :*(.  I was thinking of a scanline based collision if its possible.


Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 09, 2004, 07:09:59 AM
Not fast enough? Put in a quick bounding box check first then to disregard all absolutely out of range points and it should be speedy.

I cant think of anything that will speed it up any further.

What are you using this for anyway? It shouldnt really be the main slowdown part.


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 10, 2004, 02:24:13 AM
Sprite to poly collision.  I'll try to make a fixed point asm one to see the speed. :*)

BTW, AFlib and Rellib are gonna have 3d stuff after all!!!


Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 10, 2004, 05:52:36 AM
Cool. Well in that case it totally changes the algorithm your gonna need. Do you mean rectangle <-> triangle collision, or sprite <-> triangle collision not including transparancy?

If you do have to take into account transparancies, for speed you will probably have to have easy checks to rule out as much cases as possible before doing the slow pixel by pixel check.

Like (1) box <-> box collision detection (2) box  <-> triangle collision (3) pixel <-> triangle collision.

Or something, i duno.


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 11, 2004, 04:17:15 AM
Here's an idea.

1.  Boxbound the check
2.  if tribox and spritebox overlap...
3. check scanline per scanline, clipping outofbounds pixels off.

I don't know if that would be fast as compared to making like collision points for each sprite and just check those points.

any thoughts?


Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 11, 2004, 05:43:03 AM
Yeah that could be better. but then you may have to check if the triangle is within the sprite aswell (for small triangles).

But i duno.

Also why do you need sprites in a 3d engine?


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 12, 2004, 02:24:38 AM
No its a 2d/3d game combo I envisioned. 2d gameplay with 2d sprites. Big 3d bosses. :*)

BTW, if you are interestred, I have just converted insidetri in ASM. :*)

Works freaking fast too!!!!


Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 12, 2004, 05:16:15 AM
ah sounds cool :)


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 15, 2004, 03:45:02 AM
See it in action:
http://rel.betterwebber.com/MyProgs/Darius.zip

ASMcode:



Code:


;;;Pixel to triangle collision detection
;;;Call with:
;;;Declare sub RelInsideTri(Byval x%, Byval y%,Byval x1%, Byval y1%, Byval x2%, Byval y2%, Byval x3%, Byval y3%)

.Model Medium, BASIC
.386
.Code

align 2

;;*****************Near procedure for which side**********************************************************
Whichside      Proc  Near
Local x: word
Local y: word
Local x1: word
Local y1: word
Local x2: word
Local y2: word
Local Wside: byte

;expects
;ax = y2
;bx = x2
;cx = x1
;dx = y1
;fs = x
;gs = y
mov y2, ax
mov x2, bx
mov x1, cx
mov y1, dx

mov ax, fs
mov dx, gs
mov x, ax
mov y, dx


mov wside, 0
        mov bx, x2 ;bx% = x2%
        mov cx, x1
        sub bx, cx ;bx% = bx% - x1%
        ;IF bx% <> 0 THEN

        jnz @dxNot0

            mov dx, x ;dx% = x%
            cmp bx, dx ;IF bx% > dx% THEN
            Jle @noside1
                mov wside, -1

                jmp @Texit

@noside1:
                mov wside, 0

                jmp @Texit

@dxNot0:
        mov ax, y2 ;ax% = y2%
        mov dx, y1
        sub ax, dx ;ax% = ax% - y1%
        ;IF ax% <> 0 THEN
        jnz @dyNot0

            mov cx, y ;cx% = y%
            cmp ax, cx ;IF ax% > cx% THEN
            Jle @Noside2
                mov wside, -1

                jmp @Texit

@Noside2:
                mov wside, 0

                jmp @Texit


@dyNot0:
    ;ax = ady
    ;bx = adx
    ;cx = y
    ;dx = x
                ;dx% = (x2% - x1%)
                ;dy& = (y2% - y1%) * 256&

                shl eax, 16 ;xeax& = ax% * 256&       'dy*256
                cdq ;edxeax& = eax&          'cdq
                movsx ecx, bx ;ebx& = bx%              'movsx ebx, bx
                idiv ecx ;eax& = edxeax& \ ebx&   'idiv ebx          'vg&=eax

                ;Vg& = dy& \ dx%
                ;ddx% = (x% - x1%)
                mov cx, x ;cx% = x%
                sub cx, x1 ;cx% = cx% - x1%
                movsx ebx, cx
                imul eax, ebx ;eax& = eax& * cx%       'imul eax, cx
                mov dx, y1 ;dx% = y1%

                shl edx, 16 ;edx& = dx% * 256&
                ;cy& = Vg& * ddx% + (y1% * 256&)
                add eax, edx ;eax& = eax& + edx&
                ;whichside = (y% * 256&) < cy&
                mov bx, y ;bx% = y%

                shl ebx, 16 ;ebx& = bx% * 256&
                cmp eax, ebx ;IF eax& > ebx& THEN
                jle @noside3
                    mov wside, 0
                    jmp @Texit

@noside3:
                    mov wside, -1


@Texit:
mov al, wside

Ret


EndP


;;*****************Procedure for InsideTri*****************************************************************

Public  RelInsideT
RelInsideT proc \
            x:word, y:word, x1:word, y1:word, x2:word, y2:word,x3:word, y3:word

            Local sideA1:   Byte
            Local sideA2:   Byte
            Local SideA3:   Byte
            Local sideB1:   Byte
            Local sideB2:   Byte
            Local SideB3:   Byte
            Local cenx: word
            Local ceny: word


          ;clip
            mov ax, x1
            cmp ax, x2
            jle @noswapx1
mov ax, x2
@noswapx1:
cmp ax, x3
jle @noswapx2
mov ax, x3
@noswapx2:
            mov bx, x1
            cmp bx, x2
            jge @noswapx3
mov bx, x2
@noswapx3:
cmp bx, x3
jge @noswapx4
mov bx, x3
@noswapx4:

;ax = x1
;bx = x2

          ;clip
            mov cx, y1
            cmp cx, y2
            jle @noswapy1
mov cx, y2
@noswapy1:
cmp cx, y3
jle @noswapy2
mov cx, y3
@noswapy2:
            mov dx, y1
            cmp dx, y2
            jge @noswapy3
mov dx, y2
@noswapy3:
cmp dx, y3
jge @noswapy4
mov dx, y3
@noswapy4:
;cx = y1
;dx = y2

;test coord

cmp x, ax
jl @NoInside
cmp x, bx
jg @NoInside
cmp y, cx
jl @NoInside
cmp y, dx
jg @NoInside


;Start insideT
            ;cx% = (x1% + x2% + x3%) \ 3
            mov ax, x1
            add ax, x2
            add ax, x3
            mov bx,3
            cwd
            idiv bx
            ;cbw
            mov cenx, ax

  ;cy% = (y1% + y2% + y3%) \ 3
  mov ax, y1
            add ax, y2
            add ax, y3
            mov bx, 3
            cwd
            idiv bx
            ;cbw
            mov ceny, ax

  ;Whichside expects
;ax = y2
;bx = x2
;cx = x1
;dx = y1
;fs = x
;gs = y


  ;sideA1 = whichside(cx%, cy%, x1%, y1%, x2%, y2%)
  mov dx, cenx
  mov cx, ceny
  mov fs, dx
  mov gs, cx

  mov ax, y2
  mov bx, x2
  mov cx, x1
  mov dx, y1
  call whichside
  mov sideA1, al

  ;sideA2 = whichside(cx%, cy%, x1%, y1%, x3%, y3%)
  mov dx, cenx
  mov cx, ceny
  mov fs, dx
  mov gs, cx

  mov ax, y3
  mov bx, x3
  mov cx, x1
  mov dx, y1
  call whichside
  mov sideA2, al
  ;sideA3 = whichside(cx%, cy%, x2%, y2%, x3%, y3%)
  mov dx, cenx
  mov cx, ceny
  mov fs, dx
  mov gs, cx

  mov ax, y3
  mov bx, x3
  mov cx, x2
  mov dx, y2
  call whichside
  mov sideA3, al
  ;sideB1 = whichside(x%, y%, x1%, y1%, x2%, y2%)
  mov dx, x
  mov cx, y
  mov fs, dx
  mov gs, cx

  mov ax, y2
  mov bx, x2
  mov cx, x1
  mov dx, y1
  call whichside
  mov sideB1, al
  ;sideB2 = whichside(x%, y%, x1%, y1%, x3%, y3%)
  mov dx, x
  mov cx, y
  mov fs, dx
  mov gs, cx

  mov ax, y3
  mov bx, x3
  mov cx, x1
  mov dx, y1
  call whichside
  mov sideB2, al
  ;sideB3 = whichside(x%, y%, x2%, y2%, x3%, y3%)
  mov dx, x
  mov cx, y
  mov fs, dx
  mov gs, cx

  mov ax, y3
  mov bx, x3
  mov cx, x2
  mov dx, y2
  call whichside
  mov sideB3, al

  ;insidetri% = (sideA1 = sideB1) AND (sideA2 = sideB2) AND (sideA3 = sideB3)
  mov al, sideA1
  mov bl, sideB1
  cmp al, bl
  jne @NoInside

  mov cl, sideA2
  mov dl, sideB2
  cmp cl, dl
  jne @NoInside

        mov al, sideA3
  mov bl, sideB3
  cmp al, bl
  jne @NoInside
  mov ax, -1


@exit:

Ret

@NoInside:
xor ax, ax
ret

EndP

End



Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 16, 2004, 02:41:27 AM
Damn that is tight! It looks like the playstation :)

Good work man.


Title: 2d pixel-Triangle collision?
Post by: relsoft on July 16, 2004, 04:01:39 AM
Yeah, the idea came from G-Darius. :*).  But without your code, I could not have made it fast.  Thanks!!!


Title: 2d pixel-Triangle collision?
Post by: Nexinarus on July 16, 2004, 05:39:11 AM
No problem man. Anything to share knowlege.