
12

The attached code implements another strategy to generate complex shapes. It avoids boolean operations, and thus can speed up shape generation by a factor of 100010 000 times, reducing rendering times from hours to seconds. The code is workinprogress, and as such is likely to contain bugs. Please feel free to tell me. It has been developed using OpenSCAD 15.3.
The code is based upon the idea that polyhedron(vertexlist,facelist) needs two lists to create any possible shape. The list of vertices is user defined, and from this list the list of faces is automatically generated.
To do so, the shapetobegenerated is built up of a list of vertices, called a slice, having the same z coordinate. These slices are then stacked one on top of the other, by concatenating the lists of slices into a single vertex list and changing the z coordinate, to generate the shape. Since changing the z coordinate amounts to moving the slices around in space, this is the time to change the x and y coordinates as well, implementing a shearing action.
This is as far as the code presented goes.
Language use: implementing rotations and translations using lists of vertices differs substantially from rotating and translating shapes. To do so in OpenSCAD, functions have to be nested one in another, making for code that is difficult to read and maintain. Thus, I replace rotating and translating with tilting and moving, as an outside recognition that the words carry the same meaning only insofar their effects on the outside (i.e. on the eventual shape) are concerned. The inside effects (i.e. on how the code is designed to obtain the desired results) are very different.
Tilting the slices has so far not been implemented: Tilting the slices in space is more demanding, since unless the tilting axes are carefully chosen, the resulting shape will be unrecognizably distorted.
Results: To create this shape generated this output:
Rendering Polygon Mesh using CGAL...
Geometries in cache: 2
Geometry cache size in bytes: 14421616
CGAL Polyhedrons in cache: 0
CGAL cache size in bytes: 0
Total rendering time: 0 hours, 2 minutes, 7 seconds
Top level object is a 3D object:
Simple: yes
Vertices: 100200
Halfedges: 592184
Edges: 296092
Halffacets: 391788
Facets: 195894
Volumes: 2
Doing the same shape without the centre hole generated this output:
Rendering Polygon Mesh using CGAL...
Geometries in cache: 2
Geometry cache size in bytes: 28814128
CGAL Polyhedrons in cache: 0
CGAL cache size in bytes: 0
Total rendering time: 0 hours, 0 minutes, 5 seconds
Top level object is a 3D object:
Facets: 200396
For both runs, the cache has been flushed beforehand.
Let me know what you think
wolf
// Reverse Slicer
// build a complex shape from user definable functions
// as a faster alternative to multiple unions
// Start user definable data
$fn=100;
Slices=1000;
SliceAngle=[for( i=[0:1:Slices1]) [3.6*i,0,0]]; // angle by which each slice is tilted, currently not implemented
SlicePosition=[for( i=[1:1:Slices]) [0,0,(i1)/50]]; // position of each slice relative to origin
SliceRadius=[for( i=[1:1:Slices]) 10/pow(i,.3)];
function CircularSlice(r=1)= // returns a list of vertices, called a slice, centered around the origin, by which a circle of radius r and height 0 will be approximated
[let(Step=360/$fn) for( i=[0:1:$fn1]) [r*cos(i*Step),r*sin(i*Step),0]];
// End user definable data
// Start generating list
Offset_X=flatten([for( i=[0:1:Slices1]) MinElement_X(CircularSlice(SliceRadius[i]))]); // list of all slices needed to construct shape
VertexList=flatten([for( i=[0:1:Slices1]) MoveSlice(CircularSlice(SliceRadius[i]),SlicePosition[i])]); // list of all slices needed to construct shape
EndFace1=[for( i=[2:1:$fn1]) [0,i1,i]]; // list of all triangular faces needed to close shape at one end
EndFace2=[let(F=(Slices1)*$fn) for( i=[F:1:F+$fn3]) [F,i+2,i+1]]; // list of all triangular faces needed to close shape at other end
SideFaces=flatten([for( i=[0:1:$fn1]) for( k=[0:1:Slices]) [[i+k*$fn,(i+$fn)+k*$fn,((i+1)%$fn)+k*$fn],[((i+1)%$fn)+k*$fn,(i+$fn)+k*$fn,((i+1)%$fn+$fn)+k*$fn]] ]);
FacesList=concat(EndFace1,SideFaces,EndFace2);
function MinElement_X(Sl,A)= // Element of slice farthest out on negative y axis, defines distance of tilting (rotation) axis from x axis
min([for( i=[0:1:$fn1]) let (m=ExtractSlice(Sl,i)) m[1]]);
function flatten(l) = [ for (a = l) for (b = a) b ] ;
function ExtractSlice(List,Element)=flatten([for( i=Element) List[i]]); // extract a vector from a slice
function MoveSlice(Sl,SP)= // move slice to [x,y,z]
[for( i=[0:1:$fn1]) let (v=ExtractSlice(Sl,i)) [v[0]+SP[0], v[1]+SP[1], v[2]+SP[2]]];
// end generating list
// generate shape from list
//difference() { // test for CSG compatibility
polyhedron(VertexList,FacesList);
//cylinder(h=1000,r=1);}


