Path: chuka.playstation.co.uk!scea!peter_alau@playstation.sony.com
From: "Jamin Frederick" <jamin1@psu.edu>
Newsgroups: scea.yaroze.programming.2d_graphics
Subject: cd.c
Date: Mon, 4 Jan 1999 14:44:58 -0800
Organization: SCEA News Server
Lines: 333
Message-ID: <76r57s$jm41@scea>
NNTP-Posting-Host: dialup260-pri.voicenet.com
X-Newsreader: Microsoft Outlook Express 4.72.3110.1
X-Mimeole: Produced By Microsoft MimeOLE V4.72.3110.3


//  Collision Detection Algorithm
//  by Jamin Frederick (jamin1@psu.edu)
//  http://www.cse.psu.edu/~frederic
//
//Freely Distributable (under Yaroze license)
//Let me know if this is of use to you!
//
//CD.C
//implementation of 8-bit pixel-by-pixel sprite collision detection

//-----------------------------------------------------------------------

#include <libps.h>
#include "cd.h"

//-----------------------------------------------------------------------

 int CollisionDetect(GsSPRITE* pSpritePtrA, GsSPRITE* pSpritePtrB,
  GsIMAGE* pImagePtrA, GsIMAGE* pImagePtrB, unsigned char* pHitAu,
  unsigned char* pHitAv, unsigned char* pHitBu, unsigned char* pHitBv)
  {
  //
  //
  //
  //    (this illustration is a particular case)
  //
  //
  //
  //
  //         (ax1,ay1)
  //             +--------------+
  //             |              |
  //             |  <sprite a>  |
  //             |              |      (in world)
  //             |              |
  //             |              |
  //             |  (bx1,by1)   |
  //             |     +--------+------+
  //             |     |        |      |
  //             +-----+--------+      |
  //                   |    (ax2,ay2)  |
  //                   |               |
  //                   |               |
  //                   |   <sprite b>  |
  //                   |               |
  //                   +---------------+
  //                                 (bx2,by2)
  //
  //
  //
  //          (0,0)  [w.r.t. sprite a's (u,v) coords]
  //             +--------------+
  //             |              |
  //             |              |
  //             |              |     sprite a
  //         ah  |              |   (in main mem)
  //             |              |
  //             |(au1,av1)     |
  //             |     +--------+
  //             |     |        | --> (isw x ish)
  //             +-----+--------+
  //                         (au2,av2) = (aw-1,ah-1)
  //                    aw
  //
  //
  //
  //              (bu1,bv1) = (0,0)  [w.r.t. sprite b's (u,v) coords]
  //                    +--------+------+
  //    (isw x ish) <-- |        |      |
  //                    +--------+      |
  //                    |    (bu2,bv2)  |     sprite b
  //                bh  |               |   (in main mem)
  //                    |               |
  //                    |               |
  //                    |               |
  //                    +---------------+
  //                                (bw-1,bh-1)
  //                           bw
  //
  //
  //
  //
  // Assumptions:
  //
  //   1) both sprites are 8-bit
  //
  //   2) TIM images (sprite pixel and clut data) still
  //      maintained in main memory; parameter GsIMAGE
  //      structs contain this information if previosly
  //      used with GsGetTimInfo()
  //
  //   3) uses (x,y) position inside GsSPRITE structs as world
  //      coords; hence the collision is based on what you'd
  //      see on-screen, so be sure to update your GsSPRITEs' (x,y)
  //      values before calling this function

  // Return Values:
  //
  //   1) return: collision (TRUE) or non-collision (FALSE)
  //
  //   2) parameters: the (u,v) coords within each sprite image
  //      corresponding to the first mutually non-black pixel
  //      detected; on-screen, this is the first intersected
  //      non-black pixel found of the two sprites; this pixel
  //      is naturally inside the calculated intersection rects
  //
  // Comments:
  //
  //   1) all variables declared static to reduce stack overhead
  //      in case this function is called frequently
  //
  //   2) users of this function may NULL out return parameters if
  //      they're not needed
  //
  //   2) probably could be optimized
  //
  //   3) may be changed to include 4-bit or 16-bit sprites;
  //      I chose 8-bit to reduce the logic processing of
  //      different compressions, and I figured that most
  //      people use 8-bit sprites for most collision detection
  //      purposes anyway
  //
  //

  //table to store possible transparent-black clut entries;
  //  one allocated for each sprite
  static int lClutTableA[256];
  static int lClutTableB[256];

  //count of transparent-black clut entries for each
  //  corresponding sprite
  static int lBlackCntA;
  static int lBlackCntB;

  //32-bit memory pointers for byte indexing
  static ulong* lMemPtrA;
  static ulong* lMemPtrB;

  //offset pixel byte (8 bits) into 32-bit pointers
  static int lMemShiftA;
  static int lMemShiftB;

  //width and height of sprite a and sprite b
  static int aw;
  static int ah;
  static int bw;
  static int bh;

  //intersect horizontal and vertical offsets
  static int ox;
  static int oy;

  /* NOT USED
  //intersect width and height
  static int isw;
  static int ish;
  */

  //(center-translated) world rectangle (x,y) of sprite a
  static int ax1;
  static int ay1;
  static int ax2;
  static int ay2;

  //(center-translated) world rectangle (x,y) of sprite b
  static int bx1;
  static int by1;
  static int bx2;
  static int by2;

  //sprite a's memory (u,v) intersect rectangle
  static int au1;
  static int av1;
  static int au2;
  static int av2;

  //sprite b's memory (u,v) intersect rectangle
  static int bu1;
  static int bv1;
  static int bu2;
  static int bv2;

  //indices for pixel-by-pixel comparison of resultant (u,v) rects
  static int ay;
  static int by;
  static int ax;
  static int bx;

  //index
  static int i;

  //calculate (center-translated) world rectangle (x,y) of sprite a
  ax1 = pSpritePtrA->x - pSpritePtrA->mx;
  ay1 = pSpritePtrA->y - pSpritePtrA->my;
  ax2 = ax1 + pSpritePtrA->w - 1;
  ay2 = ay1 + pSpritePtrA->h - 1;

  //calculate (center-translated) world rectangle (x,y) of sprite b
  bx1 = pSpritePtrB->x - pSpritePtrB->mx;
  by1 = pSpritePtrB->y - pSpritePtrB->my;
  bx2 = bx1 + pSpritePtrB->w - 1;
  by2 = by1 + pSpritePtrB->h - 1;

  //bounding box test (usual case is no intersection...)
  if((ax1 > bx2 || bx1 > ax2) || (ay1 > by2 || by1 > ay2))
    return FALSE;

  //******* bounding box intersection...now try pixel-by-pixel ********

  //assign widths and heights for fast calculation
  aw = pSpritePtrA->w;
  ah = pSpritePtrA->h;
  bw = pSpritePtrB->w;
  bh = pSpritePtrB->h;

  //calculate intersect offsets
  ox  = ax1 + aw - bx1;
  oy  = ay1 + ah - by1;

  //calculate horizontal offsets from u=0
  au1 = MAX(0, aw - ox);
  au2 = MIN(aw - 1, aw - ox + bw - 1);
  bu1 = MAX(0, ox - aw);
  bu2 = MIN(bw - 1, ox - 1);

  //calculate vertical offsets from v=0
  av1 = MAX(0, ah - oy);
  av2 = MIN(ah - 1, ah - oy + bh - 1);
  bv1 = MAX(0, oy - ah);
  bv2 = MIN(bh - 1, oy - 1);

  /* NOT USED
  //calculate intersect width and height from sprite a's u-v rect
  isw = au2 - au1 + 1;
  ish = av2 - av1 + 1;
  */

  //reset mem pointer to first clut word (each containing 2 16-bit entries)
  lMemPtrA = pImagePtrA->clut;
  lMemPtrB = pImagePtrB->clut;
  lBlackCntA = 0;
  lBlackCntB = 0;

  //record transparent-black clut entries for sprites a and b
  for(i = 0; i < 256; i++)
    {
    if((ushort)(*lMemPtrA >> 16 * (i % 2)) == 0x0000)
      lClutTableA[lBlackCntA++] = i;

    if((ushort)(*lMemPtrB >> 16 * (i % 2)) == 0x0000)
      lClutTableB[lBlackCntB++] = i;

    lMemPtrA += i % 2;
    lMemPtrB += i % 2;
    }

  //try to find a pair of corresponding pixels with non-black entries;
  //  loop: scan sprite (u,v) coords vertically, top to bottom
  for(ay = pSpritePtrA->v + av1, by = pSpritePtrB->v + bv1; ay <=
pSpritePtrA->v + av2; ay++, by++)
    {
    //reset pointers to beginning of horizontal scan line
    //  (dividend for 8-bit pixels)
    lMemPtrA   = pImagePtrA->pixel + (2 * pImagePtrA->pw * ay +
pSpritePtrA->u + au1) / 4;
    lMemPtrB   = pImagePtrB->pixel + (2 * pImagePtrB->pw * by +
pSpritePtrB->u + bu1) / 4;
    //reset offsets via modulus using total pixels before current
    //  (ax,ay) and (bx,by) -- for 8-bit pixels
    lMemShiftA = (2 * pImagePtrA->pw * ay + pSpritePtrA->u + au1) % 4;
    lMemShiftB = (2 * pImagePtrB->pw * by + pSpritePtrB->u + bu1) % 4;
    //loop: scan sprite (u,v) coords horizontally, left to right
    for(ax = pSpritePtrA->u + au1, bx = pSpritePtrB->u + bu1; ax <=
pSpritePtrA->u + au2; ax++, bx++)
      {
      //loop until any black entries have been found for sprite a's
      //  current pixel (or none have been found, hence i == lBlackCntA)
      for(i = 0; i < lBlackCntA; i++)
        {
        if((*lMemPtrA >> 8 * lMemShiftA & 0xFF) == lClutTableA[i])
          break;
        }
      //if there wasn't a black entry match for sprite a's pixel, then
      //  the corresponding pixel for sprite b has to be also checked
      //  for non-blackness
      if(i == lBlackCntA)
        {
        //loop until any black entries have been found for sprite b's
        //  current pixel (or none have been found, hence i == lBlackCntB)
        for(i = 0; i < lBlackCntB; i++)
          {
          if((*lMemPtrB >> 8 * lMemShiftB & 0xFF) == lClutTableB[i])
            break;
          }
        //if there wasn't a black entry match for sprite b, then, since
        //  sprite a also had no black entry match, there is a collision
        //  on this pixel
        if(i == lBlackCntB)
          {
          //if the user didn't null out any parameters, fill into the
          //  parms the first pixels (u,v) that intersected
          if(pHitAu != NULL && pHitAv != NULL &&
            pHitBu != NULL && pHitBv != NULL)
            {
            *pHitAu = (unsigned char) ax;
            *pHitAv = (unsigned char) ay;
            *pHitBu = (unsigned char) bx;
            *pHitBv = (unsigned char) by;
            }
          //collision detect! go home
          return TRUE;
          }
        }

      lMemShiftA = (lMemShiftA + 1) % 4;
      lMemShiftB = (lMemShiftB + 1) % 4;

      //time to increase the pointer if all the bytes at the current ulong
      //  location have been "used up"
      if(lMemShiftA == 0)
        lMemPtrA++;
      if(lMemShiftB == 0)
        lMemPtrB++;
      }
    }

  //no pixels in the intersection rect had corresponding non-black entries;
  //  go home with no collision detected
  return FALSE;
  }