GRAPP 2007 Abstracts
Conference
Area 1 - Geometry and Modeling
Area 2 - Rendering
Area 3 - Animation and Simulation
Area 4 - Interactive Environments

 Area 1 - Geometry and Modeling Title: FITTING 3D MORPHABLE MODELS USING IMPLICIT REPRESENTATIONS Author(s): Curzio Basso and Alessandro Verri Abstract: We consider the problem of approximating the 3D scan of a real object through an affine combination of examples. Common approaches depends either on the explicit estimation of point-to-point correspondences or on 2-dimensional projections of the target; both present drawbacks. We follow an approach similar to (Ilic and Fua, 2003) by representing the target mesh via an implicit function, whose values at the vertices of the approximation are used to define a robust cost function. The problem is approached in two steps, by approximating first a coarse implicit representation of the whole target, and then finer, local ones; the local approximations are then merged together with a Poisson-based method. We report the results of applying our method on a subset of 3D scans from the Face Recognition Grand Challenge v.1.0. Title: SimpliPoly: Curvature-based Polygonal Curve Simplification Author(s): Sumanta Guha, Paul Janecek and Duc Cong Song Nguyen Abstract: A curvature-based algorithm to simplify a polygonal curve is described, together with its implementation. The so-called SimpliPoly algorithm uses Bezier curves to approximate pieces of the input curve, and assign curvature estimates to vertices of the input polyline from curvature values computed for the Bezier approximations. The implementation of SimpliPoly is interactive and available freely on-line. Empirical comparisons indicate that SimpliPoly performs as well as the widely-used Douglas-Peucker algorithm in most situations, and significantly better, because it is curvature-driven, in applications where it is necessary to preserve local features of the curve. Title: The heat equation and the Frenet formulas for digital curves Author(s): Sheng-Gwo Chen, Jyh-Yang Wu, Mei-Hsiu Chi and Chen-Yao Lai Abstract: In this note we shall discuss the heat equation and the eigenvalue problem for digital curves in the 3D Euclidean space. First, we shall introduce the derivative of a function along a digital curve by the weighted combination method. Then, we can define the Laplace of a function on a digital curve. The Frenet formulas for digital curves will also be discussed. Numerical simulations show our method will provide good estimations for the curvature and torsion. Title: A simple and fast hardware-accelerated point-in-polygon test Author(s): Francisco Martínez, Antonio Rueda and Francisco R. Feito Abstract: The new generations of GPUs bring us a set of new basic operations or tools that allow us to design new solutions to traditional problems in Computer Graphics. In this paper we present two approaches for the point-in-polygon problem based on the occlusion query extensions supported by modern GPUs. Both approaches are fast and their execution times do not depend on the number of edges of the polygon. Besides, one of the tests allows multiple point-in-polygon queries to be done in parallel with CPU computations. Title: A TEXTURE-BASED METRIC EXTENSION FOR SIMPLIFICATION METHODS Author(s): Carlos González, Pascual Castelló and Miguel Chover Abstract: We present an extension of the error metrics used in the simplification methods based on edge collapse operations, where we take into account texture information. Many simplification methods are only based on the geometry of the models, without considering texture information. So, the simplified models present high distorted textures. The presented metric avoids the early collapse of edges that crashes with no uniform regions of the texture. The detection of these regions is performed by an edge detector method based on Canny. For testing the new error metric, an own geometric simplification method based on edge collapses has been used. It can be observed that simplified models with this new metric present more realistic results than before. This metric produces a modification in the order of the edge collapses. It is very useful for multiresolution models. The computational cost of this metric is negligible compared with the simplification time. Title: CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS Author(s): Adriano Moreira and Maribel Yasmina Santos Abstract: This paper describes an algorithm to compute the envelope of a set of points in a plane, which generates convex or non-convex hulls that represent the area occupied by the given points. The proposed algorithm is based on a k-nearest neighbours approach, where the value of k, the only algorithm parameter, is used to control the “smoothness” of the final solution. The obtained results show that this algorithm is able to deal with arbitrary sets of points, and that the time to compute the polygons increases approximately linearly with the number of points. Title: 2D IMAGES CALIBRATION TO FACIAL FEATURES EXTRACTION Author(s): Daniel Trevisan Bravo and Sérgio Roberto Matiello Pellegrino Abstract: The extraction of facial characteristics is too much important for several applications that involve the 3D reconstruction and facial recognition. In general, the facial modeling applications that use 2D images for the 3D reconstruction, it is necessary to prepare the images for the facial features will be extracted in an efficient way. In this paper there are procedures for calibration and correction of two facial images (the frontal and the lateral) acquired in distinct instants. As this study aim is to work with human faces, it is believed that it has well known characteristics, such as the eyes position, mouth, nose curvature, etc. Taking this previous knowledge into account, it was tried to insert it in a general context to make the automatic recognition of the searched parts, building algorithms that identify those characteristics on specific regions of the face. Although this approach makes the process faster, it also imposes restrictions to the model that, however, do not disable its execution in most of cases. Title: OUT OF CORE CONSTRUCTION OF PATCH TREES Author(s): Hermann Birkholz Abstract: Current Level of Detail (LoD) approaches for triangle meshes use variably triangulated mesh patches, in order to approximate the original mesh surface. The approximation is synthesized from some of these patches, which must cover the whole surface and must not intersect each other. The patches are chosen ac-cording to the necessary view dependent triangulation. This paper addresses the creation of the required hi-erarchical data structures, in order to enable Level of Detail synthesis for very large triangle meshes. Be-cause of the limited amount of internal memory, most of the mesh data reside in external memory during the process. Due to the high access latency of external memory, commonly used algorithms for small meshes are hardly applicable for so called “Out of Core” meshes. Other methods have to be found, which overcome the problems with the external memory. Title: Volumetric Snapping: watertight triangulation of point clouds Author(s): Tim Volodine, Michael S. Floater and Dirk Roose Abstract: We propose an algorithm which constructs an interpolating triangular mesh from a closed point cloud of arbitrary genus. The algorithm first constructs an intermediate structure called a Delaunay cover, which forms a barrier between the inside and the outside of the object. This structure is used to build a boolean voxel grid, with cells intersecting the cover colored black and all other cells colored white. The outer surface of the voxel grid is snapped to the point cloud by replacing each exterior surface vertex with the closest point in the point cloud. The snapped mesh is processed such that it is manifold and consists of triangles with good aspect ratio. We show that if a fine voxel grid is used, the snapping yields Delaunay-like triangulation of the original points. High grid resolutions are possible because of the Delaunay cover and a new contouring method, which extracts the outer surface of the grid with $O(n^2)$ worst case space complexity, where $n$ is the number of voxels in one dimension. Title: Pyramid Filters Based on Bilinear Interpolation Author(s): Martin Kraus and Magnus Strengert Abstract: The implementation of several pyramid methods on programmable graphics processing units (GPUs) in recent years led to additional research interest in pyramid algorithms for real-time computer graphics. Of particular interest are efficient analysis and synthesis filters based on hardware-supported bilinear texture interpolation because they may be used as building blocks for many GPU-based pyramid methods. In this work, several new and extremely efficient GPU-implementations of pyramid filters are presented for the first time. The discussion employs a new notation, which was developed for the consistent and precise specification of these filters and also allowed us to systematically explore appropriate filter designs. The presented filters cover analysis and synthesis filters, (quasi-)interpolation and approximation, as well as discontinuous, continuous, and smooth filters. Thus, a toolbox of filters and their efficient implementations for a great variety of GPU-based pyramid methods is presented. Title: AN ENHANCED EDGEBREAKER COMPRESSION ALGORITHM FOR THE CONNECTIVITY OF TRIANGULAR MESHES Author(s): Dina Reda Khattab, Yasser Abd El-latif, Saeed Abd El-Wahab and Fahmy Tolba Abstract: Compression of digital geometry models is the answer to an industrial demand. Over the last years, many exciting ideas and new theoretical insights have been devoted to finding ways of reducing the amount of storage such models absorb. EdgeBreaker is one of the effective lossless single-rate connectivity compression techniques for triangular meshes. This paper presents an enhanced EdgeBreaker encoding algorithm which solves the problem of non-linearity of EdgeBreaker decoding procedure while reconstructing the mesh triangles in the same order they were traversed during the encoding phase. The new enhancement is based on the same data structure: the corner-table used by EdgeBreaker however, it eliminates some of the computational overhead exhibited by EdgeBreaker compression. This enhanced technique also yields to significantly smaller rates for connectivity compression than EdgeBreaker. It achieves an average compression ratio of 1.8 bit per triangle and 3.57 bit per vertex for the used benchmark 3D models. Title: TILING THE SPHERE WITH DIAMONDS FOR TEXTURE MAPPING Author(s): John Crider Abstract: The sphere can be covered by any of an infinite number of tiling sets of equilateral spherical quadrilaterals (diamonds). Five of these tiling sets have practical use for texture mapping application. Points on the sphere can be described by intersections of geodesics, which provide coordinate values in a new coordinate system, defined for each tiling set. Each of the diamonds can be subdivided by a grid of coordinate geodesics to pixel level and so can be directly mapped to and from a texture array. The diamonds can also be subdivided into spherical quadrilaterals that can be approximated by pairs of triangles for fast rendering in a graphics system. Because coordinates in the new system are readily converted to and from Cartesian coordinates, diamonds can be used easily in interactive graphics and ray-tracing applications. Title: Orthant Neighborhood Graphs - A Decentralized Approach for Proximity Queries in Dynamic Point Sets Author(s): Tobias Germer and Thomas Strothotte Abstract: This work presents a novel approach for proximity queries in dynamic point sets, a common problem in computer graphics. We introduce the notion of Orthant Neighborhood Graphs, yielding a simple, decentralized spatial data structure based on weak spanners. We present efficient algorithms for dynamic insertions, deletions and movements of points, as well as range searching and other proximity queries. All our algorithms work in the local neighborhood of given points and are therefore independent of the global point set. This makes ONGs scalable to large point sets, where the total number of points does not influence local operations. Title: Realistic Transmission Model of Rough Surfaces Author(s): Huiying Xu and Yinlong Sun Abstract: Materials have three basic types: opaque, transparent and translucent. Transparent and translucent objects involve both light reflection and transmission at surfaces. This paper develops a realistic transmission model of rough surfaces using a physically based approach called the statistical ray method. The surface is assumed locally smooth and statistical techniques can be applied to calculate light transmission through a local illumination area. We have obtained an analytical expression for single scattering. The analytical model has been compared to our Monte Carlo simulations as well as to simulations by others, and good agreements have been achieved. The proposed model has a good application potential for realistic rendering. Title: Building 3D Indoor Scenes Topology From 2D Architectural Plans Author(s): Sébastien Horna, Guillaume Damiand, Daniel Meneveaux and Yves Bertrand Abstract: This paper presents a new method for reconstructing geometry and topology of 3D buildings from 2D architectural plans. A complete topological model expresses incidence and adjacency relations between all the elements. It is necessary for both recovering accurately 2D information and constructing a coherent 3D building. In 2D, several high-level operations are proposed for creating walls, portals, stairs, etc. Semantic information is associated with all volumes for specifying openings, walls, rooms, stairs, facade, etc. The resulting 2D model is extruded for generating a 3D environment, taking the semantic information into account since doors are not processed as walls for instance. Floors are superimposed using volumes corresponding to upper and lower ceilings linked according to stairways. Title: Extracting Terrain Morphology: A New Algorithm and a Comparative Evaluation Author(s): Paola Magillo, Leila De Floriani, Emanuele Danovaro, Laura Papaleo and Maria Vitali Abstract: We consider the problem of extracting morphology of a terrain represented as a Triangulated Irregular Network (TIN). We propose a new algorithm and compare it with representative algorithms of the main approaches existing in the literature to this problem. Title: A FAST INTERPOLATION METHOD TO REPRESENT THE BRDF IN GLOBAL ILLUMINATION Author(s): Pierre Chatelier and Rémy Malgouyres Abstract: Global illumination that simulates realistic lighting environments makes use of bidirectional reflectance dis- tribution functions (BRDF). Such a function is a surface property, describing how light is re-emitted after hitting this surface. The present paper details a representation of BRDF and radiance distributions, based on control points, that aims at performance. It uses spherical triangles for interpolation, least square mean or linear programming for optimal representation, and very fast rotation by precomputing control points re- weightening. It has some more advantages for deforming an existing shape. This approach is compared to Spherical Harmonics, and outperforms this last one. Title: Morphology-Based Representations of discrete Scalar Fields Author(s): Mohammed Mostefa Mesmoudi and Leila De Floriani Abstract: Forman introduced in(Forman,1998) a theory for cell complexes that is a discrete alternative to the well known Morse theory. Forman theory is currently finding several applications in digital geometry and image processing since the handled data are discrete, see for instance (Lewiner et al.,2002a) and (Lewiner et al.,2002b). In (de Floriani et al., 2002b) we have introduced a Smale-like decomposition of a scalar field defined on a triangulated domain based on a discrete gradient field that simulates well the behaviour of gradient field in the differential case. In this paper we extend our discrete gradient vector field so that the extended form corresponds to a Forman gradient field. Hence, the extended gradient field inherits properties of both smooth Morse and discrete Forman functions. Title: Advanced direct manipulation of feature models Author(s): Rafael Bidarra, Alex Noort, Pedro Oliveira and Daniel Lourenço Abstract: In current commercial feature modelling systems, support for direct manipulation of features is not commonly available. As a result, re-designing is time-consuming due to the inefficient feedback, the insight given is rather poor, and user interaction often lacks intuitiveness. This is partly due to the lack of speed of current constraint solvers, but also to deficient interactive facilities. In this paper, we argue that providing advanced direct manipulation facilities for feature models is possible and can significantly speed up the product design process, by giving designers a much more intuitive interface, with immediate feedback and deeper insight into the consequences of each modelling action. An approach to such a direct manipulation interface is presented that brings together the advantages of direct manipulation of feature models with the necessary emphasis on fundamental feature modelling paradigms like feature parametrisation and feature validity maintenance. In particular, it offers a powerful combination of various 3D handles for real-valued feature parameters, with a preview overlay facility for all modelling operations. Details are provided on how this approach was successfully implemented in a prototype feature modelling system. Title: LOCAL MULTIRESOLUTION ANALYSIS OF A MESH Author(s): Olivier Guillot and Jean-Paul Gourret Abstract: We build a local multiresolution analysis of surfaces when the mesh have the topology of the result from the square root 3 subdivision of a coarse mesh template. We use the concept of biorthogonality and lifting to develop a set of filters for local analysis and local synthesis. The method presented here takes into account discontinuities during the subdivision process. Title: Detecting Features from Sliced Point Clouds Author(s): Ioannis Fudos, Ioannis Kyriazis and Leonidas Palios Abstract: We present a new method for extracting the feature primitives of a 3D object directly from the point cloud of its surface scan. The objective is to identify a subset of points that provides the same information about the structure and the topology of the object geometry as the point cloud itself. The entire process is carried out with the least human intervention possible, and the only information we receive as input is the point cloud of the 3D scan of the object. First, the point cloud is sliced interactively in cross sections. Each cross section consists of a 2D point cloud. A collection of curve patches is derived for each slice, describing the cross section, and providing the feature based model that we need. For the extraction of the feature points and the interpolating curve patches we use properties of the convex hull and the voronoi diagram of the point cloud. The slices are then assembled together with advanced solid modelling operations to derive a CAD model for the initial object. Title: A Virtual Environment for Archiving Micro-Presence with Image-Based Model Acquisition Author(s): Masahiko MORITA, Tastuya SAITO and Kenji KOHIYAMA Abstract: Micro Archiving is a new method of photography that helps anybody digitally archive minute structures that existing capturing systems cannot deal with. For research use, it is an effective way to make high-fidelity virtual specimens of small objects that allow scholars to share the precious academic resources over the Internet in a digital format. For commercial use, the virtual models captured by the technology can be applied to computer graphics, games, digital cinemas and other digital entertainment media. Technically, our Micro Archiving technology enables easy and fast construction of high-quality and high-resolution textured virtual 3D models of small objects. Currently, application contents of Virtual Reality, Augmented Reality and other interactive media are dependent on the use of elaborate 3D models, which require expensive manual task. Micro Archiving technology provides automatic capturing process that can comprehensively handle a high-resolution all-focused imaging, 3-dimensional modeling and transparency capturing simultaneously. Micro Archiving is best suited for minute and complex objects such as machine parts, insects, plants and small archaeological materials. Title: Hierarchical Brain Model for Coregistration Author(s): Terrence Oakes Abstract: A ubiquitous problem in coregistration of brain images is that individual sulci and gyri vary considerably between individuals, both with respect to location and shape as well as for simple existence of particular sulci. The underlying assumption of most coregistration processes is that one structure can be smoothly morphed to exactly resemble another structure if enough parameters are used. Although in a strict sense this may be true for intersubject brain registration, due to differing structures the result may not be as meaningful as desired. The proposed approach offers a groundbreaking alternative to the standard approach of continuously deformable coregistration algorithms, introducing instead a hierarchical structure of related nodes (a "nodetree") to model the brain structure using gray-matter and white-matter masks. Additonally, a proposal is made for using the nodetree structure for coregistration, employing a novel locally discontinuous but focused registration to more accurately align and compare corresponding features. This approach can provide a framework for identifying structural differences, with a goal of relating them to functional differences. Although this method uses the brain as an example, it is quite general and not limited to the brain, or even to medical images. Title: Modeling Dendritic Forms Using Path Planning Author(s): David Mould and Ling Xu Abstract: We present a method for creating geometric models of dendritic forms. Dendritic shapes are commonplace in the natural world; some examples of objects exhibiting dendritic shape include lichens, coral, trees, lightning, rivers, crystals, and venation patterns. Our method first generates a regular lattice with randomly weighted edges, then finds least-cost paths through the lattice. Multiple paths from a single starting location (or generator) are connected into a single dendritic shape. Alternatively, path costs can be used to segment volumes into irregular shapes. The pathfinding process is inexpensive, and admits control handles including endpoint placement, distribution of generators, and arrangement of nodes in the graph. Title: SURFACE MODELING OF MULTI-POINT, MULTI-FLUTE CUTTING TOOLS Author(s): Phalguni Gupta, Sanjay G. Dhande and Puneet Tandon Abstract: Cutting tools are usually represented by two-dimensional representation schema(s). The two-dimensional nomenclatures have their inherent limitations. This paper outlines a detailed surface based modeling paradigm for a variety of multi-point, multi-flute cutting tools. The work presents the generic biparametric surface patch based models of slab mills, end mills and drills. A slab mill consists of flutes (meant for cutting) and planar end surfaces, while the end mills and drills are made up of flutes, shanks and varied end geometries. The flutes are modeled as helicoidal surfaces which are generated by first developing the sectional geometry of its tip-to-tip profile and then sweeping according to the type of the cutter under consideration. The transitional surfaces of these cutters are modeled as bicubic Bézier surfaces or biparametric sweep surfaces. The relations to map proposed three-dimensional rotational angles that help define three-dimensional geometric models to conventional angles (forward mapping) and their reverse relations (inverse mapping) are also developed. The new paradigm offers immense technological advantages in terms of numerous downstream applications. Title: HIERARCHIC MODELING OF SYMMETRIC GEOMETRIES Author(s): Pritee Khanna, Puneet Tandon and Sanjay G. Dhande Abstract: The world is full of procedural ornaments, especially in cultural heritage. These ornaments are often said to be too complex for automatic modeling, and too tedious for manual modeling. A pattern is an orderly arrangement of objects in space. In this work a geometric model for symmetric patterns is proposed. The two-dimensional hierarchic model represents pattern as a tree. The model when implemented reads in a motif description, builds a tree of motifs and renders the pattern as well as final layout. Interactive editing of motif descriptions can be performed with a GUI. The proposed geometric model for two-dimensional patterns can be incorporated into design software that can be used by persons having minimal artistic skills.