Line Segment Intersection of a 3D Convex Non-Planar Polygon

Question

I am attempting to find a decently optimal algorithm for determining whether or not a line segment intersects a 3D convex non-planar polygon. The best I can figure right now is to draw a line that splits the non-planar polygon in half, determines if the line segment lies to the right or left of the splitting line, then continue splitting until I can determine intersection. The reason behind it is so I can figure in which region of a 3d spherical voronoi diagram a given point resides. However, the time to find a solution can become depending on the float resolution of my line splits.

Diagram

Non-Planar Polygon Example

In this example, I would be drawing a line segment between the blue points and the center of the unit sphere (added after the voronoi calculation, they're not the points used to calculate the diagram). Then, I need to figure out which polygon that line segment intersects with in order to determine which region it resides in.

Answer 1

This can be solved by coordinate geometry.

First, divide the polygon into triangles. For example if the polygon is ABCDE consider the triangles ABC, ACD and ADE. In your problem, the line segment intersects the polygon if and only if it intersects at least one triangle. We will check whether the line segment intersects a triangle in the following way.

Let the triangle be KLM and the line segment be UV. The equation of the plane containing KLM will be of the form ax+by+cz+d=0 and that of the line containing UV will be of the form (x-x_0)/e = (y-y_0)/f = (z-z_0)/g. By solving these equations simultaneously we can find the coordinates P=(x,y,z) of the intersection of the line and the plane.

Once P is found, we need to make sure that it lies on both UV and KLM. The former is true iff the sum of distances from P to U and V is equal to the length of UV. For the latter, check whether the areas of the triangles formed by P and the edges of KLM (that is PKL, PLM and PMK) add up to the area of KLM.