contrib/gtkgensurf/face.cpp

   1 /*\r
   2 GenSurf plugin for GtkRadiant\r
   3 Copyright (C) 2001 David Hyde, Loki software and qeradiant.com\r
   4 \r
   5 This library is free software; you can redistribute it and/or\r
   6 modify it under the terms of the GNU Lesser General Public\r
   7 License as published by the Free Software Foundation; either\r
   8 version 2.1 of the License, or (at your option) any later version.\r
   9 \r
  10 This library is distributed in the hope that it will be useful,\r
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
  13 Lesser General Public License for more details.\r
  14 \r
  15 You should have received a copy of the GNU Lesser General Public\r
  16 License along with this library; if not, write to the Free Software\r
  17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  18 */\r
  19 \r
  20 #include <stdlib.h>\r
  21 #include <math.h>\r
  22 #include "gensurf.h"\r
  23 \r
  24 #define MAX_FACES 128    // Maximum number of faces on a brush\r
  25 #define MAX_POINTS_ON_WINDING   64\r
  26 #define SIDE_FRONT              0\r
  27 #define SIDE_ON                 2\r
  28 #define SIDE_BACK               1\r
  29 #define SIDE_CROSS              -2\r
  30 \r
  31 vec3 vec3_origin = {0,0,0};\r
  32 \r
  33 void PlaneFromPoints (float *p0, float *p1, float *p2, PLANE *plane)\r
  34 {\r
  35         vec3 t1, t2;\r
  36         vec     length;\r
  37         \r
  38         VectorSubtract (p0, p1, t1);\r
  39         VectorSubtract (p2, p1, t2);\r
  40         plane->normal[0] = t1[1]*t2[2] - t1[2]*t2[1];\r
  41         plane->normal[1] = t1[2]*t2[0] - t1[0]*t2[2];\r
  42         plane->normal[2] = t1[0]*t2[1] - t1[1]*t2[0];\r
  43         \r
  44         length = (vec)(sqrt(plane->normal[0]*plane->normal[0] +\r
  45                                 plane->normal[1]*plane->normal[1] +\r
  46                                                 plane->normal[2]*plane->normal[2]  ));\r
  47         if (length == 0)\r
  48         {\r
  49                 VectorClear(plane->normal);\r
  50         }\r
  51         else\r
  52         {\r
  53                 plane->normal[0] /= length;\r
  54                 plane->normal[1] /= length;\r
  55                 plane->normal[2] /= length;\r
  56         }\r
  57         plane->dist = DotProduct (p0, plane->normal);\r
  58 }\r
  59 \r
  60 void VectorMA (vec3 va, vec scale, vec3 vb, vec3 vc)\r
  61 {\r
  62         vc[0] = va[0] + scale*vb[0];\r
  63         vc[1] = va[1] + scale*vb[1];\r
  64         vc[2] = va[2] + scale*vb[2];\r
  65 }\r
  66 \r
  67 void CrossProduct (vec3 v1, vec3 v2, vec3 cross)\r
  68 {\r
  69         cross[0] = v1[1]*v2[2] - v1[2]*v2[1];\r
  70         cross[1] = v1[2]*v2[0] - v1[0]*v2[2];\r
  71         cross[2] = v1[0]*v2[1] - v1[1]*v2[0];\r
  72 }\r
  73 \r
  74 /*\r
  75 =============\r
  76 AllocWinding\r
  77 =============\r
  78 */\r
  79 MY_WINDING      *AllocWinding (int points)\r
  80 {\r
  81         MY_WINDING      *w;\r
  82         int                     s;\r
  83 \r
  84         s = sizeof(vec)*3*points + sizeof(int);\r
  85         w = (MY_WINDING*)malloc (s);\r
  86         memset (w, 0, s); \r
  87         return w;\r
  88 }\r
  89 \r
  90 vec VectorNormalize (vec3 in, vec3 out)\r
  91 {\r
  92         vec     length, ilength;\r
  93 \r
  94         length = (vec)(sqrt (in[0]*in[0] + in[1]*in[1] + in[2]*in[2]));\r
  95         if (length == 0)\r
  96         {\r
  97                 VectorClear (out);\r
  98                 return 0;\r
  99         }\r
 100 \r
 101         ilength = (vec)1.0/length;\r
 102         out[0] = in[0]*ilength;\r
 103         out[1] = in[1]*ilength;\r
 104         out[2] = in[2]*ilength;\r
 105 \r
 106         return length;\r
 107 }\r
 108 \r
 109 /*\r
 110 =================\r
 111 BaseWindingForPlane\r
 112 =================\r
 113 */\r
 114 MY_WINDING *BaseWindingForPlane (vec3 normal, vec dist)\r
 115 {\r
 116         int                i, x;\r
 117         vec        max, v;\r
 118         vec3       org, vright, vup;\r
 119         MY_WINDING *w;\r
 120 \r
 121 // find the major axis\r
 122 \r
 123         max = -BOGUS_RANGE;\r
 124         x = -1;\r
 125         for (i=0 ; i<3; i++)\r
 126         {\r
 127                 v = (vec)(fabs(normal[i]));\r
 128                 if (v > max)\r
 129                 {\r
 130                         x = i;\r
 131                         max = v;\r
 132                 }\r
 133         }\r
 134         if (x==-1) x = 2;\r
 135                 \r
 136         VectorCopy(vec3_origin,vup);\r
 137         switch (x)\r
 138         {\r
 139         case 0:\r
 140         case 1:\r
 141                 vup[2] = 1;\r
 142                 break;          \r
 143         case 2:\r
 144                 vup[0] = 1;\r
 145                 break;          \r
 146         }\r
 147 \r
 148         v = DotProduct (vup, normal);\r
 149         VectorMA (vup, -v, normal, vup);\r
 150         VectorNormalize (vup, vup);\r
 151                 \r
 152         VectorScale (normal, dist, org);\r
 153         \r
 154         CrossProduct (vup, normal, vright);\r
 155         \r
 156         VectorScale (vup, 65536, vup);\r
 157         VectorScale (vright, 65536, vright);\r
 158 \r
 159 // project a really big axis aligned box onto the plane\r
 160         w = AllocWinding (4);\r
 161         \r
 162         VectorSubtract (org, vright, w->p[0]);\r
 163         VectorAdd (w->p[0], vup, w->p[0]);\r
 164         \r
 165         VectorAdd (org, vright, w->p[1]);\r
 166         VectorAdd (w->p[1], vup, w->p[1]);\r
 167         \r
 168         VectorAdd (org, vright, w->p[2]);\r
 169         VectorSubtract (w->p[2], vup, w->p[2]);\r
 170         \r
 171         VectorSubtract (org, vright, w->p[3]);\r
 172         VectorSubtract (w->p[3], vup, w->p[3]);\r
 173         \r
 174         w->numpoints = 4;\r
 175         \r
 176         return w;       \r
 177 }\r
 178 \r
 179 void FreeWinding (MY_WINDING *w)\r
 180 {\r
 181         if (*(unsigned *)w == 0xdeaddead)\r
 182 //              Error ("FreeWinding: freed a freed winding");\r
 183                 return;\r
 184         *(unsigned *)w = 0xdeaddead;\r
 185 \r
 186         free (w);\r
 187 }\r
 188 \r
 189 /*\r
 190 =============\r
 191 ChopWindingInPlace\r
 192 =============\r
 193 */\r
 194 void ChopWindingInPlace (MY_WINDING **inout, vec3 normal, vec dist, vec epsilon)\r
 195 {\r
 196         MY_WINDING *in;\r
 197         vec        dists[MAX_POINTS_ON_WINDING+4];\r
 198         int        sides[MAX_POINTS_ON_WINDING+4];\r
 199         int        counts[3];\r
 200         static vec dot;         // VC 4.2 optimizer bug if not static\r
 201         int        i, j;\r
 202         vec        *p1, *p2;\r
 203         vec3       mid;\r
 204         MY_WINDING *f;\r
 205         int        maxpts;\r
 206 \r
 207         in = *inout;\r
 208         counts[0] = counts[1] = counts[2] = 0;\r
 209 \r
 210 // determine sides for each point\r
 211         for (i=0 ; i<in->numpoints ; i++)\r
 212         {\r
 213                 dot = DotProduct (in->p[i], normal);\r
 214                 dot -= dist;\r
 215                 dists[i] = dot;\r
 216                 if (dot > epsilon)\r
 217                         sides[i] = SIDE_FRONT;\r
 218                 else if (dot < -epsilon)\r
 219                         sides[i] = SIDE_BACK;\r
 220                 else\r
 221                 {\r
 222                         sides[i] = SIDE_ON;\r
 223                 }\r
 224                 counts[sides[i]]++;\r
 225         }\r
 226         sides[i] = sides[0];\r
 227         dists[i] = dists[0];\r
 228         \r
 229         if (!counts[0])\r
 230         {\r
 231                 FreeWinding(in);\r
 232                 *inout = NULL;\r
 233                 return;\r
 234         }\r
 235         if (!counts[1])\r
 236                 return;         // inout stays the same\r
 237 \r
 238         maxpts = in->numpoints+4;       // cant use counts[0]+2 because\r
 239                                                                 // of fp grouping errors\r
 240 \r
 241         f = AllocWinding (maxpts);\r
 242                 \r
 243         for (i=0 ; i<in->numpoints ; i++)\r
 244         {\r
 245                 p1 = in->p[i];\r
 246                 \r
 247                 if (sides[i] == SIDE_ON)\r
 248                 {\r
 249                         VectorCopy (p1, f->p[f->numpoints]);\r
 250                         f->numpoints++;\r
 251                         continue;\r
 252                 }\r
 253         \r
 254                 if (sides[i] == SIDE_FRONT)\r
 255                 {\r
 256                         VectorCopy (p1, f->p[f->numpoints]);\r
 257                         f->numpoints++;\r
 258                 }\r
 259 \r
 260                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 261                         continue;\r
 262                         \r
 263         // generate a split point\r
 264                 p2 = in->p[(i+1)%in->numpoints];\r
 265                 \r
 266                 dot = dists[i] / (dists[i]-dists[i+1]);\r
 267                 for (j=0 ; j<3 ; j++)\r
 268                 {       // avoid round off error when possible\r
 269                         if (normal[j] == 1)\r
 270                                 mid[j] = dist;\r
 271                         else if (normal[j] == -1)\r
 272                                 mid[j] = -dist;\r
 273                         else\r
 274                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 275                 }\r
 276                         \r
 277                 VectorCopy (mid, f->p[f->numpoints]);\r
 278                 f->numpoints++;\r
 279         }\r
 280         \r
 281 //      if (f->numpoints > maxpts)\r
 282 //              Error ("ClipWinding: points exceeded estimate");\r
 283 //      if (f->numpoints > MAX_POINTS_ON_WINDING)\r
 284 //              Error ("ClipWinding: MAX_POINTS_ON_WINDING");\r
 285 \r
 286         FreeWinding(in);\r
 287         *inout = f;\r
 288 }\r
 289 \r
 290 void UseFaceBounds()\r
 291 {\r
 292         LPVOID       vp;\r
 293         float        Dot, BestDot;\r
 294         float            planepts[3][3];\r
 295         int          BestFace;\r
 296         int          i, j;\r
 297         int          NumFaces;\r
 298         vec3         SurfNormal;\r
 299         vec3         vmin,vmax;\r
 300         _QERFaceData *QERFaceData;\r
 301         PLANE        plane[MAX_FACES*2];\r
 302         PLANE        pface;\r
 303         MY_WINDING   *w;\r
 304 \r
 305         switch(Plane)\r
 306         {\r
 307         case PLANE_XY1:\r
 308                 SurfNormal[0] = 0.0;\r
 309                 SurfNormal[1] = 0.0;\r
 310                 SurfNormal[2] =-1.0;\r
 311                 break;\r
 312         case PLANE_XZ0:\r
 313                 SurfNormal[0] = 0.0;\r
 314                 SurfNormal[1] = 1.0;\r
 315                 SurfNormal[2] = 0.0;\r
 316                 break;\r
 317         case PLANE_XZ1:\r
 318                 SurfNormal[0] = 0.0;\r
 319                 SurfNormal[1] =-1.0;\r
 320                 SurfNormal[2] = 0.0;\r
 321                 break;\r
 322         case PLANE_YZ0:\r
 323                 SurfNormal[0] = 1.0;\r
 324                 SurfNormal[1] = 0.0;\r
 325                 SurfNormal[2] = 0.0;\r
 326                 break;\r
 327         case PLANE_YZ1:\r
 328                 SurfNormal[0] =-1.0;\r
 329                 SurfNormal[1] = 0.0;\r
 330                 SurfNormal[2] = 0.0;\r
 331                 break;\r
 332         default:\r
 333                 SurfNormal[0] = 0.0;\r
 334                 SurfNormal[1] = 0.0;\r
 335                 SurfNormal[2] = 1.0;\r
 336         }\r
 337 \r
 338         i  = g_FuncTable.m_pfnAllocateSelectedBrushHandles();\r
 339         vp = g_FuncTable.m_pfnGetSelectedBrushHandle(0);\r
 340         NumFaces = g_FuncTable.m_pfnGetFaceCount(vp);\r
 341 \r
 342         BestFace = -1;\r
 343         BestDot  = 0.0;\r
 344 \r
 345         for(i=0; i<NumFaces; i++)\r
 346         {\r
 347                 QERFaceData = g_FuncTable.m_pfnGetFaceData(vp,i);\r
 348                 planepts[0][0] = QERFaceData->m_v1[0];\r
 349                 planepts[0][1] = QERFaceData->m_v1[1];\r
 350                 planepts[0][2] = QERFaceData->m_v1[2];\r
 351                 planepts[1][0] = QERFaceData->m_v2[0];\r
 352                 planepts[1][1] = QERFaceData->m_v2[1];\r
 353                 planepts[1][2] = QERFaceData->m_v2[2];\r
 354                 planepts[2][0] = QERFaceData->m_v3[0];\r
 355                 planepts[2][1] = QERFaceData->m_v3[1];\r
 356                 planepts[2][2] = QERFaceData->m_v3[2];\r
 357 \r
 358                 PlaneFromPoints (planepts[0], planepts[1], planepts[2], &plane[2*i]);\r
 359                 VectorSubtract (vec3_origin, plane[2*i].normal, plane[2*i+1].normal);\r
 360                 plane[2*i+1].dist = -plane[2*i].dist;\r
 361 \r
 362                 Dot = DotProduct(plane[2*i].normal,SurfNormal);\r
 363                 if(Dot > BestDot)\r
 364                 {\r
 365                         BestDot  = Dot;\r
 366                         BestFace = i;\r
 367                         if(strlen(QERFaceData->m_TextureName))\r
 368                                 strcpy(Texture[Game][0],QERFaceData->m_TextureName);\r
 369                 }\r
 370         }\r
 371         for(i=0; i<NumFaces; i++)\r
 372         {\r
 373                 if(i==BestFace) continue;\r
 374                 QERFaceData = g_FuncTable.m_pfnGetFaceData(vp,i);\r
 375                 if(strlen(QERFaceData->m_TextureName))\r
 376                 {\r
 377                         if(strcmp(Texture[Game][0],QERFaceData->m_TextureName))\r
 378                                 strcpy(Texture[Game][1],QERFaceData->m_TextureName);\r
 379                 }\r
 380         }\r
 381 \r
 382 \r
 383         g_FuncTable.m_pfnReleaseSelectedBrushHandles();\r
 384 \r
 385         w = BaseWindingForPlane (plane[BestFace*2].normal, plane[BestFace*2].dist);\r
 386 \r
 387         for (i=0 ; i<NumFaces && w; i++)\r
 388         {\r
 389                 if (BestFace == i)\r
 390                         continue;\r
 391                 ChopWindingInPlace (&w, plane[i*2+1].normal, plane[i*2+1].dist, 0);\r
 392         }\r
 393         if(!w) return;\r
 394 \r
 395         // Get bounding box for this face\r
 396         vmin[0] = vmax[0] = w->p[0][0];\r
 397         vmin[1] = vmax[1] = w->p[0][1];\r
 398         vmin[2] = vmax[2] = w->p[0][2];\r
 399         for(j=1; j<w->numpoints; j++)\r
 400         {\r
 401                 vmin[0] = min(vmin[0],w->p[j][0]);\r
 402                 vmin[1] = min(vmin[1],w->p[j][1]);\r
 403                 vmin[2] = min(vmin[2],w->p[j][2]);\r
 404                 vmax[0] = max(vmax[0],w->p[j][0]);\r
 405                 vmax[1] = max(vmax[1],w->p[j][1]);\r
 406                 vmax[2] = max(vmax[2],w->p[j][2]);\r
 407         }\r
 408 \r
 409         FreeWinding(w);\r
 410 \r
 411         VectorCopy(plane[BestFace*2].normal,pface.normal);\r
 412         pface.dist = plane[BestFace*2].dist;\r
 413         switch(Plane)\r
 414         {\r
 415         case PLANE_XZ0:\r
 416         case PLANE_XZ1:\r
 417                 if(pface.normal[1] == 0.) return;\r
 418                 Hll = vmin[0];\r
 419                 Hur = vmax[0];\r
 420                 Vll = vmin[2];\r
 421                 Vur = vmax[2];\r
 422                 Z00 = (pface.dist - pface.normal[0]*Hll - pface.normal[2]*Vll)/pface.normal[1];\r
 423                 Z01 = (pface.dist - pface.normal[0]*Hll - pface.normal[2]*Vur)/pface.normal[1];\r
 424                 Z10 = (pface.dist - pface.normal[0]*Hur - pface.normal[2]*Vll)/pface.normal[1];\r
 425                 Z11 = (pface.dist - pface.normal[0]*Hur - pface.normal[2]*Vur)/pface.normal[1];\r
 426                 break;\r
 427         case PLANE_YZ0:\r
 428         case PLANE_YZ1:\r
 429                 if(pface.normal[0] == 0.) return;\r
 430                 Hll = vmin[1];\r
 431                 Hur = vmax[1];\r
 432                 Vll = vmin[2];\r
 433                 Vur = vmax[2];\r
 434                 Z00 = (pface.dist - pface.normal[1]*Hll - pface.normal[2]*Vll)/pface.normal[0];\r
 435                 Z01 = (pface.dist - pface.normal[1]*Hll - pface.normal[2]*Vur)/pface.normal[0];\r
 436                 Z10 = (pface.dist - pface.normal[1]*Hur - pface.normal[2]*Vll)/pface.normal[0];\r
 437                 Z11 = (pface.dist - pface.normal[1]*Hur - pface.normal[2]*Vur)/pface.normal[0];\r
 438                 break;\r
 439         default:\r
 440                 if(pface.normal[2] == 0.) return;\r
 441                 Hll = vmin[0];\r
 442                 Hur = vmax[0];\r
 443                 Vll = vmin[1];\r
 444                 Vur = vmax[1];\r
 445                 Z00 = (pface.dist - pface.normal[0]*Hll - pface.normal[1]*Vll)/pface.normal[2];\r
 446                 Z01 = (pface.dist - pface.normal[0]*Hll - pface.normal[1]*Vur)/pface.normal[2];\r
 447                 Z10 = (pface.dist - pface.normal[0]*Hur - pface.normal[1]*Vll)/pface.normal[2];\r
 448                 Z11 = (pface.dist - pface.normal[0]*Hur - pface.normal[1]*Vur)/pface.normal[2];\r
 449         }\r
 450 }\r