Point passed rectangle...

Hey everyone, I'm trying to do some collision detection here. The problem is, I'm trying to check for a collision between a point and a rectangle, with the point moving at a fairly high number of pixels per frame; the rectangle is also very small. So I can't exactly do the typical "Is the point in the rectangle?" collision detection, which is the only kind that I can find, otherwise the point might just go straight through the rectangle and no collision might be detected.

So far, the only thing I've come up with is:

Code:

-Get the equation of the line that the point is following

-If the point is below and left of the rectangle, then:
   -If moving the point puts it above and to the right of the rectangle then:
      -See if the point's movement vector intersects the bottom or left sides of the rectangle
-Else if (...)

etc. etc. etc.

Does anybody have a faster and/or better way of doing this? (Or a link to a site that I missed...)

Are we just dealing with one point, one rectangle here? Or at least, a small number of points/rectangles? If it wouldn't be too expensive, you could have the point move a smaller number of pixels at a time, but move it several times per frame, checking for collision the easy way each time.

It's probably not the best way, but might be the simplest.

That's an idea. There's only as many points as there are shots on the screen, which is as many as can fit before the first shot goes off the screen and disappears; and each shot only needs to test against 1 rectangle (1 opposing player).

I guess I can use your method for the time being, but I'd still like more suggestions if possible

Well there are several ways to do this.


Point in rectangle
One would be a simple point in rectangle check. However, this method does suffer from fly through at high speeds. There is speed at which the point will 'skip over' the rectangle. The integrals are too high and therefore the point will never be in the rectangle in any frame. Not good.

Bi-linear interpolation
To solve this you could do a simple bi-linear interpolation between the last two points. In other words trace the route that the ball or projectile would have taken in that slice of time. Just checking the point in a rectangle per frame is not enough because those are larger slices of time. If when you bi-linear interpolate between the two points you come up with a collision with the rectangle then you have a hit and you can begin to calculate your collision vectors.

A simple bi-linear interpolation can be done like this:

Code:

double BI(double v1,double v2,double v3,double v4,double f1,double f2)
{
  double val1=(v1+f1*(v2-v1));
  double val2=(v3+f1*(v4-v3));
  return (val1+f2*(val2-val1));
}

or

Code:

double BI(double v1,double v2,double v3,double v4.double f1,double f2)
{
  double val1=0.0,val2=0.0;
  asm {
    fld        [v2]
    fsub     [v1]
    fmul      [f1]
    fadd     [v1]
    fstp      [val1]

   fld         [v4]
   fsub      [v3]
   fmul      [f1]
   fadd      [v3]
   fstp       [val2]

   fld         [val2]
   fsub      [val1]
   fmul      [f2]
   fadd      [val1]
  }
}

If you bi-linear interpolated by .1 pixels on x and y, checked the new point against the rectangle, you would have it except at some very extreme speeds.

This way, however, is bound to be slow even in asm. It might be fast enough for what you want which is why I posted it. A line between two points is a simple bi-linear interpolation - which is what the slope form of a line really is.

Run along the slope of the line
The other method is to do what you said. Trace the slope of the line using the y=mx+b.


Perform two linear interpolations
Another way is to to perform two linear interpolations on x and y - which might be faster than one bi-linear interpolation.


A linear interpolation is this:

value=v1+f1*(v2-v1)

Let's take two points: 0,0 and 10,20 which represent the projectiles location in two frames. Obviously we have missed some points between our frames because the frame time is not small enough - we need to integrate between 0,0 and 20,20 to check for collision.

Code:

double LI(double v1,double v2,double f1)
{
  return (v1+f1*(v2-v1));
}

or

Code:

double LI(double v1,double v2,double f1)
{
  asm {
    fld    [v2]
    fsub [v1]
    fmul [f1]
    fadd [v1]
  }
}

So lets integrate by .1 on each axis.

;newx=LI(0,10,.1);
;newy=LI(0,20,.1);
;I put the values below for illustration
newx=0+.1*(10-0);
newy=0+.1*(20-0);

;Here are the results
;newx=1.0;
;newy=2.0;

This is where your projectile would be at 1/10th of a frame. So you see you could trace its path through the two points - and in between frames. It should not take long to do this and you would be guaranteed a hit in almost every circumstance.

