@Ronaldo, what I meant was, what kind of data structure you want ? Can you
describe it ?

$  Runsun Pan, PhD $ libs: doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), synwrite ( 2 );   $ tips: Bezier , hash ( 2 ), matrix ( 2 , 3 ), sweep ( 2 , 3 ), var ( 2 ), lerp , animation ( gif , prodVid , animlib ), precision ( 2 ), xl-control , type , rounded polygon , chfont , tailRecur ( 2, 3 ), isosphere ( 2 ), area , vol/center , RGB , CurvedImg , tests ( 2 ), text , triang , unit ; $ Apps: rollApp , blockscad , openjscad , on AWS ( pdf )

--
View this message in context: http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19405.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

@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] ][0], notfound )
);

It can be set to include action-instructions. One example is posted in
this thread  previously
http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19316.html
. 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)
  http://forum.openscad.org/file/n19409/anglePt_basic.png
  http://forum.openscad.org/file/n19409/anglePt_circle.png
  http://forum.openscad.org/file/n19409/anglePt_circle2.png

• The combination of a and a2 allows creation of any pt in respect to pqr:
  http://forum.openscad.org/file/n19409/anglePt_ball4.png
  http://forum.openscad.org/file/n19409/anglePt_ball9.png

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):
  http://forum.openscad.org/file/n19409/movePts.png

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: doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), synwrite ( 2 );   $ tips: Bezier , hash ( 2 ), matrix ( 2 , 3 ), sweep ( 2 , 3 ), var ( 2 ), lerp , animation ( gif , prodVid , animlib ), precision ( 2 ), xl-control , type , rounded polygon , chfont , tailRecur ( 2, 3 ), isosphere ( 2 ), area , vol/center , RGB , CurvedImg , tests ( 2 ), text , triang , unit ; $ Apps: rollApp , blockscad , openjscad , on AWS ( pdf )

--
View this message in context: http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19409.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

Nice approach, runsun. I have being following your work and solutions. But
the data structure I need now are quite more complex.

In your code faces.scad, for instance, you build the face list of
polyhedron, that is, the topological structure of the polyhedron. You
implicitly know the topology, a fixed one (a cube, a rod, a chain), and, for
each one of them, you write the polyhedron face lists. What I need to
implement the subdivision methods I referred before is something more
general. I need a data structure that is able to store any polyhedron but
also it should accept local changes and to be traversed in different ways,
all that in a efficient manner.

The OpenSCAD polyhedron data is not satisfactory. Suppose I need to swap an
edge of a triangulation (that is, switch the diagonal of the quadrilateral
adjacent to an edge). I will have to find (by searching all the face list)
the two faces that are adjacent to the edge. The subdivision refinement
needs to do hundreds or thousands swaps besides vertex insertions. That is
not an efficient data structure.

In the quad-edge structure, the atom element is a directed edge (and its
symmetrical - its inverted direction counterpart). Each directed edge has
two adjacent vertices and two adjacent faces. From each edge, it is possible
to get the following edge with the same left face, the following CCW edge
with the same origin vertex or the symmetrical edge. All those access are
done in constant time. And edge swap is also done in constant time. Well,
not always...

In a C, Pascal or Ruby, the atom element - the directed edge - would be an
object or a record and the connection between edges is done by pointers. So
the swap is done by changing a few (fixed) pointers. But, in OpenSCAD, each
time I do a swap I need to rewrite the whole structure. Therefore, a swap -
and any changing operations - is not a constant time operation anymore. And,
as a consequence, the subdivision method may be O(n3) (where n is the number
of edges in the last refinement). May be worst than that.

I have not enough experience with OpenSCAD to say what would happens in a
step of a subdivision method when we reach thousands of vertices.

--
View this message in context: http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19413.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

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.

--
View this message in context: http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19415.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

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.

--
View this message in context: http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19418.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

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.
http://forum.openscad.org/file/n19501/Hand_furcation.png
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.

--
View this message in context: http://forum.openscad.org/Can-you-sweep-a-object-with-fingers-tp19057p19501.html
Sent from the OpenSCAD mailing list archive at Nabble.com.