quake3format.htm

用opengl实现的bsp管理3D场景的算法

  works:
  </p>
  <p class="MsoBodyText">
  With cluster A, B and C, here is how they would be represented in binary (a
  bitset):
  </p>
  <p class="MsoBodyText">
  ABC<br>
  000
  </p>
  <p class="MsoBodyText">
  Each 0 represents a slot that is assigned to a cluster.&nbsp; Let's assume
  that:
  </p>
  <p class="MsoBodyText">
  - Cluster A can see cluster B and not C<br>
  - Cluster B can see cluster A and C<br>
  - Cluster C can see cluster B and not A
  </p>
  <p class="MsoBodyText">
  Below is a representation of each one of their bitsets:
  </p>
  <p class="MsoBodyText">
  - A&nbsp;&nbsp;&nbsp;&nbsp; 110<br>
  - B&nbsp;&nbsp;&nbsp;&nbsp; 111<br>
  - C&nbsp;&nbsp;&nbsp;&nbsp; 011
  </p>
  <p class="MsoBodyText">Does that make sense?&nbsp; Notice for A there is a 1
  in the first slot which means it can see itself, and also in the second slot
  which means it can see cluster B.&nbsp; The last slot is a 0, which tells us
  that cluster A can not see what's in cluster C because some walls or whatever
  are blocking it.&nbsp; This is where the good spatial partition speed comes
  in.&nbsp; If you are in the very bottom corner of the level in a small little
  room, you just cust out probably 95% percent of the polygons that need to be
  rendered because you can only most likely see the cluster that is right
  outside of that room.
  </p>
  <p class="MsoBodyText">To test if a cluster is visible from another cluster,
  there is obviously going to have to be some bit-shifting and other binary math
  involved.&nbsp; The basic algorithm to test a cluster against another cluster
  is as follows:
  </p>
  <p class="MsoBodyText">int visible = pVecs[currentCluster*vectorSize + (
  testCluster/8 )] &amp; (1 &lt;&lt; (testCluster &amp; 7))&nbsp;
  </p>
  <p class="MsoBodyText">If the result of <b>visible</b> isn't 0, then the <b>testCluster</b>
  can be seen from the <b>currentCluster</b>.&nbsp; We divide and % (mod) by 8
  because we are using <b>byte</b>s which are 8 bits.&nbsp; Basically, the first
  part is indexing into the array of clusters to find the correct bitset, then
  we do a binary &amp; (and) with the cluster we are testing to get the result.
  </p>
  <p class="MsoBodyText">Here is some basic code to do a cluster to cluster
  test:
  </p>
  <p class="MsoBodyText">
  <font face="Courier New" size="2">inline int <b>IsClusterVisible</b>(tVisData *pPVS, int current, int test)<br>
  {<br>
  &nbsp;&nbsp;&nbsp; if(!pPVS-&gt;pVecs || current &lt; 0) return 1;<br>
  <br>
   &nbsp;&nbsp;&nbsp; byte  vector=pPVS-&gt;pVecs[(current*pPVS-&gt;vectorSize) + (test/8)];<br>
  &nbsp;&nbsp;&nbsp; int result = vector &amp; (1 &lt;&lt; (test &amp; 7));<br>
  <br>
  &nbsp;&nbsp;&nbsp; return ( result );<br>
  }</font>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Entities</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The entity lump just stores a huge string with each
  line delimited by '\n'.&nbsp; Some types of things stored in this string is
  the deathmatch positions for the players in the beginning, weapon positions,
  sky box information, light positions, etc...&nbsp; I suggest you save it off
  to a file so that you can get a good idea on how to parse it.&nbsp; Be careful
  when writing a parser, things aren't always saved in the same order.&nbsp;
  Player positions usually store the 3D position on the map, along with the
  orientation described by a rotation angle.&nbsp; To find the length of the
  entity string to read in, just divide the entity lump's <b>length </b>by
  sizeof(<b>char</b>).
  </p>
  <p class="MsoBodyText">char *<b>strEntities</b>;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // This stores a huge string of all the entities in the level
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Brushes</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The brushes store information about a convex volume,
  which are defined by the brush sides.&nbsp; Brushes are used for collision
  detection.&nbsp; This allows the level editor to decide what is collidable and
  what can be walked through, such as trees, bushes or certain corners.
  </p>
  <p class="MsoBodyText">
  <code><font size="2" face="Courier New">struct <b>tBSPBrush</b>&nbsp;<br>
  {<br>
  &nbsp;&nbsp;&nbsp; int brushSide;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The starting brush side for the brush&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int numOfBrushSides;&nbsp;&nbsp;&nbsp;&nbsp; // Number of
  brush sides for the brush<br>
  &nbsp;&nbsp;&nbsp; int textureID;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The texture index for the brush<br>
  };</font></code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Leaf Brushes</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">Like the leaf faces, leaf brushes are used to index
  into the <b>tBSPBrush</b> array.&nbsp; Once again, brushes are used for
  collision detection.&nbsp; To calculate the number of leaf brushes in the lump
  you divide the <b>length</b> of the lump by the sizeof(<b>int</b>).&nbsp;
  </p>
  <p class="MsoBodyText">
  <code>int *<font size="2"><b>pLeafBrushes</b></font>;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The index into the brush array</code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Brush Sides</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The brush sides lump stores information about the brush
  bounding surface.&nbsp; To calculate the number of brush sides, just divide
  the lumps <b>length</b> by sizeof(<b>tBSPBrushSides</b>).
  </p>
  <p class="MsoBodyText">
  <font size="2" face="Courier New">struct <b>tBSPBrushSide</b>&nbsp;<br>
  {<br>
  &nbsp;&nbsp;&nbsp; int
  plane;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The plane index<br>
  &nbsp;&nbsp;&nbsp; int textureID;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The texture index<br>
  };</font>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Models</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The model structure stores the face and brush
  information, along with the bounding box of the object.&nbsp; These objects
  can be movable such as doors, platforms, etc...&nbsp; To calculate the number
  of models in this lump, just divide the <b>length</b> of the lump by sizeof(<b>tBSPModel</b>).
  </p>
  <p class="MsoBodyText">
  <font size="2" face="Courier New">struct <b> tBSPModel</b>&nbsp;<br>
  {<br>
  &nbsp;&nbsp;&nbsp; float min[3];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The min position for the bounding box<br>
  &nbsp;&nbsp;&nbsp; float max[3];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The max position for the bounding box.&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int faceIndex;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The first face index in the model&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int numOfFaces;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The number of faces in the model&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int brushIndex;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The first brush index in the model&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int numOfBrushes;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //
  The number brushes for the model<br>
  };</font>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Mesh Vertices</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">This stores a list of vertex offsets that are used to
  create a triangle mesh.&nbsp; To calculate the number of mesh vertices in the
  lump you divide the <b>length</b> of the lump by the sizeof(<b>int</b>).&nbsp;
  </p>
  <p class="MsoBodyText"><code>int *<font size="2"><b>pMeshVerts</b></font>;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The vertex offsets for a mesh</code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Shaders</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The shader structure basically gives you the file name,
  for a *.shader file.&nbsp; The .shader file then stores all of the information
  about blending, animating and such.&nbsp; The shader files can be found
  usually in the scripts\ folder, assuming that there are any textures in the
  level that use shaders of course.&nbsp; To calculate the number of shaders for
  this lump, just divide the <b>length</b> of the lump by sizeof(<b>tBSPShader</b>).
  </p>
  <p class="MsoBodyText"><font size="2" face="Courier New">struct <b> tBSPShader</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; char strName[64];&nbsp;&nbsp;&nbsp;&nbsp; // The name of
  the shader file&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int brushIndex;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The
  brush index for this shader&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int unknown;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // This is 99% of the time 5<br>
  };</font>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Light Volumes</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">Not everything in Quake3 is lit by lightmaps.&nbsp;
  There are other lights that have their own special properties.&nbsp; I believe
  you can get the rest of the light information from the entities lump.&nbsp; To
  calculate the number of lights in the lump, just divide the <b>length</b> of
  the lump by sizeof(<b>tBSPLights</b>).</p>
  <p class="MsoBodyText">
  <font size="2" face="Courier New">struct <b> tBSPLights</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; ubyte ambient[3];&nbsp;&nbsp;&nbsp;&nbsp; // This is the
  ambient color in RGB<br>
  &nbsp;&nbsp;&nbsp; ubyte directional[3];	// This is the directional color in
  RGB<br>
  &nbsp;&nbsp;&nbsp; ubyte direction[2];&nbsp;&nbsp; // The direction of the
  light: [phi,theta]&nbsp;<br>
  };</font>
  </p>
  <p class="MsoBodyText"><font face="Times New Roman" size="3">The light data </font><font face="Times New Roman" size="3">makes up a
  3-Dimensional grid with dimensions of:&nbsp;<br>
  </font><br>
  <font face="Courier New" size="2">x = floor(models[0].max[0] / 64)&nbsp; -
  ceil(models[0].min[0] / 64)&nbsp; + 1<br>
  y = floor(models[0].max[1] / 64)&nbsp; - ceil(models[0].min[1] / 64)&nbsp; + 1<br>
  z = floor(models[0].max[2] / 128) - ceil(models[0].min[2] / 128) + 1&nbsp;</font>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Conclusion</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">
  This is an on going project to add to this file, so if you have any pointers,
  corrections, or additions, let me know and I will post them.&nbsp; Once again,
  this was used as a tag along with the BSP tutorial series on <a href="http://www.GameTutorials.com">www.GameTutorials.com</a>.&nbsp;
  I would
  like to thanks these people for their HUGE help on creating this document and
  understanding the .bsp file format:
  </p>
  <p class="MsoBodyText">
  Kekoa Proudfoot - <font size="3">[e-mail] </font></O:P>
  </p>
  <p class="MsoBodyText">Bart Sekura - [e-mail]</p>
  <p class="MsoBodyText">Ignacio Castano - [e-mail]</p>
  <p class="MsoBodyText">Emmanuel Weber - [e-mail]</p>
  <p class="MsoBodyText"><br>
  Ben 揇igiBen