Minkowski extrude has possibilities...

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

Minkowski extrude has possibilities...

Dan Zuras 3D
> Message: 2
> Date: Mon, 30 May 2011 15:16:06 +0530
> From: Jayesh Salvi <[hidden email]>
> Subject: Re: [OpenSCAD] Python library for Solid Modelling - Cadmium
> To: [hidden email]
>
> On Mon, May 30, 2011 at 3:03 PM, Triffid Hunter
> <[hidden email]> wrote:
> > On Sun, May 29, 2011 at 12:18 PM, Jayesh Salvi <[hidden email]> wrote:
> >> On Sun, May 29, 2011 at 2:11 AM, Giles Bathgate
> >> <[hidden email]> wrote:
> >>> Have you implemented a way of doing linear extrude? I am currently
> >>> having trouble getting RapCAD's linear extrude module to work
> >>> optimally.
> >> Not yet. Currently I've managed to implement only the CSG operations
> >> and affine transformations. I'll check how linear extrusion algorithm
> >> works.
> >
> > Isn't linear extrude as simple as duplicating all the 2d object's
> > vertices along lines parallel to the normal and connecting edges as
> > appropriate to form faces?
>
> That would be one way to implement it. But I think a more generic way
> is to use Minkowski sum
> http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Minkowski_sum_3/Chapter_main.html

        If you are going to go the route of a Minkowski sum to
        implement linear extrude, then extruding with a twist
        becomes easy to generalize to more interesting things.
        Perhaps if this were generalized in such a way as to
        give the user the ability to combine 1D & 2D objects
        under Minkowski sum (as well 2D x 2D et al) it would
        lead to a more interesting tool.  Just a suggestion.  - Dan

Reply | Threaded
Open this post in threaded view
|

Re: Minkowski extrude has possibilities...

Giles Bathgate-2
On 30 May 2011 18:14, Dan Zuras 3D <[hidden email]> wrote:
>        If you are going to go the route of a Minkowski sum to
>        implement linear extrude, then extruding with a twist
>        becomes easy to generalize to more interesting things.
>        Perhaps if this were generalized in such a way as to
>        give the user the ability to combine 1D & 2D objects
>        under Minkowski sum (as well 2D x 2D et al) it would
>        lead to a more interesting tool.  Just a suggestion.  - Dan

Oh Right, I forgot to mention that RapCAD can already do a minkowski glide

minkowski(){
        polyline([[0,0,0],[0,10,10],[20,10,10],[30,20,20]]);
        cube([10,10,10]);
}

http://www.rapcad.org/wordpress/wp-content/uploads/2011/05/Minkowski-Glide.png

There is also the glide() module which does something slightly different.

Regards

Giles.

Reply | Threaded
Open this post in threaded view
|

Some of those possibilities...

Dan Zuras 3D
> Date: Mon, 30 May 2011 18:28:09 +0100
> Subject: Re: [OpenSCAD] Minkowski extrude has possibilities...
> From: Giles Bathgate <[hidden email]>
> To: Dan Zuras 3D <[hidden email]>, [hidden email]
>
> On 30 May 2011 18:14, Dan Zuras 3D <[hidden email]> wrote:
> > If you are going to go the route of a Minkowski sum to
> > implement linear extrude, then extruding with a twist
> > becomes easy to generalize to more interesting things.
> > Perhaps if this were generalized in such a way as to
> > give the user the ability to combine 1D & 2D objects
> > under Minkowski sum (as well 2D x 2D et al) it would
> > lead to a more interesting tool.  Just a suggestion.  - Dan
>
> Oh Right, I forgot to mention that RapCAD can already do a minkowski glide
>
> minkowski(){
> polyline([[0,0,0],[0,10,10],[20,10,10],[30,20,20]]);
> cube([10,10,10]);
> }
>
> http://www.rapcad.org/wordpress/wp-content/uploads/2011/05/Minkowski-Glide.png
>
> There is also the glide() module which does something slightly different.
>
> Regards
>
> Giles.

        This is nice but I was thinking of something more ambitious.
        For example one could:

                Run a Minkowski sum in cylindrical coordinates to
                make torii & knots by crossing a 2D figure in the
                theta = 0 x Z plane with a 1D figure that wraps
                generally in theta.

                Or (also in cylindrical coordinates) one could
                cross a 2D figure in the Z = 0 plane with a 1D
                figure going generally in Z in which the theta
                of that latter figure is the theta used in the
                cross & the r is the scale factor rather than a
                displacement.

                Or (in any coordinate system) one could cross
                2 figures (of any kind) together with a scalar
                function (or Z or some parameter that goes from
                0 to 1 say) that scales them both.

                Or consider any 3D figure as a 2D figure that
                changes in the remaining coordinate (say Z) as if
                it were a parameter that goes from 0 to 1 to be
                crossed with any other figure similarly reimagined
                (in, say Y) as a series of parameterized Minkowski
                sums to be unioned together into the resulting
                figure.

                Or more general Minkowski sums in any coordinate
                system.

        I can't figure out a good use for spherical coordinates in
        such a sum but I suspect there are more imaginative people
        out there who can.

        Anyway, I was just suggesting that if ordinary extrudes were
        based on a specific application of some fairly general forms
        of Minkowski sums, it might make for a better tool all around.

        And less computationally intensive than crossing 3D figures
        with each other.

        That's the idea.

        I don't know if its too ambitious to code though.

        That's up to you.

        Yours,

                                    Dan

