Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) 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 4521 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

« JGO Overlord »

Medals: 1336
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 Ninja

Medals: 64

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.
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

« JGO Overlord »

Medals: 1336
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

 nelsongames (16 views) 2018-04-24 18:15:36 nelsongames (12 views) 2018-04-24 18:14:32 ivj94 (587 views) 2018-03-24 14:47:39 ivj94 (49 views) 2018-03-24 14:46:31 ivj94 (400 views) 2018-03-24 14:43:53 Solater (64 views) 2018-03-17 05:04:08 nelsongames (110 views) 2018-03-05 17:56:34 Gornova (175 views) 2018-03-02 22:15:33 buddyBro (723 views) 2018-02-28 16:59:18 buddyBro (93 views) 2018-02-28 16:45:17
 KaiHH 13x ByerN 11x SHC 10x NuclearPixels 10x Zemlaynin 10x Guerra2442 9x Damocles 6x VaTTeRGeR 5x Spasi 4x orangepascal 4x philfrei 4x ags1 4x princec 3x ndnwarrior15 3x mesterh 3x Phased 2x
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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