general extrusion (imperfect)

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

general extrusion (imperfect)

ctchin
This post was updated on .
I've written an incomplete and imperfect generalized extrusion (arbitrary curve) routine.  

Being rather thick-skulled, I tried writing without checking and learning from the sweep code in github.  So I'm not sure how mine compares to state of the art.  Github is responding extremely slowly for me now and I'm too exhausted...  So I just toss out some result now, maybe I'm making a fool of myself... anyway...

Anyway the calling convention is:

extrude(path, orient) shape();

Where both path and orient are a vector of vectors in the format [[x0,y0,z0],  [x1,y1,z1], [x2,y2,z2], ...]

The each element of path is a point in the arbitrary curve.  Each element of orient is a vector indicating the direction that shape()'s "north" should be pointing.  This module will extrude the 2D shape() along this path keeping shape()'s "north" (as close as possible) to orient's direction.  

Shape() should be a polygon on the X-Y plane.  "North" is defined by the positive Y-axis.  Any 2D primitives, or combination/transformation of 2D primitives can be used as shape().  

The module is incomplete because I still haven't made the joints between segments, BTW number of segments shall be (len(path)-1).  

The module is imperfect because there's a singularity (?) at the N- and S-pole.  I.e. if the path vector swing pass the +Z or -Z axial directions, the orientation of the shape() is liable to become discontinuous.  

I only have energy to make a couple test cases now: Moebius I-Beam (4- or 24-segments versions)  The 4-segment version is ugly be it illustrates clearly the unsatisfactory joints but also shows each segment is twisted to connect the changing orient vectors.  

When I get home I will take a look at github for the "unofficial official version" and its test cases.   I also welcome anyone to post some (torture?) test cases for me to try, see below for format.  For the time being, I don't want to share the source of this work-in-progress.  



ang = [0:15:360];
cs=[for (a = ang) [60*cos(a),0,60*sin(a)]];
os=[for (a = ang) [cos(a/2)*cos(a),sin(a/2),cos(a/2)*sin(a)]];
extrude(cs,os) testshape();

module testshape() {
    translate([-5,-5,0]) difference() {
        square([10,10]);
        translate([-1,1.5]) square([5.25,7]);
        translate([5.75,1.5]) square([5.25,7]);
    }
}
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Parkinbot
This post was updated on .
If you don't want to calculate all your extruding path (and parameter) information you will love multivariate splines. As I just finished my library, which I (painfully) ported from Matlab to OpenSCAD, I can show you some first results:

A = [ 
  [-4.3,    .57,   .1,  .3],
  [-.9,     .32,   1,   .4],
  [1.5,     .07,   .1,  .5],
  [2.5,    -1.48,  -1,  .6],
  [5.6,    -1.68,  -2,  .7],
  [6.6,     1 ,    1.5, .4],
  [4.6,    .5 ,    1,   .3],
  [-1 ,     -2,    1.3, .7],
  [-5 ,     -2,    1.5, 1.8]
  ]*10;

N = 100; 

nS = nSpline(A,N);   // 4D-Spline rasterized

translate([0,0,50])
{
  plot4D(nS);         // 4D-plot, 4th dim is implicit radius
  plot4D(A, "red"); 
}
plot3D(col3D(nS), r=2); // 3D-plot, radius explicit
plot3D(col3D(A), r=3, c="red"); 


By the way, you said: "But I've found porting from Matlab to OpenSCAD to be quite un-painful." Have you ever tried to port some matrix related stuff? Even expressing a simple algorithm with a functional language is just a big mess, and NO FUN AT ALL. Not to mention that the result can't be read anymore.
function L = cholesky1(A)
%%  Cholesky factorization - applies only to symmetric order m band matrix
%   A - matrix to be factorized in sparse lower band representation
%   L - Cholesky matrix in sparse lower band representation
             n = size(A,1);
             L = A*0; 
             for  k = 1: n
                 L(k,2)=sqrt(A(k,2));
                 p=min(k+1,n);
               for ii=k+1:p
                 L(ii,1)=A(ii,1)/L(k,2);
                 for jj=k+1:ii
                     A(ii,2)=A(ii,2)-L(ii,1)*L(jj,1);
                 end
               end
             end


- Rudolf
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

