Computation of the Shadow Map and Sky View Factor of a terrain

Scientific relevance

As part of the development of a decision support system able to evaluate the potential of building roofs located in urban areas for producing solar energy and to identify “good candidate” roofs for installing solar panels, the goal of the iCeBOUND2 project is to investigate computation of the Shadow Map and Sky View Factor of a terrain (given as a Digital Elevation Model or Digital Urban Surface Model) using the emitter algorithm on GPUs. It extends the iCeBOUND project, conducted by Seif Ben Bader during his master thesis at EPFL, which was based on the receiver algorithm on GPUs.

The receiver model considers a cell in the map and computes whether it is shaded or not according to the sun position and the obstacle in front of it. Unlike this model, the basic idea behind the emitter algorithm is that the cells in the map are traversed following the sun beams direction and are shaded all at once. This way, memory transfer is reduced, in particular because elevation information is accessed only once per thread. There is, however, the possibility of a race condition when shading a cell which has to be taken care of.

This work is a collaboration between the HES-SO/Hepia (John White and Anthony Boulmier) and the SCITAS center (Gilles Fourestey).

Technical aspects

The goal of this project is to optimize the iCeBOUND GPU code even further. A first implementation was proposed by Seif Ben Bader during his master thesis work. This implementation is using a receiver approach: the sky visibility of each area (tile) is computed by determining whether this tile can see the sun or not. This approach is giving excellent results in an urban area where each point of the map has a very high chance to be obstructed by the higher building, therefore marching through the full heightfield is rarely occurring. However, in a more rural area, where obstruction is much more unlikely, this algorithm is accessing the heightfield information again and again, which lowers its performance.

We therefore propose to use the emitter approach that was developed as part of the e-SCT/iCeBOUND project. This version was implemented on MapReduce, it proceeds from the light source and following its direction through the tiles to determine if the points in the path are shaded. This approach has the advantage of computing all the points on the field once, but it has the disadvantage of requiring a data reduction at the end of the runs in order to merge all their path results into the full map and there is a priori no guarantee that all the points in a tile have been taken care of.

The basic idea behind the emitter implementation is that, contrary to the receiver implementation, when following the sun beam’s path, it is possible to shade all cells the heights of which are below the shadow threshold. In a sense, the emitter algorithm is more effective because it follows the information: the path on the map is computed by going in the same direction than the sun beams do. Consequently, the dynamic RAM (main memory) traffic is much lower compared to the receiver and the GPU cache is very likely to be used more than with the receiver. The main drawback of this implementation is that since each GPU thread is starting from a point of the map, it is likely that several threads will set the shadow flag in the space cell at the same time, which can be considered as a race condition. However, since the information will be the same (cells are not “unshaded”, once they are shaded their state will not change), it is safe.

Results

Whereas it is particularly effective in the case of the Shadow Map (Figure 1), the emitter paradigm is a little bit more problematic in the case of the Sky View Factor computation (Figure 2): the race condition that is not a problem for the Shadow Map computation is a problem here because for each sun position each thread needs to write the information for a particular cell concurrently. Therefore, an extra working array needs to be allocated to compute the shadow map for each sun position. Then, the information is reduced (added) to the main SVF array. This extra step does not exist for the receiver version.