How to interpolate collisions between paint events

Question

As of late, I have been researching all sorts of fancy collision detection algorithms and quadtrees for a 2 dimensional app, and have my application at the point where I want to start implementing those collision algorithms in. My gameloop is capable of calculating the Δt of my frames, and I want to perform 'interpolation' collision checks between painted frames (as opposed to 'brute-force' method: paint as fast as possible causing a general decrease in performance and animation quality).

Bottom Liner

What is the most efficient way to implement 'interpolation' collision checks and additionally, is there any collision algorithms that can simply take in the Δt and velocity to do the interpolation for me?

Additional musings and information

I am using per pixel intersection on images after AABB within a quad-tree. Images are inherently expressed as rectangles, and I find it too in-efficient to calculate convex/concave polygons around the pixels of the image that fit a defined alpha transparency threshold then perform some other algorithm such as minkowski portal refinement or recursive circles. I choose per pixel despite it's inefficiency speed wise because of the specifically rectangular constrained shape of images (Knowing this, I decrease per pixel checks by wrapping the check with a AABB collision check). In the future I might try to re-optimize/use a different method than AABB because my images will rotate at different angles.

Game Loop code: where update() handles catch-up operations.

currentUpdateTime = System.nanoTime();

    while(true) {
        beginLoopTime = System.nanoTime();

        drawPanel.repaint();

        lastUpdateTime = currentUpdateTime;
        currentUpdateTime = System.nanoTime();
        update((int) ((currentUpdateTime - lastUpdateTime)/( Math.pow(10,-9) )));//1000*1000

        endLoopTime = System.nanoTime();
        deltaLoop = endLoopTime - beginLoopTime;

        if(deltaLoop <= desiredDeltaLoop) {
           try {
           /*Refer to: 'http://stackoverflow.com/questions/1036754/difference-between-wait-and-sleep'
           on differences between Thread.sleep() and wait()*/
               wait((long) ((desiredDeltaLoop - deltaLoop)/( Math.pow(10,-6) )));
           } catch(InterruptedException e) {
               e.printStackTrace(System.out);
           }
        }
    }

score 1 · Accepted Answer · answered Jan 03 '15 at 06:22

1

I'll start by saying that this may certainly not be the best answer. It is a technique which I can think of "off the bat", not something I know is used in practice. Having said that:

Your 2D collision check with panes moving over time could be accomplished by considering your space as a 3D space with the 3rd dimension being time, and then applying 3D collision checking techniques. Panels that occupy the same space at the same time will be represented as 3D shapes which intersect, and the point(s) of intersection will tell you at what time the collision occurred.

answered Jan 03 '15 at 06:22

davmac

20,150
1
40
68

So long story short, find whether the arbitrarily made area between the initial space and final space overlap. That's what I was thinking, but I felt there was a better solution this. I think this will work fine though. – Bennett Yeo Jan 04 '15 at 17:04
@KiroYakuza "find whether the arbitrarily made area between the initial space and final space overlap" - no, that's not right; I'm not sure you understand. You should extend the object into the third dimension (time) and see if the 3D extension overlaps that of any other similarly extended objects. At any one point in time the object still only occupies its regular space. – davmac Jan 05 '15 at 01:21
(i.e. use a 3D collision check, not a 2D collision check with an extended area). – davmac Jan 05 '15 at 01:37
I'm afraid I'm not entirely sure how to utilize time as a third dimension to check collisions. Any advice? – Bennett Yeo Jan 10 '15 at 01:26
In a 3D space your co-ordinates have three dimensions (x,y,z) instead of two (x,y). In your system you have two dimensional co-ordinates and you use time (t) in place of the third co-ordinate (z), where x and y are both functions of t. So for some range of t values, you have x and y values for each t, and for each 2D object in your original space you now have a 3D shape. You can then use any 3D collision checking technique to find overlaps between your objects. (I notice you mention rotation in the question now - this complicates things! But the general principle still applies). – davmac Jan 10 '15 at 06:05

How to interpolate collisions between paint events

1 Answers1