quake3format.htm

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

       int numOfIndices;     // The number
  of&nbsp;level indices&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int lightmapID;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The
  texture index for the lightmap&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int lMapCorner[2];&nbsp;&nbsp;&nbsp; // The face's lightmap
  corner in the image&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int lMapSize[2];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The size
  of the lightmap section&nbsp;<br>
  &nbsp;&nbsp;&nbsp; float lMapPos[3];&nbsp;&nbsp;&nbsp;&nbsp; // The 3D origin of lightmap.&nbsp;<br>
  &nbsp;&nbsp;&nbsp; float lMapVecs[2][3]; // The 3D space for s and t unit vectors.&nbsp;<br>
  &nbsp;&nbsp;&nbsp; float vNormal[3];&nbsp;&nbsp;&nbsp;&nbsp; // The face
  normal.&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int size[2];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The bezier patch dimensions.&nbsp;<br>
  };<br>
  <br>
  <br>
  <font size="3" face="Times New Roman">If the face <b>type</b> is 1 (normal
  polygons), the vertexIndex and numOfVerts can be used to index into the vertex
  array to render triangle fans.<br>
  <br>
  If the face <b>type</b> is 2 (bezier path), the vertexIndex and numOfVerts act
  as a 2D grid of control points, where the grid dimensions are described by the
  size[2] array.&nbsp; You can render the bezier patches with just the vertices
  and not fill in the curve information, but it looks horrible and
  blocky.&nbsp;&nbsp;</font></code>
  </p>
  <p class="MsoBodyText"><code><font size="3" face="Times New Roman">The point
  of the curved surfaces are to be able to create a more defined surface,
  depending on the specs of the computer that is running that application.&nbsp;
  Some computers with horrible speed and video cards would make the smallest
  amount of polygons from the curve, where as the fast computers using Geforce
  cards could use the highest amount of polygons to form a perfect curve.<br>
  <br>
  If the face <b>type</b> is 3 (mesh vertices), the vertexIndex and numOfVerts
  also work the same as if the <b>type</b> is 1<br>
  <br>
  If the face <b>type</b> is 4, the vertexIndex is the position of the
  billboard.&nbsp; The billboards are used for light effects such as flares,
  etc...</font></code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Textures</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The texture structure stores the name of the texture,
  along with some surface information which are associated with the brush, brush
  sides and faces.&nbsp; To calculate the number of textures in the lump you
  divide it's&nbsp; <b>length</b> by the sizeof(<b>tBSPTexture</b>).
  </p>
  <p class="MsoBodyText">
  <code>
  <br>
  struct <b> tBSPTexture</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; char strName[64];&nbsp;&nbsp; // The name of the texture
  w/o the extension&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int flags;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The surface flags (unknown)&nbsp;<br>&nbsp;&nbsp;&nbsp; int 
                  textureType;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The type 
                  of texture (solid, water, slime, etc..)&nbsp;(type &amp; 1) =
                 1(solid)<br>
  };<br>
  <br>
  </code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Lightmaps</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">Unlike the textures, the lightmaps are stored in the .bsp
  file as 128x128 RGB images.&nbsp; Many faces share the same lightmap with
  their own section of it stored in the lightmap UV coordinates.&nbsp; Once you
  read in the lightmaps, you will want to create textures from them.&nbsp; To
  calculate the number of lightmaps&nbsp; in the lump you divide the <b> length</b> of
  the lump by the sizeof(<b>tBSPLightmap</b>).
  </p>
  <p class="MsoBodyText">
  <code>
  <br>
  struct <b>tBSPLightmap</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; byte imageBits[128][128][3];&nbsp;&nbsp; // The RGB data in
  a 128x128 image<br>
  };<br>
  <br>
  </code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="571">
    <tr bgColor="#2165ae">
      <td height="17" width="563"><b><font size="5">Nodes</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The node structure holds the nodes that make up the BSP
  tree.&nbsp; The BSP is not used for rendering so much in Quake3, but for
  collision detection.&nbsp; The node holds the splitter <b>plane</b> index, the
  <b>front</b> and <b>back</b> index, along with the bounding box for the
  node.&nbsp; If the <b>front</b> or <b>back</b> indices are negative, then it's
  an index into the leafs array.&nbsp; Since negative numbers can't constitute
  an array index, you need to use the ~ operator or -(index&nbsp; + 1) to find
  the correct index.&nbsp; This is because 0 is the starting index.&nbsp; To
  calculate the number of nodes in the lump you divide the <b> length</b> of the lump by
  the sizeof(<code><b>tNode</b></code>).
  </p>
  <p class="MsoBodyText">
  <code>
  <br>
  struct <b> tNode</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; int plane;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The index into
  the planes array&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int front;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The child index
  for the front node&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int back;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The child
  index for the back node&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int mins[3];&nbsp;&nbsp;&nbsp; // The bounding box min
  position.&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int maxs[3];&nbsp;&nbsp;&nbsp; // The bounding box max
  position.&nbsp;<br>
  };
  </code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Leafs</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The leafs, like the faces, are a very important part of
  the BSP information.&nbsp; They store the&nbsp; visibility cluster, the area
  portal, the leaf bounding box, the index into the faces, the number of leaf
  faces, the index into the brushes for collision, and finally,&nbsp; the number
  of leaf brushes.&nbsp; To calculate the number of leafs in the lump you divide
  the <b> length</b> of the lump by the sizeof(<code><b>tLeaf</b></code>).
  </p>
  <p class="MsoBodyText">
  <code>
  <br>
  struct <b> tLeaf</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; int cluster;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The visibility cluster&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int area;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The area portal&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int mins[3];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The bounding box min position&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int maxs[3];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The bounding box max position&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int leafface;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The first index into the face array&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int numOfLeafFaces;&nbsp;&nbsp;&nbsp; // The number of
  faces for this leaf&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int leafBrush;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The first index for into the brushes&nbsp;<br>
  &nbsp;&nbsp;&nbsp; int numOfLeafBrushes;&nbsp; // The number of brushes for
  this leaf&nbsp;<br>
  };
  </code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Leaf Faces</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The leaf faces are used to index into <b>tBSPFace</b>s
  array.&nbsp; You might at first think this is strange to have the <b>tBSPLeaf</b>
  structure have an index into the <b>pLeafFace</b>s array, which in turn is
  just an index into the <b>tBSPFace</b>s array.&nbsp; This is because it's set
  up to start with a starting point (<b>leafface</b>) and a count to go from
  there for each face (<b>numOfLeafFaces</b>).&nbsp; The faces array is not
  contiguous (in a row) according to each leaf.&nbsp; That is where the leaf
  faces array comes into play.&nbsp; It's kinda like the same concept of model
  loaders where they store the vertices and then have faces that store the
  indices into the vertex array for that face.&nbsp; To calculate the number of
  leaf faces 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 *pLeafFaces;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The index into the face array</code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Planes</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The plane structure stores the normal to the plane and
  it's distance to the origin.&nbsp; We use this as the splitter plane for the
  BSP tree.&nbsp; When rendering or testing collision, we can test the camera
  position against the planes to see which plane we are in front of.&nbsp; To
  calculate the number of planes in the lump you divide the <b> length</b> of the lump
  by the sizeof(<code><b>tPlane</b></code>).
  <code>
  <br>
  <br>
  struct <b> tPlane</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; float vNormal[3];&nbsp;&nbsp;&nbsp;&nbsp; //  Plane normal.&nbsp;<br>
  &nbsp;&nbsp;&nbsp; float d;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // The plane distance from origin&nbsp;<br>
  };<br>
  <br>
  </code>
  </p>
  <p class="MsoBodyText">
  </p>
  <table width="570">
    <tr bgColor="#2165ae">
      <td height="17" width="562"><b><font size="5">Visibility Data</font></b></td>
    </tr>
  </table>
  <p class="MsoBodyText">The visibility information is comprised of a bunch of
  bitsets that store a bit for every cluster.&nbsp; This is because the
  information is so massive that this way makes it faster to access and a
  smaller memory footprint.&nbsp; There is only one instance of this structure,
  but you calculate how much needs to be read in bytes by either: numOfVectors *
  vectorSize, or minute the size of 2 integers from this lumps length.&nbsp; The
  pVecs is then dynamically allocated and stores the calculate bytes.&nbsp; This
  is probably one of the most confusing parts about the .bsp file format, the
  visibilty.&nbsp; I will try and explain the important parts of it and give
  some code.
  </p>
  <p class="MsoBodyText">
  <code>
  <br>
  struct <b> tVisData</b><br>
  {<br>
  &nbsp;&nbsp;&nbsp; int numOfVectors;&nbsp;&nbsp;&nbsp;&nbsp; // This stores
  the number of bit-vectors<br>
  &nbsp;&nbsp;&nbsp; int vectorSize;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // The
  size of bit-vectors in bytes<br>
  &nbsp;&nbsp;&nbsp; byte *pVecs;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  // This holds all of the cluster bits<br>
  };
  </code>
  </p>
  <p class="MsoBodyText">
  To demonstrate what a cluster is and what we need to do with it, let's start
  with a simple example.&nbsp; When rendering, first we want to find which leaf
  we are in.&nbsp; Once again, a leaf is an end node of the BSP tree that holds
  a bunch of information about the faces, brushes and the cluster it's in.&nbsp;
  Once that leaf is founding by checking the camera position against all of the
  planes, we then want to go through all of the leafs and check if their cluster
  is visible from the current cluster we are in.&nbsp; If it is, that means that
  we need to check if that leaf's bounding box is inside of our frustum before
  we draw it.&nbsp;&nbsp;
  </p>
  <p class="MsoBodyText">
  Say we have cluster A, B and C.&nbsp; Each cluster is stored as a bit in
  bitset.&nbsp; A bitset is just a huge list of binary numbers next to each
  other.&nbsp; Each cluster has their own list of bits that store a 1 or a 0 to
  tell if the cluster in that bit is visible (1) or not visible (0).&nbsp; Since
  there is most likely more than 32 clusters in a level, you can't just use an
  integer (32-bits) to store the bits for all the clusters.&nbsp; This is why
  there are many <b>bytes</b> assigned to each cluster.&nbsp; So, here is how it