CG AROUND THE WORLD
Vol.32 No.1 February 1999
Graphics Research at National Centre for Software Technology in India
S.P. Mudur, S. Gopalsamy, Dinesh Shikhare, D.S. Dixit, B.S. Patwardhan, N.S. Nayak, S.V. Shanbhag
The National Centre for Software Technology is an autonomous research and development institution of the government of India. It is a centre for excellence in software technology and related computer science areas. It carries out research in a number of disciplines such as databases and knowledge engineering, artificial intelligence, computer networking and Internet, software engineering and graphics and CAD.
The graphics and CAD division of the centre has been active in this field since the early seventies and is one of the oldest and well-established research groups in this area in India. The current group numbers more than 20 graphics researchers with about 10 interdisciplinary associates in areas like visual design and communication, digital architecture, calligraphy, animation and linguistics.
In the very early years, the focus was on graphics and CAD for electronic design, (PCBs, IC Mask layouts, etc.) By the mid seventies, the emphasis shifted to core graphics systems with 3D support. A number of commercially viable packages, such as IndoGKS and IndoPHIGS, based on international standards, were developed collaboratively with the industrial partners and sold worldwide. Over the last 15 years the group has been very active in 3D graphics and computer aided geometric design. A parallel track right from the mid seventies has been electronic publishing with particular emphasis on software architectures for dealing with the complexity of multiple scripts and languages in the country. In each of these subfields the group has undertaken high end implementation projects for end use and distribution, and also carried out substantive fundamental research that has found its way in the form of research publications in prestigious international journals and conferences.
For the remainder of this article, we provide a brief overview of some recent research work. For more details on the division’s activities and publications, the interested reader is referred to the following Web site: http:://www.ncst.ernet.in/~graphics.
Computer Aided Geometric Design
This is one area in which the group has been continuously active for over two decades. The work has resulted in a number of innovative ideas in the form of computational techniques for representing and processing of geometric objects, carried out as doctoral research. In addition, the group has undertaken a number of research and development projects, sponsored both by government organizations and industry. Zeus is a 3D surface modeling system that includes powerful facilities for discretisation of faces, surfaces and volumes. Artemis and Arcturus are systems for composite laminate architecturing, and Clodion is a system for mechanism design and simulation.
Zeus is an interactive system for the design, specification and visualization of aircraft geometries. The system incorporates a comprehensive suite of tools that provides facilities for surface modeling, surface grid generation and volume grid generation. Zeus has multiple methods for creation of curves and surfaces.
The package supports surfaces defined in a number of representations such as curves, planes, bi-linear surfaces, NURBS and triangulated surfaces. It derives its main strength from the fact that it includes a comprehensive suite of tools for surface and volume grid generation and robust geometric algorithms for surface-surface intersection, projection of points/curves onto surfaces. The model of usage would typically follow the sequence described below.
Surface Modeling: Surface geometry is either imported from packages like CATIA™ or is constructed from section curves by lofting a surface or is defined by control points. To generate surface grids or meshes on faces of interest, the surfaces must be intersected, trimmed and then meshed.
Surface Grid Generation: Two distinct approaches available for surface grid generation are paneling and topology-based grid generation.
Paneling: Grid generation by paneling proceeds by taking planar sections of the surface configuration. Usually a parallel set of planes is used for obtaining intersection curves. These curves are trimmed and discretised and a mesh is constructed by joining corresponding points across adjacent curves (see Figure 1).
Topology-based methods: These methods obtain a topological identification of faces over the surfaces in the given geometry. The edges of faces are discretised by distributing points over them using a user defined clustering function. Zeus has two types of grid generation methods:
Structured quadrilateral grid generation: The boundary points satisfy rectangular topology. The interior points are distributed to obtain as much orthogonality at grid-line intersections and as much smoothness of arc-length and area gradients as possible (see Figure 2).
Unstructured surface triangulation: This class of grid generation method can handle faces with non-rectangular boundary topology. A face is identified over the 3D surface geometry and triangulated with constraints such as aspect ratio and density. Zeus has Delauanay-based as well as advancing front algorithms implemented for direct surface triangulation (see Figure 3).
The computational fluid dynamic (CFD) analyses by finite element methods of 3D volumetric spaces, like the volume surrounding an aircraft, rely on the availability of volume grid generation tools. These tools enable rapid discretisation of a given volume into a set of simple 3D volume elements, like tetrahedra or hexahedra. VolGrid provides the following capabilities:
Volume definition: The package provides an interface for composing volume definition using triangulated surface patches, and standard enclosures like sphere, cylinder, etc. and tools for merging surface grids along boundaries, closing gaps by local triangulation, orienting the surfaces as desired to obtain a well-defined bounded volume (see Figure 4).
Volume grids: VolGrid incorporates a tetrahedral volume grid generation method using Delaunay triangulation. The method includes and satisfies the initial boundary definition for the volume specified using the surface triangulation (see Figure 5).
Smoothing: A modified Laplacian smoothing operator has been implemented. This operator is iteratively applied to all interior vertices.
Visualization and Analysis: The package supports the following ways of visualizing volume grids: (a) planar cuts of tetrahedral grids, (b) views of the grid with layers of tetrahedra peeled off, (c) visualization using external tools such as VRML viewers. Analysis of surface and volume grids is done statistically with information about the ranges of minimum and maximum values of parameters like facet areas, volumes of tetrahedra, aspect ratios, dihedral angles, density, etc.
Artemis is a surface development package for manufacturing composite laminates. The algorithms built in the software can handle doubly curved surfaces. The flattening algorithm performs curvature analysis to discretise to planar quadrilateral patches. These quadrilateral patches are further triangulated, and a special planar development algorithm obtains a surface development, with cracks and overlaps aligned to a particular direction. Artemis incorporates automatic realignment of these dussets to user defined orientations, while maintaining the surface area and similar constraints. Figure 6 shows the flattened patch with cracks and overlaps in different orientations of a sample 3D surface shown in Figure 7.
Arcturus is a 2D detailed skin engineering system tailored to meet the needs of manufacturing of composite laminate components with special provisions to handle laminate architecture. It supports constrained editing of laminate zones and ensures integrity of the data. In addition to the standard facilities, Arcturus recognizes and provides editing facilities for zones in laminate layers. It includes a robust implementation of geometric operations like offsetting, chamfering, trimming and intersections. The graphical user interface of the package has advanced features and techniques such as forward feedback mechanism, layering and grouping.
Clodion is a mechanical system simulation package designed and implemented jointly with IIT Bombay. The mechanical system, a mechanism, is a collection of links, rigid or flexible, joints connecting these links, applied forces and imposed motions at various key points on the links. Major features of Clodion are:
Figure 8 shows the multi-frame dump for a mechanism which is being animated.
Electronic Publishing in Indian Languages
India is a multilingual country with 18 recognised official languages and over 6,000 dialects. The primary emphasis has been on the digital encoding, rendering and processing of Indian language information.
Indian Language Encoding Fundamentals
Indian language character encoding differs in interpretation from Latin script based characters, primarily due to the non-alphabetic nature of their scripts. Unlike Latin characters, a “syllable” - the Indian language equivalent unit of a written letter, has to be composed of one or more characters entered through the keyboards or any other input mechanism. There are far too many syllables to be encoded separately. A syllable is composed of vowels, consonants, modifiers and other special graphics signs. The machine then composes syllables at run time based on language dependent rules. The encoding scheme developed at NCST is the pure consonant encoding scheme. This scheme can encode unambiguously all written Indian language text and has been used in all of NCST’s Indian language products and applications.
Shaping of Indic Texts
Indic characters can combine or change shape depending on their context. A character’s appearance is affected by its ordering with respect to other characters, the font used to render the character and the application or system environment. A font normally contains certain component glyphs from which a syllable is composed at run time. For every syllable there is a corresponding sequence of glyphs. This constitutes a many-to-many mapping from encoded characters to glyphs as opposed to the simplistic one-to one mapping in Latin scripts.
NCST has developed its own shaping architecture for rendering Indian language characters and has used it in the word processors that it has developed (See Figure 9). Aalekh, the first Indian language word processor developed at NCST, made its debut in the year 1988 and ran on the PC and PC compatibles. This was followed by the Vividha series of text processing tools and a Windows based version called Darshan appeared in 1997. NCST worked closely with Microsoft Corporation, USA, in Microsoft’s localisation efforts by transferring some of its Indian language shaping know-how into their upcoming Windows 2000™ OS. This OS may be the first to support Indian languages natively.
Text Processing Components
NCST has been actively involved in applying its Indian language knowledge to industry requirements. Some of the applications developed by NCST for the industry have been automatic transliteration among different Indian languages, printing bilingual university student certificates, transliterating and printing telephone directories in local languages, etc. Much of the processing technology is in the form of software components such as multilingual edit controls, rasterisers, code converters, transliterators, name converters, etc. that can be quickly assembled together to meet an application’s requirements.
Visualisation of Complex 3D Environments
Extensive research has been carried out in the area of illumination computations, rendering and visualisation of complex 3D environments and volumetric data. The particle tracing technique based on Monte Carlo simulation of light propagation was developed here as part of doctoral research. Performance enhancement techniques were devised for direct volume rendering.
VISPAR, a research project for investigating parallel and distributed graphics computations with partial support from the Commission of European Countries (CEC) as part of CEC’s ITDC scheme, was conducted in collaboration with M/s BULL Overseas Limited. The main objective was to evolve high performance computing techniques (utilising parallel computing) that can be used to suitably enhance the implementation of NCST’s particle tracing method and produce a system for facilitating the user/designer to walkthrough in real time in complex 3D digitally modeled environments, rendered in a visually realistic manner. A distributed task delegation framework architecture for obtaining high performance in interactive manipulation and walkthrough computations of very large virtual environments has been developed. For rendering a scene that includes specular surfaces and participating media, we have devised an adaptive multi-paradigm rendering process. The entire rendering process is partitioned to use Gouraud shading and Z-buffer technique to render diffuse surfaces, ray tracing to render only the reflective and refractive surfaces and ray casting to render volumes. The overall improvements in performance are very good.
Figure 10 shows a view of a complex 3D scene rendered using the VISPAR approach. The virtual environment consists of 43,000 surface elements that include a reflecting mirror and steam coming from the spout of a teapot. The steam has been modeled as participating media using hyper-texture. The distributed multi-agent architecture and the adaptive multi-paradigm rendering process are significant contributions of the research in VISPAR.
Direct Volume Rendering Enhancement
In the course of this research, a number of performance enhancement techniques to direct volume rendering methods have been devised. We first devised a basic performance enhanced version of the direct volume-rendering algorithm. This technique segments the rendering task into two stages – a first stage in which a bounding front surface of voxels above a given density threshold is obtained, and a second stage in which the normal ray casting technique with rays starting from the front surface are used. This was followed by algorithmic extensions to the above two-stage algorithm. Each of these algorithms resulted in improved rendering speeds, and are for different data properties and visualisation requirements. A special algorithmic technique uses rotational coherence to rapidly compute intermediate views when looking around the volume continuously. Extensive performance analysis studies were carried out comparing the speed improvements and image quality obtained by the use of these different methods. Figure 11 shows a sample of the typical kind of volumetric data set on which the studies were done.
Components for Multimedia and VR
A toolkit (see Figure 12) of software components is being developed which will enable rapid assembly of applications which need to use multimedia and VR technology elements. Six classes of components envisaged are geometry, animation, audio/video, rendering, user interface and framework.
Geometry components provide a kernel for creating, manipulating and operating on curves and surfaces, including NURBS. Rendering components perform the task of generating an image from a scene description, for a given camera specification. Some components provide view dependent rendering with hidden surface removal, smooth shading, reflections, textures and volumes. Other components enable global illumination computation for effects like color bleeding, soft shadows and caustics.
Animation components provide a framework and the mechanisms required for animating 2D and 3D objects. The component set includes motion simulation support to handle kinematic constraints and forces.
Audio/video components provide services to help playback of audio and video elements in the application. The audio and video elements can be in different formats.
User interface components provide different high-level interaction techniques required by applications in this domain.
Framework components bind together all the other components into a coherent application. Framework components are application domain specific and have been planned for domains like geometry editing, virtual walkthroughs and 3D gaming and guided multimedia presentations. These components are responsible for instantiating, initializing and managing interactions among the components constituting the application.
These components are being effectively tested and used through two projects, Fatehpur Sikri Walkthrough and Captain Vyom: Sky Warrior 3D game.
The Walkthrough Framework Component
For the virtual walkthrough, the digital model being used is of an ancient city - Fatehpur Sikri - in northern India, capital of the great Mughal emperor Akbar between 1570 and 1586. Our digital architecture associate Vivek Punjabi created the digital model. The walkthrough allows the user to experience a past era, which was rich in architecture, technology, arts and even religious tolerance. The city is among the most well preserved abandoned cities in the world, apart from its well-planned architectural layout. It houses some of the finest monuments and regal courtyards providing immense technological challenges due to size, intricacies and dynamic requirements. Some of the interesting features of the walkthrough include a huge data set (5M textured polygons), intricate model, see-through textures, complex lighting effects and temporal media elements. Figures 13, 14 and 15 are some sample screen shots during the walkthrough.
The 3D Gaming Engine Component
The game is interactive, making use of only three-dimensional digital models and is based on an ongoing popular Indian television series, Captain Vyom. The television series has a regular viewership of over 10 million, and hence has established brand equity that can be enhanced through the game. The series is a futuristic, science fiction, adventure thriller using an extensive amount of 3D computer graphics and special effects. The game is built around the same storyline as the series, with all the special behavioural characteristics of the characters, be they good or evil. The game makes use of an existing library of high (broadcast) quality imagery and three-dimensional models. Three-dimensional models are used to capture complex spaces and environments, space ships, weapons and many other things that are associated with a science fiction thriller. Figures 16, 17 and 18 show some screen shots.
This article has briefly tried to cover a range of research projects that the National Centre for Software Technology has been working on in the area of graphics. The work described is certainly not exhaustive. In addition, for example, considerable theoretical level work has been conducted whose results have not been described due to lack of space. These include the area of algorithmic implementations of Minkowski operations on geometric representations, robust computation methods for geometric intersection algorithms and automatic synthesis of natural movement of articulated bodies.
The authors are grateful to all colleagues whose names are too numerous to mention and who have contributed in the past to the activities of the group.
If you would like to provide an overview of computer graphics in your country, please contact one of our Computer Graphics Around the World columnists listed on the right.
The copyright of articles and images printed remains with the author unless otherwise indicated.
Fraunhofer-Institut fuer Graphische
210 King St East
Toronto, Ontario M5A 1J7
Tel: +1-416-362-8558 x8589