Rounded Polygon

classic Classic list List threaded Threaded
172 messages Options
123456789
Reply | Threaded
Open this post in threaded view
|

Re: Rounded Polygon

adrianv
Parkinbot wrote

> adrianv wrote
>
> hull() for(i=[10,20]) cube(i);
>
> translates into the CSG tree:
>
> hull() {
>   group() {
>     cube(size = [10, 10, 10], center = false);
>     cube(size = [20, 20, 20], center = false);
>   }
> }
>
> If you edit the CSG file to
>
> hull() {
>     cube(size = [10, 10, 10], center = false);
>     cube(size = [20, 20, 20], center = false);
> }
>
> you obviously get the desired result. Therefore

What is the difference between these two things?   Taking the hull() of an
individual cube won't do anything.  

I thought the interesting case was wanting to do sequential hulls, like the
hull of every adjacent pair of objects in a list, where the list was
produced by for().  





--
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: Rounded Polygon

Parkinbot
adrianv wrote
> What is the difference between these two things?   Taking the hull() of an
> individual cube won't do anything.  

The code hulls *two* cubes. They could be translated to create something
meaningful, but this doesn't matter for the argument. The cubes will get
unioned in the first case and then hulled, and in the second case they
*only* get hulled. (Better think of 8 (translated) corners to be hulled to
gain a BezierCube).
While the result is the same, it is a significant runtime difference,
whether hull() will operate over a set of objects or a unioned object.
hull() is much faster then union().





--
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: Rounded Polygon

Ronaldo
Parkinbot <[hidden email]wrote:
While the result is the same, it is a significant runtime difference,
whether hull() will operate over a set of objects or a unioned object.
hull() is much faster then union(). 
 
Hum... There is something strange here. The following code generates a regular cube even with F6:

hull() 
for(i=[0,1]){
  polyhedron([[0,0,i],[1,0,i],[1,1,i],[0,1,i]],[[0,1,2,3,4]]);
  cube(0.5);
}

although the two polyhedron are defective (non-manifold). If we drop the hull() we get a non-manifold warning with F6. So, I don't think the hull() for(){  } construct really does any union before the hull().


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

Re: Rounded Polygon

Ronaldo
In reply to this post by Parkinbot


 Parkinbot <[hidden email]> wrote:
I just tried a run for which I put each corner as an explicite instance into
the hull body. It looks like the compile time is indeed even faster than a
full sweep (1s only). This seems to shout for a hull_for() operator that
behaves similar like the intersection_for.

We don't need a hull_for() to have a faster run. hull() disregards any edge or facets of the objects we collect for it. It operates just on the vertices. As we don't have a primitive point, we need to resort to polyhedron to hull() a list of points like I do here:

$fn= 10;           // number of points in all roundover
r0 = 0.15;         // shape parameter
r  = 2;            // rounding "radius"
s  = [10,15,20];   // cube edge length

roundedCube(s,r,r0);

module roundedCube(s=10, r=1, r0=0.073) {
  n=$fn?$fn:360/$fa;       // resolution 
  s=s[0]==undef?[s,s,s]:s; // allow for vector and number
  r = abs(r); 
  if(r==0) 
    cube(s, center=true); 
  else {
    cp  = cornerPatchCP(-s/2,r,r0);
    cp0 = PatchSample(cp,n);            // corner at -s/2
    Mx  =[[-1,0,0],[0, 1,0],[0,0, 1]];
    My  =[[ 1,0,0],[0,-1,0],[0,0, 1]];
    Mz  =[[ 1,0,0],[0, 1,0],[0,0,-1]];
    cp2 = concat( cp0, [for(pi=cp0) Mx*pi] );
    cp4 = concat( cp2, [for(pi=cp2) My*pi] );
    cp8 = concat( cp4, [for(pi=cp4) Mz*pi] );
    hull() polyhedron(cp8, [[for(i=[0:len(cp8)-1]) i]]);
  }
}
  
function BezierPoint(p, u) =
    (len(p) == 2)? 
        u*p[1] + (1-u)*p[0] :
        u*BezierPoint([for(i=[1:len(p)-1]) p[i] ], u) 
          + (1-u)*BezierPoint([for(i=[0:len(p)-2]) p[i] ], u);
            
function BPatchPoint(p,u,v) =
  BezierPoint(BezierPoint(p, u), v);
          
