Halomods Community Portal: Collision BSP structure - Halomods Community Portal

Jump to content

Page 1 of 1
  • You cannot start a new topic
  • You cannot reply to this topic

H1_Xbox
Collision BSP structure

#1 User is offline   xorgasm 

  • Member
  • PipPip
  • Group: Members
  • Joined: 26-August 11

Posted 26 August 2011 - 02:22 AM

Has anyone actually figured out how the collision BSP works in halo? I've been on and off following the halo-mods scene for years, and it always seemed like a crucial part of the blam! engine that no one really cared about reversing.

A few months ago I took a look at it, and it seemed pretty straight forward (except the 2dBsp, which took me a about a week to figure out.) I'm pretty confident I could do ray-bsp intersection tests on it, and I'm almost confident that (with a bit of trial and error) I could build one, or at least write a program to build one.

#2 User is offline   Ogrish 

  • Member
  • PipPip
  • Group: Members
  • Joined: 06-May 11
  • LocationCali

Posted 02 September 2011 - 10:15 PM

This would be more beneficial in Halo two, but please continue, and post your results.

#3 User is offline   xorgasm 

  • Member
  • PipPip
  • Group: Members
  • Joined: 26-August 11

Posted 02 September 2011 - 11:58 PM

Well, IIRC, the collision bsp structure between the two games is fairly similar, so whatever I tell you about H1 should be somewhat applicable to H2. I think the structure of the BSP tag only really heavily changes between H2 and H3, but don't quote me on that, I haven't really looked into H3 much.

What you should know to understand the following text:
1. Be somewhat familiar with linear algebra and 3d graphics (Plane-normal form, dot product, projections, convexity, etc...).
2. Data structures (half edge list, trees, etc...)
3. Probably more

Okay, so, let me start off with a bit of an intro concerning what a BSP is and how it's used in Halo. Essentially, a BSP is a binary tree that sub-divides the world into smaller, more manageable chunks (O(log2(n)) lookup for these chunks.) (http://en.wikipedia....ce_partitioning is a bit technical. http://realtimecollisiondetection.net/ is however, worth a read.) Each chunk (or leaf) contains a reference to all the surfaces in that chunk, and reference to the cluster that contains that chunk. As a consequence the collision BSP gets used not only for collision, but for scene visibility (alongside a PVS which allows the engine to draw only the clusters that are visible, and a portal system to cull away objects that can't be seen by the player.)


Part 1: Point->cluster Identification:
I'll start off my explanation with a simple example. Given some point P, I want to find the leaf (and cluster) in which it resides. Basically, this gives us enough information render the the world such that we only draw clusters that're visible.
All I really have to do, is traverse the tree until I get to a leaf node.

I'll consider these three structures of the collision BSP block:
struct CollisionBSP{

struct Bsp3dNode{
    int32 plane;  // if < 0, then the plane is flipped (I'm not 100% sure about that though)
    int32 backNode; // if < 0, then the left node is a leaf, the leaf index can be obtained by masking off the MSB from the node (Ex: leaf = node & 0x7FFFFFFF;)
    int32 frontNode; // if < 0, then the right node is a leaf, see above
};

struct Plane{ //I think that this is traditionally (i,j,k,d), but I  like my naming scheme better.
    float a; 
    float b;
    float c;
    float d;
};

struct Leaf3d{
   int flags;
   int bsp2dRef; // Don't worry about this right now
   int bsp2dCount; // Don't worry about this right now
};

Bsp2dRef{};
Bsp2dNodes{};
Surfaces{};
Edges{};
Verticies{};
}


And this one as well (the leaves block of the BSP tag):
// Note that these are an extension to the Leaf3d block of the collision structure
struct Leaves{
   int cluster;
   int surfaceRefCount;
   int surfaceRef;
};


So, start at the root node (node 0), test a point against the plane, and see whether you should follow the left node, or the right node, do this until you hit a leaf, or -1.
int findClusterForPoint(Point P)
   return traverseBspTree(0, P);

int traverseBspTree(int node, Point P)
  if(node == -1) // I'm still not 100% sure what -1 means, but I'm almost positive it means that the point fell outside the BSP.
     return -1;

  if(node < 0) // we've hit a leaf, return the cluster 
     return Leaves[node &0x7FFFFFFF].cluster;

  Plane N = getPlane(Node3d[node].plane);
  float d = dot3(N.abc,P.xyz) - N.d; // if this is < 0 the point is behind the plane, if > 0 it's in front
  if(d > 0)
     return traverseBspTree(Node3d[node].frontNode, P);
  return traverseBspTree(Node3d[node].backNode, P);

