Post
by albinopapa » November 17th, 2018, 7:10 pm
Point in [ insert shape ] is probably mostly pretty easy.
// Point in Circle
Check distance from center to point; if less or equal then change point
// Point in Triangle
Check barycentric coordinate, if all three coordinates are between 0.f and 1.f then point is in triangle
// Point in Rect
Check if greater than left and top, and less than right and bottom
// Polygon with convex hull, ( all left turns or all right turns to each vertex )
Check bounding rect first, then if passes, since it's a convex polygon, you can easily check barycentric coordinates of generated triangles using the center ( sum of all vertices / total number of vertices ) as a vertex. If there are a lot of vertices, you could even break the polygon into quadrants ( think quadtree ).
For more complex shapes and point, like concave polygon and point I'm not entirely sure. I want to say I've seen an algorithm somewhere or maybe even in one of chili's old Advanced or HUGS videos where he makes the ship.
For different shapes colliding with different shapes, there's circle/circle, ray/circle, rect/circle, segment/segment, rect/segment, rect/rect, polygone/circle, segment/polygon.
I'm sure there are more, came across a post while looking up contact manifold that talked about point/cylinder and cylinder/cone for 3D collision, though I didn't fully understand everything they were discussing.
On a project awhile back, I needed to figure out if a line was going through a rectangle. I still don't know how to do it "the right way", but what I ended up doing was getting the slope of the line and comparing it to the slopes of the lines going from each of the corners of the rectangle to the origin of the original line ( in this case it was a ship firing a laser, so I guess a ray is more accurate ). This seemed to work for my purposes though if I recall, there was a fair bit of branching.
Since you understand quite a bit of math, you might look through the Box2D library and see if it gives you some ideas for the different types of collision detection that is supports, perhaps it has something you could use.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com