vicnet
Hello,

It's funny because I work also for fun on bezier curve in Openscad.
It put my code in my vcad library (on github).


With same A:
path = [ for (a = A) [a[0], a[1], a[2] ] ];
scales = [ for (a = A) a[3] ];

vtz(50) {
    vduplicate_bezier4(path,s=scales,$fn=25) sphere(1,$fn=25);
    for (a=A) vtr([a[0], a[1], a[2] ]) vblue() sphere(a[3],$fn=25);
}

vduplicate_bezier4(path,$fn=20,s=[2,2]) sphere(1,$fn=25);
for (a=A) vtr([a[0], a[1], a[2]]) vblue() sphere(3,$fn=25);


Vicnet
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Parkinbot
Oh, that is lovely. Looks almost the same!

I suppose Bezier stuff is even more sophisticated than splines. I never dove into it, but I guess the framework to do n-dim interpolation with it should be quite similar and the only difference will be how the core equation system is set up.

Without having looked into your code yet (reading functional code is definitely not, how I want to spend my afternoon), I’d like to ask you for some general information about your approach:

1. I’m using (natural) cubic splines. Do use cubic Beziers (i.e. two control points)?

2. My approach is n-dim over one-dim – i.e. I calculate a line integral as common auxiliary x-dimension and apply an ordinary cubic spline sequence spline2D(x, y_i, N) to any given dimension (y_i) in A. I guess you follow the same way?

3. How do you automatically choose your control points? I guess there is some freedom …  

4. Beyond the different basic approaches, also the common line integral plays an important role, as I’ve found out comparing results calculated on the basis of the Euclidian norm and Eugene Lee's centripetal scheme. How do you calculate yours?

I’m planning to publish my library as part of some thingiverse project, as I have done before with other libraries. But first let me play around with it a bit and do some more testing to see how it reacts to pathological datasets. I’m a fan of fail-safe code. Also, I might extend my code to additionally cover circular curves and special boundary conditions. But if you are interested, I’d send you my current implementation via PM.

Hmm, we might combine our libraries and offer the functions through a "common interface", like:
SN = nSpline(A,N); 
BN = nBezier(A,N); 
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

doug.moen
In reply to this post by Parkinbot
Parkinbot said 'By the way, you said: "But I've found porting from Matlab to OpenSCAD to be quite un-painful." Have you ever tried to port some matrix related stuff? Even expressing a simple algorithm with a functional language it just a big mass, NO FUN AT ALL. Not to mention that the result can't be read anymore.'

OpenSCAD isn't a functional language. The minimum requirement for that is to support functions as first class values, that can be passed as arguments to functions, and returned as results (hence the name "functional"). This is the basis of the rich set of control structures found in functional languages, but missing in OpenSCAD (except that we now have list comprehensions). True functional languages also have either lazy evaluation, or at minimum support infinite lists.

If your starting point is Matlab, these features (first class functions and infinite lists) might not mean much to you. Matlab has only limited support for function values, not enough to support the functional style of programming. And Matlab's generators are not as powerful as infinite lists. But I can assure you that if you are porting a large, idiomatic functional program to OpenSCAD (or to Matlab), then it is going to be very painful, and the translated code will probably be much larger.

OpenSCAD is a declarative language, but it isn't powerful enough to qualify as functional. OpenSCAD is very weak compared to anything that people normally call a programming language, which is why we often claim that it isn't a programming language.

I don't know your specific issues with porting Matlab code, but it is quite possible that your problems are specific to OpenSCAD, and do not generalize to functional programming languages.

And yeah, we could do better in the future. My OpenSCAD2 proposal is a baby step into the world of functional programming. But there is a tricky balancing act involved: making OpenSCAD more powerful without making it too complex and ruining the properties that make it popular for non-programmers.

PS, I know nothing of splines and beziers; it's something I'd like to learn now that I see what you and others are doing with it in OpenSCAD.

On 25 November 2015 at 10:30, Parkinbot <[hidden email]> wrote:
If you don't want to calculate all your extruding path (and parameter)
information you will love multivariate splines. As I just finished my
library, which I (painfully) ported from Matlab to OpenSCAD, I can show you
some first results:


<http://forum.openscad.org/file/n14752/spline_demo.png>
By the way, you said: "But I've found porting from Matlab to OpenSCAD to be
quite un-painful." Have you ever tried to port some matrix related stuff?
Even expressing a simple algorithm with a functional language it just a big
mass, NO FUN AT ALL. Not to mention that the result can't be read anymore.



- Rudolf



--
View this message in context: http://forum.openscad.org/general-extrusion-imperfect-tp14740p14752.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

vicnet
In reply to this post by Parkinbot
Parkinbot wrote
1. I’m using (natural) cubic splines. Do use cubic Beziers (i.e. two control points)?
Yes, 2 controls points, automatically generated (with points before and after one point).

Parkinbot wrote
2. My approach is n-dim over one-dim – i.e. I calculate a line integral as common auxiliary x-dimension and apply an ordinary cubic spline sequence spline2D(x, y_i, N) to any given dimension (y_i) in A. I guess you follow the same way?
I not sure to understand integral...
I use this: https://en.wikipedia.org/wiki/B%C3%A9zier_curve and quadratic bezier curve function to calculate intermediate positions between 2 points and the 2 associated control points.

Parkinbot wrote
3. How do you automatically choose your control points? I guess there is some freedom …  
For each point, take vector from point before to after and apply a weight to get control point before and after.

Parkinbot wrote
4. Beyond the different basic approaches, also the common line integral plays an important role, as I’ve found out comparing results calculated on the basis of the Euclidian norm and Eugene Lee's centripetal scheme. How do you calculate yours?
Oops, I don't understand at all
For norm I use euclidien norm, so the same function in OpenSCAD.

Parkinbot wrote
I’m planning to publish my library as part of some thingiverse project, as I have done before with other libraries. But first let me play around with it a bit and do some more testing to see how it reacts to pathological datasets. I’m a fan of fail-safe code. Also, I might extend my code to additionally cover circular curves and special boundary conditions. But if you are interested, I’d send you my current implementation via PM.
Hmm, we might combine our libraries and offer the functions through a "common interface", like:
SN = nSpline(A,N); 
BN = nBezier(A,N); 
Why not !

a+
Vicnet
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

David Eccles (gringer)
In reply to this post by ctchin
I've also written an 'extrude along path' script. It's a Perl script to
generate an OpenSCAD polyhedron definition that extrudes a polygon
along a specified path. The path and polygon can be specified as
explicit points, or as a function on the parameter t (t = 0 .. 2*pi).

http://www.thingiverse.com/thing:186660

