# Can you sweep a object with fingers Classic List Threaded 61 messages 1234
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 Ronaldo wrote Bezier curves are different: they interpolates just the first and last control points and they are in the convex hull of its control points. In that case, I must have applied the Bezier in a wrong way. These curves are indeed built with Bezier approach, but I applied it pair-wise (each pair generates 4 CPs), so points between each pair are Bezier points. \$ Runsun Pan, PhD \$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); \$ Tips; \$ Snippets
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 2016-11-22 16:39 GMT-02:00 runsun :In that case, I must have applied the Bezier in a wrong way. These curves are indeed built with Bezier approach, but I applied it pair-wise (each pair generates 4 CPs), so points between each pair are Bezier points. Ok, I see what you have done, you did right. It is a C1 interpolation spline, sometimes called Hermite spline. You possibly estimates the tangents at the points and find the Bezier CPs of each polynomial arc based on the tangents and the extremes points of the arc. But then, the BezierCPs are not all interpolated and two of them for each arc control the starting end ending arc tangent. The same happens with Bezier CPs of surfaces: some CPs are interpolated and the others control its partial derivatives. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 In reply to this post by runsun runsun, Perhaps, the following code may help you to understand the relationship between the CPs and the Bezier triangle surface. You don't need to understand all the code. Run it, change the first two or three parameters and examine the results. use  // this should be the previous code defining Tpatches a = 45; // change freely this two parameters b = 30; // this is a z scale degree = 3; // and the polynomial degree up to 6 size = 50;  // of the base triangle // base triangle vertices base_tri = size*[ [1,0], [-1/2,sqrt(3)/2], [-1/2,-sqrt(3)/2] ]; // control points of a zero polynomial bcps =  [ for(i=[degree:-1:0]) [for(j=[0:degree-i]) base_tri*i/degree + base_tri*j/degree +base_tri*(degree-i-j)/degree ] ]; // Z values to be added to bcps zvals = [ for(i=[5:(degree+2)*(degree+1)/2+10]) b*(sin(i*a)+2) ]; // the final control points cps  = [for(i=[0:degree]) [for(j=[0:i]) [bcps[i][j], bcps[i][j], zvals[i+(i-1)*i/2+j] ] ] ]; Tpatch_grid(bcps); color("blue") Tpatch_grid(cps); show_Tpatch(Bezier_Tpatch_mesh(cps, 10),c="red"); color("red") Tpatch_grid(Bezier_Tpatch_mesh(cps, 10),t=0.7); module Tpatch_grid(tp, t=1) {     n = len(tp);     if (n>1) {         for(i=[1:n-1]) polyline(tp[i],t=t);         for(i=[1:n-1]) polyline([for(j=[0:i]) tp[n-j-1][i-j] ],t=t);         for(j=[0:n-2]) polyline([for(i=[j:n-1]) tp[i][j] ],t=t);     } } module polyline(pts, t=1, closed=false) {     if(len(pts)>1 && len(pts)>1 && t>0) {             p  = concat([for(ptsi=pts) project_to_3D(ptsi)],                         closed? [project_to_3D(pts)] : []);             for(i=[0:len(p)-2]) {                 v = p[i+1]-p[i];                 h = norm(v);                 if( h > 1e-12)                     translate(p[i])                         rotate([0, acos(v/h), atan2(v,v)])                             rotate(45) cylinder(h=h, d=t, \$fn=4);             }      } } function project_to_3D(p) =     len(p)>=3? [p, p, p] : len(p)==2 ? [p, p, 0] : [];
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 @ Ronaldo, Wow, this is cool. Thx man. \$ Runsun Pan, PhD \$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); \$ Tips; \$ Snippets
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 Looking at the result shapes, I now understand how the Bezier Triangle Patch manages to go from CPs to poly. I guess it's a method to "generate a new surface", which is different from "smoothing existing surface" that I originally imagined. \$ Runsun Pan, PhD \$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); \$ Tips; \$ Snippets
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 2016-11-23 22:49 GMT-02:00 runsun :     I guess it's a method to "generate a new surface", which is different from     "smoothing existing surface" that I originally imagined. In some sense, Bezier curves and surfaces are a smoothing process of the control points. Look at the following sequence of operations behind a Bezier quadratic: From left to right, the first figure shows the CPs (red marks) of a quadratic arc: it has one corner point. In the second, we cut the corner point out through the median points of the two edges and get 2 new green corners. In the next one, we cut the two new corners by the same process and get 4 new green corners. If we iterate indefinitely this process of cutting corners, we will get a smooth curve (the blue one): a parabola! Note that the median point of each new edge resulting from the corner cut (the blue marks) is a point of the final parabola. The corner cutting method is a smoothing process. It is not what you originally imagined because it is not an interpolation process. However, interpolation methods sometimes produce unexpected oscillations, that is a waving behavior we don't see in the data points. Even natural spline interpolation method is unstable. On the other hand, Bezier and B-spline methods are not interpolations of their CPs but have no more "oscillations" than their CPs. In CADGD, the Bezier and B-spline representations are invaluable when we understand well the relationship between the shapes and their CPs and realize why CPs are called as such.
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 In reply to this post by Ronaldo Thanks Ronaldo, nice example. To cherish stuff like that an image of what the code produces is invaluable: Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 In reply to this post by Ronaldo I have found a family of methods appropriated to build organic shapes. They are called subdivision algorithms and are founded in the subdivision methods usual to Bezier and B-spline curve and surfaces. They may be regarded as a generalization of the corner cutting method I illustrated in my previous message. Imagine you start with a cube. As a first step, we cut out each vertex of the cube by a plane through its incident edges. Twenty four new vertices now substitute the initial twelve and eighth new facets are added. Now, apply the same procedure (vertex cuts) to the resulting polyhedron again and again. The polyhedron facet number will grow exponentially and the polyhedron surface may converge to a smooth surface depending on the chosen cuts. The methods I have found are different from that in the way they cut the vertices but that is the general idea behind them. The methods are very simple and could be well implemented in OpenSCAD if we had more powerful means to build data structures. The iteration steps of the method require that the polyhedron definition be refined. I have started to write a triangulation data structure in OpenSCAD. But it is very hard to do it with just lists and even harder to debug it. Here are some references of papers on the subdivision methods: Interpolating Nets Of Curves By Smooth Subdivision SurfaceInterpolatory sqrt(3)-subdivisionsqrt(3)-subdivisionThe first reference have nice figures showing how promising is the method for organic modelling.
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 @Ronaldo, Thx for the precious references. Btw, I saw you mentioned data structure in several posts. What do you have in mind ? \$ Runsun Pan, PhD \$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); \$ Tips; \$ Snippets
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 In reply to this post by Ronaldo @ronaldo -  don't forget the doo-sabin resmooth operator which is very useful. It can be easily seen in Wings3D under the Bodies menu. Where you can also compare it to the regular smooth algorithm.
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 2016-11-28 20:00 GMT-02:00 Neon22 :@ronaldo -  don't forget the doo-sabin resmooth operator which is very useful. It can be easily seen in Wings3D under the Bodies menu. Where you can also compare it to the regular smooth algorithm.Thank you, Neon22, for the reference. I have found references to Doo-Sabin smoothing method but have not crossed with their paper yet. There are lots of method in this subdivision arena. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 @Ronaldo, what I meant was, what kind of data structure you want ? Can you describe it ? \$ Runsun Pan, PhD \$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); \$ Tips; \$ Snippets
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 2016-11-28 23:03 GMT-02:00 runsun :@Ronaldo, what I meant was, what kind of data structure you want ? Can you describe it ? Any flexible data structure able to store, modify and travel a triangulation or perhaps a more general subdivision of a manifold. I know two data structure used in B-rep and computational geometry: winged-edge and quad-edge. I have already worked with the later. See also Quad-Edge Data Structure and Library. The original paper where it was described ("Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams") is not freely available in the net. But I should warn you it is a lot abstract. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 @Ronaldo, Many thanks. Like all previous references you cited, these are very helpful to me. I'll keep them for future readings. In the mean time, although not familiar with geometry studies in general, I spent quite some time working on how I'd like to use OpenSCAD in geometry, which I believe is more or less on the same path of yours. I'd like to share some of my idea here: 1) hash: This is the basic data structure I use in almost every func/mod:   data = ["a",3,"b",4]   hash( data, "a" ) ==> 3   data2 = update( data, ["b",5, "c",1] ==> ["a",3,"b",5,"c",1]   The core of this hash is extremely simple:   function und(x,df)= x==undef?df:x;   function hash(h,k, notfound)=   (     und( [ for(i=[0:2:len(h)-2])              if( h[i]==k ) h[i+1] ], notfound )   );   It can be set to include action-instructions. One example is posted in this thread previously. Another one, with a function growPts,   pts = growPts( seed, ["x", 3, "y", 4, "z", -5, "transl", [2,3,4] ] )   we can generate a poly from a seed by, literally, "drawing with the code". It's extremely handy when creating a poly.   2) type-checking: this is essential for me to work on geometry, especially checking geometry type (other than the language type-checking like int, str, array, etc) : | 0> gtype(P)= "pt" | 1> gtype([P,Q])= "ln" | 2> gtype([P,Q,R])= "pl" | 3> gtype("a")= undef | 4> gtype([P,Q,R,P])= undef | 5> gtype([[P,Q],1])= "cir" | 6> gtype([2,[P,Q]])= "cir" | 7> gtype([P,1])= "ball" | 8> gtype([0.5,P])= "ball" 3) Other geometry inspections: isSamePt(P,Q) isonline (pt,line ) // is pt on the line ispts(o,dim=3) // are all items in o a point is90( pq1,pq2 ) // are 2 lines 90-deg to each other isOnPlane ( pqr, pt ) // is pt on plane pqr isSameSide ( pts,pqr ) // are all pts on the same side of pqr iscoline ( a,b ) // Chk if pts in a and pts in b are all on the same line. a,b could be either pt or pts isparal ( a,b )  // are a and b parallel. a, b could be line or plane ispl ( x,dim=3 ) // is x a plane ? ispt ( x,dim=3 ) // is x a point ? 4) examples of some core geometry functions: angle( pqr ) // return angle of pqr angleBisectPt( pqr ) // Return a pt that the line pt-Q cut angle(pqr) in half. anglePt( pqr, a=undef, a2=0, len=undef ...) // Create a pt at certain angle/angles in respect to pqr  * left: create pts on 30 and 60 degree on the pqr plane  * middle: create a circle on the pqr plane (varying a with a2=0)  * right: create a circle 90-degree to pqr plane (a=90 with varying a2)   * The combination of a and a2 allows creation of any pt in respect to pqr:  dist(a,b) // distance between a, b, where a,b could be pt, line, plane. intsec( a,b ) // Return the intersection between a,b where a,b could be line or plane movePts(pts,to,from) // Move a poly from any location to any location  * Fig below: Move a poly (yellow) on the [P,Q,R] plane to a [S,T,U] plane (red shape): onlinePt( pq, len, ratio) // Return a pt that is on the line pq with length=len or ratio of pq projPt(a,b,along) // Return the point where a projects on b or b projects on a. where a, b could be: pt, line or plane projPl(pl1,pl2,along,...) // Return projection of pts on plane pl1 onto pl2 along the line "along" These are just part of my lib that makes my journey of OpenSCAD full of joy. As obvious from the above functions, a "[P,Q,R]-based" referencing/coordination system is what I use to drive through the space. I've shown the possibility of moving any poly in any pqr location to any other with the movePts. Although I don't know what exactly the move is formally called, I believe it's some sort of coordination transition. The next step is to allow the moved poly be either squeezed or expanded based on the pqr angle (so the destination is no longer an orthogonal coordinate). That might be one step closer to the organic representation. We'll see. \$ Runsun Pan, PhD \$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); \$ Tips; \$ Snippets
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 I don't know much about the quad-edge structure and whether its an optimisatoin for quad shaped meshes but I am very familiar with the winged edge and it guarantees topological correctness for N sided polygons. (saved format consists of vert lists, edge lists and face lists. Structure is an edge with a left and right faces and CCW and CW edges leading off each of the two edge vertices) The only problem in using these (better IMHO) structures is when loading in a poorly connected error filled non-manifold polygonal object. You can't get a bad model properly stored in the winged edge structure and the tools to auto-fix it have not risen out of the morass yet. So you need to have a way to say if an object is not manifold and the tools need to work on that structure also.
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 You are right, Neon22. Both data structures were conceived so that only manifolds may be built and stored. If we try to represent a cube with a missing face, for instance, we will end up with a manifold that is not what was intended. And may be very hard to identify that. Quad-edges allows to represent general manifold subdivisions. That means the faces may be polygons of n sides, not only quads. The name comes from the four incarnations of each edge: two opposed directions of the edge and their dual. If we don't need the dual graph, it is possible to represent just two incarnations of each edge. I am trying now is to explore implicit representation of the triangulation topology for certain kinds of triangulation that may be used to model furcation junctions. This way I won't need an explicit topology data structure to apply Kobbelt subdivision, for instance. And the quad-edge implementation has been postponed.   The advantage of Kobbelt subdivision over Doo-Sabin, for instance, is that it works for any triangulation and its subdivisions are rather regular triangulation.
Open this post in threaded view
|

