← Back to branch summary

~rebel/horde3d/trunk

« back to all changes in this revision

Viewing changes to trunk/Tools/Dependencies/RecastNavigation/Recast/Source/RecastMeshDetail.cpp

  • Committer: felix
  • Date: 2015-07-07 12:57:07 UTC
  • Revision ID: svn-v4:5ce291ac-9df0-446f-9e4f-d57731c4dda7::1699
- Updated RecastNavigation to latest version and fixed multiple issues.
- Adapted GameDetourComponent, GameDetourCrowdComponent, DetourCrowdDemo and AAA accordingly.

Show diffs side-by-side

added added

removed removed

Lines of Context:
trunk/Tools/Dependencies/RecastNavigation/Recast/Source/RecastMeshDetail.cpp
56
56
}
57
57
 
58
58
inline float vcross2(const float* p1, const float* p2, const float* p3)
59
 
{ 
 
59
{
60
60
        const float u1 = p2[0] - p1[0];
61
61
        const float v1 = p2[2] - p1[2];
62
62
        const float u2 = p3[0] - p1[0];
68
68
                                                 float* c, float& r)
69
69
{
70
70
        static const float EPS = 1e-6f;
 
71
        // Calculate the circle relative to p1, to avoid some precision issues.
 
72
        const float v1[3] = {0,0,0};
 
73
        float v2[3], v3[3];
 
74
        rcVsub(v2, p2,p1);
 
75
        rcVsub(v3, p3,p1);
71
76
        
72
 
        const float cp = vcross2(p1, p2, p3);
 
77
        const float cp = vcross2(v1, v2, v3);
73
78
        if (fabsf(cp) > EPS)
74
79
        {
75
 
                const float p1Sq = vdot2(p1,p1);
76
 
                const float p2Sq = vdot2(p2,p2);
77
 
                const float p3Sq = vdot2(p3,p3);
78
 
                c[0] = (p1Sq*(p2[2]-p3[2]) + p2Sq*(p3[2]-p1[2]) + p3Sq*(p1[2]-p2[2])) / (2*cp);
79
 
                c[2] = (p1Sq*(p3[0]-p2[0]) + p2Sq*(p1[0]-p3[0]) + p3Sq*(p2[0]-p1[0])) / (2*cp);
80
 
                r = vdist2(c, p1);
 
80
                const float v1Sq = vdot2(v1,v1);
 
81
                const float v2Sq = vdot2(v2,v2);
 
82
                const float v3Sq = vdot2(v3,v3);
 
83
                c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp);
 
84
                c[1] = 0;
 
85
                c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp);
 
86
                r = vdist2(c, v1);
 
87
                rcVadd(c, c, p1);
81
88
                return true;
82
89
        }
83
 
 
84
 
        c[0] = p1[0];
85
 
        c[2] = p1[2];
 
90
        
 
91
        rcVcopy(c, p1);
86
92
        r = 0;
87
93
        return false;
88
94
}
93
99
        rcVsub(v0, c,a);
94
100
        rcVsub(v1, b,a);
95
101
        rcVsub(v2, p,a);
96
 
 
 
102
        
97
103
        const float dot00 = vdot2(v0, v0);
98
104
        const float dot01 = vdot2(v0, v1);
99
105
        const float dot02 = vdot2(v0, v2);
178
184
 
