Formulated Silhouettes for Sketching Terrain
© John C Whelan and
    Mahes Visvalingam, 2002

Croplogo.jpg (11317 bytes)
For the sake of posterity, please cite from the published version:
Whelan J C and Visvalingam M (2003) “Formulated Silhouettes for Sketching Terrain”, In Jones M W (ed.) Proceedings of Theory and Practice of Computer Graphics 2003, Birmingham, UK, 03-05 June 2003. p. 90 – 97
 

Contents

Figures

The figures have been reduced for  web access. To view detailed SVG files, click on the Figures.

Next
An evaluation

Abstract

The mathematical definition of silhouettes within NPAR is based on the assumption that silhouettes are the eye-centred projections of occluding contours on an imaging plane. However, occluding contours are insufficient for sketching the silhouettes of hills as drawn by cartographers. The research reported in this paper is based on the proposition that silhouettes are mental visualisations of the outlines of objects which arise from knowledge and experience of the visual world. This paper does not seek to provide an alternative definition of silhouettes. Instead, it tests the proposition that missing silhouette elements should be drawn on those visible surfaces which will become occluded if the camera position is lowered.   In the upright untransformed model, these candidate locations will have negative gradients in the view direction.  We term these candidate locations visible slopes with negative gradients. In this study, which uses a heightfield representation of terrain, parts of surface profiles parallel to the view direction are used as surrogates for these candidate locations.  A slope-based filter selects points from these candidate parts of these visible negative slopes for thinning and chaining into 3D polylines, called Formulated Silhouettes. These silhouettes do resemble the outlines drawn by people, encouraging their immediate use in the visualisation of other layers of thematic data within Digital Cartography and GIS.  Some limitations of the current prototype approach are presented to spur future hypotheses-based research on silhouettes.

KEYWORDS:  Silhouettes, Occluding Contours, Algorithmic Sketching, Terrain Visualisation, P-strokes
1.    Background and Introduction

The Cartographic Information Systems Research Group (CISRG) of the University of Hull pioneered research on the algorithmic sketching of terrain, under the direction of Visvalingam (Visvalingam 1999). The input consists of a matrix of heights. Visvalingam's algorithm (reported in Visvalingam and Whyatt, 1993) has proved useful for locating important breaks of slope in regular cross-sectional terrain profiles lying parallel and orthogonal to the line of sight, as demonstrated by computer-generated P-stroke sketches of terrain (Dowson, 1994; Visvalingam and Dowson, 1998 and 2001). The term P-stroke stands for profile stroke since the sketch consists of filtered sections of profiles, lying orthogonal to the line of sight.  The P-stroke sketch in Figure 1 does not include silhouette lines as such. Instead, silhouettes are suggested by longer P-strokes on convexities along the line of sight.  The explicit identification and rendering of silhouettes as continuous and elegant polylines would make some of these P-strokes redundant and make the sketches more airy, elegant and more useful as background in 3D thematic mapping (Visvalingam, 1990).
1.jpg (83923 bytes)

Figure 1 : P-stroke sketch of a Digital Elevation Model
Data:  © Crown Copyright; Ordnance Survey
Source: Visvalingam and Dowson 1998, p. 277, reprinted with permission from Elsevier Science.

There has been considerable interest in the real-time identification of precise silhouettes for use in non-photorealistic animation and rendering (NPAR); see for example Markosian et. al. (1997), Gooch (1999), Raskar and Cohen (1999) and Lake (2000). Silhouettes have been assumed to be occluding contours in architectural renderings (Sasada 1987) and in GIS (Weibel and Herzog 1989). The mathematical definition of silhouettes within NPAR continues to be inspired by Marr's (1982) occluding contour and assumes that silhouettes are the eye-centred projections of occluding contours. The projected depiction of these contours within a traditional 3D graphics pipeline has posed implementation problems requiring some tweaking, for example by Raskar and Cohen (1999), to guarantee their appearance. The precise identification and stylistic rendering of such occluding silhouettes, for use in real-time applications, remains a research problem. This paper, like that by Visvalingam and Dowson (1998) is mainly concerned with what should be drawn rather than with how they should be drawn.

Visvalingam and Whelan (1998) noted that occluding contours enhanced P-stroke sketches. However, the corresponding P-strokes could not be omitted because the occluding contours were not picking out other lines, sketched in by P-strokes, which would be treated as if they were silhouettes by artists and cartographers. Also, occlusion plays a progressively diminishing role when the viewpoint is raised in the map-like oblique views used by Visvalingam and Dowson (1998; 2001).

The research reported in this paper is based on the proposition that silhouettes are mental visualisations of the outlines of objects which arise from knowledge and experience of the visual world. The research on algorithmic sketching was inspired by the landscape drawings and field sketches of past masters of the art (Murchison 1839; Homes 1876; and Lobeck 1939). Their outlining of forms, which reflect how we conceive landforms with the mind's eye, is not constrained by the definition of silhouettes as occluding forms. Their silhouettes are functional and serve to indicate the spatial arrangement and characteristic profiles of landforms in a way that occluding contours alone cannot do.

It is not the aim of this paper to provide a single alternative quantitative definition of silhouettes since the projected outlines are imagined and not real. As the placement of imagined silhouettes need not be precise, they can be derived using a novel method as discussed below. It is apparent that missing parts of imagined silhouettes are located on those visible DEM slopes which will become occluded if the viewpoint is lowered. In the upright untransformed model, these candidate locations will have negative gradients in the view direction.   In this study, which uses a heightfield representation of terrain, the parts of surface profiles parallel to the view direction are surrogates of these candidate locations.  The points constituting these visible profile sections (with negative gradients) will be referred to as the candidate set or c-set. 

The model-based method used in this feasibility study consisted of slope-based filtering of the c-set, early in the visualisation pipeline. The filtered points were then thinned and chained to generate linear graphical primitives in 3D. These entities are called Formulated Silhouettes to stress that they are just one possible way of contriving the imagined parts of silhouettes. The illustrations, used in this paper, are based on copyrighted 1:50,000 DEMs supplied by the Ordnance Survey of Great Britain (OSGB).  Further testing based on 1:10,000 and 1:50,000 data supplied by OSGB and the USGS, show that Formulated Silhouettes do resemble the outlines drawn by people and that they can be used in the visualisation of other layers of thematic data within Digital Cartography and GIS (Whelan 2001). Here, an indication is provided of the value of using Formulated Silhouettes within P-stroke sketches. Some limitations of the current approach to formulating silhouettes are noted to spur further research.
2.    Occlusions are insufficient
Figure 2 shows a terrain block tilted towards the viewer by 40%; this implies that untransformed slopes  with a gradient of less than -40% along the view direction will be backfacing and occluded. Figure 2b shows the resulting occluding contours; these occluding contours are not enough for sketching the outlines of many of the features which need to be shown.  The sketch, which consists of incoherent bits and pieces of silhouettes, is incomplete and is unsatisfactory. 

2a.jpg (13634 bytes)

 2b.jpg (9614 bytes)

Figure 2: The inadequacy of occluding contours (Data: ã Crown Copyright, Ordnance Survey)

As noted above, the missing sections of silhouettes can be found within the visible slopes with negative gradients, which appear as dark areas in Figure 2a.   Stevens (1981) used the same regularly spaced profile lines, as in Figure 2a, to show how the compression of these lines within these areas, making up our c-set, provides surface information even where there is no occlusion.   Image-based techniques do recover these missing contours. Saito and Takahashi (1990) and Chang (1998) edge-detected these areas in image space as a visible curvature of the z-buffer. The use of a headlight in a Lambertian-shaded model produces similar dark areas in the projected luminance maps. Pearson and Robinson (1985), Watt (1988) and Lesage (1999) extracted sketches from such luminance maps. Watt (1988) proposed that the luminance map can yield the silhouettes and other internal creases in one pass. Although it does produce quite impressive sketches of terrain, Lesage and Visvalingam (2002) noted some problems, including gaps in silhouettes and inappropriate connection of silhouettes when lines are thickened on edge strength.

 

3.   Formulated Silhouettes

When the upright DEM is tilted towards the viewer by 40%, untransformed slopes between 0 and -40% become the candidate set (c-set), shown in Figure 3.  It is obvious that this set includes many locations, such as the valleys and plateau tops, not all parts of which would be sketched as silhouettes. When the DEM is rotated back to its upright position, the silhouettes will retreat up the slope towards the viewer.   Formulated Silhouettes represent anticipations of such occlusion but they cannot be found from gradients along the view direction alone.

Slopes orthogonal to the view direction are also very important in revealing the shape of the landforms. These slopes parallel and orthogonal to the view direction convert to luminance information provided by a horizontal headlight and vertical top light as used by Lesage and Visvalingam (2002). Decaudin (1996,   reported in Hertzmann (1999)) used similar information projected onto RGB colour bands to locate occlusions and other creases in the normal map.

This feasibility study filters data with these two first derivatives at the model level, early in the processing pipeline.   The filter tolerances were based on Macgregor's (1957, p 170) observation that a slope of 20% is of "crucial importance" since it represents the limits of cultivation. He also noted that a slope of 10% is clearly noticeable. Geographers tend to use systematic cut-offs, as they do when they classify age into 5-year categories, since these are intended to be indicative heuristics rather than precise measures. So, the cut-offs for automation had to be fine-tuned by trial and error. The directional derivatives are  weighted differently as shown in Figure 4.

3.jpg (43326 bytes)

Figure 3: The candidate points (c-set)

4.jpg (14394 bytes)

Figure 4:  Parameters for the slope-based filter

Orthogonal slopes in excess of absolute 20%  are retained and a more sensitive value of -12% is used along the view direction. The line A, passing through the origin,  is the perpendicular to the line connecting these two cut-offs.  Slopes with a diagonal aspect are retained by use of a control point, which is constrained to lie on line AB.  The location of the control point (X) was found by trial and error and our experience shows that this needs to be adjusted for some types of terrain.  In Figure 4, slopes falling within the greyed area will be removed from the c-set since they are not steep enough to cause significant silhouettes.  The subset (f-set), filtered on a column slope of 8.75% for the control point, is shown in Figure 5.  The f-set retains 8.6% of the original data in this hilly area. The problem areas, with silhouettes missing in Figure 2b, are still retained.

5.jpg (12622 bytes)

Figure 5:  The filtered set (f-set)

The f-set can be slope shaded in various ways to render the silhouettes. Since silhouettes are portrayed by polylines in many sketches, the f-set was thinned to create more white space for thematic mapping. Points in the f-set leading up to occlusions are redundant and discarded. Where the run of visible f-set points do not terminate in an occlusion, the furthest points is retained. This decision was based on trial and error. The thinned set (t-set) retained only 3.5% of the input data items. Although the various types of filtering were undertaken in sequence for scrutiny of intermediate results, they can be performed on each line of sight in parallel by hardware along with the P-strokes as noted by Visvalingam and Dowson (1998).

6.jpg (25481 bytes)

Figure 6:  Chained Formulated Silhouettes

These points are then chained into linear primitives (shown in Figure 6) to generate the Formulated Silhouettes. Silhouettes consisting of a single point were removed to eliminate noise (see Figure 7). This figure shows the generalised set (g-set) retaining 2.9% of points.   Some of these points could be retained and connected to longer silhouettes in an intelligent way. Despite this, the results are much better than those in Figure 2b and are more akin to hand drawn sketches. Note that the features highlighted as missing in Figure 2b are now present. The study shows that formulated silhouettes can be extracted using slope information alone.

7.jpg (14532 bytes)

Figure 7:  Post-filtered Formulated Silhouettes

4.   Applications
Visvalingam and Dowson (1998) noted that, unlike the silhouettes of solid objects, the open silhouettes of terrain appear to float in space and that many artists use mist, trees and so on to bed them in. Through trial and error they found extension rules for concavities to ensure that convex forms were 'grounded'. This problem does not occur with sketches from luminance maps since they include all sorts of edges to convey the solid mass of terrain even when sparse sketches were animated (Visvalingam and Lesage, 2002). Silhouettes are only used on their own for portraying distant terrain. They normally form the framework within which other information is shown; for example, Saito and Takahashi (1990) combined the silhouettes with height contours and hill shading. However, as noted by Lesage and Visvalingam (2002), height contours viewed obliquely can give a misleading impression of landforms; they noted, for example, that the plateau in Figure 1 looks like a hill in Macaire’s (1997, p 95) contour plot.

8.jpg (43028 bytes)

Figure 8: Formulated Silhouettes to enhance the P-stroke sketch

The primary aim of the feasibility study was to enhance line drawings, such as the P-stroke sketch.  An SVG file shows a P-stroke sketch with relatively few strokes.  Figure 8 shows how the P-stroke sketch can be enhanced by adding Formulated Silhouettes, which include occluding contours.  Here the P-strokes have been filtered so that they do not start or extend into the f-set. The number of points removed (2.6% of DEM points) is almost the same as the number of points added by silhouettes in the g-set (2.9%). This sketch consisting of a total of 11.8% of the DEM points is much more effective when viewed at more appropriate larger scales. Even at this reduced scale, many of the relief forms can be clearly seen.   It is possible to vary the amount of detail by omitting classes of P-strokes, and by varying the thresholds and extension rules (Visvalingam and Dowson, 1998). With these Formulated Silhouettes, it is even possible to omit the entire set of P-strokes if the thematic content provides sufficient cues as noted above.

These sketches are useful in geographical and geological mapping; in civil engineering projects, such as architecture and highway engineering; in military applications and tourism amongst others. In addition to their use as free-standing displays, they can also be included along with other supplementary material, such as text and photographs, in tourist and walkers maps.  Information on a variety of thematic layers is often draped as shading onto the terrain surface. Since land use is often attuned to slopes, the cultural information provides indications of concavities which help to tie the silhouettes into place.  In such displays, shading on surface normals and aerial perspective can reduce the clarity of the thematic information and vector enhancement is more helpful. Whelan (2001) showed that the Formulated Silhouettes enhanced slope maps and maps of remote-sensed data draped over images without detracting from their content.   30 metre resolution remote sensed imagery was overlaid as a simple texture onto the terrain in Figure 9.  The silhouettes show the landforms without detracting from the thematic content.  Silhouettes can also be used to enhance colour washed 3D visualisations of underlying surface geology as in the topographic sketches illustrating early geological texts (see Murchison, 1839).

rsi1.jpg (53197 bytes)

a) Terrain draped with Remote Sensed Image

rsi2.jpg (60890 bytes)

b) Same image with the Formulated Silhouettes in Figure 6

Figure 9 : Enhancement of remote-sensed imagery
(Image : © British National Space Centre, 2000)

Given the low data volumes in vector sketches (Figure 7 uses only 2.9% of the input points), sketches are also useful for viewing high resolution DEMs over the web and on mobile devices with limited bandwidth.   Although initially sceptical about computer-drawn sketches, members of the Map Design Group of the British Cartographic Society now welcome this strand of research since it provides scope for importing the vectorised sketch data into mapping systems for use in map publishing. The revival of the dying art of landscape drawing within NPAR and Digital Cartography also offers opportunities for cross-disciplinary research, such as into the psychology of vision, and also prompts a re-examination of the philosophical underpinning, semantics and pragmatics of cartography and of the language of maps.

5.    Future Work

Given the utility of imagined Formulated Silhouettes, future research could be pitched at different levels, including:

  1. Adaptive filtering. Figures 6 and 7 illustrate the unbalanced generalisations which result from application of global slope thresholds. Most of the c-cells on the low ridge to the right of the figures have been lost and the ridge is largely picked out by the P-strokes.  However, a reduction in the filter tolerances will lead to clutter in the hilly areas.
  2. Alternative conceptualisations of silhouettes. In terrain with low relative relief, there were insufficient Formulated Silhouettes, let alone occlusions (Visvalingam and Whelan, 2002). Che Mat (2001) found similar problems with the wireframe method proposed by Raskar and Cohen (1999).  A different approach, or even a different style, may be more effective for sketching such landforms.
  3. Operationalisation of imagined silhouettes within the dynamic 3D environment.

6.    Conclusion
In much the same way in which stereo vision is a product of mental fusion, silhouettes are the outcome of a spontaneous integration of light, texture and motion related cues in the real world. Silhouettes emerge when experienced forms are projected onto the scene as sensed. This feasibility study has shown how we could use a simple slope filter, based on  geographic observations, to abstract plausible Formulated Silhouettes, from what we have termed visible slopes with negative gradients.  New directions of research have been opened up through a clear distinction between silhouettes and occlusions.

ACKNOWLEDGEMENTS

Our special thanks go to past and present members of the CISRG participating in this research programme especially Dr. Kurt Dowson for his software for P-stroke sketching. We are grateful to the Ordnance Survey for permission to use their sample DEM  in this research.  The remote-sensed imagery comes from a British National Space Centre CD-ROM, "Window on the UK 2000".

References

British National Space Centre, 2000, "Window on the UK 2000", CD-ROM.   The data is © National Remote Sensing Centre, based on © ESA/Eurimage raw data.

Chang G., 1988, On-Line (Last accessed 25/06/02) "Curvature-based Pen and Ink Drawings from 3-D Polygonal Objects", Master of Engineering Report, Cornell University, www.nbb.cornell.edu/neurobio/land/OldStudentProjects/cs490-97to98/glenchang/index.html

Che Mat R., 2001, Evaluation of silhouette rendering algorithms in terrain visualisation, Unpublished Taught MSc Dissertation in Computer Graphics and Virtual Environments, Department of Computer Science, The University of Hull.

Decaudin P, 1996, "Cartoon-Looking Rendering of 3D-Scenes", Technical Report 2919, IN-RIA, June 1996.

Dowson K., 1994, Towards extracting artistic sketches and maps from digital elevation models, Unpublished PhD Thesis, The University of Hull

Hertzmann A., 1999, "Introduction to 3D Non-Photorealistic Rendering: Silhouettes and Outlines." In Green S., editor, SIGGRAPH'99 Course Notes. Course on Non-Photorelistic Rendering. New York, 1999., pp. 7-11 - 7-14. http://www.mrl.nyu.edu/~hertzman/hertzmann-intro3d.pdf

Holmes W. H., 1876, in Lobeck A. K., 1924, Block Diagrams and Other Methods used in Geology and Geography pp. 178 - 179

Gooch B., Sloan P-P, J., Gooch A., Shirley P., Riesenfeld R., 1999, "Interactive Technical Illustration". In Spencer S. N., editor, Proceedings of the Conference on the 1999 Symposium on interactive 3D Graphics, New York, April 1999. ACM Press., pp. 31 - 38

Lake A., Marshall C., Harris M., Blackstein M., 2000, Stylized rendering techniques for scalable real time animation, Procedings of NPAR 2000, Annecy, France, June 5-7, pp. 13 - 20

Lesage P-L and Visvalingam M., 2002, "Towards Sketch-based exploration of Terrain : a feasibility study", Computers and Graphics 26(2), pp. 309 - 328.

Lesage P-L, 1999, Towards real time sketch-based exploration of terrain: an investigation of image processing operators, Unpublished MSc Thesis, University of Hull

Lobeck A. K., 1939, Geomorphology: An Introduction to the Study of Landscapes, New York and London, Graw-Hill Book Company

Macgregor D. R., 1957, "Some Observations on the Geographical Significance of Slopes", Geography, vol. 42, pp. 167 - 173

Marr, D., 1982, Vision, W. H. Freeman and Company

Markosian L., Kowalski M. A., Trychin S. J., Bourdev L. D., Goldstein D., Hughes J. F.,1997, "Real-Time Non-Photorealistic Rendering, Computer Graphics", Proc. SIGGRAPH 97, http://www.cs.brown.edu/research/graphics/npr/home.html

Macaire, G (1997) Beyond Linear Perspective through the Deformation of 3D Objects, Unpublished MSc Thesis, University of Hull

Murchison R. I. 1839, The Silurian System, London, John Murray, Albemarle Street

Pearson D. E., Robinson J. A., 1985, "Visual Communication at Very Low Data Rates", Proceedings of the IEEE, 73 (4), pp. 795 - 812

Raskar R., Cohen M., 1999, "Image Precision Silhouette Edges". In Spencer S. N., editor, Proceedings of the Conference on the 1999 Symposium on interactive 3D Graphics, New York, April 1999. ACM Press., pp. 135 - 140

Saito T., Takahashi T., 1990, "Comprehensible Rendering of 3-D Shapes", Computer Graphics, 24(4), pp. 197 - 206

Sasada T. T., 1987, "Drawing natural scenery by computer graphics", CAD, 19(4), pp. 212 - 218

Stevens K. A., 1981, "The Visual Interpretation of surface contours", Artificial Intelligence, 17, pp. 47 -73

Visvalingam, M, 1990, "Trends and concerns in Digital Cartography" Computer-Aided Design 22 (3), 115 - 130.

Visvalingam M., 1999 (Online), "Exhibition on Art in Scientific Visualization of Terrain Data", http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/index.html

Visvalingam M., Dowson K., 1998, "Algorithms for Sketching Surfaces", Computers and Graphics, 22(2-3), pp. 269 - 280

Visvalingam M., Dowson, K., 2001, "Towards cognitive evaluation of computer-drawn sketches", The Visual Computer, 17, pp. 219-235

Visvalingam M., Whelan J. C., 1998, "Occluding Contours within Artistic Sketches of Surfaces", Proceedings of Eurographics UK ‘98, pp. 281, 289

Visvalingam M., Whelan J. C., 2002, "Sketches of the Gettsburg Battlefield", http://www2.dcs.hull.ac.uk/CISRG/projects/Getty-VI/index.htm

Visvalingam M., Whyatt, J. D., 1993, "Line Generalisation by Repeated Elimination of Points", Cartographic Journal, 30(1), pp. 46 - 51.

Watt, R.J, 1988, Visual Processing : Computational, Psychophysical and Cognitive Research, Hove : Erlbaum

Weibel R., Herzog A., 1989, "Automated Construction of Panoramic Views from DTMs", Geo-Processing Series, Dept. Geog. University of Zurich, 12, pp. 67-98

Whelan J. C., 2001, Beyond Factual to Formulated Silhouettes, Unpublished PhD Thesis, The University of Hull
Page maintained by: Mahes Visvalingam and John Whelan
Last updated on 30 June 2002

Cartographic Information Systems Research Group, University of Hull