Polyhedron tube with irregular sides -- is it possible ?

classic Classic list List threaded Threaded
86 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
nophead wrote
> It nearly can with the keyhole method but they are not acceptable to CGAL
> in that format
> as they are not manifold. Simply removing the connections between loops
> and
> ensuring the correct winding order should fix that.

This would imply that linear_extrude will not have to recourse to a
tesselation for F5. There is a lot change of involved.  



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
In reply to this post by Parkinbot
see what happens to an almost planar face created by an rotate_extrude.
<http://forum.openscad.org/file/t887/rot.png>


rotate_extrude(angle = 160)
{
 translate([10, 0])
difference()
  {
    square(10, center = true);
    square(5, center = true);
  }
}
cube(1);





--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

nophead
> This would imply that linear_extrude will not have to recourse to a tesselation for F5.
I don't understand why. I am not proposing any changes to linear_extrude.

Anyway it appears that polyhedron will accept faces with holes if they are tesselated correctly by the user. I exported your curved tube as STL and then converted it to a polyhedron with this website: https://jsfiddle.net/Riham/yzvGD/
The result is all triangles but CGAL converts all the planar faces back to polygons. Only the rotated end face remains partly triangulated due to floating point inacuracies. I.e. converting it to STL and back has improved the last segment!

image.png







On Mon, 17 Dec 2018 at 13:01, Parkinbot <[hidden email]> wrote:
see what happens to an almost planar face created by an rotate_extrude.
<http://forum.openscad.org/file/t887/rot.png>


rotate_extrude(angle = 160)
{
 translate([10, 0])
difference()
  {
    square(10, center = true);
    square(5, center = true);
  }
}
cube(1);





--
Sent from: http://forum.openscad.org/

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

nophead
Oddly F5 triangulates everything except the sqquare faces of the cube. I noticed with a sphere F5 does everything except the polar caps, they remain polygons, wierd!

image.png

On Mon, 17 Dec 2018 at 14:01, nop head <[hidden email]> wrote:
> This would imply that linear_extrude will not have to recourse to a tesselation for F5.
I don't understand why. I am not proposing any changes to linear_extrude.

Anyway it appears that polyhedron will accept faces with holes if they are tesselated correctly by the user. I exported your curved tube as STL and then converted it to a polyhedron with this website: https://jsfiddle.net/Riham/yzvGD/
The result is all triangles but CGAL converts all the planar faces back to polygons. Only the rotated end face remains partly triangulated due to floating point inacuracies. I.e. converting it to STL and back has improved the last segment!









On Mon, 17 Dec 2018 at 13:01, Parkinbot <[hidden email]> wrote:
see what happens to an almost planar face created by an rotate_extrude.
<http://forum.openscad.org/file/t887/rot.png>


rotate_extrude(angle = 160)
{
 translate([10, 0])
difference()
  {
    square(10, center = true);
    square(5, center = true);
  }
}
cube(1);





--
Sent from: http://forum.openscad.org/

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
CGAL anyway tesselates and retesselates faces on its will. linear_extrude()
and rotate_extrude() obviously don't use more complex faces respectively use
tesselation. Even sphere and cylinder at least for cones (r1, r2) construct
their faces mostly with triags and not with quads. What, beside a bunch of
options for implementation changes, would you gain by improving polyhedron()
to accept this kind of polygons with holes?


nophead wrote
> Oddly F5 triangulates everything except the sqquare faces of the cube. I
> noticed with a sphere F5 does everything except the polar caps, they
> remain
> polygons, wierd!

now look at this. I feed two bending faces defined by "almost planar"
polygons into a sweep. The two faces have a phase shift of 0 and 90 degrees.
Since I rely on the internal tesselation, I have to live with the result.
The upper face is a saddle, the lower face a sinus. (Knowing, what OpenSCAD
will probably do, I could of course change my construction code.)

use <Naca_sweep.scad>
sweep([circle(), Tz_(10, circle())]);  
function circle(r = 10, N=100, z=3) =
[for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2)]];
cube(1);
<http://forum.openscad.org/file/t887/sweep.png>


