Floating point error causing artefacts.

[davidarayan]

Floating point error causing artefacts.

[SlimeQ]

I'm also getting this issue, randomly as I move my planes around

[SlimeQ]

This appears to happen when 1 or more points in a triangle fall ON the plane.

If the other point(s) are UP, the whole triangle should be considered UP.
If the other point(s) are DOWN, the whole triangle should be considered DOWN.

If 1 point falls on the plane, 1 is UP and 1 is DOWN, then the triangle should be split between the two hulls.

[SlimeQ]

Found a few reasons for this issue.

1: Plane.SideOf uses float.Epsilon to determine whether or not a point is ON the plane. This is something like 1e-45 which in this case may as well be zero. I changed this to use an epsilon of 0.0001f which makes the behavior much more stable.

2: In Slicer.Slice, if a triangle is not successfully split, only the first vert is considered when determining the side of the whole triangle. This causes big problems if that vert is ON, because then it's just added to the upperHull via this code:

                        SideOfPlane side = pl.SideOf(verts[i0]);
                        if (side == SideOfPlane.UP || side == SideOfPlane.ON) {
                            mesh.upperHull.Add(newTri);
                        } else {
                            mesh.lowerHull.Add(newTri);
                        }

Consider the following instead:

                        SideOfPlane sa = pl.SideOf(verts[i0]);
                        SideOfPlane sb = pl.SideOf(verts[i1]);
                        SideOfPlane sc = pl.SideOf(verts[i2]);

                        SideOfPlane side = SideOfPlane.ON;
                        if (sa != SideOfPlane.ON)
                        {
                            side = sa;
                        }
                        
                        if (sb != SideOfPlane.ON)
                        {
                            Debug.Assert(side == SideOfPlane.ON || side == sb);
                            side = sb;
                        }
                        
                        if (sc != SideOfPlane.ON)
                        {
                            Debug.Assert(side == SideOfPlane.ON || side == sc);
                            side = sc;
                        }
                        
                        if (side == SideOfPlane.UP || side == SideOfPlane.ON) {
                            mesh.upperHull.Add(newTri);
                        } else {
                            mesh.lowerHull.Add(newTri);
                        }

Additionally, we can and should short out Intersector.Intersect in these cases. Currently we're only shorting out if all 3 sides are equal or 2 or more verts are ON. This is my check:

            // detect cases where one point is on the plane and the other two are on the same side
            else if ((sa == SideOfPlane.ON && sb != SideOfPlane.ON && sb == sc) ||
                     (sb == SideOfPlane.ON && sa != SideOfPlane.ON && sa == sc) ||
                     (sc == SideOfPlane.ON && sa != SideOfPlane.ON && sa == sb)) {
                return;
            }

For what it's worth I'm still getting those asserts triggered sometimes. Currently looking into how that is possible.

@DavidArayan

[DavidArayan]

This is such a frustrating bug!

@SlimeQ if your solution above provides better and more consistent results, would you be able to do a pull request and i'll merge it with the current code.

I'm going to dig out some of my old collision detection books to see if there is anything about performing reliable comparison tests on 32bit or 64bit floating point numbers. would be keen to patch it up once and for all.

[SlimeQ]

@DavidArayan I was hoping to avoid making a pull request since I made some other changes as well and didn't want to sort it out myself... anybody should be able to implement the fix from the info I provided above but I'll see if I can find the time to make the pull request myself tomorrow.

Obviously if epsilon is too big you're going to run into issues with very small meshes, but I'm not really sure what the limits here are. 0.0001f works fine for my particular case but it's literally just a box that I'm slicing with a few planes. The box is a few units high (most of the time) and at least one plane intersects the corners of the box at all times. Before the epsilon fix I was getting crazy flashing as I resized the box, because of the rounding errors.

I mean think about it, if you're just checking x == 0 you have 0 bits of wiggle room. float.Epsilon by definition gives you 1 bit of wiggle room so if you're checking that -epsilon < x < epsilon you're only giving yourself a window of 3 bits which is still ridiculously strict. I've observed this type of rounding errors elsewhere in my projects and it seems like the margin of error is somewhere around 1e-5 which is surprisingly large.

The other part is just a logic change, I determined what was happening by drawing the triangles during the split operation like so:

public static void Intersect(Plane pl, Triangle tri, IntersectionResult result) {
...
            {
                Color aColor = Color.white;
                switch (sa)
                {
                    case SideOfPlane.ON:
                        aColor = Color.yellow;
                        break;
                    case SideOfPlane.UP:
                        aColor = Color.green;
                        break;
                    case SideOfPlane.DOWN:
                        aColor = Color.red;
                        break;
                }
                
                Debug.DrawLine(a, (a+b)/2, aColor);
                Debug.DrawLine(a, (a+c)/2, aColor);
                
                Color bColor = Color.white;
                switch (sb)
                {
                    case SideOfPlane.ON:
                        bColor = Color.yellow;
                        break;
                    case SideOfPlane.UP:
                        bColor = Color.green;
                        break;
                    case SideOfPlane.DOWN:
                        bColor = Color.red;
                        break;
                }
                
                Debug.DrawLine(b, (a+b)/2, bColor);
                Debug.DrawLine(b, (b+c)/2, bColor);
                
                Color cColor = Color.white;
                switch (sc)
                {
                    case SideOfPlane.ON:
                        cColor = Color.yellow;
                        break;
                    case SideOfPlane.UP:
                        cColor = Color.green;
                        break;
                    case SideOfPlane.DOWN:
                        cColor = Color.red;
                        break;
                }
                
                Debug.DrawLine(c, (c+b)/2, cColor);
                Debug.DrawLine(c, (c+a)/2, cColor);
            }
...
}

With the super tiny epsilon, I could see the coplanar points flipping between yellow (ON) and red (DOWN) as I moved them around in world space. After the epsilon change those ON corners stay yellow but always get added to the UP hull.

[SlimeQ]

Hi @DavidArayan, Just submitted a pull request for this fix.

I have not seen the asserts get triggered using this code, there was some issue with my short-out logic before.

You may want to experiment with smaller epsilon values, but this one worked for my purposes.

[DavidArayan]

Hello @SlimeQ

Thank you for your contribution! I've tested on my end and successfully merged the pull request, cheers!