Abstract: Paper pop-ups are interesting three-dimensional books that fascinate people of all ages. The design and construction of these pop-up books however are done manually and require a lot of time and effort. This has led to computer-assisted or automated tools for designing paper pop-ups. This paper proposes an approach for automatically converting a 3D model into a multi-style paper pop-up. Previous automated approaches have only focused on single-style pop-ups, where each is made of a single type of pop-up mechanisms. In our work, we combine multiple styles in a pop-up, which is more representative of actual artist’s creations. Our method abstracts a 3D model using suitable primitive shapes that both facilitate the formation of the considered pop-up mechanisms and closely approximate the input model. Each shape is then abstracted using a set of 2D patches that combine to form a valid pop-up. We define geometric conditions that ensure the validity of the combined pop-up structures. In addition, our method also employs an image-based approach for producing the patches to preserve the textures, finer details and important contours of the input model. Finally, our system produces a printable design layout and decides an assembly order for the construction instructions. The feasibility of our results is verified by constructing the actual paper pop-ups from the designs generated by our system.

Abstract: Paper pop-ups are fascinating three-dimensional books that impart stories and information more vividly to their readers. The design and construction of these pop-up books, however, are generally done by hand, and given the lack of expertise in this area, have necessitated the need for automated or computer-assisted design of paper pop-ups. This paper presents an automatic algorithm and the underlying theory for producing paper pop-up designs from 3D models. Existing studies on paper pop-ups have mainly focused on individual styles and proposed formulations for only a limited set of mechanisms. In our work, we design multi-style pop-ups by combining the formulations of previously studied styles with our derived validity conditions for box-style pop-ups. We use a mesh abstraction technique that fits volumetric primitives unto a 3D mesh, which are later automatically mapped to selected mechanisms. We also preserve important texture and shape contours using a hybrid object- and image-space approach. Finally, we generate printable design layouts and the corresponding assembly instructions to facilitate the actual production, which verifies the feasibility of our pop-ups.

Abstract: Origamic architecture (OA) is a form of papercraft that involves cutting and folding a single sheet of paper to produce a 3D pop-up, and is commonly used to depict architectural structures. Because of the strict geometric and physical constraints, OA design requires considerable skill and effort. In this paper, we present a method to automatically generate an OA design that closely depicts an input 3D model. Our algorithm is guided by a novel set of geometric conditions to guarantee the foldability and stability of the generated pop-ups. The generality of the conditions allows our algorithm to generate valid pop-up structures that are previously not accounted for by other algorithms. Our method takes a novel image-domain approach to convert the input model to an OA design. It performs surface segmentation of the input model in the image domain, and carefully represents each surface with a set of parallel patches. Patches are then modified to make the entire structure foldable and stable. Visual and quantitative comparisons of results have shown our algorithm to be significantly better than the existing methods in the preservation of contours, surfaces and volume. The designs have also been shown to more closely resemble those created by real artists.

Abstract: A paper sliceform or lattice-style pop-up is a form of papercraft that uses two sets of parallel paper patches slotted together to make a foldable structure. The structure can be folded flat, as well as fully opened (popped-up) to make the two sets of patches orthogonal to each other. Automatic design of paper sliceforms is still not supported by existing computational models and remains a challenge. We propose novel geometric formulations of valid paper sliceform designs that consider the stability, flat-foldability and physical realizability of the designs. Based on a set of sufficient construction conditions, we also present an automatic algorithm for generating valid sliceform designs that closely depict the given 3D solid models. By approximating the input models using a set of generalized cylinders, our method significantly reduces the search space for stable and flat-foldable sliceforms. To ensure the physical realizability of the designs, the algorithm automatically generates slots or slits on the patches such that no two cycles embedded in two different patches are interlocking each other. This guarantees local pairwise assembility between patches, which is empirically shown to lead to global assembility. Our method has been demonstrated on a number of example models, and the output designs have been successfully made into real paper sliceforms.

Abstract: This paper addresses the difficult problem of finding dense correspondence across images with large appearance variations. Our method uses multiple feature samples at each pixel to deal with the appearance variations based on our observation that pre-defined single feature sample provides poor results in nearest neighbor matching. We apply the idea in a flow-based matching framework and utilize the best feature sample for each pixel to determine the flow field. We propose a novel energy function and use dual-layer loopy belief propagation to minimize it where the correspondence, the feature scale and rotation parameters are solved simultaneously. Our method is effective and produces generally better results.

