Sketcher: Ellipse support

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
User avatar
DeepSOIC
Posts: 7480
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Sun Sep 21, 2014 12:32 am

As for constraining an ellipse, I have already put my vote quite a while ago and here's what it was (rephrasing):
* The ellipse on screen is just the ellipse curve and two points - its foci. (a center point would be good to have as well)
* There are two ellipse-specific constraints on the toolbar: major radius constraint and minor radius constraint
Given those, all the rest is straightforward using normal constraints:
- a center point is center of symmetry for foci
- major axis is through foci
- minor axis is a line of symmetry for foci
- once any axis is there, angle constraint is obvious
This fits best into option 4, so I'll vote for 4.
BTW:
abdullah wrote:B.3) ellipse and two construction points => Fits two points to the foci positions
eem... Is there a distinction of points to construction/non-construction? I thought all points are construction ;)
User avatar
DevJohan
Posts: 41
Joined: Sun Jul 13, 2014 2:36 pm
Location: Stockholm, Sweden

Re: Sketcher: Ellipse support

Postby DevJohan » Sun Sep 21, 2014 12:51 am

DeepSOIC,

If you instead fix the radius, what you end up with is the distance to ellipse constraint which is the error function abdullah tried to use for point on ellipse. This is also a fourth degree equation.

To avoid the solution jumping from one point on the ellipse and circle to another point on the ellipse and circle I think some kind of extra data is required. An intermediate line is one possibility where you constrain one end of the line to the ellipse and circle curves and add tangency constraints ellipse-line and circle-line.
ellipsetocircle.png
ellipsetocircle.png (29.34 KiB) Viewed 1101 times
This tangency point does not necessarily have to be visible, but it can be quite useful if it is.
abdullah
Posts: 3259
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Sun Sep 21, 2014 4:44 am

Hi folks!

I see you have been busy with this! Thanks!!

I should have talked about the sketcher limitations involved in my previous post. This I already said somewhere in this thread, but it is so loooong that keeping track of it is difficult...
Let the ellipse have at least one construction line (for example between the two focus points) and selectable points at both ends of the major radius.
other CAD packages do have more selectable lines and points for ellipses
The ellipse on screen is just the ellipse curve and two points - its foci
The geometric elements of the sketcher can, as per current design, have 4 "own" "sub-elements", {edge,starting point, endpoint, midpoint}. This means that the code for handling (selecting, dragging, moving, drawing, ...) any element, that is generic, is restricted to those options. I think it is not enough to say, in ellipse it would be great if we had, to rewrite half the sketcher, unless there is no other way, or this other way is deemed a much worse option. This can be discussed, but let's assume for a second the answer is "we are not extending this" :) .

N.B.: I need start and endo points for elliptical arcs end.
N.B. 2: There is some relation between the naming and the UI. Even if we would consider extending... center is center, so we should create two new points for foci (for example), which would be "conic cut specific"...

Then the only other options are: specific constraints (a no go for most, I understand this) or geometric elements, not being sub-elements of the ellipse, but constrained to its shape in a way that they allow to use them as the elements "internal geometry", thereby allowing to further constraint the shape and potentially substituting the ellipse specific constraints.

Let's assume we go with construction lines and points (yes, DeepSOIC, all points are to my knowledge construction points, I like to call them construction points just to indicate their function ;) ).

