IEEE Computer Graphics and Applications

PrePrint: Parallel and Streaming Generation of Ghost Data for Structured Grids

Parallel simulations decompose large domains into many blocks. A fundamental requirement for subsequent parallel analysis and visualization is the presence of *ghost data* that supplements each block with a layer of adjacent data elements from neighboring blocks. The standard approach for generating ghost data requires all blocks to be in memory at once. This becomes impractical when there are fewer processors---and thus less aggregate memory---available for analysis than for simulation. We describe an algorithm for generating ghost data for structured grids that uses many fewer processors than previously possible. Our algorithm stores as little as one block per processor in memory and can run on as few processors as are available (possibly just one). The key idea is to slightly change the size of the original blocks by declaring parts of them to be ghost data, and by later padding adjacent blocks with this data.

PrePrint: Real Time Camera Pose Estimation for Wide Area Augmented Reality Applications

Registration between real and synthetic worlds is one of the most difficult problems in augmented reality systems. To solve the registration problem for wide area AR applications, we propose a real time camera pose estimation method. In this paper, two main contributions are: Firstly, a method based on multiple maps and local bundle adjustment is proposed to solve the online scene reconstructing problem. The method enables the registration to work without the prior knowledge of natural scenes, which really enhance the usability of AR systems. Secondly, we redefine the class of the traditional ferns and propose a new recognition method to perform the online keyframes learning and recognition to obtain a system that has the ability to learn keyframes dynamically and switch between different scenes automatically even in large scale workspaces. Some results are introduced to validate the performance of the proposed method.

PrePrint: From Styling Design to Products Fabricated by Planar Materials

This article describes a geometric modeling system that generates industry required planar pieces for fabricating user-customized products from styling designs. The processing from style design to industrial patterns is automated. Pre-stored styling designs can be automatically mapped into different reference model shapes and then unfolded into planar pieces. Besides, a map-guided algorithm has been developed to locate unfolded pieces according to industrial requirement.

PrePrint: Prajna: Adding Automated Reasoning to the Visual Analysis Process

Applications and systems can represent knowledge in a variety of ways. A graphic display might allow a knowledge analyst to infer new information through interactive visualizations. Knowledge can be represented as a collection of facts, which can then be used for automatic inference. Knowledge can also be represented or stored in various archives, such as databases or formatted files. Those developers challenged with creating applications for knowledge representation frequently have to contend not only with data challenges, but also with challenges caused by a wide variety of software toolkits, architectures, and standards for knowledge representation. To meet these obstacles, we developed the Prajna Project. The Prajna Project is a Java toolkit designed to provide various capabilities for visualization, knowledge representation, geographic displays, semantic reasoning, and data fusion. Within this paper, we present both the capabilities of the Prajna project, and use it to illustrate techniques that address these challenges.

PrePrint: Intuitive Interactive Human Character Posing with Millions of Example Poses

We present a data-driven algorithm for interactive 3D human character posing. We formulate the problem in a maximum a posteriori (MAP) framework by combining the user's inputs with the priors embedded in prerecorded human poses. Maximizing the posteriori allows us to generate a most likely human pose that satisfies the user constraints. One unique property of our system is its ability to learn priors from a huge and heterogeneous human motion capture database (2.8 million prerecorded poses) and use them to generate a wide range of natural poses, a capacity that has not been demonstrated in previous data-driven character posing systems. In addition, we present two intuitive interfaces for interactive human character posing: direct manipulation interfaces and sketching interfaces. We show the superiority of our system by comparing it with standard inverse kinematics techniques as well as to alternative data-driven techniques.

PrePrint: The Impact of the OCEAN Personality Model on the Perception of Crowds

Most current crowd simulators animate homogeneous crowds, but include underlying parameters that can be tuned to create variations within the crowd. These parameters, however, are specific to the crowd models and may be difficult for an animator or naïve user to use. We propose mapping these parameters to personality traits. In this paper, we extend the HiDAC (High-Density Autonomous Crowds) system by providing each agent with a personality model. We use the OCEAN personality model as a basis for agent psychology. To each personality trait we associate nominal behaviors; thus, specifying personality for an agent leads to an automation of the low-level parameter tuning process. We describe a plausible mapping from personality traits to the existing behavior types and analyze the overall emergent crowd behaviors. Finally, we validate our mapping by user studies that assess the perception of the traits in the animations illustrating such behaviors.

PrePrint: A Viewer-Centric Editor for Stereoscopic Cinema

