Octree-R: an adaptive octree for efficient ray tracing

Ray tracing requires many ray-object intersection tests. A way of reducing the number of ray-object intersection tests is to subdivide the space occupied by objects into many nonoverlapping subregions, called voxels, and to construct an octree for the subdivided space. We propose the Octree-R, an octree-variant data structure for efficient ray tracing. The algorithm for constructing the Octree-R first estimates the number of ray-object intersection tests. Then, it partitions the space along the plane that minimizes the estimated number of ray-object intersection tests. We present the results of experiments for verifying the effectiveness of the Octree-R. In the experiment, the Octree-R provides a 4% to 47% performance gain over the conventional octree. The result shows the more skewed the object distribution (as is typical for real data), the more performance gain the Octree-R achieves     

A new space subdivision for ray tracing CSG solids

Ray tracing successfully creates realistic images of constructive solid geometry (CSG) solids. We describe a nonuniform space subdivision scheme that reduces both the number of ray-object intersection computations and point classifications. Our method uses the face planes of the primitives' S-bounds in a bottom-up fashion and produces a subdivision wherein the localized CSG tree in each leaf voxel is greatly minimized. The use of S-bounds in the space subdivision effectively reduces the number of intersection computations as well. The reduction of the localized CSG tree in turn further reduces the number of intersection computations and point classifications. We briefly review existing methods for ray tracing CSG solids, describe our proposed space subdivision method, discuss our implementation and compare it to Bouatouch's (1987) method, and summarize our test results     

Spacetime ray tracing for animation

Techniques for the efficient ray tracing of animated scenes are presented. They are based on two central concepts: spacetime ray tracing, and a hybrid adaptive space subdivision/boundary volume technique for generating efficient, nonoverlapping hierarchies of bounding volumes. In spacetime ray tracing, static objects are rendered in 4-D space-time using 4-D analogs to 3-D techniques. The bounding volume hierarchy combines elements of adaptive space subdivision and bounding volume techniques. The quality of hierarchy and its nonoverlapping character make it an improvement over previous algorithms, because both attributes reduce the number of ray/object intersections that must be computed. These savings are amplified in animation because of the much higher cost of computing ray/object intersections for motion-blurred animation. It is shown that it is possible to ray trace large animations more quickly with space-time ray tracing using this hierarchy than with straightforward frame-by-frame rendering     

Display techniques and boundary evaluation of a Sweep-CSG modeller

Among the various techniques for displaying solid objects, ray tracing is the most popular method for sweep-generated objects, owing to its simplicity and effectiveness. The main problem in ray tracing is to find the point of intersection between the ray and the object. By taking consideration of the special features of a surface generated by sweep, the ray/object intersection problem can be reduced to 2-D planar problem. This paper presents a raycasting technique for displaying Sweep-CSG-represented solids. This technique works directly on the Sweep-CSG representation and does not require explicit boundary information. Boundary information is, however essential for line-drawing outputs. In this paper, boundary-evaluation techniques for obtaining edges of a Sweep-CSG solid are described. Special techniques for evaluating the boundaries of a solid generated by sweeping another solid are also discussed.     

Data partitioning for parallel solid modelling

Solid modelling involves processing large amounts of geometric data. Distributed processing is a promising technique for improving the speed of computationally intensive processes. Solid modelling is thus a good candidate for parallel processing. We present a method for distributing entities of solid models in an array of processors for intersection tests in evaluating boolean operations. We employ distributed boundary representation and a recursive spatial subdivision technique for data partitioning. Parallel algorithms distribute entities among the array of processors mapped to a set of 3D rectangular regions in the object space. Entities intersecting or residing in the intersection regions of the objects are distributed. An experimental system was implemented on a DECmpp 12000/Sx/8K distributed memory SIMD computer.     

Ray tracing: A quantitative analysis and a new practical algorithm

