Sketcher: Ellipse support

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
abdullah
Posts: 3458
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Tue Oct 07, 2014 3:20 pm

Ok. I discover the problem with Ulrich Frozen sketch. :D

The reason is that in the calculation of the partials, some partial is not providing as much accuracy as the default values of the matrix solving system requires. :(

I debugged this by looking into the upper triangular matrix of the QR decomposition of the Jacobian matrix, so the R matrix, which looks like this:

Code: Select all

[   -4.41901   -0.130472    -0.44053   0.0163573   -0.219657 7.56131e-14     1.75207 1.80272e-13    0.742124   -0.380427    0.790285    0.266312   0.0336102    -0.45134
          0     2.98944  0.00495286    -1.03461  -0.0745613     0.34604    0.177899    0.887651     1.37306    0.715418    -1.26972    0.904908    0.335977  -0.0196984
          0           0    -2.85861   0.0523939   -0.727781 0.000599554   0.0698627  0.00153796   -0.360184   -0.424308   -0.297734    0.476123 -0.00459743   0.0695203
          0           0           0     1.47066   0.0338867   -0.263888     -0.0289  -0.0789978   -0.365727    0.291147    0.370714    0.264242    0.236149  -0.0113145
          0           0           0           0    -1.23011   0.0165664   0.0416224  0.00573413   -0.182942   -0.259901   -0.192602    0.255306  -0.0171411   0.0403459
          0           0           0           0           0    -1.08223 -0.00657568  -0.0165861  -0.0740947   0.0641968   0.0799633   0.0519519   0.0495811  -0.0028835
          0           0           0           0           0           0    -1.34001  -0.0275786   -0.313378   0.0681821   -0.255179  -0.0935947    0.082441    -1.33387
          0           0           0           0           0           0           0    -1.09715   -0.114393    -0.09499   0.0990616   -0.110885    0.555123   0.0413386
          0           0           0           0           0           0           0           0    -1.18563   -0.130639   0.0135484   0.0457846    0.262878   0.0195759
          0           0           0           0           0           0           0           0           0    -1.35287  -0.0024465     0.26777    0.165921   0.0123557
          0           0           0           0           0           0           0           0           0           0     -1.1704   0.0712341   -0.227913  -0.0169721
          0           0           0           0           0           0           0           0           0           0           0    -1.34318     0.25488   0.0189802
          0           0           0           0           0           0           0           0           0           0           0           0     1.13971   0.0848717
          0           0           0           0           0           0           0           0           0           0           0           0           0 6.91996e-14]
Last row is on the order of 1E-14.

The default setting to consider a value zero is, if I remember well, 1E-15.

The logical "fix" would be improve the partials, but as we have struggled so much with it, I am not confident that we will be able to get that 1E-1 extra. As a solution I have opted for changing the default threshold to 1E-10 (safety coefficient). With this, if you load Ulrich's frozen sketch, it will give you 3 degrees of freedom, as it should. So it defrost :lol:

https://github.com/abdullahtahiriyo/Fre ... master.git
116f7d8..8eda73d sketcher_testing

This is "a" solution. I will be happy that now DeepSOIC tells me: C'mmon Abdullah, with my second commit you do not need this. Then I will happily undo it :lol:

Please, give it another round of testing a look for problems, so that we know whether we are in the right direction... :D

N.B. 1E-10 is for our tests. We can tune this parameter to something higher if this is the only problem we encounter. I think others won't complain. Also this 1E-10 is relative to the biggest value in the matrix, so if you would have 10 as highest number, the minimum would be 1E-9...
User avatar
DeepSOIC
Posts: 7600
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Tue Oct 07, 2014 4:15 pm

I have tried Ulrich's frozen sketch and it's frozen in my branch. Redundant constraints do their evil.
abdullah
Posts: 3458
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Tue Oct 07, 2014 6:07 pm

DeepSOIC wrote:I have tried Ulrich's frozen sketch and it's frozen in my branch. Redundant constraints do their evil.
Thank you very much for checking this.

Mostly thanks to your first patch, I think we are now reasonably near from a fully working ellipse support. At this moment we need testing and feedback. In my next available coding slot I expect to implement the missing constraints for arcofellipse (like equality). Then at the same time the rest of consteaints and dragging support...

We have a plan :D
User avatar
DeepSOIC
Posts: 7600
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Tue Oct 07, 2014 8:09 pm

I have played a bit with Ulrich's frozen sketch. Interesting it is. If I construct it from scratch by first setting sizes of ellipse and then coincidenting the arc, I end up with a movable thing. If I do the sizes last - unmovable.
The other is that if I save the movable thing to a file, and then reload the file - I get a frozen one.

Remember that derivatives can be only as accurate as the solution is. In the 100% super-precise solution, the constraints are redundant in the matrix. However, if the solution is a bit off - redundant constraints become conflicting in the matrix. So redundancy must be avoided no matter what.
logari81
Posts: 654
Joined: Mon Jun 14, 2010 6:00 pm

Re: Sketcher: Ellipse support

Postby logari81 » Tue Oct 07, 2014 8:16 pm

hi,

I see that you have come quite far with supporting ellipses.
abdullah wrote: 1) When I code, I try to replicate the structures already in place, so that the code is uniform.
that's a good habit. I can give you some hints specifically about freegcs:
- AFAIR I avoided starting variables with capital letters and I avoided underscores. So, X_0, X_1 etc. would rather be written x0, x1 etc.
- I have noticed an enumaration value named "P2OnEllipse". The numer "2" in such names is read "to", so in this case it doesn't make much sense. The name should rather be "PointOnEllipse"
- focus1_X, focus1_Y is not very uniform with the rest notation, I would rather write it focus1.x, focus1.y.