## Re: Can you sweep a object with fingers

 After a long struggle computing indices, I have been able to implement Loop's subdivision algorithm for special cases of triangulation. This is my first result, a very rough one. To avoid the implementation and test a general triangulation data structure, I decided to approach this first test with implicit triangulation of a class of triangulations that would be able to model furcations. The green grid in the image shows the specific triangulation used with this model. The triangulation is made of a circular set of Tpatches triangulations (angular sectors). In this model the triangulation has 12 sectors with 9 triangles each. Above the green triangulation you will find the control point grid for the hand upper surface. It has a total of 6*12 + 1 = 73 control points. The lower surface is a reflection of the upper one. The hand was generated by a modified version of Loop's method where I managed to interpolate prescribed border Bezier curves of degree 3: the openings of the furcation and the interstices between "fingers". They total 12 curves defined by the border control points. The surface of the image was generated by 2 iterations of Loop's method and has 16 sub-triangles for each triangle in the triangulation (a total of 1728 triangles). Each iteration of the method multiplies the triangle count by 4: so it grows exponentially. Two iterations required 2 sec. The model has some artifacts. Although it is C2 except in a few points and has the ability to interpolate border curves, I see no way to make the subdivision method to interpolate tangent planes at the border. So the full model with the two surfaces is not even C1 at the joint lines. I have found methods that are able to interpolate even curves along the surface but not tangent planes. Therefore to get a really C1 (C2 almost everywhere) furcation is necessary to build one triangulation for the entire furcation.