5692674
Synthesizing trees by plantons
In this paper, we present a two-level statistical model for characterizing the stochastic and specific nature of trees. At the low level, we define plantons, which are a group of similar organs, to depict tree organ details statistically. At the high level, a set of transitions between plantons is provided to describe the stochastic distribution of organs.Based on such a tree model, we propose a novel tree modeling approach, synthesizing trees by plantons, which are extracted from tree samples. All tree samples are captured from the real world. We have designed a maximum likelihood estimation algorithm to acquire the two-level statistical tree model from single samples or multi- samples. Experimental results show that our new model is capable of synthesizing new trees with similar, yet visually different shapes.
7624538
Variational sphere set approximation for solid objects
We approximate a solid object represented as a triangle mesh by a bounding set of spheres having minimal summed volume outside the object. We show how outside volume for a single sphere can be computed using a simple integration over the object’s triangles. We then minimize the total outside volume over all spheres in the set using a variant of iterative Lloyd clustering that splits the mesh points into sets and bounds each with an outside volume-minimizing sphere. The resulting sphere sets are tighter than those of previous methods. In experiments comparing against a state-of-the-art alternative (adaptive medial axis), our method often requires half as many spheres, or fewer, to obtain the same error, under a variety of error metrics including total outside volume, shadowing fidelity, and proximity measurement.
8634013
Fast, Sub-pixel Antialiased Shadow Maps
Solving aliasing artifacts is an essential problem in shadow mapping approaches. Many works have been proposed, however, most of them focused on removing the texel-level aliasing that results from the limited resolution of shadow maps. Little work has been done to solve the pixel-level shadow aliasing that is produced by the rasterization on the screen plane. In this paper, we propose a fast, sub-pixel antialiased shadowing algorithm to solve the pixel aliasing problem. Our work is based on the alias-free shadow maps, which is capable of computing accurate per-pixel shadow, and only incurs little cost to extend to sub-pixel accuracy. Instead of direct supersampling the screen space, we take facets to approximate pixels in shadow testing. The shadowed area of one facet is rapidly evaluated by projecting blocker geometry onto a supersampled 2D occlusion mask with bitmasks fusion. It provides a sub-pixel occlusion sampling so as to capture fine shadow details and features. Furthermore, we introduce the silhouette mask map that limits visibility evaluation to pixels only on the silhouette, which greatly reduces the computation cost. Our algorithm runs entirely on the GPU, achieving real-time performance and is an order of magnitude faster than the brute-force supersampling method to produce comparable 32× antialiased shadows.
16290950
Perceptually-motivated shape exaggeration
Image communication would appear more efficient if the visual cases of the concerned parts can be enhanced. One way to achieve this is by local shape exaggeration in rendering. In this paper, we present an interactive scheme for controllable local shape exaggeration. Our approach achieves local, direct, and consistent appearance enhancement by modifying the surface orientation in an intuitive and globally optimized manner with sparse user-specified constraints. Compared with previous approaches, the main contribution of this paper is the introduction of adaptive exaggeration function (AEF), which is capable of modulating the extent of detail enhancement to obtain a satisfactory shape exaggeration result. The AEF model is derived based on a series of experiments. We complement our new approach with a variety of examples, user studies, and provide comparisons with recent approaches.
16977214
Bidirectional Importance Sampling for Unstructured Direct Illumination
Recent research in bidirectional importance sampling has focused primarily on structured illumination sources such as distant environment maps, while unstructured illumination has received little attention. In this paper, we present a method for bidirectional importance sampling of unstructured illumination, allowing us to use the same method for sampling both distant as well as local/indirect sources. Building upon recent work in [WFA*05], we model complex illumination as a large set of point lights. The subsequent sampling process draws samples only from this point set. We start by constructing a piecewise constant approximation for the lighting using an illumination cut [CPWAP08]. We show that this cut can be used directly for illumination importance sampling. We then use BRDF importance sampling followed by sample counting to update the cut, resulting in a bidirectional distribution that closely approximates the product of the illumination and BRDF. Drawing visibility samples from this new distribution significantly reduces the sampling variance. As a main advance over previous work, our method allows for unstructured sources, including arbitrary local direct lighting and one-bounce of indirect lighting.
14656370
An Analysis-by-Synthesis Method for Heterogeneous Face Biometrics
Face images captured in different spectral bands, e.g. , in visual (VIS) and near infrared (NIR), are said to be heterogeneous. Although a person's face looks different in heterogeneous images, it should be classified as being from the same individual. In this paper, we present a new method, called face analogy , in the analysis-by-synthesis framework, for heterogeneous face mapping, that is, transforming face images from one type to another, and thereby performing heterogeneous face matching. Experiments show promising results.
18896215
Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)>=5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column. Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k>=2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k>=2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.
14833504
Optimal gossiping in square 2D meshes
Gossiping is the communication problem in which each node has a unique message to be transmitted to every other node. The nodes exchange their message by packets. A solution to the problem is judged by how many rounds of packet sending it requires. In this paper, we consider the version of the problem in which small-size packets each carrying exactly one message are used. The nodes of the target meshes are assumed to be all-port (a node's incident edges can all be active at the same time); and their edges are either half-duplex or full-duplex, which are also known as the H* model and the F* model, respectively. We study the class of 2D square meshes. Soch and Tvrdik (SIROCCO'97, pp. 253-265; Tech. rep. DC-97-04, Dept. of CS&E, Czech Technical University) have obtained optimal algorithms for the F* model (for square or nonsquare meshes). Lau and Zhang (IEEE Trans. Parallel Distribut. Syst. 13 (4) (2002) 349-358) have obtained fast algorithms for the H* model. We present optimal algorithms for both models, with the interesting property that they route their messages along the same paths and in the same order, i.e. for any edge {u,v}, the i-th message from u to v under either model is the same message.
7918770
Side-Channel Leaks in Web Applications: A Reality Today, a Challenge Tomorrow
With software-as-a-service becoming mainstream, more and more applications are delivered to the client through the Web. Unlike a desktop application, a web application is split into browser-side and server-side components. A subset of the application’s internal information flows are inevitably exposed on the network. We show that despite encryption, such a side-channel information leak is a realistic and serious threat to user privacy. Specifically, we found that surprisingly detailed sensitive information is being leaked out from a number of high-profile, top-of-the-line web applications in healthcare, taxation, investment and web search: an eavesdropper can infer the illnesses/medications/surgeries of the user, her family income and investment secrets, despite HTTPS protection; a stranger on the street can glean enterprise employees' web search queries, despite WPA/WPA2 Wi-Fi encryption. More importantly, the root causes of the problem are some fundamental characteristics of web applications: stateful communication, low entropy input for better interaction, and significant traffic distinctions. As a result, the scope of the problem seems industry-wide. We further present a concrete analysis to demonstrate the challenges of mitigating such a threat, which points to the necessity of a disciplined engineering practice for side-channel mitigations in future web application developments.