feat(AABBTree): generic intersection search method

yo35 · BotellaA · commit 78f88bd2f094 · 2025-07-09T13:49:07.000+02:00
diff --git a/include/geode/geometry/aabb.hpp b/include/geode/geometry/aabb.hpp
@@ -195,6 +195,29 @@ namespace geode
             const InfiniteLine< dimension >& line,
             EvalIntersection& action ) const;
 
+        /*!
+         * @brief Computes the intersections between any object (for which
+         * intersection against an arbitrary axis-aligned bounding box can be
+         * detected efficiently) and all element boxes.
+         * @param[in] boxFilter The functor to run to determine whether a box is
+         * intersected by the searched object or not. The box may correspond
+         * either to an internal tree node or to a tree element.
+         * @param[in] action The functor to run when a tree element box is
+         * intersected by the search object.
+         * @tparam EvalBox this functor should have an operator() defined like
+         * this: bool operator( const BoundingBox<dimension> & ) ;
+         * @tparam EvalIntersection this functor should have an operator()
+         * defined like this:
+         * bool operator()( index_t cur_element_box ) ;
+         * @note the operator define what to do with the box \p cur_element_box
+         * if it is intersected by the searched object.
+         * @note The returned boolean indicates if the search should stop or
+         * continue. Return true to stop the search, false to continue.
+         */
+        template < class EvalBox, class EvalIntersection >
+        void compute_generic_element_bbox_intersections(
+            EvalBox& boxFilter, EvalIntersection& action ) const;
+
         /*!
          * @brief Computes the intersections between a given Segment and
          * all element boxes.
diff --git a/include/geode/geometry/detail/aabb_impl.hpp b/include/geode/geometry/detail/aabb_impl.hpp
@@ -571,6 +571,54 @@ namespace geode
             return task.get();
         }
 
+        template < typename BOX_FILTER, typename ACTION >
+        bool generic_intersect_recursive( BOX_FILTER& boxFilter,
+            index_t node_index,
+            index_t element_begin,
+            index_t element_end,
+            index_t depth,
+            ACTION& action ) const
+        {
+            OPENGEODE_ASSERT(
+                node_index < tree_.size(), "Node out of tree range" );
+            OPENGEODE_ASSERT( element_begin != element_end,
+                "No iteration allowed start == end" );
+
+            // Prune sub-tree that does not have intersection
+            if( !boxFilter( node( node_index ) ) )
+            {
+                return false;
+            }
+
+            if( is_leaf( element_begin, element_end ) )
+            {
+                return action( mapping_morton( element_begin ) );
+            }
+
+            const auto it = get_recursive_iterators(
+                node_index, element_begin, element_end );
+            if( depth > async_depth_ )
+            {
+                if( generic_intersect_recursive( boxFilter, it.child_left,
+                        element_begin, it.element_middle, depth + 1, action ) )
+                {
+                    return true;
+                }
+                return generic_intersect_recursive( boxFilter, it.child_right,
+                    it.element_middle, element_end, depth + 1, action );
+            }
+            auto task = async::local_spawn( [&] {
+                return generic_intersect_recursive( boxFilter, it.child_left,
+                    element_begin, it.element_middle, depth + 1, action );
+            } );
+            if( generic_intersect_recursive( boxFilter, it.child_right,
+                    it.element_middle, element_end, depth + 1, action ) )
+            {
+                return true;
+            }
+            return task.get();
+        }
+
         [[nodiscard]] index_t closest_element_box_hint(
             const Point< dimension >& query ) const
         {
@@ -730,6 +778,19 @@ namespace geode
             line, Impl::ROOT_INDEX, 0, nb_bboxes(), 0, action );
     }
 
+    template < index_t dimension >
+    template < class EvalBox, class EvalIntersection >
+    void AABBTree< dimension >::compute_generic_element_bbox_intersections(
+        EvalBox& boxFilter, EvalIntersection& action ) const
+    {
+        if( nb_bboxes() == 0 )
+        {
+            return;
+        }
+        impl_->generic_intersect_recursive(
+            boxFilter, Impl::ROOT_INDEX, 0, nb_bboxes(), 0, action );
+    }
+
     template < index_t dimension >
     template < class EvalIntersection >
     void AABBTree< dimension >::compute_triangle_element_bbox_intersections(
