7 ms·

Free-form floor plan design using differentiable Voronoi diagram

259 points by alex_hirner 2y ago

elihu 2y ago
This is cool, in part because it's similar to an idea I had awhile back but didn't know how to actually implement it. The way I imagined it working was one Voronoi cell per room, but with a tweak where the Voronoi cells are weighted such that you can grow or shrink a Voronoi cell to fit whatever use you have for the room. (At which point it wouldn't really be a Voronoi diagram anymore, but I don't know if there's a name for this other thing. It ought to at least theoretically be possible to compute, because the way soap bubbles stack in 3 dimensions doesn't require all the soap bubbles to contain an exact quantity of air.) You could make the case that that isn't really necessary, since you can adjust Voronoi cell size just through the strategic placement of its neighboring cells, but it seemed useful to have an extra axis of control. The outer surfaces of the building could be given dome shapes, but it may be more aesthetically pleasing to give them the same angular surfaces as the interior walls by having "imaginary" cells bordering the outside that aren't part of the finished building but instead define its shape. I'd imagine the building could either be 3d-printed, or it could be constructed out of flat wall panels that are made in a factory, shipped to the building site, and bolted together (or affixed some other way) at the edges. The wall panels could also be shaped so that they form shelves or other usable surfaces out of the strange angles (especially the non-vertical walls). Ideally you'd have some program that can endlessly generate floor plan variations based on user input and site geometry, and then lay out all the plumbing and wiring and verify that it meets structural constraints, and the whole design manufactured and assembled without any human designer in the loop at all. No two houses need ever be exactly alike, every major component manufactured on-demand from standard material inputs. This would all be pretty hard to setup in reality, but it's how I imagine new construction in near-future science fiction cities, and eventually space habitats working. You spin up an O'Neil cylinder, and some program generates a layout to fill much of the interior with soap-bubble cities like massive mege-structure apartments, but without any repetition. Every neighborhood different than every other, maybe with some common stylistic elements to distinguish one part of town from another, but every location unique, like nature.
digilypse 2y ago
Really cool. Could see this being used for generative video game assets
- codetrotter 2y ago
  An FPS Death Match map, but every time a new match is started, the layouts of the rooms change somewhat. And maybe even like another commenter talked about, buildings themselves could be positioned using this technique too, so even the layout of the buildings and the roads change a bit every new match. It’ll be familiar, but at the same time unfamiliar, every time a new match starts. Some strategies will be useful across matches, some strategies will not.
  - reportgunner 2y ago
    Game called 'Due Process' has procedurally generated levels, but they are based on tilesets - I think rooms generated the OP way wouldn't make sense and would be very disorienting.
- readyplayernull 2y ago
  Recently found a similar game map generator: https://mode-vis.gumroad.com/l/IRzH https://mode-vis.gumroad.com/l/IRzH
szvsw 2y ago
Very cool! Extremely related to this, which focuses more on integrating architectural design constraints: http://www.rewdesign.ch/automated-floorplan-generation-in-architectural-design/ http://www.rewdesign.ch/automated-floorplan-generation-in-ar... https://www.researchgate.net/publication/380319243_A_hypergraph_model_shows_the_carbon_reduction_potential_of_effective_space_use_in_housing https://www.researchgate.net/publication/380319243_A_hypergr... https://github.com/ramonweber/hypergraph https://github.com/ramonweber/hypergraph
- donw 2y ago
  This is why I still come to HN. The articles may or not be useful, but you can bet that someone in the comments will link to a bunch of other related work.
  - szvsw 2y ago
    For sure. Read the author’s dissertation (should be posted on MIT DSpace by now or in the coming weeks) - it’s excellent. He just started teaching at Berkeley - definitely worth following his work. (Disclosure: I wrote all the Python API/web app/infra stuff in the repo above but not any of the underlying algorithms).
- larodi 2y ago
  I knew it Voronoi diagrams are much more than just a shiny topo tool. Incredibly simple approach, and yet so nice results. Kudos.