179
185
static float distToPoly(int nvert, const float* verts, const float* p)
180
186
{
181
 
 
 
187
        
182
188
        float dmin = FLT_MAX;
183
189
        int i, j, c = 0;
184
190
        for (i = 0, j = nvert-1; i < nvert; j = i++)
200
206
{
201
207
        int ix = (int)floorf(fx*ics + 0.01f);
202
208
        int iz = (int)floorf(fz*ics + 0.01f);
203
 
        ix = rcClamp(ix-hp.xmin, 0, hp.width);
204
 
        iz = rcClamp(iz-hp.ymin, 0, hp.height);
 
209
        ix = rcClamp(ix-hp.xmin, 0, hp.width - 1);
 
210
        iz = rcClamp(iz-hp.ymin, 0, hp.height - 1);
205
211
        unsigned short h = hp.data[ix+iz*hp.width];
206
212
        if (h == RC_UNSET_HEIGHT)
207
213
        {
216
222
                        if (nx < 0 || nz < 0 || nx >= hp.width || nz >= hp.height) continue;
217
223
                        const unsigned short nh = hp.data[nx+nz*hp.width];
218
224
                        if (nh == RC_UNSET_HEIGHT) continue;
219
 
 
 
225
                        
220
226
                        const float d = fabsf(nh*ch - fy);
221
227
                        if (d < dmin)
222
228
                        {
223
229
                                h = nh;
224
230
                                dmin = d;
225
231
                        }
226
 
                        
227
 
/*                      const float dx = (nx+0.5f)*cs - fx; 
228
 
                        const float dz = (nz+0.5f)*cs - fz;
229
 
                        const float d = dx*dx+dz*dz;
230
 
                        if (d < dmin)
231
 
                        {
232
 
                                h = nh;
233
 
                                dmin = d;
234
 
                        } */
235
232
                }
236
233
        }
237
234
        return h;
240
237
 
241
238
enum EdgeValues
242
239
{
243
 
        UNDEF = -1,
244
 
        HULL = -2,
 
240
        EV_UNDEF = -1,
 
241
        EV_HULL = -2,
245
242
};
246
243
 
247
244
static int findEdge(const int* edges, int nedges, int s, int t)
252
249
                if ((e[0] == s && e[1] == t) || (e[0] == t && e[1] == s))
253
250
                        return i;
254
251
        }
255
 
        return UNDEF;
 
252
        return EV_UNDEF;
256
253
}
257
254
 
258
255
static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r)
260
257
        if (nedges >= maxEdges)
261
258
        {
262
259
                ctx->log(RC_LOG_ERROR, "addEdge: Too many edges (%d/%d).", nedges, maxEdges);
263
 
                return UNDEF;
 
260
                return EV_UNDEF;
264
261
        }
265
262
        
266
 
        // Add edge if not already in the triangulation. 
 
263
        // Add edge if not already in the triangulation.
267
264
        int e = findEdge(edges, nedges, s, t);
268
 
        if (e == UNDEF)
 
265
        if (e == EV_UNDEF)
269
266
        {
270
267
                int* edge = &edges[nedges*4];
271
268
                edge[0] = s;
276
273
        }
277
274
        else
278
275
        {
279
 
                return UNDEF;
 
276
                return EV_UNDEF;
280
277
        }
281
278
}
282
279
 
283
280
static void updateLeftFace(int* e, int s, int t, int f)
284
281
{
285
 
        if (e[0] == s && e[1] == t && e[2] == UNDEF)
 
282
        if (e[0] == s && e[1] == t && e[2] == EV_UNDEF)
286
283
                e[2] = f;
287
 
        else if (e[1] == s && e[0] == t && e[3] == UNDEF)
 
284
        else if (e[1] == s && e[0] == t && e[3] == EV_UNDEF)
288
285
                e[3] = f;
289
 
}       
 
286
}
290
287
 
291
288
static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
292
289
{
298
295
                float a4 = a3 + a2 - a1;
299
296
                if (a3 * a4 < 0.0f)
300
297
                        return 1;
301
 
        }       
 
298
        }
302
299
        return 0;
303
300
}
304
301
 
320
317
static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e)
321
318
{
322
319
        static const float EPS = 1e-5f;
323
 
 
 
320
        
324
321
        int* edge = &edges[e*4];
325
322
        
326
323
        // Cache s and t.
327
324
        int s,t;
328
 
        if (edge[2] == UNDEF)
 
325
        if (edge[2] == EV_UNDEF)
329
326
        {
330
327
                s = edge[0];
331
328
                t = edge[1];
332
329
        }
333
 
        else if (edge[3] == UNDEF)
 
330
        else if (edge[3] == EV_UNDEF)
334
331
        {
335
332
                s = edge[1];
336
333
                t = edge[0];
337
334
        }
338
335
        else
339
336
        {
340
 
            // Edge already completed. 
 
337
            // Edge already completed.
341
338
            return;
342
339
        }
343
340
    
344
 
        // Find best point on left of edge. 
 
341
        // Find best point on left of edge.
345
342
        int pt = npts;
346
343
        float c[3] = {0,0,0};
347
344
        float r = -1;
385
382
                }
