International Journal of Shape Modeling

The models produced by means of the available 3D-scanning technologies are considered accurate enough for most applications. Unfortunately, the acquisition of complex objects is still a demanding process that cannot be performed by non-specialists. Among the open problems, one of the most difficult to grasp is the planning of the acquisition session, i.e. choosing a set of positions of the scanner to view the whole surface of the object.

Most of the algorithms proposed in the literature either can handle few degrees-of-freedom (DOFs) or are too burdensome, as they require the optimisation of complex objective functions. Hence, they are in trouble when dealing with complex surfaces. We propose a full 6-DOF pose-planning algorithm that is simple and easy to implement. We do not search for the next best view (NBV) to minimise the number of acquisitions, as most previous algorithms do. Rather, we pursue the less ambitious objective of finding a (possibly small) set of views, that guarantee a complete coverage of the surface with a minimum accuracy on the sampled data. Given an incomplete model, unsampled regions are detected and simple patches are built to cover the missing surface. New views are estimated by clustering the normals to unsampled patches.

We propose to use a moving mesh approach, a popular grid adaption technique in computational mechanics, for fast generating low-stretch mesh parameterizations. Given a triangle mesh approximating a surface, we construct an initial parameterization of the mesh and then improve the parameterization gradually. At each improvement step, we optimize the parameterization generated at the previous step by minimizing a weighted quadratic energy where the weights are chosen in order to minimize the parameterization stretch. This optimization procedure does not generate triangle flips if the boundary of the parameter domain is a convex polygon. Moreover already the first optimization step produces a high-quality mesh parameterization. We compare our parameterization procedure with several state-of-art mesh parameterization methods and demonstrate its speed and high efficiency in parameterizing large and geometrically complex models.

Recent works in geometric modeling show the advantage of local differential coordinates in various surface processing applications. In this paper we review recent methods that advocate surface representation via differential coordinates as a basis to interactive mesh editing. One of the main challenges in editing a mesh is to retain the visual appearance of the surface after applying various modifications. The differential coordinates capture the local geometric details and therefore are a natural surface representation for editing applications. The coordinates are obtained by applying a linear operator to the mesh geometry. Given suitable deformation constraints, the mesh geometry is reconstructed from the differential representation by solving a sparse linear system. The differential coordinates are not rotation-invariant and thus their rotation must be explicitly handled in order to retain the correct orientation of the surface details. We review two methods for computing the local rotations: the first estimates them heuristically using a deformation which only preserves the underlying smooth surface, and the second estimates the rotations implicitly through a variational representation of the problem.

We show that the linear reconstruction system can be solved fast enough to guarantee interactive response time thanks to a precomputed factorization of the coefficient matrix. We demonstrate that this approach enables to edit complex meshes while retaining the shape of the details in their natural orientation.

This paper presents a novel framework for view-dependent streaming of multiresolution meshes. In contrast to conventional progressive streaming in which the resolution of a model changes globally, our server dynamically adjusts the transmission order of the detail data with respect to the client's current viewpoint. By extending the truly selective refinement scheme for progressive meshes to a client-server architecture, we accomplish an efficient view-dependent streaming framework that minimizes network communication overhead to facilitate minimal latency of mesh updates for varying viewpoints. Furthermore, we reduce the per-client session data on the server side by using a special data structure for encoding which vertices have already been transmitted to each client. We provide an analytic comparison of several view-dependent streaming frameworks and show that our framework outperforms others in terms of the network overhead. Experimental results indicate that our framework is efficient enough for a broadcast scenario where one server streams geometry data to multiple clients with different view points.

This article presents a 3D shape matching method for 3D mesh models applied to content-based search in database of 3D objects. The approach is based on the multiresolution Reeb graph (MRG) proposed by Hilaga et al.¹ MRG provides a rich representation of shapes able in particular to embed the object topology. In our framework, we consider 3D mesh models of various geometrical complexity, of different resolution, and when available with color texture map. The original approach, mainly based on the 3D object topology, is not accurate enough to obtain satisfying matching. Therefore we propose to reinforce the topological consistency conditions of the matching and to merge within the graph geometrical and visual information to improve matching and calculation of shape similarity between models. Besides, all these new attributes can be freely weighted to fit the user requirements for object retrieval. We obtain a flexible multiresolutional and multicriteria representation that we called augmented multiresolution Reeb graph (aMRG). The approach has been tested and compared with other methods. It reveals very performant for the retrieval and the classification of similar 3D shapes.

In this paper we discuss the roots and multiplicities of univariate and bivariate nonlinear polynomial systems and present methods to compute them robustly. For univariate polynomial systems, we propose an algorithm called the Topological Degree Bisection (TDB) algorithm which is developed based on the concept of the topological degree of a certain Gauss map which is deduced from input polynomials. The algorithm subdivides an input domain and computes the topological degree for each subdivided domain, which provides information on root existence inside the domain and the multiplicities. This process continues until the size of the subdivided regions which contain roots is less than a certain tolerance. In the bivariate polynomial system case, we use a combination of resultants and the TDB algorithm to develop a procedure for locating the roots and computing their multiplicities. Our methods are robust and global in nature. The proposed methods are compared with a subdivision method for root finding, the Interval Projected Polyhedron (IPP) algorithm and applied for the improvement of the IPP algorithm. Complexity analysis of the proposed methods is discussed with examples which illustrate our techniques.