Abstract: While geometry reconstruction has been extensively studied, several shortcomings still exist. First, traditional geometry reconstruction methods such as geometric or photometric stereo only recover either surface depth or normals. Second, such methods require calibration. Third, such methods cannot recover accurate geometry in the presence of interreflections. In order to address these problems in a single system, we propose an approach to reconstruct geometry from light transport data. Specifically, we investigate the problem of geometry reconstruction from interreflections in a light transport matrix. We show that by solving a system of polynomial equations derived directly from the interreflection matrix, both surface depth and normals can be fully reconstructed. Our system does not require projector-camera calibration, but only make use of a calibration object such as a checkerboard in the scene to pre-determine a few known points to simplify the polynomial solver. Our experimental results show that our system is able to reconstruct accurate geometry from interreflections up to a certain noise level. Our system is easy to set up in practice.

Abstract: Dual photography is a well-known application of light transport acquired by a projector-camera system. By applying compressive sensing, compressive dual photography is a fast approach to acquire the light transport for dual photography. However, the reconstruction step in compressive dual photography can still take several hours before dual images can be synthesized because the entire light transport needs to be reconstructed from measured data. In this paper, we present a novel reconstruction approach that can directly and progressively synthesize dual images from measured data without the need of first reconstructing the light transport. We show that our approach can produce high-quality dual images in the order of minutes using only a thousand of samples. Our approach is most useful for previewing a few dual images, e.g., during light transport acquisition. As a by-product, our method can also perform low-resolution relighting of dual images. We also hypothesize that our method is applicable to reconstructing dual images in a single projector-multiple cameras system.

Abstract: We present a semi-automatic photographic recomposition approach that employs a semantics-preserving warp of the input image to enhance the visual dominance of the main subjects. Our method uses the tearable image warping method to shift the subjects against the background (and vice versa), so that their visual dominance is improved, and yet preserve the desired spatial semantics between the subjects and the background. The recomposition is guided by a measure of the resulting visual dominance of the main subjects. Our user experiment shows the effectiveness of the approach.

Abstract: Aligning image pairs with significant appearance change is a long standing computer vision challenge. Much of this problem stems from the local patch descriptors’ instability to appearance variation. In this paper we suggest this instability is due less to descriptor corruption and more the difficulty in utilizing local information to canonically define the orientation (scale and rotation) at which a patch’s descriptor should be computed. We address this issue by jointly estimating correspondence and relative patch orientation, within a hierarchical algorithm that utilizes a smoothly varying parameterization of geometric transformations. By collectively estimating the correspondence and orientation of all the features, we can align and orient features that cannot be stably matched with only local information. At the price of smoothing over motion discontinuities (due to independent motion or parallax), this approach can align image pairs that display significant inter-image appearance variations.

Abstract: We introduce a new image geometric transformation, named tearable image warping, for content-aware image retargeting and recomposition. In tearable image warping, an object is allowed to partially detached from the background during warping, which allows the background to warp more freely without distorting the object. The part of the object that is still attached to the background ensures that spatial semantics between the object and its environment is preserved. Compared to traditional non-homogeneous image warping, tearable warping produces retargeted results with less severe distortions, especially in cases of extreme retargeting. Compared to scene carving, tearable warping can better preserve the global context and achieve better scene consistency by preserving the semantic connectedness between an object and its environment. In addition, tearable warping is also able to alter the object-background relationship within the image, which makes it quite suitable for aesthetics-based image recomposition. We also show that tearable image warping is a unified approach of traditional non-homogeneous image warping and the cut-and-paste techniques.

Abstract: We present a new screen-space ambient occlusion (SSAO) algorithm that improves on the state-of-the-art SSAO methods in both performance and quality. Our method computes ambient occlusion (AO) values at multiple image resolutions and combines them to obtain the final, high-resolution AO value for each image pixel. It produces high-quality AO that includes both high-frequency shadows due to nearby, occluding geometry and low-frequency shadows due to distant geometry. Our approach only needs to use very small sampling kernels at every resolution, thereby achieving high performance without resorting to random sampling. As a consequence, our results do not suffer from noise and excessive blur, which are common of other SSAO methods. Therefore, our method also avoid the expensive, final blur pass commonly used in other SSAO methods. The use of multiple resolutions also helps reduce errors that are caused by SSAO’s inherent lack of visibility checking. Temporal incoherence caused by using coarse resolutions is solved with an optional temporal filtering pass. Our method produces results that are closer to ray-traced solutions than those of any existing SSAO method’s, while running at similar or higher frame rates than the fastest ones.

Abstract: Sand animation is a performance art technique in which an artist tells stories by creating animated images with sand. Inspired by this medium, we have developed a new multitouch digital artistic medium named SandCanvas that simplifies the creation of sand animations. SandCanvas also goes beyond traditional sand animation with tools for mixing sand animation with video and replicating recorded free-form hand gestures. In this paper, we analyze common sand animation hand gestures, present SandCanvas’s intuitive UI, and describe implementation challenges we encountered. We also present an evaluation with professional and novice artists that shows the importance and unique affordances of this new medium.

Abstract: A photograph that has visually dominant subjects in general induces stronger aesthetic interest. Inspired by this, we have developed a new approach to enhance image aesthetics through saliency retargeting. Our method alters low-level image features of the objects in the photograph such that their computed saliency measurements in the modified image become consistent with the intended order of their visual importance. The goal of our approach is to produce an image that can redirect the viewers’ attention to the most important objects in the image, and thus making these objects the main subjects. Since many modified images can satisfy the same specified order of visual importance, we trained an aesthetics score prediction model to pick the one with the best aesthetics. Results from our user experiments support the effectiveness of our approach.

Abstract: We present a new screen-space ambient occlusion (SSAO) algorithm that improves on the state-of-the-art SSAO methods in both speed and image quality. Our method computes ambient occlusion (AO) for multiple image resolutions and combines them to obtain the final high-resolution AO. It produces high-quality AO that includes details from small local occluders to low-frequency occlusions from large faraway occluders. This approach allows us to use very small sampling kernels at every resolution, and thereby achieve high performance without resorting to random sampling, and therefore our results do not suffer from noise and excessive blur, which are common of SSAO. We use bilateral upsampling to interpolate lower-resolution occlusion values to prevent blockiness and occlusion leaks. Compared to existing SSAO methods, our method produces results closer to ray-traced solutions, while running at comparable or higher frame rates than the fastest SSAO method.

Abstract: We propose a single-image, shift-invariant motion deblurring approach where the blur kernel is directly estimated from light streaks in the blurred image. Combining with the sparsity constraint, the blur kernel can be solved quickly and accurately from a user input region containing a light streak. This kernel can then be applied to state-of-the-art single-image motion deblurring methods to restore the sharp image. As our approach does not require verification of the blur kernel against the blurred image, the deblurring can be performed quickly enough for interactive use. For example, our method can be used for interactively revealing scene details in different image regions when the motion blur is not shift-invariant.

Abstract: We present a simple ray casting method to render a CSG product term. The primitives are input as polygon meshes. Our method uses the programmability on modern graphics hardware to capture at each pixel the depth values of all the primitives’ surfaces. By sorting these surface fragments in front-to-back order, we are able to find the CSG result at each pixel. Our method does not maintain additional fragment information, and deferred shading is used for the final rendering of the CSG result. Our method is general in that there is no special handling needed for intersection and subtraction operations, and non-convex primitives are treated equally as convex primitives. All previous CSG rendering algorithms may not produce correct CSG result if any of the primitives is not entirely between the near and far planes of the view frustum. This can be very inconvenient as large invisible primitives may prevent a close-up view of the CSG result. Our method can deal with this problem with a small extension. In case if the CSG result is intersected by the near plane, our method even produces solid cutaway views.

Abstract: We present a saliency-enhanced method for the classification of professional photos and snapshots. First, we extract the salient regions from an image by utilizing a visual saliency model. We assume that the salient regions contain the photo subject. Then, in addition to a set of discriminative global image features, we extract a set of salient features that characterize the subject and depict the subject-background relationship. Our high-level perceptual approach produces a promising 5-fold cross-validation (5-CV) classification accuracy of 78.8%, significantly higher than existing approaches that concentrate mainly on global features.