Now you have your cluster index, and you can refer to the PVS to properly render the scene.

Part 2: BSP & Line Segment Intersection:
I'll define a line segment 'L' as the line between two points P, Q. From this, any point on L can be written as:
P'(t) = P + t(Q-P)
Where P and Q are 3d points, and t is a real scalar value such that 0<=t<=1.

For readability, I'll let:
V = (Q-P)

So we have:
P'(t) = P + tV

Now, we essentially do the same thing as above, but things are a little more complicated now since:
  • We're dealing with a line segment that may need to be split
  • We're not just stopping at the 3d leaves


In part 1, we traversed the tree all the way down to a leaf. A 3dLeaf is essentially a collection of surfaces. To complete the collision detection, we have to see if our line segment intersects with any of those surfaces (more on this later).

Point findIntersection(Point P, Point Q)
   return traverseBspTree(0, P, Q);

Point traverseBspTree(int node, Point P, Point Q)
  if(node == -1) // I'm still not 100% sure what -1 means, but I'm almost positive it means that the point fell outside the BSP.
     return NULL;

  if(node < 0) // we've hit a leaf, preform hit test
     return hitTestLeaf(node & 0x7FFFFFFF, P, Q);

  Plane N = getPlane(Node3d[node].plane);
  float s = dot3(N.abc,P.xyz) - N.d; // if this is < 0 the point is behind the plane, > 0 in front
  float t = dot3(N.abc,Q.xyz) - N.d; // same as above, but for Q
  /*
    If both s and t are > 0 then we know the line segment is completely to the front of the plane.
    Likewise if s and t are < 0 then we know they're both behind the plane.
    But if  s > 0 and t  < 0  or s < 0 and t > 0, we know the segment straddles the plane, so we need to compute two line segments
    (P, Pn) (Qn,Q) where Pn and Qn almost lie on the plane N.
  */
  if(s > 0 && t > 0)
     return traverseBspTree(Node3d[node].frontNode, P, Q);
  if(s < 0 && t < 0)
     return traverseBspTree(Node3d[node].backNode, P, Q);
  // I can derive this on request, but now I'll find P', and Q'

  Point Pn, Qn, S, T;
  Vector V = Q-P;
  float ins = -(N.d + dot3(P,N))/dot3(V, N);
  // Now we have it that so that P+ins*V lies on the plane N
  
  // we have to make sure that the new line (P, Pn) can still intersect the splitting plane
  // so we fudge ins a little bit to make sure that it can still intersect with N (since the splitting plane may contain 
  // the surface that we want to have an intersection test against in the leaf)
  Pn= P+(ins+EPSILON)*V;
  Qn= Q+(ins-EPSILON)*V; // Same thing with (Q, Qn)

  if(s < 0) // If P,Pn is behind the plane we need to test the new segment against the back-node
      S = traverseBspTree(Node3d[node].backNode, P, Pn);
      T = traverseBspTree(Node3d[node].frontNode, Qn, Q);
  else 
      S = traverseBspTree(Node3d[node].frontNode, P, Pn);
      T = traverseBspTree(Node3d[node].backNode, Qn, Q);

   if(S is closer to P than T)
       return S
   return T


To continue I'll need the last few structures of the collision bsp.

struct CollisionBSP{
 ... 
 //Todo: explain this stuff better
   Bsp2dRef{
      int plane; // The plane used to decide what basis plane is best to project on (X,Y), (Y,Z) or (X,Z)
      int node; // starting node, if < 0 then node refers directly to a surface
   };
   Bsp2dNodes{
     float a;    // ab and d uniquely define a 2d plane 
     float b;
     float d;
     int leftChild; // if < 0 this refers to a surface (Ex, surface = leftChild & 0x7FFFFFFF;
     int rightChild;
   };

   Surfaces{
      int plane;
      int firstEdge;
      int SomeOtherstuffs;
   };
   Edges{  // Half edge data structure see:
     int startVertex;
     int endVertex;
     int forwardEdge;
     int reverseEdge;
     int leftFace;
     int rightFace;
   };
   Verticies{
      float x,y,z;
      int firstEdge;
   };
}


