Game level layout from design specification

The design of video game environments, or levels, aims to control gameplay by steering the player through a sequence of designer‐controlled steps, while simultaneously providing a visually engaging experience. Traditionally these levels are painstakingly designed by hand, often from pre‐existing building blocks, or space templates. In this paper, we propose an algorithmic approach for automatically laying out game levels from user‐specified blocks. Our method allows designers to retain control of the gameplay flow via user‐specified level connectivity graphs, while relieving them from the tedious task of manually assembling the building blocks into a valid, plausible layout. Our method produces sequences of diverse layouts for the same input connectivity, allowing for repeated replay of a given level within a visually different, new environment. We support complex graph connectivities and various building block shapes, and are able to compute complex layouts in seconds. The two key components of our algorithm are the use of configuration spaces defining feasible relative positions of building blocks within a layout and a graph‐decomposition based layout strategy that leverages graph connectivity to speed up convergence and avoid local minima. Together these two tools quickly steer the solution toward feasible layouts. We demonstrate our method on a variety of real‐life inputs, and generate appealing layouts conforming to user specifications.     

Interactive Modeling of City Layouts using Layers of Procedural Content

In this paper, we present new solutions for the interactive modeling of city layouts that combine the power of procedural modeling with the flexibility of manual modeling. Procedural modeling enables us to quickly generate large city layouts, while manual modeling allows us to hand‐craft every aspect of a city. We introduce transformation and merging operators for both topology preserving and topology changing transformations based on graph cuts. In combination with a layering system, this allows intuitive manipulation of urban layouts using operations such as drag and drop, translation, rotation etc. In contrast to previous work, these operations always generate valid, i.e., intersection‐free layouts. Furthermore, we introduce anchored assignments to make sure that modifications are persistent even if the whole urban layout is regenerated.     

Optimizing layout using spatial quality metrics and user preferences

Computational design is one of the most common tasks of immersive computer graphics projects, such as games, virtual reality and special effects. Layout planning is a challenging phase of architectural design, which requires optimization across several conflicting criteria. We present an interactive layout solver that assists designers in layout planning by recommending personalized space arrangements based on architectural guidelines and user preferences. Initialized by the designer’s high-level requirements, an interactive evolutionary algorithm is used to converge on an ideal layout by exploring the space of potential solutions. The major contributions of our proposed approach are addressing subjective aspects of the design to generate personalized layouts; and the development of a genetic algorithm with a multi-parental recombination method that improves the chance of generating higher quality offspring. We demonstrate the ability of our method to generate feasible floor plans which are satisfactory, based on spatial quality metrics and designer’s taste. The results show that the presented framework can measurably decrease planning complexity by producing layouts which exhibit characteristics of human-made design.     

Tracing Field‐Coherent Quad Layouts

Given a cross field over a triangulated surface we present a practical and robust method to compute a field aligned coarse quad layout over the surface. The method works directly on a triangle mesh without requiring any parametrization and it is based on a new technique for tracing field‐coherent geodesic paths directly on a triangle mesh, and on a new relaxed formulation of a binary LP problem, which allows us to extract both conforming quad layouts and coarser layouts containing t‐junctions. Our method is easy to implement, very robust, and, being directly based on the input cross field, it is able to generate better aligned layouts, even with complicated fields containing many singularities. We show results on a number of datasets and comparisons with state‐of‐the‐art methods.     

A linear algebra framework for automatic determination of optimaldata layouts

This paper presents a data layout optimization technique for sequential and parallel programs based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines suitable memory layouts that can be expressed by hyperplanes for each array that is referenced. We discuss the cases where data transformations are preferable to loop transformations and show that under certain conditions a loop nest can be optimized for perfect spatial locality by using data transformations. We argue that data transformations can also optimize spatial locality for some arrays without distorting temporal/spatial locality exhibited by others. We divide the problem of optimizing data layout into two independent subproblems: 1) determining optimal static data layouts, and 2) determining data transformation matrices to implement the optimal layouts. By postponing the determination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts. We then present an algorithm that considers optimizing parallelism and spatial locality simultaneously. Our results on eight programs on two distributed shared-memory multiprocessors, the Convex Exemplar SPP-2000 and the SGI Origin 2000, show that the layout optimizations are effective in optimizing spatial locality and parallelism     

A Comparison of User-Generated and Automatic Graph Layouts

The research presented in this paper compares user-generated and automatic graph layouts. Following the methods suggested by van Ham et al. (2008), a group of users generated graph layouts using both multi-touch interaction on a tabletop display and mouse interaction on a desktop computer. Users were asked to optimize their layout for aesthetics and analytical tasks with a social network. We discuss characteristics of the user-generated layouts and interaction methods employed by users in this process. We then report on a web-based study to compare these layouts with the output of popular automatic layout algorithms. Our results demonstrate that the best of the user-generated layouts performed as well as or better than the physics-based layout. Orthogonal and circular automatic layouts were found to be considerably less effective than either the physics-based layout or the best of the user-generated layouts. We highlight several attributes of the various layouts that led to high accuracy and improved task completion time, as well as aspects in which traditional automatic layout methods were unsuccessful for our tasks.     

