[Plugin] QHull

[craigbic]

YES!!!! I have been really.....really....REALLY needing this lately! I can't wait to try this as soon as I am done writing this reply. I'll let you know how it goes.

Can someone enlighten me, please? What it the purpose of having such a random geometry?

Tomasz,

I wouldn't call it "random geometry" as the "randomness" would depend on the point cloud used as the basis for the Voronoi diagram but rather call it "mathematically generated geometry". 3D Voronoi structures (2D Voronoi diagrams aside) are used in cellular-level research, bone fatigue studies, and experimental cellular architecture.

[craigbic]

Well, there are a few snags but I am still VERY pleased with this large chunk of progress. Kudus, avariant! This is a major step forward in the Qhull/Voronoi plugin development.

Has ANYBODY been able to get the "selection" versions of Voronoi, convex, Delaunay, or half working at all? I have been unable to do so under any circumstance regardless of point cloud size or attitude in SU6. I use SU6 at work and SU7 at home so I haven't tried it in SU7 yet. I generated lsystem point clouds of various sizes and was totally unable to get them to work. Then I tried various hand-made point clouds, ones generated from sandbox meshes, and even point clouds generated from 2D Voronoi diagrams and all did not work (see error message pic).

On the positive side, all of the operations based on points generated by rbox work just fine and it is really nice to have them working within SU! I guess for now, to generate 3D Voronoi geometry from my own points, I'll have to follow my own procedure as outlined in this post

I feel like we're almost there and it will only take a slight nudge to get this totally working.....I am still quite excited about this.

[Pilou]

Has ANYBODY been able to get the "selection" versions of Voronoi, convex, Delaunay, or half working at all?

In fact yes
You must make a group before launch the Qhull plug
Half works also but result is like 1*1*1 pixel at the origin so you must rescale the result

For your points I don't know yet but I suppose if you make a group maybe that works too

[avariant]

OOOhhhhh.... oversight on my part!

When examining the standard SU 'model', there usually aren't construction points. Everything is edges and faces. So, I just search for all the edges and use the starting vertex for each edge (to avoid duplicate points, I don't use the end). It never occurred to me to also search for construction points, but I can see how that would be useful!

To see how the selection part works now, create a random convex shape. Then select the component, and do voronoi on selection. There you will see how it works. In the meantime, I'll update it to capture construction points also.

As far as purpose.... well... it's artistic, right?
Actually, convex hull can have a legitimate purpose. If you have a complex model, do a convex hull selection on it, you'll get a sort of 'shrink wrap' shell of the entire model. I'm sure the others have legitimate purposes too.

[avariant]

Fixed for using Construction Points.

[watkins]

A tutorial or two to demonstrate how to use this plugin would be nice.

Regards,
Bob

[craigbic]

YES...YES.....YES!!!!! Everyhing is working now! Thank you especially for the update for use with construction points. I tried every variant I could think of, lsystem point clouds, sandbox mesh grids, convex geometry groups....it all worked.....flawlessly! It took awhile but as I told other members in other related posts.....somebody in this terrific community forum will come in and save the day!

Thank you avariant!!!

[avariant]

My pleasure. It was fun, and I've always been a fan of the 3D Voronoi shapes.

[MALAISE]

MALAISE

[halroach]

I haven't been able to generate any shapes with selected shapes, or with selected construction points, if in a group/components/outside a group/component. I get the following errors:
"qhull generated empty results"
"qhull failed to generate valid results"

ideas?

[avariant]

If your points are all on the same plane, then you won't get any results.

To ensure it works at all:
1.Create new, empty scene.
2. Plugins->Qhull->Convex->Medium
3. A convex shape should be created. Select it.
4. Plugins->Qhull->Voronoi->Selection(Free)
5. A spiky shape should be created.

If all that works, then the problems is your input data (ie model / points).

[Pilou]

So is that normal?
Always take a convex volume for any function

[avariant]

I honestly don't know the math, but A LOT of regular shapes, like cubes, planes, etc, don't generate valid voronoi results. They may still generate results from the other options, and will often work if you choose Selection (Sphere) or Selection (Box). I don't know why... math, right?

[Pilou]

No problem ! Thats fun
(click image for erase scroll bar)

kul.jpg

[22curious]

Avariant - Thank's for your Qhull.rb - it could be a crucial piece of the puzzle I'm trying to solve, except I can't get it to function with my own (grouped) convex form.

If your points are all on the same plane, then you won't get any results.

To ensure it works at all:
1.Create new, empty scene.
2. Plugins->Qhull->Convex->Medium
3. A convex shape should be created. Select it.
4. Plugins->Qhull->Voronoi->Selection(Free)
5. A spiky shape should be created.

If all that works, then the problems is your input data (ie model / points).