- twelvechairs 2y ago
  Of course the problems with all of these are - They are selecting only parts of the rich tapestry of what is meaningful and useful about an architectural space, which can also vary by culture and by person. - They also don't tend to respond to regulation requirements which may be 'hard line' or 'guideline' depending on the place. It's a complex world out there for good reason and it doesn't usually reduce well to a few key variables.
  - 2y ago
redandblack 2y ago
This will be great for deciding on voting districts
foota 2y ago
This is fascinating to me because I once tried to take a (vaguely) similar approach to generate a procedural city layout, taking a voronoi diagram, and then doing some modified flood fills to create buildings within the city while leavings streets. It feels to me like their approach could be used for this as well, since there's of course nothing that requires it to only be used for generating floor plans.
- notjoemama 2y ago
  Does anyone know how to forward this to Hello Games so they can work it into No Man’s Sky? lol
hansvm 2y ago
The general strategy of creating a differentiable representation of a problem and simply describing the constraints is pretty powerful. See also databases (allowing arbitrary knowledge storage to be a tightly integrated part of a larger ML problem), graph layouts (you can do _way_ better than something like graphviz if you add arbitrary differentiable characteristics as constraints in generation -- mixing and matching between the better parts of normal layout routines using your human intuition to say what's important about this graph in particular), ....
- nobuyuki83 2y ago
  I am one of the authors, Nobuyuki Umetani from the University of Tokyo, who implemented all the codes. I am delighted to see so many good discussions here! I fully understand that the quality of the result is low for the architectural standard. This research does not mean computing a perfect floor plan ready for architectural design. It's more like it gives the architect some rough design choices in the very early design stage. This research presents a new shape representation (differentiable Voronoi) for solving layout problems. These challenging problems typically involve geometrical and topological constraints. Existing shape representations are classified mainly into explicit (mesh) and implicit (using an implicit function) representations. While mesh representation is challenging in handling topological change, implicit representation is problematic because the boundary is not explicitly defined. Thus, it is difficult to compute the loss function based on the boundary shape. Differential Voronoi representation has both implicit and explicit representation properties (the wall is defined explicitly while the distance function from sites determines the shape) and is suitable for optimizing geometry and topology together. Thank you! I am happy that our research reaches such a large audience!!
- sleepydog 2y ago
  Do you know of a good introduction to this topic?
  - myhf 2y ago
    Differentiable Programming from Scratch https://thenumb.at/Autodiff/ https://thenumb.at/Autodiff/
javier123454321 2y ago
Geez, as architecture these plans are absolutely horrible and produce unusable spaces. As an abstract math problem, it seems marginally useful, but I would not want to live in a place laid out by this algorithm.
- Aeolun 2y ago
  I don’t think most people would build their office in the shape of a duck. There’s little you can do given those constraints xD
- photonthug 2y ago
  It seems like if you already have a weird space, you can also maybe use this to minimize cuts while you’re adding carpet, or solve constraints about minimizing distance for shared water supply pipes that need to touch the sink and the shower, etc. That said I actually might want a room shaped like a duck, provided I don’t have to put down the flooring =)
- cabidaher 2y ago
  As a non-architect, I would love if you could explain some of what makes the non-duck designs _so_ horrible. Some of them looked more than fine to me at first glance. It's also something that can be rerun over and over with little interaction in-between runs so one could generate a handful of designs starting from different seeds and get inspiration.
  - orthoxerox 2y ago
    You generally want your rooms to be not just rectilinear, but rectangular after you fill in all built-in storage spaces. And storage spaces have to be sized appropriately to their intended purpose: you don't want three-foot-deep shelves. Another thing this optimizer doesn't take into account is corridors. It has the notion of room connections and area ratios, but area ratios are the wrong way to think about corridors: you want them to be as small as possible while still having at least a certain width.
    - 2y ago