function PatchSample(cp,n) =
  [for(i=[0:n-1], j=[0:i]) 
    BPatchPoint(cp,i/(n-1),i==0? 0 : j/i) ];

function cornerPatchCP(P0,d,r0=0.5) =
  let( dx = d*[1,0,0], 
       dy = d*[0,1,0],
       dz = d*[0,0,1] )
  [ [for(j=[0:4]) P0+dx+dy],
    cCP([P0+dx+(1-r0)*dy, P0+(dx+dy)*(1-r0), P0+dx*(1-r0)+dy],r0),
    cCP([P0+dx, P0, P0+dy], r0),
    cCP([P0+dx+(1-r0)*dz, P0+(1-r0)*dz, P0+dy+(1-r0)*dz],r0),
    cCP([P0+dx+dz, P0+dz, P0+dy+dz],r0) ];
  
function cCP(p,r0=0.5) =
  [ p[0],
    p[0]+r0*(p[1]-p[0]),
    p[1],
    p[2]+r0*(p[1]-p[2]),
    p[2] ];

This is the fastest strategy I can imagine. The points sampled from the corner patches are collected in a simple list which will be the vertices of the fake polyhedron to be hulled. That fake polyhedron has just one face collecting all the vertex indices. This polyhedron is defective and it is not a manifold at all but that polyhedron is not really built, just hulled.

The second aspect of the code is that it samples the corner patch in an non uniform distribution in the parameter space. The sample rate is poor near the collapsed row of the rectangular patch and increases linearly up to the opposed patch edge. As the patch is really triangular, the sampling is geometrically more uniform. 

cornerSampling.PNG

I haven't tried your code yet (although I have borrowed some lines of code from it :) ) but I believe this last code is faster. It renders the cube in 1s with $fn=50 and in 12s with $fn=100.

Anyway, "fast" is of course always relative, because any further Boolean
operation will take its time with these vertex monsters.

It is not a monster. The number of vertices of the rounded cube is about the same of one sphere with the same $fn. So, I would not expect anything worst than the boolean operation with a sphere. In fact, it required just 9s to difference a cylinder crossing a rounded edge with $fn=32. 

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

Re: Rounded Polygon

Parkinbot
In reply to this post by Ronaldo
Ronaldo wrote
> although the two polyhedron are defective (non-manifold). If we drop the
> hull() we get a non-manifold warning with F6. So, I don't think the hull()
> for(){  } construct really does any union before the hull().

I think warnings are only tested and emitted on the final object.



--
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: Rounded Polygon

Parkinbot
In reply to this post by Ronaldo
Ronaldo wrote
> We don't need a hull_for() to have a faster run. hull() disregards any
> edge
> or facets of the objects we collect for it. It operates just on the
> vertices. As we don't have a primitive point, we need to resort to
> polyhedron to hull() a list of points like I do here:

If you create a convex body it is indeed avoidable - even I would say, it is
a work-around if you have to recur to a lazy-union to avoid the "for union
problem".

The following code creates a random convex body and looks a bit dirty. I am
somehow very reluctant to build a serious library module on this technique:

points = [for(i=[0:30]) rands(-10, 10, 3)];
faces =   [[for(i=[0:len(points)-1]) i]];
hull() polyhedron(points, faces);  // tricky convex body

However, there are also non-convex shapes. For them you need to do a proper
sweep, so this strategy is quite limited. In general I prefer to create such
a patch in a way so that it can also be swept.





--
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: Rounded Polygon

adrianv
Wouldn't Oskar Linde's hull() function solve this problem?  I don't know its
runtime performance, but it takes a point list and computes faces of the
convex hull without the uncomfortable scheme of creating a bogus polyhedron.  

https://github.com/openscad/scad-utils/blob/master/hull.scad



--
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: Rounded Polygon

Parkinbot
adrianv wrote
> Wouldn't Oskar Linde's hull() function solve this problem?  

It wouldn't solve the problem, because in general we have the case in which
a for-loop will create objects (even fancy polyhedra are objects) that get
hulled, and Oskar Linde's hull() function depends like a lazy union on a
point representation, which OpenSCAD is successfully hiding from user space.

But for fun, I did a quick runtime test and compared Oskar Linde's hull()
function with the fancy hull()polyhedron() approach. It turned out that
Oskar's function is indeed pretty much faster, when it comes to a higher
number of points. Good to know!

points = [for(i=[0:3000]) rands(-10, 10, 3)];

// polyhedron (points, hull(points));  // Oskar's approach: 6s

