K-DOP tree

Intersection problems are common in many engineering applications, for example, enforcement of non-penetration constraints in contact mechanics, cut-cells in immersed boundary methods and lattice generation in additive manufacturing, etc. For solving intersection problems an efficient search structure is important. The CGAL library offers the AABB tree structure for fast intersection computation. The k-dop whose facets are determined by hyperplanes with outer normals in a fixed number of directions is a generalisation of the bounding box, and it is promising to be more efficient and flexible than the AABB tree in the intersection search. This project aims to develop a k-dop tree structure in CGAL, and its robustness and efficiency will also be investigated compared with the AABB tree.