Joining straight segments with circular segments

How are you finding the plane for each arc?  Don't think I would call that straightforward.
But given the planes, I think it would be straightforward enough to find the arcs.

Curses, you're correct ozo the planes are not straightforward at all, sorry.  I've been solving it by creating progressively more complex versions of the problem, in the earlier ones the plane was straightforward.  Stupidly assumed the same thing, been working at this for too long.

I think I would try to start by fixing one vector, and finding the other vector given the radius, the angle of the planes, and the angle along the arcs, and look for a way to invert that function.
But I don't have time to work that out right now...

Thanks ozo, if you do find time to figure any more of it out I'd be glad to hear.

It's quite easy to fix the start vector as it already has space within the program.  In this space the direction vector is the z-axis.  If I transform the end point into this space the problem becomes simpler to describe, but no simpler to answer.

Given a point in 3 space with an arbitrary direction vector, join the point smoothly along the z-axis of the origin and the direction vector with two circular segments of equal radius.

If any one can do it with segments of unequal radius I'd really like to know.  Even find some way to do it by recursive fitting.

Do you have to use circular arcs?  The problem is trivial if you're willing to use cubic splines.

Yes, it is trivial with splines and I've already implemented that.  The code is in a program where the user is modelling a 3D environment with pipes (amongst other things).  Splines are soft, they create freeform shapes, like cables or hoses.  The circular segments are to create pipes that appear to be constructed from solid sections of pipe, like plumbing, pipes that carry material under pressure.

You can't create an S-bend from a single cubic that looks like the one you would get from two circular segments.  It's shape is approximate and it lacks C2 consistency.  When I say C2 'I mean the vertices of its tesslation are not very evenly spaced'.

Still, cubic is the only functioning answer I have at the moment.

If you're willing to use 4 quarter arcs and a line segment, that may be easier to find

Ozo, thats a very intriquing statement.  One of my build up problems involved using a line segment.  I'd be very keen to hear what the potential answer is.  Even if its unproven, I'd happily code it to see if it works.

By quater arc I guess you mean an arc out of the start then into the line, out of the line and into the end?

I mean a 90 degree arc

I can't picture how that would work?  What if the angle between the start and end points was small? Say 10 degrees?  Would it still use all 4 arcs?  Would the radius of the arcs get smaller as the angle gets smaller?

Another possiblity is using to circular segments to join to a line parallel to either point.  So that there is a straight segment of undefined length paralles to one of the points.  Either between the start point and the first segment or between the second segment and the end point.  This simplifies the problem a little.

four 90 degree arcs where you swivel the plane of the arcs give you the degrees of freedom necessary to match the direction of a straight section that joins the distance between the segments.
If the segments are very close to each other, you may need to reduce the radius of the arcs.

For small angles, a pair of 90 degree arcs on close to the same plane can cancel each other.

Would your parallel segment also be collinear to the segments?

Yes, the linear segment would be collinear with either the start or end segment.  The curves can start or end anywhere along that line, so you dont have to actually reach the point.  In that description I used parallel where I should have said colinear.

I've made a model to illustrate this version of the problem.  The cyan parts are the start and end segments, the magenta is the circular sections and the yellow is the connecting linear segment of whatever length.

I think I may have a solution that uses three segments.  You start by using arcs of unit radius, as long as the end of the final arc is on the line between the start point and end point, you can scale the radius to get to the end point.

First is an circular segment from start so that its end is parallel to the direction of the end point.  The normal of the plane for this segments is formed from the start direction and the end direction.  Its arc is the angle of the end segment along that plane.

You then have two more circular segments of equal arc arranged in an s-bend.  These segments take the end of the first circular segment onto the line between start to end.  The plane for these is calculated from the end direction and the line from start to end.  That plane also gives you the distance that the s-bend has to cover (still working homogenously).

Anyone find any holes in this idea?  Otherwise I will try coding it to see if it works.  I always get my brightest ideas when I wake up.

Wow, lots of math has suddenly arrived in my question.  Thanks both.

thehangman, the magneta arcs can be any angle whatsoever,  Part of the problem is calculating those angles.  I've only used 90 degree segments in the diagram because it's easier to model.  Other than that I tried to understand you solution and got stuck at -

'Let n be a unit normal vector to them'.

Normal to what?  The following text dosen't help me much as I'm not good with written formula.  I find it easier to follow a solution in the style of the one I give, where the method is explained rather than the math.  Still the rest of the answer seems clear enough.

NovaDenizen, that answer makes sense all the way to 'This ought to be solvable numerically'.  I don't know how to take residuals, or calculate jacobians, I will find out though.  Unfortunately I have to concentrate on other problems today.  I will get back to this tomorrow.

