|
|
|
A Part-aware Surface Metric for Shape Analysis
|
The notion of parts in a shape plays an important role in many geometry problems, including segmentation, correspondence, recognition, editing, and animation. As the fundamental geometric representation of 3D objects in computer graphics is surface-based, solutions of many such problems utilize a surface metric, a distance function defined over pairs of points on the surface, to assist shape analysis and understanding. The main contribution of our work is to bring together these two fundamental concepts: shape parts and surface metric. Specifically, we develop a surface metric that is part-aware. To encode part information at a point on a shape, we model
its volumetric context -- called the volumetric shape image (VSI) -- inside the shape's enclosed volume, to capture relevant visibility information. We then define the part-aware metric by combining an appropriate VSI distance with geodesic distance and normal variation. We show how the volumetric view on part separation addresses certain limitations of the surface view, which relies on concavity measures over a surface as implied by the well-known minima rule. We demonstrate how the new metric can be effectively utilized in various applications including mesh segmentation, shape registration, part-aware sampling and shape retrieval.
|
|
|
Hue-Preserving Color Blending
|
We propose a new perception-guided compositing operator for color blending. The operator maintains the same rules for achromatic compositing as standard operators (such as the over operator), but it modifies the computation of the chromatic channels. Chromatic compositing aims at preserving the hue of the input colors; color continuity is achieved by reducing the saturation of colors that are to change their hue value. The main benefit of hue preservation is that color can be used for proper visual labeling, even under the constraint of transparency rendering or image overlays. Therefore, the visualization of nominal data is improved. Hue-preserving blending can be used in any existing compositing algorithm, and it is particularly useful for volume rendering. The usefulness of hue-preserving blending and its visual characteristics are shown for several examples of volume visualization.
|
|
|
Energy Aware Color Sets
|
We present a design technique for colors with the purpose of lowering the energy consumption of the display device. Our approach is based on a screen space variant energy model. The result of our design is a set of distinguishable iso-lightness colors guided by perceptual principles. We present two variations of our approach. One is based on a set of discrete user-named (categorical) colors, which are analyzed according to their energy consumption. The second is based on the constrained continuous optimization of color energy in the perceptually uniform CIELAB color space. We quantitatively compare our two approaches with a traditional choice of colors, demonstrating that we typically save approximately 40 percent of the energy. The color sets are applied to examples from the 2D visualization of nominal data and volume rendering of 3D scalar fields.
|
|
|
Deformation-Driven Shape Correspondence
|
Non-rigid 3D shape correspondence is a difficult, yet fundamental, problem in computer graphics. Most applications which require a correspondence, e.g., cross-parameterization, rely on an initial set
of manually selected markers. Without user assistance, the performances of existing automatic correspondence methods depend strongly on a good initial shape alignment or shape prior, and they generally do not tolerate large shape variations. In this paper, we present an automatic feature correspondence algorithm capable of handling large, non-rigid shape variations, as well as partial matching. This is made possible by leveraging the power of state-of-the-art mesh deformation techniques and relying on a combinatorial tree traversal for correspondence search. The search is deformation-driven, prioritized by a self-distortion energy measured on meshes deformed according to a given correspondence. That is, we measure the quality of a correspondence by the effort it would take to deform the shapes into each other based on the correspondence. We demonstrate the ability of our approach to naturally match shapes which differ in pose, local scale, part decomposition, and geometric
detail through numerous examples.
|
|
|
The Lattice-Boltzmann Method on Optimal Sampling Lattices
|
Simulations of an incompressible fluid via the Lattice-Boltzmann method (LBM) are usually performed on a Cartesian lattice. In this project, we demonstrate that the body-centered cubic (BCC) lattice is better suited for such simulations and yields a 30% saving in the number of samples without incurring any loss in accuracy.
|
|
|
Mesh Segmentation through Spectral Clustering
|
Mesh segmentation often serves as the first step of digital geometry processing. A proper segmentation of a model into meaningful parts facilitates subsequent tasks, such as morphing, parameterization, shape recognition, collision detection and etc. In this project, we investigate applying spectral clustering, a powerful clustering technique from machine learning, to mesh segmentation.
In order to apply spectral clustering, we first study how to measure the affinities between mesh faces that we wish to cluster. A specific spectral clustering technique is devised and various related questions are answered under the concept of Kernel Principal Component Analysis. To reduce the computational overhead associated with spectral clustering, we apply Nystrom method and study several issues on sub-sampling.
Also to improve the segmentation quality, we have incorporated salience measure based on psychological studies. We are currently investigating possibilities of making use of prior knowledge to further enhance the robustness of the algorithm.
|
|
|
Robust Correspondence and Retrieval of Articulated Shapes
|
We consider the problem of shape correspondence and retrieval. Although our focus is on articulated shapes, the methods developed are applicable to any shape specified as a contour, in the 2D case, or a surface mesh, in 3D. We propose separate methods for 2D and 3D shape correspondence and retrieval, but the basic idea for both is to characterize shapes using intrinsic measures, defined by geodesic distances between points, to achieve robustness against bending in articulated shapes. In 2D, we design a local, geodesic-based shape descriptor, inspired by the well-known shape context for image correspondence. For 3D shapes, we first transform them into the spectral domain based on geodesic affinities to normalize bending and other common geometric transformations and compute correspondence and retrieval in the new domain. Various techniques to ensure robustness of results and efficiency are proposed. We present numerous experimental results to demonstrate the effectiveness of our approaches.
|
|
|
Minimum Ratio Contours For Meshes
|
We present a novel minimum ratio contour (MRC) algorithm, for discretely optimizing contours on the surface of triangle meshes. We compute the contour having the minimal ratio between a numerator and a denominator energy. The numerator energy measures the bending and salience (feature adaptation) of a contour, while the denominator energy measures contour length. Given an initial contour, the optimal contour within a prescribed search domain is sought. The search domain is modeled by a weighted acyclic edge graph, where nodes in the graph correspond to directed edges in the mesh. The acyclicity of this graph allows for an efficient computation of the MRC. To further improve the results, the algorithm may be run on a refined mesh to allow for smoother contours that can cut across mesh faces. Results are demonstrated for postprocessing in mesh segmentation. We also speculate on possible global optimization methods for computing a global MRC.
|
|
|
Hough-space silhouette algorithms
|
Geometric silhouettes are curves on surfaces that separate front-facing and back-facing regions for a given viewpoint. On polygon meshes, these silhouettes can conveniently be found and updated as the viewpoint moves by considering the polygons' supporting planes. To do this efficiently, we need a compact way to represent these planes. We have found that the geometric Hough transform produces a "well-behaved" data set, and lends itself to elegant algorithms for silhouette extraction and update.
|
|
|
Spatiotemporal-chromatic structure of natural scenes
|
We investigate the implications of a unified spatiotemporalchromatic basis for compression and reconstruction of images sequences. Different adaptive methods (PCA and ICA) are applied to generate basis functions.
|
|
|
Differential Visualization of Large-Scale Time-Varying 3D Volumetric Data
|
The goal of this project is to facilitate the real-time exploration of large (several 100 GB) time-varying volumetric data produced by computational modeling or medical applications.
We take advantage of temporal coherence (coherence between consequent time frames) and spatial coherence (coherence between neighboring voxels) of three-dimensional time-varying data to facilitate an efficient visualization process.
|
|
|
Hardware-Accelerated Volume Rendering and Tomography Reconstruction on BCC Lattices
|
Volumetric data are usually represented on Cartesian lattices where samples are distributed on an orthogonal raster with a grid spacing equal in every dimension. These lattices are easy to use since indexing, interpolation and representation is very convenient. Therefore, Cartesian lattices are the most commonly used lattices to represent volumetric data. However, it is known that a Cartesian lattice has no optimal topology. In 3D an optimal lattice is the Body Centered Cubic lattice (BCC).
So far, volume rendering on BCC lattices was not achieved at interactive frame rates. In this work, we show, for the first time, how 3D objects can be first tomographic reconstructed directly on the BCC lattice, and then rendered in real-time.
|
|
|
A Laparascopic Training Environment
|
Training surgeons for laparascopic surgery is both expensive and
time consuming and reducing both parameters, along with the use
of animals for surgical practice is highly desirable. The goal
of this project is development of a virtual environment which
student surgeons could use as part of the early stages in learning
to perform laparascopic surgery. We are developing an environment
that allows a trainee to perform (portions of) tasks that are analagous
to the primary tasks of real surgery:
Suturing, Tying knots, Cutting and Dissecting tissue.
|
|
|
Single Display Groupware - Supporting Face-to-Face Collaboration
|
The dominant paradigm in computer interaction assumes that one computer is dedicated to one user at any one time. This ignores the fact that in many social environments, such as school or the workplace, people are often required to communicate and work collaboratively. The research area of Single Display Groupware (SDG) attempts to address this problem by finding effective ways to allow groups of two or more people to collaborate using a shared computer display.
|
|
|
Delaunay Meshes
|
Just as the Delaunay triangulation has proven itself as an invaluable concept for meshing planar domains, Delaunay structures are often invoked when meshing surfaces in three dimensional space. However, in the latter context there are a few distinct ways to extend the concept
of the Delaunay triangulation. The traditional structure is called the
restricted Delaunay triangulation. It is the dual of the restricted
Voronoi diagram: the 3D Voronoi diagram restricted to the surface to
be approximated by the mesh. Another possibility is to use the dual of
the Voronoi diagram defined by the intrinsic (geodesic) distance
measure on the surface. Recently a new Delaunay mesh structure has
emerged. It is a triangle mesh that is a Delaunay triangulation of its
vertices with respect to its own intrinsic metric. It is attractive
because it does not need the original surface for its definition.
However, this also introduces difficulties when making approximation accuracy
claims.
We are studying the differences and similarites between these three
structures, with a focus on illuminating the properties of the latter.
|
|
|
Visualization of Multi-Modal and Time-Varying Medical Data Using Flow Visualization Approaches
|
In the medical field, time-varying data is a common occurrence. For example, patients could have a series of CT (computed tomography) or MRI (magnetic resonance imaging) scans taken over time to enable physicians to diagnose and follow progression of diseases such as multiple sclerosis or cancer. In addition, PET (Positron emission tomography) and SPECT (single photon emission computed tomography) imaging modalities are inherently time varying since human metabolism cannot be expected to remain unchanged from one moment to the next. Nonetheless, images from the medical domain are almost exclusively displayed as static pictures, and little attempt has been made to develop visual tools that emphasize changes over time.
|
|
|
Fourier Volume Rendering
|
Often, 3D objects are defined by a 3D cloud of data points, each point with its own density. Take, for example, a magnetic resonance image (MRI) of a person\'s head. The output is a cube of numbers indicating the density at each point. It takes a lot of processing to project this 3D volume data onto a 2D screen. Each data point has to be looked at and projected separately.
|
|
|
Lag Tests - A Temporal Lag Diagnostic for Virtual and Augmented Environments
|
Improvements in minimally invasive surgery, collaborative computing environments, and computer aided design are a few applications for the goal-directed human hand study and analysis performed in the Enhanced Virtual Hand Lab (EVHL). Instead of using traditional Human Computer Interaction (HCI) media such as a mouse or keyboard, hand gestures and actions are explored in three-dimensional augmented environments. I am currently exploring performance bottlenecks within various configurations of the EVHL software and hardware (see first Figure on the left).
|
|
|
CZWeb - A Graphical Aid for Web Navigation and Information Management
|
|
The World-Wide Web is the largest hypertext-based information space in the world. The introduction of modern Web browsers allows even novice computer users with limited resources to access the wide range of services and information available on this global computer network. Navigating this large space and dealing with the information retrieved from it are often daunting tasks, needing advanced information visualization tools. CZWeb is one such tool, a graphical aid to both Web navigation and to Web information management. One of CZWeb\'s important contributions is the set of the visualization methods, including the continuous Zoom distorted view/detail-in-context algorithms. This method is used to represent visited web pages and to view, filter and restructure information retrieved from the Web. Recent extensions include pattern formation methods, based on results of analysis of user studies.
The basic alogrithms have been licensed to a startup firm, ThoughtShare Communications Inc., and have formed an integral part of the initial product suite of the company.
|
|
|
Tangential distance field methods
|
We introduce a novel class of distance fields for a given surface based on tangent-space representations. At each point in space, we assign a scalar value which is a weighted sum of distances to the tangent planes of the surface. We call the resulting scalar field a tangential distance field or TDF. When applied to triangle mesh models, the tangent planes become supporting planes of the mesh triangles. The weighting scheme used to construct a TDF for a given mesh and the way the TDF is utilized can be closely tailored to a specific application. At the same time, the TDFs are continuous, lending themselves to standard optimization techniques, such as greedy local search, thus leading to efficient algorithms.
|
|
|
Haptics in Computer-Aided Design
|
Computer graphics has done a fairly good job in simulating the physical world on computer screen. This virtual world is still not realistic enough because an important sense, touching, is not included. By being able to touch objects in the virtual world, better mental models are constructed for a given data set. The understanding of the data set presented is also easier to go deeper since the user is more involved. By constructing a more realistic virtual world, many processes that are usually too dangerous, unredoable, inconvenient, or time-consuming become less dangerous, redoable, convenient, and time-saving. Medical training, virtual manufacture, and virtual assembly are good examples of applications of haptic rendering in the near future.
|
|
|
Elastic Presentation Spaces
|
A fundamental issue in user interface design is the effective use of available screen space, commonly referred to as the screen real estate problem. Elastic Presentation Spaces (ex-3DPS) is a new distortion-based viewing tool for exploring large information spaces through the use of a three-dimensional pliable surface. Arbitrarily-shaped regions (foci) on the surface may be selected and pulled towards or pushed away from the viewer thereby increasing or decreasing the level of detail contained within each region. Furthermore, multiple foci are smoothly blended together such that there is no loss of context. The manipulation and blending of foci is accomplished using a fairly simple mathematical model based on gaussian curves. This approach utilizes precognitive perceptual cues about the three-dimensional surface to make the distortions more comprehensible, and allows the user to interactively control the location, shape, and extent of the distortion.
|
|
|
Shading For Fourier Volume Rendering
|
Our project describes two methods to incorporate viable
illumination models into Fourier Volume Rendering (FVR). The lack of adequate illumination has been one of the impediments for the wide spread acceptance of FVR.
|
|
|
Interactive Spectral Volume Rendering
|
We investigate a method for volume rendering using a spectral representation of colour instead of the traditional RGB model. Our framework provides a novel exploration of datasets through enhanced transfer function design. Furthermore, the technique of post-illumination is introduced to generate new spectral images for arbitrary light colours in real-time.
|
|
|
Moving & Rotating Documents on Tabletop Displays
|
Computers have provided powerful tools for us to work with documents, and
we heard predictions of an imminent \"paperless\" office. Yet we still use
so much paper.
An uncommon interface, tabletop computer displays, have the potential to
improve document interaction on computers.
|
|
|
Adapting Frequency Domain Volume Rendering to the BCC lattice
|
The input data for 3D volume rendering is usually given by a spatial location (coordinates) in the 3D space and an associated density value. Volume rendering algorithms usually have to traverse the whole data set to generate a 2D image from the 3D data set, hence their complexity is O(n^3). n denotes the number of data values along one axis.
|
|
|
Frequency Domain Fog Simulation
|
We explored the practical tradeoffs and benefits of doing physically accurate fluid flow simulation and fog/smoke simulation in Fourier space.
|
|
|
ExoVis: Seeing an Overview and Details in 3D
|
Three-dimensional data (3D) sets can be difficult to view if the data density is high (e.g., in volume data sets such as 3D medical imaging). In addition, screen real-estate limits how much data can be seen at any given
time. However, if we view the data sequentially (e.g., one slice at a
time), it can be difficult to keep track of the current location and
remember previously viewed data to make comparisons.
|
|
|
Shape Matching using Ant Colony Optimization
|
We have developed the first Ant Colony Optimization algorithm specifically aimed at solving the Quadratic Assignment Problem for establishing shape-correspondence, with proximity information incorporated.
|
|
|
Medical Volume Reconstruction
|
We are looking at ways to speed up SPECT data reconstruction based on the highly accurate EM algorithm using texture mapping hardware.
|
|
|
CSPL - Cell System Programming Language
|
Another part of the research concentrates on providing visual access to DNA sequences. We are working on an interactive tool for visual access to long DNA sequences represented as H curves. The tool allows interactive and animated exploration of a chosen area of the sequence, without losing global context information.
|
|
|
Experimental Design Space Explorer
|
Design space explorers allow designers to rapidly explore the vast
combinatoric spaces that represent valid solutions to a design problem.
This allows investigation of a wider variety of concepts before settling on
a final design choice; moreover, it encourages more daring design directions
by removing the risk of developing an invalid design. We are constructing
such an explorer to aid in the design of experiments.
|
|
|
Full Search Content Independent Block Matching Based on the Fast Fourier Transform
|
In digital video compression, the frames of the video are broken up into small blocks. To increase the compression ratio we would like to take the difference of each block with a similar block of pixels from the previous frame. The process of searching in a given range for the block of pixels that is most similar to the block in the current frame is referred to as block matching. The algorithm that we present is called the FFT Block Matching Algorithm (FFTBMA).
|
|
|
CZTalk - A Novel Graphical Interface for Visualizing Online Discussions
|
Our research has focused on developing tools to help understand online
discussions, and this has led to the implementation of CZTalk. CZTalk is
designed as a new multi-view user interface which should help understand the
relationships between messages and the overall patterns and trends of all the
messages posted in online discussions.
|
|
|
Efficient Multiresolution Transform
|
We exploit the theory of optimal sampling lattices in designing wavelets and filter banks for volumetric datasets. A true multidimensional (non-separable) wavelet transform is derived and applied to various datasets for comparison with the corresponding separable multidimensional method.
|
|
|
Weak Refinement for Uniform Subdivision
|
A subdivision surface is a surface that, starting with an initial polygon mesh, can be repeatedly refined to generate finer and finer meshes. In the limit, this refinement produces a surface with known properties (e.g. smoothness), but in practice only a few refinements are necessary to produce a surface which closely approximates the limit surface (i.e. subdivision converges quickly).
|
|
|
Splatting Optimizations
|
Splatting is a method for visualizing point-sampled volume datasets. We present a highly optimized implementation of the splatting algorithm that achieves near real-time rendering rates.
|
|
|
The Virtual Whales Project
|
3D Animation and sound environment for the visualization of the feeding behaviours of Pacific Humpback Whales
|
|
|
Combining 2D and 3D Views for Visualization of Spatial Data
|
2D and 3D views of 3D spatial data (e.g., medical images or CAD models) are useful for different tasks:
2D: seeing details and making precise judgements
3D: getting an overview of a 3D space and navigating approximately
For some tasks, having both 2D and 3D together is useful (e.g., a physician
may use a 2D medical image for diagnosis and a 3D view to keep track of
where the 2D image belongs in 3D space). This project consisted of a series
of user studies to compare 2D views, 3D views, and various ways of
combining 2D and 3D views for various visualization tasks.
|
|
|
Non-Realistic Rendering API
|
In this project, an API has been created that provides the functionality necessary to perform operations required by many common non-realistic rendering (NRR) algorithms. NRR is a broad categorization of rendering methods which do not attempt to mimic reality. A good example of an NRR technique is the display of images with cartoon outlines.
|
|
|
A Parallel Coordinates Interface for Volume Exploration
|
Data exploration is a crucial step in scientific research. After
experimental data is collected, scientists examine, explore, and analyze
the data to gain insight into problems. For volume data, this process
involves changing and exploring visualization parameters (lighting, zoom,
rotation, colour transfer function, opacity transfer function, rendering
method, etc.). This can be very difficult with current interfaces because:
The parameter space is very large
Users cannot easily keep track of what parameter combinations they have tried
Undoing operations (to go back to previous images) requires remembering
and re-entering all parameter settings
Effects of parameter settings cannot be easily compared
We developed a parallel coordinates based user interface that addresses
these problems and facilitates volume data exploration. Each rendering
parameter is displayed on a vertical axis. A user draws a polyline across
all axes to connect a complete set of rendering parameters and create an
image. All parameters are clearly organized and visible so that users can
see and remember what options are available and what settings generated a
given image.
We record all generated images in a history bar, allowing users to easily
backtrack to previous states and see which options have been previously
tried. Users can bookmark images or compare images side-by-side by placing
them in a favourites bar.
Initial user testing indicates the parallel coordinates based interface is
a valuable tool for volume data exploration.
|
|
|
Mesh Voxelization
|
Discrete domain representation of 3D objects are common place in medical imaging, and simulations. The challenge of displaying 3D sampled data obtained from CT scan and MRI have largely been overcome. To interact with this object representation one requires an equivalent discrete representation of the object. This project tries to address that by converting existing library of 3D mesh models into discrete version.
|
|
|
Hardware-Friendly Terrain Rendering
|
Taking advantage of modern graphics hardware when rendering large data sets like terrain models is
a challenging problem. This project is developing techniques that use new hardware
capabilities to reduce the amount of data that needs to be transferred
to and stored on the graphics card, accelerate rendering, and add capabilities.
|
|
|
Treesta, a Performance Support System in Statistical Analysis
|
Treesta is a system intended to support statistical analysis, with a focus on analysis of variance (ANOVA). The main functionality of existing statistical packages, such as Matlab and SPSS, is a rich set of statistical functions, which provides different tests, and transformations, making it possible for analysts to analyze their datasets without getting caught up in complicated calculations. But when it comes to organizing the work, and supporting creativity in data analysis, the furthest they go is to present a linear history of the user’s activity along with date and time. Treesta is a text-based interface that stands between the user and Matlab, and serves as an organizational, as well as representational, tool for statistical analysis. It categorizes the user’s work into workspaces, building a tree. Each space has its own variables, figures, and history. Spaces are organized into parent/child relations, with children inheriting variables from their parent. Each space can be assigned a meaningful name and some notes containing things the analyst wants to say about that space (e.g. the reason for a certain action). Since the user can branch to a new child any time, he/she can follow and ultimately compare multiple simultaneous solutions. Treesta provides a representation of the whole environment, highlighting the relationships among spaces, as well as a summary for each space. It also provides services like replaying a certain portion of history, which allows the analyst to apply similar functions on different data.
|
|
