Non-terminating while loop

[arcman77]

In an attempt to get around the large mesh issue I was talking about here I watered down the detail of the 3d geometry of the mesh and then split it into six parts resulting in this gltf file. That seems to have helped as I now get stuck further down the pipeline of loading the navmesh, here:

    /**
    * Returns true if the polygon is convex.
    *
    * @param {Boolean} ccw - Whether the winding order is CCW or not.
    * @return {Boolean} Whether this polygon is convex or not.
    */
    convex( ccw = true ) {

        let edge = this.edge;

        do {

            const v1 = edge.tail();
            const v2 = edge.head();
            const v3 = edge.next.head();

            if ( ccw ) {

                if ( leftOn( v1, v2, v3 ) === false )   return false;

            } else {

                if ( leftOn( v3, v2, v1 ) === false ) return false;

            }

            edge = edge.next;

        } while ( edge !== this.edge );

        return true;

    }

I put a deactivated debugger stopping point inside the do-while block, and let it run until it hit an endless loop cycle, then I was able to pause execution inside this code. From there I ran this snippet:

let arr = []
while (edge && edge.vis2 === undefined) {
    arr.push(edge)
    edge.vis2 = true
    arr.push(edge)
    edge = edge.next
}
console.log(arr.length)
console.log(arr.indexOf(this.edge))

The length of the array was 16, and arr.indexOf(this.edge) returns -1, so that proves that the while loop will never terminate.

[Mugen87]

Um, I think we have to find out how an anti-cyclic edge could actually appear in Polygon. It seems something goes wrong when the polygons are generated. So instead of fixing the issue in convex(), it might be better to avoid a degenerated geometry in the first place.

[arcman7]

Agreed. I was looking for a short term fix, and probably shouldn't have made a pr out of it. I linked you the gltf model in question, though. Let me know if a more built out example demonstrating the problem would be helpful; like a babylon js playground or something.

[arcman7]

So for starters, I suppose it would be helpful to know - did you anticipate weird jigsaw-puzzle like meshes such as this:

Like does the code expect the models to be of a certain format? I can see there are disjoint little "islands" of vertices that still are counted as a part of a bigger mesh they do not share any edges with and that would be my first guess as to what's causing issues. If there's any likely candidates in terms of files or classes that you know of I could start to look.

[Mugen87]

did you anticipate weird jigsaw-puzzle like meshes such as this:

TBH, no. This is not a typical geometry for a navigation mesh.

Like does the code expect the models to be of a certain format?

It's best if your nav mesh is a single geometry with a continuous surface. There should be no stuff like coplanar edges, duplicated vertices or disconnected faces.

[arcman7]

Okay, good to know! It wasn't totally clear to me from the navigation mesh examples that the gltf file needs a single continuous geometry. I probably missed that. I'll play around with merging the meshes and see if that timeout issue occurs again.