CGAL users discussion list

["Kiran Varanasi" <>]

Hi all

I would like to implement a fast algorithm to check if a line segment intersects with any of the facets of a mesh (Polyhedron_3). My idea is to chop the line segment into tiny pieces and check if the bounding box of any of these pieces overlaps with the bounding box of a mesh facet. If yes, I will perform a costlier test of whether the line segment is exactly intersecting the facet (CGAL::do_intersect). 

My idea is to hash the facets into a search tree by bounding boxes, and then perform the test on these bounding boxes. 

CGAL has a data structure Neighbor_search_tree which works well, but I can insert only points into this search_tree. I would like to know if there is any similar data structure for bounding boxes. 

Best Regards
Kiran