feature request: Conical Extrude #273

Closed
elalish opened this Issue Feb 8, 2013 · 60 comments

10 participants

@elalish

conical_extrude(point=[x,y,z])child();

Take any 2D child object and loft it to the specified point off of the horizontal plane. This solid is guaranteed to be manifold, even for 2D objects with holes. Since each edge just becomes a triangle, the algorithm should be pretty simple. Just take a look at what pain Greg had to go through to make his involute bevel gear module. With this feature it would only take one line after his 2D gear shape to make a bevel gear.

I think this would greatly expand what shapes can be easily modeled without taking a lot of computational resources. What do you think?

-Emmett

@GilesBathgate
@nophead
@donbright
openscad member

these files seem like a good starting place.

openscad/src/builtin.cc
openscad/src/linearextrude.cc
openscad/src/PolySetCGALEvaluator.cc 

although i think with a very highly detailed 2d child shape, you might run into 'grid issues' at the very tip top of your pyramid thing, so i'd propose a 'height' parameter as well , defaulting to something like half of the z in the point parameter.

@kintel
openscad member

Another idea would be to add a 2D transformation to linear_extrude() and allow the scale to be 0.
i.e. replace the twist function with a more general transform, or just add a scale to the existing twist.

@elalish

Yes, adding a scale parameter to linear_extrude() along with its twist function would be even more general and allow a really wide class of objects. I really like that option. As for problems with the tip top, I often use r2=0 in cylinder() and that seems to work just fine. Perhaps that method could be used?

While we're on the subject, it would be nice to have $fs affect linear_extrude() with twist in the following way: split up straight lines in the 2D child into segments no longer than $fs before extruding. See this example:

linear_extrude(height=10,twist=90)square([15,1],center=true);

Even if you crank up $fn, it's hard to get a smooth shape because you're only increasing the resolution in one axis.

@GilesBathgate
@nophead
@kintel kintel was assigned Feb 12, 2013
@kintel
openscad member

I whipped up some code to add scale to linear_extrude():
linear_extrude(height=40, twist=45, scale=0.2) square(10, center=true);
Scale can also be 0 for conical objects.

It's currently in the linear_extrude_scale branch: https://github.com/openscad/openscad/tree/linear_extrude_scale

Needed:

  • Adding test cases to the test framework
  • General sanity checking of the idea
  • (dxfdata and polyset is in need of major refactoring)
@elalish

Awesome, thanks, that was fast. Is there anything I can do to help with relatively limited C skills?

One sanity check that would be nice: handling of negative scale factors (applies to cylinders with negative radius too). It's easy with parametrization to accidentally have a radius or scale factor go negative. Currently the object just disappears; it would be nice if it at least gave a warning about a negative value. And maybe clamp it to zero so that there's at least an object to look at?

@kintel
openscad member

I believe I did handle negative scales by clamping to 0.

Did you build the branch in question? - if not, that would be nice :)
We also need some test cases exercising the feature, so that would be a helpful task. i.e. extend this file accordingly (or split it in two files if it gets too messy):
https://github.com/openscad/openscad/blob/master/testdata/scad/features/linear_extrude-tests.scad

@TakeItAndRun

I have some concerns that all conical objects, generated from a 2d base that a) has a hole or b)has seperate 2d primitives will not be 2-manifold.

Please consider the following code for 2 triangles in the x,y-plane, linear extruded to a point on the z-axis:

corners1=[[1,0,0],[2,1,0],[2,-1,0],[0,0,3]];
corners2=-[[1,0,0],[2,1,0],[2,-1,0],[0,0,-3]];

polyhedron(points=corners1,triangles=[[0,1,2],[0,3,1],[1,3,2],[2,3,0]]);
polyhedron(points=corners2,triangles=[[0,1,2],[0,3,1],[1,3,2],[2,3,0]]);

This gives:

Module cache size: 0 modules
Compiling design (CSG Tree generation)...
Rendering Polygon Mesh using CGAL...
PolySets in cache: 3
PolySet cache size in bytes: 1088
CGAL Polyhedrons in cache: 8
CGAL cache size in bytes: 14556
Top level object is a 3D object:
Simple: no
Valid: yes
Vertices: 7
Halfedges: 24
Edges: 12
Halffacets: 16
Facets: 8
Volumes: 3
Total rendering time: 0 hours, 0 minutes, 0 seconds
Rendering finished.
Object isn't a valid 2-manifold! Modify your design. See http://en.wikibooks.org/wiki/OpenSCAD_User_Manual/STL_Import_and_Export