When I said that leaves contained a collection of surfaces, it was a bit of a simplification. Leaves actually contain a collection of 2dBsps. The 2dBsp is a way of splitting the faces on each leaf reference so you can get O(log2m) operations on a each leaf reference(where m is the number of surfaces referenced by a 2dBsp). So each leaf has a 2dBsp for each unique plane that can be represented by the faces in that specific leaf.

So, for example, if a leaf had four faces, but two of them landed on the same plane, you'd get a total of three 2dBspRefs. Two would be for the two non-co-planar faces (and these would point directly to surfaces), and one would be for the two co-planar faces, (which would have a 2dBsp with one node splitting them.)

Leaf code:
Point hitTestLeaf(int leaf, Point P, Point Q)
   int reference = Leaf3d[leaf].bsp2dRef;
   Point S = {NaN, NaN, NaN}, T;

   // For every bsp2d reference in the leaf
   for(int i = 0; i < Leaf3d[leaf].bsp2dRefCount; i++)

        Plane N = getPlane(Bsp2dRef[reference+i].plane);

        // check if the line segment crosses the 2d plane upon which the 2dBsp was projected
        float s = dot3(N.abc,P.xyz) - N.d; 
        float t = dot3(N.abc,Q.xyz) - N.d; 

        if(s*t >= 0) // if the line does not cross the plane, don't consider it
            continue;
        
        Vector V = Q-P;
        float ins = -(N.d + dot3(P,N))/dot3(V, N);

        T = P + V*ins;
        Point2D Tp = HaloProjectPoint2D(N, T);

        if(HitTestBsp2d(Bsp2dRef[reference+i].bsp2dNode, T, Tp) & T is closer to P than S)
             S = T 
   return S;



You may have noticed the HaloProjectPoint function. Think about it, the 2dBsp is just that 2 dimensional, but we're working with 3d points. So we have to figure out a projection onto one of the three basis planes (XY YZ ZX) plane.

boolean HitTestBsp2d(int node, Point T, Point2D Tp)
    if(node < 0)
         return surfaceTest(node & 0x7FFFFFFF, T)

    float s = dot2(Bsp2dNode[node].ij, Tp.xy) - Bsp2dNode[node].d);
    if( s > 0)
        return HitTestBsp2d(Bsp2dNode[node].rightNode, T, Tp);
   
    return HitTestBsp2d(Bsp2dNode[node].ledtNode, T, Tp);

Point2D HaloProjectPoint2D(Plane N, Point P) // This is not the best implementation to deal with projections, but it's meant to teach how they work, not to teach the best way to use them
   // First find the component of the plane normal that is the most significant
   float x = fabs(N.a);
   float y = fabs(N.B)/>;
   float z = fabs(N.c);
   int projectionAxis = 0;
   int sign = 0; // 0 means the projection axis was negative, 1 means positive

   if (z < y || z < x)
      if (j < i) // X axis has the greatest contribution
         projectionAxis = 0;
      else // Y axis has the greatest contribution
         projectionAxis = 1;
   else // otherwise Z had the greatest contribution
      projectionAxis = 2;

   if(N.abc[projectionAxis] > 0.f)
       sign = 1;

   // Choose the projection plane
    static short planeIndex[][][] = {
// Negative
    {{2, 1},  //Z,Y
    {0, 2}, //X,Z
    {1, 0}}, //Y,X
	
// Positive
    { {1, 2},  // Y, Z
      {2, 0}, // Z, X
      {0, 1}}};// X, Y
   
   return Point2D(P.xyz[planeIndex[sign][projectionAxis][0]], P.xyz[planeIndex[sign][projectionAxis][1]]);


We've essentially deduced what surface we /might/ have an intersection with, we don't know for sure yet, we only know that our line segment intersects the plane which the surface lies on. Finally we need to test to see if the point T actually falls within that surface.

