Search

• Introduction of Riemannian global illumination. • A path tracer algorithm to approximate the solution of the Riemannian global illumination. • A map of the algorithm to the GPU, using the RTX platform. • We apply the Non-Euclidean path tracer to render "Photorealistic" inside views of the 3D flat torus, Poincaré sphere, and the hyperbolic mirrored dodecahedron. These are examples of the Euclidean, spherical, and hyperbolic spaces: the Thurston classical geometries. This paper presents a novel path tracer algorithm for immersive visualization of Riemannian manifolds. To do this, we introduce Riemannian illumination, a generalization of classical Computer Graphics illumination models. In this context, global light transport is expressed by extending the rendering equation to Riemannian manifolds. Using Monte Carlo integration to solve this equation results in the novel path tracer for Non-Euclidean spaces. We discuss its basic principles, as well as the general CPU algorithm. Additionally, we discuss in detail how to implement a GPU version, using the RTX pipeline. Finally, we apply the algorithm to render "photorealistic" inside views of the flat torus, Poincaré sphere, and the hyperbolic mirrored dodecahedron. These are examples of Euclidean, spherical, and hyperbolic spaces: the Thurston classical geometries. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a new method to control scene sampling in complex ray-based rendering environments. It proposes to constrain image sampling density with a combination of object features, which are known to be well perceived by the human visual system, and image space saliency, which captures effects that are not based on the object''s geometry. The presented method uses Non-Photorealistic Rendering techniques for the object space feature evaluation and combines the image space saliency calculations with image warping to infer quality hints from previously generated frames. In order to map different feature types to sampling densities, we also present an evaluation of the object space and image space features'' impact on the resulting image quality. In addition, we present an efficient, adaptively aligned fractal pattern that is used to reconstruct the image from sparse sampling data. Furthermore, this paper presents an algorithm which uses our method in order to guarantee a desired minimal frame rate. Our scheduling algorithm maximizes the utilization of each given time slice by rendering features in the order of visual importance values until a time constraint is reached. We demonstrate how our method can be used to boost or stabilize the rendering time in complex ray-based image generation consisting of geometric as well as volumetric data. [Copyright &y& Elsevier]

Abstract: Interpolating scalar refinable functions with compact support are of interest in several applications such as sampling theory, signal processing, computer graphics, and numerical algorithms. In this paper, we shall generalize the notion of interpolating scalar refinable functions to compactly supported interpolating -refinable function vectors with any multiplicity and dilation factor . More precisely, we are interested in a -refinable function vector such that is an column vector of compactly supported continuous functions with the following interpolation property where and for . Now for any function , the function can be interpolated and approximated by Since is interpolating, for all , that is, agrees with on . Moreover, for or , such interpolating refinable function vectors can have the additional orthogonality property: for all and , while it is well-known that there does not exist a compactly supported scalar 2-refinable function with both the interpolation and orthogonality properties simultaneously. In this paper, we shall characterize both interpolating -refinable function vectors and orthogonal interpolating -refinable function vectors in terms of their masks. We shall study their approximation properties and present a family of interpolatory masks, for compactly supported interpolating -refinable function vectors, of type with increasing orders of sum rules. To illustrate the results in this paper, we also present several examples of compactly supported (orthogonal) interpolating refinable function vectors and biorthogonal multiwavelets derived from such interpolating refinable function vectors. [Copyright &y& Elsevier]

This paper presents a novel gradient-based image completion algorithm for removing significant objects from natural images or photographs. Our method reconstructs the region of removal in two phases. Firstly, the gradient maps in the removed area are completed through a patch-based filling algorithm. After that, the image is reconstructed from the gradient maps by solving a Poisson equation. A new patch-matching criterion is developed in our approach to govern the completion of gradient maps. Both the gradient and the color information are incorporated in this new criterion, so a better image completion result is obtained. Several examples and comparisons are given at the end of the paper to demonstrate the performance of our gradient-based image completion approach. [Copyright &y& Elsevier]

Video segmentation is an important preprocessing step for many computer vision and graphics tasks. Its main goal is to group the voxels in the video volume with similar appearance and motion into spatio-temporally consistent supervoxels. In this paper, we formulate video segmentation as an L 0 gradient minimization problem, so that the spatio-temporal coherence can be effectively enforced through a gradient sparsity pursuit way. In our method, the appearance and motion descriptor space is first built for over-segmented image patches of each video frame. Then the L 0 gradient minimization is performed in the descriptor space, for both spatial and temporal dimensions. To solve the non-convex L 0 norm minimization problem, we extend the fused coordinate descent algorithm from 2D image grids to 3D video volume. We conduct quantitative evaluation of our method in a public video segmentation benchmark LIBSVX. The experimental results demonstrate our superior performance to state-of-the-arts in segmentation accuracy and undersegmentation error, and comparable performance in boundary recall and explained variation. [ABSTRACT FROM AUTHOR]