In addition to the nice comments, I'd like to describe visually the construction of the solution.

Fig. 1 shows the initial cylinders.
a) The cylinders; b) the vertical planes passing by the cylinders axis, defining a vertical line intersection of both planes;
c) front view; d) top view

Fig. 2 a) The point m, in the middle of the line segment between the axis;
b) Point m in front view;
c) The added red cylinder such that the distances from each cylinder to the vertical line are equal;
d) Perspective view of the added red cylinder.

Fig. 3 a) shows the elliptical arc from the point m to the center of the red cylinder;
b) similary, another arc from m to the other cylinder. At point m, both arcs make a concordance; c) The arcs and the cylinders;
d) By dividing the arcs in n segments, construct circles, with center at each dividing point across the arcs. The radius is the same of that of the cylinders. Case the cylinders have different radius, make them changing proporcionaly to the distance from each cylinder.

The math for such construction are well described previously, say: except for the elliptical arcs, which are easely deducted from circular ones.

Jose

> the vertical planes passing by the cylinders axis,
Are the cylinders assumed to be horizontal?  

> defining a vertical line intersection of both planes;
What if there is no vertical intersection of tho planes?

> The added red cylinder such that the distances from each cylinder to the vertical line are equal;
What if the distances are negative?

>Are the cylinders assumed to be horizontal?
No.
There are infinite planes passing by the axis of any cylinder (horizontal or not).

>What if there is no vertical intersection of tho planes?
Among the infinite planes, one of them is vertical. By chosing the vertical planes passing by each cylinder, their intersection is a vertical line, so always is possible to find a vertical intersection.

>What if the distances are negative?
The idea was to make the distances equal, regardless the signal.

The questions around the proposed solution are perfectly pertinent, because the author seeks for a generic solution and the construction suggests a special case.

The orthogonality of the proposed construction is purely for easy, as well the picture given by the author. BTW the construction was made on that picture. Even the "vertical" or "horizontal" aren't necessary, they could be anything. Also there is an error on permit eliptical arcs, as the author defined them as circular.

Jose

What if the chosen vertical planes are parallel?


What if the equal distances are negative?

The vertical choose was a convention for easy understanding of the concept. It can be any crossing planes. Doesn't matter if the distances are negative, as seen in the 2D samples below.

The solution for this problem is simply to reduce it to two dimensions, find the arcs in the plane and go back to 3D by carrying the curves.

The 2D reduction is done by finding a parallel to one of the vectors such that is coplanar to the other line, thus defining the 2D space where the arcs are determined. The key elements at this step are:
- The endind points of both vectors (where the arcs start)
- the centers os the arcs
- the concordance point (where the arcs coincide)

By interpolating the key points, the final arcs can be constructed.

Please note the red lines in the drawings. They are pivot lines, where the arcs can turn around, without loss the arc of circle aspect ratio.

Well, satsumo, it is enough for 130 points... (just kiding, your question was a good challenge). Anyway, the ozo brilliant questions worth the efforts.

Jose

