5
\$\begingroup\$

I'm trying to implement a script that detects whether two rotated rectangles collide for my game, using SAT (Separating Axis Theorem). I used the method explained in the following article for my implementation in Google Dart.

2D Rotated Rectangle Collision

I tried to implement this code into my game. Basically from what I understood was that I have two rectangles, these two rectangles can produce four axis (two per rectangle) by subtracting adjacent corner coordinates.

Then all the corners from both rectangles need to be projected onto each axis, then multiplying the coordinates of the projection by the axis coordinates (point.x*axis.x+point.y*axis.y) to make a scalar value and checking whether the range of both the rectangle's projections overlap. When all the axis have overlapping projections, there's a collision.

First of all, I'm wondering whether my comprehension about this algorithm is correct. If so I'd like to get some pointers in where my implementation (written in Dart, which is very readable for people comfortable with C-syntax) goes wrong.

Thanks!

EDIT: The question has been solved. For those interested in the working implementation: Click here

\$\endgroup\$
  • \$\begingroup\$ At the moment this is a "debug my code" type question. These are typically frowned upon here, since they're only useful to the individual asking, they're not a good fit for the site. I suggest you edit the question to ask about proper algorithms for this, then ensure you've implemented yours correctly. \$\endgroup\$ – MichaelHouse Oct 15 '13 at 13:16
  • \$\begingroup\$ I apologise. Updated the question to be more resourceful to readers. Thanks for letting me know. \$\endgroup\$ – handyface Oct 15 '13 at 14:18
  • \$\begingroup\$ No problem, thanks for understanding and updating the question. \$\endgroup\$ – MichaelHouse Oct 15 '13 at 14:21
2
\$\begingroup\$

One of your problems is the overlap checking code;

if (aMin <= bMin&& bMin <= aMax)
  return true;
if (aMin <= bMax&& bMax <= aMax)
  return true;

it looks like it misses the case where the range of 'a' lies entirely inside the range of 'b' (i.e. bMin < aMin AND bMax > aMax). A simpler approach is to check for a gap (non-overlap);

if (aMax < bMin || bMax < aMin)
  return false; //no overlap
else
  return true; //yes overlap

I don't think this is a bug, but your projection code is needlessly complicated. You just need to project p on to v. To do this you just need the dot product of p & v. So replace your code from the projection function below,

  //remove this code
  num proj = (p.x*v.x+p.y*v.y)/(Math.pow(p.x,2)+Math.pow(p.y,2));
  num x = proj*v.x;
  num y = proj*v.y;

  num val = (x*v.x)+(y*v.y);
  //end remove

with

   num val = (p.x*v.x)+(p.y*v.y); //dot product of p & v

There is no need to normalize(divide by length) vector v.

\$\endgroup\$
  • \$\begingroup\$ Works like a charm, thanks a lot! I'll update my implementation for those interested in the working implementation. \$\endgroup\$ – handyface Oct 18 '13 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.