In this paper we survey all known (including own recent results) properties of the longest-edge n -section algorithms. These algorithms (in classical and recently designed conforming form) are nowadays used in many applications, including finite element simulations, computer graphics, etc. as a reliable tool for controllable mesh generation. In addition, we present a list of open problems arising in and around this topic. [ABSTRACT FROM AUTHOR]

The design of reinforced concrete sections of arbitrary shape, namely with variable geometry, holes as well as with arbitrary distribution of reinforcing steel bars, is a very common task in civil engineering, reinforced concrete structures. The design of these sections requires the integration of non-linear stress fields on complex shapes, because of the non-linear behavior of concrete in compression. In this paper, a novel algorithm is proposed to compute the ultimate strength of reinforced concrete sections under biaxial bending. The algorithm includes section subdivision into trapezoidal elements using the techniques of polygon clipping algorithm proposed by Weiler–Atherton. Exact numerical integration for normal strength concrete ( f ck ⩽ 50 MPa) is achieved, for each trapezoid, using the change of variables theorem followed by Gauss–Legendre integration. The proposed technique is hereafter referred to as WAGL (Weiler–Atherton, Gauss–Legendre). The verification of the proposed algorithm is performed by comparing analytical results between the WAGL technique and methods proposed by other authors (five examples). Additionally, the results obtained are also compared with experimental results available in the literature. The application of the WAGL technique is illustrated with two RC cross-section design examples. [ABSTRACT FROM AUTHOR]

Abstract: Parallel implementations of Ray Tracing have been enabling real time performance, as the algorithm is embarrassingly parallel. However, in order to achieve both interactivity and real time performance, the algorithm should run at a high frame rates, i.e. at least 60 frames per second. Thus, a custom parallel design in hardware is likely to achieve high rendering performance. In this paper, we improve the GridRT architecture presented in previous work. GridRT is capable of dealing with the main desirable features of Ray Tracing, such as shadows and reflection effects, imposing low area cost and a promising rendering performance. As to this work, an application-specific instruction has been added and the underlaying computation embedded into the processor’s microprogram in order to calculate the ray–triangle intersection computations. These computations are performed in pipeline, whenever possible, yielding to a considerable reduction in terms of cycles per intersection test. The presented architecture is based on the uniform grid acceleration structure. It allows for a massive twofold parallelism: parallel ray–triangle intersection tests as well as parallel processing of many rays. A hardware implementation of the improved architecture is presented, together with the corresponding performance results and resources requirements. The rendering time is reduced by 80% using a grid configuration of eight processing elements and each intersection computation time is reduced by 50% with respect to the original GridRT implementation. [Copyright &y& Elsevier]

Abstract: Realistic rain simulation is a challenging problem due to the variety of different phenomena to consider. In this paper we propose a new rain rendering algorithm that extends present state of the art in the field, achieving real-time rendering of rain streaks and splashes with complex illumination effects, along with fog, halos and light glows as hints of the participating media. Our algorithm creates particles in the scene using an artist-defined storm distribution (e.g., provided as a 2D cloud distribution). Unlike previous algorithms, no restrictions are imposed on the rain area dimension or shape. Our technique adaptively samples the storm area to simulate rain particles only in the relevant regions and only around the observer. Particle simulation is executed entirely in the graphics hardware, by placing the particles at their updated coordinates at each time-step, also checking for collisions with the scene. To render the rain streaks, we use precomputed images and combine them to achieve complex illumination effects. Several optimizations are introduced to render realistic rain with virtually millions of falling rain droplets. [Copyright &y& Elsevier]

Abstract: In many applications, the first step into the topological analysis of a discrete point set P sampled from a manifold is the construction of a simplicial complex with vertices on P. In this paper, we present an algorithm for the efficient computation of the Čech complex of P for a given value of the radius of the covering balls. Experiments show that the proposed algorithm can generally handle input sets of several thousand points, while for the topologically most interesting small values of can handle inputs with tens of thousands of points. We also present an algorithm for the construction of all possible Čech complices on P. [Copyright &y& Elsevier]