I've played around with this approach for a while http://www.thingiverse.com/thing:900137and connected it with some interpolation scheme http://www.thingiverse.com/thing:1208001into a very general solution.
Also this works astoundingly well, the solution completely ignores the wicked self intersection problem, by leaving all burden to the user. It executes amazingly fast for the price that it can not be formalized into a general pattern without a lot of effort (also in time).
The implementation you show, could indeed find its way into the language e.g. in the sense of a more flexible linear_extrude() taking a vector of polygons plus a height for equidistantanly or even a height vector for freely Zextruding along the polygon shapes. Also this is a linear scenario the operator will have to fight with welldefinedness of the polygon sequence:
1. each polygon has to be tested to be simple
2. the sequence has to be tested for selfintersection which is not trivial. I guess, you will have to
restrict the (simple) polygons to be convex, which is a strong restriction and even then you will have to employ some intelligent scheme for triangulation between the layers (see skin()).
In my eyes, a first generalization step for language integration could be to allow for a linear_extrude() with a height or/and a scale vector (or a userdefined function) describing the Z coordinates and the scale of the slices. Maybe also twisting could be done this way.
Any *bending or rotation* will introduce nonlinearity and a hole bunch of selfintersection issues.
Another much easier approach could be an operator that just piles a set of 3Dshapes on top (or aside) of each other using the first one (or z=0) as base. This will avoid the intersection and union problem by definition and all knitting can be done before entering CGAL. See this example (which is kept in 2D, because zcoordinate of a 3D shape cannot be quested in current OpenSCAD to grand for noninterscection).
Z_pile(100)
{
square(10, center = true);
square(20, center = true);
square(30, center = true);
square(10, center = true);
}
module Z_pile(h = 100)
{
echo($children);
dh = h/$children;
for(i=[0:$children1])
translate([0, 0, i*dh])
linear_extrude(height = dh)
children(i);
}


Hi, Wolf.
I have been using this approach a lot. Bellow you will find an experiment I did that helped me to debug the equations of two deformations: twist and taper. In the code, I define a module to twist a polyhedron with triangular faces and a function that taper a similar kind of polyhedron. The faces are subdivided and the deformation is applied to each vertex of the subdivision. This is the result:
and here is the code:
deform.scadAs you may see, the function and the module let to the user the burden of triangulating the nontriangular faces of the polyhedron. And, as Parkingbot pointed out, it doesn't check for selfintersections that is hard to implement and process. Finally if the polyhedron data doesn't define a manifold, the deformed object will not be acceptable by CGAL.
Ronaldo