Abstract: We present an approach to automatically register a large set of color images to a 3D geometric model. The problem arises from the modeling of real-world environments, where surface geometry is acquired using range scanners whereas the color information is separately acquired using untracked and uncalibrated cameras. Our approach constructs a sparse 3D model from the color images using a multiview geometry technique. We project special light patterns onto the scene surfaces to increase the robustness of the multiview geometry reconstruction. The sparse model is then approximately aligned with the detailed model. Planes found in the detailed model are exploited to refine the registration. Finally, the registered color images are mapped to the detailed model using weighted blending, with careful consideration of occlusion and the preservation of image details.

Abstract: We present a simple method to render complex 3D models at interactive rates using real-time displacement mapping. We use an octree to decompose the 3D model into a set of height fields and display the model by rendering the height fields using per-pixel displacement mapping. By simply rendering the faces of the octree voxels to produce fragments for ray-casting on the GPU, and with straightforward transformation of view rays to the displacement map’s local space, our method is able to accurately render the object’s silhouettes with very little special handling. The algorithm is especially suitable for fast visualization of high-detail point-based models, and models made up of unprocessed triangle meshes that come straight from range scanning. This is because our method requires much less preprocessing time compared to the traditional triangle-based rendering approach, which usually needs a large amount of computation to preprocess the input model into one that can be rendered more efficiently. Unlike the point-based rendering approach, the rendering efficiency of our method is not limited by the number of input points. Our method can achieve interactive rendering of models with more than 300 millions points on standard graphics hardware.

Abstract: We present an analytical method to estimate the absolute registration error bounds if two surfaces were to be aligned using the ICP (Iterative Closest Point) algorithm. The estimation takes into account (1) the amount of overlap between the surfaces, (2) the noise in the surface points’ positions, and (3) the geometric constraint on the 3D rigid-body transformation between the two surfaces. Given a required confidence level, the method of estimation enables us to predetermine the registration accuracy of two overlapping surfaces. This is very useful for automated range acquisition planning where it is important to ensure that the next scan to be acquired can be registered to the previous scans within the desired accuracy. We demonstrate a view-planning system that incorporates our estimation method in the selection of good candidate views for the range acquisition of indoor environments.

Abstract: We present a new and efficient next-best-view algorithm for 3D reconstruction of indoor scenes using active range sensing. To evaluate each view, we have formulated a general view metric that can include many real-world acquisition constraints and quality requirements on the resulting 3D model. We overcome the computation difficulty of evaluating this function by using an adaptive hierarchical approach to exploit the various spatial coherences inherent in the acquisition constraints and quality requirements. Experimental results show large speedups over the straightforward method used by many previous algorithms. The approach allows us to compute with a highly-detailed partial scene model and to exhaustively sample the entire 3D view space at high resolution. Our hierarchical view evaluation algorithm can also take into account each view’s sensitivity to the potential scanner positioning errors. We have also developed a metric to estimate whether the scan to be acquired from each candidate view can be accurately registered to the previous scans.

Abstract: We recently proposed a new and efficient next-best-view algorithm for 3D reconstruction of indoor scenes using active range sensing. We overcome the computation difficulty of evaluating the view metric function by using an adaptive hierarchical approach to exploit the various spatial coherences inherent in the acquisition constraints and quality requirements. The impressive speedups have allowed our NBV algorithm to become the first to be able to exhaustively evaluate a large set of 3D views with respect to a large set of surfaces, and to include many practical acquisition constraints and quality requirements. The success of the algorithm is greatly dependent on the implementation efficiency of the constraint and quality evaluations. In this paper, we describe the algorithmic details of the hierarchical view evaluation, and present efficient algorithms that evaluate sensing constraints and surface sampling densities between a view volume and a surface patch instead of simply between a single view point and a surface point. The presentation here provides examples for the design of efficient algorithms for new sensing constraints.

Abstract: Immersive electronic books (IEBooks) for surgical training will let surgeons explore previous surgical procedures in 3D. The authors describe the techniques and tools for creating a preliminary IEBook embodying some of the basic concepts.

Abstract: We describe an approach for automatically registering color images with 3D laser scanned models. We use the chi-square statistic to compare color images to polygonal models texture mapped with acquired laser reflectance values. In complicated scenes we find that the chi-square test is not robust enough to permit an automatic global registration approach. Therefore, we introduce two techniques for obtaining initial pose estimates that correspond to a coarse alignment of the data. The first method is based on rigidly attaching a camera to a laser scanner and the second utilizes object tracking to decouple these imaging devices. The pose estimates serve as an initial guess for our optimization method, which maximizes the chi-square statistic over a local space of transformations in order to automatically determine the proper alignment.

