Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (575) Games in Android Showcase (154) games submitted by our members Games in WIP (624) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Moving rects - find the moment of intersection  (Read 3071 times) 0 Members and 1 Guest are viewing this topic.
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Posted 2010-07-19 03:08:12 »

I have two rectangles that are both moving (or could be moving) that cannot be rotated (will always be AABB). I have their last position and current positions stored, they are colliding at their current position but not at their last position. I also have the velocity used to get from last to current positions.

The question is, I'm wondering the best way to move them both to the point at which they collided to avoid overlap. The only thing I can really think of is to do line intersections using their vertices, but this definitely seems overly expensive. Because they are AABB, I can dissolve the situation to one where they are either colliding along the side of the squares (thereby reflecting only over the X velocity), or the top/bottom of the squares (a Y reflection). Pretty simple situations.

Still, I'm not sure the best way to get the point of intersection. Where in between last and current positions would they collide? I can think of lots of different ways but they all seem too slow. There's got to be really cheap way of doing this given that I have two AABB.

See my work:
OTC Software
CommanderKeith
 « Reply #1 - Posted 2010-07-19 05:11:18 »

Can the rectangles move in any direction or only orthogonally (on the x and y planes)?

Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #2 - Posted 2010-07-19 07:06:13 »

And how would you handle the situation where they do not overlap in their last positions and not in their current positions, but there was a collision between them? Then you'd have to use swept rectangles.

To be honest, the collision check of 2 rectangle is so cheap, that any advanced algorithm to figure out the exact time of collision will be extremely slow. So it's probably fastest to use a binary search to converge to the solution, despite that there might be more correct algorithms.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #3 - Posted 2010-07-19 07:54:53 »

I'm pretty sure that the exact solution won't be too expensive, but for now here's code to test for rectangle intersection that doesn't involve computing line intersections
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 `/** * Tests if two axis-aligned rectangles intersect *  * @param minA * @param maxA * @param minB * @param maxB * @return true if intersection */public static boolean axisAlignedRectIntersection( Point2f minA,      Point2f maxA, Point2f minB, Point2f maxB ){   boolean xOverlap = !( minA.x > maxB.x || maxA.x < minB.x );   boolean yOverlap = !( minA.y > maxB.y || maxA.y < minB.y );   return xOverlap && yOverlap;}`

I'll have a think, might have more later...
Abuse

JGO Knight

Medals: 17

falling into the abyss of reality

 « Reply #4 - Posted 2010-07-19 09:42:07 »

Read up on Separating Axis Theorem.

which leads to this tutorial: http://www.metanetsoftware.com/technique/tutorialA.html
Page 3 of the article is An Axis-Aligned Bounding Box (AABB) Sweep Test

Some time ago I believe I used that article to implement the Sphere-Sphere sweep test(actually, I was interested in just circle-circle), and can confirm the algorithm works.

If you want to have nightmares tonight, just think about how you'd go about computing the sweep test for an arbitrary n-dimensional polygonal shape that is moving and rotating.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #5 - Posted 2010-07-19 10:12:41 »

I reckon I've got the solution. Code attached (you want the axisAlignedIntersectionTime() method), but the gist is:
• Subtract the velocities so you're testing a mobile rectangle against a static rectangle
• Split the problem: for each axis find the time period over which the rectangles intersect on that axis: the time period between the high edge of rectangle A meeting the low edge of B, and low edge of A meeting high edge of B
• If these time periods both exist (catch zero velocity case) and intersect, the rectangles first intersect at the start of the later time period
... and Robert is thy mother's brother.
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #6 - Posted 2010-07-19 11:46:51 »

I reckon I've got the solution. Code attached (you want the axisAlignedIntersectionTime() method), but the gist is:
• Subtract the velocities so you're testing a mobile rectangle against a static rectangle
• Split the problem: for each axis find the time period over which the rectangles intersect on that axis: the time period between the high edge of rectangle A meeting the low edge of B, and low edge of A meeting high edge of B
• If these time periods both exist (catch zero velocity case) and intersect, the rectangles first intersect at the start of the later time period
... and Robert is thy mother's brother.

This is (somewhat) what I had in mind, still I'm pretty sure a binary search is (much) faster, as each check is so cheap.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #7 - Posted 2010-07-19 12:11:29 »

This is (somewhat) what I had in mind, still I'm pretty sure a binary search is (much) faster, as each check is so cheap.
I'd be really surprised if that were so
The above method is 6 subtractions, 4 divisions, a handful of comparisons and you've got the exact time of intersection - whenever that occurs on the unbounded timeline. You can do this once whenever the rectangles or velocities change, rather than per-frame, and it catches the case where small or fast rectangles skip through each other.
I really can't see any way that stepping through time to find an intersection and then recursing to approximate the moment of impact will be faster in the general case.
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #8 - Posted 2010-07-19 14:46:46 »

Thanks for all the responses. I was pretty close to all these in my current implementation, I just didn't consider the time periods. That's very cool that you can just compare the ranges of time at which they will collide and use that on both axes. Cheers!

See my work:
OTC Software
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 ClaasJG (30 views) 2015-04-27 13:36:51 BurntPizza (34 views) 2015-04-23 03:42:11 theagentd (37 views) 2015-04-22 16:23:07 Riven (51 views) 2015-04-16 10:48:47 Duke0200 (60 views) 2015-04-16 01:59:01 Fairy Tailz (43 views) 2015-04-14 20:13:12 Riven (47 views) 2015-04-12 21:36:37 bus hotdog (66 views) 2015-04-10 02:39:32 CopyableCougar4 (67 views) 2015-04-10 00:51:04 BurntPizza (72 views) 2015-04-06 22:06:58
 theagentd 23x BurntPizza 17x wessles 15x Spasi 14x kingroka123 11x alwex 11x Rayvolution 7x Hanksha 7x chrislo27 7x Riven 7x kevglass 7x Olo 7x Ecumene 7x ra4king 7x KevinWorkman 6x 65K 5x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org