boolean surfaceTest(int surface, Point T)
	// Follow the edges with our surface
	// Compute the angles between the point and all the edges
	// if they add up to 2*PI, then the point is inside the polygon

	nextEdge = Surfaces[surface].firstEdge;
  	do{
		currentEdge = nextEdge;
		if (surface == Edge[currentEdge].leftSurface) {

			//follow forward edge and take
			//startVertex -> endVertex

			P = Vertex[Edge[currentEdge].startVertex];
			Q = Vertex[Edge[currentEdge].endVertex];
			
			nextEdge = Edge[currentEdge].forwardEdge;		

		}else{ //(s == c->Edge[nextEdge].rightSurface){
			
			//follow reverse edge and take
			// endVertex -> startVertex

			P = Vertex[Edge[currentEdge].endVertex];
			Q = Vertex[Edge[currentEdge].startVertex];
			
			nextEdge = Edge[currentEdge].reverseEdge;
		}
		// Get the angle between (Q-P) and (P-T)
 		angleSum += acos(dot3((Q-P),(T-P)))

		// Get the angle between (P-Q) and (Q-T)
 		angleSum += acos(dot3((P-Q),(Q-T)))
		
	}while(nextEdge != Surfaces[surface].firstEdge)
	if(fabs(angleSum - 2*Math.PI )< EPSILON)
		return true;
	return false;


That's essentially it. I'll probably take another go at this in a week or two, just to correct any mistakes and to make an attempt to explain everything better.

Part 3: Building a BSP:
I haven't actually built a bsp yet, but I assume it should follow roughly this procedure:
  • Create half edge data structure from geometry
  • Create Bsp3d nodes/leafs
  • For each leaf, create Bsp2d nodes/leafSurfaces.
  • Optimize structures

To be continued. This'll take me a while to write up, so I'll update it incrementally.

This post has been edited by xorgasm: 04 September 2011 - 09:55 PM


#4 User is offline   x86melter 

  • Member
  • PipPip
  • View blog
  • Group: Members
  • Joined: 23-July 11

Posted 09 September 2011 - 12:42 AM

Am I the only one who realizes how AWESOME this is? I have read up on bsp but I always get lost when I dive into the formulas and technical aspect. Never really had the patience, but this is intriguing me.

Nice. Work. Mang.

If I can catch up, I will undoubtedly join your bsp conquest. As I said in my message, I am interested in collision detection and ray-tracing. I once wrote a working ray-sphere intersection algorithm for objects, but it is now lost. Of course it wasn't that useful since I didn't know how to detect if an object(or the bounding sphere rather) was visible through bsp. :(

#5 User is offline   xorgasm 

  • Member
  • PipPip
  • Group: Members
  • Joined: 26-August 11

Posted 09 September 2011 - 02:10 AM

Well, IIRC, Sphere->ray intersection goes something like this:

Any point P on the surface of a sphere has a distance of radius ® to the centre point of the sphere ( call it C)

So, you can represent that with the dot product as: (Dot product is shown as multiplication *)

((P-C)*(P-C)) = r2

Then you take the equation of a ray and say that any point P' on that half-line can be represented by:
P'(t) = S + t*V

Where V is your direction vector, S is your starting point and t is some variable (which you'll solve for later.)
Now you're essentially looking at the case where P'(t) = P, for some t.

So, solve the following for t:
((P'(t)-C)*(P'(t)-C)) = r2

Which is:
((S + t*V - C)*(S + t*V - C)) = r2

Let L = S-C (to make my life simpler):
((t*V + L)*(t*V + L)) = r2

The dot product shares some aspects of multiplication, so you can essentially expand dot3((t*V + L),(t*V + L)) to:
((t*t*V*V)) + 2*(t*V*L) + (L*L) = r2

Then you end up with:
(t2*V*V) + 2*(V*L)*t + (L*L)-r2 = 0

Which is a quadratic equation with a = V*V, b = 2*(V*L) and c = L*L-r2
Then you can just use the quadratic equation to solve that for t, and plug those values into P'(t).

Wow, I did not expect to write that much.

#6 User is offline   CLuis 

  • Newbie
  • Pip
  • Group: Members
  • Joined: 10-May 11

Posted 20 November 2011 - 09:15 AM

That is awesome information. Good job!

#7 User is offline   xorgasm 

  • Member
  • PipPip
  • Group: Members
  • Joined: 26-August 11

Posted 22 November 2011 - 03:44 AM

Thanks,

I've been meaning to take all this a bit further, and try to generate a BSP from a set of mesh data, but it's a lot more work than it first appears to be. It's really hard to generate just one section of the BSP without the rest, since there's a lot of cross structure data. Not only that, but this has been a pretty intense semester, and I don't really have a lot of time to work on side projects.

Share this topic:


Page 1 of 1
  • You cannot start a new topic
  • You cannot reply to this topic

1 User(s) are reading this topic
0 members, 1 guests, 0 anonymous users