Abstract: We introduce and present preliminary results for a hybrid display system combining head mounted and projector-based displays. Our world is motivated by a surgical training application where it is necessary to simultaneously provide both a high-fidelity view of a central close up task (the surgery) and visual awareness of objects and events in the surrounding environment. In this article, we motivate the use of a hybrid display system, discuss previous work, describe a prototype along with methods for geometric calibration, and present results from a controlled human subject experiment.This article is an invited resubmission of work presented at IEEE Virtual Reality 2003. The article has been updated and expanded to include (among other things) additional related work and more details about the calibration process.

Abstract: We present a case study in the use of virtual environment technology for cultural heritage applications, describing a collaborative effort to construct two cultural heritage exhibits for a five month exhibition at the New Orleans Museum of Art. To illustrate the factors that shape museum exhibit design, we explore the initial conceptual phase and discuss our reasons for choosing certain designs. We describe the two exhibits that we built in turn, focusing on equipment and on robustness. Although little went awry during the exhibition, we explain how certain equipment did fail and how we had prepared for such crises by keeping spare equipment on-site. Finally, we report on the success of the undertaking and close with some thoughts and advice for researchers attempting similar museum-oriented projects.

Abstract: Autonomous range acquisition for 3D modeling requires reliable range registration, for both the precise localization of the sensor and combining the data from multiple scans for view-planning computation. We introduce and present a novel approach to improve the reliability and robustness of the ICP (Iterative Closest Point) 3D shape registration algorithm by smoothing the shapes surface into multiple resolutions. These smoothed surfaces are used in place of the original surface in a coarse-to-fine manner during registration, which allows the algorithm to avoid being trapped at local minima close to the global optimal solution. We used the technique of multiresolution analysis to create the smoothed surfaces efficiently. Besides being more robust, convergence is generally much faster, especially when combined with the point-to-plane error metric of Chen and Medioni. Since the point-to-plane error metric has no closed-form solution, solving it can be slow. We introduce a variant of the ICP algorithm that has convergence rate close to it but still uses the closed-form solution techniques (SVD or unit quaternion methods) of the original ICP algorithm.

Abstract: We introduce and present preliminary results for a hybrid display system combining head-mounted and projector-based displays. Our work is motivated by a surgical training application, where it is necessary to simultaneously provide both a high-fidelity view of a central close-up task (the surgery) and visual awareness of objects and events in the surrounding environment. In particular, for trauma surgeons it would be valuable to learn to work in an environment that is realistically filled with both necessary and distracting objects and events. In this paper, we motivate the use of a hybrid display system, discuss previous work, describe a prototype along with methods for geometric calibration, and present results from a controlled human subject experiment.

Abstract: This paper presents a method to compute a view frustum for a 3D object viewed from a given viewpoint, such that the object is completely enclosed in the frustum and the object’s image area is also near-maximal in the given 2D rectangular viewing region. This optimization can be used to improve the resolution of shadow maps and texture maps for projective texture mapping. Instead of doing the optimization in 3D space to find a good view frustum, our method uses a 2D approach. The basic idea of our approach is as follows. First, from the given viewpoint, a conveniently-computed view frustum is used to project the 3D vertices of the object to their corresponding 2D image points. A tight 2D bounding quadrilateral is then computed to enclose these 2D image points. Next, considering the projective warp between the bounding quadrilateral and the rectangular viewing region, our method applies a technique of camera calibration to compute a new view frustum that generates an image that covers the viewing region as much as possible.

Abstract: This paper reports on early progress with the use of immersive virtual reality technology for trauma surgery training. We discuss our technical goals and the application area, and then describe our work to date. The need to create a system that can be used by overworked, highly time-constrained surgeons and surgical trainees has affected many of our decisions, from the type of displays used to the focus on time navigation (to let trainees experience important moments and skip well-understood ones) to the use of easily-learned traditional 2D interfaces (vs. more demanding innovative 3D interfaces) for some of the interaction methods. This three-year research project, which is just entering its second year, is supported by a National Science Foundation Information Technology Research grant for collaborative research between groups at Brown University and the University of North Carolina at Chapel Hill.

