Self-intersection is not detected when intersecting triangles are on the same plane

Have some feature requests, feedback, cool stuff to share, or want to know where FreeCAD is going? This is the place.
Forum rules
Be nice to others! Read the FreeCAD code of conduct!
m3g1dd0
Posts: 7
Joined: Sat Aug 28, 2021 4:41 am

Self-intersection is not detected when intersecting triangles are on the same plane

Postby m3g1dd0 » Mon Aug 30, 2021 10:29 am

2D: co-planar

I use the following simple ASCII STL file as input for self-intersection mesh repair. It's basically five triangles on the same plane i.e. co-planar. Triangle `4` is intersecting with triangle `1`. FreeCAD cannot detect the self-intersection of facets `4` and `1`.

Image

Code: Select all

solid Simple
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 0.0e1 1.0e1
        vertex 0.0e1 +1.0e1 1.0e1
        vertex +1.0e1 0.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 +1.0e1 1.0e1
        vertex +1.0e1 0.0e1 1.0e1
        vertex 1.0e1 1.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 0.0e1 1.0e1
        vertex 0.0e1 +1.0e1 1.0e1
        vertex -1.0e1 1.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 0.0e1 1.0e1
        vertex +1.0e1 0.0e1 1.0e1
        vertex +1.0e1 -1.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.6e1 0.8e1 1.0e1
        vertex +1.6e1 0.8e1 1.0e1
        vertex +0.6e1 1.8e1 1.0e1
    endloop
endfacet
endsolid Simple

Image

3D

As another test, I use the following simple STL file. Just like previous STL, it consists of 5 facets but they are NOT on the same plane. In this case FreeCAD detects the intersection of facet `4` and `1` and deletes it properly.

Image

Code: Select all

solid Simple
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 0.0e1 1.0e1
        vertex 0.0e1 +1.0e1 1.0e1
        vertex +1.0e1 0.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 +1.0e1 1.0e1
        vertex +1.0e1 0.0e1 1.0e1
        vertex 1.0e1 1.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 0.0e1 1.0e1
        vertex 0.0e1 +1.0e1 1.0e1
        vertex -1.0e1 1.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.0e1 0.0e1 1.0e1
        vertex +1.0e1 0.0e1 1.0e1
        vertex +1.0e1 -1.0e1 1.0e1
    endloop
endfacet
facet normal 0.0e0 0.0e0 1.0e1
    outer loop
        vertex 0.6e1 0.8e1 1.2e1
        vertex +1.6e1 0.8e1 0.0e1
        vertex +0.6e1 1.8e1 0.0e1
    endloop
endfacet
endsolid Simple

Image

Question

The 2D case above is just like the 3D case with some minor differences in `Z` coordinates of some vertices.

I wonder why FreeCAD can detect self-intersection in 3D case? But not in 2D case?

FreeCAD info

Here is the content of `Help > About FreeCAD > "Copy to clipboard"`:

Code: Select all

OS: Windows 10 Version 2009
Word size of OS: 64-bit
Word size of FreeCAD: 64-bit
Version: 0.19.24291 (Git)
Build type: Release
Branch: releases/FreeCAD-0-19
Hash: 7b5e18a0759de778b74d3a5c17eba9cb815035ac
Python version: 3.8.6+
Qt version: 5.15.2
Coin version: 4.0.1
OCC version: 7.5.0
Locale: English/United States (en_US)
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby jnxd » Mon Aug 30, 2021 3:18 pm

m3g1dd0 wrote: Mon Aug 30, 2021 10:29 am
I wonder why FreeCAD can detect self-intersection in 3D case? But not in 2D case?
This is likely happening because of round-off errors while doing floating point operations. Basically the calculations must be giving some very small positive number instead of "<= 0" (around 10^-16 but may be larger depending on number of calculations involved) or something such. I'll take a look when I can.
m3g1dd0
Posts: 7
Joined: Sat Aug 28, 2021 4:41 am

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby m3g1dd0 » Tue Aug 31, 2021 7:53 am

I have uploaded a FreeCAD project file containing the test cases of 2D and 3D:

https://www.filemail.com/d/urakygvlflcecxq

Note that the link is valid for only 1 week!
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby jnxd » Tue Aug 31, 2021 3:35 pm

PR with fix: https://github.com/FreeCAD/FreeCAD/pull/5002. Note that the mesh somehow disappears now when the check is run, but comes back when "repair" is clicked. This is true for self-intersection and "all of the above" checks. If another test is run before repair, the mesh may not reappear.
User avatar
chennes
Posts: 1044
Joined: Fri Dec 23, 2016 3:38 pm
Location: Norman, OK, USA
Contact:

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby chennes » Tue Aug 31, 2021 7:34 pm

I poked at this weird mesh-hiding thing for a little while today. It seems to occur most often when also checking the normals -- and for me it doesn't happen when running "check all". I can't seem to find a consistent way of reproducing it -- any ideas?
Chris Hennes
Pioneer Library System
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby jnxd » Wed Sep 01, 2021 1:52 am

chennes wrote: Tue Aug 31, 2021 7:34 pm I poked at this weird mesh-hiding thing for a little while today. It seems to occur most often when also checking the normals -- and for me it doesn't happen when running "check all". I can't seem to find a consistent way of reproducing it -- any ideas?
Not sure if I can either. Sometimes i tried it and it didn't hide the mesh. Sometimes I "check all" and everything is hidden :|
User avatar
chennes
Posts: 1044
Joined: Fri Dec 23, 2016 3:38 pm
Location: Norman, OK, USA
Contact:

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby chennes » Wed Sep 01, 2021 4:13 am

Can you get it to happen without your patch? Are we sure it's related?
Chris Hennes
Pioneer Library System
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby jnxd » Wed Sep 01, 2021 6:01 am

chennes wrote: Wed Sep 01, 2021 4:13 am Can you get it to happen without your patch? Are we sure it's related?
Oddly, now I can't even reproduce it with the patch.
User avatar
chennes
Posts: 1044
Joined: Fri Dec 23, 2016 3:38 pm
Location: Norman, OK, USA
Contact:

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby chennes » Wed Sep 01, 2021 12:39 pm

I think this now falls officially into "Heisenbug" territory... :o
Chris Hennes
Pioneer Library System
jnxd
Posts: 239
Joined: Mon Mar 30, 2015 2:30 pm

Re: Self-intersection is not detected when intersecting triangles are on the same plane

Postby jnxd » Thu Sep 02, 2021 1:26 am

chennes wrote: Wed Sep 01, 2021 12:39 pm I think this now falls officially into "Heisenbug" territory... :o
Yes. Guess we just have to wait and watch. I can't really tell if there are any places where the modified function is used that also changes things.