This is for a novel 2D continuous collision detection I'm playing with. Suppose I have two piecewise quadratic functions that represent the motion of two objects. The number of pieces, and the intervals for them, are not necessarily synced. The intervals aren't uniform either. (All this data comes from using an adaptive timestep to integrate the motion). The piecewise functions and their first derivatives are continuous across the whole domain, though. For example: And suppose function two is defined similarly, but it might have intervals of [0, 1.5], [1.5, 3], and [3, 7]. I want to find the time of intersection (t). So the equation I'm solving looks something like this: |F1 - F2| = (r1 + r2) (for sphere intersection for instance), where F1 and F2 are the piecewise functions, and r1 and r2 are constants representing radii. At the moment, I do a naive every-interval-against-every-other-interval method, but as the motion of my objects requires more sub steps to model properly, it performs too many operations. So my thought was to build a swept AABB around each interval's piece using its end points and the extreme point of the parabola. Basically the AABBs would be 3D. So that allows me an early out (I can check to see if the pieces' AABBs intersect or not), but that doesn't lower the order of complexity. However my problem is now in a very familiar format: find all the intersecting AABBs between two sets. The only difference is that I will be discarding all my AABBs every cycle, and the AABBs for each set are arranged so that they form a long cohesive trail. What sort of broad-phase type algorithm would work well/best here?

What's the problem with checking for every overlapping region - surely you're only solving the equations once? Just find all the boundaries for the two functions you're putting in the equation (of which there are: num. intervals in F1 + num. intervals in F2 + 1, I believe). Finding the AABBs would seem more trouble than it's worth, as I see it... if the functions are changing then don't you have to calculate new AABBs anyway? Perhaps a brief explanation of the context would help.

That's what I'm doing at present. I find the intervals of both functions, and sort and divide them so I have a list of intervals over which the pieces do not change. (In my example, I would have [0, 1.5], [1.5, 3], [3, 5], and [5, 7])

However solving a piece vs. another piece isn't necessarily cheap (it forms a quartic polynomial I need to solve), and there can be a lot of pieces if the motion is especially stiff (a strong, damped spring for instance).

So I was thinking there might be a clever solution to narrow down the intervals I need to actually test. So imagine I have like a million pieces in each function. I would have to potentially solve several million quartics. But if I can broad phase out 75% of those quartic solutions, that would be more doable.

I don't really know much about broad-phase collision detection, but it seems that finding the min/max values for each piece of a function and checking for overlap (as you suggested) would greatly reduce computation time. Have you tried implementing such an algorithm yet?

As an extension to this, you might try storing along with each min/max value whether the value is the lowest/highest *from that point until the end/last piece of the function*. This way, when you are testing two functions for intersection and at a certain point within the test you find that: lowest value for F1 - highest value for F2 < r1 + r2 (for example) or vice versa, you can terminate the test immediately and save calculations for all the remaining pieces. There are several ways to check whether there are any lower/higher min/max values values for the rest of the function, but the best option seems like going over each function in reverse piece order and finding the highest/lowest value so far, then storing the results as first searched, last in array. Depending on whether a lot of the functions tend to diverge after certain values of t, this extension may help.

Quote:Original post by Alrecenk
You have 2D quadratic parametric motion equations each with time intervals, and you make this into a bunch of 3D AABBs with x,y, and time?

That is my plan, yes.

Quote:
Well, this isn't the usual case, but 3D AABBs are a good thing to have for a sort and sweep method. I would suggest sorting the time intervals into something like a sort and sweep collision structure. Since the function pieces for each object are probably already in time order you should be able to just merge a bunch of sorted lists of time intervals for each object. Then you can sweep through the list of objects sorted by time and perform a few more optimizations. When a time interval overlap is detected you check the precalculated xy AABB of the two functions. If that passes I would suggest creating 2 new AABBs for the functions in question that represent the swept AABB just for the overlapping time interval.

I'm not sure sort and sweep is a good method in this case. S&S relies somewhat on temporal coherence to make the precalculations worthwhile. I'd basically be throwing away all the AABBs after every frame, and the next frame will use an entirely different set. Also, on the time axis at any given point, there will always be a collision between two AABBs.

Quote:
I don't know how expensive the AABB calculation is, but I'd wager it's still worth it if it could avoid any quartic solving.

My thought as well.


My current thinking is some sort of AABB tree.

Did you consider my suggestion? Does it not really improve matters... (as it may not, since I thought it up quite quickly and certainly haven't tested it)?

Quote:Original post by alex_myrpg
Did you consider my suggestion? Does it not really improve matters... (as it may not, since I thought it up quite quickly and certainly haven't tested it)?

If you check out my first post, I think I talk about what you're suggesting. I find the min/max value of the piece and use it to expand the AABB if necessary from the estimate of just the end points. Or am I misunderstanding and there's more to it?

Yeah I was really just agreeing about that basic method, but what I was referring to in my previous post was my "extension" to this method. If my explanation isn't clear then let me know and maybe I can elaborate, but I suspect the method may not be that useful anyway.

Yeah, I think it loses me have way through :) Maybe a picture would help.