Abstract: Current blending methods in image-based rendering use local information such as "deviations from the closest views" to find blending weights. They include approaches such as view-dependent texture mapping and blending fields used in unstructured lumigraph rendering. However, in the presence of depth discontinuities, these techniques do not provide smooth transitions in the target image if the intensities of corresponding pixels in the source images are significantly different (e.g. due to specular highlights). In this paper, we present an image blending technique that allows the use of global visibility and occlusion constraints. Each blending weight now has a global component and a local component, which, respectively, are due to the view-independent and the view-dependent contributions of the source images. Being view-independent, the global components can be computed in a pre-processing stage. Traditional graphics hardware is exploited to accelerate the computation of the global blending weights.

Abstract: We introduce an idea and some preliminary results for a new projector-based approach to re-creating real and imagined sites. Our goal is to achieve re-creations that are both visually and spatially realistic, providing a small number of relatively unencumbered users with a strong sense of immersion as they jointly walk around the virtual site. Rather than using head-mounted or general-purpose projector-based displays, our idea builds on previous projector-based work on spatially-augmented reality and shader lamps. Using simple white building blocks we construct a static physical model that approximates the size, shape, and spatial arrangement of the site. We then project dynamic imagery onto the blocks, transforming the lifeless physical model into a visually faithful reproduction of the actual site. Some advantages of this approach include wide field-of-view imagery, real walking around the site, reduced sensitivity to tracking errors, reduced sensitivity to system latency, auto-stereoscopic vision, the natural addition of augmented virtuality and the provision of haptics. In addition to describing the major challenges to (and limitations of) this vision, in this paper we describe some short-term solutions and practical methods, and we present some proof-of-concept results.

Abstract: Traditional user interfaces for off-the-desktop applications are designed to display the output on flat 2D surfaces while the input is with 2D or 3D devices. In this paper, we focus on projector-based augmented reality applications. We describe a framework to easily incorporate the interaction on a continuum of display surfaces and input devices. We first create a 3D understanding of the relationship between the user, the projectors and the display surfaces. Then we use some new calibration and rendering techniques to create a simple procedure to effectively illuminate the surfaces. We describe various underlying techniques and discuss the results in the context of three different applications.

Abstract: We describe a new paradigm for three-dimensional computer graphics, using projectors to graphically animate physical objects in the real world. The idea is to replace a physical object—with its inherent color, texture, and material properties—with a neutral object and projected imagery, reproducing the original (or alternative) appearance directly on the object. Because the approach is to effectively "lift" the visual properties of the object into the projector, we call the projectors shader lamps. We address the central issue of complete and continuous illumination of non-trivial physical objects using multiple projectors and present a set of new techniques that makes the process of illumination practical. We demonstrate the viability of these techniques through a variety of table-top applications, and describe preliminary results to reproduce life-sized virtual spaces.

Abstract: This paper presents a framework that uses the outputs of model simplification to guide the construction of bounding volume hierarchies for use in, for example, collision detection. Simplified models, besides their application to multiresolution rendering, can provide clues to the object’s shape. These clues help in the partitioning of the object’s model into components that may be more tightly bounded by simple bounding volumes. The framework naturally employs both the bottom-up and the top-down approaches of hierarchy building, and thus can have the advantages of both approaches. Experimental results show that our method built on top of the framework can indeed improve the bounding volume hierarchy, and as a result, significantly speedup the collision detection.

Abstract: This paper presents a practical technique to automatically compute approximations of polygonal representations of 3D objects. It is based on a previously developed model simplification technique which applies vertex-clustering. Major advantages of the vertex-clustering technique are its low computational cost and high data reduction rate, and thus suitable for use in interactive applications. This paper advances the technique with careful consideration of approximation quality and smoothness in transitions between different levels of simplification, while maintaining its efficiency and effectiveness. Its major contributions include: accuracy in grading vertices for indication of their visual importance, robustness in clustering for better preservation of important features and consistencies between levels of simplification, thick-lines with dynamic normals to maximize visual fidelity, and exploitation of object and image space relationship for levels-of-simplification determination.