"normal to what":
The vector n should be orthogonal to both v and v' (i.e. the direction of the given pipes (and of unit length just like v and v').
The reason is that (as I assumed 90° arcs) that the direction at the joint of the two arcs is orthogonal to both given directions.
You can obtain  n  from v  and  v'  by calculating their corss product  v x v'  and then normalizing to unit length.
If we think the whole situation rotated so that  n  is the z-axis showing "up", then we notice that both  v  and  v'  are parallel to the xy-plane. We can calculate the height difference by means of the scalar product of  w' - w  and  n (which I wrote as <w'-w, n>)
This is twice the arc radius etc. -- I hope the rest becomes understandable then or look at the very nice illustrations by JoseParrot.

Jose Parrot, forgive me if I'm not reading this right.  Your first comment suggests a solution that dosen't match the diagrams in your second comment.  The problem with the first solution is that the line of intersection rapidly moves away as the linear segments head toward parallel.

It dosen't work if the linear segments are parallel (but not collinear).  Equally it's mathematically unstable (in a computer) as it gets near parallel.  I could special case those (which I do with collinear anyway).  Still its going to produce an undesirable answer when the segments anywhere less the 30 degrees from parallel.

Comment 2 shows what looks to be a beautiful solution, however it's not clear how the pivot lines are calculated.  They don't relate to the first answer.

That said they are very nice diagrams.

@JoseParrot, the solution also appears to fail if the start and end points are near or on top of each other, in the chosen plane.  This effectively places them at the point of intersection.  In the case of your example that means vertically, in practice I'd get the plane from the cross product of the two direction vectors.  Either way, it would behave badly.

You are understanding well, the problem is that when I proposed the first solution, didn't care to arc of circles and suggested arcs of ellipsis. Anyway it was more general than specific...

Despite the caustic (and perfect) questions post by ozo, aimed to a general solution, the proposed solution was developed around the picture of pipes.gif. That image is clearly orthogonal, say, the pipes are horizontal, thus conducting to a vertical intersection of the planes (vertical as well) which pass by each pipe axis. In that topology, of course a particular case, we can assume that such vertical line can be a pivot, such that we can rotate one of the pipes around, such that their axies are coplanar. In that step, the solution is a simple 2D tangency problem. After solving it, just return the rotated pipe (and its arc) around the pivot until its original position.

As far I understand, the math procedures by thehagman are correct to solve the concordances.

Jose

P.S. Excuse me, I have an appointment and will back as soon I can.

Can we use arbitrary combinations of straight segments and circular segments?
The extra degrees of freedom mean that the solution is not uniquely defined, but it could also simplify some of the operations.
One way could be to draw a line between point a small distance in front of each of the segments, and then use circular segments to join the line segments to that line

Yes, ozo, I am assuming them parallel. If not, the inequality r1 + r2 < d makes no sense, as you have perceived. Also, if T!=M, then the arcs have different radii, as it is the case in Fig. 3 above.

About your hint on to make the raddi equal, I guess the same, mainly if the author looks for practical applications. For example, in an oil refinary, where piping is an important area. If we had a method which use equal radii and only circular arcs, the constructive job would be easier! And less expensive.

Recalling the original picture at pipes.gif from the author, the yellow cylinder seems to be an extension such that both radii are equal. Or, if needed, we can cut someone. And better: if we are constructing a refinery and must assemble hundred of curved pipes, I would make all of them equal, for scale economy (or with few models, say small, medium, big). In the cases of  r1+r2 < d, then we can add a vertical cylindric pipe with height d, such that   2 r + h = d.

Jose

To get past the orthogonality assumption that seems to be cropping up, heres a picture of an example pipe.  As you can see, It's not orthogonal.  Ozo seems to have the better understanding of the problem and he's asking the question I would ask too.

@Ozo, the equal radius thing is to make it understandable for the user, they change the shape of the pipes interactively.  I don't mind if the arcs are of unequal radii, as long as the user can intuitively understand the behaviour of the solution.

I'm interested in your two arcs and a straight segment solution and also the arbitrary arrangement of arcs and lines.  Though again, if the user can predict its behaviour well enough.  I guess your answer with many 90 degree arcs would appear unintuitive to the user, in that it would create geometry they are not likely to want.

@JoeParrot, I will work through the math of your solution after posting this comment.  I see it relies on intersection though, and so I guess it will have the accelerating toward infinity problem.

Any answer that relies on reducing the problem to 2D (thehangman's answer does this in a different sense) has the fundamental problem of the plane used for projection.  The plane is either good for the points or the directions.  The solution fails when the other criteria are poorly matched.

I've received some points and added them to this question.

For the purpose  you describe, I think circular arcs that blend into a line connecting points in front of the two line segments may be the most practical.
The radii can be adjusted by varying the distance to the points  in front of the two segments,
(but not in a way that makes it obvious how to make them equal when the segments are at  arbitrary angles and positions)

@Ozo, how would the positions of the blend points be calculated?

Once the problem is reduced to 2D, the centre of the circular segment will be at the intersection of the perpendicular to the segment, and the bisector between the line containing the segment and the connecting line
dropping a perpendicular from the line to the centre gives the blend point.

Note that any line that intersects a point directly in front of a line segment will be coplanar with that line segment.  
And a 2D line can be drawn through any 2 points.
Also, any line that is coplanar with the line segment (unless it is parallel to the line segment) will intersect a point collinear with that line segment, so this solution is fairly general.
In fact by adjusting the distances in front of the line segments, of the two points containing the joining line, you can adjust the radii to be equal and the length of the straight segment to be 0,
which would satisfy the original condition, although the adjustments to do that are not obvious.

> a 2D line can be drawn
I meant a 3D line,
although it also happens to be true in 2D

@Ozo, I've tried but I'm not sure I follow the solution you give.  Any chance you could draw me a simple diagram? It dosen't need to be 3D as your solution reduces the problem to 2D.

What happens if the end point is on the projection of the the start point.  As shown in this diagram, the red lines are the line segments, the short blue lines are the direction vectors (the purple line is an approximation of the ideal answer).

working backwards,
in that diagram,  the length of the straight section between the two curves seems to be 0 (or very short)
so the line that the curved sections blend inro would be tangent to the inflection point of the purple.
and it looks like the points in front of the blue lines that the joining line goes through are abour 1.5 times the lengthof the horizonatl blue line away from the horzontal segment and aproximately 5 times the length of the vertical blue line away from the vertical segment

Ok, but how would the factors 1.5 and 5 be calculated for this case?  Or how would the program arrive at any other factors?  I could start with a guess, lets say half the distance from one point to the other. In this case that would produce an answer that appears to project a long way from the horizontal segment and a short way from the vertical segment.

Biggest problem is when you return the problem to 3D the joining arcs become eliptical (you have to project them and the joining line onto a plane).  The distortion involved can be severe, this is where it resembles JoseParrot's solution.  If you don't project onto the plane, the joining line segment no longer connects the arcs.

I think this answer does work in the sense that it smoothly joins the two segments.  I could find a function that calculates a reasonable projection factor that the user would understand.  I don't know if people would use a solution that puts an obvious straight segment in the middle (especially when it creates elliptical arcs).  They model straight segments themselves and expect the program to join them with bends.

This solution requires an extension cylinder.

> how would the factors 1.5 and 5 be calculated for this case?  
what I was  suggesting was that if you allow a straight segment in between, and allow the radii to differ, then you do not need to calculate those factors, and instead fit the solution to the factors you choose.

> when you return the problem to 3D the joining arcs become eliptical
No, they are circles on a plane

This numerical method I suggest is basically a multidimensional version of the Newton-Raphson method.

The residuals are the measures of how badly the parameters don't fit the constraints.  Notice that all of the constraints are of the form <expression> = 0.  So you calculate each expression based on the current estimate of the parameters and the residual is the value of the expression.  When the residuals are zero that means that the parameters meet the constraints.

The Jacobian is the matrix of partial derivatives of each of the constraint equations, wrt the 8 parameters (see http://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant ).  This is a kind of linear approximation to the nonlinear equations around the current parameter values.  

Calculating the Jacobian manually can be a lot of work, but if you have access to a symbolic math program like Mathematica, Maxima, or others then it can automatically produce the partial derivatives for all 64 entries of the Jacobian.

When you have this jacobian matrix J, you can set up a simple linear algebra problem. J * deltas = -residuals.  Solving this for deltas gives you a set of approximate 'tweaks' to apply to the parameters.  parameters += deltas

Then you recalculate the jacobian and residuals based on the tweaked parameters, and repeat the process until the parameters converge.

>Any answer ....  The plane is either good for the points or the directions.  The solution fails when the other criteria are poorly matched.

I disagree. If there is no constraints, there are no criteria to match to.

For example: Are there maximum and minimum radii? Which is the criteria for radii values? Is the criteria based on minimum material? Based on minimun resistence to fluid flowing? Distance to reference planes? Are there minimum and maximum arc angles? When must an intermediate cylinder used? The picture below shows two ways to solve the problem. Which criteria determined to use (or not) the intermediate cylider? Why not to use a single curve with a slight bigger radius?

As per the pipes at pipes.jpg picture there is no constant criteria, so the way to construct it is to use an interactive CAD tool, like AutoCAD, which is rich in resources to make all the concordances.

Back to the original question:
two arbitrary vectors in 3 space, each vector with arbitrary directions (they are the end and start of two linear segments) and to join the two points along the direction vectors with two circular segments of equal radius.

>If you don't project onto the plane, the joining line segment no longer connects the arcs.

This is not a projection, it is translation and rotation instead (descriptive geometry).

Please take on account that a line and a circle arc must be coplanar to exist any concordance between them. This is why the 2D reduction helps to solve perfectly the problem.

I've not made any response for a while as I'm working on the problem at the moment.

Just wanted to quickly answer JoseParrot's question, which are perfectly very good, and suggest I should have explained better.  The picture is created from my program, which is an interactive CAD tool.  All the geometry in the image is generated by the program.  The pipe shown is using a bezier spline solution (I mentioned this in an earlier response to NovaDenizen).

The distinction between the two cases shown would be where the user chooses to draw the control points.  You can see these on the image as yellow wireframe shapes.  Indeed you have removed them from the second image, suggesting that the other control point is underneath the 'block of metal' shown.  There is in a distance from a refence plane involved, the control points lie on the reference planes and each has value for distance to the center of the pipe (shown as a yellow line from the center of the control point).

Eventually, this question will be worth 500 points.

Curse my faulty text editing 'perfectly very good' is not proper english.

@JoseParrot, if you rotate and translate the arcs, you have to do the same thing with the corresponding end of the connecting line.  Unless you are tranforming both arcs the same, the line will fail to connect them smoothly after transformation.  Yay or nay?

If the solution does introduce a linear segment the user did not draw, it needs to be one that the user can understand and might find desirable as an answer.  Otherwise the user simply won't use the solution.

@Ozo, your latest solution has suggested another solution where the circular arcs are fitted inside the linear segments rather than along their projections.  The radius of an arc at any control points would be half the length of the shorter connected line.  Diagram below shows this solution, red is the control points, blue is the linear segments, purple is the line of the resulting pipe.

This works in the same 3D.  However the pipe is likely to intersect the geometry the reference points lie on.  It has no distinction over straight segment and and joining bend, where the other solutions do.  Another problem is no direction at the first and last points.  It might intersect less with a maximum radius rather than largest radius possible, perhaps with the maximum arc radius equal to the distance from the reference plane.

@JoseParrot, could you explain the method behind the solution with the extension please?  How does it translate into 3D?

The need for extensions is defined by arc radius and relative positions of the axis, of course.

The approach I am suggesting is described in Fig 1 below. First a special case, where both cyls are in horizontal planes.

Fig 1 a) The given cyls; b) vertical planes passing by them; c) rotate ANG degrees one of the vertical planes around their intersection such that the vertical planes coincide; d) Find the single arc which solves the problem in 2D; e) pass vertical line tangent to the arc which also is perpendicular to the horizontal circular section of the curved pipe; f) rotate back that plan by -ANG. If the tangent to the curved arc coincides with the intersection of the vertical planes, the concordance is done. If not, the rotated cylinder will be in its original axis, but at different position. By moving it along the axis we need to add an extension or cut it. Adding is acceptable. If cutting is not acceptable, then we divide the circular arc at the plan (white plan at Fig 1 f) and treat the circular section as a section of a virtual cylinder, which is the new problem and repeat the proccess in a recursive way. Please note, such recursion can repeat, by creating new arcs until the concordance is solved.

