New here but not new to programming. Been enjoy openscad for a while now and made a few things But I'm stumped so far trying to make a voronoi pattern. Been looking into it for a few weeks and I think i have found a the algorithms but they are fairly complex. Would it be possible to write this in openscad script or would it need to be a new feature/primitive in Openscad? What i was thinking was the function or primitive would be for 2d at least to start applying it to an arbitrary surface... well I'm not that advanced yet. voronoi( B= bounding polygon, P = set of points, r = Rounding, t = thickness) First step is to convert the set of points to a set of non overlapping triangles via https://en.wikipedia.org/wiki/Delaunay_triangulation Now the math there is pretty daunting but fortunately someone wrote a paper on someone simple implementation. the following link has about 20 lines of pseudo code. https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm For Each Point in P find all the triangles from step one that have this point as one of the vertices. Then you find the circumcenter of each triangle. (This is fairly easy and I have openscad script for this) for this point and the poloygon of these points is the voronoi area. from there is easy, you can just offset (-r) and minoski with the rounding parameter. The way variable are handle I'm not sure if I can do all the math (I have a ton of C experience), I don't think I've fully adjusted to how openscad doesn't have true variables yet. -- Sent from: http://forum.openscad.org/

​I have tried once to code a Delaunay triangulation method in OpenSCAD. The methods I know require​ that an initial Delaunay triangulation data structure be modified iteractively. The only data structure we have in OpenSCAD is list. List may be used to represent records but we don't have pointers like in C to promote local small changes. Besides, variables in OpenSCAD are not really variables so any change to a data structure requires that a entirely new data structure be built instead. So, a method that is O(n log n) will have an OpenSCAD implementation of O(n3) or even worst than that. And you will have to code it just with functions.

Yes I realize all that, If you look at the second link the way it works interactively is not that complicated, its 3 or 4 tests and adding/subtracting from a couple of lists and dividing triangles. But the lack of real variables makes it a mess. This is why I think its probably needs to be coded as a new primitive in openscad itself. I posted in GitHub and was directed to post here first. I know this is more of an artistic need than an engineering one, which is openscad's focus but there are some engineering uses. I think this would be a very powerful primitive like minkowski function. I still struggle with openscad functions. I get it but I have to really look at the code and figure out how to format and structure it, my brain doesn't quite work that way though in some ways they are very similar to C #defines. -- Sent from: http://forum.openscad.org/

A bigger challenge than the functional aspect of programming in OpenSCAD is that you don't get access to geometry that's been generated by the engine in a good way. Besides that, OpenSCAD is Turing complete, so implementation is technically possible, though stuff like this typically ends up involving lots of recursion. -- Sent from: http://forum.openscad.org/

Yes I've written one recursive function and this does meet the requirement that everything is know before hand so no reason it can't be done. Its just a beast. If anyone wants to lend a hand let me know. I'm only going to try to make one inside a rectangular boundary. Without access to internal structures i don't see how you could warp it to curved surfaces. -- Sent from: http://forum.openscad.org/

I implemented this several years ago. Let me know if that looks good for you :-) https://www.thingiverse.com/thing:47649 https://github.com/felipesanches/OpenSCAD_Voronoi_Generator 2018-07-20 19:10 GMT+00:00 Sislar <donp66@gmail.com>: > Yes I've written one recursive function and this does meet the requirement > that everything is know before hand so no reason it can't be done. Its > just > a beast. > > If anyone wants to lend a hand let me know. I'm only going to try to make > one inside a rectangular boundary. Without access to internal structures i > don't see how you could warp it to curved surfaces. > > > > -- > Sent from: http://forum.openscad.org/ > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

Yes I saw you code before i posted but it looks like just an approximation. I'm not sure the math you are using but it seems you have a function to get a distance. they you Minkowsky a square and a circle to that distance. the result looks ok but not prefect. and I don't see how this really is a voronoi calculation. -- Sent from: http://forum.openscad.org/

For this type of model generation you may want to use Solidpython which will give you access to normal variables, data structures etc. and generate a model that can be interpreted and viewed by OpenSCAD without creating the exponentially higher computation costs of an OpenSCAD-only implementation. On Fri, Jul 20, 2018, 07:10 Sislar <donp66@gmail.com> wrote: > New here but not new to programming. Been enjoy openscad for a while now > and > made a few things But I'm stumped so far trying to make a voronoi pattern. > Been looking into it for a few weeks and I think i have found a the > algorithms but they are fairly complex. Would it be possible to write this > in openscad script or would it need to be a new feature/primitive in > Openscad? > > What i was thinking was the function or primitive would be for 2d at least > to start applying it to > an arbitrary surface... well I'm not that advanced yet. > voronoi( B= bounding polygon, P = set of points, r = Rounding, t = > thickness) > > First step is to convert the set of points to a set of non overlapping > triangles via > https://en.wikipedia.org/wiki/Delaunay_triangulation > Now the math there is pretty daunting but fortunately someone wrote a paper > on someone simple implementation. the following link has about 20 lines of > pseudo code. > https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm > > For Each Point in P find all the triangles from step one that have this > point as one of the vertices. > > Then you find the circumcenter of each triangle. (This is fairly easy and I > have openscad script for this) for this point and the poloygon of these > points is the voronoi area. > > from there is easy, you can just offset (-r) and minoski with the rounding > parameter. > > The way variable are handle I'm not sure if I can do all the math (I have a > ton of C experience), I don't think I've fully adjusted to how openscad > doesn't have true variables yet. > > > > > > > -- > Sent from: http://forum.openscad.org/ > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