386
383
        }
387
384
        
388
 
        // Add new triangle or update edge info if s-t is on hull. 
 
385
        // Add new triangle or update edge info if s-t is on hull.
389
386
        if (pt < npts)
390
387
        {
391
 
                // Update face information of edge being completed. 
 
388
                // Update face information of edge being completed.
392
389
                updateLeftFace(&edges[e*4], s, t, nfaces);
393
390
                
394
 
                // Add new edge or update face info of old edge. 
 
391
                // Add new edge or update face info of old edge.
395
392
                e = findEdge(edges, nedges, pt, s);
396
 
                if (e == UNDEF)
397
 
                    addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, UNDEF);
 
393
                if (e == EV_UNDEF)
 
394
                    addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, EV_UNDEF);
398
395
                else
399
396
                    updateLeftFace(&edges[e*4], pt, s, nfaces);
400
397
                
401
 
                // Add new edge or update face info of old edge. 
 
398
                // Add new edge or update face info of old edge.
402
399
                e = findEdge(edges, nedges, t, pt);
403
 
                if (e == UNDEF)
404
 
                    addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, UNDEF);
 
400
                if (e == EV_UNDEF)
 
401
                    addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, EV_UNDEF);
405
402
                else
406
403
                    updateLeftFace(&edges[e*4], t, pt, nfaces);
407
404
                
409
406
        }
410
407
        else
411
408
        {
412
 
                updateLeftFace(&edges[e*4], s, t, HULL);
 
409
                updateLeftFace(&edges[e*4], s, t, EV_HULL);
413
410
        }
414
411
}
415
412
 
423
420
        edges.resize(maxEdges*4);
424
421
        
425
422
        for (int i = 0, j = nhull-1; i < nhull; j=i++)
426
 
                addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], HULL, UNDEF);
 
423
                addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], EV_HULL, EV_UNDEF);
427
424
        
428
425
        int currentEdge = 0;
429
426
        while (currentEdge < nedges)
430
427
        {
431
 
                if (edges[currentEdge*4+2] == UNDEF)
 
428
                if (edges[currentEdge*4+2] == EV_UNDEF)
432
429
                        completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
433
 
                if (edges[currentEdge*4+3] == UNDEF)
 
430
                if (edges[currentEdge*4+3] == EV_UNDEF)
434
431
                        completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
435
432
                currentEdge++;
436
433
        }
437
 
 
 
434
        
438
435
        // Create tris
439
436
        tris.resize(nfaces*4);
440
437
        for (int i = 0; i < nfaces*4; ++i)
489
486
        }
490
487
}
491
488
 
 
489
// Calculate minimum extend of the polygon.
 
490
static float polyMinExtent(const float* verts, const int nverts)
 
491
{
 
492
        float minDist = FLT_MAX;
 
493
        for (int i = 0; i < nverts; i++)
 
494
        {
 
495
                const int ni = (i+1) % nverts;
 
496
                const float* p1 = &verts[i*3];
 
497
                const float* p2 = &verts[ni*3];
 
498
                float maxEdgeDist = 0;
 
499
                for (int j = 0; j < nverts; j++)
 
500
                {
 
501
                        if (j == i || j == ni) continue;
 
502
                        float d = distancePtSeg2d(&verts[j*3], p1,p2);
 
503
                        maxEdgeDist = rcMax(maxEdgeDist, d);
 
504
                }
 
505
                minDist = rcMin(minDist, maxEdgeDist);
 
506
        }
 
507
        return rcSqrt(minDist);
 
508
}
 
509
 
 
510
// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
 
511
inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
 
512
inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
 
513
 
 
514
static void triangulateHull(const int nverts, const float* verts, const int nhull, const int* hull, rcIntArray& tris)
 
515
{
 
516
        int start = 0, left = 1, right = nhull-1;
 
517
        
 
518
        // Start from an ear with shortest perimeter.
 
519
        // This tends to favor well formed triangles as starting point.
 
520
        float dmin = 0;
 
521
        for (int i = 0; i < nhull; i++)
 
522
        {
 
523
                int pi = prev(i, nhull);
 
524
                int ni = next(i, nhull);
 
525
                const float* pv = &verts[hull[pi]*3];
 
526
                const float* cv = &verts[hull[i]*3];
 
527
                const float* nv = &verts[hull[ni]*3];
 
528
                const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv);
 
529
                if (d < dmin)
 
530
                {
 
531
                        start = i;
 
532
                        left = ni;
 
533
                        right = pi;
 
534
                        dmin = d;
 
535
                }
 
536
        }
 
