[Plugin] QHull

watkins · 14 May 2009, 16:37

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

Regards,
Bob

craigbic · 14 May 2009, 19:19

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 · 14 May 2009, 19:30

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

MALAISE · 18 May 2009, 09:10

MALAISE

halroach · 19 May 2009, 06:07

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 · 19 May 2009, 16:13

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

avariant · 19 May 2009, 23:54

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 · 20 May 2009, 00:05

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

pilou · 20 May 2009, 00:07

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

22curious · 26 Sept 2009, 22:50

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.

@avariant said:

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?)

@unknownuser said:

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 · 27 Sept 2009, 06:04

@22curious said:

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

I haven't found a solution yet...

avariant · 27 Sept 2009, 16:25

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 · 29 Sept 2009, 17:08

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 · 29 Sept 2009, 19:33

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 · 1 Oct 2009, 00:07

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:

Thanks for your feedback!

avariant · 1 Oct 2009, 23:02

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.

voronoi_demo.skp

avariant · 1 Oct 2009, 23:05

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.

22curious · 2 Oct 2009, 18:13

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:

@avariant said:

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?

@avariant said:

"... 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?

@avariant said:

"…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.

@avariant said:

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

@avariant said:

" ...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?

@avariant said:

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

@avariant said:

"(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&#058;  Drawing the crust/anticrust surfaces as shown in the 2D applet ([http://www.cs.unc.edu/~snoeyink/demos/crust/home.html](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.

%(#FF8000)[~22curious
*??...too, too many burning questions...??*]

avariant · 2 Oct 2009, 22:20

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 · 3 Oct 2009, 00:01

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.

@avariant said:

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

@avariant said:

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.

@avariant said:

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

%(#FF8040)[~22curious
*??...too, too many burning questions...??*]