# Polyhedron()

18 messages
Open this post in threaded view
|

## Polyhedron()

 A few days ago I posted a piece of code creating an ellipsoid out of individual polyhedron() faces. As doug.moen pointed out, it looked like a solid, but was just a collection of faces. Here I show what happened, and why, and how to make it a solid. First, recall that polyhedron (points=[[0,0,0],[0,1,0],[0,1,1],[0,0,1],[1,0,0],[1,1,0],[1,1,1],[1,0,1]],                      faces=[[0,1,2,3],[4,5,6,7],[3,2,6,7],[1,5,6,2],[0,4,7,3],[0,1,5,4]]); creates a cube, which is a solid. Multiple calls polyhedron (points=[[0,0,0],[0,1,0],[0,1,1],[0,0,1]],faces=[[0,1,2,3]]);             polyhedron (points=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]);             polyhedron (points=[[0,0,1],[0,1,1],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]);             polyhedron (points=[[0,1,0],[1,1,0],[1,1,1],[0,1,1]],faces=[[0,1,2,3]]);             polyhedron (points=[[0,0,0],[1,0,0],[1,0,1],[0,0,1]],faces=[[0,1,2,3]]);             polyhedron (points=[[0,0,0],[0,1,0],[1,1,0],[1,0,0]],faces=[[0,1,2,3]]); create the same cube, but this one is just a collection of faces, and an intersection() cannot be made. These faces need to be welded together using hull() to make it a solid that can be intersected, as follows: difference()   { MyCube();     translate([.5,.5,.5]) cylinder(h=2,d=.2,\$fn=20,center=true);   } module MyCube()  hull()   { color("red")      polyhedron (points=[[0,0,0],[0,1,0],[0,1,1],[0,0,1]],faces=[[0,1,2,3]]);                 color("yellow")   polyhedron (points=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]);                 color("green")    polyhedron (points=[[0,0,1],[0,1,1],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]);                 color("magenta")  polyhedron (points=[[0,1,0],[1,1,0],[1,1,1],[0,1,1]],faces=[[0,1,2,3]]);                 color("pink")     polyhedron (points=[[0,0,0],[1,0,0],[1,0,1],[0,0,1]],faces=[[0,1,2,3]]);                 color("purple")   polyhedron (points=[[0,0,0],[0,1,0],[1,1,0],[1,0,0]],faces=[[0,1,2,3]]);     } With hull() commented out, each face of the cube has a different colour, and behaves as a separate entity. With hull() active, all faces have the same colour, and there is only one entity, a cube. hull() does even more: it allows you to remove the last three calls to polyhedron() without affecting the cube. Since calls to polyhedron() are rather slow, using hull() actually speeds up rendering. The code for the ellipsoid has been given this optimization, and rendering times have dropped from 10 seconds on my machine to 5 seconds - always with cache flushed. This is the optimised code: a=30;   b=20;   c=10;    //half-axes of ellipse Step=10; difference()  { h();     cylinder(h=40, d=2, center=true, \$fn=20);} module h()     hull()   Ellipsoid(); module Ellipsoid() for (v=[Step/2:Step:180-Step])   for (u=[Step/2:Step:360-Step/2])   SurfaceElement(u,v);       module SurfaceElement(u,v)   { P0=P(u-Step/2,v-Step/2);          // corner vector for SurfaceElement()     P1=P(u+Step/2,v-Step/2);          // corner vector for SurfaceElement()     P2=P(u+Step/2,v+Step/2);          // corner vector for SurfaceElement()     polyhedron (points=[P0,P1,P2], faces=[[0,1,2]]);   }       function P(u,v)=[a*cos(u)*sin(v),b*sin(u)*sin(v),c*cos(v)];  //point on the surface of an ellipsoid There is no need to merge all points into a single list first, as has been suggested. But I still would like to know how this is done . . . Wolf
Open this post in threaded view
|