Of course you would have to do some conversions to get around the integer/double stuff - but thats an exercise left to you which should not be too hard. It is possible to do all of this with integers using fixed point math but on most processors floating point math is actually faster than doing fixed point. Hard to believe but true.

The higher the speed of the ball the smaller increments you need to check. Simply because 1/10 of 20 pixels is 2 pixels and 1/10 of 50 pixels is 5 pixels. See. But at 20 pixels per frame speed you could easily check for a collision - which means your projectile can fly across the screen and yet not miss a collision with another object.


Interpolation along a normalized vector
For the absolute slowest method you could normalize the vector between the two points and interpolate along it. However this needs to use the oh so slow sqrt() function so I don't recommend doing this. But it only has to compute this once per frame.

Code:

...
double diffx=(double)x2-(double)x1;
double diffy=(double)y2-(double)y1;

int totaldist=sqrt((diffx*diffx)+(diffy*diffy));

double incrementx=diffx/totaldist;
double incrementy=diffy/totaldist;

checkx+=(incrementx*scale);
checky+=(incrementy*scale);

if (checkx>=rect.left && checkx<=rect.right && checky>=rect.top && checky<=rect.bottom)
{
   ..hit has taken place
}

If you don't like using doubles, then use singles - but your compiler will convert them to doubles to be used by the FPU. Some of us did some research some time ago and there is no speed hit/gain by using singles or doubles on modern FPUs.


Long I know, but that's most of the methods I could think of.

Hope it helps.

Trivial rejection
All of these methods could be sped up by only using them when necessary. You could perform a trivial check of the projectiles location vs the objects location. If it is nowhere near it - there is no need to integrate between two points. Without trivial rejection code, your collision module will be very slow.

A good trivial rejection code would be to use a Taylor-Series expansion to estimate the distance between the object and the projectile.

Code:

#define MIN(x,y) ((x<y)?x:y)
#define MAX(x,y) ((x>y)?x:y)

int FastDist2D(int x,int y)
{
  x=abs(x);
  y=abs(y);

  int mn=MIN(x,y)

  return (x+y-(mn>>1)- (mn>>2) +(mn>>4));
}

The max error for this is 3.5 percent, but since it is a fast trivial rejection - who cares?

Compute in terms of the square of the distance
Another trivial rejection method is to never compute the square root. Do all calculations in terms of the square of the distance.

The last two ideas are straight out of Andre Lamothe's book Tricks of the Windows Game Programming Gurus - and they work well.

Collision detection logic

• Check all projectiles against all objects using trivial rejection.
• If trivial rejection fails, then use more precise collision detection because it's possible we might have a hit.
• If precise detection fails, we have a hit - if it passes we came close, but still not a collision.

Assembly language showoff

Wow! I'm gonna have to look some of this up... like... "interpolation" lol I'm probably a bit behind in terminology/math knowledge. I seem to never know what's going on when people talk about the math behind graphics

Earlier on, I put in confuted's solution as a temporary(?) quick-fix, but I think I'll switch over to one of the methods you explained once I manage to get it all sorted out

P.S. How would I check for a collision with a rectangle by running along the slope of the line? Would I need to run through all 8 below/left/top/right/bottomleft/bottomright/etc. cases?

Yes you would have to figure out which case to use - which is why the slope idea is prob not the fastest.

Linear interpolation is simply an interpolation or movement of a coordinate.

For instance to find the halfway point between 0 and 20 you could use linear interpolation.

value=0+.5*(20-0)

value will then equal 10.

So if we want to find a point 1/10th the distance from 0 to 20 we would do this.

value=0+.1*(20-0)

Basically there are an infinite amount of points between 0 and 20 and even between 0 and 1. By linear interpolating we can find any point between 0 and 1 or 0 and 20 or any two numbers. This is very helpful in filtering textures (colors), values, etc.


Bi-linear interpolation can be best explained like this. Let's take a square or one quad of a terrain. Each value represents a height at one of the four corners of the square. Let's say that our tank or character or whatever it is .1 inside the square on x and .2 inside the square on Y.

X - our position

Code:

100-------------------------200
.                                         .
. X                                        .
.                                         .
.                                         .
.                                         .
50.....................................70

