[Plugin] QHull

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.

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:

@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

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.

@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...??*]

22curious

Here's that skp. I think.

Ex_LSystemPOINTS_QhullStall.skp

Inspiration and texture

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:

create some points (use projections plugin) they will be created on xy plane
select all points and convert to group
select group and copy vertical (no matter how high you place copy)

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

select both groups
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

@qwertyas said:

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

lapx

Can this be achieved with this plugin.
http://www.youtube.com/watch?v=Bw61WJbe2VU&feature=related
Not working in my version.

vklidu

I have the same question
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

Thanks

serraniadan

@qwertyas said:

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

IT WAS SO DAMN SIMPLE!!! excelent dude! Thanks

DareDevil

Since a long time I dont use this plug, but I need it today and I reinstall it... and, of course, it dont works on my Win7

@qwertyas said:

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

I dont like to run as Administrator, so I searched an other "safer" way...

This is my solution for Windows :

Move the qhull directory form the SU plugins directory to the root of (I dont like to put something in the root of C:, but I prefer to run as admin )
In the SU plugin directory edit the qhull.rb and change

def self.initialize
	@qhull_path = Sketchup.find_support_file("Plugins/qhull")
	@qhull_path = @qhull_path + "/qhull-2003.1"
end

to

def self.initialize
	@qhull_path = "c;/qhull/qhull-2003.1"
end

... and all works fine !

Edit 02/2015 :

This solution for windows is now obsolete since the plugin directory is in the User/AppData folder, no more authorization needed.

DareDevil

This plugin must be updated with Qhull 2012 for more stability on Win 64.
I did it for me, but I dont know if I can post it here... It's Avariant's plug, not mine

DareDevil

I'm not a Mac user for years...
There is a MacOS portage of Qhull. There is some one to port the Qhull plugin on MacOS with it ?