gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > bounding ellipse

#22291 - sgeos - Thu Jun 17, 2004 4:07 am

Has anyone considered a bounding ellipse? How difficult would this be to implement?

-Brendan

#22307 - sgeos - Thu Jun 17, 2004 11:34 am

It looks like we are looking at something like this to pull off a bound ellipse:
Code:
#define TRUE   1
#define FALSE   0

struct circle_critter {
   int x;
   int y;
   int r;
};

struct ellipse_critter {
   int x;
   int y;
   int w;
   int h;
};

int safe_distance_sq
(
   int x0,
   int y0,
   int x1,
   int y1
)
{
   int x_distance_sq;
   int y_distance_sq;

   x_distance_sq = x0 - x1;
   x_distance_sq *= x_distance_sq;
   y_distance_sq = y0 - y1;
   y_distance_sq *= y_distance_sq;
   return x_distance + y_distance + 1;
}

int
radius_collision
(
   int source_r_sq,
   int target_r_sq,
   int safe_sq
)
{
   if ((source_r_sq + target_r_sq) < safe_sq)
      return TRUE;
   /* else */
      return FALSE;
}

int
circle_collision
(
   circle_critter *s, // source
   circle_critter *t  // target
)
{
   return
      radius_collision
      (
         s.r * s.r,
         t.r * t.r,
         safe_distance_sq(s.x, s.y, t.x, t.y)
      );
}

int ellipse_r_sq(ellipse_critter *unit, angle_t theta)
{
   int rw_sq;
   int rh_sq;

   rw_sq = unit.w * unit.w * cos(theta);
   rh_sq = unit.h * unit.h * sin(theta);
   return rw_sq + rh_sq;
}

int
ellipse_collision
(
   ellipse_critter *s, // source
   ellipse_critter *t  // source
)
{
   angle_t theta;
   int rs_sq;  // source's effective radius squared
   int rt_sq;  // targets's effective radius squared

   theta = arctan(s.x - t.x, s.y - t.y);
   rs_sq = ellipse_r_sq(s, theta)
   rs_tq = ellipse_r_sq(t, theta)
   return
      radius_collision
      (
         rs_sq,
         rt_sq,
         safe_distance_sq(s.x, s.y, t.x, t.y)
      );
}
This is pseodocode. If you see any, please point out any flaws. A bounding circle is cheap. Cheaper if r_sq is stored. A bouding ellipse is more expense. The final collision test is the used in the bounding circle, the only problem is that the "effective radius" changes with angle from the source to the target. We need to know this angle before we can calculate the effective radius. (Therefore the effective radius can not be stored.) All in all, in addition to the bounding circle overhead, a bounding ellipse requires one call to arctan, two calls to sin, and two calls to cos.

Because bounding ellipse and bounding circle collision detection are so similar, a circle to ellipse function would be easy to construct. It would require one arctan, one sin, and one cos call in addition to the standard bounding circle call.

Because most critters are not square, a bounding ellipse looks like a pretty accurate way covering a critter. How does it compare to pixel level collison detection? Thoughts in general?

-Brendan

#22315 - sgeos - Thu Jun 17, 2004 3:40 pm

A correction and some clarification. w and h in struct ellipse_critter are from the centre to the edge. That is, they are 1/2 the total w or h of the entire bounding box. 'absolute w-radius' and 'absolute h-radius'. Perhaps they should be called wr and hr? (Or rw and rh like the function below?)

ellipse_r_sq() should read:
Code:
int ellipse_r_sq(ellipse_critter *unit, angle_t theta)
{
   int rw_sq;  // effective w-radius for this angle (squared)
   int rh_sq;  // effective h-radius for this angle (squared)

   rw_sq = unit.w * cos(theta);  // get w component of effective radius
   rw_sq *= rw_sq;               // square w component
   rh_sq = unit.h * sin(theta);  // get h component of effective radius
   rh_sq *= rh_sq;               // square h component
   return rw_sq + rh_sq;         // combine for total effective radius
}
All of this is still pseudo-code/theory-code.

-Brendan