Also, if I follow your test instructions, Steps # 1-3 work, but using 4. Plugins->Qhull->Voronoi->Selection(Free) {or any of the other selection options for step 4) yields no results. Using one of the non-selection size options (small through huge) as Step 4 yields the anticipated spiky shape.

I'm having the same trouble as Halroach (did you ever find the solution why?)

Re: [Plugin] QHull

Postby Halroach on Tue May 19, 2009 8:07 am
I haven't been able to generate any shapes with selected shapes, or with selected construction points, if in a group/components/outside a group/component. I get the following errors:
"qhull generated empty results"
"qhull failed to generate valid results"

Please help me find a path to generate voronoi shapes from convex polygons generated and selected by me (not by Convex).

Thanks!

[halroach]

I'm having the same trouble as Halroach (did you ever find the solution why?)

I haven't found a solution yet...

[avariant]

Can you post a small example scene?

Very "regular" results, like a cube, a sphere, all geometry in a single plane, usually won't generate valid results. It's just how the mathematics work.

[ikun]

Hello!!

Thank you for the plugin!

It s AMAZING!

But I have the same problem as Halroach.....

... I select the group, (the convex medium), then I run voronoi Selection (Free), and suddenly, sketch up window is minimized, and appears the two error messages ...:

Qhull failed to generate valid results,

Qhull generated empty results
....

Thank yoouuu!!

[22curious]

Avariant & Halroach - thanks for the prompt responses - sorry for my delay. Drowning in plugin options, looking for solutions.

Here are examples of a few of my attempts to get Qhull to work with construction points, …because isn't the 'convex' script supposed to form the skin over specific construction points?

Stall from Qhull>convex>selection, using group created by Lsystem, pointified, and grouped:

Same result from Qhull>convex>selection, removing the lines from group created by Lsystem, leaving just the grouped construction points (even though the lines are supposed to be ignored):

Attempt to compare the object formed by selecting the point-cloud group above, Qhull>convex> Large(100), which created an apparently random small convex polygon at the origin. I scaled up the polygon (evenly), made the faces transparent, and superimposed it on the point cloud to explore whether there was any apparent relationship between the polygon created and the group of selected points. It seems there is none…?

Attempt to form a convex hull around irregular polygons Qhull>convex>selection. Tried it grouped (shown). Same failure message, with an apparently random small convex polygon at the origin. This one seems to have no relationship to the objects to be 'hulled' either:

Tried the same thing ungrouped , same (unrelated) result:

Tried using Qhull>convex>selection on the selected points (after pointifying the objects above, then exporting the points), creates an object, but there's still no apparent relationship to the points:

Stall (sort of) from Qhull>voronoi>selection, using group created by Lsystem, pointified, and grouped. Got same failure message, but the Qhull>voronoi>selection did put a spiky object at the origin:

from Qhull>delaunay>selection, using same group. Got same message, but if did put a spiky object at the origin:

Result from Qhull>half>selection, using same subgroup.
Again got same message (Qhull failed to generate valid results), but there IS a very small, apparently random spiky object at the origin:

I need to be able to manipulate surfaces formed from imported CSV points …not random objects.

I'm looking for Qhull's convex.rb to generate specific convex hull surfaces, for voronoi to crack them ...as voronoi is supposed to do. The random spiky objects are fun, beautiful, and maybe even useful - but random. And are the anticipated 'cracks' reversed, forming the spikes?

NOTE: I appreciate that some of the transformations I need can be handled by some of these awesome scripts:

__Didier's points_cloud_triangulation.rb (finally got it to work after spending LOTS of time tracking down the required fix to the delauney.rb file, removing the './').

___Finally got ArchitectBoy's skin.rb to work when I found Christian_dl's skin-26 version… as long as I use the icons, (though it does not function through Tools> skin.rb ...?). So this creates a convex hull around faces & other polygons…but I haven't found a way to implement that script using points, or to follow with voronoi.

___ Kirill2008's Pnts2mesh.rb is also very useful - (but can we get it to work with voronoi?)

__ Chris Fullmer's clf_simple_loft.rb is great for regular lines and surfaces

BUT…has anyone gotten voronoi to act on (crack) surfaces created in these alternate ways?

Many thanks. 22curious

[22curious]

Avariant and anyone using Qhull: Will you please post examples of:

- Results from successful use of Qhull with selected construction points (esp. voronoi)?
- voronoi results that show a 'cracked' surface?

Here are links to interactive voronoi examples:
- 2D applet http://www.cs.unc.edu/~snoeyink/demos/crust/home.html
- 3D http://www.youtube.com/watch?v=yVr4-Dogz5g

Thanks for your feedback!

[avariant]

I've tested the construction points grouped and it works just fine. I think your problem is that your points are too regular or all on one plane. I don't know why that causes a failure, it just does.