faces =   [[for(i=[0:len(points)-1]) i]];  
hull() polyhedron(points, faces);  // tricky convex body 74s:






--
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: Rounded Polygon

Ronaldo
In reply to this post by adrianv
I have never tried Oskar Linde's hull(). I will give it a go.

However, the bogus polyhedron technique seems to be faster and simpler. For the advocates of more orthodox solutions, it is possible to apply hull to a set of spherical regular polyhedron built by lazyUnion() the 8 corner patches glued together. As hull() will consider just the vertices and disregard the edges and faces, that seems to be a waste of running time and coding effort.

I have not looked at the sweep technique in detail yet. My concern would certainly be on the curvature continuity. 

It is a great news (and surprise) that Oskar Linde's hull is so fast. I will study it.

A domingo, 24/03/2019, 11:44, adrianv <[hidden email]> escreveu:
Wouldn't Oskar Linde's hull() function solve this problem?  I don't know its
runtime performance, but it takes a point list and computes faces of the
convex hull without the uncomfortable scheme of creating a bogus polyhedron. 

https://github.com/openscad/scad-utils/blob/master/hull.scad



--
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: Rounded Polygon

Ronaldo
In reply to this post by Parkinbot


Parkinbot <[hidden email]> wrote:
adrianv wrote
> Wouldn't Oskar Linde's hull() function solve this problem? 
(...)
But for fun, I did a quick runtime test and compared Oskar Linde's hull()
function with the fancy hull()polyhedron() approach. It turned out that
Oskar's function is indeed pretty much faster, when it comes to a higher
number of points. Good to know!

points = [for(i=[0:3000]) rands(-10, 10, 3)];

// polyhedron (points, hull(points));  // Oskar's approach: 6s

faces =   [[for(i=[0:len(points)-1]) i]]; 
hull() polyhedron(points, faces);  // tricky convex body 74s:

I have checked this comparison and concluded that the delay of the second alternative is due to the big face in the polyhedron call. I guess that the system does a triangulation of that bogus face. Instead of one big face I have defined a big list of triangular faces covering all vertices and the results were very different:

points = [for(i=[0:120000-1]) rands(-10, 10, 3)]; 
faces =   [for(i=[0:3:len(points)-1]) [i,i+1,i+2]];   
hull() // hull() spent 0s
  polyhedron(points, faces);  // tricky polyhedron spent 3s

On the other hand, Oskar Linde's hull() crashed with 6000 or more points. If that function were used in a roundedCube code, it would crash with $fn>=38.

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

Re: Rounded Polygon

Parkinbot
Good solution. Your code took 16s on my machine.



--
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: Rounded Polygon

Ronaldo
In reply to this post by Ronaldo

Ronaldo Persiano <[hidden email]> wrote:
This is the fastest strategy I can imagine. The points sampled from the corner patches are collected in a simple list which will be the vertices of the fake polyhedron to be hulled. That fake polyhedron has just one face collecting all the vertex indices. This polyhedron is defective and it is not a manifold at all but that polyhedron is not really built, just hulled.

There is no need to resort to bogus polyhedra to follow the strategy based on hull(). Instead, we just build a valid polyhedron for each corner and hull() them all. Surprisingly, the preview and render times are nearly the same as the bogus polyhedron previous code although the code is a bit more complex.

$fn = 40;           // number of points in all roundover
                    // 6560 vertices for $fn = 40
r0  = 0.073;        // shape parameter (this value approximates a circular arc)
r   = 1.5;          // rounding "radius"
s   = [15,15,20];   // cube edge length

difference(){
  roundedCube(s,r,r0);
  rotate(90,[1,1,0])cylinder(r=2,h=40); // to check F6 validity
}