I am now in a position to quantify my claims about improved rendering speed. Parkinbot publishedhas published a routine to generate a coil. When set to 200 slices per winding and 10 windings, this routine renders on my machine in 52 minutes. The equivalent coil, also having 2000 slices, renders in 11 seconds using my approach:
// Reverse Slicer
// build a complex shape from user definable functions
// as a faster alternative to multiple unions
// Start user definable data
$fn=100;
Slices=2000;
SliceAngle=[for( i=[0:1:Slices1]) 1.8*i]; // angle by which each slice is tilted
SlicePosition=[for( i=[1:1:Slices]) [0.125*i,50,0]]; // position of each slice relative to origin
SliceRadius=[for( i=[1:1:Slices]) 10];
function CircularSlice(r=1)=[let(Step=360/$fn) for( i=[0:1:$fn1]) [r*cos(i*Step),r*sin(i*Step),0]]; // returns a list of vertices, called a slice, centered around the origin, by which a circle of radius r and height 0 will be approximated
// End user definable data
// Start shape generating list
VertexList=flatten([for( i=[0:1:Slices1])
TiltSlice_X(MoveSlice(CircularSlice(SliceRadius[i]),SlicePosition[i]),SliceAngle[i])]); // list of all vertices needed to construct shape
EndFace1=[for( i=[2:1:$fn1]) [0,i1,i]]; // list of all triangular faces needed to close shape at one end
EndFace2=[let(F=(Slices1)*$fn) for( i=[F:1:F+$fn3]) [F,i+2,i+1]]; // list of all triangular faces needed to close shape at other end
SideFaces=flatten([for( i=[0:1:$fn1]) for( k=[0:1:Slices]) [[i+k*$fn,(i+$fn)+k*$fn,((i+1)%$fn)+k*$fn],[((i+1)%$fn)+k*$fn,(i+$fn)+k*$fn,((i+1)%$fn+$fn)+k*$fn]] ]);
FacesList=concat(EndFace1,SideFaces,EndFace2); // list of all faces needed to close shape
function flatten(l) = [ for (a = l) for (b = a) b ] ; // remove brackets
function ExtractSlice(List,Element)=flatten([for( i=Element) List[i]]); // extract a vector from a slice
function TiltSlice_X(Sl,A) = [for( i=[0:1:$fn1]) let (v=ExtractSlice(Sl,i)) [v[0], v[1]*cos(A), v[1]*sin(A)]]; // tilt slice around x axis
function MoveSlice(Sl,SP) = [for( i=[0:1:$fn1]) let (v=ExtractSlice(Sl,i)) [v[0]+SP[0], v[1]+SP[1], v[2]+SP[2] ]]; // move slice to SP=[x,y,z]
// End shape generating list
polyhedron(VertexList,FacesList);
Except for the increase in speed, my approach also does away with the need to have a faces list. A few extra brackets in the VertexList is all it takes for the computer to be able to generate the faces list by itself. But it also exposes shortcomings in the language: nested lists can currently be read only one level deep, and thus I was forced to develop, with function ExtractSlice, the ability to access deeper nesting levels.
The current implementation has only two nesting levels and thus cannot handle holes. By adding a third nesting level, I expect that holes can also be accomodated.
Vertices, innermost nesting level, contains a list of numbers to define a vertex.
Slices, second nesting level, contains the list of all vertices belonging to a slice.
Groups of slices, third nesting level: counting from the outside, the first slice represents material, the second a hole, the third material, etc. That this works will have to be demonstrated, though.
Thanks, Ronaldo, for pointing out that my approach is not quite new. Were you aware of the gains in rendering speed that are achieved using this approach over the more conventional approach of using unions() or hulls()? Or that the faces list can be computer generated and need not be provided by the user?
Parkinbot, I have difficulties understanding what you mean: what properties does a polygon need to have that you will call it simple? Can you explain?
Selfintersection is not a problem for me, as I design by eye, and my eye will pick up any funny shapes immediately. Whether selfintersection is a problem with CGAL remains to be seen, as at some stage I will have to try to design a Klein bottle in OpenSCAD. If CGAL is true to its mathematical roots, then I do not foresee any problem in constructing the bottle, nor do I foresee restrictions regarding convex or concave slices.
Lastly, what do you mean with "because zcoordinate of a 3D shape cannot be quested in current OpenSCAD to grand for noninterscection" With "quested" I suppose you wanted to write "queried", but what in a Palainian hell is "to grand" supposed to mean?
wolf


