Collision line segments and Rays

General Discussion
1

I often want to find the first collision along a ray. It seems like getting all of the collisions along the ray (potentially traversing through a huge number of objects if its pointed level across my map), then sorting them by distance, is a horrible way to do it.

I generally have many thousand collision solids grouped roughly into an oct-tree, and a couple of line segments, rays and sphere (not many) that collide into them. Having a ray “leak” past the first nearby collision and activate oct tree groups all the way down to leaf nodes across the entire map is bad.

Maybe a collision solid, specifically for a first hit ray would be possible? I’d also like to be able to impose a max distance to check (basically a fist hit line segment). To be clear, I’d still expect it to often process several collision points and have to sort them, but if it could skip most of the far away ones most of the time, that would be awesome.

I’ve tried some hacks with line segments guessing how far I might need to look, but thats a pain, and rather inflexible.

Doing several traversals with different line segment lengths until one hits could work, but thats sounds inefficient (if that actually is not too wasteful, then I’ll just implement that) Ex: check from 0-1 meter, then traverse again checking from 1-2, then maybe 2-4 or so up to a max. I’d tune the selection of ranges based on the exact use case.

Is that a good approach?

Example use cases: camera collision, ground collision, mouse picking

In the future, I’ll probably page collision geometry separately from visible so there isn’t any terrain collision really far away, but I still see potential for improvement here.

2

I’m no good at math, but I think it is simpler to tell if there was some collision then to tell where they were, so the first step in a collision detection will be checking if there could be a collision ( eg. positive discriminant?) then checking where it was and finally sorting them (don’t know a thing how panda collisions work, but say a ray-sphere collision could be made simpler when viewed from the sphers objec-space, so if there are two intersection point none of them is ‘first’ from the spheres point of view). I’d be supprised if panda could tell what collision was first whitout a full list of collisions - but as I say -I’m no good with math.

3

You can’t know which one is the first collision along the line until you’ve tested all of them and then checked which one is closest. So, under the hood, it would be the exact same thing as using a regular CollisionSegment in conjunction with sortEntries.

4

I don’t know the exact details of the traversal, but it seems like it should be possible to store the closest found so far (or some upper bound for it), and either decrease the bounds of the ray dynamically, or just not do the final processing step (compute the exact collision) in the case where the entire bounds of the object that intersects the ray is further that the currently known closest collision.

Thats not ideal, and might not be practical, but assuming the order of the collisions found is random (which is a horrible assumption, I know), it would reduce the number of collisions processed from N to approximately Log(N). I know its not practical to get that down to 1, but at least the average case could be improved pretty greatly by effectively swapping the ray with a shorter and shorter line segment throughout the traversal.

If you find a collision 1 meter away, there is no need to find every intersection with a building thats entire bounding box is > 100 meters away. If you test against the far away object first, nothing is gained, but if you test against the close one first (which I would expect to happen sometimes by chance), a lot is saved, thus on average its faster.

A quick test showed I often have rays hitting 7-14 intersections, and occasionally 28+.

I can imagine something that collected the bounding boxes along the ray, ordered them and recursively inspected them as needed to lazily evaluate the items in nearest to furthest order. Often in the case of overlapping bounds, multiple points would need to be tested but this would require touching far few collision objects (much less work, and potentially better cache use). For most well structured collision hierarchy (like my cube tree), this should at least get the Log(N) vs N speedup I mentioned (though I would expect a bit better than that). In my particular case 4x speed up in a lot of cases, and even higher in the worst cases (which are the real issue).

If this isn’t something that can be done with the existing traversal setup, thats understandable. I suspect it would be a good deal of work for do, but since it would gradually reduce the time spent on collision in my game (almost all the collision time is spent on these line segment and ray cases, since they perform so much worse than my spheres).

I occasionally hit nasty collision edge cases that cripple the frame rate worse than my rendering monstrosity when my line segments and rays line up along large amounts of geometry. Yes, I can get better collision geometry to fix the issue, but I think with my proposed addition, even my trivial naive setup would be fast enough.

Anyway, I just figured I should mention that one of the most common use cases of collision is currently horribly suboptimal. Other than this, panda’s collision system seems pretty good.