> ... If anyone wants to lend a hand let me know. ... Do you have some sense of what kind of help you're looking for? I'm not sure there's an obvious division of labor here. -- Sent from: http://forum.openscad.org/

I have written many Delaunay Triangulation/Voronoi Diagram programs, in many programming languages. In my opinion, OpenSCAD is probably NOT the appropriate language for this. Theoretically, of course, it is possible. But, beware of numerical instability. The best place to start is probably the O(N^4) algorithm given by O'Rourke. It gives the wrong answer in pathological cases - but this can be fixed. I recommend *against* the "edge-flipping" method mentioned by the OP. I spent months ferreting out the numerical issues - but that was in the early '80s BEFORE the theoretical result relating the Delaunay Triangulation in 3D with the Convex Hull in 3D. That's the method I use routinely, now. But...that code is fairly large, and it's not written in OpenSCAD. The current version is written in Java. If this is of interest to you, contact me off-list. Trust me - it will *not* help you implement this in OpenSCAD! My recommendation is to work out a workflow where you can generate the points you want (somehow) - compute the Voronoi Diagram (using something *other than* OpenSCAD) - and then importing something suitable for further OpenSCAD processing. That's if you want to do it on the 2D plane. If you want to try to produce a similar result on a curved 2D surface embedded in 3D, then all bets are off. I'm not particularly up on this, but I would not be surprised if there were significant dificulties in even DEFINING the Voronoi Diagram on an arbitrary curved surface. And, lifting to 3D (to take advantage of the duality with the convex hull) becomes problematic. This would require more than simple coding - I suspect there is serious theoretical work to do first. When GRUs first appeared, there was a rash of "geometric" algorithms (including DT/VD) introduced to take advantage of them. The primary difficulty with these is they don't *really* compute the Voronoi Diagram - but rather a close approximation. In some applications, that may be adequate - but be careful about definitions when reading papers. Finally - back to my suggestion to start with the O(N^4) algorithm. Consider *how many* points you need to process. If it's small enough, the theoretically slow algorithm may be adequate. The advantage is that the algorithm is simple to implement, numerically stable, and easy to understand. I haven't tried it, but it *might* be suitable for OpenSCAD implementation. No matter what language you are using, I strongly recommend that you start with simple, but perhaps slow, algorithms, first. If nothing else, they provide a check on the answers you get from more complex algorithms (on small examples, of course). If you can get O'Rourke's O(N^4) method working in OpenSCAD, you may well decide that you have better things to do than to try to implement edge-flipping, or even the 3D Convex Hull methods. -- Kenneth Sloan KennethRSloan@gmail.com Vision is the art of seeing what is invisible to others. > On 21 Jul 2018, at 08:09 , David Coneff <david.coneff@gmail.com> wrote: > > For this type of model generation you may want to use Solidpython which will give you access to normal variables, data structures etc. and generate a model that can be interpreted and viewed by OpenSCAD without creating the exponentially higher computation costs of an OpenSCAD-only implementation. > > On Fri, Jul 20, 2018, 07:10 Sislar <donp66@gmail.com <mailto:donp66@gmail.com>> wrote: > New here but not new to programming. Been enjoy openscad for a while now and > made a few things But I'm stumped so far trying to make a voronoi pattern. > Been looking into it for a few weeks and I think i have found a the > algorithms but they are fairly complex. Would it be possible to write this > in openscad script or would it need to be a new feature/primitive in > Openscad? > > What i was thinking was the function or primitive would be for 2d at least > to start applying it to > an arbitrary surface... well I'm not that advanced yet. > voronoi( B= bounding polygon, P = set of points, r = Rounding, t = > thickness) > > First step is to convert the set of points to a set of non overlapping > triangles via > https://en.wikipedia.org/wiki/Delaunay_triangulation <https://en.wikipedia.org/wiki/Delaunay_triangulation> > Now the math there is pretty daunting but fortunately someone wrote a paper > on someone simple implementation. the following link has about 20 lines of > pseudo code. > https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm <https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm> > > For Each Point in P find all the triangles from step one that have this > point as one of the vertices. > > Then you find the circumcenter of each triangle. (This is fairly easy and I > have openscad script for this) for this point and the poloygon of these > points is the voronoi area. > > from there is easy, you can just offset (-r) and minoski with the rounding > parameter. > > The way variable are handle I'm not sure if I can do all the math (I have a > ton of C experience), I don't think I've fully adjusted to how openscad > doesn't have true variables yet. > > > > > > > -- > Sent from: http://forum.openscad.org/ <http://forum.openscad.org/> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org <mailto:Discuss@lists.openscad.org> > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org <http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org> > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org