Dragging my test model went from 125-130ms per frame or 7FPS, to around 90ms or 11FPS.

This seems to add a bug with this file and chord tolerance = 0.1. I'll have a look.
intersect_ct1.zip

@ruevs Could I convince you to have a look at this? The gist is this:

In the UvGridTriangulateInto (in triangulate.cpp) there is a grid created in U,V space over a surface. First the spacing is determined in U and V, then 2 nested loops generate quads between 4 points on the grid. If any of the polygon edges (piecewise linear trim curves) cross the perimeter of the quad it is rejected. Otherwise 2 triangles are created and 4 new edges are created in "holes" which get added to the polygon later (after all the holes are identified). Once all the holes are have been cut and covered in triangles the holes are merged into the polygon and then it calls UvTriangulateInto() which fills in the rest with triangles (That's all thats used for planar surfaces / no grid).

The inefficiency is that the quads (holes) create 4 edges each which are added to the holes polygon. Since quads are adjacent, any 2 adjacent quads will create a pair of edges running in opposite directions. After all the holes are cut a call is made to eliminate the redundant edges and that function has O(n^2) time which is really bad when there are 4UV edges. The fix here is to never create the redundant edges in the first place and eliminate that call.

I also made a shortcut by not making quads for the perimeter. It turns out those are rejected anyway because they have edges from the original perimeter.

Everything worked fine. Then I realized that quads that completely contain edges will not be rejected. even in the original code. The test model proved that, but also showed that the new implementation has problems. It's also much faster. The test model I uploaded is good to show the issue.

I was up way too late last night and couldn't figure out what's wrong.

I will look - when (as right now) I am not up way too late (finished the intersection) :-)
I looked at his beautiful and "simple" function (with math that I have totally "not" forgotten 20 years ago :-D ) back in December (I came to it from CullExtraneousEdges by way of boolean.cpp) and I could not fully figure it out. However it was clear enough that it is doing a lot of unnecessary work.
You on the other hand have done a great job describing what it does. So I will try again :-)

Yesterday I downloaded your model and played with it today while doing the intersection.

By the way - since you are looking at SPolygon::UvTriangulateInto I can offer you two very simple models that cause "couldn't find an ear! fail" (https://github.com/solvespace/solvespace/blob/master/src/srf/triangulate.cpp#L353)
I know SContour::UvTriangulateInto it is not exactly on topic, but this has been bugging me for at least 9 months and is the cause for some of the "NURBS" failures :-) For example #537
CouldntFindAnEar_NURBSTests.zip

@ruevs I found it. Turns out the line "hp.l.Clear();" is inside a loop when it should be outside. I had noticed that it works when the hole is connected to the outer ring of non-quads but it fails when the hole in the grid of quads should be creating a separate inner perimeter. Oops.

Thank you anyway! I will have a look at what you suggest tomorrow. This is an area I have not looked at much. I just learned what those ears are earlier today.

Great! And it works (fetched your branch, merged with intersection).
Roughly 2.8 times faster when switching from intersection to difference on my machine with your intersect_ct1.slvs and chord tolerance 0.01 (75s vs. 27s).

I will still read and understand your changes... tomorrow.

This came out of my looking at parallel triangulation. For #481 I wanted to be sure those functions were pure - not modifying shared data structures which won't work in parallel. I did some experiments disabling code that wouldn't be needed for simple curved surfaces and stumbled into a performance issue. So far this fix improves performance more than running it in parallel on 4 cores.

If lowering chord tolerance increases edge segments by N, and surface triangles by N^2, the removal of duplicate edges was taking N^4. It seemed best not to create redundant edges in the first place.

What I find odd is that now this isn't even close to being the performance bottleneck, at least on my simple test models.

If this is up to SS standards for the code I'll merge it after a little more testing.