Wolf,
Sorry about the 'typos' (English is not my first language). Of course I meant „queried” and „ensure/guarantee“.
I perfectly agree with you: If you know what you do (selfrestriction), avoiding superfluous tests is a perfect way to get fast results.
But I can assure you: Selfintersection *is* a problem with CGAL  and dealing formally with it is the main reason why CGAL is slow.
A general scheme or a language feature cannot rely on selfrestriction (e.g. pointers in C language follow this way, and we all know, what was the result in the history of computing).
About "simple polygons" and "convexity" you can find good articles in the net, e.g. Wikipedia. We also had some discussion on it in this forum.
wolf wrote
I am now in a position to quantify my claims about improved rendering speed. Parkinbot publishedhas published a routine to generate a coil. When set to 200 slices per winding and 10 windings, this routine renders on my machine in 52 minutes. The equivalent coil, also having 2000 slices, renders in 11 seconds using my approach:
The slowness of the hullapproach is obvious and mainly comes from the large number of union() operations being involved. But it is still the only way to tackle things like that with OpenSCAD language means (and was discussed e.g. here). Also my next step was to switch to polyhedron(), which means you are programming the whole shape mostly from the scratch  and nobody will understand your code anymore, unless you put it into a welldocumented library with a simple interface like skin().
Have fun with the Klein bottle. Let me know, how you solve the selfintersection part ;)
Rudolf


wolf wrote
Selfintersection is not a problem for me, as I design by eye, and my eye will pick up any funny shapes immediately. Whether selfintersection is a problem with CGAL remains to be seen, as at some stage I will have to try to design a Klein bottle in OpenSCAD. If CGAL is true to its mathematical roots, then I do not foresee any problem in constructing the bottle, nor do I foresee restrictions regarding convex or concave slices.
Wolf, change the first three lines of your code to:
// Start user definable data
$fn=100;
Slices=200;
SliceAngle=[for( i=[0:1:Slices1]) 6.6*i];//1.8*i]; // angle by which each slice is tilted
and you get selfintersection (SI). It renders fine and fast. However, you may get a CGAL warning that "PolySet has degenerate polygons". But if you also change the last line to:
intersection(){
polyhedron(VertexList,FacesList);
cube(100);
}
you get in trouble. To find what caused the trouble may be a greater trouble.
Were you aware of the gains in rendering speed that are achieved using this
approach over the more conventional approach of using unions() or hulls()?
Or that the faces list can be computer generated and need not be provided by
the user?
Your slice approach to the spring modelling is the same of Oskar Linde's sweep that encloses all the face list computations. A more general construction is his skin that do the same. I have been using a similar more general approach to model solids enclosed by Bezier surfaces and "almost" planar faces. All face lists computation are inside a general module that process the user meshes. It works provided that the surface patches created by the user meet at boundaries and define a manifold. And that they have no SI! So, a lot of care is left to user.
However, I don't see any approach that effectively avoid nonmanifolds created by users. With OpenSCAD union, you may build a nonmanifold with two cubes having only one vertex in common. Or intersecting to cubes with just one face in common. But I agree that those are simpler to understand and avoidable than other cases.
The only approach I know that deals well and naturally with SI is frep (implicit representation). If carefully implemented it may "makeup" all model singulaties.


Parkinbot wrote
Have fun with the Klein bottle. Let me know, how you solve the selfintersection part ;)
Rudolf, don't be so skeptical. :)
The Klein bottle is a nonorientable surface. So it is the Roman surface. I processed the Roman surface with my frep evaluation system and got the following rendered image:
where the surface was unioned with a OpenSCAD sphere. It is a crude representation of a yet rudimentary (but large and complex) frep processing code. The gaps you see are the natural "makeup" of the SI the surface has.
To produce that image (and its stl), it is only required the Roman surface definition:
function cushion_surface_eval(pt, a) =
// http://mathworld.wolfram.com/CushionSurface.html let( x = pt[0], y = pt[1], z = pt[2],
x2 = x*x, y2 = y*y,
z2 = z*z, z3 = z*z2, z4 = z2*z2 )
a*(z2*x2  z4  2*z*x2 + 2*z3 + x2  z2
 pow(x2z,2)  y2*y2  2*x2*y2  y2*z2 + 2*y2*z + y2);
