[OpenSCAD] Voronoi Generator

[Sislar]

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/

[Ronaldo Persiano]

​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.

[Sislar]

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/

[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/

[Felipe Sanches]

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

Post by 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
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

[Sislar]

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/

[MichaelAtOz]

Post by Sislar
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/

[David Coneff]

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.

Post by Sislar
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
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

[Kenneth Sloan]

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
***@gmail.com
Vision is the art of seeing what is invisible to others.

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.
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
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org <http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org>
_______________________________________________
OpenSCAD mailing list
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

[Sislar]

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/

[MichaelAtOz]

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/