pimlottc 2y ago
I'm no architect, but surely the precise details of the exterior walls are decided based on the floor plan, not the other way around? Seems odd to assume the walls are fixed before the floor plan has been determined. Of course, the shape of the lot and other physical factors put general limitations on the bounds of the house, but filling the entire lot isn't usually the primary goal. Maybe it's more useful for a renovation?
- freeone3000 2y ago
  I’m not sure why you’d assume that rather than the inverse. The house is set to fit a certain number of square feet based on economic concerns (heating and cooling costs primarily), then the ordinances on setback and separation come into play, then the very clear rectangle that results is your starting point for interior planning.
  - deleted 2y ago
    [deleted]
  - contingencies 2y ago
    Both are used. Hence, any good design should explicitly state what the goals are (ie. what we are optimizing for) before embarking on the design process. Commercial real estate generally optimizes for profit, which means, floor space, however this may be subject to regulation and particularly significant cost constraints (eg. maximum height before alternate structural features required, maximum height of available raw materials, HVAC/insulation, site aspect, site topography). High end residential real estate is perhaps the most interesting, because good residential architecture facilitates aesthetic concern and draws from the full palette of commercial architecture in addition to traditional methods while not being constrained by finance. Hence, very interesting results can sometimes be obtained from good architects who will consider factors such as foliage, natural audio, etc. which are often ~ignored or afterthoughts in commercial/industrial. IMHO good and original design in adequately resourced contexts tends to be iterative and to consider all paths toward a solution, not only a preconceived approach and a waterfall solution.
- jkaptur 2y ago
geon 2y ago
What do the cells represent, and why are they more dense in some spots?
- hwillis 2y ago
  The cells are the areas closest to the voronoi sites, the dots inside the cells. The sites are the outputs of the optimizer; it adjusts the sites until the constraints are met well. The number of sites is chosen by the user. The excess sites will naturally be clustered together and weakly tend away from the interior walls. The optimizer prefers straighter walls, so it tries to cover the room in large cells (which have big straight edges) and then shove the rest of the points into a small area where they aren't affecting the internal walls. Thats why they tend to cluster into the center of internal rooms, or towards exterior corners where the wall is preset.
IshKebab 2y ago
Uhm shouldn't the rooms be rectangular? You don't see many polygonal rooms for obvious reasons...
- lm28469 2y ago
  That's the reason architecture is closer to an art than hard science. The most optimal math answer usually sucks ass from a usability/look/&c. point of view
rurban 2y ago
Cool. In the 90ies I thought similar approaches at our university, and we had practical examples of such constraints. In general city planning was much easier than structural buildings, because gravity and building rules are much stricter than city planning riles, which are trivial. We also had rules layed out graphically, and did a substitution process in the optimizations. Neufert did help much more than Christopher Alexander.
ivanjermakov 2y ago
I understand that this might be out of scope of the project, but floor plan design is more convoluted than filling the space with some constraint. Necessary things to respect: - recrangular rooms: non-straight angles are hard to work with - windows: unless this is a plan for the underground floor - water/waste water supply/vent shaft: for multi-floor buildings cannot be moved - personal needs: some people need lots of storage space, some a room to play videogames, some a huge kitchen with an isle. All of that must be reflected in a good floor plan With that said, I feel like this project might be good for less serious application like procedural game design, but is too naive for real architectural use.
- Rhapso 2y ago
  I suspect this is all well understood by the authors. We do research one simple step at a time, then we sell it as "look at this amazing thing" because we like funding (which enables future research and eating food!)
- hwillis 2y ago
  Windows and pipes/vents are just constraints. Windows are constraints to outside areas and pipes/vents/stairs are constraints between floors. Rectangularity is enforced by the wall loss function, which is adjustable. > personal needs: some people need lots of storage space, some a room to play videogames, some a huge kitchen with an isle. That's... the point. You decide you want your kitchen to be 20% bigger and the floor plan readjusts itself without needing somebody to draw up a new plan. > With that said, I feel like this project might be good for less serious application like procedural game design, but is too naive for real architectural use. Given that this is a paper submission to the Pacific Graphics conference, yes. Architecture is not really the point. You could also point out some much more obvious architectural needs, like the fact that houses need an outside too.