and then create the frep representation and display:
prim_data = [ROMAN, 5, 1, 1];
roman = f_scale(f_primitive(prim_data), 6);
mseh = f_mesh_evaluation(roman, [33,33,33], 66, 66, 66, 40, 40, 40);
union(){
mesh_surface(mesh);
sphere(12);
}
The gaps in the model can be reduced by refining the discretization of the mesh. This is the bottleneck of the approach: the time to render is O(n^3) where n is the discretization of each axis. For that image, the console output was:
Compiling design (CSG Tree generation)...
ECHO: "
INFO: mesh_surface id = 0 > received 5632 polygons to display
"
ECHO: "
INFO: mesh_surface id = 0 > generated 19488 triangles with 26592 vertices on polyhedron
"
Rendering Polygon Mesh using CGAL...
Geometries in cache: 130
Geometry cache size in bytes: 25310688
CGAL Polyhedrons in cache: 2
CGAL cache size in bytes: 47539440
Total rendering time: 0 hours, 2 minutes, 12 seconds
Top level object is a 3D object:
Simple: yes
Vertices: 9615
Halfedges: 55420
Edges: 27710
Halffacets: 36226
Facets: 18113
Volumes: 10
Rendering finished.
Bounding boxes would help here.
Ronaldo


Cool stuff, Ronaldo
The refinement problem reminds me on my first attempt to render some Schwarz p surfaces. The most famous one almost looks like the OpenSCAD logo.


Here you have it in my interpretation.
I used a primitive evaluated by:
function Schwartz_p(pt, a,b,c) = a*cos(pt[0]) + b*cos(pt[1]) + c*cos(pt[2]) ;
and the following main code to render it:
S = f_primitive([ SCHWARTZ, 1, 1, 1 ]);
msh = f_mesh_evaluation(S, [500,500,167], 1000, 1000, 666, 50,50,33);
mesh_surface(msh);
The process generated 64984 triangles with 91958 vertices and required 9min and 20sec to render.


Hi Ronaldo,
this looks good and shows that your Frepstuff is working well, besides that it could profit from some (implicit) grid refining scheme near the borders. Ok, you use the triple cosine shortcut instead of the minimal surface calculation, but this is another theme.
To be able to print it, one would also like to have a skin extruded structure, which was the point where my effort (and time) ended.
BTW, I used an ordinary R²>R function plot after resolving the implict equation to z and discretrizing it over a domain restricted to the partial symmetry. While this gives you a nice border around the top hole, you can use union operations to repeat the rendered chuck for all symmetries with the required orientation.


"I use an ordinary R²>R function plot after resolving the implicit
equation to z and discretrizing it over a domain restricted to the
partial symmetry"
Yeah <I said casually>. I do that all of the time! In my sleep, in
fact! LOL!
Kudos to you, Parkinbot! What would we do without people like you!
Jon
On 6/10/2016 8:43 AM, Parkinbot wrote:
> Hi Ronaldo,
>
> this looks good and shows that your Frepstuff is working well, besides that
> it could profit from some (implicit) grid refining scheme near the borders.
> Ok, you use the triple cosine shortcut instead of the minimal surface
> calculation, but this is another theme.
> To be able to print it, one would also like to have a skin extruded
> structure, which was the point where my effort (and time) ended.
>
> BTW, I used an ordinary R²>R function plot after resolving the implict
> equation to z and discretrizing it over a domain restricted to the partial
> symmetry. While this gives you a nice border around the top hole, you can
> use union operations to repeat the rendered chuck for all symmetries with
> the required orientation.
>
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Jon, we are talking about explicitly rendering shapes and rendering speed of the polyhedron approach. Sorry, if that gets boring for you.


