How to calculate control points of a bezier curve that avoid objects?

Question

In particular, I work in canvas with javascript.

Basically, I have objects that have borders that I want to avoid, but are still surrounded by a bezier curve. However, I don’t even know where to start writing an algorithm that will move control points to avoid a collision.

The problem is the image below, even if you are not familiar with musical notation, the problem should be pretty clear. Curve points are red dots.

In addition, I have access to the bounding boxes of each note that includes the trunk.

Therefore, naturally, collisions should be detected between the bounding rectangles and the curves (in a certain direction it would be nice, but I looked through and saw that there was a decent amount of information about this). But what happens after collision detection? What would have to happen in order to calculate the locations of the control points in order to make something more similar:

Answer 1

Bezier approach

The initial question is broad - perhaps even broad for SO, as there are many different scenarios that need to be considered in order to create a "one solution that fits all." This is a whole project in itself. Therefore, I will present the basis for a solution that you can rely on - this is not a complete solution (but close to one ...). I added some suggestions to add at the end.

The main steps for these solutions:

Group notes into two groups: left and right.

Then the control points are based on the largest angle from the first (end) point and the distance to any other note in this group, and the last end point is at any point in the second group.

The resulting angles from the two groups are then doubled (max. 90 °) and used as the basis for calculating the control points (mainly, turning the point). The distance can be further trimmed using the tension value.

Angular displacement, doubling, distance, tension and displacement complete the fine-tuning to get the best result. There may be special cases that need additional conditional checks, but this is not within the scope of this scope to cover (this will not be a complete key ready, but will provide a good basis for further work).

A few snapshots from the process:

The main code in the example is divided into two sections, two loops that analyze each half to find the maximum angle, as well as the distance. This can be combined into one loop and have a second iterator to go from right to middle in addition to that that goes from left to right, but for simplicity and a better understanding of what is happening, I split them into two loops (and presented the error in the second half - just know. I will leave this as an exercise):

var dist1 = 0, // final distance and angles for the control points dist2 = 0, a1 = 0, a2 = 0; // get min angle from the half first points for(i = 2; i < len * 0.5 - 2; i += 2) { var dx = notes[i ] - notes[0], // diff between end point and dy = notes[i+1] - notes[1], // current point. dist = Math.sqrt(dx*dx + dy*dy), // get distance a = Math.atan2(dy, dx); // get angle if (a < a1) { // if less (neg) then update finals a1 = a; dist1 = dist; } } if (a1 < -0.5 * Math.PI) a1 = -0.5 * Math.PI; // limit to 90 deg. 

And the same with the second half, but here we rotate around the corners, so it’s easier to handle them by comparing the current point with the end point instead of the end point compared to the current point. After the cycle is completed, we turn it over 180 °;

 // get min angle from the half last points for(i = len * 0.5; i < len - 2; i += 2) { var dx = notes[len-2] - notes[i], dy = notes[len-1] - notes[i+1], dist = Math.sqrt(dx*dx + dy*dy), a = Math.atan2(dy, dx); if (a > a2) { a2 = a; if (dist2 < dist) dist2 = dist; //bug here* } } a2 -= Math.PI; // flip 180 deg. if (a2 > -0.5 * Math.PI) a2 = -0.5 * Math.PI; // limit to 90 deg. 

(The error is that the longest distance is used, even if the shorter distance point has a larger angle - I will give this for now, as this is meant as an example. It can be fixed by changing the iteration.).

The relationships I found work well, this is the difference in angles between the floor and the point two times:

 var da1 = Math.abs(a1); // get angle diff var da2 = a2 < 0 ? Math.PI + a2 : Math.abs(a2); a1 -= da1*2; // double the diff a2 += da2*2; 

Now we can simply calculate the control points and use the voltage value to fine-tune the result:

 var t = 0.8, // tension cp1x = notes[0] + dist1 * t * Math.cos(a1), cp1y = notes[1] + dist1 * t * Math.sin(a1), cp2x = notes[len-2] + dist2 * t * Math.cos(a2), cp2y = notes[len-1] + dist2 * t * Math.sin(a2); 

And voila:

 ctx.moveTo(notes[0], notes[1]); ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, notes[len-2], notes[len-1]); ctx.stroke(); 

Add narrowing effect

To create a curve that is more visually pleasing to narrow, you can add simply as follows:

