Example : Traingle Circle Collision :) | |

game_maker | Hi
I've seen an example for this in Almar's home page
and I have learned another method for the test from SuperC Here :
http://www.vbgamer.com/msgboard/topic.asp?TOPIC_ID=143
soo here is my test [:)]
Download Attachment: [url="http://www.vbgamer.com/msgboard/uploaded/game_maker/2004617192152_TriangleCollision.zip"][img]icon_paperclip.gif[/img]TriangleCollision.zip[/url]2.86 KB |

Eric Coleman | It doesn't always work. Here is a picture of what I'm talking about.
Download Attachment: [url="http://www.vbgamer.com/msgboard/uploaded/Eric Coleman/20046180159_failedtest.jpg"][img]icon_paperclip.gif[/img]failedtest.jpg[/url]21.02 KB |

game_maker | Yes,True and this is also happening to the code in Almar's home page that's why I added Accuracy if you put Accuracy = 256 for example you will have 99.99% (we can say 100%) it will test 256 point (in triangle) [:)] |

Sr. Guapo | But it will be much slower... |

game_maker | Also True, because we know speed = k / accuracy You can not (or let say) it's very hard to bind or find a relation between a curve (circle) and poly (triangle) and that's what both test's do [:)] Will if we can find the center of our triangle and make a radius and so a circle then check circler collision if true then check our test [8)] I didn't bring a new Idea for collision the Idea is totally same the procedures is sort of different [:)] |

VBBR | Do you know how to find the center point of a triangle? |

Sr. Guapo | There is a way to do it geometrically... It involves bisecting all the sides of the triagle and drawing perpendicular lines through the points. Assuming all goes well, that will give a point that can create a perfect circumscribed circle, the circumscribed midpoint (BTW, If you do a similar thing with the angles, you will get the INSCRIBED midpoint) I'm sure there is a way to do it algebraically, also... Try google [;)] |

VBBR | Yeah, I remembered that but I didn't remember exactly if it were the sides of the triangle or the angles or whatever [:D] That is what happens if you last about 2 years without seeing a similar thing in school... |

Sr. Guapo | You could just calculate 2 of the side midpoints (very easy since you know the endpoints) and the slope of each of those segments, then you can find the perpendicular lines and their intersection. It may be a little computationally expensive, but as long as you aren't doing it for 100,000 triangles per frame you should be okay... |

VBBR | Probably it will be needed only once, as long as the triangle shape doesn't change. I will try to do that with this example. |

VBBR | See, I just corrected the problem this code had just by adding a point-in-circle test for each vertex [:D]
Also added an FPS counter. Get it here...
EDIT: Also, using this pre-check, an accuracy of 16 should be more than enough. 8 is already good (acceptable) for not very precise checking. (I have tested both)
Download Attachment: [url="http://www.vbgamer.com/msgboard/uploaded/VBBR/2004619161645_TriangleCollision.zip"][img]icon_paperclip.gif[/img]TriangleCollision.zip[/url]3.47 KB Gotta work on the center-point calculation now... |

Serpwidgets | Hmm... when checking a collision between a line segment and a circle, there are two possible cases where there is an intersection: 1- An endpoint of the segment is within the circle. 2- the line segment collides with a radius of the circle which is perpendicular to the segment. If neither of these cases are true, there is no collision. Out of curiosity, are you talking 2-d or 3-d objects (circles or spheres?) and are you working in 2-d or 3-d space? Here's my method of determining 2-d line segment collisions within 2-d space. I didn't thoroughly check what was in the attachments, but I saw sin and cos and other really slow functions being used, so I thought this might help. :) ---- [code] ''''Returns only true or false, doesn't care about location 'this function at most performs the following number of operations: 'Multiply = 6 'Divide = 2 'add/sub = 15 'Local Subobject lookups = 24 'Global subobject lookups = 0 Public Function CollideSegments(p1 As Vert2d, p2 As Vert2d, p3 As Vert2d, p4 As Vert2d) As Boolean Dim t As Single, s As Single 'determinants of the 2d matrices Dim theta As Single 'bottom of s&t equations theta = ((p2.X - p1.X) * (p3.Y - p4.Y)) - ((p2.Y - p1.Y) * (p3.X - p4.X)) s = (((p2.X - p1.X) * (p3.Y - p1.Y)) - ((p2.Y - p1.Y) * (p3.X - p1.X))) / theta 's is the porportion, from point 3 of line 2, of the length of line2 at which the collision occurs If s < 1 Then 'if the number is >1 or <0 then it's not within the length of the line... If s > 0 Then t = (((p3.X - p1.X) * (p3.Y - p4.Y)) - ((p3.Y - p1.Y) * (p3.X - p4.X))) / theta 't is the porportion, from point 1 of line 1, of the length of line 1 at which the collision occurs If t < 1 Then If t > 0 Then CollideSegments = True End If '0 < t < 1 End If End If '0 < s < 1 End If End Function[/code] |

game_maker | Nice [;)]
this would increase some accuracy at corners
hmmmm, I have add a Circle to Circle Collision to fast our collision
OK now we have :
- Point in Triangle Test
- Point in Circle Test
- Circle-Circle Test
Download Attachment: [url="http://www.vbgamer.com/msgboard/uploaded/game_maker/2004619173527_Triangle Collision.zip"][img]icon_paperclip.gif[/img]Triangle Collision.zip[/url]3.33 KB |

game_maker | you can avoid sin & cos functions if you identify your accuracy (you know what I mean ? )[:)] BTW : is there an use for this test (I never programmed 2D Game) [8)] |

VBBR | I have just made a small modification, put an "Abs" before the subtract operations in the distance calculations. We must work with absolute values because if you put negative numbers it will go crazy [:)]
Download Attachment: [url="http://www.vbgamer.com/msgboard/uploaded/VBBR/200461918295_Triangle Collision.zip"][img]icon_paperclip.gif[/img]Triangle Collision.zip[/url]3.55 KB |

game_maker | VBBR : My friend we don't need abs() ,, [code] (a - b) * (a - b) [/code] Is Always positive [:)] assume c = (a - b) then [code] (a - b) * (a - b) [/code] = [code] c * c [/code] = [code] c ^ 2 [/code] that's why it's always positive [:)] |

VBBR | Oh sorry for forgetting that. It's very simple math. A number to the power 2 is always positive because positive*positive=positive and negative*negative=positive also. Since the numbers are the same, they gotta be positive or negative both. Thanks for remembering. |