Abstract: Silhouettes of polyhedra are an important primitive in application areas such as machine vision and computer graphics. In this paper, we study how to select view points of convex polyhedra such that the silhouette satisfies certain properties. Specifically, we give algorithms to find all projections of a convex polyhedron such that a given set of edges, faces and/or vertices appear on the silhouette. We present an algorithm to solve this problem in time for k edges. For orthogonal projections, we give an improved algorithm that is fully adaptive in the number l of connected components formed by the edges, and has a time complexity of . We then generalize this algorithm to edges and/or faces appearing on the silhouette. [Copyright &y& Elsevier]

Abstract: This paper presents an irregular stock cutting system (NEST) developed on AutoCAD software platform. A detail description to its mechanism is included. This development is based on two known techniques: the bitmap representation to transform all shapes drawn by AutoCAD into pixel matrices before nesting, and the bottom-left-fill algorithm for nesting. The system NEST is developed for further research works on practical stock cutting problems. It provides two important parameters: one is the precision level which decides how the bitmap representation can precisely describe a shape and therefore affects the time taken by nesting procedure; the other is the unit rotation angle which make a shape self-rotates in steps with small angle and to be finally placed on sheet material with its best self-rotation angle. NEST can tightly position every shape on a sheet material and performs satisfyingly from practical view point. The nesting result is demonstrated by the original drawings of all shapes and the sheet material instead of their graphics transformed from pixel matrices. Several tests are carried out to show its performance. [Copyright &y& Elsevier]

Abstract: Parallelism is becoming the leading paradigm in today’s computer architectures. In order to take full advantage of this development, new algorithms have to be specifically designed for parallel execution while many old ones have to be upgraded accordingly. One field in which parallel computing has been firmly established for many years is computer graphics. Calculating and displaying three-dimensional computer generated imagery in real time requires complex numerical operations to be performed at high speed on a large number of objects. Since most of these objects can be processed independently, parallel computing is applicable in this field. Modern graphics processing units (GPUs) have become capable of performing millions of matrix and vector operations per second on multiple objects simultaneously. As a side project, a software tool is currently being developed at the Institute of Aerospace Systems that provides an animated, three-dimensional visualization of both actual and simulated space debris objects. Due to the nature of these objects it is possible to process them individually and independently from each other. Therefore, an analytical orbit propagation algorithm has been implemented to run on a GPU. By taking advantage of all its processing power a huge performance increase, compared to its CPU-based counterpart, could be achieved. For several years efforts have been made to harness this computing power for applications other than computer graphics. Software tools for the simulation of space debris are among those that could profit from embracing parallelism. With recently emerged software development tools such as OpenCL it is possible to transfer the new algorithms used in the visualization outside the field of computer graphics and implement them, for example, into the space debris simulation environment. This way they can make use of parallel hardware such as GPUs and Multi-Core-CPUs for faster computation. In this paper the visualization software will be introduced, including a comparison between the serial and the parallel method of orbit propagation. Ways of how to use the benefits of the latter method for space debris simulation will be discussed. An introduction to OpenCL will be given as well as an exemplary algorithm from the field of space debris simulation. [Copyright &y& Elsevier]

Abstract: In this paper we introduce new algorithm implementations of a new parametric image processing framework that will accurately process images and speed up computation for addition, subtraction, and multiplication. Its potential applications include computer graphics, digital signal processing and other multimedia applications. This Parameterized Digital Electronic Arithmetic (PDEA) model replaces linear operations with non-linear ones. The implementation of a parameterized model is presented. We also present the design of arithmetic circuits including parallel counters, adders and multipliers based in two high performance threshold logic gate implementations that we have developed. We will also explore new microprocessor architectures to take advantage of arithmetic. The experiments executed have shown that the algorithm provides faster and better enhancements from those described in the literature. The FPGA chips used is Spartan 3E from Xilinix. The critical length in the circuit implemented on the FPGA had the minimum period for the proposed subsystem is 10.209ns (maximum frequency 97.957MHz). Maximum power consumed is 2.4mW using 32nm process and we used parallelism and reuse of the Hardware components to accomplish and speed up the process. [Copyright &y& Elsevier]

