KDOPs and OBBs

[aprokop]

I see that so far 4C been playing around with KDOPs. I wanted to learn more about it, and your experience with it. What are the problems you are solving that KDOPs are better for than AABBs? Are the performance measurements indicating that?

I'm also wondering if ArborX implemented OBBs, would that be more beneficial? I found that KDOPs struggle when dealing with surface meshes at angles, which theoretically OBBs would solve. I wonder if there are use cases in 4C that could benefit from that.

[isteinbrecher]

Thanks for the question. The first application of ArborX in 4C was for embedded fiber problems (if you want to have a look at some examples you can check out https://arxiv.org/abs/1912.04153), where we deal with thin, long beam elements (almost one-dimensional, but curved) embedded inside standard 3D volume elements (e.g., hex8, hex27). In these cases, the interaction evaluation involves a fine search that performs segmentation and local projections onto curved interfaces, which is relatively slow. So our main performance gain comes from minimizing the number of candidate pairs that enter this expensive fine search phase. That’s why we chose KDOPs—simply because they offer tighter-fitting bounds than AABBs. The actual performance difference between KDOP and AABB searches within ArborX is of secondary importance in this context.

We’ve since started integrating ArborX into other parts of the code where we need a global distributed search. Since the same type of elements as previously described are searched, we’ve simply stuck with KDOPs there as well.

In our experience, the crucial objects in our applications are the beam elements, since a “bad” bounding box on a beam can hurt performance or accuracy much more than a bad one on a volume element - which in my opinion makes sense given their 1D curve like nature. Because of that, we’re definitely open to trying alternative bounding volumes that can better capture their shape. I’m not too familiar with OBBs myself, but from what I understand, they could be a good fit and worth trying.

Our long-term goal is to migrate as many as possible of our search algorithms (and there are quite a few, see #200) to use ArborX (most of those cases don't deal with beams).

I found that KDOPs struggle when dealing with surface meshes at angles

What exactly do you mean by “struggle”? Are some interaction pairs being missed, or are you seeing too many false positives, or is it something else entirely? As far as I know, we haven’t experienced any issues with KDOPs in our use cases so far.

[aprokop]

Thank you for a thorough reply. Certainly, for this kind of application, KDOP makes sense. You are essentially dealing with a volumetric data. I don't think OBB would help here. I remember stumbling on swept spheres. The line-version of it is kind of similar to these 1D objects. Maybe partitioning each beam in chunks, and approximating each chunk with a swept sphere could have some benefits.

What exactly do you mean by “struggle”? Are some interaction pairs being missed, or are you seeing too many false positives, or is it something else entirely? As far as I know, we haven’t experienced any issues with KDOPs in our use cases so far.

I meant from the performance may significantly deteriorate depending on the angle. But it really is mostly for 2D surfaces, and not 3D objects.

[isteinbrecher]

I hadn’t heard of swept spheres before, but after a quick search, I agree they seem like a very suitable bounding volume for our beam elements - especially if the beams are segmented into multiple swept spheres. If this were available within ArborX, we would definitely want to try it out, particularly if intersections between swept spheres and KDOPs can be computed (in our experience, KDOPs are still the best-suited bounding volume for classical “volume” finite elements).

Another application for ArborX that we want to consider is collision detection for periodic problems. In our case, we have axis-aligned periodic bounding boxes, and we need to detect collisions between elements that stick out of one face of the bounding box and elements on the “opposite” face. Our current idea is to first check which elements intersect the faces of the periodic boundary, then reinsert those elements with the appropriate offset to account for periodicity, and finally perform the collision search on the “extended” list of elements. That said, I’m not sure it would make sense to have such a feature built directly into ArborX, since the specifics of how periodicity should be handled can vary a lot depending on the problem setup and could become very application-specific very quickly.

[aprokop]

I hadn’t heard of swept spheres before, but after a quick search, I agree they seem like a very suitable bounding volume for our beam elements - especially if the beams are segmented into multiple swept spheres. If this were available within ArborX, we would definitely want to try it out, particularly if intersections between swept spheres and KDOPs can be computed (in our experience, KDOPs are still the best-suited bounding volume for classical “volume” finite elements).

I think implementing swept spheres is straightforward. However, intersections with KDOPs look problematic. I haven't confirmed, but to me intersection with a swept sphere is equivalent to saying that an object is within specified distance of the geometry that is being swept. The problem with KDOPs is that I don't know of a good way to compute distances to KDOPs. We disabled them in ArborX because the easy method did not work and I did not want to implement quadratic optimization problem.

Another application for ArborX that we want to consider is collision detection for periodic problems. In our case, we have axis-aligned periodic bounding boxes, and we need to detect collisions between elements that stick out of one face of the bounding box and elements on the “opposite” face. Our current idea is to first check which elements intersect the faces of the periodic boundary, then reinsert those elements with the appropriate offset to account for periodicity, and finally perform the collision search on the “extended” list of elements. That said, I’m not sure it would make sense to have such a feature built directly into ArborX, since the specifics of how periodicity should be handled can vary a lot depending on the problem setup and could become very application-specific very quickly.

Over the years, we were pinged couple times on the periodicity. We never implemented it because different projects often mean different things by that, and as you said, things could be very application-specific. What you are proposing would definitely work and is probably the easiest. There are some other approaches but I'm not sure if they are any easier. Specifically, I wonder if using custom geometries could help. One would define a geometry (which is just to create a new type to store an existing one), and then define what it means to intersect with it. There's a lot of flexibility here as to how to define periodicity. My concern is the potential performance ramifications of this approach.

Another alternative is to create a custom geometry for query with custom intersects, where it will try all periodic variants. It's a fixed cost expense without any need to change the domain. If you know which face the query geometry is sticking out from, you could limit the number of replications. This seems pretty straightforward, I think.

In general, I'd like the periodicity option to ArborX if we find some nice interface for it and reasonable performance penalties. I'm just not sure how to easily do the first step (finding elements next to the boundary).

[isteinbrecher]

I haven't confirmed, but to me intersection with a swept sphere is equivalent to saying that an object is within specified distance of the geometry that is being swept.

From what I have read, I agree with you there - and I totally understand the issues with kDOPs. We implemented a visualisation for them, which turned out much more complex than anticipated (and still has some issues).

4C/src/core/fem/src/geometric_search/4C_fem_geometric_search_utils.cpp

Line 63 in 1bf09da

get_k_dop_polyhedron_representation(const BoundingVolume boundingVolume)

For our use case the question is, if swept spheres VS AABB is better than kDOP VS kDOP. From my intuition, I would say the results should be quite similar (especially if we would segment along the beam axis with kDOPs).

Regarding the periodicity, both of your approaches seem very interesting. I think our envisioned approach would somewhat align with the second one. I will let you know if we have a working implementation there (unfortunately there is no timetable on when to actually do this...).

I'm just not sure how to easily do the first step (finding elements next to the boundary).

I totally agree with you that this is a difficult topic. For periodic bounding boxes that are AABB this interface should be straightforward, but in the general case of deformable periodic bounding boxes I also don't know what the best interface would be.