RecastContour.ccp : removeDegenerateSegments() : Contour vertex list left in invalid state.

This potential defect found while reviewing code.

If my evaluation of the code and impact is correct, problems in navmesh
generation will only occur if a single contour contains more than one
degenerate segment.  Otherwise the defect will be hidden.

Validated to still exist in SVN source as of this date.

Found in:

RecastContour.ccp : removeDegenerateSegments()

When a degenerate segment is discovered a vertex is removed using the
following code:

(simplified is an rcIntArray object that contains vertices in the following
format:  (x, y, z, id))

----------------------------------

// Degenerate segment, remove.
for (int j = i; j < simplified.size()/4-1; ++j)
{
    simplified[j*4+0] = simplified[(j+1)*4+0];
    simplified[j*4+1] = simplified[(j+1)*4+1];
    simplified[j*4+2] = simplified[(j+1)*4+2];
    simplified[j*4+3] = simplified[(j+1)*4+3];
}
simplified.pop();

----------------------------------

Only a single pop() is performed, reducing the simplified.size() by 1. 
Aren't 4 pops needed in order to indicate removal of the entire last vertex?

I'm not a C++ guy so I had to test in Java. Sorry.

Test Results:

Input test data (2 degenerate segments):

Vert Count: 5
0, 0, 0, 91
1, 2, 3, 92
1, 2, 3, 93
1, 2, 4, 94
1, 2, 4, 95

Expected data after performing removeDegenerateSegments() operation:

(Expect 2 degenerate segments to be culled.)

Vert Count: 3
0, 0, 0, 91
1, 2, 3, 93
1, 2, 4, 95

Actual data (code as is):

Vert Count: 4
0, 0, 0, 91
1, 2, 3, 93
1, 2, 4, 95
1, 2, 4, 95 <- Invalid vert.

Actual data (code updated to include 4 calls to pop())

Vert Count: 3
0, 0, 0, 91
1, 2, 3, 93
1, 2, 4, 95

Original issue reported on code.google.com by steve...@gmail.com on 9 Nov 2009 at 5:13

swordlegend / recastnavigation

RecastContour.ccp : removeDegenerateSegments() : Contour vertex list left in invalid state. #16