Hybrid terrain models combine large regular data sets and high-resolution irregular meshes [triangulated irregular network (TIN)] for topographically and morphologically complex terrain features such as man-made microstructures or cliffs. In this paper, a new method to generate and visualize this kind of 3D hybrid terrain models is presented. This method can integrate geographic data sets from multiple sources without a remeshing process to combine the heterogeneous data of the different models. At the same time, the original data sets are preserved without modification, and, thus, TIN meshes can be easily edited and replaced, among other features. Specifically, our approach is based on the utilization of the external edges of convexified TINs as the fundamental primitive to tessellate the space between both types of meshes. Our proposal is eminently parallel, requires only a minimal preprocessing phase, and minimizes the storage requirements when compared with the previous proposals.

In this paper, we present a meshing scheme for the implementation of an adaptive tessellation of triangular meshes on the graphics processing unit (GPU). Tessellation is performed according to a local test to generate primitives dynamically. The refinement procedure does not require the pre-computation of any refinement pattern. The resulting adaptive procedure is efficient and simple, and generates the tessellation pattern of each triangle dynamically. The non-recursive strategy simplifies mesh reconstruction, avoids irregular memory access patterns and uses a simple control flow to make it a good candidate to guide the evolution of tessellation algorithms on future graphics cards. To test our proposal, we have used the geometry shader of current GPUs to generate primitives dynamically.

Nowadays GPUs are commodity hardware containing hundreds of cores and supporting thousands of threads that can be used to accelerate a wide range of applications. From a programmer's perspective, GPUs offer a stream processing model which requires the application of new techniques to exploit their capabilities. In this paper we present the application of the split-and-merge technique to the following parallel tridiagonal system solvers on the GPU: cyclic reduction and recursive doubling. The split-and-merge technique naturally splits the algorithm flow in parallel paths that can be solved in shared memory, and later merged in global memory. In this way, we can solve large systems of equations efficiently exploiting the memory hierarchy of the GPU. The results obtained show a significant acceleration compared with the direct implementation of the algorithms on the GPU.

Hybrid terrains are a convenient approach for the representation of digital terrain models, integrating heterogeneous data from different sources. In this article, we present a general, efficient scheme for achieving interactive level-of-detail rendering of hybrid terrain models, without the need for a costly preprocessing or resampling of the original data. The presented method works with hybrid digital terrains combining regular grid data and local high-resolution triangulated irregular networks. Since grid and triangulated irregular network data may belong to different datasets, a straightforward combination of both geometries would lead to meshes with holes and overlapping triangles. Our method generates a single multiresolution model integrating the different parts in a coherent way, by performing an adaptive tessellation of the region between their boundaries. Hence, our solution is one of the few existing approaches for integrating different multiresolution algorithms within the same terrain model, achieving a simple interactive rendering of complex hybrid terrains.

The hierarchical radiosity algorithm provides high-quality illumination and the view-independent results obtained can be re-employed for different camera positions. On the other hand, the utilization of multiresolution models is a common solution for the real-time rendering of complex scenes. In this case, the level of detail of each object depends on the specific camera position. Unfortunately, global illumination computations may present an important performance loss in this context. In this paper we present a new solution for hierarchical radiosity for multiresolution systems. Our proposal is based on the application of an enriched hierarchical radiosity algorithm to an input scene with low-resolution objects (represented by coarse meshes) and the efficient data management of the resulting values. The representation of the information we use permits the application of the radiosity values obtained for the coarse version of an object to finer resolution versions of that object. Results of our implementation show that our algorithm produces high-quality images with an important reduction in computational costs.

Physically-based illumination is an essential factor for realistic rendering. In this context, hierarchical radiosity is one of the most accurate global illumination methods. One of the key features of the radiosity approach is that it obtains view-independent global illumination results. Unfortunately, global illumination has high computational and memory requirements, and hierarchical radiosity, though more efficient than other radiosity solutions, is not an exception. The progressive popularization of multiprocessor and multi-core processor systems makes the design and implementation of efficient parallel algorithms an appealing alternative in this field. In this paper we present a novel parallel radiosity method addressing the hierarchical radiosity computation on current homogeneous multi-core environments. One of the main contributions of our work is the use of different tasks to exploit the independent interactions among the geometric elements in the scene. Our parallel solution leads to a versatile radiosity implementation that takes advantage of the multiple computational resources in the system, such as multi-core processors and SMT (Simultaneous Multithreading) capabilities. Good results in terms of performance have been achieved.