One more substantial observation is about the "ConstraintType" enumaration. One should add values to this enumeration really sparingly. Actually the elements of this enumeration are meant to approximate the minimum number of mathematical primimitives, that the complete set of constraints can be based upon. 11 such primitives where sufficient for building all previously available constraints. That said, adding another six primitives for supporting ellipses and elliptical arcs seems -in a first look- to be a bit too much.

Some other observations:
- I have seen that in a recent patch you compare radii to decide between major and minor radius. From my experience this kind of checks are not robust and indicate that there could be some alternative and more rigorous way to formulate your equations.
- I haven't really investigated that very much but from my intuition a nice way for parametrizing the ellipse would be its center (2 dofs), one point at its intersection with one of its axes (2dofs) and the radius along the other axis (1dof). I do not differentiate which axis is major and which is minor, it shouldn't matter.
- I don't know if compilers have specific optimizations for the pow function, with exponent equal to 2, but one would normally avoid using pow for squares.

Wish you good progress with the rest.
User avatar
DeepSOIC
Posts: 7600
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Tue Oct 07, 2014 8:52 pm

logari81 wrote:- I have seen that in a recent patch you compare radii to decide between major and minor radius. From my experience this kind of checks are not robust and indicate that there could be some alternative and more rigorous way to formulate your equations.- I haven't really investigated that very much but from my intuition a nice way for parametrizing the ellipse would be its center (2 dofs), one point at its intersection with one of its axes (2dofs) and the radius along the other axis (1dof). I do not differentiate which axis is major and which is minor, it shouldn't matter.
Hi!
Well, this is very simple. The major axis is different to minor axis in that foci lie on major axis. Since foci are used in most ellipse-specific constraints so far, it's a good idea to have a permanent major axis (otherwise checks would end up in constraints, much more troublesome IMO).

And finally, the checks arose only because opencascade enforces major>minor and throws an exception if it's otherwise even momentarily. No parametrization can eliminate those checks. There may be a solution to set the new state of opencascade ellipse by a single call to a comprehensive method if there is such a method... To be honest, I haven't tried to find one.

BTW. Do you know why do we have angles in arcs as solver parameters? Angles are really easy to calculate given the endpoints, so why bother the solver to do it?
User avatar
DeepSOIC
Posts: 7600
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Sketcher: Ellipse support

Postby DeepSOIC » Tue Oct 07, 2014 10:32 pm

Abdullah, here's another patch for you! It fixes the creation of internal geometry. I was right - the major diameter line was being created back-to-front.

git commit 5151de6dc508d88a1a6f75b0d745eda1f55780d8The fix.

git commit 094053ab9e80eb740f7590676942614ca216fbb8Removal of 0.99 fudge factor 8-) .

I have an alternative solution to the problem: decide which point goes where during the constraint creation. This should improve the adherence when user manually creates his own line and applies the constraint. But this one may break something...
git commit 40750bc1ea0d1cebfe453a58ad4ed2da6a8fc7bf
User avatar
marktaff
Posts: 47
Joined: Sun Sep 21, 2014 3:25 pm
Location: Seattle, Washington, USA