Now you can say. Ok, we allow even for polygons that describe bent faces.
And in the second step, lets also allow faces that close into a ring (or
even to moebius) ... See what I mean? I would prefer to be able to put a
tesselation of my choice into a sweep.

 



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
sorry I didn't sync the code with the image. This is the code:

use <Naca_sweep.scad>

sweep([circle(), Tz_(10, circle(phi = 90))]);  
function circle(r = 10, N=100, z=3, phi=0) =
[for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2+phi)]];
 
cube(1);

Parkinbot wrote
> use
> <Naca_sweep.scad>
> sweep([circle(), Tz_(10, circle())]);  
> function circle(r = 10, N=100, z=3) =
> [for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2)]];
> cube(1);
> &lt;http://forum.openscad.org/file/t887/sweep.png&gt; 





--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

nophead
In reply to this post by Parkinbot
> would you gain by improving polyhedron() to accept this kind of polygons with holes?
It is a lot easier to define faces as polygons than it is to tesselate in user space and feed a lot of triangles to polyhedron, mainly for endcaps, particialarly with holes.

I agree an OpenSCAD tessalation operation available to the user would also enable this but since the tesselation gets thrown way and regenerated many times in OpenSCAD people might complain their tessalation was ignored.

I find the tesselation linear_extrude does ugly in some situations with twist, e.g. fan blades. I fix it by adding more points along the blade that are slight purturbed to force more facets and hence the tessalation I want.
  
module squarish(s, n) {
        polygon([
            for(i = [0 : n]) [i * s.x / n,  s.y + (i % 2) * eps],
            for(i = [0 : n]) [s.x - i * s.x / n, (i % 2) * eps],
        ]);
    }
I think making OpenSCAD preserve tesselation would be an enourmous job while it use CGAL but fixing polyhedron is a small isolated changed.

 

On Mon, 17 Dec 2018 at 14:52, Parkinbot <[hidden email]> wrote:
CGAL anyway tesselates and retesselates faces on its will. linear_extrude()
and rotate_extrude() obviously don't use more complex faces respectively use
tesselation. Even sphere and cylinder at least for cones (r1, r2) construct
their faces mostly with triags and not with quads. What, beside a bunch of
options for implementation changes, would you gain by improving polyhedron()
to accept this kind of polygons with holes?


nophead wrote
> Oddly F5 triangulates everything except the sqquare faces of the cube. I
> noticed with a sphere F5 does everything except the polar caps, they
> remain
> polygons, wierd!

now look at this. I feed two bending faces defined by "almost planar"
polygons into a sweep. The two faces have a phase shift of 0 and 90 degrees.
Since I rely on the internal tesselation, I have to live with the result.
The upper face is a saddle, the lower face a sinus. (Knowing, what OpenSCAD
will probably do, I could of course change my construction code.)

use <Naca_sweep.scad>
sweep([circle(), Tz_(10, circle())]); 
function circle(r = 10, N=100, z=3) =
[for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2)]];
cube(1);
<http://forum.openscad.org/file/t887/sweep.png>


Now you can say. Ok, we allow even for polygons that describe bent faces.
And in the second step, lets also allow faces that close into a ring (or
even to moebius) ... See what I mean? I would prefer to be able to put a
tesselation of my choice into a sweep.





--
Sent from: http://forum.openscad.org/

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
In reply to this post by Parkinbot
And another interesting observation:

The iron law to do a sweep() is: Avoid (self) intersection of faces at any
cost. This doesn't seem to apply for intersecting bending faces. While F12
announces a failure, CGAL seems to happily digest it:  

use <Naca_sweep.scad>
sweep([circle(), Tz_(5, circle(phi = 180))]);  
function circle(r = 10, N=100, z=3, phi=0) =
[for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2+phi)]];
cube(1);

<http://forum.openscad.org/file/t887/sweep.png>

Will this open the path for a representation that lets us ignore (self)
intersections?



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

nophead
Odd CGAL normally throws an exception. Perhaps it gets past if no vertices colide.

Does it say simple is yes and can you export it to STL?

On Mon, 17 Dec 2018 at 15:24, Parkinbot <[hidden email]> wrote:
And another interesting observation:

The iron law to do a sweep() is: Avoid (self) intersection of faces at any
cost. This doesn't seem to apply for intersecting bending faces. While F12
announces a failure, CGAL seems to happily digest it: 

use <Naca_sweep.scad>
sweep([circle(), Tz_(5, circle(phi = 180))]); 
function circle(r = 10, N=100, z=3, phi=0) =
[for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2+phi)]];
cube(1);

<http://forum.openscad.org/file/t887/sweep.png>

Will this open the path for a representation that lets us ignore (self)
intersections?



--
Sent from: http://forum.openscad.org/

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
I can export it to STL and import it again without any problems.



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

nophead
So possibly self intersecting is fine as long as vertices don't coincide. The topology is prerved through triangle soup when the vertices are all unique.

On Mon, 17 Dec 2018 at 15:39, Parkinbot <[hidden email]> wrote:
I can export it to STL and import it again without any problems.



--
Sent from: http://forum.openscad.org/

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
In reply to this post by Parkinbot
it is even getting wierder and wierder:

<http://forum.openscad.org/file/t887/sweep.png>



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Does it allow boolean operations???

Parkinbot <[hidden email]> wrote:
it is even getting wierder and wierder:

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo wrote
> Does it allow boolean operations???

Yes, otherwise F10 wouldn't display a tesselation. Look at the code:

use <Naca_sweep.scad>
sweep([circle(), Tx_(3, circle(phi = 180))]);  
function circle(r = 10, N=100, z=3, phi=0) =
[for(i=[0:N-1])  [r*sin(360/N*i), r*cos(360/N*i), z*cos(360/N*i*2+phi)]];
cube(1);




--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Yes, I have observed before that a non-manifold polyhedron may be rendered. The union of the cube with your shape renders without error unless the cube intersect some self intersection areas of the shape. Try your example with cube(16), for instance. You will get a CGAL error. And even when the cube contains all your shape a CGAL error is issued. A strange shape (that resembles to be a difference) results without error with cube(6). 


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
In reply to this post by Parkinbot


Em seg, 10 de dez de 2018 às 20:07, Parkinbot <[hidden email]> escreveu:
A triangulation like earcut with holes will be cumbersome to implement in
OpenSCAD. However a fast and viable solution for implementing the multi-hole
sweep is to use a vectorized lazy union sweep for the holes and difference
the result from the sweep of the outer polygon. For export one will have to
use a Boolean operation to do a CGAL check anyway.


Parkinbot,

The earcut method works fine with polygons with holes expressed as a unique polygonal by bridging the holes and outer polygon by two-way bridges fully inside the polygon interior. We just need to relax the ear test by restricting it to the candidate ear interior. I have tested it with my implementation of the ear method and it worked like a charm.

The remaining problem is to find the two-way bridges that connect all the borders. The bridges in the runsun example are not allowed because they cross other polygonal edges. I have found a paper (https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) that proposes a method to find those bridges. I have implemented the method with good results. Here are two of them:

PolyHoles2.PNG
PolyHoles1.PNG

Find attached my implementation of the bridging method.



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

