NULL dereference crash in rcBuildContours() about recastnavigation HOT 14 CLOSED

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 >=.

from recastnavigation.

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.

from recastnavigation.

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]);
    }
}

from recastnavigation.

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,

from recastnavigation.

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.

from recastnavigation.

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.

from recastnavigation.

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.

from recastnavigation.

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.

from recastnavigation.

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.

from recastnavigation.

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.

from recastnavigation.

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

from recastnavigation.

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.

from recastnavigation.

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

1.7 simplification error:

1.8 simplification error:

from recastnavigation.

Yes, that's the one.

from recastnavigation.