Skip to content

Vertex split#765

Merged
phkahler merged 1 commit intosolvespace:masterfrom
phkahler:vertex-split
Oct 23, 2020
Merged

Vertex split#765
phkahler merged 1 commit intosolvespace:masterfrom
phkahler:vertex-split

Conversation

@phkahler
Copy link
Member

Two commits. One fixes the huge performance regression and is only a little slower than prior to the regression. 18.5 seconds compared to 193 seconds. Prior to the NURBS fix that same test took a bit over 15 seconds. That seems reasonable for adding more code in order to fix an issue. The second commit here adds OpenMP parallelism to the same part of the code and bring the test down to 11.x seconds.

@phkahler phkahler requested a review from ruevs October 21, 2020 20:42
@phkahler
Copy link
Member Author

Going through all of my NURBS regression tests, this fails with a file named wrong2.slvs

I'll try more variations. Going over every curve seemed to be the problem. Still appreciate feedback, this is looking kind of ulgy IMHO but still somewhat contained.

@ruevs
Copy link
Member

ruevs commented Oct 21, 2020

I need to debug this... not enough stack in my brain to think about it "on paper" (the phone screen) :-)

@phkahler phkahler added the NURBS label Oct 22, 2020
@phkahler
Copy link
Member Author

@ruevs If you look at a simplified test using triangle mesh:
unmerged
I think what's happening but not certain: The two surfaces from the colinear sketch lines get merged into one surface but I don't think the lines get merged, so it has 6 trim curves. Then when it does union with the large box, the long edge is split at the perpendicular surfaces of the small box, but not at the point where the 2 shorter trim curves meet, so then it fails to assemble everything correctly. Splitting a line at every curves end vertex caused the additional split, but since the 2 coincident rectangles merged into one, splitting at that surface corners is not enough. have not confirmed but it seems plausible.

I suspect going over all the curves was killing cache performance in addition to that being a complex test (nearest point to curve). Every curve was being checked against every curve and then every surface in the other shell. Maybe I'll try this surface bounding box test and then check the ends of that surface trim curves instead of the surface corners.

@phkahler phkahler linked an issue Oct 22, 2020 that may be closed by this pull request
@phkahler
Copy link
Member Author

Updated with MakeMaxMin, changed the comment, pulled the OMP out into a different PR.

Copy link
Member

@ruevs ruevs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

OK now I understand thoroughly what you are doing. And after you visual explanation above I think you are doing what you intend to with this code. And now I understand why it helps.

So apart from the few comments in this review I think it is fine to merge this.

Another important point I want to make. Jonathan's logic that, if this is needed, then surface curve intersection is not doing it's job still stands. I tried to dig a little, but did not get far. However I did look at this:

bool SSurface::LineEntirelyOutsideBbox(Vector a, Vector b, bool asSegment) const {

And I think somewhere we may have a bug in an equivalent (hypothetical) "CurveEntirelyOutsideBbox" logic. But I did not find it and am out of time for now.

@phkahler
Copy link
Member Author

@ruevs I changed it back to using curve end verticies. It's faster and fixes wrong2.slvs as well. Turns out the performance problem was solved by using bounding boxes prior to doing math like ClosestPointTo().

Should it stay two commits or should I squash them?

@phkahler phkahler force-pushed the vertex-split branch 2 times, most recently from b561d8d to 3f32918 Compare October 23, 2020 01:47
…ile still fixing the NURBS issues resolved by that commit with only modest speed penalty. The performance is significantly improved by using bounding box tests on curves prior to doing complex intersection testing.
@ruevs
Copy link
Member

ruevs commented Oct 23, 2020

@phkahler I apologize for the impertinence but I pushed a small cosmetic improvement to the code. NFC.

The performance is great.

@phkahler
Copy link
Member Author

@phkahler I apologize for the impertinence but I pushed a small cosmetic improvement to the code.

No problem at all. BTW how do you push changes to a PR like that?

Going to merge now ;-)

@phkahler phkahler merged commit 0f1ece2 into solvespace:master Oct 23, 2020
@ruevs
Copy link
Member

ruevs commented Oct 23, 2020

I think that if you check the box "allow maintainers to change" or something when creating the pull request then it gives rights to them to push to your branch.

So I have a remote for you:
phkahler https://github.com/phkahler/solvespace

So:
git fetch --all
git checkout phkahler vertex-split
change stuff
git add.... whatever
git commit --amend
git push --force

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Performance Regression

2 participants