Poor single pick SoRayPickAction performance in big scenes

[Rexbas]

The SoRayPickAction with single pick could take a long time when there are a lot of nodes that intersect with the ray. This is a problem we are having in FreeCAD for bigger assemblies. It appears that the SoRayPickAction finds all intersections of all the objects behind it and then picks the one that is closest to the start of the ray. However, with single pick we are only interested in the closest intersection. I think we can significantly improve the performance of single picks. I have noticed that the method generatePrimitives(action) takes the most time to execute while finding the bounding box intersection is a lot faster. So I propose these steps to improve the performance:

1. Traverse graph to find all nodes that have bounding box intersections with the ray, store these nodes and the bounding box intersection distances in a list.
2. Sort the list based on the distance to the bounding box intersection points from closest to farthest distance.
3. Find the exact intersection point for the first node in the list.
4. Remove all nodes from the sorted list which have a bounding box intersection distance that is more than the distance to the exact intersection point found in step 3, as those will not have a closer exact intersection point, thus preventing unnecessary calculations.
5. Repeat step 3 and 4 for the next node in the list until all remaining nodes in the sorted list have been checked.

I have already tried to implement this by adding the sorted list and a flag in SoRayPickAction and modifying SoRayPickAction::beginTraversal(...). Basically first traverse as normal but instead of calling generatePrimitives(action) in SoShape::rayPick(...) I add the node to the list. Then after traversal, at the end of SoRayPickAction::beginTraversal(...), I sort the list, set the flag and do node->rayPick(this) for each node in the sorted list. However, I am getting SIGSEGV or SIGABRT errors. @VolkerEnderlein, could you help me? I have limited knowledge about Coin. How would you implement the 5 steps above?

[VolkerEnderlein]

Thanks for reaching out. I would expect this to work, but keep in mind that a bounding box might enclose a non convex object and a lower distance to this box does not imply that the enclosed shape is closer to the ray origin than shapes in boxes which are farther away from the ray's origin.