A digital editor provides the timeline control necessary to tell a story through film. Current technology, although sophisticated, does not easily extend to 3D cinema because stereoscopy is a fundamentally different medium for expression and requires new tools. We formulated a mathematical framework for use in a viewer-centric digital editor for stereoscopic cinema driven by the audience's perception of the scene. Our editing tool implements this framework and allows both shot planning and after-the-fact digital manipulation of the perceived scene shape. The mathematical framework abstracts away the mechanics of converting this interaction into stereo parameters, such as interocular, field of view, and location. We demonstrate cut editing techniques to direct audience attention and ease scene transitions. User studies were performed to examine these effects.

IEEE Computer Graphics and Applications - March/April 2010 (Vol. 30, No. 2)

IEEE Computer Graphics and Applications

PrePrint: Practical Character Physics For Animators

We describe a graphics system that significantly improves the visual quality of certain types of 3D character motion animated through traditional means by inferring physical properties and correcting the results through the use of dynamics. These physical characteristics are visualized and provide information not normally available to traditional 3D animators, such as displaying the center of mass, angular momentum and zero moment point. By comparing the original path as generated by an animator, against a proper physically-based path generated by our tool, the animator is able to interactively modify the original motion path to more closely match the generated physics-based path. This often results in better quality character motion. Two different types of motion can be adjusted: animations which involve ballistic paths, such as falling and jumping, as well as animations involving character movement which require balance and posture, such as walking or running. This dynamics visualization method is integrated into a professional software system for use in a visual effects studio that incorporates live-action with 3D animated characters in feature film production. Our research shows that between 10\% and 16\% of the shots of a character-heavy feature film will incorporate ballistic motions that may be improved by our system.

PrePrint: Linear Algorithms in Sublinear Time -- a tutorial on statistical estimation

In this tutorial we present techniques of probability theory to boost linear algorithms. The main idea is based on statistics and uses educated guesses instead of comprehensive calculations. As estimates can be calculated in sublinear time, many algorithms can benefit from statistical estimation. In our examples linear algorithms are boosted significantly without negative effects on the algorithms' results. We demonstrate this technique on a RANSAC algorithm, an image processing algorithm and on a geometrical reconstruction. The theoretic foundation of this techniques take advantage of the fact that in many cases the amount of information in a data set increases asymptotically sublinear if its size or sampling density increases. Conversely, an algorithm with expected sublinear running time can extract most information.

PrePrint: A survey on solid texture synthesis

In this survey, we illustrate the different algorithms proposed in literature to synthesize and represent solid textures. Solid textures are an efficient instrument to compactly represent both the external and internal appearance of 3D objects, providing practical advantages with respect to classical 2D texturing. Within this framework, we propose a novel classification of solid texture synthesis methods: boundary-independent and boundary-dependent methods. In the case of boundary-independent methods, the shape of the object to be textured is irrelevant and texture information can be freely generated for each point in the space. Conversely, boundary-dependent methods conform the synthesis process to the actual shape of the object, so that they can exploit this information to orient and guide the texture generation.

PrePrint: EasyToy: A Plush Toy Design System Using Editable Sketching Curves

EasyToy is an industrial-strength plush toy design system, targeting novices who want to design sophisticated toy models by themselves, simply and quickly. The fundamental tool in EasyToy is editable sketching curves, which combine the advantages of both natural expression of free-form strokes and the controllability of B-spline curves. A distinct feature in EasyToy system is that each sketching curve can be continuously edited to refine the initial rough idea. Using a small set of simple tools, EasyToy easily constructs sophisticated toy models comparable with those by professional systems. Informal user study has been conducted in a two-year period. The results are inspiring: using EasyToy, the design intent of users can be addressed fluently by mimicking traditional paper-and-pencil-based 2D/3D sketches, without distraction and interruption appearing often during the modeling processes in previous design systems.

PrePrint: Knowledge-Assisted Visualization and Segmentation of Geologic Features using Implicit Surfaces

We present a technique that allows knowledge-assisted interactive visualization and segmentation of geologic surfaces. Our method employs domain knowledge about the structure and topology of geologic features in seismic data in order to steer dynamic surfaces into those features. Specialized attributes guide evolving surfaces by adapting to the known shape of geologic features. Geometric, topological, and geologic information help steer growth and can be rendered on the evolving surface, which allows knowledge to be inferred during the process. Our technique is implemented in a 3-D visualization environment that contains domain information about geologic features in seismic data and allows users to interactively steer segmentations based on visual sources of information and knowledge. Results from a user study are presented that show the ability of this technique to transfer domain knowledge to non-experts, which allows for intuitive segmentation of geologic features.

PrePrint: Knowledge-Based 3D Reconstruction and Visualization of Human Ribcage and Lungs

