We all know Voronoi diagrams right? At the AA there was a bit of a running joke about how much they were used. A quick image search will turn up thousands of design projects based on them. Their wide appeal is understandable – they have a simple and clear logic which can be used to generate organic looking tessellations from any pattern of input points.
The recent obsession with them in architecture schools goes back maybe 6 or 7 years, but they were invented more than 100 years ago. So are there still aspects of them which have not yet been explored?
Firstly, there is a remarkably easy way of generating 2D Voronoi diagrams without any sort of coding or plugins that I suspect is perhaps not as well known as it deserves to be. Just take cones and simply look at the orthogonal projection of where they intersect.
Voila! instant Voronoi
(This is not a very computationally efficient way of doing it, but it certainly makes it more intuitively understandable)
Secondly, there is an alternative way of generalising Voronoi diagrams to 3D which gives a variety of interesting curved surfaces.
In 2 dimensions a Voronoi diagram partitions the plane(2D) according to proximity to points (0D), with the boundaries being lines (1D)
In 3D we can also divide space according to proximity to points, giving polyhedral cells -like bubbles in a foam- and this is usually what is referred to as a 3D Voronoi (and what has gained popularity within architecture)
However, there is another way of generalising from 2 to 3D that is arguably more natural. Before, we had an (N)Dimensional space partitioned according to proximity of (N-2)D objects and the boundaries were (N-1)D objects.
So taking N=3, we have a division of 3D space by surfaces according to proximity to lines.
I wrote a quick Grasshopper sketch to play around with these surfaces (sometimes called medial surfaces, but as far as I can tell, they have not yet been used much as a generative design technique). Its very crude at the moment and limited to only 2 curves, but you can see that it generates some interesting forms. (The chunky Lego aesthetic is only temporary, until I get around to having a go at implementing a marching cubes algorithm)
In the simplest case, 2 lines give a hyperbolic paraboloid:
A Hopf link:
2 Helices give a Helicoid:
A Whitehead Link:
A Square knot:
Next step is to make it work for multiple curves. There are some fascinating links with (near) minimal surfaces. Taking spatial networks or 3D weaves (like the ones in this video) as the input curves could give all sorts of interesting labyrinths.
Get the Grasshopper definition here:
medialsurface.ghx
March 16, 2009 at 11:35 pm
Unsurprisingly, Voronoi diagrams of straight lines in 3d have been studied in computational geometry, but it’s still an open problem (http://maven.smith.edu/~orourke/TOPP/P3.html) how complicated they can be. There’s an easy quadratic lower bound (a row of parallel lines in one plane and a second row of parallel lines with a different slope in a second parallel plane), a cubic upper bound, and not much known in between.
If you’re looking for a source for the cone idea of visualizing Voronoi diagrams, it’s mentioned in O’Rourke’s 1998 book ”Computational Geometry in C” as an aid for understanding Fortune’s algorithm for the construction of the diagrams. (The “beach line” in the algorithm is just the 2d projection of the intersection of the cones with a slanted plane.) The same idea is already in Fortune’s 1986 SoCG paper, attributed to a 1985 personal communication from Herbert Edelsbrunner.
March 17, 2009 at 12:59 am
Hi David, many thanks for the background.
I didnt mean to suggest that these aspects had not been studied before, just that they seem so far underutilized in design.
By the way, If any readers dont know it, do check out David’s ‘Geometry Junkyard’
http://www.ics.uci.edu/~eppstein/junkyard/
It has a massive collection of great links for many different geometric topics
March 17, 2009 at 2:25 pm
[…] out his medial surfaces between link components. Below is Piker’s image of the medial surface between the components […]
March 20, 2009 at 1:44 am
Here is a building that explores the conical voronoi ‘algorithm’….
http://www.minifienixon.com/doku.php?id=home:projects:victorian_college_of_the_arts
March 26, 2009 at 5:58 pm
I think this is the easier way for voronoi construction. Thanks Daniel for this post, i’ve realized one simple grashopper definition about this voronoi construction.
Regards,
davide
///////
http://madeincalifornia.blogspot.com/
//////
May 30, 2009 at 11:46 pm
hi,
nice page.
i’m in a bit of a hurry, but i’ll come back for a closer look soon. in the meantime, i’d like to ask a question.
i’m not a mathematician but i’m wanting to generate a medial axis transform (MAT) of a feature in a video frame, most likely using a Delaunay tesselation.
my goal is to implement a machine vision system to analyze the gait of an arthropod in a neuroethological investigation. ultimately i want to label the MAT with anatomical features for further analysis.
pinpoint accuracy is less important than efficiency, and i’m hoping i can find some kind of randomized parallel algorithm that i can run on a gpu, either using an embedded shading language or CUDA. i’m also wondering if perhaps i can exploit the optimized geometry processing pipeline of a consumer gfx card.
do you have any thoughts on this?
cheers
May 31, 2009 at 11:02 am
Hi Jono,
That sounds an interesting project – Its an application I wouldn’t have guessed at. Are you looking at arthropods like
this one? :)
I’m certainly no expert on these technical aspects of medial axes. Perhaps
this collection of links might be a good place to start.
Speeding things up by shifting them to the GPU is interesting too, but it sounds like you know more about this than me.
June 1, 2009 at 10:37 am
lol! thanx Daniel. that’s scary. but awesome! my study animal is a centipede, about 2cm long.
i’ve seen that page before, but there was some stuff i hadn’t seen (or maybe i missed it).
in particular, The Scale Space Skeletonization Page [cyvision.if.sc.usp.br/msskeletons], which is a very exciting discovery for me, and may be just what i’m looking for.
so thankyou. i’m still looking thru your other stuff on this blog. some of its amazing!
cheers.
October 5, 2009 at 12:18 pm
[…] I have written about earlier, this also generalises nicely to 3D […]
November 13, 2009 at 4:53 pm
hello deniel,
your medialsurface is amazing!!but GH file link is porbably dead now?? It will be great apperciated if you could fix the link or email the GH file directly to me.Thank you very much.The address:hero18wang@gmail.com
Thanks again.
November 13, 2009 at 4:59 pm
HI Daniel,
I know about you from the Grasshopper Social network at Ning.your works inspire me a lot.thank you.
May 14, 2010 at 2:00 pm
This looks really interesting, and I’d also like to take a look at the grasshopper definition, but the link doesn’t seem to work….. Either way, thanks!
January 9, 2014 at 7:57 pm
Hi Daniel,
Although I may be little outdated, but I would like to look at medialsurface.ghx definition.
Is it possible to download it somewhere?
P.S. Thanks for great work! It’s simply amazing!
October 14, 2017 at 3:37 am
*very nice post, i certainly love this website, keep on it