v1=100
v2=200
v3=50
v4=70
f1=.1
f2=.2

To find the altitude at .1,.2 inside of the square we perform a bi-linear interpolation.

value1=100+.1*(200-100) -----> 110

value2=50+.1*(70-50) ----------> 52

finalvalue=110+.2*(52-110) -----> 98.4

So the height at .1x,.1y inside of our square is 98.4.


See how you could filter images with this? Instead of using heights you would use RGB values.

Code:

struct RGB
{
  unsigned char red;
  unsigned char grn;
  unsigned char blu;
};


RGB color1;
RGB color2;
RGB color3;
RGB color4;
RGB finalcolor;

int x=0,y=0;
for (int i=0;i<texsizex;i++)
{
  for (int j=0;j<texsizey;j++)
  {
     i2=i+1;
     j2=j+1;
     if (i2>texsizex) i2=0;
     if (j2>texsizey) j2=0;
     color1.red=Texture[i][j].red;
     color1.grn=Texture[i][j].grn;
     color1.blu=Texture[i][j].blu;

     color2.red=Texture[i2][j].red;
     color2.grn=Texture[i2][j].grn;
     color2.blu=Texture[i2][j].blu;

     color3.red=Texture[i][j2].red;
     color3.grn=Texture[i][j2].grn;
     color3.blu=Texture[i][j2].blu;

     color4.red=Texture[i2][j2].red;
     color4.grn=Texture[i2][j2].grn;
     color4.blu=Texture[i2][j2].blu;

     finalcolor.red=BI(color1.red,color2.red,color3.red,color4.red,.5,.5);
     finalcolor.grn=BI(color1.grn,color2.grn,color3.grn,color4.grn,.5,.5);
     finalcolor.blu=BI(color1.blu,color2.blu,color3.blu,color4.blu,.5,.5);

     Pixel(x,y,finalcolor.red,finalcolor.grn,finalcolor.blu);
     x++;
   }
      x=0;
      y++;
}

Try it some time. This is all done in hardware - not exactly like this, but same idea when your video card filters textures. Notice there is linear filtering (takes 4 pixels in a line and filters them), bi-linear (usually takes 4 nearest pixels and filters them), and trilinear (not sure how to do this yet - probably 3 bilinear interpolations). This can also be done in matrix form which is must faster.

I've got some code that demos what filtering is and would show you what linear and bilinear interpolation do. Let me find em and get back to ya.

There is also cubic interpolation which takes 8 points and filters them - but I'm not sure how to do this either. Voxel maps look very good when using cubic interpolation - albeit it is very slow.

Wow, after about a week of studying that post, I think I finally get what you're saying

Um, so basically, using bilinear interpolation is like checking for a collision on several evenly-spaced points along the line? Then in that case, wouldn't Confuted's solution be faster? (i.e. do an addition and check, addition and check, etc. instead of multiplication/division and check, etc.)

Note: I haven't studied up on the normalized vector section and trivial rejection yet I'll be studying that out over the next week

And, I didn't really get much of the filtering stuff Is that for 3D graphics, or 2D or both?

[quote]
...you could have the point move a smaller number of pixels at a time...
[/uote]

Yes. But how many pixels and in which direction?? Linear interpolation allows you to do this. The only way to find out the increments on x and y are to normalize the vector.

0,50------------------------------->30,100

To get from 0,50 to 30,100 we must know how much to move on x for every y or vice versa. You could use the slope intercept form of a line to find this out or you could normalize the vector.

Normalizing the vector requires using the square root function.

First subtract the points:

diffx=x2-x1 ;30-0=30
diffy=y2-y1 ;100-50=50

so we've moved 30 pixels on x and 50 on y. Very large increments. Too large. So we need to normalize the vector. To normalize a vector you divide the x and y vectors by the total distance between the points.

The distance formula is sqrt((diffx*diffx*)+(diffy*diffy))

Then you divide diffx and diffy by this value to get your x and y normalized vectors. If you increment along this normalized vector - you will stay on the line at all times. To move along the vector in larger increments - simply multiply by a scale factor.

Note that this is also a good way to 'shoot' bullets at another object.

You only need to normalize the vector once so it's not really expensive.

Here is an example that might be in game code for shooting bullets at players/objects. Not the best structure but hey I coded it while sitting here so gimme a break.

Code:

...

struct vector2D
{
  double x;
  double y;
};

struct Bullet
{
  vector2D ScreenPos;
  vector2D VelocityVector;
  double Speed;
}


void Normalize(vector2D *Start,vector2D *End,vector2D *Result)
{
  double diffx=Start->x-End->y;
  double diffy=Start->y-End->y;
  double dist=sqrt((diffx*diffx)+(diffy*diffy));
  Result->x=diffx/dist;
  Result->y=diffy/dist;
}


void ShootBulletAt(vector2D *Source,vector2D *Target,Bullet *NewBullet,double NewSpeed)
{
  vector2D Result;
  
  Normalize(Source,Target,&Result);
  NewBullet->VelocityVector.x=Result->x;
  NewBullet->VelocityVector.y=Result->y;
  NewBullet->ScreenPos.x=(int)Source->x;
  NewBullet->ScreenPos.y=(int)Source->y;
  NewBullet->Speed=NewSpeed;

}

void UpdateBullet(Bullet *tBullet)
{
  Bullet->ScreenPos.x+=(Bullet->VelocityVector.x*Bullet->Speed);
  Bullet->ScreenPos.y+=(Bullet->VelocityVector.y*Bullet->Speed);
}


....

To show you what bilinear interpolation does code this - if you have a DOS compiler and a Win9X platform.

Code:

#include <dos.h>
#include <conio.h>

typedef unsigned char BYTE;

BYTE far *Screen;

#define XYTOMEM(x,y) ((y<<6)+(y<<8)+x)

void SetMode(void);
void Init(void);
void DrawTexture(void);
void FilterTexture(void);
double BI(double v1,double v2,double v3,double v4,double f1,double f2);

void SetMode(void)
{
  asm {
    mov ax,13h
    int 10h
  }
}

void Init(void)
{
  Screen=(BYTE far *)MK_FP(0xa000,0);
  asm {
     push   di
     les      di,[Screen]
     mov    cx,07D00h
     mov    ax,0
     rep     stosw
     pop    di
  }
  SetMode();
}

void DrawTexture
{
  for (int i=0;i<50;i++)
  {
     for (int j=0;j<50;j++)
     {
         Screen[XYTOMEM(i,j)]=16+random(10);
     }
   }
}

void FilterTexture(void)
{
  for (int i=0;i<50;i++)
  {
    for (int j=0;j<50;j++)
    {
      int i2=i+1;
      if (i2>50) i2=0;
      int j2=j+1;
      if (j2>50) j2=0;
      BYTE Pixel1=Screen[XYTOMEM(i,j)];
      BYTE Pixel2=Screen[XYTOMEM(i2,j)];
      BYTE Pixel3=Screen[XYTOMEM(i,j2)];
      BYTE Pixel4=Screen[XYTOMEM(i2,j2)];
      BYTE FilteredPixel=(BYTE)BI((double)Pixel1,(double)Pixel2,(double)Pixel3,(double)Pixel4,.5,.5);
      Screen[XYTOMEM(i,j)]=FilteredPixel;
     }
    }
}

double BI(double v1,double v2,double v3,double f1,double f2)
{
  double val1=0.0,fval=0.0;
  asm {
    
     fld    [v2]
     fsub [v1]
     fmul [f1]
     fadd [v1]
     fstp  [val1]

     fld    [v4]
     fsub [v3]
     fmul [f1]
     fadd [v3]

     fsub [val1]
     fmul  [f2]
     fadd  [val1]
     fstp [fval]
   }

return fval;
}


int main(void)
{
  Init();
  DrawTexture();
  getch();
  FilterTexture();
  getch();

return(0);
}

>>But how many pixels and in which direction??
Well, this is how I implemented it:
-Shot constructor takes an angle as an argument
-Converts the angle to rectangular form using sin/cos (I guess I could generate a lookup table to speed this up)
-Multiply the x direction by (speed / times to increment, say 20), and the same for the y direction
-Store the result in a POINTFLOAT struct
-Use the stored POINTFLOAT to change its position (also a POINTFLOAT) for each move.

