[Research] Relationship between the tension and the distance between waypoints

[Agustin Alba Chicar]

Trigger

From the issue #133 we have discussed the need to change the tension of the splines when the distance of the waypoints varies. There are several use cases in MCity as the roundabouts where a highly sampled curved comes in the RNDF description. This problem is not there when the curve is a straight line or the distance between the waypoints becomes large.

Possible issues

When a road has a none uniform geometry, let's say a piece of the road is straight and the rest is curved, it is possible to get a variation in the distance of the waypoints that makes impossible to use one value of tension for the complete path.

Samples

Here is a roundabout RNDF:

RNDF_name   roundabout
num_segments    1
num_zones   0
format_version  1.0
segment 1
num_lanes   1
segment_name    Segment
lane    1.1
num_waypoints   38
lane_width  13
1.1.1   9.998663    64.999629
1.1.2   9.998666    64.999665
1.1.3   9.998667    64.999669
1.1.4   9.998679    64.999707
1.1.5   9.998698    64.999742
1.1.6   9.998725    64.999772
1.1.7   9.998757    64.999796
1.1.8   9.998761    64.999797
1.1.9   9.998794    64.999812
1.1.10  9.998838    64.999820
1.1.11  9.998883    64.999817
1.1.12  9.998926    64.999804
1.1.13  9.998965    64.999780
1.1.14  9.998980    64.999766
1.1.15  9.998986    64.999761
1.1.16  9.998991    64.999755
1.1.17  9.999004    64.999738
1.1.18  9.999026    64.999695
1.1.19  9.999036    64.999648
1.1.20  9.999034    64.999599
1.1.21  9.999021    64.999555
1.1.22  9.999020    64.999553
1.1.23  9.999003    64.999523
1.1.24  9.999002    64.999522
1.1.25  9.998975    64.999490
1.1.26  9.998940    64.999465
1.1.27  9.998900    64.999449
1.1.28  9.998858    64.999442
1.1.29  9.998815    64.999445
1.1.30  9.998809    64.999447
1.1.31  9.998780    64.999456
1.1.32  9.998774    64.999458
1.1.33  9.998737    64.999480
1.1.34  9.998706    64.999509
1.1.35  9.998683    64.999546
1.1.36  9.998668    64.999586
1.1.37  9.998667    64.999593
1.1.38  9.998663    64.999629
end_lane
end_segment
end_file

And here is a straight lane:

RNDF_name   straight_lane
num_segments    1
num_zones   0
format_version  1.0
segment 1
num_lanes   1
segment_name    Segment
lane    1.1
num_waypoints   12
lane_width  13
1.1.1   10.000451   64.999641
1.1.2   10.000415   64.999642
1.1.3   10.000314   64.999642
1.1.4   10.000269   64.999642
1.1.5   10.000095   64.999643
1.1.6   10.000059   64.999643
1.1.7   10.000023   64.999644
1.1.8   9.999990    64.999644
1.1.9   9.999954    64.999644
1.1.10  9.999918    64.999644
1.1.11  9.999499    64.999646
1.1.12  9.999463    64.999646
end_lane
end_segment
end_file

[Michel Hidalgo]

Since the sort of splines we're using do not ensure C2, normal acceleration smoothness won't happen. Nevertheless, I believe we can approach that smoothness by reducing the magnitude of the discontinuity in curvature k, which is a sensible idea as we've already seen cases of rather smooth interpolations. Thus, the task is to find the limit of k as it approaches the control point from both sides as a function of the tension of the spline, the distance between control points and the like.

Here I'm posting first derivation results.

Given 3 points p1, p2, p3 and their tangents computed as t1 = (p2 - p1) / 2 * (1-t) and t2 = (p3 - p1)/2 * (1-t) (that is, in a cardinal spline way), the curvature k of the cubic hermite spline that interpolates the interval [p1 p2] as it approaches p2 (t -> 1) is

k12 = (norm(p2 - p1)/norm(p3 - p1)^2) * (abs(2*beta - 6)/beta^2) * sin(theta)

where beta = (1 - t)/2 and theta is the angle (p3 - p1) and (p2 - p1) form.

[Michel Hidalgo]

After a quick talk with @agalbachicar, I want to clarify what's the end goal of this approach. I'm not trying to force a condition on the spline to ensure C2 (we can't with these type of splines), but instead I'm trying to find boundaries in the tension value to achieve a given maximum jump in curvature as we approach the spline at the control points (the spline is not continuous in curvature at those points, that's why limits must be evaluated from both sides). And If that jump is small enough, we won't notice.

[Andrés Fortier]

The idea is to make the road as curved as possible without seeing any artifacts. For some roads you need to have a tension of 0.7 to avoid weird loops at intersections while for others you can relax that value to 0.5. Ideally, we want to find some metric that allows us to derive that tension value so that splines look as smooth as possible while being visually correct.

[Michel Hidalgo]

Right. After some amount of effort, I've reached a preliminary expression for a boundary in curvature k change at a point pn as a function of the tension t, the other control points p and a maximum rate of change e.

It needs validation still.

[Michel Hidalgo]

Bear in mind that this is a boundary for minimum tension, not maximum. To handle weird loops when tension gets too low it's harder. Actually, I wouldn't know how to model it :)

[Michel Hidalgo]

Ok, it seems to be valid, though not very useful. Both curvature and its derivative change proportions with distance, so we don't actually get an invariant to hold onto. I've made up a couple heuristics using the curvature expression like the one below (the rationale is to, given a three points parabola, make curvature proportional to the depth of the valley and inversely proportional to how wide the valley is), but they won't always work. One that looked promising was to keep curvature derivative a fraction of curvature, but tension gets canceled out.

So, all things considered, we'll have to try with an heuristic and settle with a best effort approach.

[Agustin Alba Chicar]

Some thoughts:

• In general, we get the loops in connections. I think this is mainly because we need to respect the tangents from one road and the other (exit and entry) and the distance between the connecting points is not related in a proper way with the applied tension and those tangents.
• One iterative and intuitive option to detect the loops is the following:

Given the spline which is defined by its control points (blue dots) we'll interpolate a path (the loop) in between those points. The parameter t will let you move over the curve from zero to one (left blue dot and right blue dot). If we have a spline that is defined with more than two points and it has a loop, it will be always between two control points so the problem of finding the loop is centered in between two control points. So, I call A the vector that joins both control points in the order they are given in the map and B and C the vectors that join the image of the spline at t_1 and t_2 to the first control point. t_1 is smaller than t_2. Finally, the projection of B and C over A (B_a and C_a) should be monotonously increasing. So, if we sample the curve we can detect the loop.

• Based on the previous idea, if we derive the polynomials projected over vector A, it will get another polynomial that should not have any roots in the open interval (0; 1) of t to be loop-free. Perhaps there is math theorem with simple solution that I'm missing that can help us.

[Michel Hidalgo]

I just pushed a monotonicity check method to the ignition::math::Spline class using bezier representations (branch ign-math3-loop-detector). Documentation and tests coveraged checked. The condition being used (that of inner bezier control points not going past each other) is not a necessary condition but a sufficient one. Incidentally, I found that there's a formal approach to the "shape classification" problem though for 2D curves only, see here.

[Michel Hidalgo]

PR sent.

[Michel Hidalgo]

This is somewhat old, isn't it @andres_fortier ?

[Andrés Fortier]

Yup, thanks @hidmic , closing this one