Abstract: This dissertation presents a new and efficient next-best-view algorithm for 3D reconstruction of indoor environments using active range sensing. A major challenge in range acquisition for 3D reconstruction is an efficient automated view planning algorithm to determine a sequence of scanning locations or views such that a set of acquisition constraints and requirements is satisfied and the object or environment of interest can be satisfactorily reconstructed. Due to the intractability of the view planning problem and the lack of global geometric information, a greedy approach is adopted to approximate the solution. A practical view metric is formulated to include many real-world acquisition constraints and reconstruction quality requirements. This view metric is flexible to allow trade-offs between different requirements of the reconstruction quality. A major contribution of this work is the application of a hierarchical approach to greatly accelerate the evaluation of the view metric for a large set of views. This is achieved by exploiting the various spatial coherences in the acquisition constraints and reconstruction quality requirements when evaluating the view metric. The hierarchical view evaluation algorithm is implemented in a view planning system targeted for the acquisition of indoor environments using a monostatic range scanner with 3D pose. The results show great speedups over the straightforward method used in many previous algorithms. The view planning system has also been shown to be robust for real-world application.
The dissertation also describes how the view metric can be generalized to incorporate general acquisition constraints and requirements, and how the hierarchical view evaluation algorithm can be generalized to scanners with general pose, and to scanners with bistatic sensors. A simple extension is also proposed to enable the hierarchical view evaluation algorithm to take into account each view’s sensitivity to the potential pose errors in the physical positioning of the scanner.
A computed new view must produce a range image that can be accurately registered to the previous scans. In this work, a metric is developed to estimate the registration accuracy of the views. This metric considers the amount of overlap, the range measurement errors, and the shape complexity of the surfaces.

Abstract: In this technical report, we derive some conditions that allow the ICP (Iterative Closest Point) surface registration algorithm to attain some absolute accuracy when aligning two surfaces.

Abstract: The Iterative Closest Point (ICP) algorithm that uses the point-to-plane error metric has been shown to converge much faster than one that uses the point-to-point error metric. At each iteration of the ICP algorithm, the change of relative pose that gives the minimal point-to-plane error is usually solved using standard nonlinear least-squares methods, which are often very slow. Fortunately, when the relative orientation between the two input surfaces is small, we can approximate the nonlinear optimization problem with a linear least-squares one that can be solved more efficiently. We detail the derivation of a linear system whose least-squares solution is a good approximation to that obtained from a nonlinear optimization.

Introduction: The HiBall wand is an elongated hard plastic that can be attached rigidly to the bottom of a HiBall. The other end of the wand is a moderately-sharp metal tip. In the HMD Lab at UNC-Chapel Hill, it is a convenient device for measuring the 3D position of any point in a space where the HiBall can be tracked by an optical ceiling tracker.
. . .
To use the tip of the wand to measure the 3D position of a point with respect to the ceiling coordinate frame, we first need to know the tip's 3D position in the HiBall's local coordinate frame. If the tip's position in the HiBall coordinate frame is known, we can always use the HiBall's current pose in the ceiling coordinate frame to express the tip’s position with respect to the ceiling coordinate frame.
This article explains a method to calibrate the wand—to find the tip’s position in the HiBall coordinate frame.

Introduction: In many virtual reality (VR) and augmented reality (AR) applications, view-dependent images of the virtual worlds are often displayed for the users. These images can be displayed on computer monitors, head-mounted displays, or projected by projectors onto some surfaces. In order to produce perspective-correct images as viewed by a user, the positions of the user’s eyes must be known when generating the images. A way to get the positions of the eyes (viewpoints) is to use a tracking device.
. . .
This article explains a method to calibrate the viewpoints with respect to a tracker—to find the eyes’ positions in the target coordinate frame.

Introduction: We will derive (and prove) a method to achieve perspective-correct interpolation by linear interpolation in the screen space. During rasterization of linear graphics primitives, such as lines and polygons, straightforward screen-space linear interpolation of vertex attributes generally does not produce perspective correct results.
. . .
In spite of this, it is still possible to obtain perspective correct results by linearly interpolating in the screen space. This can be done by interpolating the values of some functions of the attributes, instead of interpolating the attributes directly. Each interpolated result is then transformed by another function (the inverse function) to get the final attribute value at the desired point in the screen space. You will see that these functions make use of the z-values of the vertices.

Abstract: This paper looks at the motivation for simulating painting directly on 3D objects, and investigates the main issues faced by such systems. These issues include the provision of natural user interfaces, the reproduction of realistic brush effects and the surface parameterization for texture mapping so that the results of the painting can be stored on texture maps. The paper further investigates the issues involved in using a haptic interface for simulating 3D painting, and the issues in surface parameterization for texture mapping with application to 3D painting. A survey of some work related to 3D painting, haptic rendering and surface parameterization for texture mapping is presented.