259 points by alex_hirner 2y ago

This is cool, in part because it's similar to an idea I had awhile back but didn't know how to actually implement it. The way I imagined it working was one Voronoi cell per room, but with a tweak where the Voronoi cells are weighted such that you can grow or shrink a Voronoi cell to fit whatever use you have for the room. (At which point it wouldn't really be a Voronoi diagram anymore, but I don't know if there's a name for this other thing. It ought to at least theoretically be possible to compute, because the way soap bubbles stack in 3 dimensions doesn't require all the soap bubbles to contain an exact quantity of air.) You could make the case that that isn't really necessary, since you can adjust Voronoi cell size just through the strategic placement of its neighboring cells, but it seemed useful to have an extra axis of control. The outer surfaces of the building could be given dome shapes, but it may be more aesthetically pleasing to give them the same angular surfaces as the interior walls by having "imaginary" cells bordering the outside that aren't part of the finished building but instead define its shape. I'd imagine the building could either be 3d-printed, or it could be constructed out of flat wall panels that are made in a factory, shipped to the building site, and bolted together (or affixed some other way) at the edges. The wall panels could also be shaped so that they form shelves or other usable surfaces out of the strange angles (especially the non-vertical walls). Ideally you'd have some program that can endlessly generate floor plan variations based on user input and site geometry, and then lay out all the plumbing and wiring and verify that it meets structural constraints, and the whole design manufactured and assembled without any human designer in the loop at all. No two houses need ever be exactly alike, every major component manufactured on-demand from standard material inputs. This would all be pretty hard to setup in reality, but it's how I imagine new construction in near-future science fiction cities, and eventually space habitats working. You spin up an O'Neil cylinder, and some program generates a layout to fill much of the interior with soap-bubble cities like massive mege-structure apartments, but without any repetition. Every neighborhood different than every other, maybe with some common stylistic elements to distinguish one part of town from another, but every location unique, like nature.

digilypse 2y ago

Really cool. Could see this being used for generative video game assets

codetrotter 2y ago
An FPS Death Match map, but every time a new match is started, the layouts of the rooms change somewhat. And maybe even like another commenter talked about, buildings themselves could be positioned using this technique too, so even the layout of the buildings and the roads change a bit every new match. It’ll be familiar, but at the same time unfamiliar, every time a new match starts. Some strategies will be useful across matches, some strategies will not.
- reportgunner 2y ago
  Game called 'Due Process' has procedurally generated levels, but they are based on tilesets - I think rooms generated the OP way wouldn't make sense and would be very disorienting.
readyplayernull 2y ago
Recently found a similar game map generator: https://mode-vis.gumroad.com/l/IRzH https://mode-vis.gumroad.com/l/IRzH

szvsw 2y ago

Very cool! Extremely related to this, which focuses more on integrating architectural design constraints: http://www.rewdesign.ch/automated-floorplan-generation-in-architectural-design/ http://www.rewdesign.ch/automated-floorplan-generation-in-ar... https://www.researchgate.net/publication/380319243_A_hypergraph_model_shows_the_carbon_reduction_potential_of_effective_space_use_in_housing https://www.researchgate.net/publication/380319243_A_hypergr... https://github.com/ramonweber/hypergraph https://github.com/ramonweber/hypergraph

donw 2y ago
This is why I still come to HN. The articles may or not be useful, but you can bet that someone in the comments will link to a bunch of other related work.
- szvsw 2y ago
  For sure. Read the author’s dissertation (should be posted on MIT DSpace by now or in the coming weeks) - it’s excellent. He just started teaching at Berkeley - definitely worth following his work. (Disclosure: I wrote all the Python API/web app/infra stuff in the repo above but not any of the underlying algorithms).
