Hello,
Here, a little script to compute Delaunay triangulation in 2.5D (suitable for terrain modelling) and Voronoi tessellation in 2D (neighborhood clustering).
It’s pure Python code, works fine with Blender 2.63
EDIT
This script is now host on GiHub as a part of BlenderGIS toolset.
Have just wrote simple Lisp code for exporting selected points from AutoCad to OBJ, that Blender reads correctly.
Great Thank you for Delaunay!
It is AWESOME!!!
Works just fine on 2.64 RC1 =)
It should br in a trunk, alongside with Nicholas Bishop’s Convex hull operator!
May I ask you to apply some improvements on your priceless code?
Could you set limit to vertex quantity, to stop script working if it is higher than some amount, or split object to parts by 20 000 verts? Blender crashes if it selected object has got more than about 50 000 verts =)
Another issue - automatic applying location/rotation/scale on selected. Simply result suddenly appears somewhere other place, and I just forget to reset this every time I use it =)
Also, could you set to created surfaces backfacing = false by default, because of Nvidia Ogl display problem? =)
And, surely, what about reverse conversion to points? Is it possible? Please^^
First, sorry for my bad english, maybe I’m hard to understand.
Thank you for your feedback, I’m glad that this script is useful.
I changed the script to take into consideration the transformation if it not applied.
Are you sure Blender crashes or it just freezes? I can triangulate 155 000 points in 50 seconds without crash on a common machine (xp, 2Go RAM).
For back faces, it seems to me that Blender doesn’t have double sided faces, I’m wrong? I didn’t find any backfacing options in Blender Python API.
Reverse conversion ? Just edit the TIN to delete edges and faces and you get the points cloud, no?
If you work with Autocad I have an interface to use this code directly in ACAD. It’s another python code who deal with COM objects of AutoCad. Let me know if you’re interested.
whow this lisp code is awesome, my Python hack with COM objects is much more slow and all others similar lisp I tried before was bad, thx you for the link !
Your obj exporter will be very good alternative to Blender dxf importer ! Congrats …!
Ive attached my exporter at the first post of my tread. Try it, leave comments, if it were useful to you =)
This add-on is absolutely brilliant, I can’t tell you how useful it has been to me. I think you should try and have this added to the main trunk, being able to skin massive clouds so efficiently, easily and flawlessly is the kind of feature blender could use out of the box and will give us a whole new user base of people using lidar, radar and all sort of point cloud generating data techiniques! This is really very exciting!
Great addon, thanks a lot!
I have a problem, though. I’m using the VoronoiButton, not the TriangulateButton. I’ve tried to change some settings in the script to have it generate the faces of the voronoi diagram. I changed the script in 3 places:
Everything seems to work as expected; the faces show up in the object properties at the top of the screen. But when I tab to go into edit mode, blender hangs. I’m using blender 2.68a on win7-64bit.
Anyone else experiencing this? Am I missing something?
Cheers,
g
Hi,
I found the problem, the python list that contains polygons coords is “closed”, that means the last point in the list is the same of the first point and it’s not what from_pydata function expects.
You can quickly fix this by excluding the last point in list. For example in file DelaunayVoronoi.py change line 948 by polygonsIdx[inPtsIdx]=[valuesIdxDict[pt] for pt in poly[:-1]]
I think i’ll publish an update with a more consistent fix later.
[EDIT] ok I’ve updated first post with new version, now voronoi tool have an option to generate edges or faces
Fantastic, the updated code works like a charm!
Would it be possible/difficult to add a margin between the voronoi cells?
Because that would really be the icing on the cake for me.
Anyway, thanks again for your swift action and response!
shrinkFaces.zip (2.06 KB)
I’m sure this has already been done, but I wrote a script that shrinks an objects faces by offsetting its edges by a given amount (see also my previous post). I’ve attached my code (I hope).
To use: select one or more meshes and call the function ShrinkFaces(edgeOffset = 0.005, separate = False). You can specify the edge offset and whether or not you want to separate the resulting faces (as these will usually be disconnected).
Please note that the operation may take a while to complete (about 45 seconds for 1000 faces in my case). Also note that the edge offset is treated ‘as it is’, so if you make it too big, you’ll probably end up with some very-badly-defined geometry. And finally, this script can obviously be used on any mesh; it doesn’t have to be a voronoi diagram.
Wow, thanks, domlysz, your workflow is about 1000 times faster (first guess). I did come across that thread/addon while looking for an existing solution to this question, but it didn’t quite occur to me that I could apply this to my situation by simply splitting the edges of the mesh. Thumbs up to Bon Baba, too, of course.
I still have a lot to learn, apparently. Nevertheless, it was a nice exercise…
Hi again,
I’ve been playing around with this script and it works great. Unfortunately, I need diagrams on point sets of about 50.000 vertices. This takes a really long time to generate. That’s understandable, I guess, because the algorithms complexity is probably of the order n², n being the number of vertices – each vertex needs to check its environment, ie all other vertices. If i use 1000 vertices, it completes in a fraction of a second. I’ve tried using 35.000 vertices and had to stop it after about 3 hours.
So my question is this: would there be any (reasonably feasible) way to speed this up? In my case, the vertices’ distribution is quite stretched out in one direction, so let’s say the bounding box/plane would be something like 300 m by 20 m. Maybe this a priori knowledge could be used to speed up the operation, eg by limiting the number of neighbours any given vertex needs to check? Maybe preprocess the vertices and throw them in some bins along the prevalent/longest dimension?
Just thinking out loud.
Any suggestions appreciated!
g
Hi,
That’s strange, I can compute 100 000 verts in less than 30 seconds on a basic machine (OS 32 bits - 2Go RAM - 2.4GHz). What’s your config ?
Oops, apparently something went wrong the previous (and only) time I tried it with a large number of vertices. Blender just hanged (for some unknown reason) after I pushed the diagram button, while I assumed it was calculating my diagram.
I tried again just now, and got a diagram (with faces) of 100.000 vertices in about 20 seconds. Which is quite impressive, really. I’m on 64bit-win7, core-i7 @ 3.2 GHz with 16 Gb of RAM.
So I seem to have wasted your time; sorry about that.
I’m a very happy bunny, right now, though! 
g
Hi Doomlysz,
Thanks a lot for your script, it’s surprisingly fast !
Just a note, it doesn’t seem to scale linearly. Triangultaing 33000 points took 5sec on my PC (not much longer than Rhino with Grasshoper), while 66000 took 35sec (same mesh, just decimated). Maybe doing some kind of automatic chunk creation (tile the mesh in 40 000 points chunks for example) and rejoining them after, would speed up things and also reduce memory usage ?
Anyway, thanks a lot for sharing that
Thank you for 1.3! =)
Very poweful and useful!
@domlysz thanks that was really useful, I’m not doing a heavy use of it but it did great !
Does it work in 2.74?
BlenderGIS-master.zip (47kb) When I try to install this zip in addon panel it doesn’t appear there at all, like it has some errors or something