Re: Sketcher: Ellipse support

Postby marktaff » Wed Oct 08, 2014 5:51 am

After a lot of blood, sweat, and tears, here is my implementation of the DrawSketchHandlerEllipse class (src/Mod/Sketcher/Gui/CommandCreateGeo.cpp), with supporting bits from Abdullah's code.

This implementation has several things going for it:

--drawing an ellipse should look like you are drawing an ellipse (least surprise);
--the points selected to approximate the ellipse take the linear curvature of the ellipse into account, thus producing a better approximation for N points than the more obvious approach Abdullah used;
--the points clicked are points on the ellipse, which makes drawing the ellipse approximately as desired easier, which in my experience makes constraining the geometry less likely to be frustrating;
--circular ellipses are supported right up to the limits imposed by GC_Ellipse and Gui::Command::doCommand(...)*; and,
--it is well documented.

https://github.com/marktaff/FreeCAD_sf_master/tree/main

All of my work takes place in the 'main' branch.

Cheers! :-)

*This kills an edge-case bug that exists in Abdullah's implementation.
Available on chat.freenode.net#freecad while working on FreeCad
abdullah
Posts: 3458
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Wed Oct 08, 2014 12:40 pm

logari81 wrote:hi
hi... nice to meet you... :oops: em... I assume you are the logari81, Konstantinos Poulios, the great developer and creator of CGS and constraints in the current sketcher... nice to meet you!!! :D If feel honoured that you drop by in this thread.
logari81 wrote:I see that you have come quite far with supporting ellipses.
We, FreeCAD, as you know, we are a strong community, we manage to keep it going by contributions from different people. We have faced many difficulties, some because we are not proficient in the understanding of the code, others because mainly I miss the math concepts to see it right. We keep going...
logari81 wrote:that's a good habit. I can give you some hints specifically about freegcs:
Of course, feel free to dig into the code and give me as many hints as you deem necessary.
logari81 wrote: AFAIR I avoided starting variables with capital letters and I avoided underscores. So, X_0, X_1 etc. would rather be written x0, x1 etc.
I understand your concerns, as those are not part of any c/c++ coding style I have ever seen. However, there is a good reason for they being so. The C code in the partials is directly generated by sage from the formulas (saves the human error factor in editing long formulas). This has many other advantanges, as for example improving the formula without any editing (improve, paste the whole, compile). Of course, I could change all the sage worksheet, so that it uses x0 instead of X_0, but when one works with formulas, with most languages, sage included, underscode is used to indicate subindex (I think it is LaTeX inherited), and formulas are much better understood with subindexes. One thing I did is to constrain that syntax to the sections where the formulas generated by sage are copied, as a trade-off between maintaining good coding practices/aesthetics and avoiding to have to reedit otherwise correctly generated formulas.
logari81 wrote:- I have noticed an enumaration value named "P2OnEllipse". The numer "2" in such names is read "to", so in this case it doesn't make much sense. The name should rather be "PointOnEllipse"
Ok. This is clearly a typo that has propagated. I will change this. Thanks!! :D
logari81 wrote:- focus1_X, focus1_Y is not very uniform with the rest notation, I would rather write it focus1.x, focus1.y.
You are absolutely right. I introduced it yesterday. However, I think I can not use focus1.x as name of a variable, but of course I can name it focus1X and focus1Y for consistence...
logari81 wrote:One more substantial observation is about the "ConstraintType" enumaration. One should add values to this enumeration really sparingly. Actually the elements of this enumeration are meant to approximate the minimum number of mathematical primimitives, that the complete set of constraints can be based upon
Sorry. I fail to follow your reasoning. There is no physical limit, AFAIK, for the amount of enums an enum can have (well yes, related to the number of bits of an unsigned int in the given platform, which we are far away from reaching). If what you mean is that, we should reuse primitives as much as possible, avoiding to generate new ones when one can be reused, then I fully agree with you, but I fail to see how I could reuse existing primitives for a rather more complex shape like an ellipse. If you see how I could spare primitives do not hesitate to let me know. I would be more than willing to reduce them.
logari81 wrote:11 such primitives where sufficient for building all previously available constraints. That said, adding another six primitives for supporting ellipses and elliptical arcs seems -in a first look- to be a bit too much.
Well, no offense, but I think this is mainly due to the comparable simplicity of the preexisting element types in comparison with the ellipse. Being able to make a line tangent to a circle by just saying put a line at this distance from the center point of a circle was a piece of cake compared with making a line tangent to the ellipse. This, of course, can be that due to my limited knowledge of geometry I have failed to see further. Really if you can help us here, man! you are more than welcome.

