Qbasicnews.com
April 10, 2020, 04:22:22 PM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1] 2
  Print  
Author Topic: 2d pixel-Triangle collision?  (Read 7271 times)
relsoft
*/-\*
*****
Posts: 3927



WWW
« on: July 05, 2004, 11:25:16 PM »

can anyone point me to an article or tel me a fat algo?

Thanks!!!!
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
webberboy
Member
*
Posts: 95



WWW
« Reply #1 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.
Logged

url=http://webberboy.no-ip.com]Fine Hand-Crafted Pens[/url]
Pneumonoultramicroscopicsilicovolcanoconiosis:  Noun, A hypothetical, invented disease of the lungs, caused by inhaling mineral or metallic dust, such as silicon and quartzite, over a long period.]
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #2 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
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
DrV
Na_th_an
*****
Posts: 1553



WWW
« Reply #3 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. Sad  Maybe I can type it in at home if I get some time. Smiley
Logged
Rhiannon
Been there, done that
*****
Posts: 1031



WWW
« Reply #4 on: July 06, 2004, 02:34:33 PM »

Scanning it would probably be faster if you have access to one.
Logged

igitalblackie.com - Done! Smiley Ask about our hosting Wink

-Goddess of the of the No More Religion Threads movement Smiley
DrV
Na_th_an
*****
Posts: 1553



WWW
« Reply #5 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!
Logged
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #6 on: July 06, 2004, 10:53:29 PM »

Url?

Thanks!!!
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
Mango
Wandering Guru
***
Posts: 360



« Reply #7 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
Logged
Nexinarus
Wandering Guru
***
Posts: 301



WWW
« Reply #8 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 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
Logged
DrV
Na_th_an
*****
Posts: 1553



WWW
« Reply #9 on: July 07, 2004, 02:30:29 PM »

http://quickhost.qbtk.com/download.php?id=100
Logged
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #10 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.
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
Nexinarus
Wandering Guru
***
Posts: 301



WWW
« Reply #11 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.
Logged
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #12 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!!!
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
Nexinarus
Wandering Guru
***
Posts: 301



WWW
« Reply #13 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.
Logged
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #14 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?
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
Pages: [1] 2
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!