Infinite loop in Object3D.splitFaces() method

[VicEsquivel]

Hello @arakis,
I noticed that in the class Object3D, under the method splitFaces, specifically in line 329, there are some cases where having this else makes that the 2 for loops enter into an infinite state.

else
{
    i--;
    break;
}

I am checking what could be the cause, I understand that it could be somehow related to the faces of a particular mesh. But do you think you can orientate me into where this issue could be?

I understand from the code, that once it enters to the else, it goes back to a previous face1 value, but if nothing changes and it advances again to i++, it enters again into the else, and the loop begins. But how can I avoid this?

[VicEsquivel]

@arakis Sebastian, just complementing the issue, this appears when trying to do a getDifference() calculation.

BooleanModeller modeller = new BooleanModeller (solid1, solid2);            
Solid output = modeller.getDifference ();

Where solid2 is a cube primitive, and where solid1 is a plane, with this simple configuration:

I've seen that punching a hole in a plane with more vertices and triangles works fine, but with the most basic squared plane, it enters into this infinite loop.

[arakis]

If you have any suggestion how to solve this, i would be happy for a Pull Reqeust. Please keep in in mind to test your changes. It happens relative often, that a new code change solves an existing issue, but creates another one.

[VicEsquivel]

After testing my issue further. I noticed that the simple or complex mesh was not the cause of the loop itself. Neither do the code that was originally commented in the Java project: (because for some reason the code looped without increasing the getNumFaces() value, it got stuck forever in a small value of 32 faces)

//prevent from infinite loop (with a loss of faces...)
if (numFacesStart * 1000 < getNumFaces())
{
   Debug.Log("possible infinite loop situation: terminating faces split");
   return;
}

I am using this code in Unity, and the after reading this thread, #1 and contacting the original author Danilo Balby. I noticed that the source of the imprecision that lead into the infinite loop, in my particular case was:

I have a complex GameObject structure in my Unity scene, and everytime I wanted to make a Boolean difference between 2 objects where their global unity scale, (named: lossyScale) differs significantly, (for example 1 to 1000). And this calculation was left in hands of this API, it entered into the infinite loop state, because in the scale transformation between objects it originated this imprecision. (From here the name lossy)

So my solution was to simple set both objects involved in the Boolean subtraction as siblings (parent to the same game object), so that the scale calculation is handled by Unity, BEFORE this begins doing the splitFaces() method. After doing this adjustment, I have tested the exact same crash scenarios, multiple times and it has never presented the infinite loop so far.

Hope this helps someone.

[arakis]

Is there anything you could change in the repo code here, to prevent this in the future? In my opinion, the lib should work without any "workarrounds", and even if workarround are required, it should be handled by the lib itself.

But my guess is, maybe the lib has a fundamental problem by design - but this is just a guess. I just ported the code.

But again, my knowledge in Vector Math is nearly zero, i would not be able to solve that at my own. So any code contributions would be welcome.

[VicEsquivel]

@arakis I just found the core issue. And I think I know where to fix it in the repo. I can do the fix in the lib. But I will explain it here for anyone having this issue.
The TOL variable in the Segment.cs file, is a static value, and in my case, it was entering into this endless loop because somehow after splitting the faces, some really small fractions of a float were still intersecting and it began the endless loop. So I figured that if this TOLerance value, from the Segment.cs file could increment a tiny little bit every time it tries to detect if two segments intersect, this endless loop will be avoided ALWAYS.

Basically just incrementing it a little, something like this:

public class Segment
{
...
public static  double TOL = 1e-10;
public static  double TOL_INCREASER = 1e-9;//This value can be changed, from 1e-7 to 1e-12, works fine. (Faster the bigger the number is.)
...
public bool intersect(Segment segment)
        {
            TOL += TOL_INCREASER;
            if (endDist < segment.startDist + TOL || segment.endDist < startDist + TOL)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
...
}

And just simply reset the TOL value to 1e-10f every time a boolean operation is made.

[arakis]

First of all, thx for deep analyzing the problem. It may not the very best solution, seems it seems to make sense.

But it should definitifly not made as static variable.

The next problem is i see is:
if this is only a local problem (in a big mesh), TOL remain increased for all remaining segments. Is there any chance to find an implementation, that automatically will reset TOL smarter, or will use a "local increasing TOL" for the local problematic segments?