Search

Abstract: This paper proposes a method to construct a B-spline surface that interpolates the specified four groups of boundary derivative curves in the B-spline form. The discontinuity can be bounded by an arbitrary geometric invariant as the tolerance. The method first handles the six types of the compatibility problems by continuity-preserving reparameterization, knot-insertion and local control-point tuning. The transformed boundary conditions are then parametrically compatible, so the Coons strategy can be applied to construct the final interpolant. Not only can it be used in the reliable geometric modeling, but the approach also can be applied to many other algorithms that require compatibility guarantee. [Copyright &y& Elsevier]

Abstract: This paper proposes a method of blending multiple parametric surfaces in polar coordinates. It models the geometric continuity conditions of parametric surfaces in polar coordinates and presents a mechanism of converting a Cartesian parametric surface into its polar coordinate form. The basic idea is first to reparameterize the parametric blendees into the form of polar coordinates. Then they are blended simultaneously by a basis function in the complex domain. To extend its compatibility, we also propose a method of converting polar coordinate blending surface into NURBS patches. One application of this technique is to fill -sided holes. Examples are presented to show its feasibility and practicability. [Copyright &y& Elsevier]

Abstract: A unicast-based fault-tolerant multicasting method is proposed for hypercubes, which can still work well when the system contains enough faults. A multicast message may be unable to reach a destination if Hamming distance between the destination and the multicast source is large enough. A multicast message fails if any one of the destinations is unreachable from the source. An effective destination ordering scheme of the destinations is proposed for one-port systems first, it is extended to all-port systems for unicast-based fault-tolerant multicasting. Unreachable destinations from the source based on the local safety information are forwarded to a reachable destination, where the multicast message can be routed reliably. Destination ordering is completed based on Hamming distance. A multiple round p-cube routing scheme is presented for a deadlock-free fault-tolerant routing for each unicast step in hypercubes, where the same virtual channel is used for each round of p-cube routing. Sufficient simulation results are presented by comparing with the previous methods. [Copyright &y& Elsevier]

Abstract: The envelope of a one-parameter set of spheres with radii and centers is a canal surface with as the spine curve and as the radii function. This concept is a generalization of the classical notion of an offset of a plane curve. In this paper, we firstly survey the principle geometric features of canal surfaces. In particular, a sufficient condition for canal surfaces without local self-intersection is presented. Moreover, a simple expression for the area and Gaussian curvature of canal surfaces are given. We also consider the implicit equation of canal surfaces with the degree of presented. By using the degree of , a low boundary of the degree of parameterizations representations of canal surfaces is presented. [Copyright &y& Elsevier]

Abstract: A finite difference method (FDM) for multi-dimensional nonlinear coupled system of parabolic and hyperbolic equations is studied. Nonlinear coupled property is fully considered. Variant techniques of discrete functional analysis such as summation by parts and deductive reasoning are used to make prior estimates. The FD scheme is uniquely solvable and unconditionally stable. With the approximation property of the scheme, the convergence is obtained with a rate of order. [Copyright &y& Elsevier]

Abstract: A fully unsafe hypercube according to the global safety can be split into a unique set of maximal safe subcubes. Multicasting in a maximal safe subcube can be completed reliably based on information related to the maximal safe subcube. A time-optimal multicasting exists if (1) the multicast source is locally safe in the minimum subcube that contains the source and destinations (called a multicast subcube), or (2) the spanning subcube between each destination and the source is safe. We show a sufficient condition for the existence of a multicasting is: the multicast subcube is safe or the spanning subcube between the source and each destination is either safe or is contained in a safe subcube. Methods are presented to set up a partial multicast tree when the above sufficient conditions fail. It is shown that effectiveness of the algorithm can be improved drastically using the partial multicast tree setup technique. Extensive simulation results are also presented. [Copyright &y& Elsevier]

Abstract: An unstructured tetrahedral mesh generation algorithm for 3D model with constraints is presented. To automatically generate a tetrahedral mesh for model with constraints, an advancing front algorithm is presented based on conforming constrained Delaunay tetrahedralization (CCDT). To reduce the number of visibility tests between vertices with respect to model faces as well as the computation of constrained Delaunay tetrahedra, a sufficient condition for DT (constrained Delaunay tetrahedralization whose simplexes are all Delaunay) existence is presented and utilized coupled to uniform grid and advancing front techniques in our algorithm. The mesh generator is robust and exhibits a linear time complexity for mechanical models with uniform density distribution. [Copyright &y& Elsevier]

Objects and their spatial relationships are important features for human visual perception. In most existing content-based image retrieval systems, however, only global features extracted from the whole image are used. While they are easy to implement, they have limited power to model semantic-level objects and spatial relationship. To overcome this difficulty, this paper proposes a constraint-based region matching approach to image retrieval. Unlike existing region-based approaches where either individual regions are used or only first-order constraints are modeled, the proposed approach formulates the problem in a probabilistic framework and simultaneously models both first-order region properties and second-order spatial relationships for all the regions in the image. Specifically, in this paper we present a complete system that includes image segmentation, local feature extraction, first- and second-order constraints, and probabilistic region weight estimation. Extensive experiments have been carried out on a large heterogeneous image collection with 17,000 images. The proposed approach achieves significantly better performance than the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Abstract: Coons’ construction generates a surface patch that interpolates four groups of specified boundary curves and the corresponding cross-boundary derivative curves. This constructive method is simple and widely used in computer aided design. However, at the corner points, it requires compatibility of the boundary conditions, which is usually difficult to satisfy in practice. In order to handle the incompatible case where the normal directions respectively indicated by two adjacent boundaries do not agree with each other at the common corner point, we utilize the property of degenerate parametric surfaces that the normal directions can converge to multiple values at degenerate points, and therefore the local degenerate geometry can satisfy conflicting conditions simultaneously. Following this idea, we use a single patch of -degree polynomial spline surface with four degenerate corners to interpolate incompatible boundary conditions, which are represented by -degree polynomial spline curves with continuity. This method is based on symbolic operations and polynomial reparameterizations for polynomial splines, and without introducing any theoretical errors, it achieves continuity on the boundary except for the four corner points. [Copyright &y& Elsevier]

Abstract: This paper focuses on interpolating vertices and normal vectors of a closed quad-dominant mesh 1 [1] A mesh is quad-dominant if it contains quad facets as its majority. The quantity of quad facets is much more than the quantity of triangular and other multi-sided facets. -continuously using regular Coons B-spline surfaces, which are popular in industrial CAD/CAM systems. We first decompose all non-quadrangular facets into quadrilaterals. The tangential and second-order derivative vectors are then estimated on each vertex of the quads. A least-square adjustment algorithm based on the homogeneous form of continuity condition is applied to achieve curvature continuity. Afterwards, the boundary curves, the first- and the second-order cross-boundary derivative curves are constructed fulfilling continuity and compatibility conditions. Coons B-spline patches are finally generated using these curves as boundary conditions. In this paper, the upper bound of the rank of continuity condition matrices is also strictly proved to be , and the method of tangent-vector estimation is improved to avoid petal-shaped patches in interpolating solids of revolution. Several examples demonstrate its feasibility. [ABSTRACT FROM AUTHOR]

Abstract: View identification is the basic process for solid reconstruction from engineering drawings. A new method is presented to label various views from a section-involved drawing and identify geometric planes through the object at which the sections are to be located. In the approach, a graph representation is developed for describing multiple relationships among various views in the 2D drawing space, and a reasoning technique based on evidence theory is implemented to validate view relations that are used to fold views and sections in the 3D object space. This is the first automated approach which can handle multiple sections in diverse arrangements, especially accommodating the aligned section for the first time. Experimental results are given to show that the proposed solution makes a breakthrough in the field and builds a promising basis for further expansibility, although it is not a complete one. [Copyright &y& Elsevier]

Abstract: This paper proposes a second order geometric iteration algorithm for point projection and inversion on parametric surfaces. The iteration starts from an initial projection estimation. In each iteration, we construct a second order osculating torus patch to the parametric surface at the previous projection. Then we project the test point onto the torus patch to compute the next projection and its parameter. This iterative process is terminated when the parameter satisfies the required precision. Experiments demonstrate the convergence speed of our algorithm. [Copyright &y& Elsevier]

Abstract: Dynamic partial differential equation (PDE) parametric curves which can be expressed as a coupled system of two hyperbolic equations are developed. In curve design, dynamic PDE parametric curves can be modified intuitively and are more flexible than ordinary differential equation (ODE) curves. The calculation of dynamic PDE parametric curves must recur to numerical methods and a three-level finite difference scheme is proposed. Approximation and stability properties for the scheme are proved and convergence property is derived. An example of interpolating PDE curves is presented as an application of dynamic PDE parametric curves. [Copyright &y& Elsevier]

Abstract: A new algorithm for reducing control points in lofted surface interpolation to rows of data points is presented in this paper. The key step of surface lofting is to obtain a set of compatible B-spline curves interpolating each row. Given a set of points and their parameterization, a necessary and sufficient condition is proposed to determine the existence of interpolating B-spline curves defined on a given knot vector. Based on this condition, we first properly construct a common knot vector that guarantees the existence of interpolating B-spline curves to each row of points. Then we calculate a set of interpolating B-spline curves defined on the common knot vector by energy minimization. Using this method, fewer control points are employed while maintaining a visually pleasing shape of the lofted surface. Several experimental results demonstrate the usability and quality of the proposed method. [Copyright &y& Elsevier]

Curves on surfaces play an important role in computer-aided geometric design. Because of the considerably high degree of exact curves on surfaces, approximation algorithms are preferred in CAD systems. To approximate the exact curve with a reasonably low degree curve which also lies completely on the -spline surface, an algorithm is presented in this paper. The Hausdorff distance between the approximate curve and the exact curve is controlled under the user-specified distance tolerance. The approximate curve is continuous, where is the user-specified angle tolerance. Examples are given to show the performance of our algorithm. [Copyright &y& Elsevier]

Abstract: A novel method for projecting points onto a point cloud, possibly with noise, is presented based on the point directed projection (DP) algorithm proposed by Azariadis P., Sapidis N. [Drawing curves onto a cloud of points for point-based modelling. Computer-Aided Design 2005; 37(1): 109–22]. The new method operates directly on the point cloud without any explicit or implicit surface reconstruction procedure. The presented method uses a simple, robust, and efficient algorithm: least-squares projection (LSP), which projects points onto the point cloud in a least-squares sense without any specification of the projection vector. The main contribution of this novel method is the automatic computation of the projection vector. Furthermore, we demonstrate the effectiveness of this approach through a number of application examples including thinning a point cloud, point normal estimation, projecting curves onto a point cloud and others. [Copyright &y& Elsevier]

Abstract: -sided hole filling plays an important role in vertex blending. To deal with the case that the corner is surrounded by rational surfaces (i.e. NURBS surfaces), an algorithm to fill -sided holes with - G1 continuous NURBS patches that interpolate the given boundary curves and approximate the given cross-boundary derivatives is presented based on Piegl’s method. The NURBS surfaces joining along inner or boundary curves have normal vectors that do not deviate more than the user-specified angular tolerance . The boundaries as well as cross-boundary derivatives can all be NURBS curves. No restrictions are imposed on the number of boundary curves, and the cross-boundary derivatives can be specified independently. [Copyright &y& Elsevier]

Abstract: The minimum distance computation problem between two surfaces is very important in many applications such as robotics, CAD/CAM and computer graphics. Given two implicit algebraic surfaces, a new method based on the offset technique is presented to compute the minimum distance and a pair of points where the minimum distance occurs. The new method also works where there are an implicit algebraic surface and a parametric surface. Quadric surfaces, tori and canal surfaces are used to demonstrate our new method. When the two surfaces are a general quadric surface and a surface which is a cylinder, a cone or an elliptic paraboloid, the new method can produce two bivariate equations where the degrees are lower than those of any existing method. [Copyright &y& Elsevier]

Abstract: The reconstruction of 3D objects from 2D orthographic views is crucial for maintaining and further developing existing product designs. A B-rep oriented method for reconstructing curved objects from three orthographic views is presented by employing a hybrid wire-frame in place of an intermediate wire-frame. The Link-Relation Graph (LRG) is introduced as a multi-graph representation of orthographic views, and quadric surface features (QSFs) are defined by special basic patterns of LRG as well as aggregation rules. By hint-based pattern matching in the LRGs of three orthographic views in an order of priority, the corresponding QSFs are recognized, and the geometry and topology of quadric surfaces are recovered simultaneously. This method can handle objects with interacting quadric surfaces and avoids the combinatorial search for tracing all the quadric surfaces in an intermediate wire-frame by the existing methods. Several examples are provided. [Copyright &y& Elsevier]

Abstract: The reconstruction of 3D objects from 2D orthographic views is very important for the maintenance and continued development of existing product designs. An efficient method for generating 3D curvilinear wire-frames from three orthographic views is presented, which is the pivotal stage of solid reconstruction by wire-frame-oriented approaches. By unifying the recovery of spatial conics without restrictions on their positions, our method can improve the efficiency and reliability of curvilinear wire-frame reconstruction. A projection matching algorithm is proposed to efficiently reveal all match projections according to the projective properties of spatial edges. Furthermore, a four-point method, which is based on the rational Bézier form of conics, is proposed to uniformly generate various types of conics in arbitrary positions. Several examples are provided. [Copyright &y& Elsevier]

Abstract: A novel and efficient quasi-Monte Carlo method for computing the area of a point-sampled surface with associated surface normal for each point is presented. Our method operates directly on the point cloud without any surface reconstruction procedure. Using the Cauchy–Crofton formula, the area of the point-sampled surface is calculated by counting the number of intersection points between the point cloud and a set of uniformly distributed lines generated with low-discrepancy sequences. Based on a clustering technique, we also propose an effective algorithm for computing the intersection points of a line with the point-sampled surface. By testing on a number of point-based models, experiments suggest that our method is more robust and more efficient than those conventional approaches based on surface reconstruction. [Copyright &y& Elsevier]

Abstract: By Bezout''s theorem, three quadric surfaces have at most eight isolated intersections although they may have infinitely many intersections. In this paper, we present an efficient and robust algorithm, to obtain the isolated and the connected components of, or to determine the number of isolated real intersections of, three quadric surfaces by reducing the problem to computing the real intersections of two planar curves obtained by Levin''s method. [Copyright &y& Elsevier]

Abstract: A new algorithm for Boolean operations on general planar polygons is presented. It is available for general planar polygons (manifold or non-manifold, with or without holes). Edges of the two general polygons are subdivided at the intersection points and touching points. Thus, the boundary of the Boolean operation resultant polygon is made of some whole edges of the polygons after the subdivision process. We use the simplex theory to build the basic mathematical model of the new algorithm. The subordination problem between an edge and a polygon is reduced to a problem of determining whether a point is on some edges of some simplices or inside the simplices, and the associated simplicial chain of the resultant polygon is just an assembly of some simplices and their coefficients of the two polygons after the subdivision process. Examples show that the running time required by the new algorithm is less than one-third of that by the Rivero and Feito algorithm. [Copyright &y& Elsevier]

A method for generating an interpolation closed G1 arc spline on a given closed point set is presented. For the odd case, i.e. when the number of the given points is odd, this paper disproves the traditional opinion that there is only one closed G1 arc spline interpolating the given points. In fact, the number of the resultant closed G1 arc splines fulfilling the interpolation condition for the odd case is exactly two. We provide an evaluation method based on the arc length as well such that the choice between those two arc splines is made automatically. For the even case, i.e. when the number of the given points is even, the points are automatically moved based on weight functions such that the interpolation condition for generating closed G1 arc splines is satisfied, and that the adjustment is small. And then, the G1 arc spline is constructed such that the radii of the arcs in the spline are close to each other. Examples are given to illustrate the method. [Copyright &y& Elsevier]