larodi 2y ago
I knew it Voronoi diagrams are much more than just a shiny topo tool. Incredibly simple approach, and yet so nice results. Kudos.
twelvechairs 2y ago
Of course the problems with all of these are - They are selecting only parts of the rich tapestry of what is meaningful and useful about an architectural space, which can also vary by culture and by person. - They also don't tend to respond to regulation requirements which may be 'hard line' or 'guideline' depending on the place. It's a complex world out there for good reason and it doesn't usually reduce well to a few key variables.
- 2y ago

redandblack 2y ago

This will be great for deciding on voting districts

foota 2y ago

This is fascinating to me because I once tried to take a (vaguely) similar approach to generate a procedural city layout, taking a voronoi diagram, and then doing some modified flood fills to create buildings within the city while leavings streets. It feels to me like their approach could be used for this as well, since there's of course nothing that requires it to only be used for generating floor plans.

notjoemama 2y ago
Does anyone know how to forward this to Hello Games so they can work it into No Man’s Sky? lol

hansvm 2y ago

The general strategy of creating a differentiable representation of a problem and simply describing the constraints is pretty powerful. See also databases (allowing arbitrary knowledge storage to be a tightly integrated part of a larger ML problem), graph layouts (you can do _way_ better than something like graphviz if you add arbitrary differentiable characteristics as constraints in generation -- mixing and matching between the better parts of normal layout routines using your human intuition to say what's important about this graph in particular), ....

nobuyuki83 2y ago
I am one of the authors, Nobuyuki Umetani from the University of Tokyo, who implemented all the codes. I am delighted to see so many good discussions here! I fully understand that the quality of the result is low for the architectural standard. This research does not mean computing a perfect floor plan ready for architectural design. It's more like it gives the architect some rough design choices in the very early design stage. This research presents a new shape representation (differentiable Voronoi) for solving layout problems. These challenging problems typically involve geometrical and topological constraints. Existing shape representations are classified mainly into explicit (mesh) and implicit (using an implicit function) representations. While mesh representation is challenging in handling topological change, implicit representation is problematic because the boundary is not explicitly defined. Thus, it is difficult to compute the loss function based on the boundary shape. Differential Voronoi representation has both implicit and explicit representation properties (the wall is defined explicitly while the distance function from sites determines the shape) and is suitable for optimizing geometry and topology together. Thank you! I am happy that our research reaches such a large audience!!
sleepydog 2y ago
Do you know of a good introduction to this topic?
- myhf 2y ago
  Differentiable Programming from Scratch https://thenumb.at/Autodiff/ https://thenumb.at/Autodiff/

javier123454321 2y ago

Geez, as architecture these plans are absolutely horrible and produce unusable spaces. As an abstract math problem, it seems marginally useful, but I would not want to live in a place laid out by this algorithm.

Aeolun 2y ago
I don’t think most people would build their office in the shape of a duck. There’s little you can do given those constraints xD
photonthug 2y ago
It seems like if you already have a weird space, you can also maybe use this to minimize cuts while you’re adding carpet, or solve constraints about minimizing distance for shared water supply pipes that need to touch the sink and the shower, etc. That said I actually might want a room shaped like a duck, provided I don’t have to put down the flooring =)
cabidaher 2y ago
As a non-architect, I would love if you could explain some of what makes the non-duck designs _so_ horrible. Some of them looked more than fine to me at first glance. It's also something that can be rerun over and over with little interaction in-between runs so one could generate a handful of designs starting from different seeds and get inspiration.
- orthoxerox 2y ago
  You generally want your rooms to be not just rectilinear, but rectangular after you fill in all built-in storage spaces. And storage spaces have to be sized appropriately to their intended purpose: you don't want three-foot-deep shelves. Another thing this optimizer doesn't take into account is corridors. It has the notion of room connections and area ratios, but area ratios are the wrong way to think about corridors: you want them to be as small as possible while still having at least a certain width.
  - 2y ago

pimlottc 2y ago

I'm no architect, but surely the precise details of the exterior walls are decided based on the floor plan, not the other way around? Seems odd to assume the walls are fixed before the floor plan has been determined. Of course, the shape of the lot and other physical factors put general limitations on the bounds of the house, but filling the entire lot isn't usually the primary goal. Maybe it's more useful for a renovation?