537
        
 
538
        // Add first triangle
 
539
        tris.push(hull[start]);
 
540
        tris.push(hull[left]);
 
541
        tris.push(hull[right]);
 
542
        tris.push(0);
 
543
        
 
544
        // Triangulate the polygon by moving left or right,
 
545
        // depending on which triangle has shorter perimeter.
 
546
        // This heuristic was chose emprically, since it seems
 
547
        // handle tesselated straight edges well.
 
548
        while (next(left, nhull) != right)
 
549
        {
 
550
                // Check to see if se should advance left or right.
 
551
                int nleft = next(left, nhull);
 
552
                int nright = prev(right, nhull);
 
553
                
 
554
                const float* cvleft = &verts[hull[left]*3];
 
555
                const float* nvleft = &verts[hull[nleft]*3];
 
556
                const float* cvright = &verts[hull[right]*3];
 
557
                const float* nvright = &verts[hull[nright]*3];
 
558
                const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright);
 
559
                const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright);
 
560
                
 
561
                if (dleft < dright)
 
562
                {
 
563
                        tris.push(hull[left]);
 
564
                        tris.push(hull[nleft]);
 
565
                        tris.push(hull[right]);
 
566
                        tris.push(0);
 
567
                        left = nleft;
 
568
                }
 
569
                else
 
570
                {
 
571
                        tris.push(hull[left]);
 
572
                        tris.push(hull[nright]);
 
573
                        tris.push(hull[right]);
 
574
                        tris.push(0);
 
575
                        right = nright;
 
576
                }
 
577
        }
 
578
}
 
579
 
492
580
 
493
581
inline float getJitterX(const int i)
494
582
{
512
600
        float edge[(MAX_VERTS_PER_EDGE+1)*3];
513
601
        int hull[MAX_VERTS];
514
602
        int nhull = 0;
515
 
 
 
603
        
516
604
        nverts = 0;
517
 
 
 
605
        
518
606
        for (int i = 0; i < nin; ++i)
519
607
                rcVcopy(&verts[i*3], &in[i*3]);
520
608
        nverts = nin;
521
609
        
 
610
        edges.resize(0);
 
611
        tris.resize(0);
 
612
        
522
613
        const float cs = chf.cs;
523
614
        const float ics = 1.0f/cs;
524
615
        
 
616
        // Calculate minimum extents of the polygon based on input data.
 
617
        float minExtent = polyMinExtent(verts, nverts);
 
618
        
525
619
        // Tessellate outlines.
526
620
        // This is done in separate pass in order to ensure
527
621
        // seamless height values across the ply boundaries.
628
722
                }
629
723
        }
630
724
        
631
 
 
 
725
        // If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points.
 
726
        if (minExtent < sampleDist*2)
 
727
        {
 
728
                triangulateHull(nverts, verts, nhull, hull, tris);
 
729
                return true;
 
730
        }
 
731
        
632
732
        // Tessellate the base mesh.
633
 
        edges.resize(0);
634
 
        tris.resize(0);
635
 
 
636
 
        delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
 
733
        // We're using the triangulateHull instead of delaunayHull as it tends to
 
734
        // create a bit better triangulation for long thing triangles when there
 
735
        // are no internal points.
 
736
        triangulateHull(nverts, verts, nhull, hull, tris);
637
737
        
638
738
        if (tris.size() == 0)
639
739
        {
640
740
                // Could not triangulate the poly, make sure there is some valid data there.
641
 
                ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon, adding default data.");
642
 
                for (int i = 2; i < nverts; ++i)
643
 
                {
644
 
                        tris.push(0);
645
 
                        tris.push(i-1);
646
 
                        tris.push(i);
647
 
                        tris.push(0);
648
 
                }
 
741
                ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts);
649
742
                return true;
650
743
        }
651
 
 
 
744
        
652
745
        if (sampleDist > 0)
