# Concealed Conduit Routing in Building Slabs
## 2 Materials and Methods
### Workspace Representation
#### 2.1.1 The Top-level Representation  
The top level of the hierarchical representation is a weighted graph \(G\), which contains a vertex set \(V\) and an edge set \(E\), i.e., \(G=\{V,E\}\). We regard the slabs of the target building as vertices and keep them in \(V\). Then, we check the adjacency relations among the slabs to create \(E\). If two slabs are adjacent by sharing a beam or a column, then an edge is produced between them. This edge is associated with a positive weight.  
Assuming that these two slabs are \(S_{1}\) and \(S_{2}\), their centers are \(C_{1}\) and \(C_{2}\), and the edge connecting \(S_{1}\) and \(S_{2}\) is \(E_{12}\), then the weight of \(E_{12}\) is decided as follows:  
1. If \(S_{1}\) and \(S_{2}\) are coplanar, the edge weight is equal to the Manhattan distance between \(C_{1}\) and \(C_{2}\).
2. Otherwise, the edge weight is set to 1.5 times the Manhattan distance between \(C_{1}\) and \(C_{2}\).  
The weight of \(E_{12}\) approximates the shortest path length from \(C_{1}\) to \(C_{2}\). If \(S_{1}\) and \(S_{2}\) are coplanar, a path from \(C_{1}\) to \(C_{2}\) contains no bend, and thus the weight of \(E_{12}\) is set to the Manhattan distance between \(C_{1}\) and \(C_{2}\). On the other hand, if \(S_{1}\) and \(S_{2}\) are not coplanar, this path must make a 90-degree turn inside a beam or a column. In this situation, we increase the edge weight to reflect the existence of the bend and give a penalty to the path. By adopting these two principles, we hope that the pipe path will make fewer turns and contain longer straight segments.  
Figure 4 shows an example of the top-level representation. The left part contains a simple building composed of six slabs. The top-level representation of the simple building is shown in the right part. There are six vertices in the graph. Each vertex has four neighbors since each slab is adjacent to four slabs in this case. All the slabs are not coplanar. Thus, the edge weights are equal to 1.5 times the Manhattan distances of the centers of the neighboring slabs.  
* Usage and limitation of the top-level representation Graph \(G\) stores the connectivity and distances between the slabs. It also implicitly records the sizes of the slabs and their co-planarity relations. If we compute the shortest  
Figure 4: Top-level representation of a simple building: (**a**) The building, (**b**) the weighted graph of the top-level representation (the weights are not revealed).  
Figure 3: The framework of a building is composed of beams, columns, and slabs. The red, green and blue lines represent the \(x\)-, \(y\)- and \(z\)-axes.  
path from slab \(S_{a}\) to slab \(S_{b}\), this path will prefer small and coplanar slabs because of the algorithm employed for computing the path and the way in which we define the edge weights. Graph \(G\) can be used to produce the target pipes only if all the terminals reside at the slab centers. However, the terminals of the target pipes could be at any position in the slabs. The pipes created upon \(G\) cannot correctly connect them. Secondly, there are openings in the slabs, the target pipes must bypass these obstacles. Thirdly, the target pipes must be buried inside the slabs at a safe distance from the surfaces of the slabs. Graph \(G\) does not record depth information about the workspace. These issues imply that the information stored in \(G\) is not enough for routing the target pipes, and hence a finer representation of the workspace is needed for the pipe-routing process.