Generating Synthetic Space Allocation Probability Layouts Based on Trained Conditional-GANs

In this paper, a data-driven generative method is applied to generate synthetic space allocation probability layout. This generated layout could be helpful in the early stage of an architectural design. For this task, a specific training dataset is generated which is used to train the cGAN model. The training dataset consists of 300 existing apartment layouts which are coloured in a set of low feature representation. The cGAN model is trained with this dataset and the trained model is evaluated based on the quality of its generated layouts regarding the five pre-defined topological and geometrical benchmarks.     

Perfect Matching Quad Layouts for Manifold Meshes

This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.     

Route Visualization Using Detail Lenses

We present a method designed to address some limitations of typical route map displays of driving directions. The main goal of our system is to generate a printable version of a route map that shows the overview and detail views of the route within a single, consistent visual frame. Our proposed visualization provides a more intuitive spatial context than a simple list of turns. We present a novel multifocus technique to achieve this goal, where the foci are defined by points of interest (POI) along the route. A detail lens that encapsulates the POI at a finer geospatial scale is created for each focus. The lenses are laid out on the map to avoid occlusion with the route and each other, and to optimally utilize the free space around the route. We define a set of layout metrics to evaluate the quality of a lens layout for a given route map visualization. We compare standard lens layout methods to our proposed method and demonstrate the effectiveness of our method in generating aesthetically pleasing layouts. Finally, we perform a user study to evaluate the effectiveness of our layout choices.     

Quasidynamic layout optimizations for improving data locality

Compiler-directed locality optimization techniques are effective in reducing the number of cycles spent in off-chip memory accesses. Recently, methods have been developed that transform memory layouts of data structures at compile-time to improve spatial locality of nested loops beyond current control-centric (loop nest-based) optimizations. Most of these data-centric transformations use a single static (program-wide) memory layout for each array. A disadvantage of these static layout-based locality enhancement strategies is that they might fail to optimize codes that manipulate arrays, which demand different layouts in different parts of the code. We introduce a new approach, which extends current static layout optimization techniques by associating different memory layouts with the same array in different parts of the code. We call this strategy "quasidynamic layout optimization." In this strategy, the compiler determines memory layouts (for different parts of the code) at compile time, but layout conversions occur at runtime. We show that the possibility of dynamically changing memory layouts during the course of execution adds a new dimension to the data locality optimization problem. Our strategy employs a static layout optimizer module as a building block and, by repeatedly invoking it for different parts of the code, it checks whether runtime layout modifications bring additional benefits beyond static optimization. Our experiments indicate significant improvements in execution time over static layout-based locality enhancing techniques.     

Banner layout retargeting with hierarchical reinforcement learning and variational autoencoder

In many advertising areas, banners are often generated with different display sizes, so designers have to make huge efforts to retarget their designs to each size. Automating such retargeting process can greatly save time for designers and let them put creativity on new ads. This paper proposes a hierarchical reinforcement learning-based (HRL-based) method and a variational autoencoder-based (VAE-based) method by treating the automated banner retargeting problem as a layout retargeting task. The HRL and VAE models are trained separately to learn the scaling and positioning policy of the design elements from an original (base) layout. Hence, the proposed method can generate appropriate layouts for different target banner sizes. Meanwhile, evaluation metrics are proposed to assess the quality of generated layouts and are also reward conditions during the training process. To evaluate performances of the two models, SOTA methods such as Non-linear Inverse Optimization (NIO), Triangle Interpolation (TI), and Layout GAN (LGAN) are implemented and compared. Experimental results show that both HRL- and VAE-based methods retarget design layouts effectively, and the VAE model achieves better performance than the HRL model.

     

Composition-based Cache simulation for structure reorganization

Finding the best data layout has been an ultimate goal of memory optimization. Even with data access profile, heuristic algorithms are needed to reorganize data layout for better locality. The best layout could be found by running the given application with all possible data layouts and selecting the best performing layout. This approach, however, can incur too much overhead, particulary when the number of possible layouts are too many. In this paper, we present a composition-based cache simulation for structure reorganization. Instead of running all possible layouts, we simulate only the primary subsets of layouts and compose the cache misses for all layouts by summing up the cache misses of component subsets. Our experiment with the composition-based cache simulation shows that the differences in the cache misses are within 10% of the full cache simulation for 4-way and 8-way set associative caches. In addition to the cache miss estimation, our heuristic algorithm takes account of the extra instruction overhead incurred by structure reorganization. Our experiment with several structure intensive benchmarks shows the 37% reduction in the L1D read misses and the 28% reduction in the L2 read misses. As a result, the execution times are also reduced by 19% on average.     

城市建筑点云的自适应分割方法

