Intersection of a polyhedron with a line

It can be viewed as a three-dimensional version of the line clipping problem.

The halfspaces that include both ends must be parallel to the given line, and do not contribute to the solution.

This method, a variant of the Cyrus–Beck algorithm, takes time linear in the number of face planes of the input polyhedron.

Alternatively, by testing the line against each of the polygonal facets of the given polyhedron, it is possible to stop the search early when a facet pierced by the line is found.

[1] If a single polyhedron is to be intersected with many lines, it is possible to preprocess the polyhedron into a hierarchical data structure in such a way that intersections with each query line can be determined in logarithmic time per query.