// round the edges and vertices of a block with dimensions s centered at the origin
//  s  - block dimensions; may be a number or a 3d vector
//  r  - the extension of the edge ends that are rounded; 
//       equivalent to the radius of a circular rouding
//  r0 - rounding shape parameter ( 0<=r0<1 )
module roundedCube(s=10, r=1, r0=0.073) {
  n = $fn ? $fn: 360/$fa;       // resolution 
  assert(0*s==0 || 0*s==[0,0,0], "improper size value s");
  s = s[0]==undef ? [s,s,s]: s; // allow for vector and number
  assert(s[0]>0 && s[1]>0 && s[2]>0, "improper cube dimensions s");
  r = abs(r); 
  if(r==0) 
    cube(s, center=true); 
  else {
    assert(2*r<=min(s), "radius r too large for the cube dimensions");
    assert(r0>=0 && r0<1, "shape parameter r0 must satisfy 0<=ro<1" );
    cp  =  cubeCornerPatchCP(-s/2,r,r0); // corner at -s/2
    cp0 = PatchSample(cp,n);            
    pd0 = cornerPoly(cp0);              // base corner patch pdat
    Mx  = [[-1,0,0],[0, 1,0],[0,0, 1]]; // mirror matrices
    My  = [[ 1,0,0],[0,-1,0],[0,0, 1]];
    Mz  = [[ 1,0,0],[0, 1,0],[0,0,-1]];
    pd1 = [pd0];
    pd2 = concat(pd1, transfPdata(Mx,pd1)); // patch mirrorings
    pd4 = concat(pd2, transfPdata(My,pd2));
    pd8 = concat(pd4, transfPdata(Mz,pd4));
    hull()
      lazyUnion(pd8);                       // union of the 8 corners
  }
}

// unify the polyhedron data in list mPoly and call polyhedron
// assume the final polyhedron has no self-intersections
module lazyUnion(mPoly) {
  // acc = accumSum(l) => acc[0]==0, acc[i]==acc[i-1]+l[i-1]
  function accSum(l, res=[0]) =
    len(res) == len(l) ?
      res :
      accSum(l, concat(res, [ res[len(res)-1]+l[len(res)-1] ] ));
  
  verts = [for(p=mPoly) each p[0] ];
  nvert = [for(p=mPoly) len(p[0]) ];
  accv  = accSum(nvert);
  faces = [for(i=[0:len(mPoly)-1], fac=mPoly[i][1] )
              [for(v=fac) v+accv[i] ] ];
  polyhedron(verts, faces);
}

// transform all the vertices of each polyhedron data in list pdat by matrix M
function transfPdata(M, pdat) = [for(pdi=pdat) [ pdi[0]*M, pdi[1] ] ];

// the polyhedron of a corner in pdat format 
function cornerPoly(tpatch) =
  let( n = len(tpatch) ) echo(len(tpatch),[for(i=[0:n-1])   (n-1)*n/2+i ])
  [ [ for(i=[0:n-1], j=[0:i]) tpatch[i][j] ], // corner vertices
    // corner faces
    [ for(i=[1:n-1], j=[0:i-1]) let( k = i*(i+1)/2 ) 
        each [ [ k+j, k+j-i, k+j+1 ],  
        if(j<i-1)[ k+j-i, k+j-i+1, k+j+1] ], 
      // triangular patch back faces
      [for(i=[0:n-1])      i*(i+1)/2 ],
      [for(i=[n-1:-1:0]) i*(i+1)/2+i ],
      [for(i=[0:n-1])    (n-1)*n/2+i ],
      [  0, (n-1)*n/2, (n-1)*n/2+n-1 ]
    ]
  ];
           
// a point in a Bezier curve 
//  p - patch control points
//  u - parameter value 
function BezierPoint(p, u) =
    (len(p) == 2)? 
        u*p[1] + (1-u)*p[0] :
        u*BezierPoint([for(i=[1:len(p)-1]) p[i] ], u) 
          + (1-u)*BezierPoint([for(i=[0:len(p)-2]) p[i] ], u);
            
// a point in a Bezier surface patch 
//  p   - patch control points (matrix)
//  u,v - parameter values 
function BPatchPoint(p,u,v) =
  BezierPoint(BezierPoint(p, u), v);
          
// sample a Bezier patch with a triangular distribuition
// cp - control points of the patch
// n  - resolution
// a total of n*(n+1)/2 points are sampled
function PatchSample(cp,n) =
  [for(i=[0:n-1]) 
    [for(j=[0:i]) BPatchPoint(cp,i/(n-1),i==0? 0 : j/i) ] ];

// control points of a Bezier patch of a cube corner with curvature continuity
//   P0 - cube corner vertex
//   r  - the ammount of the 3 edges at the corner to be rounded
//   r0 - shape parameter
function cubeCornerPatchCP(P0,r,r0=0.5) =
  [for(p=curveCP([P0+[r,r,0],P0+[r,0,0],P0+[r,0,r]],r0))
         curveCP([p, [p[1],p[1],p[2]], [p[1],p[0],p[2]] ], r0) ];

// control points of a degree 4 Bezier curve
// starting and ending with zero curvature
//  p  - corner to be rounded (list of 3 points)
//  r0 - shape parameter
function curveCP(p,r0=0.5) =
  [ p[0], p[0]+r0*(p[1]-p[0]), p[1], p[2]+r0*(p[1]-p[2]), p[2] ];

That code is rather fast. It takes 14s to render a rounded block with 6560 vertices. 

Parkinbot, wrote: 
However, there are also non-convex shapes. For them you need to do a proper
sweep, so this strategy is quite limited. In general I prefer to create such
a patch in a way so that it can also be swept. 

Yes, this technique is valid just for convex bodies. For non-convex objects, we will have eventually to recode the computation of the patches and it will be hard to find general solutions for corners with more than 4 incoming edges. On the other hand, I don't see how to manage the rounding for general cases with sweeps.


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

Re: Rounded Polygon

adrianv
I took a look at the code.  Is it the case, Ronaldo, that your method is
creating a true bezier triangle, with the desired 3-axis symmetry?  I read
that the bezier triangular patch can be obtained by sampling a patch in a
triangle or by collapsing two points together, but details were sparse on
what happens to the control points under these transformations.  

Is the only difference between the last two versions the method of getting
the hull()?  (Do they produce the same patch?)  

And the sweep method Parkinbot posted is my original notion of sweeping the
bezier around the bezier, right?  Do you think the curvature condition will
not hold for this approach?  It seems like you could get into trouble if the
sweeping trajectory doesn't meet some kind of conditions (maybe a maximum
curvature condition?)  

It seems hard to imagine generalizing continuous curvature corners beyond
solids created by linear extrusion, and for that case, it seems like the
sweep approach will be easier, no?  I could imagine, instead of making
corners and hulling, making a sweep around an entire shape, though I suppose
it gets to be a lot of vertices.   But this would handle concave corners, I
think?   (Corners that are concave in one direction but convex in the
other.)  

With the bezier patch we have 4 edges so we could round over an octahedron,
I suppose, but it not a particularly powerful generalization.  

I also noticed a couple things about using bogus faces to polyhedron().
When I use the second method of creating triangles, I somtimes get "PolySet
has degenerate polygons".  What does that mean?  Some triangle is colinear,
or a polygon includes some colinear points?  What does polyhedron do if you
give it a non-coplanar polygon?  

When I tried swapping in this method into the bezier code the run time
increased from 2s to 3s for me (with
$fn=100, 40400 points in a corner patch.)   I tried increasing to $fn=200,
and now 160800 points in a corner patch, and then the triangles are much
faster.  





--
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: Rounded Polygon

Ronaldo


adrianv <[hidden email]> wrote:
I took a look at the code.  Is it the case, Ronaldo, that your method is
creating a true bezier triangle, with the desired 3-axis symmetry? 

In that last code, I still use rectangular Bezier patches with a collapsing row of control points so I would not expect a 3-axis symmetry. The corner patch is the same it was used in the previous code (I have just simplified the function that computes the patch CP). 
 
 I read that the bezier triangular patch can be obtained by sampling a patch in a 
triangle or by collapsing two points together, but details were sparse on
what happens to the control points under these transformations. 

I am afraid that information is not correct.
Is the only difference between the last two versions the method of getting
the hull()?  (Do they produce the same patch?) 

Yes, see above.
 
And the sweep method Parkinbot posted is my original notion of sweeping the
bezier around the bezier, right?  Do you think the curvature condition will
not hold for this approach?  It seems like you could get into trouble if the
sweeping trajectory doesn't meet some kind of conditions (maybe a maximum
curvature condition?) 

Your sweep conception seems to lead to a curvature continuity in the two axis but I have not analysed it in detail. I can not say that the Parkinbot sweep code really follows you original conception because I have not studied his code. Anyway, the results of a sweeping method would be different in nature from what I have done. I would expect that the planar face of the rounded block by the sweep method will not be a rectangle (as in my model) but a rounded rectangle.
 
It seems hard to imagine generalizing continuous curvature corners beyond
solids created by linear extrusion, and for that case, it seems like the
sweep approach will be easier, no? 

I would say that this last code could be easily extended to round any convex polyhedron where just three edges meet at each vertices (like for instance a dodecahedron). It is possible to remodel the corner patch in order to round corners where 4 edges meet but I don't know how extend that to more general cases where more than 4 edges meet at some corner. I don't know how to apply the sweep method to round a dodecahedron.
 