To help mimic some of the useful features of CT scans for early detection of diseases like lung cancer at a fraction of the cost, a knowledge‐assisted interactive 3D ribcage and lung reconstruction algorithm is proposed. The ribcage and lung reconstructions are both based on the typical PA (rear) and Lateral (side) X‐ray images that are already being acquired during preemptive screenings for lung cancer. Shared domain knowledge of human anatomy and solid modeling techniques are combined with knowledge automatically extracted from the X‐ray images through computer vision algorithms to transform a series of primitive template meshes into reconstructed ribs and lungs despite the fact that much of the 3D information is lost during the X‐ray process. An example of how the reconstructed lung geometry can be used to clip the portion of an approximate volume reconstruction to provide a supplementary interface to search for potential diseased areas is presented.

PrePrint: Natural Character Posing from a Large Motion Database

This paper presents NAT-IK, a new interactive inverse kinematics scheme that can robustly and interactively generate natural poses in a large human-reachable space. NAT-IK employs an adaptive kd-clustering algorithm to select a representative frame set from a large motion database, and a sparse approximation algorithm to accelerate the training and posing processes. The model training process needs to be done only once. The training results contain 30MB of data, which can be conveniently imported into existing animation packages.

PrePrint: Navigation Tools for Augmented CAD Viewing

The creation of a computer aided design (CAD) model is the first step in the development of any modern physical product. This model will be used during the complete life cycle of the product: prototyping, fabrication, maintenance and upgrade. During the construction, a discrepancy between the model and the object can occur. In order to maintain and upgrade the object it is mandatory to have a model that represents the reality. So that one can have an up-to-date model one has to verify it and sometimes update it. We propose a scalable solution where CAD software has been augmented with pictures of the object. Still images have been aligned to the model allowing visualization of the model and the object at the same time. This creates what can be called a mixed view. The virtual camera that renders the model in a mixed view is restricted by the still image because the alignment between the image and the model has to be maintained. We developed tools to navigate in this mixed world. We transposed the zoom and pan from 2D user interfaces in order to navigate in the mixed view. Additionally we introduced tools for intuitive navigation within a set of mixed views.

PrePrint: AniViz: A Template-based Animation Tool for Volume Visualization

We introduce AniViz – a tool for making visualization animations. The design of AniViz is mainly based on two principles. First, AniViz allows the user to make animations while exploring the data. Second, AniViz provides a set of motion templates for the user to create desirable effects as instances of those templates. AniViz also provides the user with a set of operators to edit an instance or combine multiple ones into a sequence of effects. The user can fine tune parameters associated with an instance or a sequence in a keyframe style. The length of each segment in the animation may be specified by the user or automatically allocated by AniViz based on a distance metric. AniViz offers these functionalities through a simple and easy-to-use interface. We demonstrate AniViz with several volume visualization applications.

PrePrint: Volumetric Ambient Occlusion

This paper presents a new GPU-based algorithm to compute ambient occlusion. We first examine how ambient occlusion is related to the physically founded rendering equation. The correspondence is made by introducing a fuzzy membership function that defines what ``near occlusions'' mean. Then we develop a method to calculate ambient occlusion in real-time without any pre-computation. The proposed algorithm is based on a novel interpretation of ambient occlusion that measures how big portion of the tangent sphere of the surface belongs to the set of occluded points. The integrand of the new formula has low variation, thus can be estimated accurately with a few samples. Thus, the algorithm can effectively be used in real-time systems and games to cheaply approximate global illumination effects.

PrePrint: Application-Driven Compression for Visualizing Large-Scale Time-Varying Volume Data

In many areas of science and engineering, the desires to study a problem at the highest possible resolution have led to an explosive growth of data. It is imperative to reduce the data to a manageable scale for analysis and visualization. For high-precision floating-point data, compressing the data solely based on values can only achieve a limited saving. Further reduction is possible with the fact that usually only a smaller subset of the data is of interest in analysis. In this paper, we present an application-driven approach to compressing large-scale time-varying volume data. Our method identifies a reference feature to partition the data into space-time blocks, which are compressed with various precisions depending on their association to the feature. Runtime decompression is performed with bit-wise texture packing and deferred filtering. We show that our method achieves high compression rates and interactive rendering while preserving fine details surrounding regions of interest. Such an application-driven approach points us to a promising direction for coping with the large data problems facing computational scientists.

PrePrint: Insight into 3D goal-directed movements through a division into meaningful movement phases

The measures that are currently used to evaluate users’ performances on interaction tasks in virtual environments often do not provide sufficient information for how to improve these interactions. The current paper proposes a new method for analyzing 3D goal-directed movements based on dividing them into meaningful phases. We apply the method to experimental data that we have collected earlier for a 3D task that resembles a standardized 2D multi-directional pointing task (ISO 9241-9). Our analysis demonstrates how a more detailed insight into 3D goal-directed movements can be gained. We claim that this analysis can help to better identify weak and strong points of input devices or interaction techniques.