International audience

Abstract We present a novel approach for the generation of hexahedral meshes in a volume domain given its meso‐skeleton. This compact representation of the topology and geometry, composed of both curve and surface parts, is used to produce a raw decomposition of the domain into hexahedral blocks. Analysis of the different local configurations of the skeleton leads to the construction of a set of connection surfaces that are used as a scaffold onto which the hexahedral blocks are assembled. These local configurations of the skeleton completely determine the singularities of the final mesh, and by following the skeleton, the geometry of the produced mesh naturally follows the geometry of the domain. Depending on the end user needs, the obtained mesh can be further adapted, refined or optimized, for example to better fit the boundary of the domain. Our algorithm does not involve the resolution of any global problem, most decisions are taken locally and it is thus highly suitable for parallel processing. This efficiency allows the user to stay in the loop for the correction or edition of the meso‐skeleton for which a first sketch can be given by an existing automatic extraction algorithm.

Geometric modifications of three-dimensional (3D) digital models are commonplace for the purpose of efficient rendering or compact storage. Modifications imply visual distortions that are hard to measure numerically. They depend not only on the model itself but also on how the model is visualized. We hypothesize that the model’s light environment and the way it reflects incoming light strongly influences perceived quality. Hence, we conduct a perceptual study demonstrating that the same modifications can be masked, or conversely highlighted, by different light-matter interactions. Additionally, we propose a new metric that predicts the perceived distortion of 3D modifications for a known interaction. It operates in the space of 3D meshes with the object’s appearance, that is, the light emitted by its surface in any direction given a known incoming light. Despite its simplicity, this metric outperforms 3D mesh metrics and competes with sophisticated perceptual image-based metrics in terms of correlation to subjective measurements. Unlike image-based methods, it has the advantage of being computable prior to the costly rendering steps of image projection and rasterization of the scene for given camera parameters.

Abstract We present CPH (Compact Primal Hierarchy): a compact representation of the hierarchical connectivity of surface and volume manifold meshes generated through primal subdivision refinements. CPH is consistently defined in several dimensions and supports multiple kinds of tessellations and refinements, whether regular or adaptive. The basic idea is to store only the finest mesh, encoded in a classical monoresolution structure that is enriched with a minimal set of labels. These labels allow traversal of any intermediate level of the mesh concurrently without having to extract it in an additional structure. Our structure allows attributes to be stored on the cells not only on the finest level, but also on any intermediate level. We study the trade‐off between the memory cost of this compact representation and the time complexity of mesh traversals at any resolution level.

ABSTRACT To produce impressive virtual worlds, real‐time crowd simulations require large and detailed scenes populated by agents with complex shapes and geometry. For efficiency reasons, these agents are usually approximated by point‐like representations to optimize the performances of collision avoidance and interactions between agents. This paper addresses the issue of handling deformable polygonal agents with arbitrary shapes in real time crowd simulations. The proposed multiresolution framework supports environments with arbitrary topologies and provides tools for efficient proximity queries. Copyright © 2014 John Wiley & Sons, Ltd.

ABSTRACT Realistic simulation of crowds is an important issue for the production of virtual worlds for games, entertainment or architectural and urban planning. Difficult issues need to be addressed such as collision avoidance and the handling of dynamic environments. In this paper, we present a unified structure for the simulation of crowds in complex urban environments. We propose a topological multiresolution model supporting different levels of details, allowing efficient proximity querying and compatible with real‐time rendering and hierarchical path planning. A fine exploitation of the multiscale aspect of the underlying model allows to achieve the same efficiency as the fastest existing methods. The generality of the approach allows the simulation to be executed on any two manifold, and the unified approach eases the handling of dynamic environments. Copyright © 2012 John Wiley & Sons, Ltd.

Many representation schemes have been proposed to deal with non-manifold and mixed dimensionalities objects. A majority of those models are based on incidence graphs and although they provide efficient ways to query topological adjacencies, they suffer two major drawbacks: redundancy in the storage of topological entities and relationships, and the lack of a uniform representation of those entities that leads to the development of large sets of intricate topological operators. As regards to manifold meshes - and specifically triangular ones - compact and efficient models are known for twenty years. Ordered topological models like combinatorial maps or half edges based data structures are widely studied and used. We propose a new representation scheme - the extended maps or X-maps - that enhances those models to deal with non-manifold objects and mixed dimensionalities. We exhibit properties that allows an adaptive implementation of the cells and thus ensures that X-maps scale well in case of large surface areas or manifold pieces. We show that the storage requirements for X-maps is strongly reduced compared to the radial edge and similar structures and also present optimizations in case of triangular or tetrahedral non-manifold meshes.