Efficient texture synthesis using strict Wang Tiles

Wang Tiles are constructed from four texture samples, arranged so they can always match a choice of other tiles at two edges. Because they are precomputed, Wang Tiles are a very efficient way to generate textures on the fly. But matching problems occur within tiles and at the corners of adjacent tiles. By replacing the edge-matching texture samples with a new sample in the center of the tile, and using the graph cut path-finding algorithm, we overcome these problems and introduce additional texture diversity. Our s-Wang Tiles are a stricter interpretation of the original Wang Tile design, and our tile set is also smaller than that required by ω-Tiles: only eight different tiles are required for a non-repetitive titling.     

The 4-way deterministic tiling problem is undecidable

It is shown that the (infinite) tiling problem by Wang tiles is undecidable even if the given tile set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any two adjacent edges. The reduction is done from the Turing machine halting problem and uses the aperiodic tile set of Kari and Papasoglu.     

Polyominoes simulating arbitrary-neighborhood zippers and tilings

This paper provides a bridge between the classical tiling theory and the complex-neighborhood self-assembling situations that exist in practice.The neighborhood of a position in the plane is the set of coordinates which are considered adjacent to it. This includes classical neighborhoods of size four, as well as arbitrarily complex neighborhoods. A generalized tile system consists of a set of tiles, a neighborhood, and a relation which dictates which are the “admissible” neighboring tiles of a given tile. Thus, in correctly formed assemblies, tiles are assigned positions of the plane in accordance with this relation.We prove that any validly tiled path defined in a given but arbitrary neighborhood (a zipper) can be simulated by a simple “ribbon” of microtiles. A ribbon is a special kind of polyomino, consisting of a non-self-crossing sequence of tiles on the plane, in which successive tiles stick along their adjacent edge.Finally, we extend this construction to the case of traditional tilings, proving that we can simulate arbitrary-neighborhood tilings by simple-neighborhood tilings, while preserving some of their essential properties.     

Polyomino-safe DNA self-assembly via block replacement

The standard abstract model for analyzing DNA self-assembly, aTAM, assumes that single tiles attach one by one to a larger structure. In practice, tiles may attach to each other forming structures called polyominoes and then attach to the assembly using bonds from multiple tiles. Such polyominoes may cause errors in systems designed with only aTAM in mind. In this paper, we first present a formal definition of when one tile system is a “block replacement” of another. Then we present a block replacement scheme for making any system that admits non-trivial block replacement polyomino-safe. In addition, we present a smaller block replacement scheme that makes the Chinese Remainder counter polyomino-safe and prove that the question of whether a system is polyomino-safe (or other similar properties) is undecidable. Finally, we show that applying our polyomino-safe system produces self-healing systems when applied to most self-healing systems.     

Efficient paper mosaic rendering on mobile devices based on position-based tiling

According to the growth of mobile technology, people experience high-performance mobile devices. In this environment, processing in real-time is required for mobile application. For colored paper mosaic application on mobile devices, the problem regarding speed must be solved while maintaining high-quality. In this paper, we propose an accelerated method that generates tiles based on their position. We locate tiles by considering the edges of the image and the shapes of neighbor tiles. The shape of the tiles is determined based on the position of each tile. In addition, we display the generation process of a result for our method be seemed real-time method. In here, we propose an ordering method that is similar to the ordering method of humans by considering color, edge, distance and direction.     

Staged self-assembly: nanomanufacture of arbitrary shapes with <Emphasis Type="Italic">O</Emphasis>(1) glues

We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and performance measures are motivated by a practical nanofabrication scenario through protein-based bioengineering. Staging allows us to break through the traditional lower bounds in tile self-assembly by encoding the shape in the staging algorithm instead of the tiles. All of our results are based on the practical assumption that only a constant number of glues, and thus only a constant number of tiles, can be engineered. Under this assumption, traditional tile self-assembly cannot even manufacture an n × n square; in contrast, we show how staged assembly in theory enables manufacture of arbitrary shapes in a variety of precise formulations of the model.

Combining self-healing and proofreading in self-assembly

Molecular self-assembly is a promising approach to bottom-up fabrication of complex structures. A major impediment to the practical use of self-assembly to create complex structures is the high rate of error under existing experimental conditions. Recent theoretical work on algorithmic self-assembly has shown that under a realistic model of tile addition and detachment, error correcting tile sets are possible that can recover from the attachment of incorrect tiles during the assembly process. An orthogonal type of error correction was recently considered as well: whether damage to a completed structure can be repaired. It was shown that such self-healing tile sets are possible. However, these tile sets are not robust to the incorporation of incorrect tiles. It remained an open question whether it is possible to create tile sets that can simultaneously resist wholesale removal of tiles and the incorporation of incorrect ones. Here we present a method for converting a tile set producing a pattern on the quarter plane into a tile set that makes the same pattern (at a larger scale) but is able to withstand both of these types of errors.

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

Tile-Packing Tomography Is \mathbb{NP}-hard

Discrete tomography deals with reconstructing finite spatial objects from their projections. The objects we study in this paper are called tilings or tile-packings, and they consist of a number of disjoint copies of a fixed tile, where a tile is defined as a connected set of grid points. A row projection specifies how many grid points are covered by tiles in a given row; column projections are defined analogously. For a fixed tile, is it possible to reconstruct its tilings from their projections in polynomial time? It is known that the answer to this question is affirmative if the tile is a bar (its width or height is 1), while for some other types of tiles $\mathbb {NP}$ -hardness results have been shown in the literature. In this paper we present a complete solution to this question by showing that the problem remains $\mathbb {NP}$ -hard for all tiles other than bars.     

Generating Stochastic Wall Patterns On‐the‐fly with Wang Tiles

The game and movie industries always face the challenge of reproducing materials. This problem is tackled by combining illumination models and various textures (painted or procedural patterns). Generating stochastic wall patterns is crucial in the creation of a wide range of backgrounds (castles, temples, ruins…). A specific Wang tile set was introduced previously to tackle this problem, in an iterative fashion. However, long lines may appear as visual artifacts. We use this tile set in a new on‐the‐fly procedure to generate stochastic wall patterns. For this purpose, we introduce specific hash functions implementing a constrained Wang tiling. This technique makes possible the generation of boundless textures while giving control over the maximum line length. The algorithm is simple and easy to implement, and the wall structure we get from the tiles allows to achieve visuals that reproduce all the small details of artist painted walls.     

Semi‐Stochastic Tilings for Example‐Based Texture Synthesis

We investigate semi‐stochastic tilings based on Wang or corner tiles for the real‐time synthesis of example‐based textures. In particular, we propose two new tiling approaches: (1) to replace stochastic tilings with pseudo‐random tilings based on the Halton low‐discrepancy sequence, and (2) to allow the controllable generation of tilings based on a user‐provided probability distribution. Our first method prevents local repetition of texture content as common with stochastic approaches and yields better results with smaller sets of utilized tiles. Our second method allows to directly influence the synthesis result which—in combination with an enhanced tile construction method that merges multiple source textures—extends synthesis tasks to globally‐varying textures. We show that both methods can be implemented very efficiently in connection with tile‐based texture mapping and also present a general rule that allows to significantly reduce resulting tile sets.     

移动设备上基于Wang tiles的双向纹理合成算法

为了在移动设备上实现纹理合成,首先在总结了PC平台上纹理合成技术特点的基础上,指出基于Wang tiles的纹理合成适合在资源受限的移动平台上实现;然后通过深入分析Cohen随机贴片算法中的不足,提出了改进的基于Wang tiles的双向纹理合成新算法,即包括样本纹理子图的选取、片填充和基于双向扫描的贴片算法。该算法不仅扩大了最佳切割线的搜索范围和增加了贴片的随机性,同时也减少了计算和存储需求。实验结果表明,该算法不仅能够运行在移动设备上,而且与随机贴片算法相比,还提高了非周期性视觉效果。     

Efficient Processing of Continual Range Queries for Location-Aware Mobile Services

Efficient processing of continual range queries is important in providing location-aware mobile services. In this paper, we study a new main memory-based approach to indexing continual range queries to support location-aware mobile services. The query index is used to quickly answer the following question continually: “Which moving objects are currently located inside the boundaries of individual queries?” We present a covering tile-based (COVET) query index. A set of virtual tiles are predefined, each with a unique ID. One or more of the virtual tiles are used to strictly cover the region defined by an individual range query. The query ID is inserted into the ID lists associated with the covering tiles. These covering tiles touch each other only at the edges. A COVET index maintains a mapping between a covering tile and all the queries that contain that tile. For any object position, search is conducted indirectly via the covering tiles. More importantly, a COVET-based query index allows query evaluation to take advantage of incremental changes in object locations. Computation can be saved for those objects that have not moved outside the boundaries of covering tiles. Simulations are conducted to evaluate the effectiveness of the COVET index and compare virtual tiles of different shapes and sizes.     

Automatic partitioning of parallel loops with parallelepiped-shapedtiles

In this paper, an efficient algorithm to implement loop partitioning is introduced and evaluated. We start from results of Agarwal et al. (1995) whose aim is to minimize the number of accessed data throughout the computation of a tile; this number is called the cumulative footprint of the tile. We improve these results along several directions. First, we derive a new formulation of the cumulative footprint, allowing for an analytical solution of the optimization problem stated by Agarwal et al.. Second, we deal with arbitrary parallelepiped-shaped tiles, as opposed to rectangular tiles. We design an efficient heuristic to determine the optimal tile shape in this general setting and we show its usefulness using both examples of Agarwal et al. and a large collection of randomly generated data     

Negative Interactions in Irreversible Self-assembly

This paper explores the use of negative (i.e., repulsive) interactions in the abstract Tile Assembly Model defined by Winfree. Winfree in his Ph.D. thesis postulated negative interactions to be physically plausible, and Reif, Sahu, and Yin studied them in the context of reversible attachment operations. We investigate the power of negative interactions with irreversible attachments, and we achieve two main results. Our first result is an impossibility theorem: after t steps of assembly, Ω(t) tiles will be forever bound to an assembly, unable to detach. Thus negative glue strengths do not afford unlimited power to reuse tiles. Our second result is a positive one: we construct a set of tiles that can simulate an s-space-bounded, t-time-bounded Turing machine, while ensuring that no intermediate assembly grows larger than O(s), rather than O(s?t) as required by the standard Turing machine simulation with tiles. In addition to the space-bounded Turing machine simulation, we show another example application of negative glues: reducing the number of tile types required to assemble “thin” (n×o(logn/loglogn)) rectangles.     

Optimal semi-oblique tiling

For 2D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time on a parallel machine. We consider uniform dependency computations tiled so that (at least) one of the tile boundaries is parallel to the domain boundaries. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary. Our results are based on the BSP model, which assures the portability of the results. Our predictions are justified on a sequence global alignment problem specialized to similar sequences using Fickett's k-band algorithm, for which our optimal semi-oblique tiling yields an improvement of a factor of 2.5 over orthogonal tiling. Our optimal solution requires a block-cyclic distribution of tiles to processors. The best one can obtain with only block distribution (as many authors require) is three times slower. Furthermore, our best running time is within 10 percent of the "predicted theoretical peak" performance of the machine!.     

基于构型风格的新疆民族织物图案自动生成

以新疆民族织物图案为对象,通过分析图案特点,发现具有某些元素有规 律地重复排列组合的特征,分解这些元素找出基本构型,归纳为六边形结构堆砌、砖形结构 堆砌、田字结构堆砌、三角结构堆砌、菱形结构堆砌等。用户在创作时首先选择某一种基本 构型,然后设计或嵌入适当的纹样基元到初始构型中,最后通过折叠或旋转延展生成一幅精 美的对称图案,文中原型系统可以广泛应用于新疆民族织物图案设计、广告以及服装设计等 领域。     

基于联锁分块的大规模地形建模方法研究

针对已有MRLoD算法生成的地形=三角形网不稳定等缺点,提出了一种新的基于联锁分块的大规模地形建模方法,在对地形进行分块调度的基础上通过预先建立分块模板和分块联锁模板,渲染时动态匹配各模板建立平滑完整的分块模型,在分块调度及附加计算策略下,拼接各分块以完成整块地形的多分辨率建模,并以高效的方式将模型数据传人渲染硬件.实验表明,在满足了精度要求的同时提高了模型的稳定性,有效减少了实时计算量,在渲染效率上取得了令人满意的结果,能够满足用户对大规模地形的实时漫游的要求.     

基于MPI的大规模栅格影像并行瓦片化算法

当前主流GIS软件以及互联网地图应用在WebGIS（网络地理信息系统）解决方案中都广泛采用地图切片（又称瓦片）,切片处理服务是实现影像在WebGIS上快速无缝浏览的关键技术。针对目前传统算法以及商业GIS软件在大数据量栅格影像快速瓦片化方面的不足,提出一种名为ParaTile的高效栅格影像快速瓦片化方法,ParaTile基于MPI共享外存的并行技术,利用多进程对原始栅格影像进行数据划分,每个进程对其所划分的区域进行独立读写和计算,而后再按照TMS或者Google Tile定义的标准将瓦片进行编码输出。实验采用不同级别大小的遥感影像进行测试,结果表明ParaTile在面对不同规模的数据时,无论从速度还是算法稳定性上都较现有算法和工具具有显著优势,特别是当数据量越大时,这种优势愈加明显。