Hmm, reading your post over again, that sounds a lot like your linear interpolation - although in my case I start out with an angle to shoot at (the angle that the player's aimer is at), and in your example you started out with a destination to move to.

I have to go now, but I'll stick your bilinear interpolation code into my compiler and see what it is when I have a chance later.

So you are using sin/cos?


#define DEGTORAD(x) (double)(((double)x*PI/180.0))

x+=sin(DEGTORAD(angle))*speed;
y+=cos(DEGTORAD(angle))*speed;


Finding the angle each time seems a bit expensive, but if it works then have at it. I tried using angles in pong but gave up and gave up using angles for projectiles as well. It is much easier to break up the angle into x and y components w/o using sin and cos.

Essentially:

xincrement=cos(DEGTORAD(angle))
yincrement=sin(DEGTORAD(angle))


Yes what you are doing is sort of like a linear interpolation along a vector - the vector is derived from the x and y components of the angle or the sin and cos.

But sin and cos are very slow - almost as slow as the sqrt() but on modern systems perhaps it would not make a diff - unless you get a lot of projectiles in the system.

The only time I use angles is for particle effects like explosions - compute the angle - derive the x and y vectors - move along those vectors.

Store the result in a POINTFLOAT struct

What you said is pretty much what I did, except that I stored the increments in "vect.x" and "vect.y" instead of xincrement and yincrement, and I multiply the x and y increments by speed instead of incrementing by x*speed and y*speed

Although, my old code was horribly inefficient for finding the vector towards a target

Code:

1. Find the slope to the target
2. Use arctan to find the angle <---- !!!
3. Use sin/cos to break the angle into x and y components <---- !!!
4. Move along the x and y increments

And this would have been calculated (number of rockets) times every frame since the angle changed every frame!

Ouch!!


Fastest way I've found is two linear interpolations. I've coded several methods and have been working on this ever since you posted.

Code:

for (double i=0.0;i<.9;i+.1)
{
  int newx=(int)LI(x2,x1,i);
  int newy=(int)LI(y2,y1,i);
  
  if (newx>left && newx<right)
  {
    if (newy>top && newy<bottom)
    {
        ....hit
    }
   }
}

If the distance between the two points is small, you might want to increase the step size or only do one linear interp per axis and find the halfway point. But if you only want the halfway point it is:

Code:

int halfwayx=x1+((x2+x1)>>1);
int halfwayy=y1+((y2+y1)>>1);

I've coded several methods and have been working on this ever since you posted.

*head begins to bloat*

>>Fastest way I've found is two linear interpolations.
Cool Not only does it SOUND impressive, it works good too!

As a side note, would this be a good way to check if an instant-shot (i.e. a laserbeam or something) hits something? I.e. linear interpolate along the aiming vector 1 pixel at a time, and wherever it hits something, draw a line to where it hit?

Also, I plugged your code into my compiler (MSVC), and it came up with about 70 errors After changing asm to _asm, and taking out "far" (It says it's been deprecated or something) and fixing a couple typos, I've reduced it to 2 errors:
-MK_FP (undeclared identifier)
-random (undeclared identifier)

Could you supply the code for MK_FP and random?

Well...that's because that code was 16-bit and was for DOS. If you know DirectX programming you can init DirectX in mode 13h, create a surface, lock it and get a pointer to it - from then on it is exactly like coding in DOS.

You will not use MK_FP() or the make far pointer macro in MSVC. There are no far pointers in protected mode. A far pointer is one that lies outside of your segment, in this case, the video memory. Since in PM there aren't any segments (although Windows is quite confusing here) MK_FP() is obsolete. The random() function is equiv to the rand() % value in MSVC. Locking the surface and using the returned pointer is equiv to getting a far pointer to video memory in real mode.

Random(500) would be rand() % 500. This is how it is in DJGPP - I'm sure there is an equivalent random number generator function in MSVC.

The tile engine source I sent you is purely for MSVC and DirectX so you should not have any probs with it.

If you have a Win9X platform d/l Turbo C from Borland and put this code in it - then it will work. Don't forget to get TASM though and place it in the TC directory - or the asm statements will generate errors.

>>Well...that's because that code was 16-bit and was for DOS.
Ah, ok. Wasn't sure if "console" would count as DOS.

I'll see what I can do with DirectX-erizing it...