home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / qbsp / merge.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-12  |  5.1 KB  |  278 lines
  1. // merge.c
  2.  
  3. #include "bsp5.h"
  4.  
  5.  
  6. #define CONTINUOUS_EPSILON    0.001
  7.  
  8. /*
  9. ================
  10. CheckColinear
  11.  
  12. ================
  13. */
  14. void CheckColinear (face_t *f)
  15. {
  16.     int            i, j;
  17.     vec3_t        v1, v2;
  18.     
  19.     for (i=0 ; i<f->numpoints ;i++)
  20.     {
  21. // skip the point if the vector from the previous point is the same
  22. // as the vector to the next point
  23.         j = (i - 1 < 0) ? f->numpoints - 1 : i - 1;
  24.         VectorSubtract (f->pts[i], f->pts[j], v1);
  25.         VectorNormalize (v1);
  26.         
  27.         j = (i + 1 == f->numpoints) ? 0 : i + 1;
  28.         VectorSubtract (f->pts[j], f->pts[i], v2);
  29.         VectorNormalize (v2);
  30.         
  31.         if (VectorCompare (v1, v2))
  32.             Error ("Colinear edge");            
  33.     }
  34.     
  35. }
  36.  
  37.  
  38. /*
  39. =============
  40. TryMerge
  41.  
  42. If two polygons share a common edge and the edges that meet at the
  43. common points are both inside the other polygons, merge them
  44.  
  45. Returns NULL if the faces couldn't be merged, or the new face.
  46. The originals will NOT be freed.
  47. =============
  48. */
  49. face_t *TryMerge (face_t *f1, face_t *f2)
  50. {
  51.     vec_t        *p1, *p2, *p3, *p4, *back;
  52.     face_t        *newf;
  53.     int            i, j, k, l;
  54.     vec3_t        normal, delta, planenormal;
  55.     vec_t        dot;
  56.     plane_t        *plane;
  57.     qboolean        keep1, keep2;
  58.     
  59.     if (f1->numpoints == -1 || f2->numpoints == -1)
  60.         return NULL;
  61.     if (f1->planeside != f2->planeside)
  62.         return NULL;
  63.     if (f1->texturenum != f2->texturenum)
  64.         return NULL;
  65.     if (f1->contents[0] != f2->contents[0])
  66.         return NULL;
  67.     if (f1->contents[1] != f2->contents[1])
  68.         return NULL;
  69.         
  70. //
  71. // find a common edge
  72. //    
  73.     p1 = p2 = NULL;    // stop compiler warning
  74.     j = 0;            // 
  75.     
  76.     for (i=0 ; i<f1->numpoints ; i++)
  77.     {
  78.         p1 = f1->pts[i];
  79.         p2 = f1->pts[(i+1)%f1->numpoints];
  80.         for (j=0 ; j<f2->numpoints ; j++)
  81.         {
  82.             p3 = f2->pts[j];
  83.             p4 = f2->pts[(j+1)%f2->numpoints];
  84.             for (k=0 ; k<3 ; k++)
  85.             {
  86.                 if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
  87.                     break;
  88.                 if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
  89.                     break;
  90.             }
  91.             if (k==3)
  92.                 break;
  93.         }
  94.         if (j < f2->numpoints)
  95.             break;
  96.     }
  97.     
  98.     if (i == f1->numpoints)
  99.         return NULL;            // no matching edges
  100.  
  101. //
  102. // check slope of connected lines
  103. // if the slopes are colinear, the point can be removed
  104. //
  105.     plane = &planes[f1->planenum];
  106.     VectorCopy (plane->normal, planenormal);
  107.     if (f1->planeside)
  108.         VectorSubtract (vec3_origin, planenormal, planenormal);
  109.         
  110.     back = f1->pts[(i+f1->numpoints-1)%f1->numpoints];
  111.     VectorSubtract (p1, back, delta);
  112.     CrossProduct (planenormal, delta, normal);
  113.     VectorNormalize (normal);
  114.     
  115.     back = f2->pts[(j+2)%f2->numpoints];
  116.     VectorSubtract (back, p1, delta);
  117.     dot = DotProduct (delta, normal);
  118.     if (dot > CONTINUOUS_EPSILON)
  119.         return NULL;            // not a convex polygon
  120.     keep1 = dot < -CONTINUOUS_EPSILON;
  121.     
  122.     back = f1->pts[(i+2)%f1->numpoints];
  123.     VectorSubtract (back, p2, delta);
  124.     CrossProduct (planenormal, delta, normal);
  125.     VectorNormalize (normal);
  126.  
  127.     back = f2->pts[(j+f2->numpoints-1)%f2->numpoints];
  128.     VectorSubtract (back, p2, delta);
  129.     dot = DotProduct (delta, normal);
  130.     if (dot > CONTINUOUS_EPSILON)
  131.         return NULL;            // not a convex polygon
  132.     keep2 = dot < -CONTINUOUS_EPSILON;
  133.  
  134. //
  135. // build the new polygon
  136. //
  137.     if (f1->numpoints + f2->numpoints > MAXEDGES)
  138.     {
  139. //        Error ("TryMerge: too many edges!");
  140.         return NULL;
  141.     }
  142.  
  143.     newf = NewFaceFromFace (f1);
  144.     
  145. // copy first polygon
  146.     for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
  147.     {
  148.         if (k==(i+1)%f1->numpoints && !keep2)
  149.             continue;
  150.         
  151.         VectorCopy (f1->pts[k], newf->pts[newf->numpoints]);
  152.         newf->numpoints++;
  153.     }
  154.     
  155. // copy second polygon
  156.     for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
  157.     {
  158.         if (l==(j+1)%f2->numpoints && !keep1)
  159.             continue;
  160.         VectorCopy (f2->pts[l], newf->pts[newf->numpoints]);
  161.         newf->numpoints++;
  162.     }
  163.  
  164.     return newf;
  165. }
  166.  
  167.  
  168. /*
  169. ===============
  170. MergeFaceToList
  171. ===============
  172. */
  173. qboolean    mergedebug;
  174. face_t *MergeFaceToList (face_t *face, face_t *list)
  175. {    
  176.     face_t    *newf, *f;
  177.     
  178.     for (f=list ; f ; f=f->next)
  179.     {
  180. //CheckColinear (f);        
  181. if (mergedebug)
  182. {
  183. Draw_ClearWindow ();
  184. Draw_DrawFace (face);
  185. Draw_DrawFace (f);
  186. Draw_SetBlack ();
  187. }
  188.         newf = TryMerge (face, f);
  189.         if (!newf)
  190.             continue;
  191.         FreeFace (face);
  192.         f->numpoints = -1;        // merged out
  193.         return MergeFaceToList (newf, list);
  194.     }
  195.     
  196. // didn't merge, so add at start
  197.     face->next = list;
  198.     return face;
  199. }
  200.  
  201.  
  202. /*
  203. ===============
  204. FreeMergeListScraps
  205. ===============
  206. */
  207. face_t *FreeMergeListScraps (face_t *merged)
  208. {
  209.     face_t    *head, *next;
  210.     
  211.     head = NULL;
  212.     for ( ; merged ; merged = next)
  213.     {
  214.         next = merged->next;
  215.         if (merged->numpoints == -1)
  216.             FreeFace (merged);
  217.         else
  218.         {
  219.             merged->next = head;
  220.             head = merged;
  221.         }
  222.     }
  223.  
  224.     return head;
  225. }
  226.  
  227.  
  228. /*
  229. ===============
  230. MergePlaneFaces
  231. ===============
  232. */
  233. void MergePlaneFaces (surface_t *plane)
  234. {
  235.     face_t    *f1, *next;
  236.     face_t    *merged;
  237.     
  238.     merged = NULL;
  239.     
  240.     for (f1 = plane->faces ; f1 ; f1 = next)
  241.     {
  242.         next = f1->next;
  243.         merged = MergeFaceToList (f1, merged);
  244.     }
  245.  
  246. // chain all of the non-empty faces to the plane
  247.     plane->faces = FreeMergeListScraps (merged);
  248. }
  249.  
  250.  
  251. /*
  252. ============
  253. MergeAll
  254. ============
  255. */
  256. void MergeAll (surface_t *surfhead)
  257. {
  258.     surface_t       *surf;
  259.     int                     mergefaces;
  260.     face_t          *f;
  261.     
  262.     printf ("---- MergeAll ----\n");
  263.  
  264.     mergefaces = 0; 
  265.     for (surf = surfhead ; surf ; surf=surf->next)
  266.     {
  267.         MergePlaneFaces (surf);
  268. Draw_ClearWindow ();
  269.         for (f=surf->faces ; f ; f=f->next)
  270.         {
  271. Draw_DrawFace (f);
  272.             mergefaces++;
  273.         }
  274.     }
  275.     
  276.     printf ("%i mergefaces\n", mergefaces);
  277. }
  278.