Ray-tracing triangular trimmed free-form surfaces

This paper presents a new approach to rendering triangular algebraic free-form surfaces. A hierarchical subdivision of the surface with associated tight bounding volumes provides for quick identification of the surface regions likely to be hit by a ray. For each leaf of the hierarchy, an approximation to the corresponding surface region is stored. The approximation is used to compute a good starting point for the iteration, which ensures rapid convergence. Trimming curves are described by a tree of trimming primitives, such as squares, circles, polygons, and free-form curves, combined with Boolean operations. For trimmed surfaces, an irregular adaptive subdivision is constructed to quickly eliminate all parts outside the trimming curve from consideration during rendering. Cost heuristics are introduced to optimize the rendering time further     

基于旋转曲面场景的快速光线跟踪算法

针对旋转曲面场景提出一种基于综合包围盒技术快速光线跟踪算法。根据二次曲线的局部单调性原理,将母线划分成多个单调区间,连接所有单调区间构造一棵二叉树,在光线跟踪阶段对每个单调区间再剖分,得到的子区间作为二叉树的叶子节点,使用综合包围壳方法为每个子区间计算合适的包围壳。实验结果表明该算法对旋转曲面场景逼近程度好,绘制的图形质量高,平均绘制速率比Kajiya传统算法提高40％。     

Three improvements of the ray tracing algorithm for CSG trees

Ray tracing is one of the most powerful techniques for image synthesis today. The most beautiful pictures in computer graphics were made by this method. Unfortunately, the computational expense and the computation time are very high. For reduction of computational effort in this paper three improvements for the ray tracing algorithm will be introduced. Two of them are extensions of existing improvements, the third is a new idea: (1) use of enclosures in the object tree; (2) bounding the ray length and (3) dynamical temporary object trees. These improvements are independent and therefore can be used separately or together. They are for ray tracing objects described in a CSG model. The improvements can also be used for secondary rays.     

直线与Bzier曲面求交的分割迭代综合法

本文所介绍的适合光线跟踪算法的直线与B(?)zier曲面求交的方法,采用了空间一般位置的圆柱和长方体作为曲面包围盒,并综合利用了分割法的稳定性和牛顿迭代法的效率,从而加快了用光线跟踪技术生成Bzier曲面的真实感图形的速度。     

Reliable Collision Detection for Time-Dependent Parametric Surfaces

We improve on an algorithm by Von Herzen, Barr, and Zatz (HBZ) to detect geometric collisions between pairs of time-dependent parametric surfaces. The HBZ algorithm uses upper bounds on the parametric derivatives to guarantee detection of collisions and near misses, thus avoiding the defects of algorithms which sample the surfaces, possibly missing sharp spikes. Unfortunately, the user of the HBZ algorithm must supply not only routines computing the surface functions, but also routines bounding every component in the Jacobian of these surface functions over an arbitrary parametric range. Although they give helpful analyses for several types of surfaces, HBZ admit the need to provide Jacobian bounding routines as a disadvantage.We propose using interval arithmetic to bound functional values over a parametric input range, thus eliminating the need for the Jacobian entirely. Our interval version of the collision detection algorithm assumes neither bounded differentiability nor satisfaction of the Lipschitz criterion. Therefore, our code can detect geometric collisions for the much larger class of surface functions for which bounds on the function values can be computed using interval arithmetic. We contrast our code to that of HBZ and give timing comparisons.     

Efficient Hierarchical Refinement and Clustering for Radiosity in Complex Environments

Generating accurate radiosity solutions of very complex environments is a time-consuming problem. We present a rapid hierarchical algorithm that enables such solutions to be computed quickly and efficiently. Firstly, a new technique for bounding the error in the transfer of radiosity between surfaces is discussed, incorporating bounds on form factors, visibility, irradiance, and reflectance over textured surfaces. This technique is then applied to the problem of bounding radiosity transfer between clusters of surfaces, leading to a fast, practical clustering algorithm that builds on the previous work of Sillion¹. Volumes are used to represent clusters of small surfaces, but unlike previous algorithms, the orientations of surfaces inside each cluster are accounted for in both the error bound and radiosity transfer. This enables an accurate solution to be generated very efficiently, and results are presented demonstrating the performance of the algorithm on a variety of complex models, one containing almost a quarter of a million initial surfaces.     

Ray Tracing Free-Form B-Spline Surfaces

We present a method for using ray tracing to render spline surfaces?one that is suitable for any object generated from control vertices via tensor-product B-splines. The method derives from kajiya's work on ray tracing procedurally defined surfaces1 and makes use of two preprocessing steps. One involves the controlvertex refinement recurrences due to Riesenfeld et. al.2, and the second generates a tree of nested bounding boxes. Intersection testing involves running Kajiya's algorithm on the tree, followed by two to three (on the average) iterations of Newton's method.     

Fast Insertion‐Based Optimization of Bounding Volume Hierarchies

We present an algorithm for fast optimization of bounding volume hierarchies (BVH) for efficient ray tracing. We perform selective updates of the hierarchy driven by the cost model derived from the surface area heuristic. In each step, the algorithm updates a fraction of the hierarchy nodes to minimize the overall hierarchy cost. The updates are realized by simple operations on the tree nodes: removal, search and insertion. Our method can quickly reduce the cost of the hierarchy constructed by the traditional techniques, such as the surface area heuristic. We evaluate the properties of the proposed method on fourteen test scenes of different complexity including individual objects and architectural scenes. The results show that our method can improve a BVH initially constructed with the surface area heuristic by up to 27% and a BVH constructed with the spatial median split by up to 88%.     

Fast Ray Tracing NURBS Surfaces

In this paper,a new algorithm wit extrapolation process for computing the ray/surface intersection is presented.Also,a ray is defined to be the intersection of two planes,which are non-orthogonal in general,in such a way that the number of multiplication operations is reduced.In the preprocessing step,NURBS surfaces are subdivded adaptively into rational Bezier patches.Parallelepipeds are used to enclose the respective patches as tightly as possible Therefore,for each ray that hits the enclosure(i.e.,parallelepiped)of a patch the intersection points with the parallelepiped‘s faces can be used to yield a good starting point for the following iteration.The improved Newton iteration with extrapolation process saves CPU time by reducing the number of iteration steps.The intersection scheme is facter than previous methods for which published performance data allow reliable comparison.The method may also be used to speed up tracing the intersection of two parametric surfaces and oter operations that need Newton iteration.     

一种裁剪参数曲面的有限元网格剖分方法

在板料冲压成形模拟分析中,从CAD系统输入的模具的曲面模型包含大量的裁剪参数曲面,曲面之间的相邻关系复杂,针对这种曲面模型的特点,提出了一种裁剪参数曲面的有限元网格剖分方法,单个裁剪参数曲面采用非约束边界的等参数映射法,各个裁剪参数曲面各自独立地网格剖分产生了网格单元后,再将各个裁剪参数曲面的网格单元合并为单元相容,即单元间无裂缝和覆盖的网格模型,这种方法适合于需要大量裁剪参数曲面拼合的复杂曲面模型,如汽车覆盖件模型的网格剖分。     

Rapid and Accurate Contact Determination between Spline Models using ShellTrees

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree , that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bézier patches as part of pre-processing. At runtime it dynamically computes a tight fitting axis-aligned bounding box across each Bézier patch and efficiently checks all such boxes for overlap. Using off-line and on-line techniques for tree construction, our algorithm computes ShellTrees for Bézier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.     

Approximating Parametric Curves With Strip Trees Using Affine Arithmetic

We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation information given by affine arithmetic. As an application, we show how to compute approximate distance fields for parametric curves. ACM CSS: I.3.3 Computer Graphics—Curve, surface, solid, and object representations, G.1.2 Numerical Analysis—Approximation of surfaces and contours, G.1.0 Numerical Analysis—Interval arithmetic     

Automatic Creation of Object Hierarchies for Radiosity Clustering

Using object clusters for hierarchical radiosity greatly improves the efficiency and thus usability of radiosity computations. By eliminating the quadratic starting phase very large scenes containing about 100k polygons can be handled efficiently. Although the main algorithm extends rather easily to using object clusters, the creation of 'good' object hierarchies is a difficult task both in terms of construction time and in the way how surfaces or objects are grouped to clusters. The quality of an object hierarchy for clustering depends on its ability to accurately simulate the hierarchy of the energy flow in a given scene. Additionally it should support visibility computations by providing efficient ray acceleration techniques.
In this paper we will present a new approach of building hierarchies of object clusters. Our hybrid structuring algorithm provides accuracy and speed by combining a highly optimized bounding volume hierarchy together with uniform spatial subdivisions for nodes with regular object densities. The algorithm works without user intervention and is well suited for a wide variety of scenes. First results of using these hierarchies in a radiosity clustering environment are very promising and will be presented here.
The combination of very deep hierarchies (we use a binary tree) together with an efficient ray acceleration structure shifts the computational effort away from form factor and visibility calculation towards accurately propagating the energy through the hierarchy. We will show how an efficient single pass gathering can be used to minimize traversal costs.     

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.     

Solving nonlinear polynomial systems in the barycentric Bernstein basis

We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study.     

An efficient and robust contact algorithm for a compliant contact force model between bodies of complex geometry

Dynamic analysis of many mechanical systems often involves contacts among rigid bodies. When calculating the contact force with a compliant contact force model, a penetration depth and a contact reference frame (a contact point and normal and tangent directions) should be determined from the geometrical information of the rigid body surfaces. In order to improve the speed and robustness of the contact analysis, this paper proposes a contact search algorithm for surfaces composed of triangles. This algorithm is divided into two parts, the pre-search and the detailed search. In the pre-search, a bounding box tree and an overlap test are used to find intersecting triangle pairs, and triangle connectivity information is used to identify and separate multiple contact regions. Then an efficient and robust detailed search algorithm is proposed, where the penetration depth and contact reference frame are determined from the results of the pre-search. Finally, the contact force for each contact region is calculated from a modified compliant contact force model. Numerical examples are also presented to illustrate the accuracy and performance.     

A sparse matrix algorithm on the Boolean vector machine

The Boolean Vector Machine (BVM) is a large network of extremely small processors with very small memories operating in SIMD mode using bit serial arithmetic. Individual processors communicate via a hardware implementation of the Cube Connected Cycles (CCC) network. A prototype BVM with 2048 processing elements, each with 200 binary bits of memory, is currently being built using VLSI technology.

The BVM's bit-serial arithmetic and the small memories of individual processors are apparently a drawback to its effectiveness when applied to large numerical problems. In this paper we analyze an implementation of a basic matrix-vector iteration algorithm for sparse matrices on the BVM. We show that a 2²⁰ Pe BVM can deliver over 1 billion (10⁹) useful floating-point operations per second for this problem. The algorithm is expressed in a new language (BVL) which has been defined for programming the BVM.     

Topological correction of hypertextured implicit surfaces for ray casting

Hypertextures are a useful modelling tool in that they can add three-dimensional detail to the surface of otherwise smooth objects. Hypertextures can be rendered as implicit surfaces, resulting in objects with a complex but well defined boundary. However, representing a hypertexture as an implicit surface often results in many small parts being detached from the main surface, turning an object into a disconnected set. Depending on the context, this can detract from the realism in a scene, where one usually does not expect a solid object to have clouds of smaller objects floating around it. We present a topology correction technique, integrated in a ray casting algorithm for hypertextured implicit surfaces, that detects and removes all the surface components that have become disconnected from the main surface. Our method works with implicit surfaces that are C² continuous and uses Morse theory to find the critical points of the surface. The method follows the separatrix lines joining the critical points to isolate disconnected components.