merge.cpp 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259
  1. #include "bsp5.h"
  2. // TryMerge
  3. // MergeFaceToList
  4. // FreeMergeListScraps
  5. // MergePlaneFaces
  6. // MergeAll
  7. #define CONTINUOUS_EPSILON ON_EPSILON
  8. // =====================================================================================
  9. // TryMerge
  10. // If two polygons share a common edge and the edges that meet at the
  11. // common points are both inside the other polygons, merge them
  12. // Returns NULL if the faces couldn't be merged, or the new face.
  13. // The originals will NOT be freed.
  14. // =====================================================================================
  15. static face_t* TryMerge(face_t* f1, face_t* f2)
  16. {
  17. vec_t* p1;
  18. vec_t* p2;
  19. vec_t* p3;
  20. vec_t* p4;
  21. vec_t* back;
  22. face_t* newf;
  23. int i;
  24. int j;
  25. int k;
  26. int l;
  27. vec3_t normal;
  28. vec3_t delta;
  29. vec3_t planenormal;
  30. vec_t dot;
  31. dplane_t* plane;
  32. bool keep1;
  33. bool keep2;
  34. if (f1->numpoints == -1 || f2->numpoints == -1)
  35. {
  36. return NULL;
  37. }
  38. if (f1->texturenum != f2->texturenum)
  39. {
  40. return NULL;
  41. }
  42. if (f1->contents != f2->contents)
  43. {
  44. return NULL;
  45. }
  46. //
  47. // find a common edge
  48. //
  49. p1 = p2 = NULL; // shut up the compiler
  50. j = 0;
  51. for (i = 0; i < f1->numpoints; i++)
  52. {
  53. p1 = f1->pts[i];
  54. p2 = f1->pts[(i + 1) % f1->numpoints];
  55. for (j = 0; j < f2->numpoints; j++)
  56. {
  57. p3 = f2->pts[j];
  58. p4 = f2->pts[(j + 1) % f2->numpoints];
  59. for (k = 0; k < 3; k++)
  60. {
  61. if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
  62. {
  63. break;
  64. }
  65. if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
  66. {
  67. break;
  68. }
  69. }
  70. if (k == 3)
  71. {
  72. break;
  73. }
  74. }
  75. if (j < f2->numpoints)
  76. {
  77. break;
  78. }
  79. }
  80. if (i == f1->numpoints)
  81. {
  82. return NULL; // no matching edges
  83. }
  84. //
  85. // check slope of connected lines
  86. // if the slopes are colinear, the point can be removed
  87. //
  88. plane = &g_dplanes[f1->planenum];
  89. VectorCopy(plane->normal, planenormal);
  90. back = f1->pts[(i + f1->numpoints - 1) % f1->numpoints];
  91. VectorSubtract(p1, back, delta);
  92. CrossProduct(planenormal, delta, normal);
  93. VectorNormalize(normal);
  94. back = f2->pts[(j + 2) % f2->numpoints];
  95. VectorSubtract(back, p1, delta);
  96. dot = DotProduct(delta, normal);
  97. if (dot > CONTINUOUS_EPSILON)
  98. {
  99. return NULL; // not a convex polygon
  100. }
  101. keep1 = dot < -CONTINUOUS_EPSILON;
  102. back = f1->pts[(i + 2) % f1->numpoints];
  103. VectorSubtract(back, p2, delta);
  104. CrossProduct(planenormal, delta, normal);
  105. VectorNormalize(normal);
  106. back = f2->pts[(j + f2->numpoints - 1) % f2->numpoints];
  107. VectorSubtract(back, p2, delta);
  108. dot = DotProduct(delta, normal);
  109. if (dot > CONTINUOUS_EPSILON)
  110. {
  111. return NULL; // not a convex polygon
  112. }
  113. keep2 = dot < -CONTINUOUS_EPSILON;
  114. //
  115. // build the new polygon
  116. //
  117. if (f1->numpoints + f2->numpoints > MAXEDGES)
  118. {
  119. // Error ("TryMerge: too many edges!");
  120. return NULL;
  121. }
  122. newf = NewFaceFromFace(f1);
  123. // copy first polygon
  124. for (k = (i + 1) % f1->numpoints; k != i; k = (k + 1) % f1->numpoints)
  125. {
  126. if (k == (i + 1) % f1->numpoints && !keep2)
  127. {
  128. continue;
  129. }
  130. VectorCopy(f1->pts[k], newf->pts[newf->numpoints]);
  131. newf->numpoints++;
  132. }
  133. // copy second polygon
  134. for (l = (j + 1) % f2->numpoints; l != j; l = (l + 1) % f2->numpoints)
  135. {
  136. if (l == (j + 1) % f2->numpoints && !keep1)
  137. {
  138. continue;
  139. }
  140. VectorCopy(f2->pts[l], newf->pts[newf->numpoints]);
  141. newf->numpoints++;
  142. }
  143. return newf;
  144. }
  145. // =====================================================================================
  146. // MergeFaceToList
  147. // =====================================================================================
  148. static face_t* MergeFaceToList(face_t* face, face_t* list)
  149. {
  150. face_t* newf;
  151. face_t* f;
  152. for (f = list; f; f = f->next)
  153. {
  154. //CheckColinear (f);
  155. newf = TryMerge(face, f);
  156. if (!newf)
  157. {
  158. continue;
  159. }
  160. FreeFace(face);
  161. f->numpoints = -1; // merged out
  162. return MergeFaceToList(newf, list);
  163. }
  164. // didn't merge, so add at start
  165. face->next = list;
  166. return face;
  167. }
  168. // =====================================================================================
  169. // FreeMergeListScraps
  170. // =====================================================================================
  171. static face_t* FreeMergeListScraps(face_t* merged)
  172. {
  173. face_t* head;
  174. face_t* next;
  175. head = NULL;
  176. for (; merged; merged = next)
  177. {
  178. next = merged->next;
  179. if (merged->numpoints == -1)
  180. {
  181. FreeFace(merged);
  182. }
  183. else
  184. {
  185. merged->next = head;
  186. head = merged;
  187. }
  188. }
  189. return head;
  190. }
  191. // =====================================================================================
  192. // MergePlaneFaces
  193. // =====================================================================================
  194. void MergePlaneFaces(surface_t* plane)
  195. {
  196. face_t* f1;
  197. face_t* next;
  198. face_t* merged;
  199. merged = NULL;
  200. for (f1 = plane->faces; f1; f1 = next)
  201. {
  202. next = f1->next;
  203. merged = MergeFaceToList(f1, merged);
  204. }
  205. // chain all of the non-empty faces to the plane
  206. plane->faces = FreeMergeListScraps(merged);
  207. }
  208. // =====================================================================================
  209. // MergeAll
  210. // =====================================================================================
  211. void MergeAll(surface_t* surfhead)
  212. {
  213. surface_t* surf;
  214. int mergefaces;
  215. face_t* f;
  216. Verbose("---- MergeAll ----\n");
  217. mergefaces = 0;
  218. for (surf = surfhead; surf; surf = surf->next)
  219. {
  220. MergePlaneFaces(surf);
  221. for (f = surf->faces; f; f = f->next)
  222. {
  223. mergefaces++;
  224. }
  225. }
  226. Verbose("%i mergefaces\n", mergefaces);
  227. }