cmodel.pas

delphi编的不错的贪吃蛇

var
  leaf_count, leaf_maxcount: Integer;
  leaf_list: PIntegerArray;
  leaf_mins, leaf_maxs: vec3_p;
  leaf_topnode: Integer;

procedure CM_BoxLeafnums_r(nodenum: Integer);
var
  plane: cplane_p;
  node: cnode_p;
  s: Integer;
begin
  while True do
  begin
    if (nodenum < 0) then
    begin
      if (leaf_count >= leaf_maxcount) then
      begin
        //	Com_Printf ('CM_BoxLeafnums_r: overflow'#10);
        Exit;
      end;
      leaf_list[leaf_count] := -1 - nodenum;
      Inc(leaf_count);
      Exit;
    end;

    node := @map_nodes[nodenum];
    plane := node.plane;
    //	s = BoxOnPlaneSide (leaf_mins, leaf_maxs, plane);
    s := BOX_ON_PLANE_SIDE(leaf_mins^, leaf_maxs^, plane);
    if (s = 1) then
      nodenum := node.children[0]
    else if (s = 2) then
      nodenum := node.children[1]
    else
    begin                               // go down both
      if (leaf_topnode = -1) then
        leaf_topnode := nodenum;
      CM_BoxLeafnums_r(node.children[0]);
      nodenum := node.children[1];
    end;
  end;
end;

function CM_BoxLeafnums_headnode(var mins, maxs: vec3_t;
  list: PIntegerArray; listsize, headnode: Integer; topnode: PInteger): Integer;
begin
  leaf_list := list;
  leaf_count := 0;
  leaf_maxcount := listsize;
  leaf_mins := @mins;
  leaf_maxs := @maxs;

  leaf_topnode := -1;

  CM_BoxLeafnums_r(headnode);

  if (topnode <> nil) then
    topnode^ := leaf_topnode;

  Result := leaf_count;
end;

function CM_BoxLeafnums(var mins, maxs: vec3_t; list: PInteger;
  listsize: Integer; topnode: PInteger): Integer;
begin
  Result := CM_BoxLeafnums_headnode(mins, maxs, PIntegerArray(list), listsize,
    map_cmodels[0].headnode, topnode);
end;

(*
==================
CM_PointContents

==================
*)

function CM_PointContents(const p: vec3_t; headnode: Integer): Integer;
var
  l: Integer;
begin
  if (numnodes = 0) then                // map not loaded
  begin
    Result := 0;
    Exit;
  end;

  l := CM_PointLeafnum_r(p, headnode);

  Result := map_leafs[l].contents;
end;

(*
==================
CM_TransformedPointContents

Handles offseting and rotation of the end points for moving and
rotating entities
==================
*)

function CM_TransformedPointContents(const p: vec3_t; headnode: Integer;
  const origin, angles: vec3_t): Integer;
var
  p_l: vec3_t;
  temp: vec3_t;
  forward_, right, up: vec3_t;
  l: Integer;
begin
  // subtract origin offset
  VectorSubtract(p, origin, p_l);

  // rotate start and end into the models frame of reference
  if (headnode <> box_headnode) and
    ((angles[0] <> 0) or (angles[1] <> 0) or (angles[2] <> 0)) then
  begin
    AngleVectors(angles, @forward_, @right, @up);

    VectorCopy(p_l, temp);
    p_l[0] := DotProduct(temp, forward_);
    p_l[1] := -DotProduct(temp, right);
    p_l[2] := DotProduct(temp, up);
  end;

  l := CM_PointLeafnum_r(p_l, headnode);

  Result := map_leafs[l].contents;
end;

(*
===============================================================================

BOX TRACING

===============================================================================
*)

// 1/32 epsilon to keep floating point happy
const
  DIST_EPSILON: Single = (0.03125);

var
  trace_start, trace_end: vec3_t;
  trace_mins, trace_maxs: vec3_t;
  trace_extents: vec3_t;

  trace_trace: trace_t;
  trace_contents: Integer;
  trace_ispoint: qboolean;              // optimized case

  (*
  ================
  CM_ClipBoxToBrush
  ================
  *)

procedure CM_ClipBoxToBrush(const mins, maxs, p1, p2: vec3_t;
  trace: trace_p; brush: cbrush_p);
var
  i, j: Integer;
  plane, clipplane: cplane_p;
  dist: Single;
  enterfrac, leavefrac: Single;
  ofs: vec3_t;
  d1, d2: Single;
  getout, startout: qboolean;
  f: Single;
  side, leadside: cbrushside_p;
begin
  enterfrac := -1;
  leavefrac := 1;
  clipplane := nil;

  if (brush^.numsides = 0) then
    Exit;

  Inc(c_brush_traces);

  getout := False;
  startout := False;
  leadside := nil;

  for i := 0 to brush^.numsides - 1 do
  begin
    side := @map_brushsides[brush^.firstbrushside + i];
    plane := side^.plane;

    // FIXME: special case for axial

    if not trace_ispoint then
    begin                               // general box case
      // push the plane out apropriately for mins/maxs

      // FIXME: use signbits into 8 way lookup for each mins/maxs
      for j := 0 to 2 do
      begin
        if (plane^.normal[j] < 0) then
          ofs[j] := maxs[j]
        else
          ofs[j] := mins[j];
      end;
      dist := DotProduct(ofs, plane^.normal);
      dist := plane^.dist - dist;
    end
    else
    begin                               // special point case
      dist := plane^.dist;
    end;

    d1 := DotProduct(p1, plane^.normal) - dist;
    d2 := DotProduct(p2, plane^.normal) - dist;

    if (d2 > 0) then
      getout := True;                   // endpoint is not in solid
    if (d1 > 0) then
      startout := True;

    // if completely in front of face, no intersection
    if (d1 > 0) and (d2 >= d1) then
      Exit;

    if (d1 <= 0) and (d2 <= 0) then
      Continue;

    // crosses face
    if (d1 > d2) then
    begin                               // enter
      f := (d1 - DIST_EPSILON) / (d1 - d2);
      if (f > enterfrac) then
      begin
        enterfrac := f;
        clipplane := plane;
        leadside := side;
      end;
    end
    else
    begin                               // leave
      f := (d1 + DIST_EPSILON) / (d1 - d2);
      if (f < leavefrac) then
        leavefrac := f;
    end;
  end;

  if not startout then
  begin                                 // original point was inside brush
    trace^.startsolid := true;
    if not getout then
      trace^.allsolid := True;
    Exit;
  end;
  if (enterfrac < leavefrac) then
  begin
    if (enterfrac > -1) and (enterfrac < trace^.fraction) then
    begin
      if (enterfrac < 0) then
        enterfrac := 0;
      trace^.fraction := enterfrac;
      trace^.plane := clipplane^;
      trace^.surface := @leadside^.surface^.c;
      trace^.contents := brush^.contents;
    end;
  end;
end;

(*
================
CM_TestBoxInBrush
================
*)

procedure CM_TestBoxInBrush(const mins, maxs, p1: vec3_t;
  trace: trace_p; brush: cbrush_p);
var
  i, j: Integer;
  plane: cplane_p;
  dist: Single;
  ofs: vec3_t;
  d1: Single;
  side: cbrushside_p;
begin
  if (brush.numsides = 0) then
    Exit;

  for i := 0 to brush.numsides - 1 do
  begin
    side := @map_brushsides[brush^.firstbrushside + i];
    plane := side^.plane;

    // FIXME: special case for axial

    // general box case

    // push the plane out apropriately for mins/maxs

    // FIXME: use signbits into 8 way lookup for each mins/maxs
    for j := 0 to 2 do
    begin
      if (plane^.normal[j] < 0) then
        ofs[j] := maxs[j]
      else
        ofs[j] := mins[j];
    end;
    dist := DotProduct(ofs, plane^.normal);
    dist := plane^.dist - dist;

    d1 := DotProduct(p1, plane^.normal) - dist;

    // if completely in front of face, no intersection
    if (d1 > 0) then
      Exit;
  end;

  // inside this brush
  trace^.allsolid := True;
  trace^.startsolid := True;
  trace^.fraction := 0;
  trace^.contents := brush^.contents;
end;

(*
================
CM_TraceToLeaf
================
*)

procedure CM_TraceToLeaf(leafnum: Integer);
var
  k: Integer;
  brushnum: Integer;
  leaf: cleaf_p;
  b: cbrush_p;
