“Computational network design from functional specifications” by Peng, Mitra, Yang, Bao, Fink, et al. …

  • ©Chi-Han Peng, Niloy J. Mitra, Yongliang Yang, Fan Bao, Daniel Fink, Dongming Yan, and Peter Wonka



Session Title:



    Computational network design from functional specifications




    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.


    1. AlHalawani, S., and Mitra, N. J. 2015. Advances in Visual Computing: ISVC 2015, Part II. ch. Congestion-Aware Warehouse Flow Analysis and Optimization, 702–711.Google Scholar
    2. AlHalawani, S., Yang, Y.-L., Liu, H., and Mitra, N. J. 2013. Interactive facades: Analysis and synthesis of semi-regular facades. Computer Graphics Forum (Proc. EUROGRAPHICS) 32, 2pt2, 215–224.Google Scholar
    3. AlHalawani, S., Yang, Y.-L., Wonka, P., and Mitra, N. J. 2014. What makes London work like London. Computer Graphics Forum (Proc. SGP) 33.Google Scholar
    4. Aliaga, D., Vanegas, C., and Benes, B. 2008. Interactive Example-Based Urban Layout Synthesis. ACM TOG (Siggraph Asia) 27, 5. Google ScholarDigital Library
    5. Bao, F., Yan, D.-M., Mitra, N. J., and Wonka, P. 2013. Generating and exploring good building layouts. ACM TOG (Siggraph) 32, 4. Google ScholarDigital Library
    6. Baswana, S., and Sen, S. 2007. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 4, 532–563. Google ScholarDigital Library
    7. Board, T. R. 2010. Highway Capacity Manual. Transportation Research Board.Google Scholar
    8. Chen, G., Esch, G., Wonka, P., Müller, P., and Zhang, E. 2008. Interactive procedural street modeling. ACM TOG (Siggraph) 27, 3, 103:1–9. Google ScholarDigital Library
    9. Deussen, O., Hanrahan, P., Lintermann, B., Měch, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modeling and rendering of plant ecosystems. In Proc. ACM SIGGRAPH, 275–286. Google ScholarDigital Library
    10. Galin, E., Peytavie, A., Guérin, E., and Benes, B. 2011. Authoring hierarchical road networks. Computer Graphics Forum 29, 7, 2021–2030.Google ScholarCross Ref
    11. Garcia-Dorado, I., Aliaga, D. G., and Ukkusuri, S. V. 2014. Designing large-scale interactive traffic animations for urban modeling. Computer Graphics Forum (Proc. EUROGRAPHICS) 33, 2, 411–420. Google ScholarDigital Library
    12. Génevaux, J.-D., Galin, E., Guérin, E., Peytavie, A., and Beneš, B. 2013. Terrain generation using procedural models based on hydrology. ACM TOG (Siggraph) 32, 4, 143:1–143:13. Google ScholarDigital Library
    13. Gurobi Optimization, Inc., 2014. Gurobi optimizer reference manual.Google Scholar
    14. Handy, S., Paterson, R., and Butler, K. 2003. Planning for street connectivity: Getting from here to there. In Planning Advisory Service Report.Google Scholar
    15. Kass, M., Witkin, A., and Terzopoulos, D. 1988. Snakes: Active contour models. Int. Journal of Computer Vision 1, 4, 321–331.Google ScholarCross Ref
    16. Koster, A., Kutschka, M., and Raack, C. 2010. Towards robust network design using integer linear programming techniques. In Next Generation Internet (NGI), 2010 6th EURO-NF Conference on, 1–8.Google Scholar
    17. Krajzewicz, D., Erdmann, J., Behrisch, M., and Bieker, L. 2012. Recent development and applications of SUMO – Simulation of Urban MObility. International Journal On Advances in Systems and Measurements 5, 3&4, 128–138.Google Scholar
    18. Liu, H., Yang, Y.-L., AlHalawani, S., and Mitra, N. J. 2013. Constraint-aware interior layout exploration for precast concrete-based buildings. The Visual Computer (CGI Special Issue). Google ScholarDigital Library
    19. Luathep, P., Sumalee, A., Lam, W. H., Li, Z.-C., and Lo, H. K. 2011. Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach. Transportation Research Part B: Methodological 45, 5, 808–827.Google ScholarCross Ref
    20. Ma, C., Vining, N., Lefebvre, S., and Sheffer, A. 2014. Game level layout from design specification. Computer Graphics Forum (Proc. EUROGRAPHICS) 33, 2, 95–104. Google ScholarDigital Library
    21. Maréchal, N., Guérin, E., Galin, E., Merillou, S., and Mrillou, N. 2010. Procedural generation of roads. Computer Graphics Forum 29, 2, 429–438.Google ScholarCross Ref
    22. Marshall, S. 2005. Streets & Pattern. Spon press, New York.Google Scholar
    23. MATSim, 2015. Matsim, http://www.matsim.org/.Google Scholar
    24. Merrell, P., Schkufza, E., and Koltun, V. 2010. Computer-generated residential building layouts. ACM TOG (Siggraph Asia) 29, 6, 181:1–181:12. Google ScholarDigital Library
    25. Meyer, M., and Miller, E. 2000. Urban Transportation Planning. McGraw-Hill.Google Scholar
    26. Miller, C. E., Tucker, A. W., and Zemlin, R. A. 1960. Integer programming formulation of traveling salesman problems. J. ACM 7, 4, 326–329. Google ScholarDigital Library
    27. Nishida, G., Garcia-Dorado, I., and Aliaga, D. G. 2015. Example-driven procedural urban roads. Computer Graphics Forum, 1–14.Google Scholar
    28. Ortzar, J. d. D., and Willumsen, L. 2011. Modelling Transport. Wiley.Google Scholar
    29. Parish, Y. I. H., and Müller, P. 2001. Procedural modeling of cities. In Proc. ACM SIGGRAPH, 301–308. Google ScholarDigital Library
    30. Peng, C.-H., Barton, M., Jiang, C., and Wonka, P. 2014. Exploring quadrangulations. ACM TOG 33, 1, 12:1–12:13. Google ScholarDigital Library
    31. Peng, C.-H., Yang, Y.-L., and Wonka, P. 2014. Computing layouts with deformable templates. ACM TOG (Siggraph) 33, 4, 99:1–99:11. Google ScholarDigital Library
    32. Runions, A., Fuhrer, M., Lane, B., Federl, P., Rolland-Lagan, A.-G., and Prusinkiewicz, P. 2005. Modeling and visualization of leaf venation patterns. ACM TOG (Siggraph) 24, 3, 702–711. Google ScholarDigital Library
    33. Sewall, J., Wilkie, D., Merrell, P., and Lin, M. 2010. Continuum Traffic Simulation. Computer Graphics Forum (Proc. EUROGRAPHICS) 29, 2, 439–448.Google ScholarCross Ref
    34. Sewall, J., Wilkie, D., and Lin, M. C. 2011. Interactive hybrid simulation of large-scale traffic. ACM TOG (Siggraph Asia) 30, 6. Google ScholarDigital Library
    35. Southworth, M., and Ben-Joseph, E. 2003. Streets and the Shaping of Towns and Cities. Island Press, Wasington DC.Google Scholar
    36. Vanegas, C. A., Aliaga, D. G., Beneš, B., and Waddell, P. A. 2009. Interactive design of urban spaces using geometrical and behavioral modeling. ACM TOG (Siggraph Asia) 28, 5. Google ScholarDigital Library
    37. Vanegas, C. A., Garcia-Dorado, I., Aliaga, D. G., Benes, B., and Waddell, P. 2012. Inverse design of urban procedural models. ACM TOG (Siggraph Asia) 31, 6, 168:1–168:11. Google ScholarDigital Library
    38. VISSIM, 2015. http://vision-traffic.ptvgroup.com/.Google Scholar
    39. Wardrop, J. 1952. Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers 1, 2, 325–378.Google ScholarCross Ref
    40. Weber, B., Müller, P., Wonka, P., and Gross, M. H. 2009. Interactive geometric simulation of 4D cities. Computer Graphics Forum (Proc. EUROGRAPHICS) 28, 2, 481–492.Google ScholarCross Ref
    41. Wilkie, D., Sewall, J., and Lin, M. C. 2013. Flow reconstruction for data-driven traffic animation. ACM TOG (Siggraph) 32, 4. Google ScholarDigital Library
    42. Yang, H., and Bell, M. 1998. Models and algorithms for road network design: a review and some new developments. Transport Reviews 18, 3.Google ScholarCross Ref
    43. Yang, Y.-L., Wang, J., Vouga, E., and Wonka, P. 2013. Urban pattern: Layout design by hierarchical domain splitting. ACM TOG (Siggraph Asia). Google ScholarDigital Library
    44. Yu, L.-F., Yeung, S.-K., Tang, C.-K., Terzopoulos, D., Chan, T. F., and Osher, S. 2011. Make it home: Automatic optimization of furniture arrangement. ACM TOG (Siggraph) 30, 4, 86:1–86:11. Google ScholarDigital Library

ACM Digital Library Publication: