Bezier curves?

[Dov Grobgeld]

Hello,

Is there an easy way to define bezier curves in cadquery? What I would like is to have something similar to postscript/svg with intermixed moveto/lineto/curveto/arcto, etc. I.e. would like something like this

```

wire = (qc

            .Wire

            .moveto(100,100)

            .curveto(cp1,cp2,dst)  # cp1,cp2,dst = Vector() or tuple(float,float)

            .arcto((100,100),r))

```

There is spline() which is very powerful, but coming from more of a graphics/font background and not a cad background, miss the simplicity of curveto (Bezier).

If Bezier curves can be imported, there are some nice connections that can be done.

1. Construct from an svg path string. E.g.

```python

wire = qc.Wire.FromSvgPath('M 130 110 C 120 140, 180 140, 170 110')

```

2. Construct from an asymptote [1] string

```python

wire = qc.Wire.FromAsyPath('''

pair [] z={(0,0), (0,1), (2,1), (2,0), (1,0)};
return z[0]..z[1]..z[2]..z[3]..z[4]..cycle;

''')

```

See also the following short demo that I wrote of how to convert from Asymptote to Blender. With Bezier curves it should be easy to convert to CadQuery as well. [2] (Of course you can always linearize the curves, but that I feel would lose too much.)

[1] https://asymptote.sourceforge.io/doc/Paths-and-guides.html

[2] https://github.com/dov/asy2blender

[Neri-Engineering]

I am currently working on a curve generator specifically for SVG.  However it won't be available for another two weeks or so.

The input to my function will be a list of 2D points, at least three of them.

The output will be an SVG "path", with a combination of 'M', 'L', 'Q', and 'C' constructs (the last two being quadratic and cubic curves, with one and two control points respectively).  The function will be REQUIRED TO MAKE A CURVE THAT PASSES THROUGH ALL THE POINTS, WITHOUT MISSING ANY.

I believe that this sort of "problem" has been addressed many times over and over again (kind of like re-inventing the wheel), but I am not satisfied with how it's been done from what I have seen.  (By the way I also reinvented the bicycle wheel, which I had great success with).  The most notable change that my generator will have is that it will "infer" a predecessor point and it will "infer" a successor point, above and beyond the list of points passed.  These inferred points will make some heuristic attempts at preserving the "curvature" at the start and end of path, where as most path generators like this tend to extend the ends with line segments, which isn't acceptable in my opinion  For example, if we have a perfect 2D square with consecutive clockwise vertices being A, B, C, and D, then passing { A, B, C, D, A} to my function will cause it to first "augment" that list, and the hope is that this predecessor/successor function will heuristically determine that the predecessor to the list is exactly D, and that the successor to the list is exactly B.  In other words the function starts out by augmenting the { A, B, C, D, A } list to be exactly { D, A, B, C, D, A, B }, but it does this not by inspecting the elements of the list but rather by computing those end points by a brute force method which has very complex analysis-esque overtones.  In this manner it will be possible to draw something that resembles a circle with only passing the points { A, B, C, D, A} to the function.

Many people who implement B-splines overlook these fine details.  As a result we usually get B-spline code which causes the start and end of path to "straighten out", which I see as being totally wrong.  You want to preserve the curvature at the end of the path.  In tennis they would say "follow through".

[Neri-Engineering]

Sorry, I think I understand your question, and I don't have the answer.

You want to ability to explicitly specify control points explicitly (through which the curve does not necessarily pass) for Cubic or Quadratic curves.

What I was working on was different - I am working from the other side of things, computing the control points where they are not previously known (inferring them).

On Sunday, February 25, 2024 at 2:58:53 PM UTC-6 dov.gr...@gmail.com wrote:

[Neri-Engineering]

I had a look through the class cq.py in the source code.  While there are moveTo(), lineTo(), threePointArc(), and spline() methods, it does indeed appear as if explicitly specifying both cubic and quadratic curves in the form of some sort of curveTo() function seems to be missing, where the control points are explicitly given, whereby the curve itself usually DOES NOT PASS THROUGH THOSE CONTROL POINTS.  The ability to do that is quite important.  In the meantime there is probably some way to use the wrapped object(s) to do it, Adam could tell you more I think.

[Neri-Engineering]

I would humbly suggest adding the following two calls to the API in cq.py.

    def quadraticCurveTo(
        self: T, control: VectorLike, endpt: VectorLike, forConstruction: bool = False,
    ) -> T:

    def cubicCurveTo(
        self: T, control_start: VectorLike, control_end: VectorLike, endpt: VectorLike, forConstruction: bool = False,
    ) -> T:

The curve would typically not pass through the control points (unless curve is degenerate and is a line), but the curve is required to pass through the last point specified by endpt.  The control points determine the tangent of curve at end points, among other things.  These are much needed IMHO.  Typically only cubic curves are used in practice, quadratic not so much.  This way of specifying curves is different from the spline() method, which under the hood most likely ends up utilizing a series of quadratic and/or cubic curves.

[Dov Grobgeld]

Great! Your humble suggestion is exactly what I’d like to see!

I noticed that OCP.Geom2d, which is already used by cadquery/occ_impl/shapes.py has a Geom2d_BezierCurve class, so I guess it shouldn’t be too difficult to implement.

Regards,

--
cadquery home: https://github.com/CadQuery/cadquery
post issues at https://github.com/CadQuery/cadquery/issues
run it at home at : https://github.com/CadQuery/CQ-editor
---
You received this message because you are subscribed to the Google Groups "CadQuery" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cadquery+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cadquery/ce9092eb-3111-4421-ad1f-e5f88e7da574n%40googlegroups.com.

[Neri]

In the meantime there probably exist "hooks" to the underlying layers (OCCT) such that you can "circumvent" the CadQuery API and "talk" directly to the OpenCascade layer.  I am not an expert in that area however.  There exists some mention of that in the online documentation/manual for CadQuery.

[Adam Urbanczyk]

What do you exactly miss in the spline method? You can specify a segment with two points and two tangents.

[Neri]

How?

A spine, when passed four points, is by agreement required to generate a curve that passes THROUGH the points specified.  I believe I tested this very idea in one of my pieces of code, but I could be wrong.

If you want to specify the curve with endpoints and control points, the curve will typically NOT pass through the control points, unless it's a degenerate case such as line.  These are two fundamentally different ways of specifying curves, although the spline method uses the more primitive control point method under the hood, in many cases.  This is my understanding of cubic and quadratic curve segments.

[Dov Grobgeld]

Expanding on Neri's answer, a tangent adds one degree of freedom, whereas a control point adds two degrees of freedom. There are an infinite number of curves connecting two points where the tangents are fixed. This graph shows it:

The blue curves all have the same tangents directions at the left and the right vertices, but they are different Bezier curves. I believe that splines define some kind of a tension parameter which will automatically choose a unique curve.

Another couple of constraints reasons in favor of Bezier curves are:

1. Some people, like me, coming from graphics arts backgrounds, as opposed to CAD backgrounds, are more used to Bezier than to splines. And there is no harm in redundancy for convenience. C.f. move() vs moveto().

2. Writing a constructor like Wire.CreateFromSvgPath('M 100 100 L200 200') etc becomes much easier with Bezier support. This would enable someone to use e.g. inkscape, and draw a curve, and then just copy and paste the path into the above constructor. I could even imagine writing an emacs macro that would launch inkscape on the current path and then save it back in the python source code. :-)

Regards,

To view this discussion on the web visit https://groups.google.com/d/msgid/cadquery/9125922c-ad38-4694-87e5-971dd36d0530n%40googlegroups.com.

[Neri]