cone

To remove this problem, I would linear (conical) extrude to the one before last step (meaning to a scale close to zero). For the last step do a hull() on the 2d-form and make it into a little pyramid to the top of the linear extrude.

@elalish

Okay, I've managed to install Git, download your source and switch to the linear_extrude_scale branch. However, upon running ./scripts/macosx-build-dependencies.sh, I get a bunch of errors which start with it not finding the basics like stdlib.h and stdio.h, etc. I already had to change my path just to get it to find make, which apparently is due to some reorganization in Mac OS 10.8. I'm guessing this is related? Let me know if you need more details.

@kintel
openscad member

I'm out travelling atm., but will be back Monday. Could you post some more info, e.g. Xcode version, clang version, gcc version. Also, the log messages leading up to the error would be useful. I aim to make the Mac build painless so I'll look into this. I don't yet have a 10.8 box around though.

@elalish

Xcode is up to date (4.6), gcc says: i686-apple-darwin11-llvm-gcc-4.2, and I can't find clang. The error is really long, but I'm guessing the first part is all that really matters (it goes on and on like this):

$ ./scripts/macosx-build-dependencies.sh
Detected Lion or later
Using gcc compiler
Using basedir: /Users/Emmett/openscad/../libraries
Building Qt 4.8.4 ...
/Users/Emmett/libraries/src/qt-everywhere-opensource-src-4.8.4/config.tests/mac/xcodeversion.cpp:42:20: error: stdlib.h: No such file or directory
/Users/Emmett/libraries/src/qt-everywhere-opensource-src-4.8.4/config.tests/mac/xcodeversion.cpp:43:19: error: stdio.h: No such file or directory
/Users/Emmett/libraries/src/qt-everywhere-opensource-src-4.8.4/config.tests/mac/xcodeversion.cpp:44:43: error: CoreFoundation/CoreFoundation.h: No such file or directory

@kintel
openscad member

It might be that Qt needs some extra love to build on 10.8. If you're feeling adventurous, try googling around and see if you can build Qt manually and then adapt the script accordingly. Alternatively, install Qt through some other means and comment out the line which builds Qt in the script.

@elalish

Hmm, not sure I'm that adventurous. This is pretty much the edge of my skillset in this area. In any case, enough people use my scad designs that I pretty much have to stick to a release version anyway.

Back to the feature, would it be possible to allow it to also take a vector argument for scale: [x_scale, y_scale]? This would be more consistent with the rest of the 2D subsystem, and I just started a design that would benefit from it. Thanks, and sorry I'm not of more help.

@kintel
openscad member

What we really want is to perform any 2D transform on the original shape.
We don't support sending module instantiations as parameters, but something like that would make sense - perhaps in a future version where we can change the behavior of the extrude node.

For now, I agree that it would make sense to make scale a vector. Some additional code is needed for corner cases such as one of the dimensions being zero, so it needs some thinking/work/testing.

@elenzil

this is a fantastic feature.
I'm having trouble compiling it on osx tho;
"macosx-build-dependencies.sh" runs for about 20 minutes then fails.

@kintel
openscad member

How does it fail?
Which Mac OS X version are you using?
Which Xcode version?

@elenzil

it generates about 53,000 lines of compile output, then concludes with
"...failed updating 2 targets..."
unfortunately, "error" does not appear in those 53,000 lines.

xcode 4.6.1, osx 10.8.3

I built by:

git clone https://github.com/openscad/openscad.git
cd openscad
source setenv_mjau.sh
./scripts/macosx-build-dependencies.sh

.. note, that's not even the branch in question,
so perhaps i should move to a different forum.

@kintel
openscad member

OK, sounds like a Mountain Lion issue, or smth. to do with your environment.
Can you open a new issue for this?
In the meantime, I'll see if I can find a 10.8 box to test on.

@kintel
openscad member

elenzil: See #335

@jasonwebb

I'm having a hard time understanding how to build from source, but I could REALLY use that linear_extrude_scale function. Any chance someone could compile / release a binary for that? If not, how long might I expect to wait before I can download OpenSCAD from openscad.org and have access to that function?

I'm using Win7 x64, by the way, and as I understand it my platform is more complicated than the others to build for :S

@kintel
openscad member

