Presented here is an algorithm for scaling binary images based on piecewise polynomial interpolation. The algorithm defines a set of convolution kernels which can be used to scale the original image data by an arbitrary scaling factor and to reduce or remove the aliasing artifacts. The convolution kernels are derived from a surface geometry that is mathematically defined over the original data. This algorithm solves a quantization error problem which had prohibited practical applications of any polynomial as an interpolant for image scaling. Its microscopic behavior has been analyzed in a software simulation testbed. It can be applied for scaling binary images in the areas of facsimile imaging and font scaling. It has been fully tested and implemented in a commercial product.
Current monotonicity analysis of optimization problems has loose ends and loopholes which confuse the understanding, teaching and use of the techniques. These embarrassments are removed in this article by redefining slightly the domain, the objective and constraint functions, and even the notion of criticality itself. This leads to a simple and clear `Strong' Monotonicity Theorem giving extensions of the two monotonicity principles are straightforward corollaries. This theorem not only incorporates Hansen, Jaumard and Lu's extensions to non-monotonic functions, but also clarifies the special elimination rules applicable to variables in the constraints but not the objective. This sets the stage for analyzing optimization problems with non-monotonic functions.
The design of many industrial and engineering systems can often be accomplished using flow graphs of various types. Examples include manufacturing processes and data processing applications, Graph Transformation Expert System, is an expert system which has been developed by WUT for applying techniques of artificial intelligence to the architectural design of data and signal processing systems. Software and hardware architectures may be defined for such systems using data flow graphs, in which nodes represent data processing steps and directed areas represent the `flow' of data between the processing steps. Starting with a user- defined generic processing graphic, this expert will transform the graph by applying transformation rules in order to specialize the processing graph to satisfy specified design goals and/or hardware constraints. Although the particular application for which this expert is designed is that of data and signal processing systems, it can provide an expert system framework for other problems specified graphically; for example, manufacturing systems, information systems, and product distribution systems.
This paper reviews the two spline methods: one with interval tension; and the other with point tension. Another spline method has been described which provides point and interval tension control. This method recovers, as a special case, the above mentioned two spline methods and provides a well controlled shape designing. An efficient algorithm has been given to display the curve scheme for the case N equals 2.
Shading of planar regions is one of the basic studies in the field of raster graphics. A new algorithm dealing with the problem is proposed in this paper. By this algorithm, the complicated planar regions need not be converted to simple planar polygons, and can be directly disposed of in the same way. The algorithm runs fast, and the time and space consuming by the shading process are considerably saved.
Plane, quadric surfaces are fundamental elements of three-dimension geometric modeling systems. Intersecting between them is the most basic operation in the system. In this paper, the intersection algorithms in GEMS 4.0 modeling system are discussed, and the method of calculating valid parameter interval to obtain valid intersection curve segments is advanced. At the end, how to calculate the NURBS parameter of intersection point is given.
Rounding of polyhedra is an important operation in CAD/CAM. This paper presents a new rounding scheme based on NURBS. Algorithms for generating edge and corner roundings are developed. Rounding surfaces generated are all NURBS surfaces and rounding radius can be precisely controlled. G1 continuity is satisfied between roundings and their base planes and along common edges between edge roundings and corner rounding.
A product modeling system GEMS 4.0 has been implemented, in which feature representation is used at the highest level abstraction of a product model, boundary representation is used at the bottom level, while CSG model is adopted at the median level. A BRep data structure capable of modeling non-manifold is adopted. NURBS representation is used for all curved surfaces. Quadric surfaces have dual representations consisting of their geometric data such as radius, centerpoint, and center axis. The geometric data are not only necessary for the mapping of form features of the corresponding CSG models, but also useful for accelerating certain time consuming calculations such as surface-surface intersections. Boundary representation of free form surfaces are easily built by sweeping and skinning method with NURBS geometry. Set operations on curved solids with boundary representation are performed by an evaluation process consisting of four steps: intersection, construction, classification and selection.
This article introduces a high-level topological representation for general multibody systems, the spatial directed graph. This simplified topological structure emphasizes the principal aspects of motion in multilink systems and forms a concise representation for the entire class of kinematically constrained multibody systems. It is shown that certain kinematic invariants with respect to this representation allow the simple formulation of kinematic constraints. In this context, it is observed that the only variables that are amenable to an operational algebra associated with this graph are the dual velocities. This formalism represents the starting point for the automatic generation of motion equations for generic multibody systems with applications in motion animation, virtual reality, robotics.
Image alignment is an essential step for 3D reconstruction of organs from serial sections. The conventional means are proved to be either unsuitable or inefficient for microscopies of pulmonary alveolus. A technical description of the alignment problem for micro-section of soft tissues is presented. An efficient automatic alignment algorithm for 3D reconstruction of pulmonary alveolus sections, based on pyramid structure, is proposed. The resultant images of 3D reconstruction demonstrate that our algorithm is promising.
A new approach for triangulating trimmed surfaces is presented in this paper. The main idea is based on constructing triangles net. The algorithm consists of: (1) reconstruction boundaries of the trimmed surfaces; (2) constructing triangles net; (3) triangulation in narrow polygon zone; (4) accuracy checking and triangle subdivision. In this paper, topological consistency of triangles net is checked in parametric domain. Property of a triangle is appraised in 3D space. Excellent triangles net without cracks can finally be received. The algorithm has been successfully used in surface modeling system SCAD 1.0.
In this paper, we exploit the generation of images of approximations to fractals and fractal-like objects by using the generalized iterated Kronecker products and give several examples to show its application. After that, we propose a fast algorithm to estimate the fractals dimension which is generated by generalized Kronecker product under some conditions, and we also give the proof of it.
The detection of dominant points is an important problem in shape recognition. In this paper, the dominant point is divided into two kinds of point: corner point and tangent point, and a two stage method to detect the dominant point is proposed. The corner points are first detected based on the curvature smoothed by Gaussian filter, and tangent points are detected based on the curvature accumulation curve with the commonly used splitting method.
Verbal protocol analysis has been widely used to capture the processes of problem solving behavior. Early research studied humans solving well-defined problems such as cryptarithmetic and Tower of Hanoi problems, but it also extended to chess. Other research has focused on continuous and discrete process control tasks. Our work explores some of the cognitive difficulties involved in CAD model construction. It addresses mental transformations in the physical world, and the nature of cognitive loads when constructing physical models. It also investigates the transport of skills from physical world model construction to a screen world construction process. This paper describes our findings and performance measures in the construction of physical models.
The convergency of iterative processes can present unexpected behaviors. In this paper an analysis of iterative processes convergency is made, and illustrated by its application to Newton model. This leads to the definition of a dynamic relaxation scheme that enables to master iterative processes convergency in limit cases.
This paper proposes a theoretical framework, based on domain subdivision for parallel radiosity. Moreover, three various implementation approaches, taking advantage of partitioning algorithms and global shared memory architecture, are presented.
A new lighting model for natural light in cloudy sky is proposed. In order to represent cloudy scenes and the distribution of the natural light in the cloudy sky, the sky in the model is expressed by a part of a sphere which is called S surface. A layer, called C layer, is set just under the S surface to deal with the distribution of clouds. The natural light is supposed to be given by finite point light sources on the S surface, and three kinds of light components--direct light, scattering light and ambient light are used in each point light source to represent the natural light in various weather conditions. The spectrum in the model varies with the sun altitude.
Many computer graphics programmers are working in the area of scientific visualization. In this paper, we apply the surface fitting algorithm to visualize the 3D terrain and objects. How to obtain the DTM dataset by digitizer is first discussed. And then the representation of objects is described. Finally, the synthetic processing method of the DTM dataset and the objects' dataset is presented, and the high-speed display system of displaying the 3D terrain and objects is also introduced.
A new shading model for linear light source is presented. It accounts for both diffuse reflection and specular reflection of the illuminated surface. By regarding a linear light source as a directional rectangular light source with infinitesimal width, a simple formula is derived for calculating the diffuse reflection component. The specular reflection component is represented by an integration taking Phong's specular model as the kernel and evaluated by a linear approximation. Finally, an efficient shadow detection algorithm for linear light source is proposed. The images rendered with the shading model are very photo realistic.
Curves that are easy to control are useful in design. In this paper we use cubic curves using basis functions proposed by Said. Curves with these basis functions are robust and easy to control. We utilized this representation in designing curves through a given intermediate point, and as a simple application is the approximation of a quarter circle. By blending two curves, we can improve the capability of the representations.
Engineering design practice usually follows a design hierarchy. Constraints more or less reflect engineering requirements. But constraints are practically useful only when they are correctly embedded into design hierarchies. The concept of geometric features is introduced to serve the following purposes: to allow a designer to work with the conventional design hierarchy; to control the effect of constraints; and to decompose a complicated constraint based geometric modeling problem into simpler ones. Geometric features are constructed hierarchically. Although constraints are applied to low level geometric entities (points, lines, etc.), the impact on a design model is usually imposed on higher level features. In terms of constraints processing, each feature is viewed as an independent problem and its constraints are solved independently. All constraints in a design model are therefore solved hierarchically bottom up.
Shoe uppers are often constructed of panels which overlap one another and which may or may not have been thinned along the periphery. One of the visual features important to aesthetic shoe CAD is the profile variation along the panel boundary caused by either stitching or compressed gluing. Based upon an understanding of geometric requirements, the following issues are addressed: offset curve generation according to a classification of local geometry of an arbitrary 3D surface patch; cross section type handling; profile representation and rendering.
This paper put an emphasis on the importance of two points which are crucial when the aim is physically based lighting simulation. The first one is the spectral approach which considers emitted, reflected, diffused and transmitted light as wavelength dependent. The second corresponds to the different steps aiming at converting into RGB components the radiance arriving at the viewpoint through the pixels of a screen.
This paper presents a new approach to construct C1 continuous surfaces on N-sided regions of composite B-spline surfaces. For C0 continuous surfaces on the N-sided regions, their smooth surfaces are constructed by the integral smoothing operation with variable integral neighbors, and the final surfaces are C1 continuous with the original surfaces on the N-sided region boundary.
A new double layer interpolation to cubic parametric curves is derived and analyzed. In the outer layer interpolation, while (Delta) 2f <EQ 2 a cubic parametric curve is split into lines; in the inner layer interpolation, every line is split into discrete points. This approach uses 32 bit integer values and arithmetic shifts.
The quality of a plastic product is determined by the material used, the mold design, and the processing conditions. The objectives of a mold design consist of a mold cooling system, a runner system, and associated gate locations with their types and sizes, and cavity design. Meanwhile, the most important processing conditions during the fill phase are the mold temperature, the melt temperature, and the filling time. In this paper, we use genetic algorithm to optimize molding conditions, which consist of the mold temperature, the melt temperature, and the filling time, based upon the results from flow simulation.
In this paper, explicit formulas are developed for representing a uniform bicubic spline surface that passes through an array of data points. The interpolated surface in the closed case is topologically equivalent to a torus. Open surface cases are reduced to closed surface cases by introducing one or two rows of `free points' such that the spline surface wraps around its boundaries. Ordinary interpolation surfaces in open cases can thus be constructed with the same formulas. It turns to be more intuitive and effective to control and modify the shape of the resultant surfaces by adjusting `free points' than by the usual derivatives and twist vectors. The interpolation surface is obtained in a two step way and the procedure is very easy to implement. Experimental results demonstrate that the proposed formulas are practically useful.
In this paper, we derive a new basis for constructing C2 quintic interpolation spline curve that is called BB spline. The C2 biquintic interpolation spline surface is briefly constructed by tension-product and has properties of interpolation, C2-continuity and locality. The local shape of interpolation spline curve and surface can be modified by the change of shape-parameters. The effects of the shape-parameters are also discussed.
Collision detection is very important in virtual reality. If the objects in virtual world act as they do in physical world, the simulation of virtual world will seem more believable. Due to computational complexity, completing both accuracy and efficiency in a detection algorithm makes a serious dilemma to algorithm designer. After analyzing varieties of approaches to solving collision detection problem, we prove that most successful algorithms have to use some kinds of object related information to reduce detected object pairs and surface set pairs. Then a new approach--multiscale based space descriptions model--is proposed to solve collision detection problem.
An advanced method for the generation of 2D parametric model is presented. The method is based on designer's idea from 3D conceptual model to 2D geometry model. Based on geometric reasoning, the system effectively supports parametric modification of a given design in one view or multiple views through dimension-drive. This approach has been realized on micro computers.
In this paper, the necessary and sufficient conditions and an algorithm for G4 continuity between adjacent Bezier patches are presented. The effects of shape parameters for surface connection are investigated in details. The algorithm can be generalized directly to the case of higher order geometric continuity for surface connecting. It has important applications in surface modeling, surface blending and surface connecting.
The ray reflection, refraction, diffusion, and transparency are important functions for visualizing 3D objects. Every ray intersection with object boundaries and its normal direction on the intersecting point are used to simulate the optical interference of rays with objects. It is theoretically impossible, however, to construct smoothly interpolated continuous boundaries from a discrete array of sampled values, such as a set of volume elements. Although many volume visualization techniques have been proposed, it is still difficult to ensure appropriate surface topology by a simple algorithm. In the present paper, two new isosurface constructors named MMC (Modified Marching Cubes) and DC (Deformed Cubes) are investigated. MMC is a modification of Marching Cubes algorithm, which is well known as a high resolution isosurface constructor. MMC algorithm produces topologically correct triangulated isosurfaces that are guaranteed to be orientable and closed. DC algorithm is much simpler than MMC, and the produced triangulated isosurfaces are also topologically adequate, and as accurate as MMC. Experimental results and comparisons of the interpolated triangulated isosurfaces in terms of the shape precision between MMC and DC are also presented.
For many purposes, problems appear easier to understand when they are formulated by graph theory. In this paper, the recurrence relation of B-spline is modeled by a weighted digraph and a one-to-one correspondence between B-spline functions and weighted digraph paths is proved. A matrix representation of the B-spline digraph is utilized, which yields to compute the B- spline functions as matrix products.
For a triangulation of a planar polygonal region, we develop a C2 interpolation scheme. A model triangle T is subdivided into a split (Delta) asymmetric with the vertices of T. We prove that there exists a C2 piecewise polynomial of degree 5 on (Delta) interpolating arbitrarily given values and derivatives of orders up to 2 at the vertices and on the edges of the triangle.
In this paper the wave recursive interpolation of uniform T-subdivision scheme including wave parameter is defined. The convergence of sequences of control polygons produced by wave recursive interpolation T-subdivision scheme and the smoothness of the limit curve are analyzed.
In the paper, by combining the Coons's idea and the B-spline method, we propose the method to construct the blended B-spline surface to interpolate its four boundary curves, present an algorithm to convert the blended B-spline surface to the NURBS surface and discuss the approximation means of treating the singularity of the blended B-spline surface. At the end of the paper, the conclusions are given.
This paper presents a geometric model of breaking waves. In this model, there are three amplitude coefficient functions and two phase functions. The functions are all unknown ones concerning surf similarity parameter (xi) . Genetic Algorithms is used to obtain the optimum solution of the model for a certain wave pattern, and all unknown functions simulating several wave patterns. Experiment result has proved that Genetic Algorithms are very successful for modeling breaking waves.
The proportional division property of quadratic Bezier curves is presented and proved in the paper. Based on that property, a new computer graphic algorithm to generate quadratic Bezier curves are derived. Discussed in the paper also are the approach to plot cubic Bezier curves with the derived algorithm and two inverse fitting methods for quadratic Bezier curves under certain boundary conditions.
Aiming at detail enhancement in volume rendering, a new volume illumination model, called Composed Scattering Model (CSM), is presented. In order to enhance different details in data, scattering intensity is decomposed into volume scattering intensity and surface scattering intensity, and composed with boundary detection operators. CSM can generate images containing more details than current volume rendering models. This model has been applied to the direct volume rendering of 3D data sets obtained by CT and MRI. The resultant images show not only rich details but also clear boundary surfaces. CSM is demonstrated as an accurate volume rendering model suited for detail enhancement in volume data set.
An algorithm for constructing dynamic convex hull of n points in the plane based on the new criteria for determination of vertex type and vertex position is presented. While this algorithm has O(log n) time for update and O(nlog n) time for the total processing as existing ones, the new criteria make it more compact, explicit and reasonable. In addition, it has the ability to deal with all special cases and therefore is more powerful.
This paper has inferred a corrected wave resistance formula which can be suitable to the real ship's wave resistance computation and to be used to improve the hull's surfaces, through a method which adapts linear wave resistance theory and wave analysis. This paper uses B- spline curve surface to fit the hull's surface and uses SUMT to optimize the hull's surface. A ship form with minimum wave resistance has been obtained. The results of the computation and experiments have proven that the method, presented by this paper, is an effective method for ship improvement and design.
The researches for Bezier and polynomial curves and surfaces, and their applications to curve- fitting have been reported in many papers. However the relation between control points and polynomial coefficients, because of the complexity of computation, have rarely been studied. In this paper, we propose a new method to transform the Bezier to the polynomial representation and vice-versa. An equation is given, for generating an (m + 1) polygonal Bezier control points to approximate an (n + 1) ones. This method, unlike previous works, is more transparent because it is given in form of one equation. With this method, the curve goes through the two endpoints of the polygonal, and we do not need to perform any transformation such as Chebyshev polynomial in order to obtain good approximation. A criterion of reduction is given in order to known if a polygonal Bezier is reducible without error or not. An error estimation is also given only in terms of control points. All equations are given explicitly and in matrix form, for Bezier curves. Finally, we discuss some applications of this method to curve-fitting, order increasing and decreasing, and also its extension to rational Bezier and polynomial.
This paper presents GC1 continuity condition between adjacent NURBS surface patches along common boundary curve and deduces specific algorithms for control points and weights of NURBS surface patch. For making another NURBS surface patch and one given NURBS surface patch to attain GC1, according to algorithms condition, we can adjust another surface patch control points and weights. It is much more convenient for engineers to apply.
A method for constructing high precision parametric planar curve is presented. The method uses the uniform parametrization to assign nodes and evaluates slope vectors at the nodes by supposing that the given data points are taken from a parametric quadratic polynomial. The constructed curve is a C1 piecewise parametric cubic polynomial, and it reproduces exactly a parametric polynomial of degree two or less.
In this paper, we present a method for macroscopical sampling based on geometrical constraints and apply it to circular arc global recognition, by a series of tests, it indicated that this method is simple, convenient and efficient, and it has high robustness.
A new method for control of path motion is presented. To describe the motion of an object, we adopt two independent control curves, namely the path of the object in 3D space and the velocity curve of the object along the path in 2D space. Techniques for constructing the velocity curve according to various application are presented. The task of finding the exact position of the object along the path is facilitated by employment of a look-up table which matches the arclength of the path with a corresponding parameter value. An efficient arclength parametrization algorithm for path curve of Bezier form is developed.
A special kind of points sets named DPDIS is defined in this paper, followed by an elegant algorithm for constructing the convex hull of this class of points sets. Taking advantages of the characteristics of this sets category, this algorithm finishes its work within an O(N) complexity. The crux of this algorithm is a new sorting method by which all points can be sorted along x direction in linear time.
In this paper, a new method for GC1 interpolating cubic unrestricted curve meshes is presented. By choosing the rational combination-functions which ensure the compatibility of twists at nodepoints, quintic vector-valued first order cross-boundary derivatives of surface patches are generated. The resulting surface patches are taken to be the Coons-Boolean sum patches interpolating the boundary information obtained, and are converted to rational biquintic Bezier patches. Compared with other similar interpolation methods, this method has the advantages that it uses lower degree (biquintic) Bezier patches, and that it is local.
Let a 2D random function X(x,y) to denote fBm with exponent 0 < H < 1, then its spectral density Sx(u,v) has relation: Sx(u,v) 1/(u2 + v2)H+1. Such algorithm based on fBm has shown us beautiful pictures of fractal mountains. But the mountains (fractal surfaces) were produced naturally by random process. As a result, the macroscopic shapes and global positions of fractal mounts are not controllable. This paper presents a method that generates fractal mountains with controllable macroscopic shapes and positions using spectral synthesis. First, the discrete data of Y(x,y) on finite grids are inputted, and FFT is employed to produce discrete spectral F(u,v). Second, by InvFFT, low frequency components of F(u,v) together with high frequency components of F(u,v) are transformed to produce Z(x,y)--fractal surface. The macroscopic shapes are controlled by low frequency; meanwhile, the high frequency describes texture of fractal mountains.
In this paper, a new solution to the problem for reconstructing the surface of 3D objects over a set of cross-sectional contours is proposed. An algorithm for single branch contours connection, which is based on the closest local polar angle method, is first presented. Then an approach to solving the branching problem is proposed. Next, a method for surface shading is given. Finally, these methods have been applied to the reconstruction of the external surface of a complex shaped object such as the cellar region of human brain. The results show that the presented methods are practical and satisfactory.
Solid modeling system based on accuracy model achieves a higher level accuracy than faceted system, but many problems exist, such as complexities of geometric calculation. This article presents a new method for representing and maintaining accuracy information in a solid system. A structural representation is introduced, some operations and validity checking are explained.
To address the need for producing high quality designs with better life-cycle performance and shorter product development lead-times, the methods for developing new CAD systems that support integrated concurrent engineering design are studied. A feature-based, integrated concurrent design model, and associated software structure are proposed. In this prototype system, a design is modeled using features from the three most important perspectives of a mechanical product: design, manufacturing and geometry. A hybrid database scheme has been developed for representing the qualitative and quantitative information of these models. The methods for identifying the most cost-effective design and optimal concurrent design are illustrated using examples.
This paper concentrates on the modeling of complex surfaces over arbitrary topologies. Methods and techniques newly developed are presented for high-quality curve and surface modeling in CAD system, e.g., composing of rectangular and triangular patches, modeling of closed surfaces over polyhedral topologies, blending free-form surfaces with geometric continuity. The data structure and data exchange are based on STEP, the international standard for external representation of product data. NURBS (Nonuniform Rational B-spline Surface) representation is adopted as a unified approach to advanced curve and surface design.
Openness is very critical to the CAD kernel (supporting) systems, because a closed CAD system can not provide a deliberate solution to the practical needs. In this paper, we devise an open strategy for CAD kernel systems based on the client/server architecture. With this open strategy, the CAD kernel system can be costumed (clipping or extending) to fit the various applications' needs. Both of the implementation issues and the application development methods are explored.
In this paper, a product data model for progressive die CAD/CAM system is introduced. A special form feature representation model is proposed as part of a product data model to improve design representation. The features are defined as a form feature tree associated with various types of technical constraints such as tolerance and relations for supporting the integration of solid modeling and manufacturing applications. Several examples are presented to illustrate the model and its applications.
An efficient technique is described for rendering Finite Element Modeling (FEM) volume data. The data are not a regular 3D grid. This algorithm can deal with most kinds of FEM data, such as hexahedron 8 nodes, hexahedron 20 nodes etc. Two methods to visualize the FEM data have been presented in the rendering stage. The comparison of these two methods have also been discussed later in this paper.
CAPP (computer aided process planning) is an important bridge linking CAD and CAM. It has been a major problem to convert design into suitable forms for various applications. Two common approaches (i.e. feature recognition and design by features) have been widely used to tackle this problem, but the progress has not met industrial expectations. This paper presents a hybrid method that combines both approaches to create a feature-based component data model (FBCDM) which is suitable for machining process planning and NC programming. Illustrative examples are provided to demonstrate the concept and algorithms devised. Attempts are made to reduce human intervention to a minimum at the design stage in tagging feature-related information while making full use of geometric reasoning to generate the FBCDM. Essential manufacturability assessment is carried out during the modeling process.