Research

Approximate Convex Decomposition

Collision detection is essential for realistic physical interactions in video games and computer animation. In order to ensure real-time interactivity with the player/user, video game and 3D modeling software developers usually approximate the 3D models composing the scene (e.g. animated characters, static objects...) by a set of simple convex shapes such as ellipsoids, capsules or convexhulls. In practice, these simple shapes provide poor approximations for concave surfaces and generate false collision detections.

A second approach consists in computing an exact convex decomposition of a surface S, which consists in partitioning it into a minimal set of convex sub-surfaces. Exact convex decomposition algorithms are NP-hard and non-practical since they produce a high number of clusters.

To overcome this limitation, we relax the exact convexity constraint and coonsider instead the problem of computing an approximate convex decomposition of S. Here, the goal is to determin a partition of the mesh vertices with a minimal number of clusters, while ensuring that each cluster has concavity lower than a user defined threshold.

Frame-based Animated Mesh Compression

The FAMC (Frame-based Animated Mesh Compression) codec was promoted in 2008 as of the MPEG standard. FAMC combines a model-based motion compensation strategy, with a transform/predictive coding of the residual errors. Here, a skinning model is automatically computed from frame-based representation and then encoded within the bitstream in order to be exploited for motion compensation. Subsequently, either (1) DCT/Lifting wavelets or (2) PCA or (3) layer-based predictive coding is employed to exploit the remaining spatio-temporal correlations.

The FAMC codec offers high compression performances (60% of gains in bitrates w.r.t. previous MPEG-4 technology and 20-40% w.r.t. the state-of-the-art approaches) and is well suited for compressing both geometric and photometric attributes. In addition, FAMC supports a rich set of functionalities including streaming, spatial, temporal and quality scalability and progressive transmission.

Triangle Fan-based Mesh Compression

The TFAN (Triangle FAN-based compression) approach compresses in a unified manner meshes of arbitrary topologies (e.g. non-manifold, non-oriented and closed/open meshes with arbitrary genus), while offering a linear computational complexity for both encoding and decoding. In addition, the TFAN compressed representation is optimized for real-time decoding applications.

The TFAN codec outperform existing techniques such as MPEG-4/3DMC (3M Mesh Coding) or Touma and Gotsman approaches, with decoding times lower by an order of magnitude at equivalent or even better levels of compression efficiency (+- 10% in bitrate). In addition, when applied to non-manifold meshes, the compression performances are significantly enhanced (6-30% gain in bitrate). Due to its high compression performances the TFAN approach has been promoted in 2009 as part of the MPEG standard.

B-Spline Compression of 3D Meshes

This paper introduces a new approach for efficient progressive compression of dense and smooth 3D meshes. Based on a multiple-patch B-Spline representation, the proposed compression scheme includes three stages: mesh segmentation into patches, parameterization and B-Spline fitting. The geometry images of the B-Splines control points are compressed with optimized still image encodes, while the mesh connectivity is losslessly encoded by applying the Touma and Gotsman (TG) algorithm.

The experimental evaluation, carried out on a corpus of meshes from the Stanford and Cyberware repositories, shows that the proposed compression scheme achieves significant gains (30% on average) when compared to the spectral compression approach and outperforms both MPEG-4 and TG codecs, particularly at low bitrates (i.e. less than 8 bits per vertex).