# Voronoi Generator

16 messages
Open this post in threaded view
|

## Voronoi Generator

 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_triangulationNow 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_algorithmFor 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 [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

 ​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. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

 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/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

 In reply to this post by Sislar 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/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

 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 [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

 I implemented this several years ago. Let me know if that looks good for you :-)https://www.thingiverse.com/thing:47649https://github.com/felipesanches/OpenSCAD_Voronoi_Generator2018-07-20 19:10 GMT+00:00 Sislar :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 [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
Open this post in threaded view
|

## Re: Voronoi Generator

 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/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

Open this post in threaded view
|

## Re: Voronoi Generator

 In reply to this post by Sislar > ... 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/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

Open this post in threaded view
|

## Re: Voronoi Generator

 Thanks Kenneth, What algorithm did you use to do the triangulation?  I haven't looked at O'Rourke why do you suggest it? the Bowyer-Watson doesn't look too bad and its O(N Log N). I agree its quite daunting given the limitations of openscad. That is why I think it would be better as a built in function.  What would be the process to do that.  I assume some forum (this one?) or is there a developers forum. I posted to where I thought it should go and was directed here.  If you have the code in C/Java i would think it shouldn't be that difficult to implement inside Openscad. More likely the time consuming part would be debating what are the right parameters interface. For instance I think it would be best if the function returned an array of polygons but I don't think there is any openscad function like that. So if its drawing the polygons then you need to build in some of the things that will make it useful visually such as offset(-1) all the polygons to get edges, and they do you want to do some rounding etc. Someone asked about a division of work,  if it was C then it would be easy to divide the work. The other way is to just have the code on GitHub and two or more people can modify it as long as they talk frequently. I have functions for point in circumcircle. I need one to find a triangle that bounds a given set of point. function to divide a triangle into three triangles given a point in the triangle (ok this is pretty trival) I'm having trouble with the overall structure and recursion.  so One person to write a skeleton of the code and others to fill in specific functions. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Voronoi Generator

 Administrator In reply to this post by Sislar Sislar wrote > 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. Perhaps you should have another look. It uses intersection_for() to creatively make the cells. While it doesn't calculate vectors as such, it is an accurate voronoi. Set round=0.1 to see it better (round=0 gets an error) ----- Admin - PM me if you need anything, or if I've done something stupid... Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above. The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out! -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org Admin - email* me if you need anything, or if I've done something stupid... * click on my MichaelAtOz label, there is a link to email me. Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above. The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
Open this post in threaded view
|

## Re: Voronoi Generator

 In reply to this post by Sislar Implementing incrementally updating data structures in OpenSCAD is a chore. Try implementing a 2-3 tree if you want to see what it's like. You could just do the 'dumb' O(N^5) Delaunay algorithm.... something like: function triangulatepoints (points) =    [       for (i=[0:len(points)-4]) for(j=[i:len(points)-3]) for(k=[j:len(points)-2]) for(l=[l:len(points)-1])           if(circlecheck([i,j,k,l],points)) [i,j,k,l]    ] ; Circlecheck returns false if any of there are any points inside the 'circumsphere' of points i,j,k,l, and true otherwise. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|