We present a new method to accelerate the process of finding nearest ray-object intersections in ray tracing. The algorithm consumes an amount of memory more or less linear in the number of objects. The basic ideas can be characterized with a modified BSP tree and plane traversal. Plane traversal is a fast linear time algorithm to find the closest intersection point in a list of bounding volumes hit by a ray. We use plane traversal at every node of the high outdegree BSP tree. Our implementation is competitive to fast ray-tracing programs. We present a benchmark suite that allows for an extensive comparison of ray-tracing algorithms.     

Analysis of an algorithm for fast ray tracing using uniform space subdivision

Ray tracing is becoming popular as the best method of rendering high quality images from three dimensional models. Unfortunately, the computational cost is high. Recently, a number of authors have reported on ways to speed up this process by means of space subdivision which is used to minimize the number of intersection calculations. We describe such an algorithm together with an analysis of the factors which affect its performance. The critical operation of skipping an empty space subdivision can be done very quickly, using only integer addition and comparison. A theoretical analysis of the algorithm is developed. It shows how the space and time requirements vary with the number of objects in the scene.     

An intersection algorithm based on Delaunay triangulation

A robust method for finding points of intersection of line segments in a 2-D plane is presented. The plane is subdivided by Delaunay triangulation to localize areas where points of intersection exist and to guarantee the topological consistency of the resulting arrangement. The subdivision is refined by inserting midpoints recursively until the areas containing points of intersection are sufficiently localized. The method is robust in the sense that it does not miss points of intersection that are easily detectable when costly line-pair checking is performed. The algorithm is adaptive in the sense that most of the computational cost is incurred for the areas where finding points of intersection is difficult     

Estimation of planar curves, surfaces, and nonplanar space curvesdefined by implicit equations with applications to edge and range imagesegmentation

