New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Invalid BSPTree created during union #41

Closed
jerdmanGH opened this Issue Jul 13, 2018 · 5 comments

Comments

Projects
None yet
2 participants
@jerdmanGH
Copy link

jerdmanGH commented Jul 13, 2018

It is possible to create an invalid Sphere2D BSPTree containing a node with a null cut and attribute using the RegionFactory union method.

I have been able to trace this down to the SubCircle split method. The returned SplitSubHyperplane contains one side of the split as null but the BSPTree split method assumes that both sides will return non-null values.

The code below can be used to reproduce this issue. Note that a lowering the provided tolerance value will "solve" the issue but this is an edge case that should still be addressed.

        RegionFactory<Sphere2D> regionFactory = new RegionFactory<>();
        S2Point[] s2pA = new S2Point[]{
                new S2Point(new Vector3D(0.2122954606, -0.629606302, 0.7473463333)),
                new S2Point(new Vector3D(0.2120220248, -0.6296445493, 0.747391733)),
                new S2Point(new Vector3D(0.2119838016, -0.6298173178, 0.7472569934)),
                new S2Point(new Vector3D(0.2122571927, -0.6297790738, 0.7472116182))};

        S2Point[] s2pB = new S2Point[]{
                new S2Point(new Vector3D(0.2120291561, -0.629952069, 0.7471305292)),
                new S2Point(new Vector3D(0.2123026002, -0.6299138005, 0.7470851423)),
                new S2Point(new Vector3D(0.2123408927, -0.6297410403, 0.7472198923)),
                new S2Point(new Vector3D(0.2120674039, -0.6297793122, 0.7472653037))};

        final SphericalPolygonsSet spsA = new SphericalPolygonsSet(0.0001, s2pA);
        final SphericalPolygonsSet spsB = new SphericalPolygonsSet(0.0001, s2pB);
        SphericalPolygonsSet invalidSPS = (SphericalPolygonsSet) regionFactory.union(spsA, spsB);
        //Causes a NullPointerException
        System.out.println(invalidSPS.getSize());

maisonobe added a commit that referenced this issue Jul 15, 2018

Fixed a corner case in BSPTree split.
Thanks to jerdmanGH for spotting the issue.
Fixes GitHub #41.
@maisonobe

This comment has been minimized.

Copy link
Contributor

maisonobe commented Jul 15, 2018

The issue should be fixed in the git repository.
Note that as the spherical polygons in the test case are very small with respect to the tolerance
(or rather the tolerance is very large with respect to the spherical polygons), the result of the union
operation is now a consistent BSP tree, but is not very accurate. As several points from the two
polygons are too close to each other, they are considered equal, which distorts the result.
This is considered normal.
I agree that the consistency of the tree needed to be fixed.

Thanks for the report, for the analysis, and for the simple test case!

@maisonobe maisonobe closed this Jul 15, 2018

@jerdmanGH

This comment has been minimized.

Copy link

jerdmanGH commented Jul 23, 2018

Thanks for the quick turnaround. Is there a planned release date for 1.4?

@maisonobe

This comment has been minimized.

Copy link
Contributor

maisonobe commented Jul 23, 2018

No release date planned for now, but we could do that.
Do you need a release soon or would a release in the next few months suit your needs?

@jerdmanGH

This comment has been minimized.

Copy link

jerdmanGH commented Jul 23, 2018

I've been playing around with tolerance values to try to determine if there is an "ideal" setting that will fit my use case but keep running into issues. The latest is a "this should never happen" exception that can be reproduced using the code below. I can submit this as a new issue but it may already be fixed by your previous commit. I'm going to put in a check for minimum allowable size for shapes to see if that gets me past this. I'm hopeful that I can find a workaround without the need for an accelerated release.

        S2Point[] s2pA = new S2Point[]{
                new S2Point(new Vector3D(0.1504230736114679, -0.6603084987333554, 0.7357754993377947)),
                new S2Point(new Vector3D(0.15011191112224423, -0.6603400871954631, 0.7358106980616113)),
                new S2Point(new Vector3D(0.15008035620222715, -0.6605195692153062, 0.7356560238085725)),
                new S2Point(new Vector3D(0.1503914563063968, -0.6604879854490165, 0.7356208472763267))
        };
        final SphericalPolygonsSet spsA = new SphericalPolygonsSet(1E-100, s2pA);
        spsA.getSize();
@maisonobe

This comment has been minimized.

Copy link
Contributor

maisonobe commented Jul 23, 2018

Please open a new issue. It is not fixed by the previous commit.

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