This "construction geometry" must be constrained to the shape via a constraint. Why? The construction lines and points are not part of the geometric element. As such, they do not move solidary to the shape, unless some constraint forces them to. So there have to be "means" in the UI that allows a user to constrain this construction elements to the shape. This is what I was referring to previously as "reusing of constraints" or a "new generic constraint" (to favorize any option, let's call this "forcing constraint", which is quite stupid, as any constraint forces :lol: ).

From the solver point of view, this "forcing constraint" fixes the value of the construction elements to move solidary to the geometric element (e.g. ellipse). Let me show you how this constraining could work in practice. An external geometry (could be the line of Ulrich's reply, or the two foci of DeepSOIC) is selected and via a button in the toolbar is constrained to the ellipse. A constraint of this type appears in the constraint's dialog. The solver builds its internal constraints (relations between variables) from this constraint list. The system is solved based on this internal constraints. My point here is that: we need a constraint as a carrier of the constraining information towards the solver if we use construction elements.

Oh man! You are overcomplicating it, we have to create construction elements and then assign them. Maybe I am, but if the only issue is the creation and constraining, then a sketcher tool can be created to accelerate the process. You select a geometric element, you push that tool button, and the construction lines and points are created and constrained to the geometric element (for example in the ellipse you could just draw 5 relevant elements, axes, line between foci, points of the foci, points at the end of the ellipse). Of course, you can remove what you do not want or need...That may still be overcomplicating it. We could even make all this geometry appear on creation of certain geometric elements, for example the ellipse, so that it is thought as "the ellipse comes always with a construction line, or with two foci". However, this might be visually too many elements.

There are some many interesting points in your answers. I find it fascinating how users of different disciplines tend to want some construction elements over others:
Let the ellipse have at least one construction line (for example between the two focus points) and selectable points at both ends of the major radius.
The ellipse on screen is just the ellipse curve and two points - its foci. (a center point would be good to have as well)
With option 4, implemented as explained in the previous paragraphs, we could have both, and even more. Let's assume we go for option 4. We have a new constraint, "align to internal geometry", applicable to any geometric element (actually one could think of this as a generic flexible "extension" of the basic parameters {edge, ...}).

Two modes of operation:
1. Select a plurality of construction elements and a geometric element, and we apply the constraint, the construction elements (as supported) are "forced constrained" to the element.
2. Use an accelerator (sketcher tool) as explained above, it might bring a modal dialog, with a list of supported "internal elements" for the selected geometric elements. Then the user selects foci, and Ulrich's line between foci.
For each element of those a "forcing constraint" is created {alternatively, you push everything and the user removes the unneeded}.

You could have both at the same time...

P.S.: One limitation though, the constraints that are applied to those construction elements are unaware of the fact that they are part of an ellipse, it is not like selecting the subelements {edge,...}. Then the system knows it is an ellipse. It comes to my mind, selecting the point at the end of the major axis and hitting "radius" would not work out of the box, because that point does not know he belongs to an ellipse, and no radius is defined for a single point.

Now, to some comments to your specific solutions:
- Ulrich1a =>
* Nice idea, line between foci! No phi-constraint, agreed.
* Distances between foci fully define the ellipse, I agree, though people may think more in terms of a,b (radiuses). Ah! there it comes "Radius constraint extension"... In fact, using the radius constraint to calculate several radiuses seems to me difficult to integrate. Why? Radius is thought to be applied to an edge, the ellipse has one edge and two radii (one to many). If you use a construction element, like a point at the end of the major axis, the point does not know it belongs to an ellipse. It will be length constrains, for example, or point to point distance (center to extreme on major radius).
* Please note that which parameters go into the solver is inmaterial, as far as they fully constrain an ellipse. We can show the user some and then use others in the solver... My solver implementation uses (centerx,centery,major,minor, phi), but you can input any other thing and then calculate them. Some solver constraints rely on foci while others rely on center point... This is ok, no limitations there.
- DeepSOIC
* I really plan to get rid of the ellipse specific constraints

PROPOSAL:
After consideration of all your input requirements, I think that solution 4 is the more appropriate. Let me know if you see major problems with it, some of the main Developers, any input from you here?

Let me know any additional input you would like to be consider...
abdullah
Posts: 3259
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Sun Sep 21, 2014 5:55 am

I feel sorry, that you all were forced to do all that math and tests, because I made just a guess without proof. It is my fault.
It sounded good to me. It really took me no time. I copied the point on object constraint code into a new constraint (which somehow I needed to do any way), and modified a to be a+distance and b to b+distance. It did not took more than 15 minutes. Even when I have to derive new partials, well sage does it for me, I just have to put your function in (around 15 minutes if the structure is there)

If you think you have something that reasonably should work, even without proof, I am happy to try it.
Do we need for every constraint a single error function or is it possible to apply two error functions at the same time, that may be of a simpler structure?
The answer, as far as I understand, is it depends. As far as the total error can be expressed in terms of both errors, and the partials and be summed up, it can be tried. I have not seen this in any of the existing constraints.
If this is possible, some already existing constraints may be reused for other tasks. So only a new error function for the bisecting line of the two lines from the ellipse point to the focus points is needed?
Now, this is a different, more specific case. If the constraints are fully independent (the system matrix formed by the gradients has independent rows for each, i.e. if the rank of the matrix produced by the several separate constraints is equal to the number of constraints.), then you can certainly apply two or more solver constraints to implement an UI constraint, and even more, you are encouraged to do so, as this simplifies the code. OIne simple example is the coincident constraint, implemented as two equality constraints:

int System::addConstraintP2PCoincident(Point &p1, Point &p2, int tagId)
{
addConstraintEqual(p1.x, p2.x, tagId);
return addConstraintEqual(p1.y, p2.y, tagId);
}

Another example:
int System::addConstraintPerpendicularArc2Line(Arc &a, Point &p1, Point &p2,
int tagId)
{
addConstraintP2PCoincident(p1, a.end, tagId);
double dx = *(p2.x) - *(p1.x);
double dy = *(p2.y) - *(p1.y);
if (dx * cos(*(a.endAngle)) + dy * sin(*(a.endAngle)) > 0)
return addConstraintP2PAngle(p1, p2, a.endAngle, 0, tagId);
else
return addConstraintP2PAngle(p1, p2, a.endAngle, M_PI, tagId);
}

What is not possible is to use a gemetric element that does not exist in the sketch (trying to implement a constraint using a point that is not in the sketcher)...
I made an error function for the point on ellipse without sqare root:
I will try to put them those into different branches for testing. We would then welcome Jim (and actually anyone who wants) assistance to find converging problems...

Moreover:
I have tried a similar approach to circle-tangent-ellipse problem and got stuck being unable to analytically solve this little crazy 4-th order polynomial equation...
Numerically solving an equation is possible. My original implementation of the point on ellipse did that. The selection of an adequate root can be done by selecting the right starting point for the Newton-Raphson algorithm. The problem that may arise is that I need an full error function (with all its parameters), so that I can derive the partials. If numerically solving an equation removes information (i.e. variables) in the error fuction, then the partials will have problems of convergence. This problem I had, when afterwards trying to set a vertical constraint to a line that was point on ellipse (see Jim-Redundancy test you may find some 20 posts ago in this thread).

That is what I call "the magic" behind your two approaches for point on object and line tangency. My calculus is not great, but I can solve a specific problem. I totally miss that "magic" of making using the properties of the curve to "geometrically" solve the problem.

Another approach I tried was, for (I do not longer remember if it was point on object or tangency to line), is to solve analytically everything in cartesian coordinates. It was so long that each partial in C was around 600 Kb of code (without simplifying all the partials where 59M of c code, which caused gcc to fail to compile the code, preprocesor and not enough virtual memory errors), that simplified could be compiled, and even if that would not be assumable to be integrated, I tried it and it had convergency problems...

One of them is typical, when you have vertical lines the slope is oo... so you have convergency problems. That is why a "distance based approach" as yours, is the right way, IMO. I am not an expert anyway...

When I have some time, I will look into those equations...of you both. Thanks a lot for your support!!!

To avoid the solution jumping from one point on the ellipse and circle to another point on the ellipse and circle I think some kind of extra data is required. An intermediate line is one possibility where you constrain one end of the line to the ellipse and circle curves and add tangency constraints ellipse-line and circle-line.
No other tangency works with "helper points". However, I would lie if I would said I did not try it. Could you please upload your sketch so I can take a look?

If we miserably fail to bring it in other terms, we might consider implementing the tangent in this case with the tangent applying constraint generating that point... I can not say I like it... also because other tangents don't...

Nevertheless, I agree it might be useful...

...gotta go guys, let me know what you think!!
abdullah
Posts: 3259
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Sun Sep 21, 2014 9:12 am

Call for testing of convergence / problems of Point on Ellipse:

Original:
https://github.com/abdullahtahiriyo/Fre ... master.git
* [new branch] sketcher_ellipse2_tangent_circunf_ulrich1a_original_pointonellipse

vs squared:
https://github.com/abdullahtahiriyo/Fre ... master.git
* [new branch] sketcher_ellipse2_tangent_circunf_ulrich1a_squared_pointonellipse

I consider this constraint implementation as final. So let me know any problem relating to it.
abdullah
Posts: 3259
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Sun Sep 21, 2014 9:36 am

To avoid the solution jumping from one point on the ellipse and circle to another point on the ellipse and circle I think some kind of extra data is required. An intermediate line is one possibility where you constrain one end of the line to the ellipse and circle curves and add tangency constraints ellipse-line and circle-line.
Ok. I got it. I did it with an extra point putting point on line+point on circle+point on ellipse+line tangent to ellipse+line tangent to circle.... it is a nice exercise to test convergence of ellipse constraints. Actually it is even fun to grab the circles center and drag it to roll in the outside part of the ellipse, as it would be a wheel :lol:
ellipse25.png
ellipse25.png (26.97 KiB) Viewed 1073 times
ulrich1a
Posts: 1920
Joined: Sun Jul 07, 2013 12:08 pm

Re: Sketcher: Ellipse support

Postby ulrich1a » Sun Sep 21, 2014 9:55 am

abdullah wrote:My solver implementation uses (centerx,centery,major,minor, phi), but you can input any other thing and then calculate them. Some solver constraints rely on foci while others rely on center point... This is ok, no limitations there.
I do vote for a solver representation of only the two foci and the major radius. You may need adding only a few lines to your code, in order to use the existing ellipse input routine to adapt to the new parametrization:
Starting to draw the ellipse at the center point. It is needed only temporarly at the beginning.
Defining the major radius at dragging in one direction. This is already implemented.
At the click for the definition of a make an assumption of for example b = 0.5 * a. The two foci can now be calculated. As you have already all information needed to define an ellipse: a, b, phi from the angle of the line drawn to define a.
The input of b should than change only the distance of the foci.

This approach follows the logic of the sketcher: Also lines are not defined by one point and an angle to the coordinate system and a length, but by two points.
In the current implementation the ellipse rotates havily at dragging at it. This follows directly from the parametrization with a, b, phi and center point. The solver just converges to a rotated solution of the ellipse. I do expect a better behavior at dragging at the ellipse with the parametrization of two foci and a.

Ulrich
User avatar
DeepSOIC
Posts: 7480
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Sun Sep 21, 2014 12:45 pm

ulrich1a wrote:I do vote for a solver representation of only the two foci and the major radius.
+1, except, IMO, not major radius, but minor radius. Why? Because major radius has to be large enough to fit the foci in the ellipse, while minor radius can be anything above zero (and even negative can just work).
User avatar
DeepSOIC
Posts: 7480
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Sun Sep 21, 2014 12:59 pm

abdullah wrote:each partial in C was around 600 Kb of code
Why can't you use numerical derivatives? I think they should be good enough unless the matrix is ill-conditioned (i.e. two constraints are very close to being conflicting/redundant).
abdullah
Posts: 3259
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Sun Sep 21, 2014 5:36 pm

In the current implementation the ellipse rotates havily at dragging at it. This follows directly from the parametrization with a, b, phi and center point. The solver just converges to a rotated solution of the ellipse. I do expect a better behavior at dragging at the ellipse with the parametrization of two foci and a.
Thanks for posting this. Actually it has come to my attention that phi varies a lot. The changes are not just a couple to change solver (all the partials have to be recalculated for all the implemented constraints). However, it is very much doable and I agree with you in that I expect more stable behaviour.
except, IMO, not major radius, but minor radius. Why? Because major radius has to be large enough to fit the foci in the ellipse, while minor radius can be anything above zero (and even negative can just work).
Ok. I do not fully follow the advantages of using minor instead of major, but for me it is ok. Could be agree to one or the other, so that we do not have to recalculate the partials next week because of changing from one to the other? Ulrich, as you proposed first, what do you think?
Why can't you use numerical derivatives?
I am sorry I have to ask what do you exactly mean by this... Could you put me some example? I am a little bit math constraint...

BTW, the currently partials are just some bytes...