Abstract: Polycube map is a global cross-surface parameterization technique, where the polycube shape can roughly approximate the geometry of modeled objects while retaining the same topology. The large variation of shape geometry and its complex topological type in real-world applications make it difficult to effectively construct a high-quality polycube that can serve as a good global parametric domain for a given object. In practice, existing polycube map construction algorithms typically require a large amount of user interaction for either pre-constructing the polycubes with great care or interactively specifying the geometric constraints to arrive at the user-satisfied maps. Hence, it is tedious and labor intensive to construct polycube maps for surfaces of complicated geometry and topology. This paper aims to develop an effective method to construct polycube maps for surfaces with complicated topology and geometry. Using our method, users can simply specify how close the target polycube mimics a given shape in a quantitative way. Our algorithm can both construct a similar polycube of high geometric fidelity and compute a high-quality polycube map in an automatic fashion. In addition, our method is theoretically guaranteed to output a one-to-one map. To demonstrate the efficacy of our method, we apply the automatically-constructed polycube maps in a number of computer graphics applications, such as seamless texture tiling, T-spline construction, and quadrilateral mesh generation. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for approximating arbitrary polygonal meshes with subdivision surfaces, with the objective of preserving the relevant features of the object while searching the coarsest possible control mesh. The main idea is to firstly extract the feature lines of the object, and secondly construct the subdivision surface over this network. Control points are created by approximating these lines while the connectivity is built with respect to the anisotropy of the object. Our algorithm reinforces the similarity between the subdivision surface and the original shape by affecting an integer sharpness degree to each control edge in order to accurately reproduce the different curvature radii of corresponding fillets and blends. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a novel method that represents the highly complex point sets by clustering and reconstructing the points to normal-mapped B-spline surfaces (NBSs). The main idea is to construct elaborate normal maps on simple surfaces for the realistic rendering of complex point-set models. Based on this observation, we developed the coarse, NBSs to approximate the original point datasets with fine surface details. In our algorithm, a genetic clustering algorithm is proposed to automatically segment the point samples into several clusters according to their statistical properties, and a network of B-spline patches with normal maps are constructed according to the clustering results. In respect to signal processing, our algorithm decouples the original data into two collections: coarse geometry information and fine surface details. The multi-level B-spline surfaces are employed to describe the coarse geometry information, and the normal maps are constructed to capture the fine surface details. Our experimental results show that this representation facilitates the modeling and rendering of complex point sets without losing the visual qualities. [Copyright &y& Elsevier]

Abstract: This paper presents a new interpretation of a digital circle in terms of the distribution of square numbers in discrete intervals. The number-theoretic analysis that leads to many important properties of a digital circle succinctly captures the original perspectives of digital calculus and digital geometry for its visualization and characterization. To demonstrate the capability and efficacy of the proposed method, two simple algorithms for the construction of digital circles, based on simple number-theoretic concepts, have been reported. Both the algorithms require only a few primitive operations and are completely devoid of any floating-point computation. To speed up the computation, especially for circular arcs of high radii, a hybridized version of these two algorithms has been given. Experimental results have been furnished to elucidate the analytical power and algorithmic efficiency of the proposed approach. It has been also shown, how and why, for sufficiently high radius, the number-theoretic technique can expedite a circle construction algorithm. [Copyright &y& Elsevier]

Abstract: The winged- and half-edge data structures are commonly used representations for polyhedron models. Due to the complexity, students in an introductory course to computer graphics usually have difficulty in handling these data structures and developing applications. This paper describes the authors’ effort in the development of a visualization and animation tool for teaching and learning these data structures. This tool also includes a simple pseudo-code-like language for algorithm design. Instructors may employ this tool for presentation and demonstration purposes. Students may use the simple language to develop and experiment with new algorithms before their actual implementation. The visualization and animation system may be used to explore and understand the relationship among mesh elements and algorithm execution. [Copyright &y& Elsevier]

The Pythagorean tree is a fractal figure with a branching structure based upon the Pythagorean theorem. This paper describes the use of a greedy algorithm to encourage a homogenous spread of detail for asymmetrical trees and avoid localized regions of high detail. A model of prioritized branch growth based on this idea is used to optimize tree shape, allowing more visually interesting trees to be grown using significantly fewer segments. A comparison of the fractal dimension of the resulting shapes supports the general success of this approach. [Copyright &y& Elsevier]

The paper presents a new algorithm for point-in-polygon queries. By decomposing a polygon into a set of convex polygons and then constructing a BSP tree, the algorithm performs an inclusion query against the polygon in two steps. In the first step, it finds the convex polygon that is most likely to contain the query point through the BSP tree, and then in the second step, it tests whether the query point is in the convex polygon by employing advanced techniques for point-in-convex-polygon queries. The new algorithm is immune of singularity and has a performance of conducting a query by time demand in O(log n), and storage requirement in O(n). The time complexity of the preprocessing is O(n log n) for convex decomposition and BSP tree construction. The new algorithm has its performance in various aspects comparable to the state-of-art algorithms based on trapezoidation. Furthermore, as the number of convex polygons is always much fewer than the number of trapezoids in partitioning a polygon, and a high-quality search tree can always be constructed to manage the convex polygons, the new algorithm can run much faster than the trapezoidation-based algorithms, up to over double folds in maximum. [Copyright &y& Elsevier]

