Improve rendering speed
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 1000-10 000 times, reducing rendering times from hours to seconds.
The code is work-in-progress, 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 shape-to-be-generated 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
http://forum.openscad.org/file/n17580/Screenshot_20160608_110911.png
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:Slices-1]) [3.6i,0,0]]; // angle by which
each slice is tilted, currently not implemented
SlicePosition=[for( i=[1:1:Slices]) [0,0,(i-1)/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:$fn-1])
[rcos(iStep),rsin(i*Step),0]];
// End user definable data
// Start generating list
Offset_X=flatten([for( i=[0:1:Slices-1])
MinElement_X(CircularSlice(SliceRadius[i]))]); // list of all slices
needed to construct shape
VertexList=flatten([for( i=[0:1:Slices-1])
MoveSlice(CircularSlice(SliceRadius[i]),SlicePosition[i])]); // list of
all slices needed to construct shape
EndFace1=[for( i=[2:1:$fn-1]) [0,i-1,i]]; // list of all triangular
faces needed to close shape at one end
EndFace2=[let(F=(Slices-1)$fn) for( i=[F:1:F+$fn-3]) [F,i+2,i+1]]; //
list of all triangular faces needed to close shape at other end
SideFaces=flatten([for( i=[0:1:$fn-1]) 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:$fn-1]) 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:$fn-1]) 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);}
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I've played around with this approach for a while
http://www.thingiverse.com/thing:900137
and connected it with some interpolation scheme
http://www.thingiverse.com/thing:1208001
into 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 equi-distantanly or even a height vector for
freely Z-extruding along the polygon shapes. Also this is a linear scenario
the operator will have to fight with well-definedness of the polygon
sequence:
- each polygon has to be tested to be simple
- the sequence has to be tested for self-intersection 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
user-defined 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 non-linearity and a hole bunch of
self-intersection issues.
Another much easier approach could be an operator that just piles a set of
3D-shapes 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 z-coordinate of a 3D shape cannot be quested in current
OpenSCAD to grand for non-interscection).
http://forum.openscad.org/file/n17584/pile.png
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:$children-1])
translate([0, 0, i*dh])
linear_extrude(height = dh)
children(i);
}
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17584.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
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:
http://forum.openscad.org/file/n17608/Twist%26Taper.png
and here is the code:
deform.scad http://forum.openscad.org/file/n17608/deform.scad
As you may see, the function and the module let to the user the burden of
triangulating the non-triangular faces of the polyhedron. And, as Parkingbot
pointed out, it doesn't check for self-intersections 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
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17608.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I am now in a position to quantify my claims about improved rendering speed.
Parkinbot published http://www.thingiverse.com/thing:648813 has
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:Slices-1]) 1.8i]; // angle by which each
slice is tilted
SlicePosition=[for( i=[1:1:Slices]) [0.125i,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:$fn-1])
[rcos(iStep),rsin(iStep),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:Slices-1])
TiltSlice_X(MoveSlice(CircularSlice(SliceRadius[i]),SlicePosition[i]),SliceAngle[i])]);
// list of all vertices needed to construct shape
EndFace1=[for( i=[2:1:$fn-1]) [0,i-1,i]]; //
list of all triangular faces needed to close shape at one end
EndFace2=[let(F=(Slices-1)$fn) for( i=[F:1:F+$fn-3]) [F,i+2,i+1]]; //
list of all triangular faces needed to close shape at other end
SideFaces=flatten([for( i=[0:1:$fn-1]) 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:$fn-1]) 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:$fn-1]) 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?
Self-intersection is not a problem for me, as I design by eye, and my eye
will pick up any funny shapes immediately. Whether self-intersection 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 z-coordinate of a 3D shape cannot be
quested in current OpenSCAD to grand for non-interscection" With "quested" I
suppose you wanted to write "queried", but what in a Palainian hell is "to
grand" supposed to mean?
wolf
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17613.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
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 (self-restriction),
avoiding superfluous tests is a perfect way to get fast results.
But I can assure you: Self-intersection 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 self-restriction (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
published http://www.thingiverse.com/thing:648813
has 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 hull-approach 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
http://forum.openscad.org/Non-Linear-Transformations-tp14539p16673.html
). 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 well-documented
library with a simple interface like skin()
https://github.com/openscad/list-comprehension-demos/blob/master/skin.scad
.
Have fun with the Klein bottle. Let me know, how you solve the
self-intersection part ;-)
Rudolf
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17615.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
wolf wrote
Self-intersection is not a problem for me, as I design by eye, and my eye
will pick up any funny shapes immediately. Whether self-intersection 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:Slices-1]) 6.6i];//1.8i]; // angle by
which each slice is tilted
and you get self-intersection (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 non-manifolds
created by users. With OpenSCAD union, you may build a non-manifold 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 f-rep
(implicit representation). If carefully implemented it may "makeup" all
model singulaties.
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17617.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Parkinbot wrote
Have fun with the Klein bottle. Let me know, how you solve the
self-intersection part ;-)
Rudolf, don't be so skeptical. :)
The Klein bottle is a non-orientable surface. So it is the Roman surface. I
processed the Roman surface with my f-rep evaluation system and got the
following rendered image:
http://forum.openscad.org/file/n17619/Roman_surface-sphere.png
where the surface was unioned with a OpenSCAD sphere. It is a crude
representation of a yet rudimentary (but large and complex) f-rep 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 = xx, y2 = yy,
z2 = zz, z3 = zz2, z4 = z2z2 )
a(z2x2 - z4 - 2zx2 + 2z3 + x2 - z2
- pow(x2-z,2) - y2y2 - 2x2y2 - y2z2 + 2y2z + y2);
and then create the f-rep 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
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17619.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
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.
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17625.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Here you have it in my interpretation.
http://forum.openscad.org/file/n17629/Schwartz_surface.png
I used a primitive evaluated by:
function Schwartz_p(pt, a,b,c) = acos(pt[0]) + bcos(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.
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17629.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Hi Ronaldo,
this looks good and shows that your Frep-stuff 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.
--
View this message in context: http://forum.openscad.org/Improve-rendering-speed-tp17580p17631.html
Sent from the OpenSCAD mailing list archive at Nabble.com.