Nabble removed Mailing-list integration from the Forum.
This killed the Forum. This is now an ARCHIVE.
It is likely Nabble will shutdown in the future.
So basically the Forum is now out of date, we are looking into migrating the history.
OpenSCAD support is now provided by the Mailing List.
See the first pinned post here for instructions on subscribing to the mailing list.
Voronoi Generator
Locked
123
123
 
|
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 [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.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. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 <[hidden email]>: Yes I've written one recursive function and this does meet the requirement _______________________________________________ OpenSCAD mailing list [hidden email] 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/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
|
|
In reply to this post by Sislar
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 <[hidden email]> wrote: New here but not new to programming. Been enjoy openscad for a while now and _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
|
|
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 |
|
|
In reply to this post by davidconeff
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.
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
|
|
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 |
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
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, 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. |
|
|
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 |
|
|
Here's the start of a Delaunay triangulator that operates in userland.
delaunay2d.scad <http://forum.openscad.org/file/t2140/delaunay2d.scad> -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
|
|
I'm not sure these are particularly legible, but that's what you get for
using OpenSCAD. delaunay2d.scad <http://forum.openscad.org/file/t2140/delaunay2d.scad> This needs some work to dedup and deal with degeneracies. delaunay3d.scad <http://forum.openscad.org/file/t2140/delaunay3d.scad> -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
|
Administrator
|
I haven't digested it yet, but I just came across this:
https://doc.cgal.org/4.8/Manual/packages.html#PartVoronoiDiagrams ----- 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! -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, 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. |
|
|
In reply to this post by NateTG
delaunay2d.scad works well in many cases but produces an obviously wrong result (one missing edge and one missing face) e.g. for theses points:
points = [[7.38276, -12.8839], [2.89678, -16.8555], [12.3433, -13.6067], [7.62988, -18.7426], [0.799678, -21.9285], [13.0129, -18.8988], [6.12022, -23.6863], [12.0965, -23.8574]]; Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
|
|
In reply to this post by Sislar
I made another algorithm for a voronoi generator. It works, but don't be in a hurry, because it's slow, very slow (tips for speeding it up appreciated).
module voronoi($maxx=1000,$my=1000,$numpoints=10,fn,gaps=1,$quick=true){ $pointsx=rands(0,$maxx,$numpoints); $pointsy=rands(0,$maxy,$numpoints); module cone(ix,fn){ projection() difference(){ translate([$pointsx[ix],$pointsy[ix],0]) cylinder(d1=$maxx*2,d2=0.01,h=1000,$fn=fn); union(){ for(n=[0:$numpoints-1]){ if(n!=ix){ if((abs($pointsx[ix]-$pointsx[n])<$maxx/($numpoints/40))||!$quick){ if((abs($pointsy[ix]-$pointsy[n])<$maxy/($numpoints/40))||!$quick){ translate([$pointsx[n],$pointsy[n],0]) cylinder(d1=$maxx*2,d2=0.01,h=1000,$fn=fn); } } } } } } } intersection(){ square($maxx,$maxy); for(n=[0:$numpoints-1]){ offset(-gaps/2) cone(n,fn); } } } //Try it with a low numpoints and fn (it'll be a little odd with low fn, but close enough for testing) first. //quick=true means that it won't look for intersections with far-away points. Usually, it works, but occasionally, it might cause errors. //Gaps are the width of the gaps between the polygons. //maxx & maxy are the dimensions of the generated area. //Commented out so that it won't render on load, it's slow... //voronoi($maxx=2000,$maxy=2000,$numpoints=100,fn=5,gaps=10,$quick=false); It is slow, though, even with fairly modest settings, we are talking minutes. Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
|
|
I don't think that using CGAL to do calculations using geometry by intersecting coneis going to be particularly efficient. The traditional sweep line approach is likely to be much faster, even if it is a chore to implement in OpenSCAD. I think there's a geometric way to get a Delaunay triangulation by mapping [x,y] to [x,y,x^2+y^2] and then taking the convex Hull. That's likely to to be much faster, but I don't think you can extract the dual in any way. Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
|
|
I agree, this is not the efficient way, but it's a simple way (especially in OpenSCAD). Sometimes, efficiency in terms of developer time takes precedence over efficiency in terms of execution time. I also like that it's an algorithm that's easy to understand, which is good for teaching/learning. Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
«
Return to OpenSCAD
|
1 view|%1 views
| Free forum by Nabble | Edit this page |