Interference detection through rasterization

Interference detection is a useful technique, but it is also generally time-consuming. In this paper, a new type of interference detection algorithm is proposed for real-time interference detection. The algorithm first rasterizes the projection of the target objects and calculates the z-values, just as done by the z-buffer visible surface algorithm. For interference detection, all z-values and pointers to the corresponding faces of objects are saved in a z-list for each pixel. Sorting the z-list against the z-values allows the detection of overlapping objects in the z-direction at each pixel position and, thus, finds interfering faces by referring to the face pointers in the z-list. The algorithm is simple and easy to implement. Its computational complexity is directly proportional to the number of polygons, and, in addition, standard graphics hardware can be used to greatly accelerate execution. Another advantage is that the algorithm can be applied to all ‘ray-traceable’ objects, including algebraic surfaces, and procedurally defined objects; traditionally these were not suitable subjects for interference detection. The algorithm is implemented on a graphics workstation using a standard graphics library. Interference detection at a practical interaction speed is achieved for complicated objects such as polyhedra with thousands of polygons. The algorithm can be used in two ways: for inexpensive interference detection, and as an efficient culling method for more precise collision/interference detection algorithms.     

Analysis of axially temperature-dependent functionally graded carbon nanotube reinforced composite plates

This article presents a comprehensive analysis to investigate the static buckling stability and static deflection of axially single-walled (SW) functionally graded (FG) carbon nanotubes reinforced composite (CNTRC) plates with temperature-dependent material properties and graded by different functions, for the first time. The distribution of the carbon nanotubes is described by two functions, one for the x-direction CNTs distribution (CNTRC-x plate) and another for z-direction CNTs distribution (CNTRC-z plate). The graduation functions of CNTs are unidirectional (UD CNTRC), FG-X CNTRC, FG-O CNTRC, and FG-V CNTRC. The extended rule of mixture and the molecular dynamics simulations are exploited to evaluate the equivalent mechanical properties of FG-CNTRC plate. Equilibrium equations are formulated using principal of Hamilton and solved analytically using Galerkin method to cover various boundary conditions. New higher order shear deformation theory is proposed. The numerical results gained by the proposed solution are verified by comparing with those of published ones. Numerical results present influences of gradation function, inhomogeneity parameters, aspect ratio, thickness ratio, boundary conditions and temperature on the static buckling and deflection of FG-CNTRC plate using modified higher order shear theories.

     

A pseudo-spectral method with volume penalisation for magnetohydrodynamic turbulence in confined domains

We present a Fourier pseudo-spectral method for solving the resistive magnetohydrodynamic equations of incompressible flow in confined domains. A volume penalisation method allows to take into account boundary conditions and the geometry of the domain. A code validation is presented for the z-pinch test case. Numerical simulations of decaying MHD turbulence in two space dimensions show spontaneous spin-up of the flow in non-axisymmetric geometries, which is reflected by the generation of angular momentum. First results of decaying MHD turbulence in a cylinder illustrate the potential of the new method for three-dimensional simulations.     

A boundary equation of the principal period-2 component in the degree-n bifurcation set

The degree-n bifurcation set is a generalized Mandelbrot set for the complex polynomial P _c (z)=z ⁿ +c. The boundary of the principal period-2 component in the degree-n bifurcation set is first defined and then formulated by a parametrization of its image, which is the unit circle under the multiplier map. We investigate the boundary equation using the geometric symmetry of the degree-n bifurcation set with respect to rays of symmetry in the complex plane. In addition, an algorithm drawing the boundary curve with Mathematica codes is proposed.     

Dimension splitting algorithm for a three-dimensional elliptic equation

This paper presents a finite-element dimension splitting algorithm (DSA) for a three-dimensional (3D) elliptic equation in a cubic domain. The main idea of DSA is that a 3D elliptic equation can be transformed into a series of two-dimensional (2D) elliptic equations in the X–Y plane along the Z-direction. The convergence speed of the DSA for a 3D elliptic equation depends mainly on the mesh scale of the Z-direction. P ₂ finite-element discretization in the Z-direction for DSA is adopted to accelerate the convergence speed of DSA. The error estimates are given for DSA applying P ₁ or P ₂ finite-element discretization in the Z-direction. Finally, some numerical examples are presented. We apply the parallel solving technology to our numerical examples and obtain good parallel efficiency. These numerical experiments test and verify theoretical results.     

The simulation of 3D elastic scattering produced by thin rigid inclusions using the traction boundary element method

A mixed formulation that uses both the traction boundary element method (TBEM) and the boundary element method (BEM) is proposed to compute the three-dimensional (3D) propagation of elastic waves scattered by two-dimensional (2D) thin rigid inclusions. Although the conventional direct BEM has limitations when dealing with thin-body problems, this model overcomes that difficulty. It is formulated in the frequency domain and, taking into account the 2-1/2D configuration of the problem, can be expressed in terms of waves with varying wavenumbers in the zdirection, k_z. The elastic medium is homogeneous and unbounded and it should be noted that no restrictions are imposed on the geometry and orientation of the internal crack.     

Three-dimensional graph drawing

Graph drawing research has been mostly oriented toward two-dimensional drawings. This paper describes an investigation of fundamental aspects of three-dimensional graph drawing. In particular we give three results concerning the space required for three-dimensional drawings. We show how to produce a grid drawing of an arbitraryn-vertex graph with all vertices located at integer grid points, in ann×2n×2n grid, such that no pair of edges cross. This grid size is optimal to within a constant. We also show how to convert an orthogonal two-dimensional drawing in anH×V integer grid to a three-dimensional drawing with volume. Using this technique we show, for example, that three-dimensional drawings of binary trees can be computed with volume . We give an algorithm for producing drawings of rooted trees in which thez-coordinate of a node represents the depth of the node in the tree; our algorithm minimizes thefootprint of the drawing, that is, the size of the projection in thexy plane. Finally, we list significant unsolved problems in algorithms for three-dimensional graph drawing. This work was performed as part of the Information Visualization Group(IVG) at the University of Newcastle. The IVG is supported in part by IBM Toronto Laboratory.     

On the Use of Level Curves in Image Analysis

A digitized image is viewed as a surface over the xy-plane. The level curves of this surface provide information about edge directions and feature locations. This paper presents algorithms for the extraction of tangent directions and curvatures of these level curves. The tangent direction is determined by a least-squares minimization over the surface normals (calculated for each 2 × 2 pixel neighborhood) in an averaging window. The curvature calculation, unlike most previous work on this topic, does not require a parameterized curve, but works instead directly on the tangents across adjacent level curves. The curvature is found by fitting concentric circles to the tangent directions via least-squares minimization. The stability of these algorithms with respect to noise is studied via controlled tests on computer generated data corrupted by simulated noise. Examples on real images are given which show application of these algorithms for directional enhancement, and feature point detection.     

On Parabolic Boundary Layers for Convection–Diffusion Equations in a Channel: Analysis and Numerical Applications

In this article we discuss singularly perturbed convection–diffusion equations in a channel in cases producing parabolic boundary layers. It has been shown that one can improve the numerical resolution of singularly perturbed problems involving boundary layers, by incorporating the structure of the boundary layers into the finite element spaces, when this structure is available; see e.g. [Cheng, W. and Temam, R. (2002). Comput. Fluid. V.31, 453–466; Jung, C. (2005). Numer. Meth. Partial Differ. Eq. V.21, 623–648]. This approach is developed in this article for a convection–diffusion equation. Using an analytical approach, we first derive an approximate (simplified) form of the parabolic boundary layers (elements) for our problem; we then develop new numerical schemes using these boundary layer elements. The results are performed for the perturbation parameter ε in the range 10⁻¹–10⁻¹⁵ whereas the discretization mesh is in the range of order 1/10–1/100 in the x-direction and of order 1/10–1/30 in the y-direction. Indications on various extensions of this work are briefly described at the end of the Introduction.Dedicated to David Gottlieb on his 60th birthday.     

Solid weak BCC-algebras

We characterize weak BCC-algebras in which the identity (xy)z=(xz)y is satisfied only in the case when elements x and y belong to the same branch.     

Efficient MFS Algorithms for Inhomogeneous Polyharmonic Problems

In this work we develop an efficient algorithm for the application of the method of fundamental solutions to inhomogeneous polyharmonic problems, that is problems governed by equations of the form Δ ^ℓ u=f, ℓ∈ℕ, in circular geometries. Following the ideas of Alves and Chen (Adv. Comput. Math. 23:125–142, 2005), the right hand side of the equation in question is approximated by a linear combination of fundamental solutions of the Helmholtz equation. A particular solution of the inhomogeneous equation is then easily obtained from this approximation and the resulting homogeneous problem in the method of particular solutions is subsequently solved using the method of fundamental solutions. The fact that both the problem of approximating the right hand side and the homogeneous boundary value problem are performed in a circular geometry, makes it possible to develop efficient matrix decomposition algorithms with fast Fourier transforms for their solution. The efficacy of the method is demonstrated on several test problems.     

Efficient ray shooting and hidden surface removal

In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n ²⁺) preprocessing, for any fixed > 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn ⁴⁺) preprocessing and has a query time ofO(logn).We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any > 0, we can obtain an algorithm with running time , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.This research was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The first and third authors were also supported by the Dutch Organization for Scientific Research (N.W.O.).     

A Fast Spectral Subtractional Solver for Elliptic Equations

The paper presents a fast subtractional spectral algorithm for the solution of the Poisson equation and the Helmholtz equation which does not require an extension of the original domain. It takes O(N ² log N) operations, where N is the number of collocation points in each direction. The method is based on the eigenfunction expansion of the right hand side with integration and the successive solution of the corresponding homogeneous equation using Modified Fourier Method. Both the right hand side and the boundary conditions are not assumed to have any periodicity properties. This algorithm is used as a preconditioner for the iterative solution of elliptic equations with non-constant coefficients. The procedure enjoys the following properties: fast convergence and high accuracy even when the computation employs a small number of collocation points. We also apply the basic solver to the solution of the Poisson equation in complex geometries.     

Finite settling time stabilisation: the robust SISO case

This article deals with the problem of robustness to multiplicative plant perturbations for the case of finite settling time stabilisation (FSTS) of single input single output (SISO), linear, discrete-time systems. FSTS is a generalisation of the deadbeat control and as in the case of deadbeat control the main feature of FSTS is the placement of all closed-loop poles at the origin of the z-plane. This makes FSTS sensitive to plant perturbations hence, the need of robust design. An efficient robustness index is introduced and the problem is reduced to a finite linear programme where all the benefits of the simplex method, such as effectiveness, efficiency and ability to provide complete solution to the optimisation problem, can be exploited.     

Boundary domain integral method for high Reynolds viscous fluid flows in complex planar geometries

The article presents new developments in boundary domain integral method (BDIM) for computation of viscous fluid flows, governed by the Navier–Stokes equations. The BDIM algorithm uses velocity–vorticity formulation and is based on Poisson velocity equation for flow kinematics. This results in accurate determination of boundary vorticity values, a crucial step in constructing an accurate numerical algorithm for computation of flows in complex geometries, i.e. geometries with sharp corners. The domain velocity computations are done by the segmentation technique using large segments. After solving the kinematics equation the vorticity transport equation is solved using macro-element approach. This enables the use of macro-element based diffusion–convection fundamental solution, a key factor in assuring accuracy of computations for high Reynolds value laminar flows. The versatility and accuracy of the proposed numerical algorithm is shown for several test problems, including the standard driven cavity together with the driven cavity flow in an L shaped cavity and flow in a Z shaped channel. The values of Reynolds number reach 10,000 for driven cavity and 7500 for L shaped driven cavity, whereas the Z shaped channel flow is computed up to Re = 400. The comparison of computational results shows that the developed algorithm is capable of accurate resolution of flow fields in complex geometries.     

Mesh refinement for shape optimization

The numerical solution of shape optimization problems is considered. The algorithm of successive optimization based on finite element techniques and design sensitivity analysis is applied. Mesh refinement is used to improve the quality of finite element analysis and the computed numerical solution. The norm of the variation of the Lagrange augmented functional with respect to boundary variation (residuals in necessary optimality conditions) is taken as an a posteriori error estimator for optimality conditions and the Zienkiewicz—Zhu error estimator is used to improve the quality of structural analysis. The examples presented show meaningful effects obtained by means of mesh refinement with a new error estimator.     

On some generalizations of BCC-algebras

We describe weak BCC-algebras (also called BZ-algebras) in which the condition (xy)z=(xz)y is satisfied only in the case when elements x and y belong to the same branch. We also characterize branchwise commutative and branchwise implicative weak BCC-algebras satisfying this condition. We also describe connections between various types of implicative weak BCC-algebras.     

Routing in Polygons Without Rectilinearly Visible Corners

In this paper we present an algorithm for the routing problem in a routing region which is bordered by a simple polygonal line, such that there are no rectilinearly visible corners. The routing problem consists in finding pairwise edge-disjoint paths in the grid for the nets connecting some given pairs of boundary vertices. Whenever a solution exists our algorithm finds it in time O(U log²U), where U is the size of the boundary. This is a generalization of the algorithm for rectangle routing by Mehlhorn and Preparata (1986, J. Assoc. Comput. Mach.33, 60-85), which up to now has been the only method with sublinear running time in respect of the routing area.     

The BG distributed simulation algorithm

We present a shared memory algorithm that allows a set of f+1 processes to wait-free “simulate” a larger system of n processes, that may also exhibit up to f stopping failures. Applying this simulation algorithm to the k-set-agreement problem enables conversion of an arbitrary k-fault-tolerant{\it n}-process solution for the k-set-agreement problem into a wait-free k+1-process solution for the same problem. Since the k+1-processk-set-agreement problem has been shown to have no wait-free solution [5,18,26], this transformation implies that there is no k-fault-tolerant solution to the n-process k-set-agreement problem, for any n. More generally, the algorithm satisfies the requirements of a fault-tolerant distributed simulation.\/ The distributed simulation implements a notion of fault-tolerant reducibility\/ between decision problems. This paper defines these notions and gives examples of their application to fundamental distributed computing problems. The algorithm is presented and verified in terms of I/O automata. The presentation has a great deal of interesting modularity, expressed by I/O automaton composition and both forward and backward simulation relations. Composition is used to include a safe agreement\/ module as a subroutine. Forward and backward simulation relations are used to view the algorithm as implementing a multi-try snapshot\/ strategy. The main algorithm works in snapshot shared memory systems; a simple modification of the algorithm that works in read/write shared memory systems is also presented. Received: February 2001 / Accepted: February 2001