NULL dereference crash in rcBuildContours()

[jackpoz]

I got a NULL dereference crash in mergeRegionHoles() called by rcBuildContours() using revision eacaa87

region.outline is NULL as shown by Visual Studio

callstack:

mmaps_generator.exe!mergeRegionHoles(rcContext * ctx, rcContourRegion & region) Line 751
mmaps_generator.exe!rcBuildContours(rcContext * ctx, rcCompactHeightfield & chf, const float maxError, const int maxEdgeLen, rcContourSet & cset, const int buildFlags) Line 1103

I didn't change any call to Recast to use the new features of a89bb84 .
I can reproduce the bug and I'm available to test any crashfix.

[memononen]

This should not happen (tm) :) Can you make this happen in RecastDemo and can you provide a test level?

If not, can you add this after the qsort:

if (!region.outline)
{
    printf(“Region without outline!\n”);
    for (int i = 0; i < region.nholes; i++)
    {
        printf(“ - Hole %d\n”, i);
        rcContour* hole = region.holes[i].contour;
        for (int j = 0; j < hole->nverts; i++)
            printf(“%d, %d, %d,\n”, hole->verts[j*4+0],hole->verts[j*4+1],hole->verts[j*4+2]);
    }
    return;
}

The correct fix is probably this, but I'd like to verify with the data:

                // Positively would contours are outlines, negative holes.
                if (winding[i] >= 0)

Change > to >=.

[jackpoz]

Region without outline!
Hole 0
2, 1419, 80,
4, 1420, 80,
6, 1422, 42,
5, 1421, 75,

Even with >= it still prints that log .

Reproducing it with RecastDemo will probably take a while, meanwhile here are more details I found debugging it in rcBuildContours():

• cset.nconts = 10
• winding = {0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0xff, 0x01};
• chf.maxRegions = 15 so nregions = 16
• 9th winding has a hole and it corresponds to 15th region
• the outline of 15th region is never set, I don't see either a outline = in the holes handling code before mergeRegionHoles() calls.

Update:
https://github.com/memononen/recastnavigation/blob/master/Recast/Source/RecastContour.cpp#L1099 reg.holes[reg.nholes++].contour = &cont; is actually making https://github.com/memononen/recastnavigation/blob/master/Recast/Source/RecastContour.cpp#L1091 regions[i].nholes = 0; useless, setting nholes back to a number != 0 , while leaving outline to NULL.

[memononen]

The code around 1091 allocating distributing space for the holes, and the code around 1099 is then assigning values to the holes.

The outline you printed looks ok, let's print some more values. Can you put this the line before // Finally merge each regions holes into the outline., let's dump 'em all:

bool failure = false;
for (int i = 0; i < nregions; i++)
    if (!regions[i].outline)
        failure = true;
if (failure)
{
    // Dump all countours
    for (int i = 0; i < cset.nconts; ++i)
    {
        rcContour& cont = cset.conts[i];
        int area = calcAreaOfPolygon2D(cont.verts, cont.nverts);
        printf(“Contour %d: reg=%d area=%d\n”, i, cont.reg, area);
            for (int j = 0; j < cont.nverts; i++)
                printf(“%d, %d, %d,\n”, contverts[j*4+0],cont.verts[j*4+1],cont.verts[j*4+2]);
    }
}

[jackpoz]

Contour 8 Region 14 is the one with a hole