Nowadays, one of the most active areas of research in computer graphics is focused on improving the performance of global illumination methods. In this paper we present a new parallel method for hierarchical radiosity computation. Contrary to usual solutions in the literature our approach carries out an effective partitioning and distribution of the input geometry among the processors. Thus, the memory constraint is reduced when processing large scenes. The method presented in this paper also introduces a multi-thread scheduling to improve interaction between processors. This solution replaces the polling strategy usually used in parallel computing, when several independent tasks need to establish asynchronous communication. The great flexibility of our parallel implementation has been demonstrated by the good results achieved on a testbed with different computing systems and test scenes

The demand for high quality and speed in graphical representations of 3D scenes is continuously increasing. An important aspect of visual realism is real-time processing of transparent objects. In order to provide a realistic solution to be considered for future graphics cards, proposed extensions to the hardware need to be small. In this paper, we propose two new hardware oriented proposals for computing order independent transparency for any number of layers. The first proposal is based on the precomputation of the contribution factor of each element to the final colour of the pixel. This permits the evaluation of the transparent objects without requiring their previous sorting. The second proposal is based on the utilization of a pre-sorting stage so that the transparent objects are organized in a back to front order. In both proposals, time requirements are reduced with respect to previous solutions.

Point based rendering techniques have recently become a promising alternative for high quality rendering of complex scenes. In order to handle a high number of points, the current graphics cards structure has to be analyzed for efficient exploitation of the hardware resources available. In this context, the real time perspective projections become a challenge because of the reduced number of dividers available in the graphics cards and their recursive structure. In this paper, we present a point projection algorithm that avoids the division operations. The technique we propose is based on the identification of the candidate pixels on the screen, and the selection of the correct one through simple comparison operations. The simplicity of the algorithm we propose permits the utilization of different projection units operating in parallel. We also present a scheduling that permits the introduction and efficient exploitation of a pipelined system. The algorithm is regular, simple, and characterized by efficient data management so that the processing rate is directly associated with the number of projection units employed. As a result, real time performance for the projection operations, even for critical scenes, can be achieved.

This paper presents a new design for two operand normalization. The two operand normalization operation involves the normalization of at least one of two operands by left shifting both by the same amount. Our design performs the computation of the shift by making an OR of the bits of both operands in a tree network, encoding the position of the first nonzero bit. The encoded position is obtained most significant bit first, and then there is an overlapping with the shifting operation. The design we propose replaces two leading zero detector circuits and a comparator, that are present in the conventional approach. Our scheme demonstrates to be more area efficient than the conventional one. The circuit we propose is useful in floating point complex multiplication and COordinate Rotation DIgital Computer (CORDIC) processors.

The Viterbi algorithm is widely used in communications and signal processing. Recently, several area-efficient architectures for this algorithm have been proposed. Area-efficient architectures trade speed for area by means of mapping the N states of the trellis describing the Viterbi algorithm to P processing elements, where N>P. In this paper a practical VLSI implementation of an area-efficient architecture to evaluate the Viterbi algorithm is presented. The architecture that has been implemented is composed of only two processing elements and the corresponding routing network to process, in different cycles, all the states of the trellis. The resulting architecture has been integrated in a chip using a 0.7 /spl mu/ CMOS technology, occupying an area of 9 mm/sup 2/.

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages.

The main part of the Viterbi algorithm is a nonlinear feedback loop which presents a bottleneck for high-speed implementations. We present a novel scheduling scheme that allows increasing the available speed of the system. This is done through the utilization of look-ahead techniques to compute non-sequential data and, in this way, break the recursivity of the algorithm. This permits introducing pipelining. As a result, we obtain a speed growth comparable to previous parallel solutions, but with less hardware cost.

Trellis coded quantization (TCQ) is an efficient technique for encoding memoryless sources. Furthermore TCQ can be incorporated into a transform coding structure (such as the discrete cosine transform) for encoding monochrome and color images with fixed rate or entropy-constrained schemes. In all these cases an expanded codebook is partitioned into subsets used to label the branches of an appropriate graph (trellis). For a given data sequence, the Viterbi algorithm is then used to find the minimum mean square error path through the trellis. We present a generic architecture scheme that can be easily adapted to the different TCQ image compression methods. We also present a formal model that permits a regular and modular design solution that is optimal for a particular set of area and/or speed constraints.