653
746
        {
654
747
                // Create sample locations in a grid.
681
774
                                samples.push(0); // Not added
682
775
                        }
683
776
                }
684
 
                                
 
777
                
685
778
                // Add the samples starting from the one that has the most
686
779
                // error. The procedure stops when all samples are added
687
780
                // or when the max error is within treshold.
690
783
                {
691
784
                        if (nverts >= MAX_VERTS)
692
785
                                break;
693
 
 
 
786
                        
694
787
                        // Find sample with most error.
695
788
                        float bestpt[3] = {0,0,0};
696
789
                        float bestd = 0;
728
821
                        edges.resize(0);
729
822
                        tris.resize(0);
730
823
                        delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
731
 
                }               
 
824
                }
732
825
        }
733
 
 
 
826
        
734
827
        const int ntris = tris.size()/4;
735
828
        if (ntris > MAX_TRIS)
736
829
        {
737
830
                tris.resize(MAX_TRIS*4);
738
831
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS);
739
832
        }
740
 
 
 
833
        
741
834
        return true;
742
835
}
743
836
 
744
 
static void getHeightData(const rcCompactHeightfield& chf,
745
 
                                                  const unsigned short* poly, const int npoly,
746
 
                                                  const unsigned short* verts, const int bs,
747
 
                                                  rcHeightPatch& hp, rcIntArray& stack)
 
837
 
 
838
static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 
839
                                                                                   const unsigned short* poly, const int npoly,
 
840
                                                                                   const unsigned short* verts, const int bs,
 
841
                                                                                   rcHeightPatch& hp, rcIntArray& stack)
748
842
{
749
843
        // Floodfill the heightfield to get 2D height data,
750
844
        // starting at vertex locations as seeds.
848
942
                                continue;
849
943
                        
850
944
                        const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir);
851
 
 
 
945
                        
852
946
                        int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width;
853
947
                        hp.data[idx] = 1;
854
948
                        
857
951
                        stack.push(ai);
858
952
                }
859
953
        }
860
 
 
 
954
        
861
955
        memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
862
 
 
 
956
        
863
957
        // Mark start locations.
864
958
        for (int i = 0; i < stack.size(); i += 3)
865
959
        {
869
963
                int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
870
964
                const rcCompactSpan& cs = chf.spans[ci];
871
965
                hp.data[idx] = cs.y;
872
 
        }
 
966
                
 
967
                // getHeightData seeds are given in coordinates with borders
 
968
                stack[i+0] += bs;
 
969
                stack[i+1] += bs;
 
970
        }
 
971
        
 
972
}
 
973
 
 
974
 
 
975
 
 
976
static void getHeightData(const rcCompactHeightfield& chf,
 
977
                                                  const unsigned short* poly, const int npoly,
 
978
                                                  const unsigned short* verts, const int bs,
 
979
                                                  rcHeightPatch& hp, rcIntArray& stack,
 
980
                                                  int region)
 