## Re: Polyhedron()

 I like this!  It seems that it could be used to generate other shapes, since the "shape" code is all in the final function. Jon On 11/10/2015 5:55 AM, wolf wrote: > A few days ago I  posted > > a piece of code creating an ellipsoid out of individual polyhedron() faces. > As  doug.moen > > pointed out, it looked like a solid, but was just a collection of faces. > Here I show what happened, and why, and how to make it a solid. > > First, recall that > polyhedron > (points=[[0,0,0],[0,1,0],[0,1,1],[0,0,1],[1,0,0],[1,1,0],[1,1,1],[1,0,1]], >                       > faces=[[0,1,2,3],[4,5,6,7],[3,2,6,7],[1,5,6,2],[0,4,7,3],[0,1,5,4]]); > creates a cube, which is a solid. > Multiple calls > polyhedron (points=[[0,0,0],[0,1,0],[0,1,1],[0,0,1]],faces=[[0,1,2,3]]); > polyhedron (points=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]); > polyhedron (points=[[0,0,1],[0,1,1],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]); > polyhedron (points=[[0,1,0],[1,1,0],[1,1,1],[0,1,1]],faces=[[0,1,2,3]]); > polyhedron (points=[[0,0,0],[1,0,0],[1,0,1],[0,0,1]],faces=[[0,1,2,3]]); > polyhedron (points=[[0,0,0],[0,1,0],[1,1,0],[1,0,0]],faces=[[0,1,2,3]]); > create the same cube, but this one is just a collection of faces, and an > intersection() cannot be made. > These faces need to be welded together using hull() to make it a solid that > can be intersected, as follows: > difference() >    { MyCube(); >      translate([.5,.5,.5]) cylinder(h=2,d=.2,\$fn=20,center=true); >    } > module MyCube() >   hull() >    { color("red")      polyhedron > (points=[[0,0,0],[0,1,0],[0,1,1],[0,0,1]],faces=[[0,1,2,3]]); >      color("yellow")   polyhedron > (points=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]); >      color("green")    polyhedron > (points=[[0,0,1],[0,1,1],[1,1,1],[1,0,1]],faces=[[0,1,2,3]]); >      color("magenta")  polyhedron > (points=[[0,1,0],[1,1,0],[1,1,1],[0,1,1]],faces=[[0,1,2,3]]); >      color("pink")     polyhedron > (points=[[0,0,0],[1,0,0],[1,0,1],[0,0,1]],faces=[[0,1,2,3]]); >      color("purple")   polyhedron > (points=[[0,0,0],[0,1,0],[1,1,0],[1,0,0]],faces=[[0,1,2,3]]); >    } > With hull() commented out, each face of the cube has a different colour, and > behaves as a separate entity. With hull() active, all faces have the same > colour, and there is only one entity, a cube. hull() does even more: it > allows you to remove the last three calls to polyhedron() without affecting > the cube. Since calls to polyhedron() are rather slow, using hull() actually > speeds up rendering. > The code for the ellipsoid has been given this optimization, and rendering > times have dropped from 10 seconds on my machine to 5 seconds - always with > cache flushed. > This is the optimised code: > > a=30;   b=20;   c=10;    //half-axes of ellipse > Step=10; > difference()  { h();     cylinder(h=40, d=2, center=true, \$fn=20);} > module h() > hull()   Ellipsoid(); > module Ellipsoid() > for (v=[Step/2:Step:180-Step])   for (u=[Step/2:Step:360-Step/2]) > SurfaceElement(u,v); > module SurfaceElement(u,v) >    { P0=P(u-Step/2,v-Step/2);          // corner vector for SurfaceElement() >      P1=P(u+Step/2,v-Step/2);          // corner vector for SurfaceElement() >      P2=P(u+Step/2,v+Step/2);          // corner vector for SurfaceElement() >      polyhedron (points=[P0,P1,P2], faces=[[0,1,2]]); >    } > function P(u,v)=[a*cos(u)*sin(v),b*sin(u)*sin(v),c*cos(v)];  //point on the > surface of an ellipsoid > > There is no need to merge all points into a single list first, as has been > suggested >  . > But I still would like to know how this is done . . . > > Wolf > > > > > > -- > View this message in context: http://forum.openscad.org/Polyhedron-tp14338.html> Sent from the OpenSCAD mailing list archive at Nabble.com. > > _______________________________________________ > OpenSCAD mailing list > [hidden email] > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org> > > > ----- > No virus found in this message. > Checked by AVG - www.avg.com > Version: 2016.0.7227 / Virus Database: 4457/10972 - Release Date: 11/09/15 > > _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron()

 This post was updated on . In reply to this post by wolf This is how you do it with list comprehensions to make a manifold polyhedron that doesn't need wrapping in hull. a=30;   b=20;   c=10;    //half-axes of ellipse Step=10;   function P(u,v)=[a*cos(u)*sin(v),b*sin(u)*sin(v),c*cos(v)];  //point on the surface of an ellipsoid   function SurfaceElement(u,v) = let(hs = Step / 2) [ P(u - hs, v - hs),                                                     P(u + hs, v - hs),                                                     P(u + hs, v + hs),                                                     P(u - hs, v + hs)]; function quad(i) = let(p = i * 4) [[p, p + 1, p + 2], [p, p + 2, p + 3]];   function flatten(l) = [ for (a = l) for (b = a) b ] ;     elements = flatten([let(s = Step / 2) for(v = [s : Step : 180 - s]) for(u = [s : Step: 360 - s]) SurfaceElement(u, v)]); faces    = flatten([for(v = [0 : 180 / Step - 1]) for(u = [0 : 360 / Step - 1]) quad(v * 360 / Step + u) ]); difference() {     polyhedron(elements, faces);     cylinder(h=40, d=2, center=true, \$fn=20); }
