diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastRasterization.cpp')
-rw-r--r-- | extern/recastnavigation/Recast/Source/RecastRasterization.cpp | 167 |
1 files changed, 123 insertions, 44 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastRasterization.cpp b/extern/recastnavigation/Recast/Source/RecastRasterization.cpp index 658b0e1fb51..d2bb7c98f18 100644 --- a/extern/recastnavigation/Recast/Source/RecastRasterization.cpp +++ b/extern/recastnavigation/Recast/Source/RecastRasterization.cpp @@ -1,5 +1,5 @@ // -// Copyright (c) 2009 Mikko Mononen memon@inside.org +// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org // // This software is provided 'as-is', without any express or implied // warranty. In no event will the authors be held liable for any damages @@ -20,8 +20,8 @@ #include <math.h> #include <stdio.h> #include "Recast.h" -#include "RecastTimer.h" -#include "RecastLog.h" +#include "RecastAlloc.h" +#include "RecastAssert.h" inline bool overlapBounds(const float* amin, const float* amax, const float* bmin, const float* bmax) { @@ -48,8 +48,7 @@ static rcSpan* allocSpan(rcHeightfield& hf) { // Create new page. // Allocate memory for the new pool. - const int size = (sizeof(rcSpanPool)-sizeof(rcSpan)) + sizeof(rcSpan)*RC_SPANS_PER_POOL; - rcSpanPool* pool = reinterpret_cast<rcSpanPool*>(new unsigned char[size]); + rcSpanPool* pool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM); if (!pool) return 0; pool->next = 0; // Add the pool into the list of pools. @@ -83,16 +82,17 @@ static void freeSpan(rcHeightfield& hf, rcSpan* ptr) hf.freelist = ptr; } -static void addSpan(rcHeightfield& hf, int x, int y, - unsigned short smin, unsigned short smax, - unsigned short flags) +static void addSpan(rcHeightfield& hf, const int x, const int y, + const unsigned short smin, const unsigned short smax, + const unsigned char area, const int flagMergeThr) { + int idx = x + y*hf.width; rcSpan* s = allocSpan(hf); s->smin = smin; s->smax = smax; - s->flags = flags; + s->area = area; s->next = 0; // Empty cell, add he first span. @@ -127,9 +127,8 @@ static void addSpan(rcHeightfield& hf, int x, int y, s->smax = cur->smax; // Merge flags. -// if (s->smax == cur->smax) - if (rcAbs((int)s->smax - (int)cur->smax) <= 1) - s->flags |= cur->flags; + if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr) + s->area = rcMax(s->area, cur->area); // Remove current span. rcSpan* next = cur->next; @@ -155,6 +154,21 @@ static void addSpan(rcHeightfield& hf, int x, int y, } } +/// @par +/// +/// The span addition can be set to favor flags. If the span is merged to +/// another span and the new @p smax is within @p flagMergeThr units +/// from the existing span, the span flags are merged. +/// +/// @see rcHeightfield, rcSpan. +void rcAddSpan(rcContext* /*ctx*/, rcHeightfield& hf, const int x, const int y, + const unsigned short smin, const unsigned short smax, + const unsigned char area, const int flagMergeThr) +{ +// rcAssert(ctx); + addSpan(hf, x,y, smin, smax, area, flagMergeThr); +} + static int clipPoly(const float* in, int n, float* out, float pnx, float pnz, float pd) { float d[12]; @@ -186,9 +200,10 @@ static int clipPoly(const float* in, int n, float* out, float pnx, float pnz, fl } static void rasterizeTri(const float* v0, const float* v1, const float* v2, - unsigned char flags, rcHeightfield& hf, + const unsigned char area, rcHeightfield& hf, const float* bmin, const float* bmax, - const float cs, const float ics, const float ich) + const float cs, const float ics, const float ich, + const int flagMergeThr) { const int w = hf.width; const int h = hf.height; @@ -196,12 +211,12 @@ static void rasterizeTri(const float* v0, const float* v1, const float* v2, const float by = bmax[1] - bmin[1]; // Calculate the bounding box of the triangle. - vcopy(tmin, v0); - vcopy(tmax, v0); - vmin(tmin, v1); - vmin(tmin, v2); - vmax(tmax, v1); - vmax(tmax, v2); + rcVcopy(tmin, v0); + rcVcopy(tmax, v0); + rcVmin(tmin, v1); + rcVmin(tmin, v2); + rcVmax(tmax, v1); + rcVmax(tmax, v2); // If the triangle does not touch the bbox of the heightfield, skip the triagle. if (!overlapBounds(bmin, bmax, tmin, tmax)) @@ -223,9 +238,9 @@ static void rasterizeTri(const float* v0, const float* v1, const float* v2, for (int y = y0; y <= y1; ++y) { // Clip polygon to row. - vcopy(&in[0], v0); - vcopy(&in[1*3], v1); - vcopy(&in[2*3], v2); + rcVcopy(&in[0], v0); + rcVcopy(&in[1*3], v1); + rcVcopy(&in[2*3], v2); int nvrow = 3; const float cz = bmin[2] + y*cs; nvrow = clipPoly(in, nvrow, out, 0, 1, -cz); @@ -256,38 +271,78 @@ static void rasterizeTri(const float* v0, const float* v1, const float* v2, if (smax < 0.0f) continue; if (smin > by) continue; // Clamp the span to the heightfield bbox. - if (smin < 0.0f) smin = bmin[1]; - if (smax > by) smax = bmax[1]; + if (smin < 0.0f) smin = 0; + if (smax > by) smax = by; // Snap the span to the heightfield height grid. - unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, 0x7fff); - unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), 0, 0x7fff); + unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, RC_SPAN_MAX_HEIGHT); + unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), (int)ismin+1, RC_SPAN_MAX_HEIGHT); - addSpan(hf, x, y, ismin, ismax, flags); + addSpan(hf, x, y, ismin, ismax, area, flagMergeThr); } } } -void rcRasterizeTriangle(const float* v0, const float* v1, const float* v2, - unsigned char flags, rcHeightfield& solid) +/// @par +/// +/// No spans will be added if the triangle does not overlap the heightfield grid. +/// +/// @see rcHeightfield +void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, + const unsigned char area, rcHeightfield& solid, + const int flagMergeThr) { - rcTimeVal startTime = rcGetPerformanceTimer(); + rcAssert(ctx); + + ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); const float ics = 1.0f/solid.cs; const float ich = 1.0f/solid.ch; - rasterizeTri(v0, v1, v2, flags, solid, solid.bmin, solid.bmax, solid.cs, ics, ich); + rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + + ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); +} + +/// @par +/// +/// Spans will only be added for triangles that overlap the heightfield grid. +/// +/// @see rcHeightfield +void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, + const int* tris, const unsigned char* areas, const int nt, + rcHeightfield& solid, const int flagMergeThr) +{ + rcAssert(ctx); - rcTimeVal endTime = rcGetPerformanceTimer(); + ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); + + const float ics = 1.0f/solid.cs; + const float ich = 1.0f/solid.ch; + // Rasterize triangles. + for (int i = 0; i < nt; ++i) + { + const float* v0 = &verts[tris[i*3+0]*3]; + const float* v1 = &verts[tris[i*3+1]*3]; + const float* v2 = &verts[tris[i*3+2]*3]; + // Rasterize. + rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + } - if (rcGetBuildTimes()) - rcGetBuildTimes()->rasterizeTriangles += rcGetDeltaTimeUsec(startTime, endTime); + ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); } - -void rcRasterizeTriangles(const float* verts, int nv, - const int* tris, const unsigned char* flags, int nt, - rcHeightfield& solid) + +/// @par +/// +/// Spans will only be added for triangles that overlap the heightfield grid. +/// +/// @see rcHeightfield +void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, + const unsigned short* tris, const unsigned char* areas, const int nt, + rcHeightfield& solid, const int flagMergeThr) { - rcTimeVal startTime = rcGetPerformanceTimer(); + rcAssert(ctx); + + ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); const float ics = 1.0f/solid.cs; const float ich = 1.0f/solid.ch; @@ -298,11 +353,35 @@ void rcRasterizeTriangles(const float* verts, int nv, const float* v1 = &verts[tris[i*3+1]*3]; const float* v2 = &verts[tris[i*3+2]*3]; // Rasterize. - rasterizeTri(v0, v1, v2, flags[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich); + rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); } - rcTimeVal endTime = rcGetPerformanceTimer(); + ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); +} - if (rcGetBuildTimes()) - rcGetBuildTimes()->rasterizeTriangles += rcGetDeltaTimeUsec(startTime, endTime); +/// @par +/// +/// Spans will only be added for triangles that overlap the heightfield grid. +/// +/// @see rcHeightfield +void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, + rcHeightfield& solid, const int flagMergeThr) +{ + rcAssert(ctx); + + ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); + + const float ics = 1.0f/solid.cs; + const float ich = 1.0f/solid.ch; + // Rasterize triangles. + for (int i = 0; i < nt; ++i) + { + const float* v0 = &verts[(i*3+0)*3]; + const float* v1 = &verts[(i*3+1)*3]; + const float* v2 = &verts[(i*3+2)*3]; + // Rasterize. + rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + } + + ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); } |