ICCD: Interactive Continuous Collision Detection between Deformable Models Using Connectivity-Based Culling

We present an interactive algorithm for continuous collision detection between deformable models. We introduce multiple techniques to improve the culling efficiency and the overall performance of continuous collision detection. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh as part of self-collision tests. Second, we introduce the concept of “procedural representative triangles” to remove all redundant elementary tests between nonadjacent triangles. Finally, we exploit the mesh connectivity and introduce the concept of “orphan sets” to eliminate redundant elementary tests between adjacent triangle primitives. In practice, we can reduce the number of elementary tests by two orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior collision detection algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations, and breaking objects.     

VBTC: GPU‐Friendly Variable Block Size Texture Encoding

Recent advances in computer graphics have relied on high‐quality textures in order to generate photorealistic real‐time images. Texture compression standards meet these growing demands for data, but current texture compression schemes use fixed‐rate methods where statically sized blocks of pixels are represented using the same numbers of bits irrespective of their data content. In order to account for the natural variation in detail, we present an alternative format that allows variable bit‐rate texture compression with minimal changes to texturing hardware. Our proposed scheme uses one additional level of indirection to allow the variation of the block size across the same texture. This single change is exploited to both vary the amount of bits allocated to certain parts of the texture and to duplicate redundant texture information across multiple pixels. To minimize hardware changes, the method picks combinations of block sizes and compression methods from existing fixed‐rate standards. With this approach, our method is able to demonstrate energy savings of up to 50%, as well as higher quality compressed textures over current state of the art techniques.     

Efficient simplex computation for fixture layout design

Fixture, to hold an object by making multiple contacts, is a fundamental tool in manufacturing. A fixture layout is an arrangement of contacts on an object’s surface. Designing a fixture layout of an object can be reduced to computing the largest simplex and the resulting simplex is classified using the radius of the largest inscribed ball centered at the origin. We present three different algorithms to compute such a simplex: a simple randomized algorithm, an interchange algorithm, and a branch-and-bound algorithm. We also present methods to combine different algorithms to improve the performance and highlight their performance on complex 3D models consisting of thousands of triangles. Our randomized algorithm computes a feasible fixture layout in linear time and is well-suited for real-time applications. The interchange algorithm computes an optimal simplex in linear time such that no single vertex can be changed to enlarge the simplex, and it provides a practical method for complex 3D objects. The branch-and-bound algorithm computes the largest simplex by using lower and upper bounds on the radius of the inscribed ball, by which the computation time is reduced by a factor of five in comparison with the brute-force search.     

Real-time path planning in dynamic virtual environments using multiagent navigation graphs

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.     

Rapid and Accurate Contact Determination between Spline Models using ShellTrees

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree , that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bézier patches as part of pre-processing. At runtime it dynamically computes a tight fitting axis-aligned bounding box across each Bézier patch and efficiently checks all such boxes for overlap. Using off-line and on-line techniques for tree construction, our algorithm computes ShellTrees for Bézier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.     

Robust Algorithms for Object Localization

Model-based localization, the task of estimating an object's pose from sensed and corresponding model features, is a fundamental task in machine vision. Exact constant time localization algorithms have been developed for the case where the sensed features and the model features are the same type. Still, it is not uncommon for the sensed features and the model features to be of different types, i.e., sensed data points may correspond to model faces or edges. Previous localization approaches have handled different model and sensed features of different types via sampling and synthesizing virtual features to reduce the problem of matching features of dissimilar types to the problem of matching features of similar types. Unfortunately, these approaches may be suboptimal because they introduce artificial errors. Other localization approaches have reformulated object localization as a nonlinear least squares problem where the error is between the sensed data and model features in image coordinates (the Euclidean image error metric). Unfortunately, all of the previous approaches which minimized the Euclidean image error metric relied on gradient descent methods to find the global minima, and gradient descent methods may suffer from problems of local minima. In this paper, we describe an exact, efficient solution to the nonlinear least squares minimization problem based upon resultants, linear algebra, and numerical techniques. On a SPARC 20, our localization algorithm runs in a few microseconds for rectilinear polygonal models, a few milliseconds for generic polygonal models, and one second for generalized polygonal models (models composed of linear edges and circular arcs).     

Discriminative subgraphs for discovering family photos

Computational Visual Media - We propose to use discriminative subgraphs to discover family photos from group photos in an efficient and effective way. Group photos are represented as face graphs by...     

ACMICS: an agent communication model for interacting crowd simulation

Behavioral plausibility is one of the major aims of crowd simulation research. We present a novel approach that simulates communication between the agents and assess its influence on overall crowd behavior. Our formulation uses a communication model that tends to simulate human-like communication capability. The underlying formulation is based on a message structure that corresponds to a simplified version of Foundation for Intelligent Physical Agents Agent Communication Language Message Structure Specification. Our algorithm distinguishes between low- and high-level communication tasks so that ACMICS can be easily extended and employed in new simulation scenarios. We highlight the performance of our communication model on different crowd simulation scenarios. We also extend our approach to model evacuation behavior in unknown environments. Overall, our communication model has a small runtime overhead and can be used for interactive simulation with tens or hundreds of agents.     

Molecular Characterization of α- and β-Thalassaemia among Malay Patients

Both α- and β-thalassaemia syndromes are public health problems in the multi-ethnic population of Malaysia. To molecularly characterise the α- and β-thalassaemia deletions and mutations among Malays from Penang, Gap-PCR and multiplexed amplification refractory mutation systems were used to study 13 α-thalassaemia determinants and 20 β-thalassaemia mutations in 28 and 40 unrelated Malays, respectively. Four α-thalassaemia deletions and mutations were demonstrated. −−^SEA deletion and α^CSα accounted for more than 70% of the α-thalassaemia alleles. Out of the 20 β-thalassaemia alleles studied, nine different β-thalassaemia mutations were identified of which β^E accounted for more than 40%. We concluded that the highest prevalence of (α- and β-thalassaemia alleles in the Malays from Penang are −−^SEA deletion and β^E mutation, respectively.     

Incremental penetration depth estimation between convex polytopes using dual-space expansion

We present a fast algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski sums. The surface of the Minkowski sums is computed implicitly by constructing a local dual mapping on the Gauss map. We also present three heuristic techniques that are used to estimate the initial features used by the walking algorithm. We have implemented the algorithm and compared its performance with earlier approaches. In our experiments, the algorithm is able to estimate the penetration depth in about a milli-second on an 1 GHz Pentium PC. Moreover, its performance is almost independent of model complexity in environments with high coherence between successive instances.