981
{
 
982
        // Note: Reads to the compact heightfield are offset by border size (bs)
 
983
        // since border size offset is already removed from the polymesh vertices.
 
984
        
 
985
        stack.resize(0);
 
986
        memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
 
987
        
 
988
        bool empty = true;
 
989
        
 
990
        // Copy the height from the same region, and mark region borders
 
991
        // as seed points to fill the rest.
 
992
        for (int hy = 0; hy < hp.height; hy++)
 
993
        {
 
994
                int y = hp.ymin + hy + bs;
 
995
                for (int hx = 0; hx < hp.width; hx++)
 
996
                {
 
997
                        int x = hp.xmin + hx + bs;
 
998
                        const rcCompactCell& c = chf.cells[x+y*chf.width];
 
999
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
1000
                        {
 
1001
                                const rcCompactSpan& s = chf.spans[i];
 
1002
                                if (s.reg == region)
 
1003
                                {
 
1004
                                        // Store height
 
1005
                                        hp.data[hx + hy*hp.width] = s.y;
 
1006
                                        empty = false;
 
1007
                                        
 
1008
                                        // If any of the neighbours is not in same region,
 
1009
                                        // add the current location as flood fill start
 
1010
                                        bool border = false;
 
1011
                                        for (int dir = 0; dir < 4; ++dir)
 
1012
                                        {
 
1013
                                                if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
 
1014
                                                {
 
1015
                                                        const int ax = x + rcGetDirOffsetX(dir);
 
1016
                                                        const int ay = y + rcGetDirOffsetY(dir);
 
1017
                                                        const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
 
1018
                                                        const rcCompactSpan& as = chf.spans[ai];
 
1019
                                                        if (as.reg != region)
 
1020
                                                        {
 
1021
                                                                border = true;
 
1022
                                                                break;
 
1023
                                                        }
 
1024
                                                }
 
1025
                                        }
 
1026
                                        if (border)
 
1027
                                        {
 
1028
                                                stack.push(x);
 
1029
                                                stack.push(y);
 
1030
                                                stack.push(i);
 
1031
                                        }
 
1032
                                        break;
 
1033
                                }
 
1034
                        }
 
1035
                }
 
1036
        }
 
1037
        
 
1038
        // if the polygon does not contian any points from the current region (rare, but happens)
 
1039
        // then use the cells closest to the polygon vertices as seeds to fill the height field
 
1040
        if (empty)
 
1041
                getHeightDataSeedsFromVertices(chf, poly, npoly, verts, bs, hp, stack);
873
1042
        
874
1043
        static const int RETRACT_SIZE = 256;
875
1044
        int head = 0;
887
1056
                                memmove(&stack[0], &stack[RETRACT_SIZE*3], sizeof(int)*(stack.size()-RETRACT_SIZE*3));
888
1057
                        stack.resize(stack.size()-RETRACT_SIZE*3);
889
1058
                }
890
 
 
 
1059
                
891
1060
                const rcCompactSpan& cs = chf.spans[ci];
892
1061
                for (int dir = 0; dir < 4; ++dir)
893
1062
                {
895
1064
                        
896
1065
                        const int ax = cx + rcGetDirOffsetX(dir);
897
1066
                        const int ay = cy + rcGetDirOffsetY(dir);
898
 
                        
899
 
                        if (ax < hp.xmin || ax >= (hp.xmin+hp.width) ||
900
 
                                ay < hp.ymin || ay >= (hp.ymin+hp.height))
901
 
                                continue;
902
 
                        
903
 
                        if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != RC_UNSET_HEIGHT)
904
 
                                continue;
905
 
                        
906
 
                        const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir);
907
 
                        
 
1067
                        const int hx = ax - hp.xmin - bs;
 
1068
                        const int hy = ay - hp.ymin - bs;
 
1069
                        
 
1070
                        if (hx < 0 || hx >= hp.width || hy < 0 || hy >= hp.height)
 
1071
                                continue;
 
1072
                        
 
1073
                        if (hp.data[hx + hy*hp.width] != RC_UNSET_HEIGHT)
 
1074
                                continue;
 
1075
                        
 
1076
                        const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir);
908
1077
                        const rcCompactSpan& as = chf.spans[ai];
909
 
                        int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width;
910
 
                        hp.data[idx] = as.y;
911
 
 
 
1078
                        
 
1079
                        hp.data[hx + hy*hp.width] = as.y;
 
1080
                        
912
1081
                        stack.push(ax);
913
1082
                        stack.push(ay);
914
1083
                        stack.push(ai);
915
1084
                }
916
1085
        }
917
 
        
918
1086
}
919
1087
 
920
1088
static unsigned char getEdgeFlags(const float* va, const float* vb,
924
1092
        static const float thrSqr = rcSqr(0.001f);
925
1093
        for (int i = 0, j = npoly-1; i < npoly; j=i++)
926
1094
        {
927
 
                if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && 
 
1095
                if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr &&
928
1096
                        distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr)
929
1097
                        return 1;
930
1098
        }
953
1121
        rcAssert(ctx);
954
1122
        
955
1123
        ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
956
 
 
 
1124
        
957
1125
        if (mesh.nverts == 0 || mesh.npolys == 0)
958
1126
                return true;
959
1127
        
1032
1200
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
1033
1201
                return false;
1034
1202
        }
1035
 
 
 
1203
        
1036
1204
        int vcap = nPolyVerts+nPolyVerts/2;
1037
1205
        int tcap = vcap*2;
1038
 
 
 
1206
        
1039
1207
        dmesh.nverts = 0;