Open this post in threaded view
|

## Re: Polyhedron()

 Hmm, all the newlines got eaten but I have fixed it on the forum post.On 10 November 2015 at 12:05, nophead wrote:This is how you do it with list comprehensions to make a manifold polyhedron that doesn't need wrapping in hull. a=30; b=20; c=10; //half-axes of ellipse Step=10; function P(u,v)=[a*cos(u)*sin(v),b*sin(u)*sin(v),c*cos(v)]; //point on the surface of an ellipsoid function SurfaceElement(u,v) = let(hs = Step / 2) [ P(u - hs, v - hs), P(u + hs, v - hs), P(u + hs, v + hs), P(u - hs, v + hs)]; function quad(i) = let(p = i * 4) [[p, p + 1, p + 2], [p, p + 2, p + 3]]; function flatten(l) = [ for (a = l) for (b = a) b ] ; elements = flatten([let(s = Step / 2) for(v = [s : Step : 180 - s]) for(u = [s : Step: 360 - s]) SurfaceElement(u, v)]); faces = flatten([for(v = [0 : 180 / Step - 1]) for(u = [0 : 360 / Step - 1]) quad(v * 360 / Step + u) ]); difference() { polyhedron(elements, faces); cylinder(h=40, d=2, center=true, \$fn=20); } View this message in context: Re: Polyhedron() Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron()

Open this post in threaded view
|

## Re: Polyhedron()

Open this post in threaded view
|

## Re: Polyhedron()

Open this post in threaded view
|

## Re: Polyhedron()

Open this post in threaded view
|

## Re: Polyhedron()

 doug.moen wrote I think that the underlying topic of discussion is: polyhedron() is difficult to use. Is there an easier way to convert a collection of vertices into a 3D object? ... There are surface reconstruction hooks in CGAL: http://doc.cgal.org/latest/Surface_reconstruction_points_3/...but as with many things, the devil's in the implementation-details. Andrew.
Open this post in threaded view
|

## Re: Polyhedron()

Open this post in threaded view
|

## Re: Polyhedron()

 In reply to this post by doug.moen doug.moen wrote I think that the underlying topic of discussion is: polyhedron() is difficult to use. Is there an easier way to convert a collection of vertices into a 3D object? ...... The raw output from a 3D scanner is a point cloud. There exists software for converting this point cloud into a polyhedral mesh. I think it would be interesting to add a point_cloud() operation to OpenSCAD, for converting a list of vertices into a manifold 3D object. The algorithm should exist somewhere as open source. It's probably slower than polyhedron(), but much easier to use. The point_cloud() primitive would give us very simple and easy to write code for generating an ellipsoid. Something like this: a=30;   b=20;   c=10;    //half-axes of ellipse Step=10; point_cloud(   [for (v=[0: Step: 180])     for (u=[0: Step: 360])       P(u,v)   ]); function P(u,v)=[a*cos(u)*sin(v),b*sin(u)*sin(v),c*cos(v)]; The underlying approach could be simplified into generating simple shapes. For example, the ellipsoid shape, if watched closely, is basically the same as the "chain" object described in my faces.scad tool topologically. So a point_cloud() primitive can be easily coded as such: a=30;   b=20;   c=10;    //half-axes of ellipse Step=10; function P(u,v)=[ a*cos(u)*sin(v)                 , b*sin(u)*sin(v)                 , c*cos(v) ];   module point_cloud( pts, shape, nside, nseg ){      polyhedron( points=pts, faces= faces(shape, nside, nseg) ); } pts = [for (v=[Step: Step: 180-Step])           for (u=[Step: Step: 360])             P(u,v)         ]; point_cloud(    pts   , shape="chain"   , nside= 360/Step   , nseg= 180/Step-2 ); In fact, this approach is why I made faces.scad in the first place. As seen in the link mentioned, generating a basic form of polyhedron is a simple matter of generating points and picking a shape. \$ Runsun Pan, PhD \$ libs:doctest, faces(git), offline doc(git), runscad.py(2,git), synwrite(2);   \$ tips:Collection of tips on github
Open this post in threaded view
|

