With virtual reality, digital painting on 2D canvases is now being extended to 3D spaces. Tilt Brush and Oculus Quill are widely accepted among artists as tools that pave the way to a new form of art - 3D emmersive painting. Current 3D painting systems are only a start, emitting textured triangular geometries. In this paper, we advance this new art of 3D painting to 3D volumetric painting that enables an artist to draw a huge scene with full control of spatial color fields. Inspired by the fact that 2D paintings often use vast space to paint background and small but detailed space for foreground, we claim that supporting a large canvas in varying detail is essential for 3D painting. In order to help artists focus and audiences to navigate the large canvas space, we provide small artist-defined areas, called rooms, that serve as beacons for artist-suggested scales, spaces, locations for intended appreciation view of the painting. Artists and audiences can easily transport themselves between different rooms. Technically, our canvas is represented as an array of deep octrees of depth 24 or higher, built on CPU for volume painting and on GPU for volume rendering using accurate ray casting. In CPU side, we design an efficient iterative algorithm to refine or coarsen octree, as a result of volumetric painting strokes, at highly interactive rates, and update the corresponding GPU textures. Then we use GPU-based ray casting algorithms to render the volumetric painting result. We explore precision issues stemming from ray-casting the octree of high depth, and provide a new analysis and verification. From our experimental results as well as the positive feedback from the participating artists, we strongly believe that our new 3D volume painting system can open up a new possibility for VR-driven digital art medium to professional artists as well as to novice users.
To our best knowledge, octrees as deep as 24 were not used for ray casting. The deepest trees we found was @math used in @cite_6 , which is equivalent to the octree depth of 12 (our canvas is equivalent to @math ), and the ray angle drift error has not been identified as a challenge. We propose a solution and thoroughly analyze the numerical precision associated with ray drift during ray traversal using a very deep tree.
@cite_6
71158427 1582613544 1968399077 1518294493
In this paper an acceleration method for finding the nearest ray–object intersection for ray tracing purposes is presented. We use the concept of BSP trees enriched by rope trees. These are used to accelerate the traversal of the BSP tree. We give a comparison of experimental results between the technique based on BSP tree and uniform spatial subdivision. We improve on earlier FPT algorithms for computing a rooted maximum agreement forest (MAF) or a maximum acyclic agreement forest (MAAF) of a pair of phylogenetic trees. Their sizes give the subtree-prune-and-regraft (SPR) distance and the hybridization number of the trees, respectively. We introduce new branching rules that reduce the running time of the algorithms from O(3kn) and O(3kn logn) to O(2.42kn) and O(2.42kn logn), respectively. In practice, the speed up may be much more than predicted by the worst-case analysis. We confirm this intuition experimentally by computing MAFs for simulated trees and trees inferred from protein sequence data. We show that our algorithm is orders of magnitude faster and can handle much larger trees and SPR distances than the best previous methods, treeSAT and sprdist. We study distorted metrics on binary trees in the context of phylogenetic reconstruction. Given a binary tree T on n leaves with a path metric d, consider the pairwise distances d(u,v) between leaves. It is well known that these determine the tree and the d length of all edges. Here, we consider distortions @math of d such that, for all leaves u and v, it holds that @math if either d(u,v)< M + f 2 or @math , where d satisfies f ≤ d(e) ≤ g for all edges e. Given such distortions, we show how to reconstruct in polynomial time a forest T1, ... ,Tα such that the true tree T may be obtained from that forest by adding α-1 edges and α-1 ≤ 2-Ω(M g) n. Our distorted metric result implies a reconstruction algorithm of phylogenetic forests with a small number of trees from sequences of length logarithmic in the number of species. The reconstruction algorithm is applicable for the general Markov model. Both the distorted metric result and its applications to phylogeny are almost tight. Motivated by applications in parallel and dynamic graph algorithms, we investigate the tradeoff between width and diameter of tree decompositions. For all integers n, k and K with 1 ≤ k ≤ K ≤ n− 1, denote by D(n, k, K) the maximum, over all n-vertex graphs G of treewidth k, of the smallest diameter of a tree decomposition of G of width K. We determine D(n, k, K), up to a constant factor, for all values of n, k and K. When K is bounded by a constant (the case of greatest practical relevance), D(n, k, K) is θ(n) for K ≤ 2k-1, θ(√n) for 2k ≤ K ≤ 3k−2, and θ(log n) for K ≥ 3k−1. We provide much more accurate bounds for the case K ≤ 2k−1.