/ Satoshi Nishimura / Assistant Professor
/ N. M. Thalmann / Visiting Professor
/ Veronique Martin-Lang / Visiting Researcher
The Computer Graphics Laboratory is currently working on the following research projects:
Parallel processing is one of the most powerful ways for improving the processing speed of computers. Especially in the area of computer graphics, many researchers have been trying to apply the techniques of parallel processing to various problems. There are three reasons for this research:
In the Computer Graphics Laboratory, we have a parallel graphics machine called the VC-1 which was developed by Prof.~Nishimura, one of the members of our laboratory. The VC-1 comprises 16 processing elements each of which contains the Intel i860 processor.
One of the current research directions is the extension of the VC-1 architecture so that anti-aliasing is fully supported. We are also planning to add special hardware for rasterization to the VC-1 architecture to improve polygon rendering performance.
Another research direction is to develop a parallel machine for real-time volume rendering. Volume rendering is particularly important in medical applications. We are planning to develop scalable hardware including a special chip for trilinear interpolation and alpha-blending.
Shape of a 3-dimensional object is a concept of fundamental importance for its description, analysis and representation. Many combinatorial models have been proposed and extensively studied for the representation of subdivided objects (e.g. incidence and adjacency graphs, combinatorial maps, simplicial sets, etc). These models take essentially the topology of the subdivision into account whereas most information about the shape is left to the imbedding. We focus our research on the definition of a representation of a surface via some of its shape information. Some differential geometry considerations led us to the fact that curvature-based features and especially ridges and ravines are a good characterization of the shape. More precisely, we are interested in the detection of extrema of the maximal principal curvature along the associated principal direction. We developed a fast and robust numerical algorithm which detects the ridges of any smooth surface defined by a height function and we are now working on its extension to any surface. The method is inspired from image analysis techniques. We are also working on the surface reconstruction problem from the ridges.
Refereed Journal Papers
This thesis describes a parallel computer architecture for real-time image synthesis together with a parallel polygon rendering algorithm for it. The first half of the thesis describes the hardware architecture. It is based on a loosely-coupled MIMD multiprocessor architecture. The most remarkable difference from previous parallel architectures for computer graphics is the existence of a novel frame buffer subsystem called the conflict-free multiport frame buffer (CFMFB). In the CFMFB, a local frame buffer is prepared for each processor and a merged picture of all the local frame buffer contents is displayed on the screen. In the local frame buffer, a demand-paging technique is utilized for reducing memory requirements. A prototype machine called the VC-1 is developed to evaluate this architecture and also to provide an environment for developing parallel software. The second half of the thesis focuses on a parallel polygon rendering algorithm for the above architecture. In the algorithm, the set of input polygons is partitioned among the processors, each of which independently computes the images of assigned polygons using the Z-buffer method. To improve the performance, two techniques, adaptive parallel rasterization and dynamic cluster rebalancing, are developed. From the performance measurement, the linear speed-up of the VC-1 architecture is observed up to a 256-processor system.
The VC-1 is a parallel graphics machine for polygon rendering based on image composition. This paper describes the architecture of the VC-1 along with a parallel polygon rendering algorithm for it. The structure of the VC-1 is a loosely-coupled array of 16 general-purpose processors, each of which is equipped with a local frame buffer. The contents of the local frame buffers are merged in real time for generating the final image. The local frame buffers are virtualized with a demand-paging technique, by which the image memory capacity for each local frame buffer is reduced to one eighth of full-screen capacity. Polygons are rendered in either pixel parallel or polygon parallel depending on the on-screen area of each polygon. The real performance of the VC-1 as well as estimated performance for systems with up to 256 processors is shown.
This work fits into the domain of topology-based geometric modeling. An assembling of non-overlapping patches can be interpreted as a subdivision of a geometric object into cells of different dimensions and a combinatorial structure can be associated with it. More precisely, our study deals with the manipulation of simplicial sets imbedded on triangular patches. We give the definition and properties of simplicial sets and triangular Bezier spaces and discuss the relationship between these two entities. The advantages of this approach are developed and some construction operations for the manipulation of this structure are presented.
This study comes within the scope of geometric modeling, more precisely, topology-based modeling. A subdivision of an onject is represented by a combinatorial structure (which defines the topology of the object) and an imbedding into the Euclidian 3-dimensional space. The mathematical notion of simplicial set is the basis of a general framework for the definition of many combinatorial structures. So, we are studying different problems related to simplicial sets : definition, implementation and use of construction operations and algorithms for computing topological properties ; extension of these operations and algorithms for handling several cellular combinatorial structures defined in geometric modeling for representing the topology of any subdivision. We present in this paper a part of this study, i.e. the definitions of two classes of simplicial structures (semi-simplicial and simplicial sets), definition of imbedding (based on triangular Bezier spaces), and the definitions (for these structures) of several classical construction operations (creation of a simplex with its boundary, identification, extrusion, inverse operations). These structures and operations are implemented in the kernel of a modeler of triangulated geometric objects.