+- Qbasicnews.com (http://qbasicnews.com/newforum)
+-- Forum: QBasic (http://qbasicnews.com/newforum/forum-4.html)
+--- Forum: QB Discussion & Programming Help (http://qbasicnews.com/newforum/forum-11.html)
+--- Thread: 2d pixel-Triangle collision? (/thread-4266.html)
2d pixel-Triangle collision? - relsoft - 07-06-2004
can anyone point me to an article or tel me a fat algo?
Thanks!!!!
2d pixel-Triangle collision? - webberboy - 07-06-2004
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.
2d pixel-Triangle collision? - relsoft - 07-06-2004
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
2d pixel-Triangle collision? - DrV - 07-06-2004
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. 
2d pixel-Triangle collision? - Rhiannon - 07-06-2004
Scanning it would probably be faster if you have access to one.
2d pixel-Triangle collision? - DrV - 07-06-2004
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!
2d pixel-Triangle collision? - relsoft - 07-07-2004
Url?
Thanks!!!
2d pixel-Triangle collision? - Mango - 07-07-2004
Quote: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
2d pixel-Triangle collision? - Nexinarus - 07-07-2004
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 FUNCTION2d pixel-Triangle collision? - DrV - 07-07-2004
http://quickhost.qbtk.com/download.php?id=100