17601595
Geocube – GPU accelerated real-time rendering of transparency and translucency
We present a new method based on GPU acceleration for real-time transparency and translucency rendering. Our method computes refraction at both the front and back sides of a transparent object, as well as internal reflection, thus delivering interactive realistic transparency effects on a commodity PC. The real-time performance is made possible by a new acceleration data structure, called geocube, that enables the use of GPU for fast ray-surface intersection testing. In addition, within the same framework, we introduce the novel use of the mip-map for a hierarchical representation of a sequence of key prefiltered environment maps to simulate translucency. By taking ray depth into account and using GPU to interpolate the key filtered maps to produce the desired blurring effects, we achieve real-time realistic translucency rendering of slightly scattering media that allows show-through of background details.
16675497
Revisiting the [mu]-basis of a rational ruled surface
The µ-basis of a rational ruled surface P(s,t) = P0(s) + tP1(s) is defined in Chen et al. (Comput. Aided Geom. Design 18 (2001) 61) to consist of two polynomials p(x, y, z, s) and q(x, y, z, s) that are linear in x, y, z. It is shown there that the resultant of p and q with respect to s gives the implicit equation of the rational ruled surface; however, the parametric equation P(s, t) of the rational ruled surface cannot be recovered from p and q. Furthermore, the µ-basis thus defined for a rational ruled surface does not possess many nice properties that hold for the µ-basis of a rational planar curve (Comput. Aided Geom. Design 18 (1998) 803). In this paper, we introduce another polynomial r(x, y, z, s, t) that is linear in x, y, z and t such that p, q, r can be used to recover the parametric equation P(s, t) of the rational ruled surface; hence, we redefine the µ-basis to consist of the three polynomials p, q, r. We present an efficient algorithm for computing the newly-defined µ-basis, and derive some of its properties. In particular, we show that the new µ-basis serves as a basis for both the moving plane module and the moving plane ideal corresponding to the rational ruled surface.
14471402
Computing quadric surface intersections based on an analysis of plane cubic curves
Computing the intersection curve of two quadrics is a fundamental problem in computer graphics and solid modeling. We present an algebraic method for classifying and parameterizing the intersection curve of two quadric surfaces. The method is based on the observation that the intersection curve of two quadrics is birationally related to a plane cubic curve. In the method this plane cubic curve is computed first and the intersection curve of the two quadrics is then found by transforming the cubic curve by a rational quadratic mapping. Topological classification and parameterization of the intersection curve are achieved by invoking results from algebraic geometry on plane cubic curves. 2003 Elsevier Science (USA). All rights reserved.
2992545
Constrained 3D shape reconstruction using a combination of surface fitting and registration
We investigate 3D shape reconstruction from measurement data in the presence of constraints. The constraints may fix the surface type or set geometric relations between parts of an object's surface, such as orthogonality, parallelity and others. It is proposed to use a combination of surface fitting and registration within the geometric optimization framework of squared distance minimization (SDM). In this way, we obtain a quasi-Newton like optimization algorithm, which in each iteration simultaneously registers the data set with a rigid motion to the fitting surface and adapts the shape of the fitting surface. We present examples to show the applicability of our method to constrained 3D shape fitting for reverse engineering of CAD models and to high accuracy fitting with kinematic surfaces, which include surfaces of revolution (reconstructed from fragments of archeological pottery) and spiral surfaces, which are fitted to 3D measurement data of shells. Our optimization algorithm can combine registration of multiple scans of an object and model fitting into a single optimization process which is shown to be superior to the traditional procedure, which first registers the data and then fits a model to it.
14919460
Interpolation on quadric surfaces with rational quadratic spline curves
Abstract Given a sequence of points { X i } i =1 n on a regular quadric S : X T AX = 0 ⊂ E d , d ⩾ 3, we study the problem of constructing a G 1 rational quadratic spline curve lying on S that interpolates { X i } i =1 n . It is shown that a necessary condition for the existence of a nontrivial interpolant is ( X 1 T AX 2 )( X i T AX i +1 ) > 0, i = 1,2…, n − 1. Also considered is a Hermite interpolation problem on the quadric S : a biarc consisting of two conic arcs on S joined with G 1 continuity is used to interpolate two points on S and two associated tangent directions, a method similar to the biarc scheme in the plane (Bolton, 1975) or space (Sharrock, 1987). A necessary and sufficient condition is obtained on the existence of a biarc whose two arcs are not major elliptic arcs. In addition, it is shown that this condition is always fulfilled on a sphere for generic interpolation data.
7101460
On the Difference Method for Drawing Conic Arcs
Abstract The difference method is an efficient way to generate an inscribed polygon of a conic section. We address the implementation issues of the difference method, that is, how to choose the difference parameter and initial points so that the inscribed polygon has a minimal number of line segments and is within a given tolerance of the conic arc. We also discuss how the difference method can be used to draw conic arcs represented by rational quadratic Bezier curves.
3184000
Revealing true subspace clusters in high dimensions
Subspace clustering is one of the best approaches for discovering meaningful clusters in high dimensional space. One cluster in high dimensional space may be transcribed into multiple distinct maximal clusters by projecting onto different subspaces. A direct consequence of clustering independently in each subspace is an overwhelmingly large set of overlapping clusters which may be significantly similar. To reveal the true underlying clusters, we propose a similarity measurement of the overlapping clusters. We adopt the model of Gaussian tailed hyper-rectangles to capture the distribution of any subspace cluster. A set of experiments on a synthetic dataset demonstrates the effectiveness of our approach. Application to real gene expression data also reveals impressive meta-clusters expected by biologists.
17166482
Benchmarking the effectiveness of sequential pattern mining methods
Recently, there is an increasing interest in new intelligent mining methods to find more meaningful and compact results. In intelligent data mining research, accessing the quality and usefulness of the results from different mining methods is essential. However, there is no general benchmarking criteria to evaluate whether these new methods are indeed more effective compared to the traditional methods. Here we propose a novel benchmarking criteria that can systematically evaluate the effectiveness of any sequential pattern mining method under a variety of situations. The benchmark evaluates how well a mining method finds known common patterns in synthetic data. Such an evaluation provides a comprehensive understanding of the resulting patterns generated from any mining method empirically. In this paper, the criteria are applied to conduct a detailed comparison study of the support-based sequential pattern model with an approximate pattern model based on sequence alignment. The study suggests that the alignment model will give a good summary of the sequential data in the form of a set of common patterns in the data. In contrast, the support model generates massive amounts of frequent patterns with much redundancy. This suggests that the results of the support model require more post processing before it can be of actual use in real applications.
1884379
Penalty Function Approach for Constrained Convolutive Blind Source Separation
A new approach for convolutive blind source separation(BSS) using penalty functions is proposed in this paper. Motivated by nonlinear programming techniques for the constrained optimization problem, it converts the convolutive BSS into a joint diagonalization problem with unconstrained optimization. Theoretical analyses together with numerical evaluations reveal that the proposed method not only improves the separation performance by significantly reducing the effect of large errors within the elements of covariance matrices at low frequency bins and removes the degenerate solution induced by a null unmixing matrix, but also provides an unified framework to constrained BSS.
385307
STING: A Statistical Information Grid Approach to Spatial Data Mining
Spatial data mining, i.e., discovery of interesting characteristics and patterns that may implicitly exist in spatial databases, is a challenging task due to the huge amounts of spatial data and to the new conceptual nature of the problems which must account for spatial distance. Clustering and region oriented queries are common problems in this domain. Several approaches have been presented in recent years, all of which require at least one scan of all individual objects (points). Consequently, the computational complexity is at least linearly proportional to the number of objects to answer each query. In this paper, we propose a hierarchical statistical information grid based approach for spatial data mining to reduce the cost further. The idea is to capture statistical information associated with spatial cells in such a manner that whole classes of queries and clustering problems can be answered without recourse to the individual objects. In theory, and confirmed by empirical studies, this approach outperforms the best previous method by at least an order of magnitude, especially when the data set is very large.
9409183
A Novel Hybrid Approach to the Permutation Problem of Frequency Domain Blind Source Separation
We explore the permutation problem of frequency domain blind source separation (BSS). Based on performance analysis of three approaches: exploiting spectral continuity, exploiting time envelope structure and beamforming alignment; we present a new hybrid method which incorporates a psychoacoustic filtering process for the misaligned permutations unable to be delt with by these approaches. We use a sub- space based method (MUSIC) rather than conventional beamforming for the accurate estimation of the direction of arrivals (DOAs) of the source components, and a frequency dependent distance for the correla- tion of time envelopes. The proposed methods are compared with other approaches by signal to interference ratio (SIR) evaluation, and the new hybrid approach is shown to have the best performance.