begin
  leaf := @map_leafs[leafnum];
  if ((leaf.contents and trace_contents) = 0) then
    Exit;

  // trace line against all brushes in the leaf
  for k := 0 to leaf.numleafbrushes - 1 do
  begin
    brushnum := map_leafbrushes[leaf^.firstleafbrush + k];
    b := @map_brushes[brushnum];
    if (b^.checkcount = checkcount) then
      Continue;                         // already checked this brush in another leaf
    b^.checkcount := checkcount;

    if ((b^.contents and trace_contents) = 0) then
      Continue;
    CM_ClipBoxToBrush(trace_mins, trace_maxs, trace_start, trace_end, @trace_trace, b);
    if (trace_trace.fraction = 0) then
      Exit;
  end;

end;

(*
================
CM_TestInLeaf
================
*)

procedure CM_TestInLeaf(leafnum: Integer);
var
  k: Integer;
  brushnum: Integer;
  leaf: cleaf_p;
  b: cbrush_p;
begin
  leaf := @map_leafs[leafnum];
  if ((leaf^.contents and trace_contents) = 0) then
    Exit;

  // trace line against all brushes in the leaf
  for k := 0 to leaf^.numleafbrushes - 1 do
  begin
    brushnum := map_leafbrushes[leaf^.firstleafbrush + k];
    b := @map_brushes[brushnum];
    if (b^.checkcount = checkcount) then
      Continue;                         // already checked this brush in another leaf
    b^.checkcount := checkcount;

    if ((b^.contents and trace_contents) = 0) then
      Continue;
    CM_TestBoxInBrush(trace_mins, trace_maxs, trace_start, @trace_trace, b);
    if (trace_trace.fraction = 0) then
      Exit;
  end;

end;

(*
==================
CM_RecursiveHullCheck

==================
*)

procedure CM_RecursiveHullCheck(num: Integer; p1f, p2f: Single; const p1, p2: vec3_t);
var
  node: cnode_p;
  plane: cplane_p;
  t1, t2, offset: Single;
  frac, frac2: Single;
  idist: Single;
  i: Integer;
  mid: vec3_t;
  side: Integer;
  midf: Single;
begin
  if (trace_trace.fraction <= p1f) then
    Exit;                               // already hit something nearer

  // if < 0, we are in a leaf node
  if (num < 0) then
  begin
    CM_TraceToLeaf(-1 - num);
    Exit;
  end;

  //
  // find the point distances to the seperating plane
  // and the offset for the size of the box
  //
  node := @map_nodes[num];
  plane := node^.plane;

  if (plane^._type < 3) then
  begin
    t1 := p1[plane^._type] - plane^.dist;
    t2 := p2[plane^._type] - plane^.dist;
    offset := trace_extents[plane^._type];
  end
  else
  begin
    t1 := DotProduct(plane^.normal, p1) - plane^.dist;
    t2 := DotProduct(plane^.normal, p2) - plane^.dist;
    if (trace_ispoint) then
      offset := 0
    else
      offset := fabs(trace_extents[0] * plane^.normal[0]) +
        fabs(trace_extents[1] * plane^.normal[1]) +
        fabs(trace_extents[2] * plane^.normal[2]);
  end;

  {
  CM_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
  CM_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
  return;
  }
    // see which sides we need to consider
  if (t1 >= offset) and (t2 >= offset) then
  begin
    CM_RecursiveHullCheck(node^.children[0], p1f, p2f, p1, p2);
    Exit;
  end;
  if (t1 < -offset) and (t2 < -offset) then
  begin
    CM_RecursiveHullCheck(node^.children[1], p1f, p2f, p1, p2);
    Exit;
  end;

  // put the crosspoint DIST_EPSILON pixels on the near side
  if (t1 < t2) then
  begin
    idist := 1.0 / (t1 - t2);
    side := 1;
    frac2 := (t1 + offset + DIST_EPSILON) * idist;
    frac := (t1 - offset + DIST_EPSILON) * idist;
  end
  else if (t1 > t2) then
  begin
    idist := 1.0 / (t1 - t2);
    side := 0;
    frac2 := (t1 - offset - DIST_EPSILON) * idist;
    frac := (t1 + offset + DIST_EPSILON) * idist;
  end
  else
  begin
    side := 0;
    frac := 1;
    frac2 := 0;
  end;

  // move up to the node
  if (frac < 0) then