1

i am programming a C++ collision detection in my game and am trying to come up with an algorithm: I have a capsule defined with two center points (C1, C2), length and a radius. Then i have a ray defined with two points (R1, R2). I already know that they are intersecting. I just need to find inner part of ray that is contained in capsule (H1-H2). Thanks in advance for all the help.

image

EvilTak
  • 7,091
  • 27
  • 36
grynca
  • 37
  • 4
  • This attitude is exactly why so many knowledgable engineers I know are leaving SO. The second bullet in the help on "What topics can I ask" is "a software algorithm." This is _clearly_ a question of that sort. It's absolutely related to programming. @Someprogrammerdude – Gene Sep 23 '18 at 02:32

1 Answers1

3

First let's take a look at a diagram for reference:

enter image description here

The procedure for calculating H1 and H2 is as follows:

  1. Compute the intersection, if any, between the ray R and the line segment P1P2. We're only interested in intersections that lie within the interior of P1P2. Similarly for P3P4. The points P1 to P4 can be calculated easily from the circle centers, C1 and C2, and some vector math. E.g. P1 = C1 + r*nC, where nC is the normal (CCW) of the unit vector from C1 to C2. This answer on SO provides the necessary math to determine if an intersection exists between two line segments and, if so, calculate the parameter h, such that H=R1+h(R2-R1), where H is an intersection point. This step can produce 0, 1, or 2 valid h values, depending on whether the ray intersects neither, one, or both of P1P2, P3P4.
  2. Compute the intersection points, if any, between the ray and each of the 2 circles. Again, an SO answer provides the necessary math for ray to circle intersection. Each circle can produce 0, 1, or 2 intersections, again represented parametrically.
  3. If no valid h values were generated from steps 1 & 2 then the ray does not intersect the capsule. Otherwise, calculate hMin and hMax, the min and max parameter values of all valid intersections identified in steps 1 & 2. Note that it's possible that hMin==hMax, in the case where the ray is tangent to one of the circles and does not intersect P1P2 or P3P4. The required intersection point(s) can now be calculated as H1=R1+hMin(R2-R1) and H2=R1+hMax(R2-R1).

I'm afraid my language of choice is Java rather than C++, but hopefully you'll find the code (IDEOne) I put together helpful as a reference. Please be aware that no effort was put it to handle robustness issues resulting from the rounding of double values during calculations.

RaffleBuffle
  • 5,396
  • 1
  • 9
  • 16