Reply | Threaded
Open this post in threaded view
|

Re: Some of those possibilities...

Giles Bathgate-2
On 31 May 2011 01:35, Dan Zuras 3D <[hidden email]> wrote:
>                Or more general Minkowski sums in any coordinate
>                system.

Like I mentioned before the main barrier here is that CGAL insists for
minkowski that one of the operands be "fully dimentional" so any kind
of sum consisting of a 2D polygon summed with a "1D figure that wraps
generally in theta." (whatever that means) or a 2D polygon summed with
another 2D polygon, using the library we are using its not possible.

The only examples that are possible are 3D polyhedron summed with
another 3D polyhedron, or a 3D polyhedron summed with 3D polyline.

There is of course

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Minkowski_sum_2/Chapter_main.html

But then this also has the limitation that the output of the sums can
only exist on the XY plane, and so still you can't implement your
vision.

>  I don't know if its too ambitious to code though.

I'd say... I think it would mean re-implementation of minkowski, or
modifying upstream code. Its too ambitious for me anyway.

Regards

Giles

Reply | Threaded
Open this post in threaded view
|

Re: Some of those possibilities...

Dan Zuras 3D
> Date: Tue, 31 May 2011 09:33:14 +0100
> Subject: Re: [OpenSCAD] Some of those possibilities...
> From: Giles Bathgate <[hidden email]>
> To: Dan Zuras 3D <[hidden email]>, [hidden email]
>
> On 31 May 2011 01:35, Dan Zuras 3D <[hidden email]> wrote:
> >         Or more general Minkowski sums in any coor=
> dinate
> >         system.
>
> Like I mentioned before the main barrier here is that CGAL insists for
> minkowski that one of the operands be "fully dimentional" so any kind
> of sum consisting of a 2D polygon summed with a "1D figure that wraps
> generally in theta." (whatever that means) or a 2D polygon summed with
> another 2D polygon, using the library we are using its not possible.
>
> The only examples that are possible are 3D polyhedron summed with
> another 3D polyhedron, or a 3D polyhedron summed with 3D polyline.

        Ah, the minkowski sum from graph theory is somewhat more
        general.  Of course, it only deals with points & lines.

        As I recall...

        If G1 = {P1,L1} where p1(i) is in P1 for i in [1,i1] &
        l1(i,j) in L1 implies that there is a line from p1(i) to
        p1(j) & the same for a G2 = {P2,L2} then the minkowski
        sum G1 (+) G2 is {P12,L12} where p1(i) + p2(j) is in P12
        for all i in [1,i1] & j in [1,i2].  And there is a line
        from p1(i) + p2(j) to p1(i') + p2(j') if i = i' & l2(j,j')
        is in L2 or j = j' & l1(i,i') is in L1.

        But you also have to deal with surfaces as well as the
        effective union of all these things.

        Hmm...

        Now that I look at this definition I realize that the
        surfaces of a minkowski sum are bounded by the lines from
        p1(i) + p2(j) --> p1(i') + p2(j) --> p1(i') + p2(j') -->
        p1(i) + p2(j') --> p1(i) + p2(j).  So the original surfaces
        can be ignored.  I think I have that right.  Can someone
        check that?

        Nope.  That's wrong.  One must also include all surfaces in
        G1 crossed with points in G2 & vice versa.  Otherwise holes
        would not come out correct.  And any hope of a consistent
        orientation is totally lost.

        The union still has to be done but I think that's correct.

        Oh, and what I meant by summing in another coordinate system
        was just that: do the sum in those coordinates.  So that a
        2D figure in the Z x theta = 0 plane when crossed with the
        line that goes from (r=1,theta=0,z=0) to (r=1,theta=5,z=0)
        only adds 5 degrees to the theta of every element of the 2D
        figure.  That 'translation' in cylindrical coordinates amounts
        to a rotation in cartisian coordinates.  Thus tori & knots
        become easy.

>
> There is of course
>
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Minkowski_sum_2/Chap=
> ter_main.html
>
> But then this also has the limitation that the output of the sums can
> only exist on the XY plane, and so still you can't implement your
> vision.

        Its not so much that.  A minkowski sum has no notion of
        dimensionality attached to it.  It is that if you start
        with two figures in the same plane then all the sums of
        points from one figure added to points in the other are
        also in that plane.

        (Strictly speaking, figures in parallel planes result in
        a figure in a third parallel plane.)

        That is what limits the result to 2D.  If you crossed a
        figure in one plane with a figure in another you would
        get a sum that spans the space formed by those planes.

        (Again, strictly speaking, crossing two plane figures in
        two NON parallel planes results in a figure that spans
        the extent of those figures in 3D.)

        Thus having both figures in the same plane is a
        degenerate case.  (And figures in the Z=0 plane are
        doubly degenerate.)

>
> >  I don't know if its too ambitious to code though.
>
> I'd say... I think it would mean re-implementation of minkowski, or
> modifying upstream code. Its too ambitious for me anyway.
>
> Regards
>
> Giles

        Yeah, I can see that if you're grabbing this from CGAL
        rather than doing it from scratch, you have to live with
        the limitations you're given.

        Ah, well, too bad.

                                Dan