9
3

RecastRasterization.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454
  1. //
  2. // Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
  3. //
  4. // This software is provided 'as-is', without any express or implied
  5. // warranty. In no event will the authors be held liable for any damages
  6. // arising from the use of this software.
  7. // Permission is granted to anyone to use this software for any purpose,
  8. // including commercial applications, and to alter it and redistribute it
  9. // freely, subject to the following restrictions:
  10. // 1. The origin of this software must not be misrepresented; you must not
  11. // claim that you wrote the original software. If you use this software
  12. // in a product, an acknowledgment in the product documentation would be
  13. // appreciated but is not required.
  14. // 2. Altered source versions must be plainly marked as such, and must not be
  15. // misrepresented as being the original software.
  16. // 3. This notice may not be removed or altered from any source distribution.
  17. //
  18. #define _USE_MATH_DEFINES
  19. #include <math.h>
  20. #include <stdio.h>
  21. #include "Recast.h"
  22. #include "RecastAlloc.h"
  23. #include "RecastAssert.h"
  24. inline bool overlapBounds(const float* amin, const float* amax, const float* bmin, const float* bmax)
  25. {
  26. bool overlap = true;
  27. overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
  28. overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
  29. overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap;
  30. return overlap;
  31. }
  32. inline bool overlapInterval(unsigned short amin, unsigned short amax,
  33. unsigned short bmin, unsigned short bmax)
  34. {
  35. if (amax < bmin) return false;
  36. if (amin > bmax) return false;
  37. return true;
  38. }
  39. static rcSpan* allocSpan(rcHeightfield& hf)
  40. {
  41. // If running out of memory, allocate new page and update the freelist.
  42. if (!hf.freelist || !hf.freelist->next)
  43. {
  44. // Create new page.
  45. // Allocate memory for the new pool.
  46. rcSpanPool* pool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM);
  47. if (!pool) return 0;
  48. // Add the pool into the list of pools.
  49. pool->next = hf.pools;
  50. hf.pools = pool;
  51. // Add new items to the free list.
  52. rcSpan* freelist = hf.freelist;
  53. rcSpan* head = &pool->items[0];
  54. rcSpan* it = &pool->items[RC_SPANS_PER_POOL];
  55. do
  56. {
  57. --it;
  58. it->next = freelist;
  59. freelist = it;
  60. }
  61. while (it != head);
  62. hf.freelist = it;
  63. }
  64. // Pop item from in front of the free list.
  65. rcSpan* it = hf.freelist;
  66. hf.freelist = hf.freelist->next;
  67. return it;
  68. }
  69. static void freeSpan(rcHeightfield& hf, rcSpan* ptr)
  70. {
  71. if (!ptr) return;
  72. // Add the node in front of the free list.
  73. ptr->next = hf.freelist;
  74. hf.freelist = ptr;
  75. }
  76. static bool addSpan(rcHeightfield& hf, const int x, const int y,
  77. const unsigned short smin, const unsigned short smax,
  78. const unsigned char area, const int flagMergeThr)
  79. {
  80. int idx = x + y*hf.width;
  81. rcSpan* s = allocSpan(hf);
  82. if (!s)
  83. return false;
  84. s->smin = smin;
  85. s->smax = smax;
  86. s->area = area;
  87. s->next = 0;
  88. // Empty cell, add the first span.
  89. if (!hf.spans[idx])
  90. {
  91. hf.spans[idx] = s;
  92. return true;
  93. }
  94. rcSpan* prev = 0;
  95. rcSpan* cur = hf.spans[idx];
  96. // Insert and merge spans.
  97. while (cur)
  98. {
  99. if (cur->smin > s->smax)
  100. {
  101. // Current span is further than the new span, break.
  102. break;
  103. }
  104. else if (cur->smax < s->smin)
  105. {
  106. // Current span is before the new span advance.
  107. prev = cur;
  108. cur = cur->next;
  109. }
  110. else
  111. {
  112. // Merge spans.
  113. if (cur->smin < s->smin)
  114. s->smin = cur->smin;
  115. if (cur->smax > s->smax)
  116. s->smax = cur->smax;
  117. // Merge flags.
  118. if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr)
  119. s->area = rcMax(s->area, cur->area);
  120. // Remove current span.
  121. rcSpan* next = cur->next;
  122. freeSpan(hf, cur);
  123. if (prev)
  124. prev->next = next;
  125. else
  126. hf.spans[idx] = next;
  127. cur = next;
  128. }
  129. }
  130. // Insert new span.
  131. if (prev)
  132. {
  133. s->next = prev->next;
  134. prev->next = s;
  135. }
  136. else
  137. {
  138. s->next = hf.spans[idx];
  139. hf.spans[idx] = s;
  140. }
  141. return true;
  142. }
  143. /// @par
  144. ///
  145. /// The span addition can be set to favor flags. If the span is merged to
  146. /// another span and the new @p smax is within @p flagMergeThr units
  147. /// from the existing span, the span flags are merged.
  148. ///
  149. /// @see rcHeightfield, rcSpan.
  150. bool rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y,
  151. const unsigned short smin, const unsigned short smax,
  152. const unsigned char area, const int flagMergeThr)
  153. {
  154. rcAssert(ctx);
  155. if (!addSpan(hf, x, y, smin, smax, area, flagMergeThr))
  156. {
  157. ctx->log(RC_LOG_ERROR, "rcAddSpan: Out of memory.");
  158. return false;
  159. }
  160. return true;
  161. }
  162. // divides a convex polygons into two convex polygons on both sides of a line
  163. static void dividePoly(const float* in, int nin,
  164. float* out1, int* nout1,
  165. float* out2, int* nout2,
  166. float x, int axis)
  167. {
  168. float d[12];
  169. for (int i = 0; i < nin; ++i)
  170. d[i] = x - in[i*3+axis];
  171. int m = 0, n = 0;
  172. for (int i = 0, j = nin-1; i < nin; j=i, ++i)
  173. {
  174. bool ina = d[j] >= 0;
  175. bool inb = d[i] >= 0;
  176. if (ina != inb)
  177. {
  178. float s = d[j] / (d[j] - d[i]);
  179. out1[m*3+0] = in[j*3+0] + (in[i*3+0] - in[j*3+0])*s;
  180. out1[m*3+1] = in[j*3+1] + (in[i*3+1] - in[j*3+1])*s;
  181. out1[m*3+2] = in[j*3+2] + (in[i*3+2] - in[j*3+2])*s;
  182. rcVcopy(out2 + n*3, out1 + m*3);
  183. m++;
  184. n++;
  185. // add the i'th point to the right polygon. Do NOT add points that are on the dividing line
  186. // since these were already added above
  187. if (d[i] > 0)
  188. {
  189. rcVcopy(out1 + m*3, in + i*3);
  190. m++;
  191. }
  192. else if (d[i] < 0)
  193. {
  194. rcVcopy(out2 + n*3, in + i*3);
  195. n++;
  196. }
  197. }
  198. else // same side
  199. {
  200. // add the i'th point to the right polygon. Addition is done even for points on the dividing line
  201. if (d[i] >= 0)
  202. {
  203. rcVcopy(out1 + m*3, in + i*3);
  204. m++;
  205. if (d[i] != 0)
  206. continue;
  207. }
  208. rcVcopy(out2 + n*3, in + i*3);
  209. n++;
  210. }
  211. }
  212. *nout1 = m;
  213. *nout2 = n;
  214. }
  215. static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
  216. const unsigned char area, rcHeightfield& hf,
  217. const float* bmin, const float* bmax,
  218. const float cs, const float ics, const float ich,
  219. const int flagMergeThr)
  220. {
  221. const int w = hf.width;
  222. const int h = hf.height;
  223. float tmin[3], tmax[3];
  224. const float by = bmax[1] - bmin[1];
  225. // Calculate the bounding box of the triangle.
  226. rcVcopy(tmin, v0);
  227. rcVcopy(tmax, v0);
  228. rcVmin(tmin, v1);
  229. rcVmin(tmin, v2);
  230. rcVmax(tmax, v1);
  231. rcVmax(tmax, v2);
  232. // If the triangle does not touch the bbox of the heightfield, skip the triagle.
  233. if (!overlapBounds(bmin, bmax, tmin, tmax))
  234. return true;
  235. // Calculate the footprint of the triangle on the grid's y-axis
  236. int y0 = (int)((tmin[2] - bmin[2])*ics);
  237. int y1 = (int)((tmax[2] - bmin[2])*ics);
  238. y0 = rcClamp(y0, 0, h-1);
  239. y1 = rcClamp(y1, 0, h-1);
  240. // Clip the triangle into all grid cells it touches.
  241. float buf[7*3*4];
  242. float *in = buf, *inrow = buf+7*3, *p1 = inrow+7*3, *p2 = p1+7*3;
  243. rcVcopy(&in[0], v0);
  244. rcVcopy(&in[1*3], v1);
  245. rcVcopy(&in[2*3], v2);
  246. int nvrow, nvIn = 3;
  247. for (int y = y0; y <= y1; ++y)
  248. {
  249. // Clip polygon to row. Store the remaining polygon as well
  250. const float cz = bmin[2] + y*cs;
  251. dividePoly(in, nvIn, inrow, &nvrow, p1, &nvIn, cz+cs, 2);
  252. rcSwap(in, p1);
  253. if (nvrow < 3) continue;
  254. // find the horizontal bounds in the row
  255. float minX = inrow[0], maxX = inrow[0];
  256. for (int i=1; i<nvrow; ++i)
  257. {
  258. if (minX > inrow[i*3]) minX = inrow[i*3];
  259. if (maxX < inrow[i*3]) maxX = inrow[i*3];
  260. }
  261. int x0 = (int)((minX - bmin[0])*ics);
  262. int x1 = (int)((maxX - bmin[0])*ics);
  263. x0 = rcClamp(x0, 0, w-1);
  264. x1 = rcClamp(x1, 0, w-1);
  265. int nv, nv2 = nvrow;
  266. for (int x = x0; x <= x1; ++x)
  267. {
  268. // Clip polygon to column. store the remaining polygon as well
  269. const float cx = bmin[0] + x*cs;
  270. dividePoly(inrow, nv2, p1, &nv, p2, &nv2, cx+cs, 0);
  271. rcSwap(inrow, p2);
  272. if (nv < 3) continue;
  273. // Calculate min and max of the span.
  274. float smin = p1[1], smax = p1[1];
  275. for (int i = 1; i < nv; ++i)
  276. {
  277. smin = rcMin(smin, p1[i*3+1]);
  278. smax = rcMax(smax, p1[i*3+1]);
  279. }
  280. smin -= bmin[1];
  281. smax -= bmin[1];
  282. // Skip the span if it is outside the heightfield bbox
  283. if (smax < 0.0f) continue;
  284. if (smin > by) continue;
  285. // Clamp the span to the heightfield bbox.
  286. if (smin < 0.0f) smin = 0;
  287. if (smax > by) smax = by;
  288. // Snap the span to the heightfield height grid.
  289. unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, RC_SPAN_MAX_HEIGHT);
  290. unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), (int)ismin+1, RC_SPAN_MAX_HEIGHT);
  291. if (!addSpan(hf, x, y, ismin, ismax, area, flagMergeThr))
  292. return false;
  293. }
  294. }
  295. return true;
  296. }
  297. /// @par
  298. ///
  299. /// No spans will be added if the triangle does not overlap the heightfield grid.
  300. ///
  301. /// @see rcHeightfield
  302. bool rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2,
  303. const unsigned char area, rcHeightfield& solid,
  304. const int flagMergeThr)
  305. {
  306. rcAssert(ctx);
  307. rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
  308. const float ics = 1.0f/solid.cs;
  309. const float ich = 1.0f/solid.ch;
  310. if (!rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
  311. {
  312. ctx->log(RC_LOG_ERROR, "rcRasterizeTriangle: Out of memory.");
  313. return false;
  314. }
  315. return true;
  316. }
  317. /// @par
  318. ///
  319. /// Spans will only be added for triangles that overlap the heightfield grid.
  320. ///
  321. /// @see rcHeightfield
  322. bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
  323. const int* tris, const unsigned char* areas, const int nt,
  324. rcHeightfield& solid, const int flagMergeThr)
  325. {
  326. rcAssert(ctx);
  327. rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
  328. const float ics = 1.0f/solid.cs;
  329. const float ich = 1.0f/solid.ch;
  330. // Rasterize triangles.
  331. for (int i = 0; i < nt; ++i)
  332. {
  333. const float* v0 = &verts[tris[i*3+0]*3];
  334. const float* v1 = &verts[tris[i*3+1]*3];
  335. const float* v2 = &verts[tris[i*3+2]*3];
  336. // Rasterize.
  337. if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
  338. {
  339. ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
  340. return false;
  341. }
  342. }
  343. return true;
  344. }
  345. /// @par
  346. ///
  347. /// Spans will only be added for triangles that overlap the heightfield grid.
  348. ///
  349. /// @see rcHeightfield
  350. bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
  351. const unsigned short* tris, const unsigned char* areas, const int nt,
  352. rcHeightfield& solid, const int flagMergeThr)
  353. {
  354. rcAssert(ctx);
  355. rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
  356. const float ics = 1.0f/solid.cs;
  357. const float ich = 1.0f/solid.ch;
  358. // Rasterize triangles.
  359. for (int i = 0; i < nt; ++i)
  360. {
  361. const float* v0 = &verts[tris[i*3+0]*3];
  362. const float* v1 = &verts[tris[i*3+1]*3];
  363. const float* v2 = &verts[tris[i*3+2]*3];
  364. // Rasterize.
  365. if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
  366. {
  367. ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
  368. return false;
  369. }
  370. }
  371. return true;
  372. }
  373. /// @par
  374. ///
  375. /// Spans will only be added for triangles that overlap the heightfield grid.
  376. ///
  377. /// @see rcHeightfield
  378. bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt,
  379. rcHeightfield& solid, const int flagMergeThr)
  380. {
  381. rcAssert(ctx);
  382. rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
  383. const float ics = 1.0f/solid.cs;
  384. const float ich = 1.0f/solid.ch;
  385. // Rasterize triangles.
  386. for (int i = 0; i < nt; ++i)
  387. {
  388. const float* v0 = &verts[(i*3+0)*3];
  389. const float* v1 = &verts[(i*3+1)*3];
  390. const float* v2 = &verts[(i*3+2)*3];
  391. // Rasterize.
  392. if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
  393. {
  394. ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
  395. return false;
  396. }
  397. }
  398. return true;
  399. }