The author addresses the problem of parametric representation and estimation of complex planar curves in 2-D surfaces in 3-D, and nonplanar space curves in 3-D. Curves and surfaces can be defined either parametrically or implicitly, with the latter representation used here. A planar curve is the set of zeros of a smooth function of two variables x-y, a surface is the set of zeros of a smooth function of three variables x-y-z, and a space curve is the intersection of two surfaces, which are the set of zeros of two linearly independent smooth functions of three variables x-y-z For example, the surface of a complex object in 3-D can be represented as a subset of a single implicit surface, with similar results for planar and space curves. It is shown how this unified representation can be used for object recognition, object position estimation, and segmentation of objects into meaningful subobjects, that is, the detection of `interest regions' that are more complex than high curvature regions and, hence, more useful as features for object recognition     

基于退化多边形求交的多面体虚拟壳模型重构

三维模型的重建和表示是计算机图形和计算机视觉中一个重要的领域,其广泛应用于自动识别,工业自动化设计以及虚拟场景的重建。文中实现一个从照片序列重建三维物体多面体模型的系统,使用由轮廓恢复形体(SFS),通过经由轮廓光锥相交得到包围物体的虚拟壳。在系统中采用的共极线几何和增量运算把所有的三维的相交计算投射到二维平面的退化多边形求交来降低相交计算的复杂度。与传统多面体虚拟壳重构相比,算法有以下几点改进:在图像平面以退化多边形组织投影锥体和物体轮廓的交集,把任意锥面与物体轮廓的交集归一到一个退化多边形;基于退化多边形的二维平面上多边形快速相交算法。通过这些改进可以减少虚拟壳的生成时间并有助于实时绘制的实现。     

面向三角网格的自适应细分

细分曲面存在的一个问题是随着细分次数的增多,网格的面片数迅速增长,巨大的数据量使得细分后的模难以进行其它处理。针对这个问题,该文利用控制点的局部信息提出了一种基于Loop模式的自适应细分算法,利用该算法可避免在相对光滑处再细分,与正常细分相比,既大大减少了数据量,提高了模型的处理速度,又达到了对模型进行细分的目的。     

Line-drawing algorithms for parallel machines

The fact that conventional line-drawing algorithms, when applied directly on parallel machines, can lead to very inefficient codes is addressed. It is suggested that instead of modifying an existing algorithm for a parallel machine, a more efficient implementation can be produced by going back to the invariants in the definition. Popular line-drawing algorithms are compared with two alternatives; distance to a line (a point is on the line if sufficiently close to it) and intersection with a line (a point on the line if an intersection point). For massively parallel single-instruction-multiple-data (SIMD) machines (with thousands of processors and up), the alternatives provide viable line-drawing algorithms. Because of the pixel-per-processor mapping, their performance is independent of the line length orientation     

Biconic subdivision of surfaces of revolution and its applications in intersection problems

This paper presents a novel method for the subdivision of surfaces of revolution. We develop a new technique for approximating the genertrix by a series of pairs of conic sections. By using an error estimate based on convex combination, an efficient least-squares approach is proposed that yields near-optimal fitting. The resulting surface approximation is shown to be more efficient than other tessellation methods in terms of the number of fitting segments. This in turn allows us to implement efficient and robust algorithms for such surfaces. In particular, novel intersection techniques based on the proposed subdivision method are introduced for the two most fundamental types of intersections – line/surface and surface/surface intersections. The experimental results show that our method outperforms conventional methods significantly in both computing time and memory cost.     

Shape-based indexing scheme for camera view invariant 3-D object retrieval

Camera view invariant 3-D object retrieval is an important issue in many traditional and emerging applications such as security, surveillance, computer-aided design (CAD), virtual reality, and place recognition. One straightforward method for camera view invariant 3-D object retrieval is to consider all the possible camera views of 3-D objects. However, capturing and maintaining such views require an enormous amount of time and labor. In addition, all camera views should be indexed for reasonable retrieval performance, which requires extra storage space and maintenance overhead. In the case of shape-based 3-D object retrieval, such overhead could be relieved by considering the symmetric shape feature of most objects. In this paper, we propose a new shape-based indexing and matching scheme of real or rendered 3-D objects for camera view invariant object retrieval. In particular, in order to remove redundant camera views to be indexed, we propose a camera view skimming scheme, which includes: i) mirror shape pairing and ii) camera view pruning according to the symmetrical patterns of object shapes. Since our camera view skimming scheme considerably reduces the number of camera views to be indexed, it could relieve the storage requirement and improve the matching speed without sacrificing retrieval accuracy. Through various experiments, we show that our proposed scheme can achieve excellent performance.     

Pixel-selected ray tracing

An acceleration method based on an idea that T. Whitted (Commun. ACM, vol.23, no.6 pp.343-349, June 1980) presented on ray tracing is discussed. He proposed making antialiased images by hierarchical adaptive oversampling. The present authors use hierarchical adaptive undersampling to reduce the number of pixels whose intensity must be calculated by ray tracing. To implement pixel-selected ray tracing (PSRT), homogeneous regions in images must first be found. Generally, adaptive undersampling can result in some image-quality defects, because small objects and parts of thin or wedge-shaped objects may disappear when they are located between the initially sampled pixels. PSRT has an improved algorithm that uses pixels with the correct object information from among the sampled pixels to find pixels with erroneous color and correct them. Moreover, PRST uses ray-object intersection trees for precise classification of the homogeneity of regions and for fast intensity calculation in homogeneous regions. Experimental results are presented. They show that PSRT is two to nine times faster than standard ray tracing     

Linear Interval Estimations for Parametric Objects Theory and Application

The new concept of parametrized bounding volumes for parametric objects is proposed to replace the common compact bounding volumes like axis aligned bounding boxes and parallelepipeds. Linear Interval Estimations (LIEs) are developed as a realization of the discussed ideas. Two reliable methods for the computation of LIEs are introduced based on a new understanding of the use of affine arithmetics and a special application of Taylor Models. The particular structure of LIEs allows an effective intersection test of LIEs with rays, boxes and other LIEs. The test gives besides of a possible location of the intersection in object space information about affected parts in the parameter spaces of the enclosed objects. A subdivision algorithm for the intersection of two parametric surface patches with remarkable experimental results is presented as a possible application.     

基于改进扫描线算法的快速图形运算

提出了一个基于改进扫描线算法的快速图形运算方法。该算法把图形逻辑或拓扑运算和交点计算有机地结合起来,并给出了一种新的交点判断计算方法和基于点的逻辑运算方法,大大减少了图形运算中的冗余计算。该算法具有运算速度快Ｏ（ＮｌｏｇＮ）、空间要求少Ｏ（Ｎ＾１／２）等特点。     

An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques

Geometric set operations play an integral role in systems for CAD/CAM, for robot planning, and for modeling objects such as underground formations from empirical data. Two major issues in the implementation of geometric set operations are efficiency in the search for geometric intersections and effectiveness in the treatment of singular intersection cases. This article presents an algorithm for geometric set operations on planar polyhedral nonmanifold objects that addresses both these issues. First, an efficient search for geometric intersections is obtained by localizing the search to small regions of object space through a cellular subdivision scheme using the polytree data structure. Second, an effective treatment of singular intersection cases is obtained by mapping each singular intersection occurring in a region into one of a small set of cases.     

The visual hull concept for silhouette-based image understanding

Many algorithms for both identifying and reconstructing a 3-D object are based on the 2-D silhouettes of the object. In general, identifying a nonconvex object using a silhouette-based approach implies neglecting some features of its surface as identification clues. The same features cannot be reconstructed by volume intersection techniques using multiple silhouettes of the object. This paper addresses the problem of finding which parts of a nonconvex object are relevant for silhouette-based image understanding. For this purpose, the geometric concept of visual hull of a 3-D object is introduced. This is the closest approximation of object S that can be obtained with the volume intersection approach; it is the maximal object silhouette-equivalent to S, i.e., which can be substituted for S without affecting any silhouette. Only the parts of the surface of S that also lie on the surface of the visual hull can be reconstructed or identified using silhouette-based algorithms. The visual hull depends not only on the object but also on the region allowed to the viewpoint. Two main viewing regions result in the external and internal visual hull. In the former case the viewing region is related to the convex hull of S, in the latter it is bounded by S. The internal visual hull also admits an interpretation not related to silhouettes. Algorithms for computing visual hulls are presented and their complexity analyzed. In general, the visual hull of a 3-D planar face object turns out to be bounded by planar and curved patches     

Subspace Procrustes Analysis

Procrustes analysis (PA) has been a popular technique to align and build 2-D statistical models of shapes. Given a set of 2-D shapes PA is applied to remove rigid transformations. Later, a non-rigid 2-D model is computed by modeling the residual (e.g., PCA). Although PA has been widely used, it has several limitations for modeling 2-D shapes: occluded landmarks and missing data can result in local minima solutions, and there is no guarantee that the 2-D shapes provide a uniform sampling of the 3-D space of rotations for the object. To address previous issues, this paper proposes subspace PA (SPA). Given several instances of a 3-D object, SPA computes the mean and a 2-D subspace that can model rigid and non-rigid deformations of the 3-D object. We propose a discrete (DSPA) and continuous (CSPA) formulation for SPA, assuming that 3-D samples of an object are provided. DSPA extends the traditional PA, and produces unbiased 2-D models by uniformly sampling different views of the 3-D object. CSPA provides a continuous approach to uniformly sample the space of 3-D rotations, being more efficient in space and time. We illustrate the benefits of SPA in two different applications. First, SPA is used to learn 2-D face and body models from 3-D datasets. Experiments on the FaceWarehouse and CMU motion capture (MoCap) datasets show the benefits of our 2-D models against the state-of-the-art PA approaches and conventional 3-D models. Second, SPA learns an unbiased 2-D model from CMU MoCap dataset and it is used to estimate the human pose on the Leeds Sports dataset.