Boolean set operations on non-manifold boundary representation objects

For Boolean operations on geometric models, we have developed an intersection algorithm for non-manifold boundary models with vertices, linear edges, planar faces, and volumetric regions. The algorithm operates by intersecting entities in an ordered manner, from vertex to edge, then to face elements. Singular intersections are systematically handled by determining if an entity in one object is within a tolerance region of the entity in the other object. The algorithm performs Boolean operations between objects of different dimensionality as well as solids. An implementation of the proposed algorithm and the experimental results are briefly discussed.     

Efficient editing of solid models by exploiting structural and spatial locality

Computer aided design systems based on solid modellers must provide fast visual feedback to users when objects are edited. This implies that boundary representations must be updated rapidly, because displays typically are generated in current-generation modellers from face, edge and vertex data.This paper describes algorithms for updating a boundary representation when an object's constructive solid geometry (CSG) representation is edited. The algorithms exploit the structural (representational) locality inherent in most object modifications by taking advantage of previously computed boundary representations for (sub-) objects that are not affected by the editing operations. They also exploit spatial locality by re-computing boundaries only within the spatial region where changes can occur. The algorithms are efficient, and are guaranteed to produce valid solids because they are based on CSG.     

An efficient algorithm for finding the CSG representation of a simple polygon

Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary.We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.The first author would like to acknowledge the support of the National Science Foundation under Grants CCR87-00917 and CCR90-02352. The fourth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the first author was visiting the DEC Systems Research Center.     

Stellar Mesh Simplification Using Probabilistic Optimization

This paper proposes the stellar mesh simplification method, a fast implementation of the Four‐Face Cluster (FFC) algorithm. In this method, a probabilistic optimization heuristic substitutes the priority queue of the original method, which results in a 40% faster algorithm with the same order of distortion. It extends naturally to a progressive and/or multiresolution scheme for combinatorial surfaces. This work also presents a simple way to encode the hierarchy of the resulting multiresolution meshes. This work also focuses on important aspects for the development of a practical and robust implementation of this simplification technique, and on the analysis of the influence of the parameters.     

Topological model for 3D image representation: Definition and incremental extraction algorithm

In this paper, we define the three-dimensional topological map, a model which represents both the topological and geometrical information of a three-dimensional labeled image. Since this model describes the image’s topology in a minimal way, we can use it to define efficient image processing algorithms. The topological map is the last level of map hierarchy. Each level represents the region boundaries of the image and is defined from the previous level in the hierarchy, thus giving a simple constructive definition. This model is an extension of the similar model defined for 2D images. Progressive definition based on successive map levels allows us to extend this model to higher dimension. Moreover, with progressive definition, we can study each level separately. This simplifies the study of disconnection cases and the proofs of topological map properties. Finally, we provide an incremental extraction algorithm which extracts any map of the hierarchy in a single image scan. Moreover, we show that this algorithm is very efficient by giving the results of our experiments made on artificial images.     

Algorithms for automatic conversion of a 3-view drawing of a plane-faced part to the 3-D representation

The past decade has seen an increase in the capability of the computer to do cognitive tasks such as understanding natural language or interpreting pictures. The programs doing such processing have much in common with theorem-proving programs, operating system optimizing algorithms and methods of problem solving in formal grammars.The present tutorial describes an approach to interpreting a ‘3-view’ drawing for the construction of its ‘3-D’ representation.     

Two-layer symbolic representation for stochastic models with phase-type distributed events

Among the techniques that have been proposed for the analysis of non-Markovian models, the state space expansion approach showed great flexibility in terms of modelling capacities.The principal drawback is the explosion of the state space. This paper proposes a two-layer symbolic method for efficiently storing the expanded reachability graph of a non-Markovian model in the case in which continuous phase-type distributions are associated with the firing times of system events, and different memory policies are considered. At the lower layer, the reachability graph is symbolically represented in the form of a set of Kronecker matrices, while, at the higher layer, all the information needed to correctly manage event memory is stored in a multi-terminal multi-valued decision diagram. Such an information is collected by applying a symbolic algorithm, which is based on a couple of theorems. The efficiency of the proposed approach, in terms of memory occupation and execution time, is shown by applying it to a set of non-Markovian stochastic Petri nets and comparing it with a classical explicit expansion algorithm. Moreover, a comparison with a classical symbolic approach is performed whenever possible.     

Asymptotic boundary conditions with immersed finite elements for interface magnetostatic/electrostatic field problems with open boundary

Many of the magnetostatic/electrostatic field problems encountered in aerospace engineering, such as plasma sheath simulation and ion neutralization process in space, are not confined to finite domain and non-interface problems, but characterized as open boundary and interface problems. Asymptotic boundary conditions (ABC) and immersed finite elements (IFE) are relatively new tools to handle open boundaries and interface problems respectively. Compared with the traditional truncation approach, asymptotic boundary conditions need a much smaller domain to achieve the same accuracy. When regular finite element methods are applied to an interface problem, it is necessary to use a body-fitting mesh in order to obtain the optimal convergence rate. However, immersed finite elements possess the same optimal convergence rate on a Cartesian mesh, which is critical to many applications. This paper applies immersed finite element methods and asymptotic boundary conditions to solve an interface problem arising from electric field simulation in composite materials with open boundary. Numerical examples are provided to demonstrate the high global accuracy of the IFE method with ABC based on Cartesian meshes, especially around both interface and boundary. This algorithm uses a much smaller domain than the truncation approach in order to achieve the same accuracy.     

Computer-based task representation: a methodology for improving system design

Task analysis procedures can be used in all stages of system development to examine the nature and severity of performance demands placed upon human operators. Task analyses involve considerable effort in obtaining a detailed set of measurements that represent the behavioural and cognitive tasks performed by the operators; these measures are referred to as task representation. The present article describes a flexible method for incorporating task representation data into an electronic spreadsheet. Such a computer-based procedure has many advantages over the more traditional paper and pencil approaches to task representation and analysis, including greater flexibility in data analysis and the inclusion of both objective and subjective measures of workload. Portions of an illustrative task representation and task analysis are presented along with a discussion of the strengths of computer-based task representation and analysis.     

Homotopy perturbation technique for solving two-point boundary value problems - comparison with other methods

The two-point boundary value problems occur in a wide variety of problems in engineering and science. In this paper, we implement the homotopy perturbation method for solving the linear and nonlinear two-point boundary value problems. The main aim of this paper is to compare the performance of the homotopy perturbation method with extended Adomian decomposition method and shooting method. As a result, for the same number of terms, the homotopy perturbation method yields relatively more accurate results with rapid convergence than other methods. The computer symbolic systems such as Maple and Mathematica allow us to perform complicated and tedious calculations.     

An adaptive boundary element for eigenvalue problems with the Helmholtz equation: simplified h-scheme

A simplified h-version of the adaptive boundary elements is proposed for the eigenvalue analysis of the Helmholtz equation. The new scheme considers the effect of each local boundary element refinement, not on the eigenvalue but on the eigenvector, which is devised for possible application of the conventional adaptive mesh construction strategy for boundary value problems. In this paper, for improvement of computational efficiency, the local reanalysis for obtaining the eigenvector is employed. The error indicator of the eigenvector in place of that of the eigenvalue, the global value, decides selectively the boundary elements to be refined. Utility of the proposed method is compared, through some examples, with those previously developed.     

B2-splines: a local representation for cubic spline interpolation

The cubicB-spline representation provides the local interaction properties and the sufficient order of continuity required in free-form curve and surface modelling in CAD. Basic problems are nevertheless encountered when applyingB-splines to interpolation, where they have global behavior. In this paper, we present theB2-spline formulation, a superset of theB-splines with local interpolation properties. Besides providing the local interpolation access, theB2-spline interaction operations can also be used directly as aB-spline modelling interface. Modelling aplications are discussed especially with the skinning method for interpolating surfaces through curve networks.     

Array based HV/VH tree: an effective data structure for layout representation

We present a new data structure for the representation of an integrated circuit layout. It is a modified HV/VH tree using arrays as the primary container in bisector lists and leaf nodes. By grouping and sorting objects within these arrays together with a customized binary search algorithm, our new data structure provides excellent performance in both memory usage and region query speed. Experimental results show that in comparison with the original HV/VH tree, which has been regarded as the best layout data structure to date, the new data structure uses much less memory and can become 30% faster on region query.     

Hierarchical structure to winged-edge structure: a conversion algorithm

The winged-edge data structure is advantageous for traversing the topological graph of the boundary representation of a solid object. This paper presents an algorithm for converting hierarchical boundary representations into representations in the winged-edge data structure. As a result of the conversion, the adjacency relationships of geometric entities embedded in hierarchical boundary representations,-which may be evaluated through boundary evaluation on solid objects defined via Boolean set-operations, can be easily and efficiently accessed.     

Energy decay rate for a von Karman system with a boundary nonlinear delay term

In this paper, we show the energy decay rate for a von Karman system with a boundary nonlinear delay term. This work is devoted to investigate the influence of kernel function $g$ and the effect of the boundary nonlinear term ${\mu }_1{\left|u_t\left(t\right)\right|}^{m?1}{u}_t\left(t\right)$, a boundary nonlinear time delay term ${\mu }_2{\left|u_t(t?\tau )\right|}^{m?1}{u}_t(t?\tau )$ and prove energy decay rates of solutions when $g$ do not necessarily decay exponentially and the boundary condition has a time delay.     

Approximate solution for a variable-coefficient semilinear heat equation with nonlocal boundary conditions

This paper develops an iterative algorithm for the solution to a variable-coefficient semilinear heat equation with nonlocal boundary conditions in the reproducing space. It is proved that the approximate sequence u _n (x, t) converges to the exact solution u(x, t). Moreover, the partial derivatives of u _n (x, t) are also convergent to the partial derivatives of u(x, t). And the approximate sequence u _n (x, t) is the best approximation under a complete normal orthogonal system.     

User modelling for adaptive computer systems: a survey of recent developments

User modelling is becoming an important sub-area of Artificial Intelligence with both theoretical and practical consequences. The theoretical foundations of user modelling are to be found in key areas of AI, such as knowledge representation and plan recognition, while its practical applications impinge on the construction of intelligent user interfaces and adaptive systems. This paper provides a survey of current work in user modelling. The paper begins by distinguishing between AI approaches, which are the subject of this survey, and those of HCI (Human-Computer Interaction) and then considers the major issues in user modelling such as: types of user modelling system, the sorts of information modelled, how the information is acquired, represented and used. The paper concludes by examining some of the more problematic aspects of user modelling as well as indicating areas for future research.