Algorithms for line and plane intersection with a convex polyhedron with o ( sqrt ( N )) expected complexity in E3
Václav Skala · 2014
Efficiency of intersection algorithms is fundamental for solving many problems in computer graphics, e.g. line and polygon clipping etc. For a line clipping by a convex polyhedron the well known Cyrus-Beck's (CB) algorithm is usually used with O(N) complexity, where N is a number of facets. For a plane clipping by a convex polyhedron algorithms used are of O(N) complexity. On the contrary, in the E2 case, the order is given by indexes of the polygon vertices, which leads to O(lg N) computational complexity [Skala 1994]. However, an intersection of a plane and a convex polyhedron given as a triangular mesh, results to a convex polyline lying on a plane in a general position in E3.