Parkinbot wrote
this looks good and shows that your Frepstuff is working well, besides that it could profit from some (implicit) grid refining scheme near the borders.
Yes, the borders are a lot rough. I did not implemented any feature detection scheme. They are a lot harder to implement. A local refining scheme would improve the edges but they would be rough anyway.
Ok, you use the triple cosine shortcut instead of the minimal surface calculation, but this is another theme.
To be able to print it, one would also like to have a skin extruded structure, which was the point where my effort (and time) ended.
I used the approximation I found in Wikipedia. I am not acquainted to the minimal surface theory and have not found any exact implicit form of the surface.
By changing the code a little and redefining the Schwartz primitive, I got the following:
The upper image represents just the surface and it is not a manyfold. It was obtained by commenting 4 lines of the f_mesh_evaluation code eliminating the six bounding box of the mesh.
The lower image seems to be what you wanted. The Schwartz primitive for that was simply redefined as:
function Schwartz_p(pt, a,b,c,d) =
let( s = a*cos(pt[0]) + b*cos(pt[1]) + c*cos(pt[2]) )
min( s,  s + d);
So, the inside surface was obtained just by doing an "offset" of the original function value and the min() is equivalent to an intersection. That is one of the marvelous things of the implicit representation of freps.
This last run took a longer time to preview: 20min. So, I think we are in the wrong thread to discuss this subject :)
BTW, I used an ordinary R²>R function plot after resolving the implict equation to z and discretrizing it over a domain restricted to the partial symmetry. While this gives you a nice border around the top hole, you can use union operations to repeat the rendered chuck for all symmetries with the required orientation.
I have no idea of what you are saying here. But I tip my hat to you.
@jon, I could not say it better.


One more point: Rudolf, who I suppose is German, referred to a minimal surface created by Schwartz, who I suppose is German too. I would like to render a minimal surface created by a Brazilian mathematician (I am a Brazilian too): the Costa surface. But I have not found any implicit form of it. If someone give me a reference for that I would be very grateful.
Ronaldo
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Parkinbot:
Not boring! Just above my head! I really am amazed at what some of you
are doing. As I said, Kudos!
Jon
On 6/10/2016 12:21 PM, Parkinbot wrote:
> Jon, we are talking about explicitly rendering shapes and rendering speed of
> the polyhedron approach. Sorry, if that gets boring for you.
>
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Ronaldo,
thanks again, for showing how mighty your approach is. I tried to dig out my code on that, but found only my first approach, which I did in OpenSCAD. I think I changed to Matlab after that. I remember there was a point, I got frustrated on calculating the skin part  in which your approach seems to be very good.
its better here http://www.indiana.edu/~minimal/archive/Triply/genus3/PLines/web/For the R²>R part: You can resolve the skin equation
0 = cos(x) + cos(y) + cos(z)
for z
z = acos(cos(x)  cos(y))
and then solve this system for any (feasible) zdiscretrization, while restricting x and y (out of R²) to the symmetry region (shown by the lines in linked picture). Not such a big deal.
So, the inside surface was obtained just by doing an "offset" of the
original function value and the min() is equivalent to an intersection. That
is one of the marvelous things of the implicit representation of freps.
yes, this is indeed marvelous. I'll have to dig into that one day.
Hermann Schwarz was a German mathematican. Can't help you with Costa ... Surface math is not my world by the way.


A good way to get nice borders for the Schwarzp even with an unrefined grid is to do the meshing over a slightly enlarged domain and then intersect with a cube ...


Parkinbot wrote
A good way to get nice borders for the Schwarzp even with an unrefined grid is to do the meshing over a slightly enlarged domain and then intersect with a cube ...
Done.
For easy comparison, I have left the top and bottom surfaces uncut. I have refined the mesh a lot this time: it has 140000 points. The final model has 43000 polygons, subdivided in 137000 triangles with a total of 197000 vertices. It took 38min to render.
I agree, jon, this is definitely not an appropriate example for this thread. :)
Ronaldo


Well done. Now you see that it is not harmonic. The minimal surface connects with circles.
But I'll vote for it to get the logo of multithreaded OpenSCAD.


Hi, Rudolf.
I have built a simple animation with the Schwarz surface generated by my frep library. Here is the file:
Schwarz.mp4I could not display the video with the online software but it can be downloaded to be played offline. The animation loosely suggests that an OpenSCAD model is made of the combination of small parts.

12
