portals.c

   1
   2 #include "quakedef.h"
   3
   4 #define MAXRECURSIVEPORTALPLANES 1024
   5 #define MAXRECURSIVEPORTALS 256
   6
   7 tinyplane_t portalplanes[MAXRECURSIVEPORTALPLANES];
   8 int portalplanestack[MAXRECURSIVEPORTALS];
   9 int portalplanecount;
  10 int ranoutofportalplanes;
  11 int ranoutofportals;
  12
  13 int R_ClipPolygonToPlane(float *in, float *out, int inpoints, int maxoutpoints, tinyplane_t *p)
  14 {
  15         int i, outpoints, prevside, side;
  16         float *prevpoint, prevdist, dist, dot;
  17
  18         if (inpoints < 3)
  19                 return inpoints;
  20         // begin with the last point, then enter the loop with the first point as current
  21         prevpoint = in + 3 * (inpoints - 1);
  22         prevdist = DotProduct(prevpoint, p->normal) - p->dist;
  23         prevside = prevdist >= 0 ? SIDE_FRONT : SIDE_BACK;
  24         i = 0;
  25         outpoints = 0;
  26         goto begin;
  27         for (;i < inpoints;i++)
  28         {
  29                 prevpoint = in;
  30                 prevdist = dist;
  31                 prevside = side;
  32                 in += 3;
  33
  34 begin:
  35                 dist = DotProduct(in, p->normal) - p->dist;
  36                 side = dist >= 0 ? SIDE_FRONT : SIDE_BACK;
  37
  38                 if (prevside == SIDE_FRONT)
  39                 {
  40                         if (outpoints >= maxoutpoints)
  41                                 return -1;
  42                         VectorCopy(prevpoint, out);
  43                         out += 3;
  44                         outpoints++;
  45                         if (side == SIDE_FRONT)
  46                                 continue;
  47                 }
  48                 else if (side == SIDE_BACK)
  49                         continue;
  50
  51                 // generate a split point
  52                 if (outpoints >= maxoutpoints)
  53                         return -1;
  54                 dot = prevdist / (prevdist - dist);
  55                 out[0] = prevpoint[0] + dot * (in[0] - prevpoint[0]);
  56                 out[1] = prevpoint[1] + dot * (in[1] - prevpoint[1]);
  57                 out[2] = prevpoint[2] + dot * (in[2] - prevpoint[2]);
  58                 out += 3;
  59                 outpoints++;
  60         }
  61
  62         return outpoints;
  63 }
  64
  65 float portaltemppoints[2][256][3];
  66 float portaltemppoints2[256][3];
  67
  68 /*
  69 void R_TriangleToPlane(vec3_t point1, vec3_t point2, vec3_t point3, tinyplane_t *p)
  70 {
  71         vec3_t v1, v2;
  72         VectorSubtract(point1, point2, v1);
  73         VectorSubtract(point3, point2, v2);
  74         CrossProduct(v1, v2, p->normal);
  75 //      VectorNormalize(p->normal);
  76         VectorNormalizeFast(p->normal);
  77         p->dist = DotProduct(point1, p->normal);
  78 }
  79 */
  80
  81 int R_PortalThroughPortalPlanes(tinyplane_t *clipplanes, int clipnumplanes, float *targpoints, int targnumpoints, float *out, int maxpoints)
  82 {
  83         int numpoints, i;
  84         if (targnumpoints < 3)
  85                 return targnumpoints;
  86         if (maxpoints < 3)
  87                 return -1;
  88         numpoints = targnumpoints;
  89         memcpy(&portaltemppoints[0][0][0], targpoints, numpoints * 3 * sizeof(float));
  90         for (i = 0;i < clipnumplanes;i++)
  91         {
  92                 numpoints = R_ClipPolygonToPlane(&portaltemppoints[0][0][0], &portaltemppoints[1][0][0], numpoints, 256, clipplanes + i);
  93                 if (numpoints < 3)
  94                         return numpoints;
  95                 memcpy(&portaltemppoints[0][0][0], &portaltemppoints[1][0][0], numpoints * 3 * sizeof(float));
  96         }
  97         if (numpoints > maxpoints)
  98                 return -1;
  99         memcpy(out, &portaltemppoints[1][0][0], numpoints * 3 * sizeof(float));
 100         return numpoints;
 101 }
 102
 103 static int portal_markid = 0;
 104
 105 int Portal_RecursiveFlowSearch (mleaf_t *leaf, vec3_t eye, int firstclipplane, int numclipplanes)
 106 {
 107         mportal_t *p;
 108
 109         if (leaf->portalmarkid == portal_markid)
 110                 return true;
 111
 112         // follow portals into other leafs
 113         for (p = leaf->portals;p;p = p->next)
 114         {
 115                 int newpoints, i, prev;
 116                 vec3_t center;
 117                 vec3_t v1, v2;
 118                 tinyplane_t *newplanes;
 119                 // only flow through portals facing away from the viewer
 120                 if (PlaneDiff(eye, (&p->plane)) < 0)
 121                 {
 122                         newpoints = R_PortalThroughPortalPlanes(&portalplanes[firstclipplane], numclipplanes, (float *) p->points, p->numpoints, &portaltemppoints2[0][0], 256);
 123                         if (newpoints < 3)
 124                                 continue;
 125                         else if (firstclipplane + numclipplanes + newpoints > MAXRECURSIVEPORTALPLANES)
 126                                 ranoutofportalplanes = true;
 127                         else
 128                         {
 129                                 // find the center by averaging
 130                                 VectorClear(center);
 131                                 for (i = 0;i < newpoints;i++)
 132                                         VectorAdd(center, portaltemppoints2[i], center);
 133                                 // ixtable is a 1.0f / N table
 134                                 VectorScale(center, ixtable[newpoints], center);
 135                                 // calculate the planes, and make sure the polygon can see it's own center
 136                                 newplanes = &portalplanes[firstclipplane + numclipplanes];
 137                                 for (prev = newpoints - 1, i = 0;i < newpoints;prev = i, i++)
 138                                 {
 139 //                                      R_TriangleToPlane(eye, portaltemppoints2[i], portaltemppoints2[prev], newplanes + i);
 140                                         VectorSubtract(eye, portaltemppoints2[i], v1);
 141                                         VectorSubtract(portaltemppoints2[prev], portaltemppoints2[i], v2);
 142                                         CrossProduct(v1, v2, newplanes[i].normal);
 143                                         VectorNormalizeFast(newplanes[i].normal);
 144                                         newplanes[i].dist = DotProduct(eye, newplanes[i].normal);
 145                                         if (DotProduct(newplanes[i].normal, center) <= newplanes[i].dist)
 146                                         {
 147                                                 // polygon can't see it's own center, discard and use parent portal
 148                                                 break;
 149                                         }
 150                                 }
 151                                 if (i == newpoints)
 152                                 {
 153                                         if (Portal_RecursiveFlowSearch(p->past, eye, firstclipplane + numclipplanes, newpoints))
 154                                                 return true;
 155                         }
 156                                 else
 157                                 {
 158                                         if (Portal_RecursiveFlowSearch(p->past, eye, firstclipplane, numclipplanes))
 159                                                 return true;
 160                         }
 161                         }
 162                 }
 163         }
 164
 165         return false;
 166 }
 167
 168 //float viewportalpoints[16*3];
 169
 170 void Portal_PolygonRecursiveMarkLeafs(mnode_t *node, float *polypoints, int numpoints)
 171 {
 172         int i, front;
 173         float *p;
 174
 175 loc0:
 176         if (node->contents < 0)
 177         {
 178                 ((mleaf_t *)node)->portalmarkid = portal_markid;
 179                 return;
 180         }
 181
 182         front = 0;
 183         for (i = 0, p = polypoints;i < numpoints;i++, p += 3)
 184         {
 185                 if (DotProduct(p, node->plane->normal) > node->plane->dist)
 186                         front++;
 187         }
 188         if (front > 0)
 189         {
 190                 if (front == numpoints)
 191                 {
 192                         node = node->children[0];
 193                         goto loc0;
 194                 }
 195                 else
 196                         Portal_PolygonRecursiveMarkLeafs(node->children[0], polypoints, numpoints);
 197         }
 198         node = node->children[1];
 199         goto loc0;
 200 }
 201
 202 int Portal_CheckPolygon(model_t *model, vec3_t eye, float *polypoints, int numpoints)
 203 {
 204         int i, prev, returnvalue;
 205         mleaf_t *eyeleaf;
 206         vec3_t center, v1, v2;
 207
 208         portal_markid++;
 209
 210         Portal_PolygonRecursiveMarkLeafs(model->nodes, polypoints, numpoints);
 211
 212         eyeleaf = Mod_PointInLeaf(eye, model);
 213
 214         // find the center by averaging
 215         VectorClear(center);
 216         for (i = 0;i < numpoints;i++)
 217                 VectorAdd(center, (&polypoints[i * 3]), center);
 218         // ixtable is a 1.0f / N table
 219         VectorScale(center, ixtable[numpoints], center);
 220
 221         // calculate the planes, and make sure the polygon can see it's own center
 222         for (prev = numpoints - 1, i = 0;i < numpoints;prev = i, i++)
 223         {
 224 //              R_TriangleToPlane(eye, portaltemppoints2[i], portaltemppoints2[prev], newplanes + i);
 225                 VectorSubtract(eye, (&polypoints[i * 3]), v1);
 226                 VectorSubtract((&polypoints[prev * 3]), (&polypoints[i * 3]), v2);
 227                 CrossProduct(v1, v2, portalplanes[i].normal);
 228                 VectorNormalizeFast(portalplanes[i].normal);
 229                 portalplanes[i].dist = DotProduct(eye, portalplanes[i].normal);
 230                 if (DotProduct(portalplanes[i].normal, center) <= portalplanes[i].dist)
 231                 {
 232                         // polygon can't see it's own center, discard
 233                         return false;
 234                 }
 235         }
 236
 237         portalplanecount = 0;
 238         ranoutofportalplanes = false;
 239         ranoutofportals = false;
 240
 241         returnvalue = Portal_RecursiveFlowSearch(eyeleaf, eye, 0, numpoints);
 242
 243         if (ranoutofportalplanes)
 244                 Con_Printf("Portal_RecursiveFlowSearch: ran out of %d plane stack when recursing through portals\n", MAXRECURSIVEPORTALPLANES);
 245         if (ranoutofportals)
 246                 Con_Printf("Portal_RecursiveFlowSearch: ran out of %d portal stack when recursing through portals\n", MAXRECURSIVEPORTALS);
 247
 248         return returnvalue;
 249 }
 250
 251 float boxpoints[4*3];
 252
 253 #define Portal_MinsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4) \
 254 {\
 255         if (eye[(axis)] < ((axisvalue) - 0.5f))\
 256         {\
 257                 boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
 258                 boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
 259                 boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
 260                 boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
 261                 if (Portal_CheckPolygon(model, eye, boxpoints, 4))\
 262                         return true;\
 263         }\
 264 }
 265
 266 #define Portal_MaxsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4) \
 267 {\
 268         if (eye[(axis)] > ((axisvalue) + 0.5f))\
 269         {\
 270                 boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
 271                 boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
 272                 boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
 273                 boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
 274                 if (Portal_CheckPolygon(model, eye, boxpoints, 4))\
 275                         return true;\
 276         }\
 277 }
 278
 279 int Portal_CheckBox(model_t *model, vec3_t eye, vec3_t a, vec3_t b)
 280 {
 281         if (eye[0] >= (a[0] - 1.0f) && eye[0] < (b[0] + 1.0f)
 282          && eye[1] >= (a[1] - 1.0f) && eye[1] < (b[1] + 1.0f)
 283          && eye[2] >= (a[2] - 1.0f) && eye[2] < (b[2] + 1.0f))
 284         {
 285                 return true;
 286         }
 287
 288         Portal_MinsBoxPolygon
 289         (
 290                 0, a[0],
 291                 a[0], a[1], a[2],
 292                 a[0], b[1], a[2],
 293                 a[0], b[1], b[2],
 294                 a[0], a[1], b[2]
 295         );
 296         Portal_MaxsBoxPolygon
 297         (
 298                 0, b[0],
 299                 b[0], b[1], a[2],
 300                 b[0], a[1], a[2],
 301                 b[0], a[1], b[2],
 302                 b[0], b[1], b[2]
 303         );
 304         Portal_MinsBoxPolygon
 305         (
 306                 1, a[1],
 307                 b[0], a[1], a[2],
 308                 a[0], a[1], a[2],
 309                 a[0], a[1], b[2],
 310                 b[0], a[1], b[2]
 311         );
 312         Portal_MaxsBoxPolygon
 313         (
 314                 1, b[1],
 315                 a[0], b[1], a[2],
 316                 b[0], b[1], a[2],
 317                 b[0], b[1], b[2],
 318                 a[0], b[1], b[2]
 319         );
 320         Portal_MinsBoxPolygon
 321         (
 322                 2, a[2],
 323                 a[0], a[1], a[2],
 324                 b[0], a[1], a[2],
 325                 b[0], b[1], a[2],
 326                 a[0], b[1], a[2]
 327         );
 328         Portal_MaxsBoxPolygon
 329         (
 330                 2, b[2],
 331                 b[0], a[1], b[2],
 332                 a[0], a[1], b[2],
 333                 a[0], b[1], b[2],
 334                 b[0], b[1], b[2]
 335         );
 336
 337         return false;
 338 }