polyHoles.scad (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo,

thanks, this sounds like a progress. Although the no cross restriction will
be difficult to guarantee in general when defining such a polygon, it seems
to be a step forward to implementing a fast multi-hole sweep like for
regular grids with fancy holes as shown in the example code attached. But to
be honest, meanwhile I dislike the implicitness of this representation. When
adding a new hole to a given object one will have to alter the whole polygon
sequence. This is very clumsy and makes me prefer the solution I already
characterized:

Parkinbot wrote
> However a fast and viable solution for implementing the multi-hole
> sweep is to use a vectorized lazy union sweep for the holes and difference
> the result from the sweep of the outer polygon. For export one will have
> to
> use a Boolean operation to do a CGAL check anyway.

While this approach is a bit slower, it addresses an even larger class of
problems, since the multi-holes may even leave the outer body during the
sweep - which relaxes the no-mutual-intersection rule a bit. And it is easy
to add a new hole, because you just extend the vector describing the holes.

Nevertheless, if OpenSCAD offered a built-in lazy_union() operator, we
wouldn't have to discuss such things at all.

difference()
{
  cube([100, 100, 5], center = true);  
  forXY(10, 10, 10, 10)
  linear_extrude(5.01, center = true, twist=45, slices = 20)
  square(6, center= true);  
}

module forX(dx = 10, N=4) for($i=[0:N-1]) translate([-((N-1)/2-$i)*dx,0, 0])
children();
module forY(dy = 10, M=4) for($i=[0:M-1]) translate([0, -((M-1)/2-$i)*dy])
children();
module forXY(dx = 10, N=4, dy = 10, M=4) forX(dx, N) forY(dy, M) children();






--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo


Em qua, 9 de jan de 2019 às 12:45, Parkinbot <[hidden email]> escreveu:
But to
be honest, meanwhile I dislike the implicitness of this representation. When
adding a new hole to a given object one will have to alter the whole polygon
sequence. This is very clumsy and makes me prefer the solution I already
characterized:

I understand your point but I see a very simple and general way to overcome it.

Suppose we have a lazyUnion operator with the following header:

module lazyUnion(<list of objects>)

where the objects in the parameter list are given in a polyhedron data format, that is, a pair of vertex list and face list. This module is easy to be coded by:
1) concat in one list all vertices of all objects;
2) displace (by a fixed amount) the indices of the face list of an object to agree with the new order of the concatenated vertex list;
3) call polyhedron with the new vertex list and the concat of the updated face list.

Usually we think to lazy-union manifold objects but this may be generalized to lazy-union a set of surfaces that will enclose one (or many) manifold. Surely, we need to assure manifoldness of the result to have a proper object for CGAL. The ground of this generalization is that OpenSCAD aggregates multiple vertices with the same coordinates as one vertex as I mentioned 2 years ago (http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19203.html).

With that in mind, the sweep of a polygon with holes may be structured as:
a) individually sweep each polygonal border of the outer polygon and of the holes without their caps returning the result in a polyhedron data format (a simplification of the current sweep codes);
b) triangulate the sweep ends of polygons with holes and generate its result in a polyhedron data format;
c) call lazyUnion with the list of the above data.

As a final touch, each function which generates polyhedron data format should have an additional parameter to promote, when needed, the reversion of all its faces. This parameter, with default false, may be set true when a Thrown Together view shows an incorrect orientation of that surface.

lazyUnion thought as such has many other uses as the reference I gave above illustrates.

When facing cases where the swept holes leak out the outer sweep, then uses the slower boolean method.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo

you are right, changing the representation is a typical interface task and
can be easily done within sweep() and transparent to the user.  
Collect the first and last faces of the outer manifold and the holes, find
the right polyHoles-polygon to represent it and then use earcut. The rest is
a vectorized sweep.
I haven't had time to play with your algorithm more extensively as I am
short of time being on travel until Sunday. Can you post the current version
of your earcut()? Don't find mine anymore.

I would propose the following interface to keep the "affine" state as long
as possible - and allow for the lazy union of multihole sweeps:  

module sweepMH(manifolds)
{
   prepdata = sweepMH(manifolds);
   polyhedron(prepdata[0], prepdata[1]);
}
 
function sweepMH(manifolds) =
  let(firstface = earcut(polyHole(manifolds)))
  let(lastface = earcut(polyHole(manifolds, last=true))
...






--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Parkinbot,

Find attached my last version of the polygon triangulation. I have reviewed it converting recursions to iterations with C-like for in order to escape the cycles early as possible. This version of the ear method is adapted to polygons with two-way bridges. I have also a simple polygon check but it rejects polygons with bridges. To accept polygon with bridges in that check requires a whole new set of cumbersome tests. I don't like my implementation of the check that resort to quick sort to make it somewhat more efficient but if you want to try it, let me know. Another function that you may consider, that is included in the same file of the simple polygon test, is the plane fitting and projection to "flatten" almost planar 3D polygons converting it in a 2D polygon before the triangulation is called.

Both polygon triangulation and polygon with holes bridging methods fail if they receive a non valid input. Without a proper validity check their use is a blind fly.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

polygon_triangulation_2.scad (4K) Download Attachment
12345