The feature stalled a bit since it's hard to cover all the corner cases. Simple examples should work in the branch though. It's hard to say when/if this will work - it needs someone to think through it properly and finish the implementation.

In terms of Windows, we build Windows binaries using a cross-compilers on Linux. Building Windows binaries on Windows itself turns out to be a lot harder, paradoxically enough :/
We don't have any Windows users on the development team, so it's hard to do much about that atm...

@NateTG

We don't support sending module instantiations as parameters, but something like that would make sense -
perhaps in a future version where we can change the behavior of the extrude node.

How about using a lookup table? I.e. a vector of ordered pairs [h,[x_scale,y_scale,theta]] and then running conical extrude on a polygon...
i.e.
conical_extrude_xyt(points=[...],edges=[[ ],[ ],..],height=h,slices=n,scaling=[])
...
..

@NateTG

Please consider the following code for 2 triangles in the x,y-plane, linear extruded to a point on the z-axis:
...
corners1=[[1,0,0],[2,1,0],[2,-1,0],[0,0,3]];
...
polyhedron(points=corners1,triangles=[[0,1,2],[0,3,1],[1,3,2],[2,3,0]]);
...

It seems that this fails because the face triangles are incorrectly oriented.

corners1=[[1,0,0],[2,1,0],[2,-1,0],[0,0,3]];
corners2=-[[1,0,0],[2,1,0],[2,-1,0],[0,0,-3]];

polyhedron(points=corners1,triangles=[[0,2,1],[0,1,3],[1,2,3],[2,0,3]]);
polyhedron(points=corners2,triangles=[[0,2,1],[0,1,3],[1,2,3],[2,0,3]]);

Worked just fine for me.

@kintel
openscad member

NateTG:
conical_extrude_xyt(points=[...],edges=[[ ],[ ],..],height=h,slices=n,scaling=[])

looks equivalent to

linear_extrude(height=h,slices=n,scale=[x,y,r]) polygon(points=[...],edges=[[ ],[ ],..])

The latter feels more OpenSCAD'ish.

Otoh, I have a feeling we'll at some point have to introduce a generalized extrusion mechanism, so I'm not too concerned of messing up linear_extrude with more parameters as a temporary measure.

@kintel
openscad member

Also, since this feature has the potential for playing really well with recursion, we should try to get it into the upcoming release.

@NateTG

I was thinking in terms of implementing it as a module.
I meant scale=[[h_1,[x_1,y_1,theta_1]],[h_2,[x_2,y_2,theta_2]...]
So that the scaling can be linearly interpolated with the height like lookup() does.

@kintel
openscad member

elalish: FYI: OpenSCAD should now build fine on 10.8.

@TakeItAndRun
@kintel
openscad member

The current syntax suggestion is:
linear_extrude(height=a, slices=b, twist=c, scale=[x,y]), where twist and scale will be interpolated over the extrusion.

The missing piece is how to deal with situations where either x-scale or y-scale is zero.
If using concave polygons, polygons with holes, or disjoint polygons as a basis, the result will be non-manifold. It will still be printable though, so the manifold requirement is too strict in this case.

Test cases, especially corner cases, are welcome :)

@nophead

Sorry my last comment was rubbish. I didn't realise your manifold comments referred to when the scale gets to 0 and forms a point.

@TakeItAndRun
@TakeItAndRun

I tried the option of limiting the scale to a small number and that worked great:

// scale
s_min=0.00001;
function s0(t)=1-t/(tmax-tmin);
function s(t)=(abs(s0(t))<=s_min)?s_min:s0(t);

I'll posed an example on the mailing list (I cant work out how to include pictures and code here.

@kintel
openscad member

TakeItAndRun: Your assumption is correct. Also, using a minimum scale factor could be a good idea - it's going to be bit of work getting the pyramid thing to work properly.

The concept of manifoldness doesn't correctly reflect printability or even validity of a solid object. There are some special cases where non-manifold objects are perfectly printable, but unfortunately, CGAL doesn't know about 3D printers and won't let us work with such geometry. The typical cases of this are:

  • Donut with no hole
  • two cubes sharing a vertex or an edge

In the future we'll likely allow such objects to be exported, but we still don't have a way of doing CSG operations on them.

@nophead
@kintel
openscad member

