ART GALLERY PROBLEM

Many years ago GI in rendering wasn’t as fast and easy to use as it is today. It was indeed possible but for animations you had to pre-bake indirect illumination as much as possible. One way of doing this was to place a bunch of cameras at good positions before shooting rays into the scene. Generally this sounds easy but the interesting question was the following: What are good camera position? To save render time you had to use as few cameras as possible but at the same time it was necessary to cover as much as possible of the scene. Basically this is a visibility problem and exactly what the classical art gallery problem is all about. There exist various algorithms which could be used in different ways. Some are listed here:

https://en.wikipedia.org/wiki/Art_gallery_problem

A fairly simple and efficient algorithm is described in a paper by Michael Batty and Sanjay Rana. It’s closely related to spatial analysis and since I already had some experience in this field it was finally the algorithm I implemented in Houdini.

M. Batty, S. Rana: The automatic definition and generation of axial lines and axial maps

 

ISOVIST AND VISIBILITY GRAPH

Isovists and visibility graphs are quite interesting and have been used in different fields throughout the last 30 years. They were used to analyse and understand space, helped to predict how people move through museums and were the conceptual basis for numerous path- and wayfinding applications. Broadly speaking, both isovist and visibility graph do generally the same thing but in different ways. An isovist is basically a polygon describing the visible area or volume around a given point, whereas a visibility graph is, as the name implies, a graph connecting visible points which is stored internally as adjacency matrix . Although the algorithms are different, the measures you’ll get by using one or the other are quite similar. For example: max and min distance to obstacles, average distance, area, perimeter, different statistics based on distances, and so on to name a few. These measures can be used later to derive properties of the analysed space. Thus it became important in the field of architecture and urban planning, robot motion planning and computational geometry, But it’s also used in other less obvious areas like sociology, spatial cognition and architectural psychology.  For a more complete explanation check out the following links:

https://en.wikipedia.org/wiki/Isovist
https://en.wikipedia.org/wiki/Visibility_graph

There exist various specialized software packages which can compute such a visibility analysis but out of interest I thought I implement my own version in Houdini. Most of the algorithms are written in C++ though it might be possible to do most of it in VEX nowadays. The main reason why I did use the HDK is simple because I used BGL (Boost Graph Library) for some calculations on the visibility graph and also because of better performance. While VEX is fast and gives you multithreading for free, C++ is still faster in this case, mainly due to the fact that I needed to do a lot of calculations on large arrays.

The images below show the main difference between the isovist and a visibility graph in 2D. The isovist on the left is a polygon describing the visual area around a viewpoint, whereas the visibility graph on the right is basically an adjacency graph. If we do the calculation on more than just one point, the result is a field with various measures indicating different spatial properties.

The obvious choice how to to compute the isovist is by rotating around a vector and test for intersections with the environment. It is easy to implement but leads to a number of problems. For instance, in the left image below the vector is rotated around in one degree steps. This is sufficient for nearby walls but results in poor precision at larger distances and acute angles. A much better approach is to sample directly the points of the surrounding geometry (image on the right side below). This works simply by checking the points visibility. If the point in visible, check for subsequent ray-intersections and finaly compute the isovist. This solution is not just much better precision-wise but also performance-wise. Instead of at least 360 rays I had to shoot just 56 rays into the scene.

Most of the measurands derived from the isovists are scalars.  By computing the gradient however,  it is easy to get a vector field. This is useful for many things. For instance, to guide agents in a simulation.

Currently the following measurands are implemented:
Min. distance, max. distance, average distance, min. diameter, max. diameter, min. distance direction, max. distance direction, standard deviation distance, variance distance, skewness distance, dispersion distance, area, perimeter, closed perimeter, open perimeter, openness, min. convex core, compactness, convexity, circularity, centrality, jaggedness, roundness, clustering coefficient, revelation, connectivity. Some of these measurands are shown in the images below.

 

For some related reading:
M. L. Benedikt: To take hold of space: isovists and isovist fields
A. Turner, M. Doxa, D. O’Sullivan, A. Penn: From isovists to visibility graphs: a methodology for the analysis of architectural space
M Batty: Exploring isovist fields: space and shape in architectural and urban morphology.
G. Franz, J. M. Wiener: Exploring isovist-based correlates of spatial behavior and experience