tuxalin
Support for hooking in line segment intersection
Greetings again. I'm working on implementing a custom line segment intersection in Minetest, and I'm hoping to do it without modifying THST code, because that is a messy workaround and more work to maintain. My colleague and I have written one implementation by calling the predicate directly with the object I'm testing intersection for, instead of using predicate.bbox, and then implementing the necessary template specializations in my code to handle the line segment intersection. That worked, but as I said, it's not the cleanest solution. I'm interested in your thoughts on how we should go about this, and whether the predicates can be generalized to allow extending it to handle types other than bboxes. Thank you!
I think that should be possible, I would also go for generalizing the predicates, but it would help to get a high level snippet of the use case or what the API might look like in your case. Note that the RTree does support other types via Indexable getter, but that has to be a bbox since that's how the tree stores the nodes (could be optimized for points).
One of our ideas is to abstract the box away from the predicate. It can have a childsCanFulfillQuery and fulfillsQuery (names are only for example). One would basically be intersects called for the parents, and the other would be something like contains called for leaves. In our case setting both to intersects suffices, so a single "functional" predicate is enough for our purposes, but we don't know whether that might be problematic for backwards compatibility.
That being said, anything like extending a template or having an iterator we can call that lets us implement the collision logic works great for us.
I see, it's still a bit fuzzy for me, as I don't know what functions you use, I presume it's the query predicate and it sounds like you want a predicate for children and parents. But a simple code snippet would help with this, something like:
auto pred = [] (some args) { some code }; tree.query(predicate, std::back_inserter(vec));
So I can understand better what you want to do in the predicate.
So I can understand better what you want to do in the predicate.
Our predicate is effectively boxLineCollision (should probably be called "intersection" instead; we also don't need the normal or the intersection point, just the bool basically).
We're trying to get the boxes that intersect with the given line segment by first checking whether the parent intersects with the segment and only after that checking the children. This also means we don't need different predicates for children and parents. The current predicates are simply too box-focused for our purposes.
I might be interested in working on this myself if we come up with a good solution. I'd like to restate the problem here in case the solutions we proposed are distracting from the actual problem we want to solve. If THST is the wrong tool for what we're trying to do, please say so.
We have a player and some various non-player entities. When the player points at an entity, we want to detect that this entity has been selected. There may be a large number of entities, and we have to compute this frequently, so the performance of the implementation is important. The existing solution, if I understand it correctly, is to raycast from the player to some maximum distance away from the player, and check against the selectionbox of each entity at each point along the raycast.
The inefficiency of that approach for large numbers of entities is the underlying problem. Our proposed solution is to use a spatial tree to avoid many of the checks and thus get more performance out of the raycast.
Is line segment/raycasting something that will be added in the near future?
Is line segment/raycasting something that will be added in the near future?
It is planned but I didn't had much free time and can't give an estimate.
I might be interested in working on this myself if we come up with a good solution. I'd like to restate the problem here in case the solutions we proposed are distracting from the actual problem we want to solve. If THST is the wrong tool for what we're trying to do, please say so.
We have a player and some various non-player entities. When the player points at an entity, we want to detect that this entity has been selected. There may be a large number of entities, and we have to compute this frequently, so the performance of the implementation is important. The existing solution, if I understand it correctly, is to raycast from the player to some maximum distance away from the player, and check against the selectionbox of each entity at each point along the raycast.
The inefficiency of that approach for large numbers of entities is the underlying problem. Our proposed solution is to use a spatial tree to avoid many of the checks and thus get more performance out of the raycast.
Sorry for the delayed response, Would that be using the rtree or quadtree? From what I know usually quadtree/octree are better suited for that (and easier implement) but with the rtree there are probably fewer ray/box queries. If you can provide a function signature of how you would use it in your use case I could figure out how long it would take.
Added support via: template <typename OutIter, typename Predicate = spatial::detail::AlwayTruePredicate> ize_t rayQuery(const RealType rayOrigin[Dimension], const RealType rayDirection[Dimension], OutIter out_it, const Predicate& predicate = spatial::detail::AlwayTruePredicate()) const;
Yes, thank you so much! Some other bugs cropped up, so I haven't gotten to testing the new method yet, but it looks like a good solution to our problem. I'll try to PR fixes and regression tests for any bugs we find.