Yes, except if they only share an edge, not a face, I don't see how that's not representable physically. The two cubes would merely be touching.
My point in mentioning this was to say that "non-manifold" describes any situation where an edge is used by more or less than two polygons. Some of these cases are obviously degenerate (internal faces or missing faces), but some cases make sense. I'm wondering if there is a mathematical concept for differentiating between these two types of non-manifoldness..

@kintel
openscad member

Merged the first version of this (without TakeItAndRun's epsilon suggestion) into master.
Test cases are missing, so it would be helpful if anyone wants to give it a shot!

I knotted down some notes here:
https://github.com/openscad/openscad/blob/master/testdata/scad/features/linear_extrude-scale-tests.scad

Building Mac binaries as we speak..

@nophead
@elalish
@kintel
openscad member

If we were actually able to keep edges separate, we could indeed represent these as either separate volumes, or separate (but coincident) edges in the same volume. Perhaps there are some functions deep down in CGAL somewhere for making this possible...

PS. New Mac binaries are online.

@MichaelAtOz

TakeItAndRun commented a day ago
I'll posed an example on the mailing list (I cant work out how to include pictures and code here.

See the markdown link up there (when composing/editing) ........................................................................^
or here <- that markup was done as [here](url)

For code use three `s to bracket your code
```
your
code
```
to produce

your 
code

or ` on both sides to bracket in-line code snippet ie that was `in-line code snippet`

For images I just use the select them link below (when composing/editing) to upload an image, alternatively
![Sky Whale - Happy Birthday Canberra](http://www.abc.net.au/news/image/4679766-3x2-700x467.jpg) gives you this (although the Alt Text doesn't seem to do anything)

Sky Whale - Happy Birthday Canberra

and BTW

TakeItAndRun commented a day ago

above was done by a leading > ie >TakeItAndRun commented a day ago

and you can escape any of the special chars
e.g. [words in sq brackets](followed by a url looking thing) with a \
ie \[words in sq brackets]\(followed by a url looking thing)

Oh & p.s. No that is not photoshopped

@NateTG

I wasn't able to find an easy reference for it -- how do I build a branch?

@kintel
openscad member

It's in master now, no need to build a branch..

@NateTG

Hmm... I've got version [2013,5,10] and linear_extrude doesn't seem to handle scale as an argument in syntax highlighting, and I tried to make frustrum, but got a rod. I.e.:

linear_extrude(height=5,scale=5) {
   circle(r=1);
}

produces a rod.

@kintel
openscad member

The scale first appeared in 2013.05.11.

@TakeItAndRun
@GilesBathgate

The best suggestion I heard about a generic linear_extrude is where you specify one or more 2d polyline paths to extrude along. I think the minimum number you need to do anything useful is two. The distance between the lines represents the scale, and the path that the lines follow represents the twist.

Does anyone understand that or do I need to add more explanation?

@TakeItAndRun
@kintel
openscad member

TakeItAndRun: Yes, the scale parameter can be both a scalar and a vector, just as in the scale module, cube module etc.

Allowing a negative scale factor sounds scary..

@kintel
openscad member

Giles: I agree that a generic linear_extrude would make sense. This issue is just a small addition to the existing extrude module.

As TakeItAndRun points out, it needs to be designed properly. I've started thinking about it, e.g. how to allow parametrized functions as parameters, using curves as well as polylines, perhaps merging rotate and linear extrude into a generalized module, and perhaps offer a helper library for the typical special cases. This is a separate discussion though, perhaps I should open a wiki page for collecting this..

@TakeItAndRun
@kintel
openscad member

I see - it's mostly about writing code carefully to make sure polygon winding order gets correctly reverse for negative scale factors.. I'll think about it.

@TakeItAndRun
@NateTG

If you put ``` in front of your code, the it will show as fixed space, which can do wonders for readability:

this is a test
   this is an indented test
      if this had been a real code sample, it might have been useful.
@GilesBathgate

@MichaelAtOz @NateTG Can we stop trying to teach people GitHub Flavored Markdown.

@kintel
openscad member

I addressed the color issue in #366.

@kintel kintel closed this in 71ab237 May 22, 2013
@kintel
openscad member

wops, it auto-closed.
One missing piece: Take a look at negative scale factors

@kintel kintel reopened this May 22, 2013
@kintel
openscad member

OK, negative scales won't make it - we'd need to explicitly find the point of self-intersection and deal with winding orders for negative scales. This would require a bit of work and I'm not convinced it's worth it atm.

@kintel kintel closed this May 22, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment