Evaluation of Silhouette Rendering Algorithms in Terrain Visualisation
Ruzinoor Che Mat
Computer Science Department
The University of Hull
Phone Number: 006-04-9284795
currently working as lecturer in Nothern University of Malaysia
Dr. Mahes Visvalingam
Reader in Digital Cartography
The University of Hull
Hull HU6 7RX,
Phone Number: 44-(0)1482 465295
Computer graphics has now become an important and popular subject to study. It not only involves photorealistic rendering, or photorealism (realism), but also involves Non-photorealistic Rendering (NPR). In computer graphics, photorealistic-rendering attempts to make artificial images of simulated 3D environments to mirror the real world. This is different from NPR which produces images of a simulated 3D world in an artistic style. Researchers in NPR have investigated the display of 3D worlds using various display models. Recent works, for example, have focused on the modelling of artistic images and styles using silhouette rendering algorithms. This dissertation explores how silhouette rendering algorithms could be used in terrain visualisation. Reviews of silhouette rendering algorithms was done and two approaches were selected for implementation and testing with the real terrain data. These two approaches were implemented in a 3D modelling system to create a new method of displaying and viewing terrain data in an artistic style.Introduction
In particular, most approaches generate silhouette lines by detecting the edges between front-facing and back-facing polygons. The first approach implemented in this project was introduced by Dietrich (1999) and also implemented by Everitt (2001), using the cubemaps technique, taking advantage of a graphics card (GeForce 256) for rendering the silhouette. This approach works in real time and produces fast rendering. The second approach implemented in this project was introduced by Raskar and Cohen (1999) and this approach sets the front-facing polygons as white and the back-facing polygons are drawn as wireframe triangles; this was also implemented by Liu (2001). This project was implemented using the approach developed by Liu (2001). The wireframe approach produced more promising results than the cubemaps approach, and was tested with a different data set. Some limitations of this approach for sketching terrain are also highlighted. This dissertation show that silhouette rendering algorithms produce terrain images that are closer to human drawn illustration than those provided by traditional computer graphics approaches.
Research on terrain visualisation is being undertaken not only by cartographers and geologists but also by the computer graphics community. Most of the researchers aim to create 3D depictions of terrain that are detailed and accurate. The P-stroke style is one of the techniques developed for artistic depiction of terrain (Visvalingam and Dowson, 1998); but the P-stroke style is only appropriate for static sketches, works only in 2.5D, and does not show silhouettes correctly. Terrain sketches may be obtained through silhouette rendering algorithms from the image and/or the model of terrain. This dissertation investigated whether some existing silhouette rendering algorithms could be used to supplement the cues used in P-stroke sketching with a 3D-terrain visualisation system. It is also will be focused on the derivation of sketches from silhouette rendering algorithms. More specifically, this project will review the silhouette rendering algorithms, and select two approaches for implementation and testing with real terrain data. These two approaches were implemented in a 3D modelling system to create a new method of displaying and viewing terrain data in an artistic style.Previous Work in Terrain Visualisation
The first approach implemented in this project involved using the cubemaps technique, taking advantage of a graphics card (GeForce 256) for rendering the silhouette. This method was introduced by Dietrich (1999) and also implemented by Everitt (2001). This approach works in real time and produces fast rendering. The second approach implemented in this project was introduced by Raskar and Cohen (1999). It sets the front-facing polygons to white and the back-facing polygons are drawn as wireframe triangles; this was also implemented by Liu (2001). This project was implemented using the approach developed by Liu (2001). The wireframe approach produced more promising results than the cubemaps approach, and was tested with a different data set. Some limitations of this approach for sketching terrain are highlighted. This dissertation shows that silhouette rendering algorithms produce terrain images that are closer to human drawn illustration than those provided by traditional computer graphics approaches.
The main objective of this project are therefore as follows:-
This project has achieved its aim and objectives. The digital elevation models (DEM) was used as real data for modelling terrain in 3D. Two different types of DEM (Port Talbot DEM and Gettysburg DEM) have been used in implementation and testing. Two algorithms for silhouette rendering have been successfully implemented in this project.
- To evaluate different research on silhouette rendering algorithms and to select two approaches for implementation and testing with real terrain data.
- To provide software platforms for sketching terrain in 3D that can be extended and used with different approaches of sketching.
The first approach was implemented using Microsoft Visual C++ with OpenGL and the GLUT library. This approach has not been implemented using Borland C++ Builder due to some problems with rendering the silhouette. It used existing code provided by nVidia Corporation and code for the terrain model was added by the author in Microsoft Visual C++.
The second approach was implemented using Borland C++ Builder Version 5.0. A successful 3D-terrain model was developed by reading the DEM data from the file; the silhouette rendering algorithms were added to it and it produced good sketches of terrain. The OpenGL component was used for rendering the silhouette. The simple Graphical User Interface (GUI) was built using the Forms on Borland C++ Builder and produced a user friendly environment for the user. This program runs successfully on Windows 9x and Window NT.
Szemberg et al. (1997) produced methods for object and terrain visualisation by means of the combination of two algorithms, one for terrain data and one for objects. Their purpose was to generate, aerial images of terrain with objects, efficiently and rapidly. In this work, terrain surfaces are represented by regular grids described by 2D matrices, one determining the height at each point and the other determining the texture. These projects compared the results obtained with two approaches. One used the OpenGL Graphical System for visualising both terrain and objects. The other one used an optimised algorithm for visualising the terrain; the image and the depth information obtained are then transferred to OpenGL, to be integrated in the scene containing the objects.Research on Silhouettes
Actually, research in this area is much related to Non Photorealistic Rendering (NPR) technique. This paragraph reviews some techniques on NPR. Green et al. (1999) used an interactive NPR system, which has the capability to an interactively display a custom shaded model and edge lines. However, Markosian et al. (1997) presented new real time NPR technique based on an economy of line. This technique uses a rendered method for determining visible lines and surfaces, based on a modification of Appel's hidden line algorithm. They demonstrate the system with several NPR styles, which all operate on complex models at interactive frame rates. Erbert and Rheingans (2000) introduced volume illustration NPR in the context of a volume model. Their approach involved combining the familiarity of a physics-based illumination model with the ability to enhance important features using NPR techniques. The reality is that NPR software (Piranesi) now is available on the market (Richens, 2000). This software has a capability for rendering any 3D image as a Non-photorealistic image.
This project on sketching falls within the area of Non-Photorealistic Rendering (NPR), which was defined by Green et al. (1999) as concerned with producing imagery that look as if an artist had draw it. NPR has also described by Hertzmann (2001 p.7) as "any attempt to create images to convey a scene without directly rendering a physical simulation". The purpose of this technique is to produce images that appear to have been drawn by hand.Implementation and Evaluation
Researchers in NPR have investigated the display of 3D worlds using various display models. Recent works have focused on the modelling of artistic images and styles using silhouette (Hertzmann, 1999), graphite pencil (Sousa and Buchanan, 1999), computer generated watercolour (Curtis et al., 1997) and pen-and-ink illustration (Salisbury et al., 1997). The aim of this chapter is to provide a review of techniques for drawing silhouettes.
The silhouette techniques can be divided into those operating on
Silhouettes and edges are not the same. The main difference between them was provided by Kaltenbach and Veigl (2001 p.2) as "the edges are independent of the point view (if visibility is not concerned) while the silhouette is highly viewpoint dependent and, in general, not correspondent to edges." Hertzmann (2001 p.8) has provided an extensive review on silhouettes and the survey of the technological problem for finding visible silhouettes of 3D surfaces. He mentioned that "silhouette are important both perceptually and aesthetically. Efficient silhouette detection is an interesting technical problem, because silhouette typically occur only in a few places on a 3D shape at any given moment".
- 3D surfaces (model based)
- the image planes (image based)
Saito and Takahashi (1990) showed how silhouette edges could be used to enhance the display of images. The silhouette edges can be rendered by highlighting the discontinuities in the z-buffer derivative. This is similar with creases or folds in the image that can be rendered using same technique as before but for the second derivative of z-buffer. They also render the outlines of 3D objects by applying edge-detection filters to specially prepared depth and normal maps and compositing the results with the rest of the scene.
Curtis (1998) has introduced the loose and sketchy techniques for rendering silhouettes. This technique automatically draws the visible silhouette edges of a 3-D model by using image processing and a stochastic, physically based particle system. It requires only a depth map of the model and a few simple parameters set by the user to detecting the silhouette.
One-pass Silhouette RenderingThis method was introduced in the previous chapter. It has been implemented by taking advantage of the graphics card (GeForce 256) for showing silhouettes. The calculation of eye vector (E) and surface normal (N) are done using the cube map technique. Dietrich (1999) described cube maps as special textures that consist of 6 square faces, one each for +X, -X, +Y, -Y, +Z and -Z. It is indexed via 3D texture co-ordinates that represent a unit vector. A cube map is a directional look-up table which referring a RGBA colour for each input 3D vector. Because of this feature, cube maps are often used for environment mapping. To render using this technique, the steps needed are: -
By using this technique to render, the silhouette edge can be detected in the models.
- The -Z face would be totally white.
- The -+X and +-Y faces would be half white and half black.
- The +Z face would be totally black.
- Use model's normal vectors to index into cube map.
- The normal vector facing toward the side or the back of the viewer would produce black.
- The normal vectors facing the viewer would select white.Evaluation
Silhouette Terrain rendered by One-pass Rendering Method
This technique produced a good silhouette for 3D-terrain image. The slope, break slope, occlusion and valley are clearly shown in the model. But this effect only can be performed when the point of view is set at certain values close to the eye. Other than that, some problems can be pointed out from the model. These problem included:-
- There are many errors of omission and inclusion.
- Lack of balance.
- Sudden appearance and disappearance of shading on the plain.
- Unstable silhouette edges.Figure shows where there are missing silhouettes on the teapot surface and the terrain surface. All of the problems are marked by a square. For example, the teapot spout has missed the silhouette edges. The large area of grey at the bottom of the teapot is not a silhouette. The same problem has also occurred in the terrain, where the large areas of grey are seen in the flat area of the terrain. When the camera was moved, there are suddenly appearances and disappearance (omission) of shading on the plane.
Silhouette problem representation
This approach is faster because hardware is being used for acceleration. This approach will not work in a normal PC because this approach requires the hardware driver for the GeForceII card to run the program. The silhouettes produced by this approach give a better representation for the teapot image but not for terrain in 3D. What has been found in this investigation is that the cube map approach for rendering the silhouette still has a problem as already discussed.
Wireframe MethodThis method has been introduced by Raskar and Cohen (1999) and adapted by Liu (2001). Raskar and Cohen (1999) presented several simple methods to draw silhouette edges but Liu (2001) only implemented one of the methods and it rendering using stroke textures. This section will investigate and implement what has been done by Liu (2001). This method is called the Wireframe Method. The idea of this method is to render the front facing polygons as a white background and render the back facing polygons as a wireframe. It involved multi-pass rendering for highlighting silhouette edges.
This method has been implemented using Borland C++ Builder version 5.0 and OpenGL component. The code for this method is written in an object oriented fashion. The OpenGL component for this program is using a pre-existing component (TGLPanel) created by Ward (2001). The advantage of using Borland C++ Builder is that it makes it easy to implement the Graphical User Interface (GUI) and also creates a professional appearance. Other than that, by making code in object oriented fashion, it makes it easier to extend this program for another purpose. It also makes it easier for a programmer to understand the flow of this program.
The pseudo-code for this method to implemented in Borland Builder is as follows:-
- Draw background in black
- Enable back face culling
- Render front facing polygons in white
- Enable front face culling, set depth function "Less than or Equal To"
- Render back-facing polygons in wireframe mode in black
This technique also produced good 3D terrain silhouette edges. The silhouette edges produced using this method are better than those produced by the One Pass Silhouette Rendering method. For investigation on this method, there are many different approaches have been used for testing. One of the approaches is by setting the line width for silhouette edges with different size. As shown by Figure below, using different line width for depicting the silhouette edges, give different results. The silhouette edges producing by line width set as 2.0 seems to give the best results. Otherwise, silhouette edges produced by line width set as 4.0 is not reasonable for depicting the silhouette edges because the line width is too big for a silhouette edges.The second approach is by setting the silhouette edges as a line and line stipple. To set the line stipple, glLineStipple function has been used. The code below shows how this function is set in this program.
Silhouette edges with line width set as 2.0
Silhouette edges with line width set as 4.0Figure below shows the comparison of this approach
- // function for setting line stipple
- glLineStipple (1, 0x4444);
- glEnable (GL_LINE_STIPPLE);
- glDisable(GL_LINE_STIPPLE);Another approach for investigating this method is setting the different camera projections. One projection is set as orthographic and the other one is set as perspective. Figure below shows the result of this induction.
Silhouette edges set as a line with the line width set as 3.0
Silhouette edges set as a line stipple with the line width set as 6.0The silhouette edges in an orthographic projection are better than in perspective projection. The orthographic projection gives more information about the edges of terrain where it shows in detail the slopes and break slopes. But for perspective projection, some of the edges seem to be joining each other as a line. Therefore, to make a better appearance in perspective projection, it needs filtering towards the viewer.
Silhouette edges with projection camera set as orthographic function.
Silhouette edges with projection camera set as perspective function.
Some testing with different types of hardware have been done for investigating this method, focusing on the graphics cards. Table bellow shows the specification of both hardwares. The results of this test are shown in Figure bellow. It seems that the result produced by figure (a) is better than the results produced in figure (b). This is because the hardware used for figure (b) has not drawn the undertaken back-face culling properly. The circle shows where the problem occurs at the edges of the silhouette. This problem appears as a thick line of edges. When zooming into this line of edges, a wireframe of polygons will appear. In figure (a), drawn with proper back-face culling, all the thick lines have been thinned.
Table for Specification of different hardware used for rendering
PC Specification 1 PC Specification 2
- PentiumIII 750 MHz
- 256Mb RAM
- 15 Gb Hard Drive
- 50X CD-ROM Drive
- NVIDIA GEFORCE DDR VGA BIOS (Version 2.10.03.02.04) Creative (CT6971) (AGP)
- PentiumII 750 MHz
- 256Mb RAM
- 15 Gb Hard Drive
- 50X CD-ROM Drive
- ELSA GLADIAC MX 32MB SDR AGP (Version 3.11.00.18.33) GeForceII MX cards
a) Silhouette edges of terrain rendered using PC Specification 1
b) Silhouette edges of terrain rendered using PC Specification 2
Comparing results with using different hardwareThe last effect that can be observed from investigating this method is that the results of terrain image produced extra lines on the silhouette edges. These effects are shown by squared in Figure below:-Conclusion
Problem in the terrain images with wireframe methods.
From the evaluation,this method seem to be effective for showing the silhouette edges. By setting the edges as a different type of line and setting different camera projections, the user can get different information from terrain image. This method works in real-time and is relatively fast for rendering the silhouette edges. The edges of the silhouettes in wireframe method are rendered for each polygon, in order to produce the terrain image. This causes problem, where some lines look like the straight lines. For the whole, this method is very effective and suitable for use with the sketching technique.
Some suggestions for future work are listed below:-
The aim and objectives were met in full. This project makes a contribution to the Cartographic Information Systems Research Group (CISRG) at The University of Hull. It investigated the scope for artistic depiction of terrain using the proposed silhouette rendering algorithms.
By researching this project, valuable experience was gained on how to model terrain from the original grid DEM data, and also understanding of the algorithms for rendering the silhouette. Other than that, the author also learnt the new programming environment for creating a 3D model. This environment is called Borland C++ Builder and had not been used previously by the author. There are many ways for creating the 3D model using Borland C++ Builder. One of the ways is by using VCL (Visual Component Library) with the GLUT (discussed in Chapter 4) library to develop the 3D model. The author decided to use the OpenGL Component (TGLPanel), developed by Ward (2001) with the Borland C++ Builder to develop the 3D-model terrain. This improved the author's C++ and OpenGL programming skills, and also taught the author how to develop a program using RAD (Rapid Application Development) programming.
This project has been constructed in an object oriented fashion which makes it easy for another programmer to extend this program. Several idea for future work were produced, including the use of the code for silhouette rendering within a system for P-stroke sketching of terrain in 3D.
On the whole, silhouette rendering algorithms are found to be sufficient enough for visualising the terrain as an artistic sketch. Although the wireframe method for rendering the silhouette does not work in real time, it is enough for rendering the terrain as a silhouette. The wireframe method implemented by Liu (2001) was found to be quite useful for visualising image in 3D; it could be modelled as a Module in IRIS Explorer.
I would like to acknowledge the support and guidance that I have received from my supervisor, Dr. Mahes Visvalingam and to thank her for assisting with the preparation of this dissertation. I would also like to thank PhD students in The Department of Computer Science, John Whelan, Fotis Hadginikos, and Chris Mather, for suggesting software platforms that could be used in this project. Thanks are due to Chris Mather for an example of C++ and James Ward, Research Fellow in The Department of Computer Science, for letting me permission use his OpenGL component for this project and for debugging program.
I would also like to thank Dr. Helen Wright, Course Director of MSc Computer Graphics and Virtual Environments for answering questions on IRIS Explorer in relation to my project on silhouettes.
The digital elevation models (DEM) used in the implementation and testing of this research are provided by Ordinance Survey and The US Geological Survey respectively. The data remain their copyright.
Barequet,G.; Duncan,C.A.; Goodrich,M.T.; Kumar,S.; Pop,M.; 1999, Efficient Perspective-Accurate Silhouette Computation, Proceedings of the fifteenth Annual Symposium on Computational Geometry, pp. 417 - 418
Brandes, D.; 1983, Sources for Relief Representation, The Cartographic Journal, 20(2), pp. 87 - 94
Bremer, D.J.; Hughes, J.F.;
1998, Rapid Approximate Silhouette Rendering of Implicit Surfaces, In Proc.
The Third International Workshop on Implicit Surfaces. http://citeseer.nj.nec.com/cache/papers2/cs/11768/http:zSzzSzwww.cs.brown.eduzSzpeoplezSzjfhzSziszSzpaper.pdf/rapid-approximate-silhouette-rendering.pdf
Dietrich, S.; 1999, Cartoon
Rendering and Advanced Texture Features of the GeForce 256 Texture Matrix,
Projectives Textures, Cube Maps, Texture Coordinate Generation and DOTPRODCUT3
Texture Blending, Technical Report from NVIDIA Corporation.
Dowson, K.; 1994, Towards Extracting Artistic Sketches and Maps from Digital Elevation Models, unpublished PhD Thesis, The Department of Computer Science, The University of Hull, 203pp.
Erbert, D.; Rheingans, P.; 2000, Volume Illustration: Non-Photorealistic Rendering of Volume Models, Proceedings of IEEE Visualisation '00, pp. 195 - 200.
Everitt, C.; 2000, One-Pass Silhouette Rendering with GeForce and GeForce2, Technical Report from NVIDIA Corporation. http://partners.nvidia.com/marketing/developer/devrel.nsf/TechnicalDemosFrame?OpenPage [Accessed 4/08/2001]
Foley, J.; 2000, Getting There: The Ten Top Problems Left, IEEE Computer Graphics and Applications, 20(1), pp. 66 - 68
Gooch A.; Gooch B.; Shirley P.; Cohen E.; 1998, A Non-Photorealistic Lighting Model for Automatic Technical Illustration, Proceeding of SIGGRAPH 98, pp. 447 - 452.
Gooch A.; 1998, Interactive Non-Photorealistic Technical Illustration, Master Thesis The University of Utah, 56 pp.
Hertzmann, A.; 1999, Introduction to 3D Non-Photorealistic Rendering: Silhouettes and Outlines, SIGGRAPH '99 Course Notes. http://www.mrl.nyu.edu/hertzmann/
Kaltencbach, A.; Veigl, S.;
2001, Non-Photorealistic Rendering in Technical Illustrations, ProSeminar:
Lau, L., 1997, Terrain Visualisation
TerraView, Technical Report from Advanced Computational Modelling Centre
University of Queensland.
http://www.acmc.uq.edu.au/~ll/thesis/html/client/Scape.html#SGIMachine [Accessed 9/07/2001]
Lesage, P.L.; 1999b, [Online,
1999], Towards real-time sketch-based exploration of terrain data : an
investigation of image processing operators, Unpublished Masters Thesis,
University of Hull.
http://www2.dcs.hull.ac.uk/CISRG/people/lesage [Accessed 8/03/2001]
Liu, J; 2001, Computer Generated
pen-and-ink Illustration, Technical Reports Department of Computer Science
SUNY at stony brook.
http://www.cs.sunysb.edu/~jliu/cse528/final_proj_report.html [Accessed 8/03/2001]
Raskar R.; Cohen M.; 1999, Image Precision Silhouette Edges, Proceedings of the 1999 symposium on Interactive 3D graphics, Atlanta, GA USA, pp. 135 - 140
Saito T.; Takahashi T.; 1990, Comprehensible Rendering of 3D Shapes, Computer Graphics (Proceeding of SIGGRAPH '90), 24(4), pp. 197 - 206
Visvalingam, M.; Dowson, K.; 1998, Algorithms for Sketching Surfaces, Computer and Graphics, 22(3), pp. 269 - 280
Visvalingam, M.; 1999, Art in
Scientific Visualisation of Terrain Data, [Online]
http://www2.dcs.hull.ac.uk/CISG/ [Accessed 6/03/2001]
Visvalingam, M.; Whelan, J.C.; 1998, Occluding Contours within Artistic Sketches of Surfaces, in Eurographics-UK '98, (16th Annual Conference of the Eurographics Association, University of Leeds, 25 - 27 March 1998), pp. 281 - 289.
Ward, J.; 2001, Tutor, Department of Computer Science, The University of Hull. http://www.crema.co.uk
Whelan, J.; 2001, Final Year
PhD Students, The University of Hull.
Last Updated: 28 October 2002