• IndieCity Slide Image

  • Aftermath Slide Image

  • City Living Slide Image

Development

2D Object Intersection

Posted by on Jun 12, 2012 in Development, Programming | No Comments

2D Object Intersection

Hi there!

I’m Rob, and welcome to my section of the XG hive mind! I wanted somewhere to store and talk about solved / partially solved issues that crop up during development. Hopefully it’ll be semi-blog style, and not just the outpouring of this poor crazed programmers ravaged mind! Lets get into it!

The Problem

Ok, so here at XG we’re currently working on some procedural content ideas. I’ve been looking to place object in 2D space, and not have them intersect.

Each object has a bounding volume/box and to make life easy is Axis Aligned (AABB), each object can be any size.

Now it’s a simple test to see if two AABB hit each other:

diag_box_1

Diag 1: Edges of Box for testing

As you can see we Test all 4 Edges to see if they are outside the bounds of the box, but what this does not tell us is what sides/edges where hit! This is important for us to be able to separate intersecting objects. The possible intersections are as follows:

diag_box_2

Diag 2: Test Cases 1-4

I tried a few options to see which edges were hit, but in the end the best option seemed to be to test which corner was inside the box and extrapolate the result from there.

Things to Note

First, the Objects need to be tested A.DirectionHit(B) and B.DirectionHit(A) to Satisfy test 3.
Second, this code will fail the fourth test. This is because none of the points are ever inside the a box, but the edges pass through.

Conclusions?

Once we can find these intersection by testing, we can then solve them. Solving is fairly simple and just a matter of moving the Object based on which edge is hit. The complexity grows has the number of objects increase too, but that’s another problem entirely!

Looking back at what I said right at the start, I think we’ll categorize this post under option 2!


Leave a Reply