freeone3000 2y ago
I’m not sure why you’d assume that rather than the inverse. The house is set to fit a certain number of square feet based on economic concerns (heating and cooling costs primarily), then the ordinances on setback and separation come into play, then the very clear rectangle that results is your starting point for interior planning.
- deleted 2y ago
  [deleted]
- contingencies 2y ago
  Both are used. Hence, any good design should explicitly state what the goals are (ie. what we are optimizing for) before embarking on the design process. Commercial real estate generally optimizes for profit, which means, floor space, however this may be subject to regulation and particularly significant cost constraints (eg. maximum height before alternate structural features required, maximum height of available raw materials, HVAC/insulation, site aspect, site topography). High end residential real estate is perhaps the most interesting, because good residential architecture facilitates aesthetic concern and draws from the full palette of commercial architecture in addition to traditional methods while not being constrained by finance. Hence, very interesting results can sometimes be obtained from good architects who will consider factors such as foliage, natural audio, etc. which are often ~ignored or afterthoughts in commercial/industrial. IMHO good and original design in adequately resourced contexts tends to be iterative and to consider all paths toward a solution, not only a preconceived approach and a waterfall solution.
jkaptur 2y ago

geon 2y ago

What do the cells represent, and why are they more dense in some spots?

hwillis 2y ago
The cells are the areas closest to the voronoi sites, the dots inside the cells. The sites are the outputs of the optimizer; it adjusts the sites until the constraints are met well. The number of sites is chosen by the user. The excess sites will naturally be clustered together and weakly tend away from the interior walls. The optimizer prefers straighter walls, so it tries to cover the room in large cells (which have big straight edges) and then shove the rest of the points into a small area where they aren't affecting the internal walls. Thats why they tend to cluster into the center of internal rooms, or towards exterior corners where the wall is preset.

IshKebab 2y ago

Uhm shouldn't the rooms be rectangular? You don't see many polygonal rooms for obvious reasons...

lm28469 2y ago
That's the reason architecture is closer to an art than hard science. The most optimal math answer usually sucks ass from a usability/look/&c. point of view

rurban 2y ago

Cool. In the 90ies I thought similar approaches at our university, and we had practical examples of such constraints. In general city planning was much easier than structural buildings, because gravity and building rules are much stricter than city planning riles, which are trivial. We also had rules layed out graphically, and did a substitution process in the optimizations. Neufert did help much more than Christopher Alexander.

ivanjermakov 2y ago

I understand that this might be out of scope of the project, but floor plan design is more convoluted than filling the space with some constraint. Necessary things to respect: - recrangular rooms: non-straight angles are hard to work with - windows: unless this is a plan for the underground floor - water/waste water supply/vent shaft: for multi-floor buildings cannot be moved - personal needs: some people need lots of storage space, some a room to play videogames, some a huge kitchen with an isle. All of that must be reflected in a good floor plan With that said, I feel like this project might be good for less serious application like procedural game design, but is too naive for real architectural use.

Rhapso 2y ago
I suspect this is all well understood by the authors. We do research one simple step at a time, then we sell it as "look at this amazing thing" because we like funding (which enables future research and eating food!)
hwillis 2y ago
Windows and pipes/vents are just constraints. Windows are constraints to outside areas and pipes/vents/stairs are constraints between floors. Rectangularity is enforced by the wall loss function, which is adjustable. > personal needs: some people need lots of storage space, some a room to play videogames, some a huge kitchen with an isle. That's... the point. You decide you want your kitchen to be 20% bigger and the floor plan readjusts itself without needing somebody to draw up a new plan. > With that said, I feel like this project might be good for less serious application like procedural game design, but is too naive for real architectural use. Given that this is a paper submission to the Pacific Graphics conference, yes. Architecture is not really the point. You could also point out some much more obvious architectural needs, like the fact that houses need an outside too.