Fuig 2 shows: a) the original cyls; b) the solution for the simplest case. c) a generalization of the problem.

Jose

@JoseParrot, 'repeat the proccess in a recursive way', I like that, solving by recursion had not occured to me.  I'm running scenarios for this through my poor old head, so far it's producing reasonable answers.  The method of choosing the plane for the 2D solution and the transforms involved makes the difference between a viable solution or not from a user perspective.

I'm curious about the cutting you mention, how would cutting help?

Let me suggest to limit the scope of the possibilities. For example, in Fig 1 we see two options in a and b for concordance between the same two lines. In c we see a detail of the condition to solve the option b: centers c1 and c2 must be in positions such that the radii r1 and r2 are equal to the distance between them and that the contanct point of yhe arcs is in the line c1c2.

Also to force the general cases to be reduced to the ones in Fig. 2 and 3, being the options in Fig. 2 a special case of the more general at Fig. 3.

Finally, in Fig. 4, an option with cutting.

Jose

If you can require the user to give the input as a set of connected line segments,
which can be shortened instead of extended to connect pairwise with a single circular
arc. then the computations should become very simple, all the arcs can be made to have
the same radius, and the user would have sufficient control to specify the same solution that would have been generated by the original criterion.
And I think the user control would have a more intuitive relationship to the result.

Yes, that is a great simplification of the problem, limiting the scope to a condition at same time very simple and with a wide range of possibilities.

Each arc can be constructed directly in 3D, say, the 3D reduction to 2D as discussed before isn't required, although in strict sense it is a 2D solution because each pair of lines and their concordance arc are constructed in a single plane.

I agree also with the user experience to result very intuitive.

Jose

Quick update, I'm still working on this problem.

I had a go at coding the solution with circles inside the control points.  It works well enough but is different in both code and user interaction to the bezier solution I already have.  It offers substantially less control to the user.

If anyone has any suggestions for methods I'm still actively watching this thread.

Althought the discussions and themes around are very interesting, we are at risk of loss of focus, going to other direction than the proposed question.

I don`t see any relationship between the required arc of circles to make the concordance between cylindric tubes and bezier curves. Actually I see the "control points" as the vertices of the angles where the concordances exist. Like a 3D version of the figure pipes.gif in Chamfer solution.

Seems that ozo`s comment 25370579 has the key for the solution to the problem, by simplifying the solution to few construction steps without limiting the possible inputs of the problem.

Jose