In this paper, we present a search method with multi-class probability estimates for sketch-based 3D engineering part retrieval. The purpose of using probabilistic output from classification is to support high-quality part retrieval by motivating user relevance feedback from a ranked list of top categorical choices. Given a free-hand user sketch, we use an ensemble of classifiers to estimate the likelihood of the sketch belonging to each predefined category by exploring the strengths of various individual classifiers. Complementary shape descriptors are used to generate classifiers with probabilistic output using support vector machines (SVM). A weighted linear combination rule, called adapted minimum classification error (AMCE), is developed to concurrently minimize the classification errors and the log likelihood errors. Experiments are conducted using our Engineering Shape Benchmark database to evaluate the proposed combination rule. User studies show that users can easily identify the desired classes and then the parts under the proposed method and algorithms. Compared with the best individual classifier, the classification accuracy using AMCE increased by 7% for 3D models, and the average best rank improved by 11.6% for sketches. [Copyright &y& Elsevier]

In geometric modeling and processing, computer graphics and computer vision, smooth surfaces are approximated by discrete triangular meshes reconstructed from sample points on the surfaces. A fundamental problem is to design rigorous algorithms to guarantee the geometric approximation accuracy by controlling the sampling density. This paper gives explicit formulae to the bounds of Hausdorff distance, normal distance and Riemannian metric distortion between the smooth surface and the discrete mesh in terms of principle curvature and the radii of geodesic circum-circle of the triangles. These formulae can be directly applied to design sampling density for data acquisitions and surface reconstructions. Furthermore, we prove that the meshes induced from the Delaunay triangulations of the dense samples on a smooth surface are convergent to the smooth surface under both Hausdorff distance and normal fields. The Riemannian metrics and the Laplace–Beltrami operators on the meshes are also convergent to those on the smooth surfaces. These theoretical results lay down the foundation for a broad class of reconstruction and approximation algorithms in geometric modeling and processing. Practical algorithms for approximating surface Delaunay triangulations are introduced based on global conformal surface parameterizations and planar Delaunay triangulations. Thorough experiments are conducted to support the theoretical results. [Copyright &y& Elsevier]

Triangle surface models belong to the most popular type of geometric objects description in computer graphics. Therefore, the problem of fast visualization of this type of data is often solved. One popular approach is stripification, i.e., a conversion of a triangulated object surface into strips of triangles. This enables a reduction of the rendering time by reducing the data size which avoids redundant lighting and transformation computations. The problem of finding an optimal decomposition of triangle surface models to a set of strips is NP-hard and there exist a lot of different heuristic stripification techniques. This paper should help to orient in the jungle of stripification algorithms. We present an overview of existing stripification methods and detailed description of several important stripification methods for fully triangulated meshes. As different authors usually use different data sets and different architectures, it is nearly impossible to compare the quality of stripification methods. For this reason we also present a set of tests of these methods to give the reader a better possibility to compare these methods. [Copyright &y& Elsevier]

In this paper we solve the following optimization problem: given a simple polygon P, what is the maximum-area polygon that is axially symmetric and is contained in P? This problem pops up in shape reasoning when planar shapes are approximated by simpler shapes, e.g., symmetric shapes, or when they are decomposed hierarchically into simpler shapes. We propose an algorithm for solving the problem, analyze its running time, and describe our implementation of it (for the case of a convex polygon). The algorithm is based on building and investigating a planar map, each cell of which corresponds to a different configuration of the inscribed polygon. We prove that the complexity of the map is , where n is the complexity of P. For a convex polygon the complexity is in the worst case. A substantial part of the work concentrates on calculation and analysis of arcs of the planar map. Arcs represent topological changes of the structure of the inscribed polygon, and are determined by the geometry of the original polygon. For each face of the map we calculate the area function of the inscribed polygons and look for a global maximum of the compound area function. We achieve this goal by using a numerical method. [Copyright &y& Elsevier]

