> 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