Now that I'm aware how powerful OpenSCAD code can be (see for example
[http://www.thingiverse.com/thing:942566]), I realise it can be
converted to pure OpenSCAD code, but need to put in some more time to
do the porting.

Unfortunately, I can't work out how to get rid of ugly twists in the
extrusion.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Parkinbot
In reply to this post by doug.moen
doug.moen wrote
OpenSCAD isn't a functional language. The minimum requirement for that is to support functions as first class values, that can be passed as arguments to functions, and returned as results (hence the name "functional"). This is the basis of the rich set of control structures found in functional languages, but missing in OpenSCAD (except that we now have list comprehensions). True functional languages also have either lazy evaluation, or at minimum support infinite lists.
Ok, I don't want to get into a paradigm and purism discussion. My concern is very practical and aims at the expressive power I can use to write useful and readable code for designing stuff, I want to design. So let's call it a small subset of a functional language. In your roadmap I can see that you want to brush it up to go further into this direction.
Are you sure, novice programmers will be happy or even able to follow you there? We talk about playing around with vectors, matrices and Euclidian spaces and functions. And about algorithms dealing with those entities. No one wants to juggle around with infinite lists or write a parser or a compiler.
As the subset for now is still very small, I think OpenSCAD’s functions could be also brushed up to go more into the procedural direction, like QBASIC or basic C, which also can live without functional arguments and pointers. Thus allowing for things like statement sequences, local variables and random write access to vectors and matrices, as I already proposed in http://forum.openscad.org/feature-request-plug-ins-tp14663p14721.html
doug.moen wrote
Matlab has only limited support for function values, not enough to support the functional style of programming. And Matlab's generators are not as powerful as infinite lists.
My starting point by far is not restricted to Matlab, which is by the way the most expressive language I have ever programmed with. So forget about this.
doug.moen wrote
But I can assure you that if you are porting a large, idiomatic functional program to OpenSCAD (or to Matlab), then it is going to be very painful, and the translated code will probably be much larger.
I also doubt that, beside the fact that functional programs are unreadable, trying to be elegant at the first place. But this is also not the point.
doug.moen wrote
OpenSCAD is very weak compared to anything that people normally call a programming language, which is why we often claim that it isn't a programming language.
So why not opening it up with a plugin-API, instead of dreaming about an expressive power far beyond Matlab and which 99% of the users will curse at.
doug.moen wrote
I don't know your specific issues with porting Matlab code, but it is quite possible that your problems are specific to OpenSCAD, and do not generalize to functional programming languages.
I’ve given a code example, doing some very usual matrix related steps. Have a try …
doug.moen wrote
PS, I know nothing of splines and beziers; it's something I'd like to learn now that I see what you and others are doing with it in OpenSCAD.
I’m sure this concept can also be useful for you, e.g. to read newer DXF-formats into OpenSCAD or refine meshing.

- Rudolf
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Parkinbot
In reply to this post by David Eccles (gringer)
David Eccles (gringer) wrote
I've also written an 'extrude along path' script. It's a Perl script to generate an OpenSCAD polyhedron definition that extrudes a polygon along a specified path.
Welcome to the club. Wouldn't it be nicer, to be able to just call out?

David Eccles (gringer) wrote
I realise it can be converted to pure OpenSCAD code, but need to put in some more time to do the porting.
Coming from Perl, you might be lucky. But I doubt. My port took twice the time of developing the whole code at first hand.

David Eccles (gringer) wrote
Unfortunately, I can't work out how to get rid of ugly twists in the
extrusion.
Refine your mesh, if you calc all in Perl. If you use linear_extrude() there is a slices parameter to do this. Or you use some interpolation technique like nSplines() or vduplicate_bezier4()

- Rudolf
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Neon22
Given the choice I personally would prefer a Bspline based approach over a Bezier.
- due to the control points affecting the curve locally.

Extrude along path has to make local transformations at each step to avoid the flipping problem created by gimbal locking (Euler interp and fixed rotation order). Else its quaternions and off we go...

So making each extrude be a local coordinate offset from previous one is ideal solution.
Also means we can make adjustments each extrusion - like scale, shape change,...
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Parkinbot
In reply to this post by vicnet
vicnet wrote
I not sure to understand integral...
A line integral is a measure for the length of a line (in our case the polygon defined by the base points). You can use the natural Euclidian norm, called 2-norm, (you say later, you do this), but there are also other choices with calculation schemes.

vicnet wrote
Parkinbot wrote
3. How do you automatically choose your control points? I guess there is some freedom …  
For each point, take vector from point before to after and apply a weight to get control point before and after.
I understand. How do calc the weight? Or is it always the same weight, say 1.1, which may be parametrized?

vicnet wrote
Parkinbot wrote
Hmm, we might combine our libraries and offer the functions through a "common interface", like:
SN = nSpline(A,N); 
BN = nBezier(A,N); 
Why not !
I'll put a note here with a link to the thing, as soon as I've published it!

@Neon22
You said you'd prefer B-splines over beziers. They are a good choice to flatten a polygon, but don't contain the polygon points. Will you implement them? Then we might reserve you some space in the lib

 Rudolf
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

vicnet
Parkinbot wrote
I understand. How do calc the weight? Or is it always the same weight, say 1.1, which may be parametrized?
It is a parameter.

a+
Vicnet
https://github.com/vicnet/vcad
Reply | Threaded
Open this post in threaded view
|

Re: general extrusion (imperfect)

Neon22
Rudolf,
No sorry but it's beyond me. I can make stuff, I know a couple of things, but I'm not a mathematician.

Kochanek splines would get my vote as they are well behaved and the curves go through the knots.
I've used them a lot several years ago(87).
So if implemented using basis function (array) then could have a number of spline types by changing just the basis array.
- https://en.wikipedia.org/wiki/Kochanek%E2%80%93Bartels_spline
Basis array pseudcode:
- http://cubic.org/docs/hermite.htm

Cheers...