Intersection of a sphere and a triangle

I am currently engaged in moving a sphere in space with collisions with other objects. There were problems with solving the problem about the intersection of a sphere and a triangle (of which I have polyhedra).

The coordinates of the center of the sphere and its radius are given, as well as the three points of the triangle in space. You need to find out whether the triangle intersects the sphere (with its side or area).

Even more formally: Given a point O (x0, y0, z0) - center spheres. Given a real number r - the radius of the sphere. Given three vertices of the triangle: A (x1, y1, z1), B(x2, y2, z2), C (x3, y3, z3). It is necessary to answer the question: does the triangle have at least one point in common with the sphere?

Author: Kromster, 2020-04-14
Source

3 answers

Recommended sequence of actions.

  1. Plot the plane of the triangle.
  2. Build a projection on this plane of the center of the sphere, and then the circle of the intersection of the sphere and the plane.
  3. Solve the problem of having a common point for a triangle and a circle on the plane.

To simplify the calculation, it is recommended to rotate relative to the center of the sphere so that the plane of the triangle is perpendicular to one of the coordinate lines.

 3
Author: Akina, 2020-04-15 12:14:13

The easiest way:

  1. Immediately check whether the entire triangle lies in the sphere (because then it does not exactly intersect it). To do this, compare the distance from its vertices to the center of the sphere with its radius. If all three points are inside, then you can immediately give the answer 'no'. Otherwise:
  2. Find the point of the triangle closest to the center of the sphere. To do this, we project the center onto the plane of the triangle. If the projection lies inside the triangle, then go to step 4.
  3. Otherwise, the desired point lies on the sides of the triangle. We will find it by searching for the minimum distance to the segments - the same sides.
  4. Let's check whether the found point lies inside the sphere. If yes, then there is an intersection, otherwise - no.
 2
Author: KingCake, 2020-04-14 17:28:13

The problem can be reduced to the problem "Determine if the 2D shape and the ball have common points".

  1. If all the points of the 2D shape are removed from the center of the ball by a distance of <= r, then the 2D shape is inside the ball.

  2. If n points are inside, and k points are outside, where n > 0 and k > 0, then the 2D shape intersects the ball.

  3. It remains to consider the case when all the points are outside. Obviously, the intersection will only occur if the closest point to the center is the circle is a point ПЛОСКОСТИ ФИГУРЫ at a distance <= r and when this point lies in the shape. If the previous two conditions were not met, then check whether <= r all the perpendiculars to the segments and whether these perpendiculars cut into the segments. If they crash, and the length is <= r(at least one if there is one), then the figure intersects the ball.

 1
Author: Miron, 2020-04-15 12:02:31