自动地提取城市建筑点云数据中的高层次结构是城市数字化等应用的重要基础步骤.通过提出"自适应分割"的概念来自动地获取三维城市建筑点云的一种灵活、层次化的结构表示.由于城市建筑的单元分布大都呈一种级联或者交错的形式,与之前采用全局规则格点进行分析的方法不同,文中采用一种自适应的方法对建筑点云进行分析;也可将自适应分割的概念用于建筑图像的分析上.最后给出了在不同类型的建筑点云和图像进行分析的结果以及一些相关的应用.     

Interactive Reconfiguration of Urban Layouts

The layout of an urban space is a complex collection of man-made structures arranged in parcels, city blocks, and neighborhoods. An editor for interactively reconfiguring city layouts exploits geographical information system (GIS) data and provides tools to expand, scale, replace, and move parcels and blocks while efficiently exploiting their connectivity and zoning. The ability to create, extend, and change a model of a large-scale urban environment is useful for a variety of computer graphics applications. For example, it lets urban planning applications simulate changes to city layouts or newly proposed neighborhoods, create hypothetical views of an urban area after applying development and growth algorithms, and show architects the results of using common building blocks to design a new city layout.     

MIQP‐based Layout Design for Building Interiors

We propose a hierarchical framework for the generation of building interiors. Our solution is based on a mixed integer quadratic programming (MIQP) formulation. We parametrize a layout by polygons that are further decomposed into small rectangles. We identify important high‐level constraints, such as room size, room position, room adjacency, and the outline of the building, and formulate them in a way that is compatible with MIQP and the problem parametrization. We also propose a hierarchical framework to improve the scalability of the approach. We demonstrate that our algorithm can be used for residential building layouts and can be scaled up to large layouts such as office buildings, shopping malls, and supermarkets. We show that our method is faster by multiple orders of magnitude than previous methods.     

A CSP technique-based interactive control panel layout

An interactive and iterative control panel layout method based on the constraint satisfaction problem (CSP) technique was developed to generate an ergonomically sound panel design. This control panel layout method attempts to incorporate a variety of relevant ergonomic principles and design constraints, and generate an optimal or, at least, a ‘satisfactory’ solution through an efficient search algorithm. The problem of seeking an ergonomically sound panel design should be viewed as a multi-criteria problem, and most of the design objectives should be understood as constraints. Hence, a CSP technique was employed in this study for dealing with the multi-constraints layout problem. The efficient search algorithm using ‘preprocess’ and ‘look_ahead’ procedures was developed to handle the vast amount of computational effort. In order to apply the CSP technique to the panel layout procedure, the ergonomic principles such as spatial compatibility, frequency-of-use, importance, functional grouping, and sequence-of-use were formalized as CSP terms. The effectiveness of the proposed panel layout method was evaluated by example problems, and the results clearly showed that the generated layouts properly considered various ergonomic design principles.     

Procedural modeling of urban zone by optimization

Procedural modeling technology may be applied for constructing a large‐scale urban scene. Most of the previous studies have exploited a grammar‐based modeling method to generate models. Nevertheless, we formulate the urban planning as a constrained layout optimization problem, propose an algorithm to solve the problem, and procedurally generate models of the urban zone. It produces an extensive urban virtual environment for computer games and simulations at low cost. We optimize a cost function to distribute buildings and roads subject to some urban planning constraints. We employ particle swarm optimization and two‐step path planning to find the optimal solution, which is further interpreted as the 2D blueprint of the urban zone. During the optimization, we adopt the spatial pattern tree structure to reduce the combinational search space greatly. 3D city models in large scale are then assembled according to the 2D blueprints. Experimental results prove that our method can efficiently produce the virtual urban scene similar to that designed by urban planners. Copyright © 2008 John Wiley & Sons, Ltd.     

Cognitive Strategies for the Visual Search of Hierarchical Computer Displays

This article investigates the cognitive strategies that people use to search computer displays. Several different visual layouts are examined: unlabeled layouts that contain multiple groups of items but no group headings, labeled layouts in which items are grouped and each group has a useful heading, and a target-only layout that contains just one item. A number of plausible strategies were proposed for each layout. Each strategy was programmed into the EPIC cognitive architecture, producing models that simulate the human visual-perceptual, oculomotor, and cognitive processing required for the task. The models generate search time predictions. For unlabeled layouts, the mean layout search times are predicted by a purely random search strategy, and the more detailed positional search times are predicted by a noisy systematic strategy. The labeled layout search times are predicted by a hierarchical strategy in which first the group labels are systematically searched, and then the contents of the target group. The target-only layout search times are predicted by a strategy in which the eyes move directly to the sudden appearance of the target. The models demonstrate that human visual search performance can be explained largely in terms of the cognitive strategy that is used to coordinate the relevant perceptual and motor processes, a clear and useful visual hierarchy triggers a fundamentally different visual search strategy and effectively gives the user greater control over the visual navigation, and cognitive strategies will be an important component of a predictive visual search tool. The models provide insights pertaining to the visual-perceptual and oculomotor processes involved in visual search and contribute to the science base needed for predictive interface analysis.