I could imagine, instead of making
corners and hulling, making a sweep around an entire shape, though I suppose
it gets to be a lot of vertices.   But this would handle concave corners, I
think?   (Corners that are concave in one direction but convex in the
other.) 

With the bezier patch we have 4 edges so we could round over an octahedron,
I suppose, but it not a particularly powerful generalization. 

Yes, see above.
I also noticed a couple things about using bogus faces to polyhedron().
When I use the second method of creating triangles, I somtimes get "PolySet
has degenerate polygons".  What does that mean?  Some triangle is colinear,
or a polygon includes some colinear points?  What does polyhedron do if you
give it a non-coplanar polygon? 

Did you get that warning with my last code? That warning usually means that there is degenerated faces (colinear points)  or a badly structured face list or the point list has some point not referenced by any face. If some face is non-planar, the system triangulate it in some arbitrary way. In my last code, the corner polyhedron has 3 non-triangulated planar faces. 
 
When I tried swapping in this method into the bezier code the run time
increased from 2s to 3s for me (with
$fn=100, 40400 points in a corner patch.)   I tried increasing to $fn=200,
and now 160800 points in a corner patch, and then the triangles are much
faster. 

I haven't understood what you have done here.

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

Re: Rounded Polygon

adrianv
Ronaldo wrote
> adrianv &lt;

> avm4@

> &gt; wrote:
>
>> I took a look at the code.  Is it the case, Ronaldo, that your method is
>> creating a true bezier triangle, with the desired 3-axis symmetry?
>
>
> In that last code, I still use rectangular Bezier patches with a
> collapsing
> row of control points so I would not expect a 3-axis symmetry. The corner
> patch is the same it was used in the previous code (I have just simplified
> the function that computes the patch CP).
>
>
>>  I read that the bezier triangular patch can be obtained by sampling a
>>  patch in a
>>  triangle or by collapsing two points together, but details were sparse
>> on
>> what happens to the control points under these transformations.
>
> I am afraid that information is not correct.

Are you sure?  Are bezier patches or curves a different representation of
the degree n (or degree n,m) polynomial, or are there polynomials not
represented by the bezier framework?  It appears just based on counting
parameters that it should be possible to get all polynomials with a bezier
representation, which would mean the claim I quoted above is true...but
perhaps not very interesting without a control point mapping.  

>> And the sweep method Parkinbot posted is my original notion of sweeping
>> the
>> bezier around the bezier, right?  Do you think the curvature condition
>> will
>> not hold for this approach?  It seems like you could get into trouble if
>> the
>> sweeping trajectory doesn't meet some kind of conditions (maybe a maximum
>> curvature condition?)
>>
>
> Your sweep conception seems to lead to a curvature continuity in the two
> axis but I have not analysed it in detail. I can not say that the
> Parkinbot
> sweep code really follows you original conception because I have not
> studied his code. Anyway, the results of a sweeping method would be
> different in nature from what I have done. I would expect that the planar
> face of the rounded block by the sweep method will not be a rectangle (as
> in my model) but a rounded rectangle.

I haven't studied his code yet either.  I have to first understand the sweep
function, so it seemed like a bit more work.  It seems possible that the
result would be different in nature, but I don't agree that the planar face
would be rounded.   Suppose I sweep a square along a line.  The result---a
standard linear extrude---is a cuboid shape with rectangular faces.  If I
sweep a rounded-corner square along a line I will get a cuboid shape with
rounded edges, four rectangular faces, and then two ends whose faces are the
rounded corner square.   If I sweep a rounded corner square along a rounded
corner square then (assuming the roundover doesn't dominate the square), the
square's sides will have flat sections and the sweep will convert these into
rectangular faces.   I think that the resulting shape should actually be
identical to the shape produced from the bezier method except (possibly) at
the corners.  


>> It seems hard to imagine generalizing continuous curvature corners beyond
>> solids created by linear extrusion, and for that case, it seems like the
>> sweep approach will be easier, no?
>
> I would say that this last code could be easily extended to round any
> convex polyhedron where just three edges meet at each vertices (like for
> instance a dodecahedron). It is possible to remodel the corner patch in
> order to round corners where 4 edges meet but I don't know how extend that
> to more general cases where more than 4 edges meet at some corner. I don't
> know how to apply the sweep method to round a dodecahedron.

Yes, definitely it should be straight forward to adapt your approach to a
meeting of 3 edges, and the ordinary square bezier can handle corners where
4 edges meet.  I wonder if the triangular bezier can be generalized to an
n-gon bezier defined somehow on a regular n-gon?  

What the sweep approach can (at least in principle) do is apply a roundover
to an (arbitrary?) shape that is generated by linear extrusion.  Basically
instead of doing linear extrusion you sweep along the shape's boundary a
rounded rectangle of the appropriate dimensions to create the desired shape.  

>> I also noticed a couple things about using bogus faces to polyhedron().
>> When I use the second method of creating triangles, I somtimes get
>> "PolySet
>> has degenerate polygons".  What does that mean?  Some triangle is
>> colinear,
>> or a polygon includes some colinear points?  What does polyhedron do if
>> you
>> give it a non-coplanar polygon?
>>
>
> Did you get that warning with my last code? That warning usually means
> that
> there is degenerated faces (colinear points)  or a badly structured face
> list or the point list has some point not referenced by any face. If some
> face is non-planar, the system triangulate it in some arbitrary way. In my
> last code, the corner polyhedron has 3 non-triangulated planar faces.

No, not with the latest version of your code.  With tests of the application
of hull() to bogus polyhedra.  


>> When I tried swapping in this method into the bezier code the run time
>> increased from 2s to 3s for me (with
>> $fn=100, 40400 points in a corner patch.)   I tried increasing to
>> $fn=200,
>> and now 160800 points in a corner patch, and then the triangles are much
>> faster.
>>
>
> I haven't understood what you have done here.

Your earlier version of the bezier code used the bogus polyhedron method
with one large face.  I substituted small bogus triangles and it got
slightly slower when there were 40000 points in the patch.  But when there
were 160000 bogus triangles were much faster than one huge bogus face.  

___



--
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: Rounded Polygon

Ronaldo


 adrianv <[hidden email]> wrote:
>>  I read that the bezier triangular patch can be obtained by sampling a
>>  patch in a
>>  triangle or by collapsing two points together, but details were sparse
>> on
>> what happens to the control points under these transformations.
>
> I am afraid that information is not correct.

Are you sure?  Are bezier patches or curves a different representation of
the degree n (or degree n,m) polynomial, or are there polynomials not
represented by the bezier framework?  It appears just based on counting
parameters that it should be possible to get all polynomials with a bezier
representation, which would mean the claim I quoted above is true...but
perhaps not very interesting without a control point mapping. 

Yes, I am quite sure. A rectangular Bezier patch with degrees n and m is in a (large but incomplete) subset of all two variables polynomials of degree (n+m). A triangular Bezier patch of degree n is really a  two variable polynomial of degree n and it has (n+1)(n+2)/2 coefficients (CPs). In our case, degree 4, triangular patches have 15 CPs while a rectangular patch of degree 4x4 will have 25 CPs. I guess that positioning appropriately those 25 CPs we would get any degree 4 polynomial in two variable. But the interrelations of those CPs will be something much more complex than you have referred. At the end, just 15 degree of freedom will remain. There is no sampling that would exempt the fulfillment of those 10 relations.

Yes, definitely it should be straight forward to adapt your approach to a
meeting of 3 edges, and the ordinary square bezier can handle corners where
4 edges meet.  I wonder if the triangular bezier can be generalized to an
n-gon bezier defined somehow on a regular n-gon? 

As far as I know, there is no n-gon Bézier patch for n>4.

> Did you get that warning with my last code? That warning usually means
> that
> there is degenerated faces (colinear points)  or a badly structured face
> list or the point list has some point not referenced by any face. If some
> face is non-planar, the system triangulate it in some arbitrary way. In my
> last code, the corner polyhedron has 3 non-triangulated planar faces.

No, not with the latest version of your code.  With tests of the application
of hull() to bogus polyhedra. 

The way I have defined that large bogus face, by taking each 3 points in sequence as vertices of a triangle, some vertices may remain untouched by any face when the number of vertices is not multiple of 3 and that will generate a warning like you get.
Your earlier version of the bezier code used the bogus polyhedron method
with one large face.  I substituted small bogus triangles and it got
slightly slower when there were 40000 points in the patch.  But when there
were 160000 bogus triangles were much faster than one huge bogus face. 

Were you comparing the running time of the bogus polyhedron process with the Oskar Linde's hull() of points?

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

Re: Rounded Polygon

adrianv
I have made an attempt at the triangular bezier patch.  I do not know if I
have picked parameters that achieve continuous curvature, but the patch is
looking reasonable.  Here is one corner, with control points displayed.
There are 3 control points that appear "free" in some sense---that is, not
falling on the edge with their value already determined to achieve the
continuous curvature edge curve.  

<http://forum.openscad.org/file/t2477/tribez2.png>

Here's the code.  It seems like computing the bezier points is kind of slow,
but I don't know if there's a more clever way to do it.  

h=0.6;
corner = [0,0,0];
dx = [-1,0,0];
dy = [0,-1,0];
dz = [0,0,-1];
P1 = corner-dx-dy;
P2 = corner-dx-dz;
P3 = corner-dy-dz;
P12 = corner-dx;
P13 = corner-dy;
P23 = corner-dz;
P2face = corner-h*dx-h*dz;
P1face = corner - h*dx-h*dy;
P3face = corner-h*dy-h*dz;


P = [
 [P1,               P12+h*(P1-P12), P12,    P12+h*(P2-P12), P2],
 [P13 + h*(P1-P13), P1face,         P2face, P23+h*(P2-P23)],
 [P13,              P3face,         P23],
 [P13 + h*(P3-P13), P23 + h*(P3-P23)],
 [P3]
];


sdx=1/16;
pts = ( [for(u=[0:sdx:1])
    each [for(v=[0:sdx:1-u]) tribez(P,u,v)]]);
echo(len(pts), "points");

fastpointhull(pts);  //polyhedron(pts, faces=hull(pts));

function tribez(P,u,v) = len(P) == 1 ? P[0][0] :
   let(
     n = len(P)-1,
     Pu = [for(i=[0:n-1]) select(P[i],[1:len(P[i])-1])], //  
select(P[i],1,-1)],
     Pv = [for(i=[0:n-1]) select(P[i],[0:len(P[i])-2])], //  
select(P[i],0,len(P[i])-2)],
     Pw = select(P,[1:n])
     )
   tribez(u*Pu+v*Pv+(1-u-v)*Pw,u,v);
     
