Shape Grammar for Room Layout
Cherry ZhangDavid R. Cheriton School of Computer Science
Objectives
There are many existing applications for room planning[1,2]. These applications are based on "drag-and-drop" concepts, in which users have full control of the planning process. The purpose of this project is to show that simple room layouts can be generated automatically using shape grammars. This project was written in C++ with OpenGL and Gtk. The concept of using shape grammars to generate room layouts can be applied to real-world applications such as interior design, games, dorm and hotel room design, and layout planning.Why can we use shape grammars for interior design
- Pattern: Room layouts have certain patterns in furniture arrangements. For example, a double-bed dorm always have two beds, two desks, two chairs, two closets and possibly other furnitures. The beds are usually placed at the corners of the room. In a dining room, most people prefer to have the same number of chairs at each side of the table. These patterns allow us to write "grammars" or "production rules" to generate room layouts automatically.
- Variety: If we incorporate randomness in choosing production rules, then the algorithm will help us produce various room layouts.
- Speed: "Drag-and-drop" applications are more suitable for planning a small number of rooms because they require users to manually place each furniture. If we want to generate a large number of different room layouts, then using shape grammars is a better choice. Shape-grammar based applications require minimal effort from users and rely on fast computer algorithms.
Theoretical basis
In this project, I derived my own shape grammars for room layouts based on the following concepts- Split grammar: We start with a large object/shape. Then we split it into smaller objects/shapes according some production rules. Splitting ends when we reach a "terminal" (un-splitable object/shape).
- Attribute grammar: We use parameters, either specified by users or by the system itself, to control the selection of production rules.
- L-Systems: L-Systems is "recursive" in nature because the same production rules can be applied again and again. Unlike context-free grammars, L-Systems allows the application of multiple production rules at a single iteration.
Problems with existing shape grammars
In this course, we studied several papers on generating buildings with shape grammars. We observed two major problems with existing shape grammars:- Complex Input: Most applications for generating buildings with shape grammars require the user to input complex shape grammars. Therefore, the users have to be technical enough to write shape grammars that can be parsed and compiled by the application.
- Evaluation: Shape grammars can generate a large variety of buildings. Some results are unfeasible in real life. Therefore we need some evaluatoin schemes or algorithms to filter the results. We must also allow users to be able to participate in the filtering process.
Examples 1: single-bed dorm layouts
In general, the start symbol of the grammar is the room itself. The non-terminals are "functional areas" or "spatial divisions" of the room. The terminal symbols are the furnitures. The following shape grammars are used to generate single-bed dorm layouts:&emsp &emsp bedroom → split {"X", 0.5, 0.5} sleep_area | study_area
&emsp &emsp bedroom → split {"Y", 0.5, 0.5} sleep_area | study_area
&emsp &emsp sleep_area → split {"X", 0.7, 0.3} BED | CLOSET
&emsp &emsp sleep_area → split {"Y", 0.7, 0.3} BED | CLOSET
&emsp &emsp study_area → split {"X", 0.2, 0.8} DESK | CHAIR
&emsp &emsp study_area → split {"Y", 0.2, 0.8} DESK | CHAIR
&emsp &emsp place_at_edge{study_area, DESK, CHAIR}
&emsp &emsp place_at_corner{sleep_area, BED}
&emsp &emsp place_at_corner{sleep_area, CLOSET}
Start symbol = { bedroom }
Non-terminals = { sleep_area, study_area }
Terminals = { BED, DESK, CHAIR, CLOSET }
Examples 2: double-bed dorm layouts
In general, the start symbol of the grammar is the room itself. The non-terminals are "functional areas" or "spatial divisions" of the room. The terminal symbols are the furnitures. The following shape grammars are used to generate double-bed dorm layouts:&emsp &emsp bedroom → split {"X", 0.5, 0.5} sleep_area | study_area
&emsp &emsp bedroom → split {"Y", 0.5, 0.5} sleep_area | study_area
&emsp &emsp sleep_area → split {"X", 0.5, 0.5} sleep_area_1 | sleep_area_2
&emsp &emsp sleep_area_1 → split {"X", 0.7, 0.3} BED_1 | CLOSET_1
&emsp &emsp sleep_area_1 → split {"Y", 0.7, 0.3} BED_1 | CLOSET_1
&emsp &emsp sleep_area_2 → split {"X", 0.7, 0.3} BED_2 | CLOSET_2
&emsp &emsp sleep_area_2 → split {"Y", 0.7, 0.3} BED_2 | CLOSET_2
&emsp &emsp study_area → split {"X", 0.5, 0.5} study_area_1 | study_area_2
&emsp &emsp study_area → split {"Y", 0.5, 0.5} study_area_1 | study_area_2
&emsp &emsp study_area_1 → split {"X", 0.2, 0.8} DESK_1 | CHAIR_1
&emsp &emsp study_area_1 → split {"Y", 0.2, 0.8} DESK_1 | CHAIR_1
&emsp &emsp study_area_2 → split {"X", 0.2, 0.8} DESK_2 | CHAIR_2
&emsp &emsp study_area_2 → split {"Y", 0.2, 0.8} DESK_2 | CHAIR_2
&emsp &emsp place_at_corner{sleep_area_1,BED_1, CLOSET_1}
&emsp &emsp place_at_corner{sleep_area_2,BED_2, CLOSET_2}
&emsp &emsp place_at_edge{study_area_1,DESK_1, CHAIR_1}
&emsp &emsp place_at_edge{study_area_2,DESK_2, CHAIR_2}
Start symbol = { bedroom }
Non-terminals = { sleep_area, sleep_area_1, sleep_area_2, study_area, study_area_1, study_area_2 }
Terminals = { BED_1, BED_2, DESK_1, DESK_2, CHAIR_1, CHAIR_2, CLOSET_1, CLOSET_2 }
Some implementation details
- To solve the "complex input" problem with the existing shape grammars, I implemented a "grammar generating" function in my application. Instead of shape grammars, users only have to specify furniture types, number of each furniture and optionally, dimension of each furniture. The application generates a unique set of shape grammars automatically, according to user inputs. For now, shape grammar generation is mainly hard-coded to cover all possible inputs.
- To partially solve the "evaluation" issue mentioned above, I used mixed-initiative design. For each set of shape grammars, the application generates a relatively large configuration tree, which stores a set of both feasible and non-feasible layouts. The current application presents all the layouts to the users and let them decide what they likes.
- The most important data structure in the application is a tree. There are three different types of nodes in the tree: division nodes, level nodes, and leaf nodes. Division nodes represent "functional spaces" of a room (e.g. sleep area or study area), or non-terminals in the shape grammars. Leaf nodes represent furnitures, or terminals in the shape grammars. Level nodes are parents of leaf nodes. They are mainly used to easily identify leaf nodes. Division nodes can be divided into other division nodes, based on a "split" rule in the shape grammar. Leaf nodes (furnitures) can only be "arranged", not "divided". All types of nodes store a set of possible configurations they have. A layout is a combination of different configurations of each leaf node. A graphical representation of the concept is shown in the next section.
- The current application apply a limited number of rules in placing furnitures. For example, beds and closets are always placed at the corner of the subspace they are in. Chairs are always placed in front of desks. These rules help reduce the number of non-feasible layouts and keeps the configuration tree relatively small.
Results
Figure 1: The parse tree for the shape grammars for generating a bedroom with two beds, two desks and two chairs.
Figure 2: The configuration tree for spatial subdivision and furniture arrangements for a bedroom with one bed, one deskand one chair.
Figure 3: The interface of the application.
Figure 4: An example showing spatial subdivisions of functional areas.
Figure 5: Some feasible layouts for a single-bed dorm. The shape grammars are shown in Example 1.
Figure 6: An infeasible layout for a single-bed dorm. The shape grammars are shown in Example 1.
Figure 7: Some feasible layouts for a two-bed dorm. The shape grammars are shown in Example 2.
Figure 8: An infeasible layout for a two-bed dorm. The shape grammars are shown in Example 2.
Discussions
- Split grammar
I studied some examples on split grammars in [4] and [5].In these examples, builds are first considered as a whole, then sub-divided into smaller components such as floors and facades, until an undividable component, such as a window, is reached. I noticed that similar idea can be used for room layouts. Figure is illustrates the subdivision process used in this project.
An exapmle of facade split.
An example of building split.
A sample shape grammar input for generating buildings.
- Comparison of context-free grammar, split grammar, and my shape grammar for this project
The general form for a rule in context-free grammar is A → r, where r is a string of terminals or non-terminals, including A itself. None of the papers on shape grammars we've seen discussed about the relationship between shape grammars and context-free grammars, or provided any justifications on whether shape grammar is a subset of context-free grammar. On the other hand, it is easy to see that split grammar is not a subset of context-free grammar because for instance, we do not allow the right-hand side of a production rule to contain the non-terminal on the left-hand side of the rule. Also, as seen in the split grammar example above, we use the "Repeat" rule rather than a production rule to generate repetitive patterns. Therefore in my opinion, we cannot yet view shape grammars as a form of formal grammars. Instead, we should consider shape grammars as a set of production rules that we use for very specific tasks. The shape grammars used in my project were derived for producing room layouts only. I provide no justifications on its formality. - Extension
The most straight forward way to extend the application is to hard-code more rules for generating shape grammars based on user inputs. For now, the configuration tree is "binary" for division and level nodes. That is, we only allow split-to-two-parts operations for divisions. It should not be too hard to extend the binary tree to multi-children tree to support other split operations. - Limitations and future work
There are three ways for users to select their desired layout from all possible layouts. My application adopts the first ways. It allows users to browse through all possible layouts and explicitly select their desired one. Another way is "guided-search". In guided search, we present a few "distinctive" layouts and ask users to choose the one that is most similar to their desired layout. The application then search through only part of the configuration tree that contains the selected layout. The results of the search will be a set of layouts similar to the selected layout. In theory, guided search should be faster and work better for large configuration trees. Another way for users to select their desired layout is to allow them to manipulate the arrangment of each functional space or furniture. This idea is similar to [3]. I think the third way defeats the purpose of having shape grammars. If an application relies too much on user interactions or gives too much freedom to the users, then it will resemble a "drag and drop" application more.
Some possible future work includes:
(1) Improve models for furnitures and rooms to make the application look graphically appealing. This requires a significant amount of time.
(2) Support more types of furnitures and rooms. To add support for additional furnitures, we simply expand our parser to have more division and level nodes. The configuration tree will grow in-depth. On the other hand, adding support for additional room type, such as dining room and living room, is difficult. For example, the way to divide functional spaces of a living room or a dining room is very different from that of a bedroom. Dining room usually has a table in the middle and chairs around the table. "Split" operations are not the best choice in dividing a dining room space. This means that in order to support additional room types, we essentially need a new parser and division algorithms.
(3) Implement guided-search algorithms.
(4) Extend configuration trees to support multiple children. This is useful if we want to "group" furnitures together. For example, we may allow "sleep_area" to have three children: bed, bedside table, and chair. Then instead of subdividing the "sleep_area", the application will put all the three furnitures into one area. The advantage of this approach is that the arrangement of furnitures will appear to be less "rigid" due to the removal of "split" operations.
References
[1] http://mydeco.com/rooms/planner/[2] http://www.homedesignersoftware.com/interior/
[3] M. Lipp, P. Wonka, and M. Wimmer. Interactive visual editing of grammars for procedural architecture. In Proceedings of ACM SIGGRAPH 2008 / ACM Transactions on Graphics, volume 27. ACM Press, 2008.
[4] P. Wonka, M. Wimmer, F. Sillion, and W. Ribarsky. Instant architecture. In Proceedings of ACM SIGGRAPH 2003 / ACM Transactions on Graphics, volume 22, pages 669-677. ACM Press, July 2003.
[5] P. Muller, P. Wonka, S. Haegle, A. Ulmer, and L. Van Gool. Procedural Modeling of Buildings. In Proceedings of ACM SIGGRAPH 2006/ACM Transactions on Graphics, ACM Press, New York, NY, USA, vol. 25, 614-623.