Reverse Engineering References

[Skarma]

Halo uses frustum culling on sphere bounding volumes to determine object visibility. There is a sphere-tree in memory I found that contains all the necessary information to determine if an object is completely outside, partially inside, or completely inside the view frustum. All the frustum plane normals and positions are calculated and filled into the sphere-tree before the object rendering code is even called, not sure exactly how or where yet.

The sphere-tree is located at memory address 0x0075E2B0 for Halo CE 1.08, if you want to check it out. It is an array of 128? possible sphere volumes. The format is this:

Note: The plane normals, plane positions, and unknown reals are quaternions. There is a total of 6 planes in the view frustum.

struct BoundingSphere
{
  uint32 Index;
  real UnknownReal[4];
  BoundingFrustum Frustum;
  int8 padding[76];
};

Needed declarations for the function

#define OUT_FRUSTUM     0
#define PARTIAL_FRUSTUM 1
#define IN_FRUSTUM      2
 
 
#define DotProduct(a,b) ((a)[0] * (b)[0] + (a)[1] * (b)[1] + (a)[2] * (b)[2])
 
 
typedef unsigned int uint32;
typedef unsigned short uint16;
typedef float real;
 
struct BoundingFrustum
{
  real UnknownReal[27];
  real PlaneNorm[6][4];
  real NearClippingDistance;
  real FarClippingDistance;
  real PlanePos[6][4];
};

uint16 GetObjectVisibility(real *SphereCentre, BoundingFrustum *Frustum, real SphereRadius)
{
  real Distance[6];
 
  if((SphereCentre[0] - SphereRadius) > Frustum->PlanePos[4][3]) return OUT_FRUSTUM;
  if((SphereCentre[1] - SphereRadius) > Frustum->PlanePos[5][1]) return OUT_FRUSTUM;
  if((SphereCentre[2] - SphereRadius) > Frustum->PlanePos[5][3]) return OUT_FRUSTUM;
 
  if((SphereCentre[0] + SphereRadius) < Frustum->PlanePos[4][2]) return OUT_FRUSTUM;
  if((SphereCentre[1] + SphereRadius) < Frustum->PlanePos[5][0]) return OUT_FRUSTUM;
  if((SphereCentre[2] + SphereRadius) < Frustum->PlanePos[5][2]) return OUT_FRUSTUM;
 
  for(uint32 i = 0; i < 6; i++)
  {
    Distance[i] = DotProduct(Frustum->PlaneNorm[i], SphereCentre) - Frustum->PlaneNorm[i][3];
    if(Distance[i] > SphereRadius) return OUT_FRUSTUM;
  }
 
  for(uint32 i = 0; i < 6; i++)
  {
    if(i==4) continue; // doesn't check the 5th plane
    if(Distance[i] > -SphereRadius) return PARTIAL_FRUSTUM;
  }
 
  return IN_FRUSTUM;
}