Sphere intersecting triangle
Blitz3D Forums/Blitz3D Programming/Sphere intersecting triangle
| ||
| I get the feeling this is simple enough, but once again my basic math repertoire stands in my way. I wish to make a function to determine whether a sphere at coords sX#, sY# and sZ#, with radius sR#, is intersecting a triangle described by x1#, y1#, z1#, x2#, y2#, z2#, x3#, y3# and z3#. I realize that Blitz's sphere-to-polygon collisions already take care of this in a way, but I only wish to check for intersections, not have an actual solid-body collision, plus Blitz collisions are often glitchy and require strange handling to get a proper reading from EntityCollided(). So, looking for a straight-math solution: how do I go about this? Keep in mind that I mostly only understand layman's terms for math; if you're going to refer to things like cross-products, be prepared to tell me what cross-products are (and yeah what are cross-products?). |
| ||
| i guess that you only need to calculate 3d distance between the center of the sphere to each of the 3 points 3d distance = SquareRooth(deltaX*deltaX + deltaY*deltaY + deltaZ*deltaZ) being deltas the difference between each axis between center of the sphere and one of the 3 points wich define the triangle If all distances are bigger than the radius then the triangle is outside if all are smaller, the triangle is inside and if some are bigger and some smaller the triangle is intersecting the sphere. Note that isn't needed to calculate the square root in each cases (wich some people like to evade for timings reasons), you may compare squared values, you only need to calculate Radius*Radius at first and then compare it between each distance3d without the squareroot operation. naturally, matematically could one of the distances be equal and is it intersecting, tangent etc... (probably not of interest or yes depending on your application. Seen from a vector point of view, you need to calculate the Magnitude of the vectors defined between the center of the sphere and each of the points wich define the triangle Another aproach could be to find the plane defined by the triangle and use some of the shelf routines to calculate distance between a plane to a point (the center of the sphere) and if it is smaller than the radius or bigger you find if the triangle is or not intersecting the sphere. Probably here you need to find a Normal vector to the plane formed by T1, T2, T3 (Tn = points wich define the triangle), wich will be paralell to the distance from the center of the sphere and the plane wich contains the triangle and... some other operations... the first one: get a vector normal to the plane is simple to find (for some strange people): A vector normal = CrossPorduct(Vector1, Vector2) being Vector1 = the vector from T1 to T2 Vector2 = the vector form T1 to T3 I currently don't understand it (if it make you feel better) but i used it somewhat in the past and it seems to work!, naturally each time i left them for a while i became completely ignorat about the subject. Juan Last edited 2012 Last edited 2012 Last edited 2012 |
| ||
| The first question must be why do you need this. Perhaps you could get away with some lesser, easier condition. A full solution to your question would be quite messy. It starts out easily. The triangle is a collection of points. We can check if a point is in a sphere by testing if the distance from the point to the center is not more than the radius. So in principal we do this for all points in the triangle, determining the minimum distance from a triangle point to the center. That tells us if the triangle intersects the sphere. But the devil is in the details. If that minimum distance point is in the interior of the triangle then calculus comes to the rescue and gives us the tools to solve this. But if that point is somewhere on the boundary then it gets tougher. We are reduced to handling a bunch of special cases. A little googling turned up some code which purports to do exactly this: Matlab code for Distance between Point and Triangle in 3D The comments in the code point to a pdf which discusses the problem and presents an algorithm. You may find the math incomprehensible but the general idea can still be gleaned. |
| ||
| Hmmm... So the fiddliness of the problem means that even a successful implementation is not as simple as I'd thought. Alright, that does make me personally feel better, but perhaps I should address Floyd's question now. It's for a ball-and-paddle collision checker, similar to Breakout. While normally this would be a simple If ball\x > leftPaddleEdge type of problem, there's a twist: the playing field is circular, and the paddle rotates around the perimeter rather than sliding back & forth at the bottom. What I ultimately need is a reliable way to check if a ball of variable radius bR# has collided with the paddle, which can change widths, position and most importantly, rotation. I learned some time ago that generally, in Blitz3D, collisions are fine if you want to stop something like a ball moving through a wall, but if you want to see if said ball is actually colliding with a wall then you're better off coding your own "collision" detection routine. Last edited 2012 |
| ||
| So this is essentially a 2D problem with moving circles and rectangles. The paddle is presumably impenetrable, so we need only consider the sides of the rectangle and this boils down to circle versus line segment intersection. That should be doable. The key factor is the nonlinear motion. That really cranks up the complexity. But the motion of the paddle is constrained to a predefined circular path. That takes away some of the complexity. Still, it sounds quite challenging. |
| ||
| this boils down to circle versus line segment intersection. .......... Oh good god I'm a complete idiot. I was completely overcomplicating this entire issue. I actually produced some code for my now-on-hold project of Midnight Hacker that addresses this exact problem: a circle intersecting a line at any arbitrary rotation or position. For some strange reason, I'd been thinking more in 3D terms for this and got wrapped up in the two polygons that make up the paddle's quad rather than the lines that form its actual hitbox perimeter.Thanks a mil Floyd, now I can get this whole thing cracked with a copy-paste and a little tailoring. Last edited 2012 |
   |