Contour 0: reg = 6 area = 4194
0, 239, 80,
80, 241, 80,
80, 237, 31,
72, 238, 42,
59, 235, 46,
55, 233, 42,
42, 230, 42,
34, 228, 32,
24, 227, 33,
8, 227, 28,
8, 226, 21,
13, 226, 16,
21, 226, 14,
24, 226, 9,
37, 227, 13,
46, 227, 5,
50, 228, 5,
49, 227, 0,
0, 225, 0,
Contour 1: reg = 7 area = 3984
0, 1482, 80,
80, 1481, 80,
80, 1481, 36,
72, 1481, 41,
50, 1481, 40,
44, 1481, 45,
38, 1481, 44,
15, 1481, 18,
17, 1481, 0,
0, 1482, 0,
Contour 2: reg = 5 area = 4519
0, 1746, 16,
38, 1812, 74,
44, 1816, 79,
48, 1816, 80,
80, 1752, 47,
80, 1717, 0,
0, 1732, 0,
Contour 3: reg = 10 area = 1287
80, 235, 25,
80, 228, 3,
72, 229, 4,
70, 228, 0,
55, 228, 0,
55, 229, 9,
44, 228, 14,
42, 228, 19,
33, 227, 20,
26, 227, 16,
14, 227, 25,
21, 227, 23,
25, 227, 27,
36, 228, 26,
46, 230, 37,
56, 232, 32,
60, 234, 40,
72, 236, 34,
76, 235, 25,
Contour 4: reg = 11 area = 813
80, 292, 20,
80, 289, 6,
63, 288, 1,
54, 300, 18,
32, 293, 17,
23, 289, 23,
33, 293, 24,
54, 301, 33,
Contour 5: reg = 12 area = 25
0, 1230, 34,
5, 1232, 27,
0, 1232, 24,
Contour 6: reg = 8 area = 2487
0, 1230, 57,
0, 1229, 80,
80, 1230, 80,
80, 1231, 32,
41, 1230, 56,
38, 1231, 56,
26, 1231, 41,
22, 1231, 40,
17, 1229, 46,
20, 1229, 54,
15, 1229, 64,
10, 1229, 64,
Contour 7: reg = 9 area = 1154
0, 1850, 80,
52, 1840, 80,
50, 1838, 76,
0, 1841, 38,
Contour 8: reg = 14 area = -8
2, 1419, 80,
4, 1420, 80,
6, 1422, 42,
5, 1421, 75,
Contour 9: reg = 13 area = 78
64, 1821, 80,
70, 1817, 80,
80, 1796, 70,
80, 1791, 64,
Region without outline!
Hole 0
2, 1419, 80,
4, 1420, 80,
6, 1422, 42,
5, 1421, 75,

[memononen]

The areas look ok, but that one. Can you post your build settings?

Also If you can post a screenshot of the the location where the navmesh is from with compact heighfield region debug draw, that would help me a lot.

[jackpoz]

I added the settings to RecastDemo and was able to reproduce it, you can find the branch with a test case at https://github.com/jackpoz/recastnavigation/tree/issue38

The only custom changes are some x64 fixes. Load the Tile Mesh sample and then the map5712525.obj mesh, tick the TrinityCore Configs custom check and then Build all tiles. The bounding box is actually a section of the whole mesh and that's how it's supposed to be.

[memononen]

Thanks for setting up a test case, I'll take a look at it.

Quick note about settings:

m_agentHeight = 6 * m_cellSize;
m_agentMaxClimb = 8 * m_cellSize;

Agent climb must be less than agent height or you'll get invalid navmesh in some cases.

[jackpoz]

I had to set those settings to allow to "jump" over high fences by walking over them, most of the meshes are in open space anyway. Thank you tho for taking a look at those configs.

[memononen]

The crash is fixed now, but you'll get a warning when building your level. The problem comes from contour simplification. You are using error of 1.8, which can sometimes be too eager to cut corners and that creates overlapping contour. I suggest to make the error lower, like 1.5.

[jackpoz]

Looks like 1.787f is low enough to avoid the crash, that high simplification value made some complex meshes work much better. I'll lower it down and see how it works, thank you for the feedback.

[jackpoz]

what are the effects tho of skipped region ? I can't see any particular visible difference in recast demo

[memononen]

The change I made basically just does not try to merge the contours if there is no outline. The triangulator then will try to triangulate the contour, and may succeed to do that for a region (there will also be error spit out when this happens). So all in all, the process tries to create as many triangles as it can.

You can see this effect at the backside of the dome in your test case. There is small sliver navmesh piece on the rims of the dome (hard to exaplain), half of it wil be missing.

[jackpoz]

I guess you are referring to tile 19,22 , in particular this section:

1.7 simplification error:

1.8 simplification error:

[memononen]

Yes, that's the one.