However, as far as creating what you call 'cracked' surface, the basic answer is that's not how voronoi is being represented here. Voronoi is a mathematical representation in which each barrier is equidistant from its nearest points, giving the telltale cobblestone appearance. What you are missing, however, is that along the boundaries of your sample area the cells are undefined. In all the images you see, the cells are just clipped off in a nice rectangular boundary. A similar method could be done in 3D (like the youtube video), but in this case, it's not. I'm not 100% on the math here, to be honest, but what I think is happening is the cell boundaries are being evaluated out until they "close" naturally, resulting often in long spikes. If you delete those spikes on a simple example, you will see that the cell boundaries do, in fact, lay equidistant between nearest neighbors.

The problem, I think, is that you are expecting it to look like a 2d cobblestone image, but the 3D representation just doesn't work that way without the artificial boundaries.

[avariant]

Here is a very simple collection of points from which I generated a convex hull, delauney (which appears to connect nearest neighbors), and voronoi. They all worked.

Just to clarify in your above examples, you say you used Convex->Large(100) and it didn't match your selection. As clearly stated, Large(100) creates 100 random points, and has no correlation what so ever to your selection. Only the choices with "Selection" in them use the selected items in any way.

Also, if Qhull (the 3rd party exe) fails, the script might use old data to generate the shape, which is why, despite the message, you may see a shape created.

[22curious]

Avariant - thank you for taking the time to reply and for providing examples using your own selection to help troubleshoot both my operation and perception of the Qhull tool.

First, to clarify our examples:

Your "...very simple collection of points from which I generated a convex hull, delauney (which appears to connect nearest neighbors), and voronoi…all worked."

Your convex hull and delaunay examples (Avariant, 01Oct09)clearly worked. I remain confused by exclusion of some of the shown points from the voronoi shape.

?** Did you use Qhull>> voronoi >selection(free) or ..>selection(Bounding Box)?
?** Do results for your examples differ when you opt for selection(boundingBox) or selection(sphere) or selection(free) ?
?** Why are some of the shown points outside the voronoi shape?
?** Are all shown points = selected construction points?
?** Perhaps some of these unenclosed points are negative vertices added by selection of certain options in Qhull?

"... what I think is happening is the cell boundaries are being evaluated out until they "close" naturally, resulting often in long spikes. If you delete those spikes on a simple example, you will see that the cell boundaries do, in fact, lay equidistant between nearest neighbors."

It does seem that the voronoi spikes are extending to 3D vanishing points. In my selection examples, I chose selection(bounding box)…so I didn't expect unbounded regions.

?** Perhaps the ruby script could control bounding box options?

?** Are these 'natural' vanishing points established from the geometry of the selected points?

Qhull may be adding (infinity?)vertices for unbounded regions.
?** The long spikes may relate to 'infinity' vertices' added by Qhull - perhaps that option can be controlled in the ruby?

"…in your(22curious) examples, you say you used Convex->Large(100) and it didn't match your selection. "

Only the third (22curious) example used Convex>Large(100), to compare to the other examples using my C points and the Selection(Bounding Box)option.

"Also, if Qhull (the 3rd party exe) fails, the script might use old data to generate the shape, which is why, despite the message, you may see a shape created."

Spot on. The same shape IS repeatedly being created. Now to figure out why, and how to reliably refresh the data.

" ...I think your problem is that your points are too regular or all on one plane. I don't know why that causes a failure, it just does."

The points generated from Lsystem were irregular and not coplanar. …I moved and erased some of the polygon vertices in the later examples in an attempt to avoid the known complications related to coplanar points…do you think having a subsets of coplanar points in a larger set of irregular points (like in the later 22curious examples) would cause problems?

"What you are missing, however, is that along the boundaries of your sample area the cells are undefined. In all the images you see, the cells are just clipped off in a nice rectangular boundary. A similar method could be done in 3D (like the youtube video), but in this case, it's not."

Well…I had hoped that choosing the 'selection (bounding box)' option would establish nice rectangular boundaries around the point cloud, (and similarly, nice spherical boundaries with selection(sphere)).

?** Do you think such bounding and clipping can be done with a modified ruby script (or would it require change to the Qhull core files)?

?** I'd welcome any suggestions/snippets for establishing artificial boundaries ?

My perspective lack of success with the Qhull plugin is mostly based on my failure: to refresh the construction points array for the Voronoi shapes; to bind the unbounded points; and to understand excluded 'negative' points.

"(a) 'cracked' surface, ...is not how voronoi is being represented here. Voronoi is a mathematical representation in which each barrier is equidistant from its nearest points, giving the telltale cobblestone appearance. "

Yes.

I do understand that the Qhull 3D voronoi should not look like the YouTube vid. If I can get each Qhull surface to function using given construction points - that will be success for this plugin.

THEN I will pursue modifying the script to accomplish my goals.
I need a 3D 'cracked' modification of the 2D cobblestone voronoi image… not exactly like the YouTube example, but similar. What I have in mind:

First establish the voronoi regions on the horizontal plane using x,y coordinates, add faces for each region at z elevations, run a follow-me profile on the edges (for starters, a deep V profile), select and pull down those vertices to form 3D 'cracks'. Rather like the Giant's causeway in Ireland, generated from data.

Separate script: Drawing the crust/anticrust surfaces as shown in the 2D applet (http://www.cs.unc.edu/~snoeyink/demos/crust/home.html) using the x, y coordinates, then applying the z's to form topography of ridgetops (crusts) and drainageways (anti-crusts).

Thank you for patience with my questions. It will take me some time to digest your code, as I'm a ruby infant.

~22curious
?**?...too, too many burning questions...?**?

[avariant]

It is true, there are points outside the Voronoi geometry. While I can't say for certain, I think it's because that some or all of the cell planes associated with those points are completely unbounded, so the script has no way of representing them as faces.

I used Selection(free) on all the previous examples. Selection (Bounding Box) was an attempt to reduce the number of unbounded points by adding "invisible" points at all the bounding box corners. In general, it doesn't really work.

All the points are construction points, yes.

I would like to see better 'enforced' bounding, absolutely. And I suspect that it's probably possible, but probably requires a lot more math than I've got in there now.

For dealing with "old" data, I suspect the script could be updated to actually delete the 'results' file where the Qhull output is placed before every run.

As for why you aren't getting results with your LSystem data, I'm not sure. If you want to post a scene I can take a look at it. If it's a ruby issue, I'll try to do something about it. If it's something inside Qhull, there won't really be much I can do.

[22curious]

After playing with the 2D Delaunay/Voronoi/Crust applet a bit more, I'm coming to terms with the CPoints outside the voronoi surface, assuming these points are in outer, unbounded cells with diverging faces (faces that converge to spikes for adjacent cells). These surfaces with spikes extending all the way to points should result from use of Qhull>voronoi>selection(free.

For some purposes, we (at least I) do need to enforce boundaries.

...Selection (Bounding Box) was an attempt to reduce the number of unbounded points by adding "invisible" points at all the bounding box corners. In general, it doesn't really work. ...

Setting the math aside for a moment, just conceptualizing - would it make sense:

?** to make the 'invisible' bounding box corner points and faces physically visible to us - (perhaps in a very transparent, different color), but keep the corner points 'invisible' to the calculations drawing the voronoi faces?
?** to make these bounding faces = bounding section planes?
?** to use the section planes to truncate/bind the spikes?
?** perhaps allow user interaction with section plane/truncation placement before finishing the cuts and deleting all beyond the boundaries?

To this newb, the 'bounding box' lends itself to using six sections for the bounding/truncating process. The spherical boundaries seem to require a different approach - unless spherical section surfaces exist. I'd be , but wouldn't that be fun?

For dealing with "old" data, I suspect the script could be updated to actually delete the 'results' file where the Qhull output is placed before every run.

?** Can you suggest scripts/snippets where this forced data refresh technique is used?

More about that 'old data' issue: I'm afraid that I may have confused Qhull by installing both ArchitectBoy's qhull and Avariant's Qhull into my plugins folder at the same time (suppose that's a Not2Do ). However, I still fail to get valid results from the Lsystem points after moving ArchitectBoy's version elsewhere.

...RE: LSystem data...post(ing) a scene.

'Will post the Lsystem *.skp after I find a alternate route for uploading *.skp's. The screenshots I saved to PhotoBucket, which doesn't seem to handle *.skp format.

~22curious
?**?...too, too many burning questions...?**?

[22curious]

Here's that skp. I think.

[qwertyas]

to make it work on VISTA, WINDOWS 7 run SKETCHUP AS ADMINISTRATOR

step by step:
1 rightclick on sketchup icon
2 select run as administrator
3 agree to yellow popup window
sketchup will start

to get flat voronoi net:
1. create some points (use projections plugin) they will be created on xy plane
2. select all points and convert to group
3. select group and copy vertical (no matter how high you place copy)

now you have two identical groups of points one above the second

4. select both groups
5. select menu plugins>qhull>voronoi> selection free

the voronoi tesselation will show up between point selections
done!

works for me, I hope will work for you

[dbalex]

thanks avariant for the plugin and thanks qwertyas for the workflow! it works perfectly!

[thomthom]

to make it work on VISTA, WINDOWS 7 run SKETCHUP AS ADMINISTRATOR

One has to find all the exe files that comes with the plugin, right click the files -> Properties and press the Unblock button. This is because Windows blocks executables downloaded from the internet.

[bigstick]

Any chance of a Mac version? There is a Mac version of Qhull here:- http://www.math.sunysb.edu/~sorin/online-docs/qhull/qh-get.htm