error in rendering on simple shape

tgirod commented 7 years ago

System information

SolveSpace version: 2.3~7c1ca460

Operating system: archlinux

Expected behavior

Proper display

Actual behavior

ugly triangle

This ugly yellow triangle shouldn't be there. Note that it appears only when the four feet of the table are fully constrained on the corners.

Additional information

the file : table.zip

whitequark commented 7 years ago

Seems like another NURBS boolean bug. ~~Does this behavior disappear if you check "Force NURBS surfaces to triangle mesh"?~~ yes

whitequark commented 7 years ago

@Evil-Spirit This is interesting. It's a NURBS failure but it fails in polygon code:

couldn't find an ear! fail

How should we solve it?

phkahler commented 4 years ago

I would like to submit the following as possibly a simplified case of the same issue: polytest.zip

A similar triangulation error happens in the base sketch but not the extrusion.

Evil-Spirit commented 4 years ago

How should we solve it?

I think the current triangulator shouldn't fail on easy cases. So, probably need to reconsider epsilons.

phkahler commented 4 years ago

How should we solve it?

I think the current triangulator shouldn't fail on easy cases. So, probably need to reconsider epsilons.

@Evil-Spirit Agreed. I've been suspecting something like that. How precise are constraints enforced by the solver? Can the triangulation code rely on two coincident points being within RATPOLY_EPS distance? Some of the remaining NURBS issues appear to be related to coincident points being not coincident enough.

I was thinking of writing a pass over all vertexes prior to doing NURBS booleans and forcing then to be exactly coincident if within some tolerance to see if that helps, but that wouldn't help polytest.slvs since it's just a 2D sketch.

Evil-Spirit commented 4 years ago

@phkahler dealing with epsilons is fight we can't win. Just mathematics with all their robust predicates can fight.

phkahler commented 4 years ago

I now have 4 sketches, all 2D that exhibit triangulation errors similar in appearance to this. I found out why one was failing and made a somewhat special case fix. I now have a better fix that resolves all 4 planar sketch issues, but it still does not fix the problem with this table.

You can make the table work fine by going to SContour::IsEar() in the section here:

        if(p.EqualsExactly(tr.a)) continue;
        if(p.EqualsExactly(tr.b)) continue;
        if(p.EqualsExactly(tr.c)) continue;

Comment out the 2nd test. This will make all sorts of things fail, but it will fix the table in this issue. Like the comment says, the coincident points need to be allowed for bridges to work. For some reason the table sketch requires something not to be classified as an ear in order to work (presumably the big triangle that should not be present, but maybe not). It turns out there are some obvious situations where a non-ear might have a coincident point at B and be falsely declared an ear, and that's what is happening in all of my 2D sketch failures and the same fix works for all of them. I'm starting to suspect that the large triangle on the table is not misclassified, but something else in the triangulation is mis-classified and results in assumptions being violated during the remaining triangulation - I saw something similar in other cases, where the first wrong-ear caused the remaining polygon to become self-intersecting which led to another issue.

I have a way to watch the ear-triangulation step by step but it's a pain and will be harder with the 3D table which will output many polygons. It involves outputting the vertices and the order they are deleted and plotting that in a spreadsheet.

Not sure why I went down this rabbit hole but it's exhausting! I may join Patreon yet...

phkahler commented 4 years ago

So after writing that big note, I closed my text editor for the day. Opened the table and looked at it and the answer came to me. The large triangle is formed of 3 point A,B,C but apparently something is coincident with B - lets call that point b. What's happening is as triangles are clipped, the left and top rectangles collapse into pairs of anti-parallel coincident edges. So it goes A,B,C, x,y,z, c,b,a and then some more stuff. I had already tried clipping a bridge to nowhere A,B,a before so it must be a pair of bridges to somewhere. The thing is one of those triangles (A,B,C) or (c,b,a) is in the right order to be considered an ear. Normally the coincident edges would be OK but in this case not so much. So a one-liner to check that and say it's not an ear. This might cause issues if it ever comes up as a valid ear and gets rejected but I suspect there will always be another valid ear somewhere.

Lots of clean-ups left, but I really am closing the text editor for now. I should also zip up my 4 test cases and post them here for future reference.

solvespace / solvespace