1040
1208
        dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
1041
1209
        if (!dmesh.verts)
1044
1212
                return false;
1045
1213
        }
1046
1214
        dmesh.ntris = 0;
1047
 
        dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char*)*tcap*4, RC_ALLOC_PERM);
 
1215
        dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
1048
1216
        if (!dmesh.tris)
1049
1217
        {
1050
1218
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
1072
1240
                hp.ymin = bounds[i*4+2];
1073
1241
                hp.width = bounds[i*4+1]-bounds[i*4+0];
1074
1242
                hp.height = bounds[i*4+3]-bounds[i*4+2];
1075
 
                getHeightData(chf, p, npoly, mesh.verts, borderSize, hp, stack);
 
1243
                getHeightData(chf, p, npoly, mesh.verts, borderSize, hp, stack, mesh.regs[i]);
1076
1244
                
1077
1245
                // Build detail mesh.
1078
1246
                int nverts = 0;
1083
1251
                {
1084
1252
                        return false;
1085
1253
                }
1086
 
 
 
1254
                
1087
1255
                // Move detail verts to world space.
1088
1256
                for (int j = 0; j < nverts; ++j)
1089
1257
                {
1098
1266
                        poly[j*3+1] += orig[1];
1099
1267
                        poly[j*3+2] += orig[2];
1100
1268
                }
1101
 
        
 
1269
                
1102
1270
                // Store detail submesh.
1103
1271
                const int ntris = tris.size()/4;
1104
 
 
 
1272
                
1105
1273
                dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
1106
1274
                dmesh.meshes[i*4+1] = (unsigned int)nverts;
1107
1275
                dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
1108
 
                dmesh.meshes[i*4+3] = (unsigned int)ntris;              
 
1276
                dmesh.meshes[i*4+3] = (unsigned int)ntris;
1109
1277
                
1110
1278
                // Store vertices, allocate more memory if necessary.
1111
1279
                if (dmesh.nverts+nverts > vcap)
1112
1280
                {
1113
1281
                        while (dmesh.nverts+nverts > vcap)
1114
1282
                                vcap += 256;
1115
 
                                
 
1283
                        
1116
1284
                        float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
1117
1285
                        if (!newv)
1118
1286
                        {
1158
1326
                        dmesh.ntris++;
1159
1327
                }
1160
1328
        }
1161
 
                
 
1329
        
1162
1330
        ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
1163
 
 
 
1331
        
1164
1332
        return true;
1165
1333
}
1166
1334
 
1170
1338
        rcAssert(ctx);
1171
1339
        
1172
1340
        ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
1173
 
 
 
1341
        
1174
1342
        int maxVerts = 0;
1175
1343
        int maxTris = 0;
1176
1344
        int maxMeshes = 0;
1177
 
 
 
1345
        
1178
1346
        for (int i = 0; i < nmeshes; ++i)
1179
1347
        {
1180
1348
                if (!meshes[i]) continue;
1182
1350
                maxTris += meshes[i]->ntris;
1183
1351
                maxMeshes += meshes[i]->nmeshes;
1184
1352
        }
1185
 
 
 
1353
        
1186
1354
        mesh.nmeshes = 0;
1187
1355
        mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM);
1188
1356
        if (!mesh.meshes)
1190
1358
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4);
1191
1359
                return false;
1192
1360
        }
1193
 
 
 
1361
        
1194
1362
        mesh.ntris = 0;
1195
1363
        mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM);
1196
1364
        if (!mesh.tris)
1198
1366
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4);
1199
1367
                return false;
1200
1368
        }
1201
 
 
 
1369
        
1202
1370
        mesh.nverts = 0;
1203
1371
        mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM);
1204
1372
        if (!mesh.verts)
1222
1390
                        dst[3] = src[3];
1223
1391
                        mesh.nmeshes++;
1224
1392
                }
1225
 
                        
 
1393
                
1226
1394
                for (int k = 0; k < dm->nverts; ++k)
1227
1395
                {
1228
1396
                        rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]);
1237
1405
                        mesh.ntris++;
1238
1406
                }
1239
1407
        }
1240
 
 
 
1408
        
1241
1409
        ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
1242
1410
        
1243
1411
        return true;
1244
1412
}
1245