5

We already test against bounding volumes before we test the actual solids. The number of times test_intersection_from_ray is called is therefore already fairly limited to the best candidates.

So, unless I misunderstand you, all your proposal would change is that the sorting happens before the actual collision test, and presumably to allow limiting the number of collisions as not to test the other candidates. But it’s not easy to figure out which should be first without testing all of them first.

But that is exactly why we have CollisionSegment; if you set it to a 1 metre length, it won’t bother testing against objects that are 100 metres away. A CollisionSegment is better suited for this all around because it would also have a much smaller bounding volume, resulting in a much lower set of potential collision entries to consider in the first place.

6

I understand this, but I consider the 20+ actual hits that I don’t care be bad candidates, but they are called anyway. The tons of far away near misses is a problem too (way more bounds checks that are needed to find the closest collision)

In the cause of a mouse picking ray, I can’t make it 1 meter long if I expect something to be close, sine there might not be anything close. If it got no hits, I’d have to traverse again with a longer one. This would have to repeat until I found one. The problem in question occurs when theres is a big difference between the maximum distance I might want to know about a collision at, and the actual distance to the first collision.

Anyway, I looked at the source a bit. Seems like a minimal way would need to introduce some per pass state into the CollosionSolid. When CollosionSolid.test_intersection found a hit, it would record the location to this per pass state.

Then ideally that somehow needs to make it into the from_node_gbv passed into CollisionTraverser::compare_collider_to_node so entire node hierarchies can be skipped it they are further than the collision.

The better way I describe above would would require a different CollisionTraverser::traverse, that would collect compare_collider_to_node requests in a priority queue for each “from CollosionSolid” sorted by distance from the “from CollosionSolid” origin to the furthest part of the GeometricBoundingVolume *into_node_gbv (this can over estimate the distance, but not underestimate).

Then instead of producing a collection of collision entries, it would process this queue, keeping only the closest found so far, until the distance to the closest known collision exceeds the distance value for the next entry in the queue. When an item in the queue contained child nodes, processing that node would also add the children into the queue.

I think an alternative TraverseClosest method could me implemented that would implement this logic, or it could be somehow selected based on a flag in the from CollisionSolid or the CollisionHandler (That would be ideal, if the handler is CollisionHandlerClosestOnly, it would use this approach)

Interestingly, I think this could be done with just changes to the CollisionTraverser, so it could be prototype via a CollisionTraverser subclass, or just a implementation of something like CollisionTraverser.

Anyway, I completely understand that its just an optimization of a special (but common) case; I just want to try and get across that is in-fact possible. After looking at how the source is structured, it does not look like any significant changes would be needed, just additions.

Trying to do this seems like a rather horrible choice for a first C++ panda project, but if no one else want to take it on, I may eventually make an attempt at some point. I think it would be a nice feature to have: it would be both easier to use, and faster for the most common use-case of collisions.

7

But again, how would you calculate the distance before you actually do the intersection test? There could be funky cases of spheres being inside another sphere’s bounding volume but still being closer or farther away or something like that, so you need a method to test for the distance that works in every case, with every type of collision solid. The only method I know which does that is a sphere-line intersection, which is done by test_intersection.

8

The key is that you only need an lower bound on the distance (maybe I got that backwards in my other post), so some really approximate test would be fine. If the lower bound estimate were always 0, it would be as slow as it is now (but still correct), so anything is an improvement (and cases you don’t know what to do with can just return 0). For into spheres, just return distance between origins minus radius of sphere. This works for from anything into sphere, since the ordering we care about is distance from the from origin to the collision.

I only really care about efficiently handling the higher nodes in my cube-tree which I think get spheres, so that should be enough (everything else can return their parent’s value, or 0). Other cases could be added later if desired.

The goal is to avoid unnecessary recursion of checking all the children of nodes and solids which are too far away. If you can only check the parent node’s estimated lower bound, that saves a lot of time, since there may be thousands of children and solids inside, and many actual collisions.

It may be pretty inefficient, but I realized I think I can at least make a prototype of the algorithm in python (I’ll just call the existing traverse once I get down to collision nodes so its not super slow). I may experiment with this soon.