We are working on upgrading one of our Rhino plugins from Rhino 7 to Rhino 8. We came across the following bug with CurveCurve intersections for circles and arcs.
If you run the code below on Rhino 7 the intersections for the circle and arc are the same. It correctly shows that the circle completely overlaps the arc. In Rhino 8 for the second call, with the arc as the first parameter and curve as the second parameter, it return an incorrect overlap.
var tolerance = 1e-3;
var circle = new Circle(new Point3d(0, 0, 0), 1);
var arc1 = new Arc(circle, new Interval(0, RhinoMath.ToRadians(45)));
var circleCurve = new ArcCurve(circle).ToNurbsCurve();
var arc1Curve = new ArcCurve(arc1).ToNurbsCurve();
var intersections = Intersection.CurveCurve(circleCurve, arc1Curve, tolerance, tolerance);
var intersection1 = intersections[0];
var interval1 = intersection1.OverlapA;
intersections = Intersection.CurveCurve(arc1Curve, circleCurve, tolerance, tolerance);
var intersection2 = intersections[0];
var interval2 = intersection2.OverlapA;
The code is mainly used for filtering out duplicate curves for exports out of rhino. So running it on any list of curves in reverse could be used as a temporary solution since it would only impact performance. Still, it is an underlying bug that probably impacts other curve intersections as well.
Let me know if anyone has a fix or workaround for this.
EDIT… did an error in my script - this is the script that reproduces the error in script editor:
// #! csharp
using System;
using Rhino;
using Rhino.Geometry;
using Rhino.Geometry.Intersect;
using Rhino.DocObjects;
double tolerance = 1e-3;
var circle = new Circle(new Point3d(0, 0, 0), 1);
var arc1 = new Arc(circle, new Interval(0, RhinoMath.ToRadians(45)));
var circleCurve = new ArcCurve(circle);//.ToNurbsCurve();
var arc1Curve = new ArcCurve(arc1);//.ToNurbsCurve();
Rhino.RhinoDoc.ActiveDoc.Objects.Add(circleCurve);
Rhino.RhinoDoc.ActiveDoc.Objects.Add(arc1Curve);
var intersections = Intersection.CurveCurve(circleCurve, arc1Curve, tolerance, tolerance);
var intersection1 = intersections[0];
var interval1 = intersection1.OverlapA;
intersections = Intersection.CurveCurve(arc1Curve, circleCurve, tolerance, tolerance);
var intersection2 = intersections[0];
var interval2 = intersection2.OverlapA;
Curve sub1 = circleCurve.Trim(interval1);
Rhino.RhinoDoc.ActiveDoc.Objects.Add(
sub1,
new Rhino.DocObjects.ObjectAttributes()
{
ObjectColor = System.Drawing.Color.DarkGreen,
ColorSource = ObjectColorSource.ColorFromObject,
Name = "sub1"
});
Curve sub2 = arc1Curve.Trim(interval2);
Rhino.RhinoDoc.ActiveDoc.Objects.Add(
sub2,
new Rhino.DocObjects.ObjectAttributes()
{
ObjectColor = System.Drawing.Color.DarkRed,
ColorSource = ObjectColorSource.ColorFromObject,
Name = "sub2"
});
and a screenshot that shows what s wrong - moved the curves…
black the circle and the overlapping arc
green - the first intersection with correct / expected result
red - the second reversed intersection order - unexpected / wrong
Thanks for taking a look. In your code you are adding sub1 twice. The corrected code below shows that the intervals are not the same, so the resulting trimmed curves are different.
var tolerance = 1e-3;
var circle = new Circle(new Point3d(0, 0, 0), 1);
var arc1 = new Arc(circle, new Interval(0, RhinoMath.ToRadians(45)));
var circleCurve = new ArcCurve(circle).ToNurbsCurve();
var arc1Curve = new ArcCurve(arc1).ToNurbsCurve();
var intersections = Intersection.CurveCurve(circleCurve, arc1Curve, tolerance, tolerance);
var intersection1 = intersections[0];
var interval1 = intersection1.OverlapA;
intersections = Intersection.CurveCurve(arc1Curve, circleCurve, tolerance, tolerance);
var intersection2 = intersections[0];
var interval2 = intersection2.OverlapA;
Curve sub1 = circleCurve.Trim(interval1);
var rhinoDoc = RhinoDoc.ActiveDoc;
rhinoDoc.Objects.Add(
sub1,
new Rhino.DocObjects.ObjectAttributes()
{
ObjectColor = System.Drawing.Color.DarkGreen,
ColorSource = ObjectColorSource.ColorFromObject,
Name = "sub1"
});
Curve sub2 = arc1Curve.Trim(interval2);
rhinoDoc.Objects.Add(
sub2,
new Rhino.DocObjects.ObjectAttributes()
{
ObjectColor = System.Drawing.Color.DarkRed,
ColorSource = ObjectColorSource.ColorFromObject,
Name = "sub2"
});
I’m working bit by bit on improving the intersectors but this is a big project that will take some time.
I’m interested in your bug, though, because from where I’m standing it’s not clear to me to what extent we’ll be able to make “overlaps” work in the way that you’re trying to use them. Getting sane overlaps is much harder than getting sane intersections. It is a little unclear what should even be meant by an overlap in the first place (mathematically speaking…).
That said, since you’re interested in detecting identical curves, you might try CrvDeviation. Although this isn’t spelled out explicitly in the documentation, what this function is attempting to do is compute something called the Hausdorff distance between two curves. If the Hausdorff distance is small, you can be assured that the curves are close to the same—this also accounts for differing parametrizations, which can be very helpful.
If CrvDeviation doesn’t work for you either, I’d be interested in hearing about it, since I’m building up some tools internally for computing this kind of Hausdorff distance to use in regression testing. Somewhere on my todo list is making sure CrvDeviation works well, too…
Thanks for the prompt reply. I can see how getting reliable overlaps are hard with curves in a general sense. It is a bit simpler in my example code with the curves being known parametric objects like arc and circles.
We’ve known for a while that CurveCurve intersections have some unexpected behaviour and consequently started adding unit tests for intersection and overlap scenarios that we had to write custom code for. Hence we caught this one.
I’ll see if we can use CurveDeviation. I’m assuming it uses Curve.GetDistanceBetweenCurves under the hood.
besides all theory - as intersections are everywhere - from trimming to fillets to constructing nice transitions.
Maybe several strategies should run in parallel (threads) - besides a pure mathematic approach, a second approximate with polylines and meshes, check endpoints, midpoints, quads, …
this will allow to evaluate the result and check if both approaches come to comparable results - and maybe add some fine-tuning if the results are not comparable within 1/10 of document tolerance…
i also think there should be some priority:
endpoint vs point on crv
midpoint vs point on crv
corner vs edge
edge vs point on surface
…
@sfp the ugly boolean Union bug is also your business ?
happy coding and thanks for your effort - kind regards - tom
maybe i have not drunk enough coffee today but this one is to much for my brain now
It looks gross, but it’s pretty intuitive geometrically.
Take these two straight line segments. It’s easier to grok the “directed” Hausdorff distance from one curve to the other first.
Two straight line segments. Consider the “maximum minimum distance” from the red line segment to the blue one. Since the lines are parallel they are all the same, and the length of any one of those black arrows is “the directed Hausdorff distance from the red line to the blue line”.
The reason for this strange construction is that you could have two curves which overlap exactly but which can’t be compared pointwise because they have completely different parametrizations.
@SK-Structurecraft It looks to me like you aren’t trying to find if the circle and arc are “the same”, but just whether one of them overlaps the other, even if it doesn’t have the full extent of the other (one curve is roughly a subset of the other).
If this is right, read my previous reply to @Tom_P about the “directed Hausdorff distance”. CrvDeviation is supposed to check whether your two curves are exactly the same by computing the (undirected) Hausdorff distance. So it actually may not be exactly what you want.
Either way, if you are comfortable programming, it should be easy to hack together a rough version of this “directed Hausdorff distance”. Something like this:
T = a grid of equally spaced parameters for curve 1
max_min_dist = 0
for t in T:
x = curve 1 evaluated at parameter t
y = closest point to x on curve 2
min_dist = dist(x, y)
max_min_dist = max(max_min_dist, min_dist)
If max_min_dist is small, curve 1 approximately overlaps curve 2.
The finer you make the initial grid of samples on your first curve, the more accurate max_min_dist will be.
@sfp Thanks for the details on the Hausdorff distance. Had a go at using it for our purposes and it seems to address the circle-arc bug well. We ran it through our unit tests and there were no side-effects so we’ll use that as another tool in the toolbox moving forward for removing duplicate curves. It does have some performance tradeoffs, so you want to use this I would recommend simpler filtering methods to be used before using this or Intersection.CurveCurve.
For anyone interested, here is the code for using it.
/// <summary>
/// Removed any curves that are identical using <see cref="Curve.GetDistanceBetweenCurves"/>.
/// It calculates the Hausdorff distance between two curves.
/// </summary>
private static List<Curve> RemoveCurves(List<Curve> curves, double tolerance)
{
var newCurves = new List<Curve>();
var absorbedCurves = new List<Curve>();
for (int i = 0; i < curves.Count; i++)
{
Curve curveA = curves[i];
if (absorbedCurves.Contains(curveA)) continue;
for (int j = i + 1; j < curves.Count; j++)
{
Curve curveB = curves[j];
var completed = Curve.GetDistancesBetweenCurves(
curveA, curveB, tolerance,
out var maxDistance, out _, out _,
out var minDistance, out _, out _
);
if (!completed || maxDistance > tolerance) continue;
// If the distance between the lines is zero they should completely overlap
// over their entire domain. In that case pick the longer one.
if (curveA.GetLength() > curveB.GetLength())
{
absorbedCurves.Add(curveB);
}
else
{
absorbedCurves.Add(curveA);
break;
}
}
if (!absorbedCurves.Contains(curveA))
{
newCurves.Add(curveA);
}
}
return newCurves;
}
today but this one is to much for my brain now:
