“Computational network design from functional specifications” by Peng, Mitra, Yang, Bao, Fink, et al. …
Conference:
Type:
Title:
- Computational network design from functional specifications
Session/Category Title: PROCEDURAL MODELING
Presenter(s)/Author(s):
Moderator(s):
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.
References:
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
