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
19#include <math.h>
20#include <stdio.h>
21#include "Recast.h"
22#include "RecastAlloc.h"
23#include "RecastAssert.h"
24
25/// Check whether two bounding boxes overlap
26///
27/// @param[in] aMin Min axis extents of bounding box A
28/// @param[in] aMax Max axis extents of bounding box A
29/// @param[in] bMin Min axis extents of bounding box B
30/// @param[in] bMax Max axis extents of bounding box B
31/// @returns true if the two bounding boxes overlap. False otherwise.
32static bool overlapBounds(const float* aMin, const float* aMax, const float* bMin, const float* bMax)
33{
34 return
35 aMin[0] <= bMax[0] && aMax[0] >= bMin[0] &&
36 aMin[1] <= bMax[1] && aMax[1] >= bMin[1] &&
37 aMin[2] <= bMax[2] && aMax[2] >= bMin[2];
38}
39
40/// Allocates a new span in the heightfield.
41/// Use a memory pool and free list to minimize actual allocations.
42///
43/// @param[in] hf The heightfield
44/// @returns A pointer to the allocated or re-used span memory.
45static rcSpan* allocSpan(rcHeightfield& hf)
46{
47 // If necessary, allocate new page and update the freelist.
48 if (hf.freelist == NULL || hf.freelist->next == NULL)
49 {
50 // Create new page.
51 // Allocate memory for the new pool.
52 rcSpanPool* spanPool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM);
53 if (spanPool == NULL)
54 {
55 return NULL;
56 }
57
58 // Add the pool into the list of pools.
59 spanPool->next = hf.pools;
60 hf.pools = spanPool;
61
62 // Add new spans to the free list.
63 rcSpan* freeList = hf.freelist;
64 rcSpan* head = &spanPool->items[0];
65 rcSpan* it = &spanPool->items[RC_SPANS_PER_POOL];
66 do
67 {
68 --it;
69 it->next = freeList;
70 freeList = it;
71 }
72 while (it != head);
73 hf.freelist = it;
74 }
75
76 // Pop item from the front of the free list.
77 rcSpan* newSpan = hf.freelist;
78 hf.freelist = hf.freelist->next;
79 return newSpan;
80}
81
82/// Releases the memory used by the span back to the heightfield, so it can be re-used for new spans.
83/// @param[in] hf The heightfield.
84/// @param[in] span A pointer to the span to free
85static void freeSpan(rcHeightfield& hf, rcSpan* span)
86{
87 if (span == NULL)
88 {
89 return;
90 }
91 // Add the span to the front of the free list.
92 span->next = hf.freelist;
93 hf.freelist = span;
94}
95
96/// Adds a span to the heightfield. If the new span overlaps existing spans,
97/// it will merge the new span with the existing ones.
98///
99/// @param[in] hf Heightfield to add spans to
100/// @param[in] x The new span's column cell x index
101/// @param[in] z The new span's column cell z index
102/// @param[in] min The new span's minimum cell index
103/// @param[in] max The new span's maximum cell index
104/// @param[in] areaID The new span's area type ID
105/// @param[in] flagMergeThreshold How close two spans maximum extents need to be to merge area type IDs
106static bool addSpan(rcHeightfield& hf,
107 const int x, const int z,
108 const unsigned short min, const unsigned short max,
109 const unsigned char areaID, const int flagMergeThreshold)
110{
111 // Create the new span.
112 rcSpan* newSpan = allocSpan(hf);
113 if (newSpan == NULL)
114 {
115 return false;
116 }
117 newSpan->smin = min;
118 newSpan->smax = max;
119 newSpan->area = areaID;
120 newSpan->next = NULL;
121
122 const int columnIndex = x + z * hf.width;
123 rcSpan* previousSpan = NULL;
124 rcSpan* currentSpan = hf.spans[columnIndex];
125
126 // Insert the new span, possibly merging it with existing spans.
127 while (currentSpan != NULL)
128 {
129 if (currentSpan->smin > newSpan->smax)
130 {
131 // Current span is completely after the new span, break.
132 break;
133 }
134
135 if (currentSpan->smax < newSpan->smin)
136 {
137 // Current span is completely before the new span. Keep going.
138 previousSpan = currentSpan;
139 currentSpan = currentSpan->next;
140 }
141 else
142 {
143 // The new span overlaps with an existing span. Merge them.
144 if (currentSpan->smin < newSpan->smin)
145 {
146 newSpan->smin = currentSpan->smin;
147 }
148 if (currentSpan->smax > newSpan->smax)
149 {
150 newSpan->smax = currentSpan->smax;
151 }
152
153 // Merge flags.
154 if (rcAbs((int)newSpan->smax - (int)currentSpan->smax) <= flagMergeThreshold)
155 {
156 // Higher area ID numbers indicate higher resolution priority.
157 newSpan->area = rcMax(newSpan->area, currentSpan->area);
158 }
159
160 // Remove the current span since it's now merged with newSpan.
161 // Keep going because there might be other overlapping spans that also need to be merged.
162 rcSpan* next = currentSpan->next;
163 freeSpan(hf, currentSpan);
164 if (previousSpan)
165 {
166 previousSpan->next = next;
167 }
168 else
169 {
170 hf.spans[columnIndex] = next;
171 }
172 currentSpan = next;
173 }
174 }
175
176 // Insert new span after prev
177 if (previousSpan != NULL)
178 {
179 newSpan->next = previousSpan->next;
180 previousSpan->next = newSpan;
181 }
182 else
183 {
184 // This span should go before the others in the list
185 newSpan->next = hf.spans[columnIndex];
186 hf.spans[columnIndex] = newSpan;
187 }
188
189 return true;
190}
191
192bool rcAddSpan(rcContext* context, rcHeightfield& heightfield,
193 const int x, const int z,
194 const unsigned short spanMin, const unsigned short spanMax,
195 const unsigned char areaID, const int flagMergeThreshold)
196{
197 rcAssert(context);
198
199 if (!addSpan(heightfield, x, z, spanMin, spanMax, areaID, flagMergeThreshold))
200 {
201 context->log(RC_LOG_ERROR, "rcAddSpan: Out of memory.");
202 return false;
203 }
204
205 return true;
206}
207
208enum rcAxis
209{
210 RC_AXIS_X = 0,
211 RC_AXIS_Y = 1,
212 RC_AXIS_Z = 2
213};
214
215/// Divides a convex polygon of max 12 vertices into two convex polygons
216/// across a separating axis.
217///
218/// @param[in] inVerts The input polygon vertices
219/// @param[in] inVertsCount The number of input polygon vertices
220/// @param[out] outVerts1 Resulting polygon 1's vertices
221/// @param[out] outVerts1Count The number of resulting polygon 1 vertices
222/// @param[out] outVerts2 Resulting polygon 2's vertices
223/// @param[out] outVerts2Count The number of resulting polygon 2 vertices
224/// @param[in] axisOffset THe offset along the specified axis
225/// @param[in] axis The separating axis
226static void dividePoly(const float* inVerts, int inVertsCount,
227 float* outVerts1, int* outVerts1Count,
228 float* outVerts2, int* outVerts2Count,
229 float axisOffset, rcAxis axis)
230{
231 rcAssert(inVertsCount <= 12);
232
233 // How far positive or negative away from the separating axis is each vertex.
234 float inVertAxisDelta[12];
235 for (int inVert = 0; inVert < inVertsCount; ++inVert)
236 {
237 inVertAxisDelta[inVert] = axisOffset - inVerts[inVert * 3 + axis];
238 }
239
240 int poly1Vert = 0;
241 int poly2Vert = 0;
242 for (int inVertA = 0, inVertB = inVertsCount - 1; inVertA < inVertsCount; inVertB = inVertA, ++inVertA)
243 {
244 // If the two vertices are on the same side of the separating axis
245 bool sameSide = (inVertAxisDelta[inVertA] >= 0) == (inVertAxisDelta[inVertB] >= 0);
246
247 if (!sameSide)
248 {
249 float s = inVertAxisDelta[inVertB] / (inVertAxisDelta[inVertB] - inVertAxisDelta[inVertA]);
250 outVerts1[poly1Vert * 3 + 0] = inVerts[inVertB * 3 + 0] + (inVerts[inVertA * 3 + 0] - inVerts[inVertB * 3 + 0]) * s;
251 outVerts1[poly1Vert * 3 + 1] = inVerts[inVertB * 3 + 1] + (inVerts[inVertA * 3 + 1] - inVerts[inVertB * 3 + 1]) * s;
252 outVerts1[poly1Vert * 3 + 2] = inVerts[inVertB * 3 + 2] + (inVerts[inVertA * 3 + 2] - inVerts[inVertB * 3 + 2]) * s;
253 rcVcopy(&outVerts2[poly2Vert * 3], &outVerts1[poly1Vert * 3]);
254 poly1Vert++;
255 poly2Vert++;
256
257 // add the inVertA point to the right polygon. Do NOT add points that are on the dividing line
258 // since these were already added above
259 if (inVertAxisDelta[inVertA] > 0)
260 {
261 rcVcopy(&outVerts1[poly1Vert * 3], &inVerts[inVertA * 3]);
262 poly1Vert++;
263 }
264 else if (inVertAxisDelta[inVertA] < 0)
265 {
266 rcVcopy(&outVerts2[poly2Vert * 3], &inVerts[inVertA * 3]);
267 poly2Vert++;
268 }
269 }
270 else
271 {
272 // add the inVertA point to the right polygon. Addition is done even for points on the dividing line
273 if (inVertAxisDelta[inVertA] >= 0)
274 {
275 rcVcopy(&outVerts1[poly1Vert * 3], &inVerts[inVertA * 3]);
276 poly1Vert++;
277 if (inVertAxisDelta[inVertA] != 0)
278 {
279 continue;
280 }
281 }
282 rcVcopy(&outVerts2[poly2Vert * 3], &inVerts[inVertA * 3]);
283 poly2Vert++;
284 }
285 }
286
287 *outVerts1Count = poly1Vert;
288 *outVerts2Count = poly2Vert;
289}
290
291/// Rasterize a single triangle to the heightfield.
292///
293/// This code is extremely hot, so much care should be given to maintaining maximum perf here.
294///
295/// @param[in] v0 Triangle vertex 0
296/// @param[in] v1 Triangle vertex 1
297/// @param[in] v2 Triangle vertex 2
298/// @param[in] areaID The area ID to assign to the rasterized spans
299/// @param[in] hf Heightfield to rasterize into
300/// @param[in] hfBBMin The min extents of the heightfield bounding box
301/// @param[in] hfBBMax The max extents of the heightfield bounding box
302/// @param[in] cellSize The x and z axis size of a voxel in the heightfield
303/// @param[in] inverseCellSize 1 / cellSize
304/// @param[in] inverseCellHeight 1 / cellHeight
305/// @param[in] flagMergeThreshold The threshold in which area flags will be merged
306/// @returns true if the operation completes successfully. false if there was an error adding spans to the heightfield.
307static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
308 const unsigned char areaID, rcHeightfield& hf,
309 const float* hfBBMin, const float* hfBBMax,
310 const float cellSize, const float inverseCellSize, const float inverseCellHeight,
311 const int flagMergeThreshold)
312{
313 // Calculate the bounding box of the triangle.
314 float triBBMin[3];
315 rcVcopy(triBBMin, v0);
316 rcVmin(triBBMin, v1);
317 rcVmin(triBBMin, v2);
318
319 float triBBMax[3];
320 rcVcopy(triBBMax, v0);
321 rcVmax(triBBMax, v1);
322 rcVmax(triBBMax, v2);
323
324 // If the triangle does not touch the bounding box of the heightfield, skip the triangle.
325 if (!overlapBounds(triBBMin, triBBMax, hfBBMin, hfBBMax))
326 {
327 return true;
328 }
329
330 const int w = hf.width;
331 const int h = hf.height;
332 const float by = hfBBMax[1] - hfBBMin[1];
333
334 // Calculate the footprint of the triangle on the grid's z-axis
335 int z0 = (int)((triBBMin[2] - hfBBMin[2]) * inverseCellSize);
336 int z1 = (int)((triBBMax[2] - hfBBMin[2]) * inverseCellSize);
337
338 // use -1 rather than 0 to cut the polygon properly at the start of the tile
339 z0 = rcClamp(z0, -1, h - 1);
340 z1 = rcClamp(z1, 0, h - 1);
341
342 // Clip the triangle into all grid cells it touches.
343 float buf[7 * 3 * 4];
344 float* in = buf;
345 float* inRow = buf + 7 * 3;
346 float* p1 = inRow + 7 * 3;
347 float* p2 = p1 + 7 * 3;
348
349 rcVcopy(&in[0], v0);
350 rcVcopy(&in[1 * 3], v1);
351 rcVcopy(&in[2 * 3], v2);
352 int nvRow;
353 int nvIn = 3;
354
355 for (int z = z0; z <= z1; ++z)
356 {
357 // Clip polygon to row. Store the remaining polygon as well
358 const float cellZ = hfBBMin[2] + (float)z * cellSize;
359 dividePoly(in, nvIn, inRow, &nvRow, p1, &nvIn, cellZ + cellSize, RC_AXIS_Z);
360 rcSwap(in, p1);
361
362 if (nvRow < 3)
363 {
364 continue;
365 }
366 if (z < 0)
367 {
368 continue;
369 }
370
371 // find X-axis bounds of the row
372 float minX = inRow[0];
373 float maxX = inRow[0];
374 for (int vert = 1; vert < nvRow; ++vert)
375 {
376 if (minX > inRow[vert * 3])
377 {
378 minX = inRow[vert * 3];
379 }
380 if (maxX < inRow[vert * 3])
381 {
382 maxX = inRow[vert * 3];
383 }
384 }
385 int x0 = (int)((minX - hfBBMin[0]) * inverseCellSize);
386 int x1 = (int)((maxX - hfBBMin[0]) * inverseCellSize);
387 if (x1 < 0 || x0 >= w)
388 {
389 continue;
390 }
391 x0 = rcClamp(x0, -1, w - 1);
392 x1 = rcClamp(x1, 0, w - 1);
393
394 int nv;
395 int nv2 = nvRow;
396
397 for (int x = x0; x <= x1; ++x)
398 {
399 // Clip polygon to column. store the remaining polygon as well
400 const float cx = hfBBMin[0] + (float)x * cellSize;
401 dividePoly(inRow, nv2, p1, &nv, p2, &nv2, cx + cellSize, RC_AXIS_X);
402 rcSwap(inRow, p2);
403
404 if (nv < 3)
405 {
406 continue;
407 }
408 if (x < 0)
409 {
410 continue;
411 }
412
413 // Calculate min and max of the span.
414 float spanMin = p1[1];
415 float spanMax = p1[1];
416 for (int vert = 1; vert < nv; ++vert)
417 {
418 spanMin = rcMin(spanMin, p1[vert * 3 + 1]);
419 spanMax = rcMax(spanMax, p1[vert * 3 + 1]);
420 }
421 spanMin -= hfBBMin[1];
422 spanMax -= hfBBMin[1];
423
424 // Skip the span if it's completely outside the heightfield bounding box
425 if (spanMax < 0.0f)
426 {
427 continue;
428 }
429 if (spanMin > by)
430 {
431 continue;
432 }
433
434 // Clamp the span to the heightfield bounding box.
435 if (spanMin < 0.0f)
436 {
437 spanMin = 0;
438 }
439 if (spanMax > by)
440 {
441 spanMax = by;
442 }
443
444 // Snap the span to the heightfield height grid.
445 unsigned short spanMinCellIndex = (unsigned short)rcClamp((int)floorf(spanMin * inverseCellHeight), 0, RC_SPAN_MAX_HEIGHT);
446 unsigned short spanMaxCellIndex = (unsigned short)rcClamp((int)ceilf(spanMax * inverseCellHeight), (int)spanMinCellIndex + 1, RC_SPAN_MAX_HEIGHT);
447
448 if (!addSpan(hf, x, z, spanMinCellIndex, spanMaxCellIndex, areaID, flagMergeThreshold))
449 {
450 return false;
451 }
452 }
453 }
454
455 return true;
456}
457
458bool rcRasterizeTriangle(rcContext* context,
459 const float* v0, const float* v1, const float* v2,
460 const unsigned char areaID, rcHeightfield& heightfield, const int flagMergeThreshold)
461{
462 rcAssert(context != NULL);
463
464 rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
465
466 // Rasterize the single triangle.
467 const float inverseCellSize = 1.0f / heightfield.cs;
468 const float inverseCellHeight = 1.0f / heightfield.ch;
469 if (!rasterizeTri(v0, v1, v2, areaID, heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
470 {
471 context->log(RC_LOG_ERROR, "rcRasterizeTriangle: Out of memory.");
472 return false;
473 }
474
475 return true;
476}
477
478bool rcRasterizeTriangles(rcContext* context,
479 const float* verts, const int /*nv*/,
480 const int* tris, const unsigned char* triAreaIDs, const int numTris,
481 rcHeightfield& heightfield, const int flagMergeThreshold)
482{
483 rcAssert(context != NULL);
484
485 rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
486
487 // Rasterize the triangles.
488 const float inverseCellSize = 1.0f / heightfield.cs;
489 const float inverseCellHeight = 1.0f / heightfield.ch;
490 for (int triIndex = 0; triIndex < numTris; ++triIndex)
491 {
492 const float* v0 = &verts[tris[triIndex * 3 + 0] * 3];
493 const float* v1 = &verts[tris[triIndex * 3 + 1] * 3];
494 const float* v2 = &verts[tris[triIndex * 3 + 2] * 3];
495 if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
496 {
497 context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
498 return false;
499 }
500 }
501
502 return true;
503}
504
505bool rcRasterizeTriangles(rcContext* context,
506 const float* verts, const int /*nv*/,
507 const unsigned short* tris, const unsigned char* triAreaIDs, const int numTris,
508 rcHeightfield& heightfield, const int flagMergeThreshold)
509{
510 rcAssert(context != NULL);
511
512 rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
513
514 // Rasterize the triangles.
515 const float inverseCellSize = 1.0f / heightfield.cs;
516 const float inverseCellHeight = 1.0f / heightfield.ch;
517 for (int triIndex = 0; triIndex < numTris; ++triIndex)
518 {
519 const float* v0 = &verts[tris[triIndex * 3 + 0] * 3];
520 const float* v1 = &verts[tris[triIndex * 3 + 1] * 3];
521 const float* v2 = &verts[tris[triIndex * 3 + 2] * 3];
522 if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
523 {
524 context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
525 return false;
526 }
527 }
528
529 return true;
530}
531
532bool rcRasterizeTriangles(rcContext* context,
533 const float* verts, const unsigned char* triAreaIDs, const int numTris,
534 rcHeightfield& heightfield, const int flagMergeThreshold)
535{
536 rcAssert(context != NULL);
537
538 rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
539
540 // Rasterize the triangles.
541 const float inverseCellSize = 1.0f / heightfield.cs;
542 const float inverseCellHeight = 1.0f / heightfield.ch;
543 for (int triIndex = 0; triIndex < numTris; ++triIndex)
544 {
545 const float* v0 = &verts[(triIndex * 3 + 0) * 3];
546 const float* v1 = &verts[(triIndex * 3 + 1) * 3];
547 const float* v2 = &verts[(triIndex * 3 + 2) * 3];
548 if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
549 {
550 context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
551 return false;
552 }
553 }
554
555 return true;
556}
557