We propose an algorithm that generates networks for design scenarios like mid-scale urban street layouts (a-c) and floorplans for office spaces (d). The user simply specifies an input mesh as the problem domain along with high-level specifications of the functions of the generated network. Examples include preference for interior-to-boundary traffic (a) or interior-to-interior traffic (b), networks with specified destinations (i.e., sinks) on the boundary (c,d) and local feature control, such as reducing T-junctions (b) or forbidding dead-ends (c). For (a-c), the average travel time (distance) for interior-to-boundary traffic as estimated by the traffic simulator SUMO is indicated in green.

---

Abstract

Connectivity and layout of underlying networks largely determine agent behavior and usage in many environments. For example, transportation networks determine the flow of traffic in a neighborhood, whereas building floorplans determine the flow of people in a workspace. Designing such networks from scratch is challenging as even local network changes can have large global effects. We investigate how to computationally create networks starting from only high-level functional specifications. Such specifications can be in the form of network density, travel time versus network length, traffic type, destination location, etc. We propose an integer programming-based approach that guarantees that the resultant networks are valid by fulfilling all the specified hard constraints and that they score favorably in terms of the objective function. We evaluate our algorithm in two different design settings, street layout and floorplans to demonstrate that diverse networks can emerge purely from high-level functional specifications.

---

Results

Example results. Sink vertices are marked in red. The coverage range is two edges wide. The distance values of active half-edges are colored (see legends for color ranges). Boundary edges are excluded from the calculations. We forbid deadends and edges that are too close to each other. (a) to (c): A typical urban layout scenario such that all boundary vertices are sinks. The first two use different weights to optimize for (a) numbers of network edges and (b) sum of distance values. Note that we do not specifically constrain the maximum distance values. (c): A result that also optimizes for distance values but with the point-to-point constraint enabled (sampled vertices are marked in yellow). (d): We now constrain a boundary vertex (top middle) to be the sole sink. (e) to (g): A typical floorplan scenario such that a few inner vertices are sinks (e.g., elevators). Similarly, they differ by different relative weights and whether the point-to-point constraint is enabled.

Pipeline. For each sub-region, as determined by the input major roads, we generate layouts in three levels of decreasing coverage ranges. For each level, a rough street network is first generated by the IP-based approach (shown in gray). Afterwards, the geometry of the generated street network is refined by a smoothing process. Dead-ends are typically allowed only at the last level.

Optimization results with changing λ_L (to minimize network lengths) versus λ_D (to minimize travel distances). A larger λ_L leads to shorter network lengths but longer travel distances, while a larger λ_D leads to the opposite.

Diverse street layouts resulting from different functional specifications. The first two layouts are optimized for (a) minimal network lengths and (b) minimal travel distances to the boundary, using different specifications of the optimization weights. The travel distances are shown in the bottom-left corners. (c) A layout with a single exit on the left. We also prefer a tree-like structure for this case, which is realized by allowing deadends on the second (collector roads) level. (d) A layout that encourages through-traffic in the vertical direction. This is realized by enforcing a shortest path connecting the two user-specified vertices (green) without inner branches on the second level. Note that through-traffic in other directions (e.g., horizontal) is implicitly discouraged. (e) A network that better supports interior-to-interior traffic, realized by the point-to-point constraint with a user-specified partition.

@article{peng2016funcNetwork,
 title = {Computational Network Design from Functional Specifications},
 author = {Peng, Chi-Han and Yang, Yong-Liang and Bao, Fan and 
            Fink, Daniel and Yan, Dong-Ming and Wonka, Peter and Mitra, N. J.},
 journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2016)},
 volume = {35},
 issue = {4},
 pages = {},
 year = {2016},
}