An approach to a calculation-minimized hidden line algorithm

Hidden line algorithms based only on picture primitives, cannot recognize the areas of a picture which are completely visible or invisible. By testing each primitive of these areas they produce an overhead of calculation. Moreover, they waste time by first calculating the hidden lines explicitely and then displaying the remaining edges. This paper describes a method, which rather computes the visible parts of a picture, than excludes the invisible ones. Furthermore an approach to recognize complete visible areas instead of single visible edges is made. A comparison with other techniques will show the qualitatively better calculation rate of the new method.     

An efficient scan conversion and hidden surface removal algorithm

A scan conversion and hidden surface algorithm is discussed in detail. The algorithm is of the Watkins class but differs markedly in implementation. It is running on an 8K Varian 620 computer, and is used to produce shaded color renderings of three-dimensional objects. Details of the data structure used and of the internal sortings is given. Together with a video disk subsystem, the minicomputer system is capable of producing studio quality T.V. images in 8–70 s, depending on image complexity.     

A simple and efficient Union–Find–Delete algorithm

The Union–Find data structure for maintaining disjoint sets is one of the best known and widespread data structures, in particular the version with constant-time Union and efficient Find. Recently, the question of how to handle deletions from the structure in an efficient manner has been taken up, first by Kaplan et al. (2002) [2] and subsequently by Alstrup et al. (2005) [1]. The latter work shows that it is possible to implement deletions in constant time, without affecting adversely the asymptotic complexity of other operations, even when this complexity is calculated as a function of the current size of the set.In this note we present a conceptual and technical simplification of the algorithm, which has the same theoretical efficiency, and is probably more attractive in practice.     

A simple and efficient real-coded genetic algorithm for constrained optimization

This paper presents a simple and efficient real-coded genetic algorithm (RCGA) for constrained real-parameter optimization. Different from some conventional RCGAs that operate evolutionary operators in a series framework, the proposed RCGA implements three specially designed evolutionary operators, named the ranking selection (RS), direction-based crossover (DBX), and the dynamic random mutation (DRM), to mimic a specific evolutionary process that has a parallel-structured inner loop. A variety of benchmark constrained optimization problems (COPs) are used to evaluate the effectiveness and the applicability of the proposed RCGA. Besides, some existing state-of-the-art optimization algorithms in the same category of the proposed algorithm are considered and utilized as a rigorous base of performance evaluation. Extensive comparison results reveal that the proposed RCGA is superior to most of the comparison algorithms in providing a much faster convergence speed as well as a better solution accuracy, especially for problems subject to stringent equality constraints. Finally, as a specific application, the proposed RCGA is applied to optimize the GaAs film growth of a horizontal metal-organic chemical vapor deposition reactor. Simulation studies have confirmed the superior performance of the proposed RCGA in solving COPs.     

A simple,efficient degree raising algorithm for B-spline curves

This paper presents a new algorithm to compute the degree-raised version of a spline. The new algorithm is as fast as the best existing algorithm, but is much easier to understand and to implement. The new control vertices of the degree-raised spline are obtained simply by a series of knot insertions followed by a series of knot deletions.     

Triangulating multiply-connected polygons: A simple, yet efficient algorithm.

We present a new, simple, yet efficient algorithm for triangulating multiply-connected polygons. The algorithm requires sorting only local concave minima (sags). The order in which triangles are created mimics a flooding process of the interior of the polygon. At each stage, the algorithm analyses the positions and neighborhoods of two vertices only, and possibly checks for active sags, so as to determine which of five possible actions to take. Actions are based on a local decomposition of the polygon into monotonic regions, or gorges (raise the water level in the current gorge, spill into an adjacent gorge, jump to the other bank of a filled gorge, divide a gorge into two, and fill a gorge to its top). The implementation is extremely simple and numerically robust for a large class of polygons. It has been tested on millions of cases as a preprocessing step of a walkthrough and inspection program for complex mechanical and architectural scenes. Extensive experimental results indicate that the observed complexity in terms of the number of vertices, remains under in all cases.     

A simple and efficient parallel FFT algorithm using the BSP model

We present a new parallel radix-4 FFT algorithm based on the BSP model. Our parallel algorithm uses the group-cyclic distribution family, which makes it simple to understand and easy to implement. We show how to reduce the communication cost of the algorithm by a factor of 3, in the case that the input/output vector is in the cyclic distribution. We also show how to reduce computation time on computers with a cache-based architecture. We present performance results on a Cray T3E with up to 64 processors, obtaining reasonable efficiency levels for local problem sizes as small as 256 and very good efficiency levels for local sizes larger than 2048.     

Resolution correction: A simple and efficient algorithm with error analysis

A new procedure to correct experimental spectra for instrumental resolution is described. A-priori knowledge is not used, in contrast to other deconvolution methods; consequently the range of applications is very wide, while the necessary computations are simple. Use is being made of the Fast Fourier Transform technique, which makes the method suitable to process large amounts of data. Not only the propagation of the random statistical errors but also the contribution from systematic errors, which arise in any method, is estimated. The validity of the method is demonstrated by means of numerical tests taken from different sources in the literature.     

A simple and efficient algorithm for determining the symmetries of polyhedra

In this paper we present a simple and efficient algorithm for determining the rotational symmetries of polyhedral objects in O(m²) time using O(m) space, where m represents the number of edges of the object. Our algorithm is an extension of Weinberg's algorithm for determining isomorphisms of planar triply connected graphs. The symmetry information detected by our algorithm can be utilized for various purposes in artificial intelligence, robotics, assembly planning and machine vision.     

A hidden line algorithm for a model generated by assembling solid convex polyhedra

A simple algorithm is presented for removing the hidden lines from an object which consists of a collection of solid blocks. The elementary blocks are general convex polyhedra with any number of faces. The representation of the object as a whole requires that the lines of separation between contiguous blocks are also removed.The procedures developed are described in detail and illustrated by flowcharts.     

An algorithm for hidden line ruled surface display using microprocessor

A simple algorithm for hidden line Ruled Surface graphics, typically used in Radio Astronomy is discussed using low cost microcomputer system built around Motorola 6800 processor and Matrox 256**2 graphics module of raster size 256 × 256 points. Resolution of the plot can be improved by displaying on a bigger raster like 1024 × 1024 points.     

A simple algorithm for digital line recognition in the general case

This paper is concerned with the digital line recognition problem for lines of fixed thickness in the naive and general cases. Previous incremental algorithms from Debled-Rennesson and Reveillès [A linear algorithm for segmentation of digital curves, Int. J. Pattern Recognition Artif. Intell. 9(6) (1995)] and from Buzer [A linear incremental algorithm for naive and standard digital lines and planes recognition, Graphical Models 65(1-3) (2003) 61-76] deal with the 8-connected case or with sophisticated machinery coming from linear programming. We present the first elementary method that works with any set of points (not necessarily 8-connected) and we propose a linear time algorithm under some restrictions. This paper deals with implementation details giving pseudo-code of our method. We insist on linking the recognition problem to the intrinsic properties of convex hulls.     

A hidden line mechanism using overinking

A spiral spring is computed by repeated application of the transform for rotation about x-axis and shifting along the x-axis. The image is plotted with a slow drying spirit pen on overhead transparency film. The resultant overinking produces an image comprising half a left-handed spring and half a right-handed spring which must be split and half flipped to produce the required result. Images of molluses are produced using a similar technique, with the transform for scaling and rotation.     

Local search: A new hidden line elimination algorithm to display spherical coordinate equations

Local Search, a new hidden line elimination algorithm, is presented. Local Search is a variant of the Scan-Line algorithm. Its performance is compared to that of two other Scan-Line algorithms for elimination of hidden lines from displays defined by spherical coordinate equations. In this paper, metrics are developed to evaluate the theoretical worst-case performance of each algorithm as a function of the display's complexity. Our performance evaluation is restricted to algorithms which can be implemented on personal computers. Data on the run-time performance of each algorithm were then collected to validate the worst case metrics. These data substantiate the hypothesis that, for complex displays, the Local Search algorithm performs hidden line elimination more efficiently than other Scan-Line algorithms.     

一种简单有效的算法在肿瘤亚型发现中的应用

本文采用了一种简单有效的肿瘤亚型发现的算法。该算法主要包括三个步骤:首先对数据进行预处理;然后采用定义的信息系数进行信息基因的选择;最后将层次聚类算法与t-检验相结合,完成了肿瘤亚型的发现。以白血病和结肠癌的基因表达谱为例,得出了很好的分型结果,表明了该方法的有效性和可行性。     

eXploratory K-Means: A new simple and efficient algorithm for gene clustering

In this paper, a novel gene expression clustering method known as eXploratory K-Means (XK-Means) is proposed. The method is based on the integration of the K-Means framework, and an exploratory mechanism to prevent premature convergence of the clustering process. Experimental results reveal that the performance of XK-Means in grouping gene expressions, measured in terms of speed, error and stability, is superior to existing methods that are based on evolutionary algorithm. In addition, the complexity of the proposed method is lower and the method can be easily implemented in practice.     

A simple algorithm for structured-grid generation with application to efficient Navier-Stokes computation

A grid generation procedure using a simple algorithm is presented. The present method is essentially based on the electro-static theory. By distributing electric charges at the boundary points, an electro-static vector field is produced inside the region between the inner and outer boundaries. The resulting electric force lines, which all emanate from grid points on the body, can be utilized as one family of grid lines. The other family of grid lines is easily constructed by plotting points at regular intervals along the electric force lines. The electric charge distribution is uniquely determined by an appropriate boundary condition, as long as the total amount of charges on each closed boundary is constant. The actual Navier-Stokes simulation using the block-structured grid generated by the present method was also carried out for a complex space vehicle configuration.     

Coifes—an efficient structural graphics program using the hidden line technique

The theory of the hidden-line, or opaque-imaging problem for polyhedra is discussed, with particular emphasis on its application to finite-element structures. Documentation is provided for the program COIFES, which is a versatile implementation of a fast algorithm for removing hidden lines from objects consisting of mixed sets of non-intersecting polyhedra and polygons.     

An efficient algorithm for line and polygon clipping

We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.     

钢结构中基于工程规则的三维线消隐算法

详细分析了钢结构中节点图纸的消隐规则,把消隐的工程规则归纳为虚线的显示,并结合简化的实体布尔运算算法,提出了隐藏度和半隐藏度的概念,较好地解决了工程图纸中虚线的生成问题。