Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (497)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Moving rects - find the moment of intersection  (Read 2865 times)
0 Members and 1 Guest are viewing this topic.
Offline 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
Offline 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)?

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Member


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 <code>true</code> 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...
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


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

Read up on Separating Axis Theorem.

Google gives this: http://supertux.lethargik.org/wiki/Sweep_collision_algorithms
which leads to this tutorial: http://www.metanetsoftware.com/technique/tutorialA.html
which cites this article in it's references: http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php
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
Offline ryanm

Senior Member


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.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline ryanm

Senior Member


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

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (22 views)
2014-09-19 03:14:18

Dwinin (35 views)
2014-09-12 09:08:26

Norakomi (62 views)
2014-09-10 13:57:51

TehJavaDev (89 views)
2014-09-10 06:39:09

Tekkerue (44 views)
2014-09-09 02:24:56

mitcheeb (65 views)
2014-09-08 06:06:29

BurntPizza (47 views)
2014-09-07 01:13:42

Longarmx (35 views)
2014-09-07 01:12:14

Longarmx (40 views)
2014-09-07 01:11:22

Longarmx (36 views)
2014-09-07 01:10:19
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!