Bezier curves are really useful for drawing perfect circular arcs to "fillet" two line segments.  The "fillet" would have a radius.  Usually the lines being connected via circular arc are perpendicular to each other, but of course not always.  Also the cubic Bezier curve is very good at approximating a quarter of a circle (even though it's not perfect).  Cubic Bezier curves are highly preferred over splines in certain situations.  For example you can't really compare driving an automatic Benz to a manual BMW.  I prefer the BMW but not everyone does.

A more insightful discussion of Bezier cubic curves for approximation of circular arcs:  https://stackoverflow.com/questions/1734745/how-to-create-circle-with-b%C3%A9zier-curves

I think that people who prefer the Mercedes automatic would also gravitate towards splines, whereas the people who prefer the manual Porsche would tend to gravitate towards Bezier curves with explicit control points.  It's because with the spline you don't really know how the tangent will be drawn; it's really up the to implementation to decide.

It's interesting that you bring up the SVG path string.  I am currently working on going from the sequence of 2D points and generating a spline which will be expressed as exactly that which you mention: the SVG path string which in my case will only consist of M, L, and C.  Yes, it would be cool to have a constructor that took such a SVG string argument and returned an object type.

I would take these projects on except that for the next two weeks I'm completely focused on the SVG and static image generation in CadQuery, programmatically.  I need another two weeks.  I don't do well with removing the floppy disc from floppy drive while program is executing.  I prefer to finish executing before changing floppy disc.

Written hurriedly, didn't proofread.  Sorry.

[Neri]

I came across some programming gems while trying to write my own [more robust] B-spline code.  Just wanted to share a single piece.  The function computes an arc length of a circle, but the way I specify the inputs is what makes this tricky.  Reason for this function is that I will be doing some kind of comparison of lengths of two circular arcs going in opposite directions of a potential cubic Bezier curve.  This ratio of circular arcs will somehow be used to determine magnitude of control point placement.  That's not important for this discussion; what's neat is just the function below, by itself.  Graphics programming is full of neat little gems like this one.

This has already gone through several iterations of being simplified; I don't know if it can be simplified further, and I don't know how correctly it works, yet.

from math             import acos
from math             import sin

from OCP.gp           import gp_Pnt2d
from OCP.gp           import gp_Vec2d


# Computes the length of the perfect circular arc which starts at point A and
# which arrives at point B sweeping in the direction of specified tangent ray.
# Please note that this may entail taking the long way around the circle,
# depending on the orientation of input values; that behavior is intended.
#
def circular_arc_length(point_A:       gp_Pnt2d,
                        point_B:       gp_Pnt2d,
                        tangent_at_B:  gp_Vec2d):  # Assumed to be normalized.
    #
    # The way we perform this computation is by considering a right triangle
    # formed by three vertices: (1) point B, (2) midpoint M along segment AB,
    # and (3) center C of circular arc.  By symmetry we can show that angle κ
    # is the angle of this right triangle which is opposite seg BM.  The rest
    # should be realized by drawing a pictogram and by analyzing fringe cases.

    AB      = gp_Vec2d(point_A, point_B)
    len_AB  = AB.Magnitude()

    if (len_AB == 0.0): return 0.0

    dot     = AB.Dot(tangent_at_B)  # Dot product might be negative.
              # Function 'acos()' returns a value in range [0,π].
    κ       = acos(min(1.0, max(-1.0, dot / len_AB)))  # Be bounded, be safe!
    sin_κ   = sin(κ)  # Because kappa ∈ [0,π], sin(κ) not negative.
    ε       = 1.0e-7  # Open interval radius for considering sin(κ) to be zero.

    if (abs(sin_κ) < ε):  # Technically we can omit the 'abs()'.
        if (dot > 0): return len_AB
        else: raise ValueError("Circular arc has infinite length.")
    radius  = len_AB / 2 / sin_κ
    arc_len = 2 * κ * radius
    return arc_len


point_A       = gp_Pnt2d( 1.0, 0.0 )
point_B       = gp_Pnt2d(-1.0, 0.0 )
tangent_at_B  = gp_Vec2d( 0.0,-1.0 )
print(circular_arc_length(point_A, point_B, tangent_at_B))

[Neri]

I am stumbling upon many, many programming gems which are needed to implement my B-spline library.  Here is a simple one, of which only the API description is included, not the implementation.  I am wondering if there is something like this in OpenCascade?

# Returns the center point of circle which passes through A, B, and C.  If the
# three input points are such that there exists a line which contains (or
# nearly contains) the three input points, then the special Python 'None' value
# is returned instead.
#
# Regarding degenerate cases: the only thing that this code inhibits is a
# division by zero.  Otherwise the computation will proceed.  Therefore, the
# caller may specify an 'epsilon' value which, if set to be strictly greater
# than zero, will filter out results where bounding box perimeter ratios are
# less than epsilon, by returning the special Python value 'None' in those
# cases.  The perimeter ratio compared is the ratio of bounding box perimeter
# containing only A,B,C versus perimeter of bounding box containing A,B,C,Ψ,
# where Ψ is the computed center of circle.  This is a post-computation
# filtering approach which excludes results that are blowing up towards
# infinity.  Setting 'epsilon' to be closer to zero will cause circle centers
# that are further away to be accepted as accurate.  A good value for epsilon
# [in my opinion] is in the range of 1e-5 to 1e-6.
#
def compute_circle_center(point_A: gp_Pnt2d,
                          point_B: gp_Pnt2d,
                          point_C: gp_Pnt2d,
                          epsilon: float= 1.0e-6) -> gp_Pnt2d:

My opinion of OpenCascade is that it's very powerful when used properly, but there are many unimplemented APIs, or the implementation does not agree with what the API states, or the implementation is outright buggy.  Using OpenCascade is akin to stepping through a field of landmines in order to reach the ultimate paradise; you need to be very careful where you step but the outcome is very wonderful.

There is another sub-problem "gem" that I've also solved, and this one is too complicated so even the API comment is too big to include here, so I'll state it in plain English while omitting the details of how to handle degenerate or fringe cases.

You have four points A, B, C, D in 2D given as inputs.  Return an affine 2D transformation, based on those four input points, which causes the transformed points A', B', C', D' to lie perfectly on a circle.  The definition of an affine transformation in 2D is that a pair of parallel lines gets transformed to parallel lines, and that there is an inverse to the transform.

This is a non-trivial problem and I have the solution, which is needed to properly implement elliptical B-spline curves.  I have no idea what OpenCascade or what other implementations employ.  The main computation involves a transcendental [I think] formula which cannot be expressed in closed form; a binary search approach, taking at most 48 or so steps, is employed to come up with a numeric value for the "shear" operation.

The reason I need this ability is for curve prediction and curve fitting.  If I am given a sequence of points A, B, C, D, E, F... which all more or less lie on an elliptical curve, or where sections of it lie on elliptical curves, then I want to return a B-spline which preserves those elliptical curves as much as possible.  This all boils down to my desire to draw perfect SVG curves for outline drawings that employ the perspective projection: https://github.com/CadQuery/cadquery/issues/1524 .

[Dov Grobgeld]

I got my first POC working which is turning a Bezier curve into a CadQuery Wire. The result is here:

https://gist.github.com/dov/8dc6882edafc379cb1754aedf0b014b0

Based on this it code it should be straightforward to build a "constructor" taking a SVG path string and turn it into a cadquery wire.

I'm sure it can be integrated better more idiomatically into CadQuery though...

Regards,

To view this discussion on the web visit https://groups.google.com/d/msgid/cadquery/c701b825-3445-4c55-adfe-4ef2dba1323an%40googlegroups.com.

[Neri]

Ah wonderful.  I hope that the scaling of control points as you accept them is consistent with the standard way of doing this.

For example if you pass these as inputs:

1316.00,   39.00
1335.88,   39.00
1352.00,   55.12
1352.00,   75.00

Then it should approximate a quarter circle very closely.  That is assuming all your code is using the

kappa = tangent(90°/4)*(4/3) = 0.55228475

strategy and/or scaling factors for control points when trying to draw quarter circles (and you scale that for larger or smaller arcs, proportionately).  You never know what this code is doing under the hood until you look at it.  BTW what's 'POC'?

[Dov Grobgeld]

Hi Neri,

Yes, these are "standard" bezier coordinates, and indeed inserting your example points creates a curve visually indistinguishable from quarter of a circle.

POC = Proof Of Concept - I should have spelt it out.

Regards,

To view this discussion on the web visit https://groups.google.com/d/msgid/cadquery/bc2b51e6-a853-4cfe-95b3-f9a38b6c6d15n%40googlegroups.com.

[Neri]

Sunday morning math problem.

            # An interesting mathematical hypothesis/question is as follows.
            # Given 2D points A=(-1,0), B=(1,0), and C=(Cx,1) and given a pure
            # "shear along x" 2D affine transformation 'Tr' with some nonzero
            # numeric shear value, will Tr(Circle(A,B,C)), which is an ellipse,
            # be "contained" by Circle(A,B,Tr(C)) when only considering the
            # area above y=0?  How about if we only consider the area above
            # y=1?  Please note that Circle(Tr(A),Tr(B),Tr(C)) is equal to
            # Circle(A,B,Tr(C)) due to the nature of shear transformations.

I wonder if there is a "math forum" somewhere.  My brain is over-taxed with these sorts of problems at the moment.

Some puzzles are fun but too many are too many.

[Dov Grobgeld]

Neri, try MathExchange

To view this discussion on the web visit https://groups.google.com/d/msgid/cadquery/6bdbb8a6-b979-4592-b528-ca67545dcf0an%40googlegroups.com.

[Dov Grobgeld]

Bezier continuation!

I got curveTo() working for a cubic bezier! 

It has the same semantics as the SVG (and postscript) curveto commands. I.e. it starts from the current point, adds two control points, and lands at the final x,y coordinate.

Here's an screenshot:

I'll prepare a pull request in the next few days.

Regards,

[Neri]

That is really, really awesome and in my opinion much needed functionality.

Just a few technical questions for you.

(1) I understand that there is an implicit moveTo(0,0) to start off.  That's okay.  You're allowing the omission of explicitly stating that.  It's how the rest of CadQuery works I think.  Everything starts at the origin, usually.

(2) You've added an explicit close() which is like the 'Z' in SVG.  The 'Z' in SVG is optional, and if omitted will not close the path.  Are you allowing for paths that are closed manually, and are you allowing for paths that are open?  In your code, had you omitted the close() it would have been a manual closing of the path because you are explicitly returning to the origin via cubic curve.

(3) The six-arg cubic curveTo() is great, but for clarity are you planning to expose a three-arg version, which accepts some kind of 2D point data types?  Not sure what that data type would be in CadQuery at the moment.  I know in OpenCascade it's gp_Pnt2d, but things are generally kept separate; exposing OpenCascade details in CadQuery API is frowned upon.

(4) Perhaps offer an alias to curveTo() named cubicCurveTo() for clarity, because I was wondering if there will be a quadraticCurveTo(), which may or may not be necessary.  It's available in SVG but in general it's very difficult working with quadratic curves, and may not be necessary altogether.

(5) Will you offer support for drawing these kinds of curves with a Z coordinate specified?  I don't even know where that would be applicable; certainly it would not be good for extrusions as you've demonstrated in your example.  However, in my metric thread library (here: https://sourceforge.net/p/nl10/code/HEAD/tree/cq-code/common/metric_threads.py ) I am constructing a wire [or something] via makeHelix() and then I do a sweep() of a thread profile through that helical path, e.g. with isFrenet=True .  I could certainly see myself replacing the makeHelix() with a sequence of Bezier curves that you expose.  In other words THERE WOULD BE A NEED for 3D points being specified, I feel.  I think the 3D paradigm is analogous to the 2D paradigm, and it would be my expectation that OpenCascade allows that to be specified in their underlying cubic Bezier curves.

I don't mean to be a stickler but my habit in programming is to be excessively "retentive" if you know what I mean.  I like to proofread and proofread all of my code, imagining situations that may come up before they do in actual usage.  I like to cross my i's and dot my t's when it comes to specifying the API first and foremost; I like to imagine scenarios and model things before problems occur; the implementation bugs and complications in code are secondary in my opinion.  How do you feel about my points above?  Just wondering.  Are we going to use the FreeBSD approach or the Linux/GNU approach here.  It's a difference in philosophy of course.  I also don't mean to be domineering or control-freakish.  The Linux camp is okay with making incremental improvements that aren't perfect, while the FreeBSD camp prefers an "all or nothing" approach, where they usually strive for perfection.

[Adam Urbanczyk]

Hey, thanks, but could you actually answer my question? What do you miss in the spline method in CQ (i.e. cq.Workplane.spline)?

BTW: Bezier curve *is* a B-spline with a specific knot vector.

[Dov Grobgeld]

Oops. This answer should have gone to the list.

Hi Adam,

I thought I answered what I miss in the answer that you quoted. :-) Even if they are mathematically the same, coming from a more graphic arts background, I find expressing the curve in terms of Bezier outlines more natural. And what's wrong with a bit of redundancy in the API if it caters to people from different backgrounds? 

If you don't agree, I'd be interested to hear why?

Regards,

To view this discussion on the web visit https://groups.google.com/d/msgid/cadquery/80123428-efd2-40d1-9a10-8f463cc87954n%40googlegroups.com.

[Dov Grobgeld]

Hello,

I just created a pull request for my Bezier changes. Feel free to comment. See:

https://github.com/CadQuery/cadquery/pull/1529

Regards,

[Neri]

Yes, it's possible to implement a Bezier/control-point curve using B-splines as the underlying implementation [usually].  However in many cases the end-user using the "knot" B-spline method of specifying curves does not know the exact algorithms used to implement that B-spline, let alone how the tangents at endpoints are handled (e.g. elliptical curve prediction or asymptotic to line segment are two obvious choices).  So to go from B-spline as the underlying "machinery" to Bezier/control-point as the high level user-API, it's not only "undoing" what is done in the implementation but it also leaves a lot of guesswork as to how the B-spline you're working with uses Bezier curves under the hood.  (Usually, I assume, Bezier curves are used as the low-level building blocks, and not the other way around.)  In many cases the B-spline implementations don't spell out in excruciating detail how the curves are chosen based on knots.  Sometimes they do spell this out.

For example I am in the process of implementing a B-spline [which of course uses Bezier cubic curves as the underlying low-level mechanism] which uses elliptical curves to decide on how to handle the "knots".  Yes, the B-spline WILL pass through the B-spline points, but this method is completely different from most methods that implement B-splines [I think].  It would be unreasonable to implement a Bezier-style library (where control points are specified, not necessarily where the curve will pass through) on top of my elliptical-approximating B-spline library.