Abstract: Volino and Thalmann have published a conjecture proposing sufficient conditions for non-selfintersection of surfaces. Such conditions may be used in solid modeling, computer graphics, and other application areas, as a basis for collision-detection algorithms. In this paper we clarify certain of the hypotheses of the proposed theorem, and give a proof. A brief summary of possible pitfalls related to using the conditions, when the hypotheses of the formal theorem given here are not satisfied, is also given. We also give examples, and show that the theorem can be extended to domains that are not simply connected. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce a new approach to line drawing that attempts to maintain a uniform packing density of horizontal segments to diagonal segments throughout the line. While the conventional line drawing algorithms perform linear time computations to find the location of the pixels, our algorithm takes logarithmic time. Also, experimental results show that the quality of line is acceptable and comparable to the well-known Bresenham''s line-drawing algorithm. [Copyright &y& Elsevier]

Abstract: Image morphing has been extensively studied in computer graphics and it can be summarized as follows: given two input images, morphing algorithms produce a sequence of inbetween images which transforms the source image into the target image in a visually pleasant way. In this paper, we propose an algorithm, based on recent advances from texture-from-sample ideas, which synthesizes a metamorphosis sequence targeted specifically for textures. We use the idea of binary masks—or texton masks—to control and drive the morphing sequence. Our solution provides an automatic mapping from source texels into target texels and thus guarantees a coherent and visually smoothing transition from the source texture into the target texture. We compare our morphing results with prior work and with simple interpolation between corresponding pixels in the same source and target images. [Copyright &y& Elsevier]

Abstract: This paper presents an intuitive, freehand sketching application for Computer Aided Design (CAD) that can reconstruct a 3D object from a single, flat, freehand sketch. A pen is used to draw 2D sketches consisting of straight and curved strokes connected at vertices. The sketches are processed by a reconstruction algorithm that uses the angular distribution of the strokes and their connectivity to determine an orthogonal 3D axis system whose projection correlates with the observed stroke orientations. The axis system is used to determine a plausible depth for each vertex. This approach works well for drawings of objects whose edges predominantly conform to some overall orthogonal axis system. A second, independent optimization procedure is then used to reconstruct each curved stroke in the original sketch, assuming that the curve is planar. New strokes can be attached to the 3D object, or drawn directly onto the object''s faces. An implementation of the reconstruction algorithm based on Levenberg–Marquardt optimization allows objects with over 50 strokes to be reconstructed in interactive time. [Copyright &y& Elsevier]

Abstract: Impostors can be used as an alternative representation of distant objects in complex 3D scenes. They work by replacing the distant object with a simple texture map. Although this texture map must be updated as the viewpoint moves around the scene, it is not necessary to do this every frame. The saving inherent in not completely rendering the entire scene for every frame means that using impostors can significantly improve frame rate. One of the main challenges presented by the implementation of such a rendering algorithm is the capture, organisation and tracking of the impostor textures needed for every object. This paper explores some ways of doing this using OpenGL in ways that make the best use of current consumer level graphics hardware. [Copyright &y& Elsevier]

A central geometric structure in applications such as robotic path planning and hidden line elimination in computer graphics is the visibility graph. A new parallel algorithm to construct the reduced visibility graph in a convex polygonal environment is presented in this paper. The computational complexity is O(p2log(n/p)) where p is the number of objects and n is the total number of vertices. A key feature of the algorithm is that it supports easy mapping to hardware. The algorithm has been simulated (and verified) using C. Results of hardware implementation show that the design operates at high speed requiring only small space. In particular, the hardware implementation operates at approximately 53 MHz and accommodates the reduced visibility graph of an environment with 80 vertices in one XCV3200E device. [Copyright &y& Elsevier]

This paper looks at an algebraic formulation of one dimensional cellular automata. Using the formulation connections to combinatorial structures and graph theory become clear. Strong results about uniqueness and isomorphism allows us to outline effective algorithms for the generation of exhaustive lists of reversible one dimensional cellular automata, and to count the number of distinct examples that exist. These algorithms use the “orderly algorithm” methods to avoid the pitfalls of brute force searches. [Copyright &y& Elsevier]

The field of computer graphics is expanding and evolving rapidly. Past computer graphics courses addressed low-level topics such as line drawing algorithms (Computers and Graphics 2000;24(1):151–155) while the graphics industry has moved toward scene graph representations of three-dimensional scenes. This discrepancy has moved some educators to suggest graphics courses exclude 2D topics for concentration on 3D. This paper suggests that such a switch is unnecessary and provides a course outline blending old and new topics to provide breadth and relevancy without abandoning the basics. [Copyright &y& Elsevier]