%cube(size=[1,1,1]);


module fastpointhull(points){
    //points = simplify3d_path(points);  // colinear points are not on the
hull and generate a warning message
    extra = len(points)%3;
    list = concat(
                [[for(i=[0:extra+2])i]],
                [for(i=[extra+3:3:len(points)-3])[i,i+1,i+2]]);
    hull() polyhedron(points, faces=list);
}


function select(vector,indices) = [ for (index = indices) vector[index] ];




--
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: Rounded Polygon

Ronaldo
adrianv <[hidden email]> wrote:
I have made an attempt at the triangular bezier patch.  I do not know if I
have picked parameters that achieve continuous curvature, but the patch is
looking reasonable.  Here is one corner, with control points displayed.
There are 3 control points that appear "free" in some sense---that is, not
falling on the edge with their value already determined to achieve the
continuous curvature edge curve.   

Nice work! I was following the same route but with degree 6 triangular patch which is, I suppose, the minimum degree to have curvature continuity.
But I could not find a good way to compute curvature for triangular patches to check my models. Anyway, I am afraid that the 3 CPs you consider free to shape the surface should have precise positions to get curvature continuity. I have drawn the triangular grid of your CPs and got the following image with h=0.3.

As the central triangle is not coplanar with any of the corner planes I think we would not have zero cross border second derivative at the patch borders. Perhaps we get zero cross border curvature with h=0 but that is too much restrictive.

My next step will be to compute the cross border curvature to check the surface models.

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

ControlNet_h_0.3.PNG (28K) Download Attachment
ControlNet_h_0.PNG (21K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Rounded Polygon

Parkinbot
In reply to this post by adrianv
Looks like a patch, but it doesn't make a smooth connection on rotation ...

translate([-1, -1])fastpointhull(pts);  
rotate([0,0,90])
translate([-1, -1])fastpointhull(pts);  

<http://forum.openscad.org/file/t887/patch.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: Rounded Polygon

adrianv
It's not clear to me what the constraints are for controlling the derivative
matching for the triangular patch, but yes, it appears I have with order 4
not even matched the first derivative.  

So this raises the questions:  Is the code correct?  Is it possible to match
derivatives as desired (with a patch of sufficient order)?  

Should the edges of the patch match the 4th order 1d bezier curve with the
same control points?  



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

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