I would try to explain the reasons behind each, if I can recall them...The additional values in the enum are:

P2OnEllipse = 13 => The only way we have come to is to make an specific solver constraint. I do not see how I could do it with existing constraints.

TangentEllipseLine = 14 => same as for the previous one applies.

Point2EllipseDistance = 15 => Hey!!! Thanks man, this was simply not used, part of previous attempts (just removed it)

EqualMajorAxesEllipse = 17 => This could be avoided by selecting other parametrization of the ellipse, where the length of the major axis is a parameter, but would have generated the need of another one, like the minor, or would have brought stability problems (like when we defined it with center, major, minor and phi, where phi is the inclination of the major axis).

EllipticalArcRangeToEndPoints = 18 => the parametrization in an ellipse is with t, the eccentric anomally, I have found no way of doing this with normal constraints. However, it could be removed if we consider DeepSOIC's proposal. I would really ask you for more input with this. I will very much welcome your opinion on why to go in one or other direction, or why not to go in one or another direction.

InternalAlignmentPoint2Ellipse = 16 => This is really the solution we found, so that the UI is not bloated with tons of shape specific constraints (usually needed for complex forms).

As said. I would very much welcome any further input.
logari81 wrote:Some other observations:
- I have seen that in a recent patch you compare radii to decide between major and minor radius. From my experience this kind of checks are not robust and indicate that there could be some alternative and more rigorous way to formulate your equations.
If I may, with all due respect, I think you might have misunderstood the reason of the comparison.

It is not to decide between major and minor in the sense of applying one or the other. It is to decide which one to assign first to the GeomEllipse provided by OCC, so that, once the solver got to the right values for the axes a,b; these are assigned to the major and minor parameters of GeomEllipse in such a way (i.e. in such an order), that in the moment after assigning the first one and before assigning the second one, OCC's GeomEllipse always has a major length higher or equal to the minor length. If that is not the case, GeomEllipse will throw an exception. So, it is not a problem that the solver wants to assign to the ellipse an a<b, it is a problem of the temporal values stored in GeomEllipse, and OCC's limitation that major must be >= minor.
logari81 wrote:- I haven't really investigated that very much but from my intuition a nice way for parametrizing the ellipse would be its center (2 dofs), one point at its intersection with one of its axes (2dofs) and the radius along the other axis (1dof). I do not differentiate which axis is major and which is minor, it shouldn't matter.
I really have to give it a thought. I may even do test implementation... Thanks for the tip!!
logari81 wrote:- I don't know if compilers have specific optimizations for the pow function, with exponent equal to 2, but one would normally avoid using pow for squares.
A modern compiler should optimize it as shown in:
http://stackoverflow.com/questions/6321 ... h-x-double

both produce the same assembly according to the most voted answer.

My reason to have pow instead of a simpler multiplication is related to the fact that sage directly generates the code corresponding to the formula for me. :D

Thank you very much for dropping by. Do not hesitate to drop some more lines if you have the time and energy to do so... I am only happy that after seing what I have done with your files your heart is still beating ;)
abdullah
Posts: 3458
Joined: Sun May 04, 2014 3:16 pm

Re: Sketcher: Ellipse support

Postby abdullah » Wed Oct 08, 2014 1:03 pm

DeepSOIC wrote: Remember that derivatives can be only as accurate as the solution is. In the 100% super-precise solution, the constraints are redundant in the matrix. However, if the solution is a bit off - redundant constraints become conflicting in the matrix. So redundancy must be avoided no matter what.
If the solution is "a bit off" and we can not get to a better solution, I think the solution left to us is to convince the solver that a bit off is ok. In other words, if threshold would be set by default to 1e-30, I am concident other constraints will also fail, because there will be rows with 1e-28... Not that I am defending this solution, because I do not like it, but I think that "avoiding redundancies" is really a much more complicated problem (you would need to call the solver before adding a constraint and after it and deciding whether to include it or not... too complicated)...