Fix - Large Brushmodel Flickering/Not Visible

[mh]

In case anybody missed it:

Original thread, discussion and sample code

There is a problem with many Quake engines where extra large brush models go into too many leafs during the process of the server determining which entities to send to the client. Quake sets a maximum of 16 leafs which an entity can be in, and if all 16 of those are filled by leafs outside of the PVS, then the entity won't be sent.

This is not necessarily restricted to brush models and could in theory also happen with MDLs, although in practice I have never seen one large enough to cause the problem. It could also happen if QBSP carves your map up such that there are more than 16 leafs butting together close enough in a tight area, but I'd expect that's quite unlikely.

The original thread linked above contains a discussion of the problem, various methods of fixing it, and sample code for one method of fixing it (derived from DirectQ; this will have to be adapted to your own engine, but it should be quite evident what needs to be changed).

The code given is by no means the only way or the best way, but it has been in production for over a year and has been proven to work with a specific incidence of the problem.

[revelator]

also fixed some trouble i had with the world volume carving code in earlier mhquake code so (Realm is based on one of those).

something tells me the limit was a bit conservative as these problems
surfaced even in standard id1 maps.

the world volume carving system actually relies on having all leaf data availiable but for some reason without this fix it didnt.

[revelator]

btw it also causes a massive speedup in loading times +

Code: Select all

void SV_WriteEntitiesToClient (edict_t   *clent, sizebuf_t *msg)
{
    int      e, i;
    int      bits;
    int      packet;
    byte   *pvs;
    vec3_t   org;
    float   miss;
    edict_t   *ent;
    float   lastmsg;

    // terminate lastmessage properly.
    memset (&lastmsg, 0, sizeof(float));

    // find the client's PVS
    VectorAdd (clent->v.origin, clent->v.view_ofs, org);

    pvs = SV_FatPVS (org, sv.worldmodel);

    // send over all entities (except the client) that touch the pvs
    ent = NEXT_EDICT(sv.edicts);

    for (e=1 ; e<sv.num_edicts ; e++, ent = NEXT_EDICT(ent))
    {
        // ignore if not touching a PV leaf
        if (ent != clent)   // clent is ALLWAYS sent
        {
            // ignore ents without visible models
            if (!ent->v.modelindex || !pr_strings[ent->v.model]) continue;

         // link to PVS leafs - deferred to here so that we can compare leafs that are touched to the PVS.
         // this is less optimal on one hand as it now needs to be done separately for each client, rather than once
         // only (covering all clients), but more optimal on the other as it only needs to hit one leaf and will
         // start dropping out of the recursion as soon as it does so.  on balance it should be more optimal overall.
         ent->touchleaf = false;

         SV_FindTouchedLeafs (ent, sv.worldmodel->nodes, pvs);

         // if the entity didn't touch any leafs in the pvs don't send it to the client
         if (!ent->touchleaf) continue;
        }

        // send an update
        bits = 0;

        for (i=0 ; i<3 ; i++)
        {
            miss = ent->v.origin[i] - ent->baseline.origin[i];

            if ( miss < -0.1 || miss > 0.1 )
            {
                bits |= U_ORIGIN1<<i;
            }
        }

        if ( ent->v.angles[0] != ent->baseline.angles[0] )
        {
            bits |= U_ANGLE1;
        }

        if ( ent->v.angles[1] != ent->baseline.angles[1] )
        {
            bits |= U_ANGLE2;
        }

        if ( ent->v.angles[2] != ent->baseline.angles[2] )
        {
            bits |= U_ANGLE3;
        }

        if (ent->v.movetype == MOVETYPE_STEP)
        {
            bits |= U_NOLERP;   // don't mess up the step animation
        }

        if (ent->baseline.colormap != ent->v.colormap)
        {
            bits |= U_COLORMAP;
        }

        if (ent->baseline.skin != ent->v.skin)
        {
            bits |= U_SKIN;
        }

        if (ent->baseline.frame != ent->v.frame)
        {
            bits |= U_FRAME;
        }

        if (ent->baseline.effects != ent->v.effects)
        {
            bits |= U_EFFECTS;
        }

        if (ent->baseline.modelindex != ent->v.modelindex)
        {
            bits |= U_MODEL;
        }

        if (e >= 256)
        {
            bits |= U_LONGENTITY;
        }

        if (bits >= 256)
        {
            bits |= U_MOREBITS;
        }

        // Original + missing for worst case
        packet = 16 + 2;

        if (sv.protocol != PROTOCOL_VERSION)
        {
            ++packet; // PROTOCOL_VERSION_EXT3
        }

        if (sv_max_datagram == MAX_DATAGRAM)
        {
            packet += 256; // Empirical margin to avoid Loop_SendMessage or other overflows
        }

        if (msg->maxsize - msg->cursize < packet)
        {
            if (COM_Timeout (&lastmsg, 2))
            {
                Con_Printf ("packet overflow\n");
            }
            return;
        }

        //
        // write the message
        //
        MSG_WriteByte (msg, bits | U_SIGNAL);

        if (bits & U_MOREBITS)
        {
            MSG_WriteByte (msg, bits>>8);
        }

        if (bits & U_LONGENTITY)
        {
            MSG_WriteShort (msg,e);
        }
        else
        {
            MSG_WriteByte (msg,e);
        }

        if (bits & U_MODEL)
        {
            MSG_WriteByteShort (msg, ent->v.modelindex);
        }

        if (bits & U_FRAME)
        {
            MSG_WriteByte (msg, ent->v.frame);
        }

        if (bits & U_COLORMAP)
        {
            MSG_WriteByte (msg, ent->v.colormap);
        }

        if (bits & U_SKIN)
        {
            MSG_WriteByte (msg, ent->v.skin);
        }

        if (bits & U_EFFECTS)
        {
            MSG_WriteByte (msg, ent->v.effects);
        }

        if (bits & U_ORIGIN1)
        {
            MSG_WriteCoord (msg, ent->v.origin[0]);
        }

        if (bits & U_ANGLE1)
        {
            MSG_WriteAngle(msg, ent->v.angles[0]);
        }

        if (bits & U_ORIGIN2)
        {
            MSG_WriteCoord (msg, ent->v.origin[1]);
        }

        if (bits & U_ANGLE2)
        {
            MSG_WriteAngle(msg, ent->v.angles[1]);
        }

        if (bits & U_ORIGIN3)
        {
            MSG_WriteCoord (msg, ent->v.origin[2]);
        }

        if (bits & U_ANGLE3)
        {
            MSG_WriteAngle(msg, ent->v.angles[2]);
        }
    }
}

progs.h

Code: Select all

typedef struct edict_s
{
    link_t         area;         // linked to a division node or leaf
   qboolean      touchleaf;      // true if the ent touches a leaf in the pvs

    entity_state_t   baseline;
    entvars_t       v;            // C exported fields from progs
// other fields from progs come immediately after
} edict_t;

world.c

Code: Select all

/*
===============
SV_FindTouchedLeafs
===============
*/
void SV_FindTouchedLeafs (edict_t *ent, mnode_t *node, byte *pvs)
{
   mplane_t   *splitplane;
   int         sides;
   int         leafnum;

loc0:;
   // ent already touches a leaf
   if (ent->touchleaf) return;

   // hit solid
   if (node->contents == CONTENTS_SOLID) return;

   // add an efrag if the node is a leaf
   // this is used for sending ents to the client so it needs to stay
   if (node->contents < 0)
   {
loc1:;
      leafnum = ((mleaf_t *) node) - sv.worldmodel->leafs - 1;

      if ((pvs[leafnum >> 3] & (1 << (leafnum & 7))))
      {
         ent->touchleaf = true;
      }
      return;
   }

   // NODE_MIXED
   splitplane = node->plane;
   sides = BOX_ON_PLANE_SIDE (ent->v.absmin, ent->v.absmax, splitplane);

   // recurse down the contacted sides, start dropping out if we hit anything
   if ((sides & 1) && !ent->touchleaf && node->children[0]->contents != CONTENTS_SOLID)
   {
      if (!(sides & 2) && node->children[0]->contents < 0)
      {
         node = node->children[0];
         goto loc1;
      }
      else if (!(sides & 2))
      {
         node = node->children[0];
         goto loc0;
      }
      else
      {
            SV_FindTouchedLeafs (ent, node->children[0], pvs);
      }
   }

   if ((sides & 2) && !ent->touchleaf && node->children[1]->contents != CONTENTS_SOLID)
   {
      // test for a leaf and drop out if so, otherwise it's a node so go round again
      node = node->children[1];

      if (node->contents < 0)
      {
         goto loc1;
      }
      else
      {
            goto loc0;   // SV_FindTouchedLeafs (ent, node, pvs);
      }
   }
}