hypar-io / Elements

The smallest useful BIM.
https://www.hypar.io
MIT License
349 stars 74 forks source link

Implement Intersects for ICurve and all subtypes #1008

Closed DmytroMuravskyi closed 1 year ago

DmytroMuravskyi commented 1 year ago

BACKGROUND:

DESCRIPTION:

FUTURE WORK:

TESTING:

REQUIRED:

COMMENTS:


This change is Reviewable

DmytroMuravskyi commented 1 year ago

@anthonie-kramer Added draft of implementation for ICurve.Intersects(ICurve). Now every function pair is presented by they can be added for sure. BaseCurve types: InfiniteLine, Circle and Ellipse - have function for intersecting with one another but not with other types. TrimmedCurve are the same but with domain check. All code is located in TrimmedCurve with only PointOnDomain implemented in each subclass. Line.PointOnLine function is logically collides with Line.PointOnDomain but they still little bit different as PointOnLine has includeEnds parameter. IndexedPolycurve has no new intersection math and just about intersecting individual pieces. Since there can be duplicating intersections at joint points between sub curves - extra filtering s added. Bezier is not yet implemented as it's most complex type. Equation.SolveIterative needs improvements - I've added basic implementation to show the full picture here. There are many existing Intersects functions that may overlap with new functons. Good example is Line.Intersects(Line, out Vector3) that is different by just out parameter from new Line.Intersects(Line, out List) This mean that just using l1.Intersects(l2, out var intersections) will not compile as it's ambiguous. This can be fixed by either changing the signature of new function tree to some non colliding name or allowing specific implementations have different signature from interface function. In line to line case there will be only one out point, although all other intersections have multiple of them.

Does Intersects need tolerance parameter added?

DmytroMuravskyi commented 1 year ago

I will add the documentation for sure as a next step.

Added implementation for Bezier. For Bezier-Line, Bezier-Circle, Bezier-Ellipse I used the iterative approach where I search where function of distance from iterated point to other object is zero. For Bezier-Bezier this approach is not working, so I used approach described in document mentioned in Bezier file - intersecting subdivided bounding boxes.

Both approaches have weak points I want to minimize right now: root can be possibly missed or 2 roots can be found around an intersection point.

Other issue I'm working on is resolving ambiguity between bool Intersects(Line l, out Vector3 result, bool infinite = false, bool includeEnds = false) old from Line bool Intersects(TrimmedCurve curve, out List results) where T : ICurve new from TrimmedCurve as l0.Intersects(l1, out var intersections) is always interpreted as old one and you must specify List. Maybe it's not a big problem.

DmytroMuravskyi commented 1 year ago

Missing arc intersections are fixed in the latest push. Is there something else missing in this PR?