Shape recognition and pose estimation for mobile Augmented Reality

Nestor is a real-time recognition and camera pose estimation system for planar shapes. The system allows shapes that carry contextual meanings for humans to be used as Augmented Reality (AR) tracking targets. The user can teach the system new shapes in real time. New shapes can be shown to the system frontally, or they can be automatically rectified according to previously learned shapes. Shapes can be automatically assigned virtual content by classification according to a shape class library. Nestor performs shape recognition by analyzing contour structures and generating projective-invariant signatures from their concavities. The concavities are further used to extract features for pose estimation and tracking. Pose refinement is carried out by minimizing the reprojection error between sample points on each image contour and its library counterpart. Sample points are matched by evolving an active contour in real time. Our experiments show that the system provides stable and accurate registration, and runs at interactive frame rates on a Nokia N95 mobile phone.     

External Memory View-Dependent Simplification

In this paper, we propose a novel external-memory algorithm to support view-dependent simplification for datasets much larger than main memory. In the preprocessing phase, we use a new spanned sub-meshes simplification technique to build view-dependence trees I/O-efficiently, which preserves the correct edge collapsing order and thus assures the run-time image quality. We further process the resulting view-dependence trees to build the meta-node trees, which can facilitate the run-time level-of-detail rendering and is kept in disk . During run-time navigation, we keep in main memory only the portions of the meta-node trees that are necessary to render the current level of details, plus some prefetched portions that are likely to be needed in the near future. The prefetching prediction takes advantage of the nature of the run-time traversal of the meta-node trees, and is both simple and accurate. We also employ the implicit dependencies for preventing incorrect foldovers, as well as main-memory buffer management and parallel processes scheme to separate the disk accesses from the navigation operations, all in an integrated manner. The experiments show that our approach scales well with respect to the main memory size available, with encouraging preprocessing and run-time rendering speeds and without sacrificing the image quality.     

Directional Discretized Occluders for Accelerated Occlusion Culling

We present a technique for accelerating the rendering of high depth-complexity scenes. In a preprocessing stage, we approximate the input model with a hierarchical data structure and compute simple view-dependent polygonal occluders to replace the complex input geometry in subsequent visibility queries. When the user is inspecting and visualizing the input model, the computed occluders are used to avoid rendering geometry which cannot be seen. Our method has several advantages which allow it to perform conservative visibility queries efficiently and it does not require any special graphics hardware. The preprocessing step of our approach can also be used within the framework of other visibility culling methods which need to pre-select or pre-render occluders. In this paper, we describe our technique and its implementation in detail, and provide experimental evidence of its performance. In addition, we briefly discuss possible extensions of our algorithm.     

A GPU persistent grid mapping for terrain rendering

In this paper we present persistent grid mapping (PGM), a novel framework for interactive view-dependent terrain rendering. Our algorithm is geared toward high utilization of modern GPUs, and takes advantage of ray tracing and mesh rendering. The algorithm maintains multiple levels of the elevation and color maps to achieve a faithful sampling of the viewed region. The rendered mesh ensures the absence of cracks and degenerate triangles that may cause the appearance of visual artifacts. In addition, an external texture memory support is provided to enable the rendering of terrains that exceed the size of texture memory. Our experimental results show that the PGM algorithm provides high quality images at steady frame rates. Electronic supplementary material Supplementary material is available in the online version of this article at and is accessible for authorized users.     

Topology simplification for polygonal virtual environments

We present a topology simplifying approach that can be used for genus reductions, removal of protuberances, and repair of cracks in polygonal models in a unified framework. Our work is complementary to the existing work on geometry simplification of polygonal datasets and we demonstrate that using topology and geometry simplifications together yields superior multiresolution hierarchies than is possible by using either of them alone. Our approach can also address the important issue of repair of cracks in polygonal models, as well as for rapid identification and removal of protuberances based on internal accessibility in polygonal models. Our approach is based on identifying holes and cracks by extending the concept of α-shapes to polygonal meshes under the L_∞ distance metric. We then generate valid triangulations to fill them using the intuitive notion of sweeping an L_∞ cube over the identified regions     

Seamless patches for GPU-based terrain rendering

In this paper we present a novel approach for interactive rendering of large terrain datasets. Our approach is based on subdividing a terrain into rectangular patches at different resolutions. Each patch is represented by four triangular tiles that are selected form different resolutions, and four strips which are used to stitch the four tiles in a seamless manner. Such a scheme maintains resolution changes within patches through the stitching strips, and not across patches. At runtime, these patches are used to construct a level-of-detail representation of the input terrain based on view-parameters. A selected level of detail only includes the layout of the patches and their boundary edges resolutions. The layout includes the location and dimension of each patch. Within the graphics hardware, the GPU generates the meshes of the patches by using scaled instances of cached tiles and assigns elevation for each vertex from cached textures. Since adjacent rectangular patches agree on the resolution of the common edges, the resulted mesh does not include cracks or degenerate triangles. Our algorithm manages to achieve quality images at high frame rates while providing seamless transition between different levels of detail.     

Generalized View-Dependent Simplification

We propose a technique for performing view-dependent geometry and topology simplifications for level-of-detail-based renderings of large models. The algorithm proceeds by preprocessing the input dataset into a binary tree, the view-dependence tree of general vertex-pair collapses. A subset of the Delaunay edges is used to limit the number of vertex pairs considered for topology simplification. Dependencies to avoid mesh foldovers in manifold regions of the input object are stored in the view-dependence tree in an implicit fashion. We have observed that this not only reduces the space requirements by a factor of two, it also highly localizes the memory accesses at run time. The view-dependence tree is used at run time to generate the triangles for display. We also propose a cubic-spline-based distance metric that can be used to unify the geometry and topology simplifications by considering the vertex positions and normals in an integrated manner.     

Interactive GPU-based adaptive cartoon-style rendering

In this paper we present a novel real-time cartoon-style rendering approach, which targets very large meshes. Cartoon drawing usually uses a limited number of colors for shading and emphasizes special effects, such as sharp curvature and silhouettes. It also paints the remaining large regions with uniform solid colors. Our approach quantizes light intensity to generate different shadow colors and utilizes multiresolution mesh hierarchy to maintain appropriate levels of detail across various regions of the mesh. To comply with visual requirements, our algorithm exploits graphics hardware programmability to draw smooth silhouette and color boundaries within the vertex and fragment processors. We have adopted a simplification scheme that executes simplification operators without incurring extra simplification operations as a precondition. The real-time refinement of the mesh, which is performed by the graphics processing unit (GPU), dramatically improves image quality and reduces CPU load.