## Re: Polyhedron()

 Administrator In reply to this post by doug.moen > On Nov 10, 2015, at 10:33 AM, doug moen <[hidden email]> wrote: > > Peter Falke has suggested the idea of feeding a collection of points to hull(). This would be as simple as adding an optional ‘points’ parameter to hull; i.e. pass points=[…] instead of children will just hull the points. I’m uncertain if this should perhaps be a separate module, to avoid mixing group nodes and leaf nodes. > I think it would be interesting to add a point_cloud() operation to OpenSCAD, for converting a list of vertices into a manifold 3D object. The algorithm should exist somewhere as open source. This would be cool. One challenge could be that the output of such an operation is depending on which algorithm was used, which would potentially lock us into one particular library or implementation where people start to depend on specific artifacts (similar to how people are using cylinder(\$fn=6) to create prisms).  -Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron()

 Administrator In reply to this post by doug.moen > On Nov 10, 2015, at 10:33 AM, doug moen <[hidden email]> wrote: > > I think that the underlying topic of discussion is: polyhedron() is difficult to use. Is there an easier way to convert a collection of vertices into a 3D object? Another potential operator: skin -> create and orient a bunch of 2D polygons in 3D space and create a skin around the result. This is already possible in user-space, but requires building 2D shapes manually: https://github.com/openscad/list-comprehension-demos#extrusionscad -Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron()

Open this post in threaded view
|

## Re: Polyhedron()

 Administrator > On Nov 10, 2015, at 13:24 PM, Torsten Paul <[hidden email]> wrote: > > On 11/10/2015 04:33 PM, doug moen wrote: >> Peter Falke has suggested the idea of feeding a collection of points to hull(). >> > See also there: https://github.com/openscad/openscad/pull/1168> Ah, right. The old CGAL dependency issue. I’m thinking we should stop looking at CGAL as a library, but as a collection of tools, write wrappers for each of these tools separately, and keep the library dependency decoupled from any interfaces.  -Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron()

 This post has NOT been accepted by the mailing list yet. In reply to this post by kintel kintel wrote This would be cool. One challenge could be that the output of such an operation is depending on which algorithm was used, which would potentially lock us into one particular library or implementation where people start to depend on specific artifacts (similar to how people are using cylinder(\$fn=6) to create prisms). Actually... upon looking into Wikipedia, the convex hull of a point cloud is well-defined and not implementation/algorithm dependent.  Someone might decide to write, say, Chan's algorithm (https://en.wikipedia.org/wiki/Chan%27s_algorithm) into a OpenSCAD library, with calling convention as doug suggested. On the other hand, the non-convex solid defined by a point cloud is ill-posed. doug.moen wrote this technique is not general, since it can't be used to construct a non-convex object. Consider the simple case of 9 points: ```[[0,0,0], [1,0,0], [1,1,0], [0,1,0], [0,1,1], [1,1,1], [1,0,1], [0,0,1], [0.5,0.5,0.5]]```Which is the 8 vertices of a cube plus its center point.  A polyhedron with all these vertices can be a cube minus a pyramid but which way should the concave side face?  There problem is ill-posed. I have my imperfect solution to using polyhedron() to generate highly complex solids, I understand the desire to make it easier to use (thanks to doug's post for summarizing/clarifying the topic) but someone need to come up with a rigourously posed question before someone else could come up with a general solution.
 In reply to this post by kintel (I'm re-posting this, due to a tech issue, hope I'm not annoying anyone) kintel wrote This would be cool. One challenge could be that the output of such an operation is depending on which algorithm was used, which would potentially lock us into one particular library or implementation where people start to depend on specific artifacts (similar to how people are using cylinder(\$fn=6) to create prisms). Actually... upon looking into Wikipedia, the convex hull of a point cloud is well-defined and not implementation/algorithm dependent.  Someone might decide to write, say, Chan's algorithm (https://en.wikipedia.org/wiki/Chan%27s_algorithm) into a OpenSCAD library, with calling convention as doug suggested. On the other hand, the non-convex solid defined by a point cloud is ill-posed. doug.moen wrote this technique is not general, since it can't be used to construct a non-convex object. Consider the simple case of 9 points: ```[[0,0,0], [1,0,0], [1,1,0], [0,1,0], [0,1,1], [1,1,1], [1,0,1], [0,0,1], [0.5,0.5,0.5]]```Which are the 8 vertices of a cube plus its center point.  A polyhedron with all these vertices can be a cube minus a pyramid but which way should the concave side face?  There problem is ill-posed. I have my imperfect solution to using polyhedron() to generate highly complex solids, I understand the desire to make it easier to use (thanks to doug's post for summarizing/clarifying the topic) but someone need to come up with a rigourously posed question before someone else could come up with a general solution.