Instead of stroking the path after adding the first Bezier curve, adjust the control points with a slight angle offset. Then continue the path by adding another Bezier curve going from right to left, and finally fill it ( fill() closes the path implicitly):

 // first path from left to right ctx.beginPath(); ctx.moveTo(notes[0], notes[1]); // start point ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, notes[len-2], notes[len-1]); // taper going from right to left var taper = 0.15; // angle offset cp1x = notes[0] + dist1*t*Math.cos(a1-taper); cp1y = notes[1] + dist1*t*Math.sin(a1-taper); cp2x = notes[len-2] + dist2*t*Math.cos(a2+taper); cp2y = notes[len-1] + dist2*t*Math.sin(a2+taper); // note the order of the control points ctx.bezierCurveTo(cp2x, cp2y, cp1x, cp1y, notes[0], notes[1]); ctx.fill(); // close and fill 

Final result (with pseudonyms - voltage = 0.7, filling = 10)

Fiddle

Recommended improvements:

• If the distances between the two groups are large or the angles are steep, they can probably be used as a sum to reduce the tension (distance) or increase it (angle).
• The dominance / area factor can affect distances. Dominance, indicating where the highest parts are shifted (it lies more on the left or right side and accordingly affects the voltage for each side). It is possible / potentially can be enough in itself, but needs to be tested.
• The cone angle offset should also be related to the sum of the distance. In some cases, the lines intersect and do not look so good. The cone can be replaced by manually selecting the parsing of Bezier points (manual implementation) and add the distance between the source points and the points for the return path depending on the position of the array.

Hope this helps!

Answer 2

Cardinal spline and filtering approach

If you are open to using a non-Bezier approach, the following may give an approximate curve above the notes.

These solutions consist of 4 steps:

• Collect the top of the notes / stems
• Filter out gaps in the path
• Filter points on one slope
• Spline critical curve generation

This is a prototype solution, so I did not test it for all possible combinations. But this should give you a good starting point and basis for continuing.

The first step is easy, type the dots representing the top of the note - for demonstration, I use the following set of dots, which slightly reflects the image that you have in the message. They are arranged in x, y order:

 var notes = [60,40, 100,35, 140,30, 180,25, 220,45, 260,25, 300,25, 340,45]; 

which will be presented as follows:

Then I created a simple multi-pass algorithm that filters out dips and points on one slope. The steps in the algorithm are as follows:

• As long as anotherPass (true) exists, it will continue or until the maximum number of passes has been set
• The point is copied to another array if the skip flag is not set.
• He will then compare the current point with the next one to see if it has a downward slope.
• If so, he will compare the next point with the next and see if it has an up-slope
• If so, it is considered dip, and the skip flag is set so that the next point (current midpoint) will not be copied
• The next filter will compare the slope between the current and next point, and then the next and next.
• If it is the same skip flag.
• If he needs to set the skip flag, he will also set anotherPass flag.
• If there are no points at which it is filtered (or the maximum number of passes), the cycle will end

The main function is as follows:

 while(anotherPass && max) { skip = anotherPass = false; for(i = 0; i < notes.length - 2; i += 2) { if (!skip) curve.push(notes[i], notes[i+1]); skip = false; // if this to next points goes downward // AND the next and the following up we have a dip if (notes[i+3] >= notes[i+1] && notes[i+5] <= notes[i+3]) { skip = anotherPass = true; } // if slope from this to next point = // slope from next and following skip else if (notes[i+2] - notes[i] === notes[i+4] - notes[i+2] && notes[i+3] - notes[i+1] === notes[i+5] - notes[i+3]) { skip = anotherPass = true; } } curve.push(notes[notes.length-2], notes[notes.length-1]); max--; if (anotherPass && max) { notes = curve; curve = []; } } 

The result of the first pass will be after the displacement of all points on the y axis - note that the falling note is ignored:

After passing all the necessary passes, the final array of points will be represented as follows:

The only step is to smooth the curve. To do this, I used my own implementation of the cardinal spline (licensed under MIT and can be found here ), which takes an array with x, y points and smooths its addition of interpolated points based on the tension value.

It will not generate a perfect curve, but the result will be:

Fiddle

There are ways to improve the visual result, which I did not consider, but I will leave it to you if you consider it necessary. Among them may be:

• Find the center of the points and increase the offset depending on the angle so that it is larger at the top
• The end points of a smooth curve are sometimes twisted - this can be fixed by adding a start point right below the first point, as well as at the end. This will make the curve have a better look / finish.
• You can draw a double curve to make a cone effect (thin start / end, thicker in the middle) using the first point in this list on another array, but with a very slight offset at the top of the arc, and then render it on top.

The algorithm was created ad-hook for this answer, so it obviously did not pass the proper check. There may be special occasions and a combination discarding it, but I think this is a good start.

Known disadvantages:

• It is assumed that the distance between each stem is the same for slope detection. This must be replaced by factor comparison if the distance varies within the group.
• It compares the slope with exact values ​​that may fail if floating point values ​​are used. Compare with epsilon / tolerance