Well, it’s been a long time since my last blog post. Free-time is rare and (un)fortunately there is a rather long list of unfinished projects I could and probably should continue working on. One of these projects and a topic that has generally interested me a lot for many years is the large field of visibility-based analysis. A few years ago I wrote a short blog-post about it here. Since I’ve been working on it again in the last few months and have rewritten most of the old implementation, I thought it might be a good time for an update.
On a conceptual level, visibility-based analysis methods are quite fascinating, as the relationship between visuospatial properties and psychological responses and behavior is one of the most important considerations in how people interact with and in their (built) environment. On the computational and algorithmic level, it is quite a challenge to make it accurate, fast, and memory efficient at the same time, especially for a three-dimensional environment. This starts with the generation of an accurate representation of visible space (in other words, a two- or three-dimensional polygon/polyhedron) and ends with the computation of various geometric and topological measures based on those structures. The general principle of spatial analysis is not hard to understand, but getting deeper into the concepts does take some time. This is especially true for the various quantitative measures and their meaning. A great deal of research has been done in the last forty years, a considerable amount of which has come from the fields of psychology and philosophy.
Visibility-based spatial analysis is a way to investigate and understand the relationships between (visible) spatial properties, (human) experience, emotional associations, and behavior. From a conceptual and computational perspective, there are currently two main approaches. The first approach is called isovist analysis and is mainly concerned with geometry, the second is based on the mutual visibility of points and is summarized under the term visibility graph analysis (VGA). While isovists deploy geometric-spatial information for a particular position in space, VGA unfolds the topological relationship of different positions in space to each other.
In order to explore space to its full extent, it is imperative to complement the typical two-dimensional analysis with a three-dimensional method. For that reason, three different approaches have been implemented: a (1) geometry-based, a (2) topology-based, and an (3) image-based method (which will be the topic of another blog post …).
At its core, any visibility analysis application has to meet several requirements: (1) fast ray-casting for (inter)visibility computation, (2) geometry and/or graph generation, (3) data analysis and manipulation, and finally (4) data visualization. Since Houdini is more than capable in all these areas, it was the logical choice for the software framework on which I developed and implemented such a tool. Many of the algorithms have been written either in VEX or, to take advantage of today’s GPU processing power, in OpenCL. To keep the entire toolset as flexible and accessible as possible, only a few algorithms are written in C++ using the HDK. All in all, it’s about 67.500 lines of custom code and 1683 nodes.
Without going into detail, here are some basic examples of what it can do:
- Generate axial lines (all axial lines and fewest axial lines)
- Generate spatial partitions (s-partition and e-partition)
- Compute a sufficient set of points and isovists (based on a fast iterative algorithm to approximate the famous art gallery problem)
- Generate movement patterns (based on various spatial measures)
- Two- and three-dimensional isovist an visibility graph generation
- 360° spherical panorama image generation to supplement three-dimensional isovist analysis
Top left: all axial lines and fewest axial lines; Top middle: s- and p-partition; Top right: sufficient set of points and isovist polygons; Bottom left: movement pattern; Bottom middle: 2D/3D isovist (bottom: tri-planar and contour 2.5 D isovist); Bottom right: 360° spherical panorama images (lighting, depth)
For the generation of two- and three-dimensional isovists, I’m using two different methods. (1) One method is based on simply sending rays from the “viewpoint” radially into the scene. This works quite robustly (no problems with overlapping and/or intersecting polygons) and is very fast, since ray casting is implemented to work on the gpu. However, the resulting isovist is always an approximation but not an accurate representation of visible space. This becomes even more apparent for areas farther away. Because rays are distributed evenly over a circle/sphere around the viewpoint, distant areas of the environment are captured in less and less detail. (2) The second method circumvents this problem by computing an accurate isovist. To do this, a sweep-line algorithm is used which relies on the connectivity structure of the mesh. The resulting polygon/polyhedron consists of vertices and edges only at the exact intersections with the 3D environment and is therefore an exact two/three-dimensional representation of visible space around a particular viewpoint. In the image below, you can see the area difference between exact isovists (sweep-line algorithm) and isovists created by simply radially sampling the scene (radial ray-casting algorithm).
Left: radial ray casting – 180 rays, area difference of max. 29.6 m²; Middle: radial ray casting – 360 rays, area difference of max. 12.6 m²; Right: radial ray casting – 720 rays, area difference of max. 7.3 m² (Well, instead of using absolute values, I should have expressed the difference in percentages, so that it actually would make sense …)
Top left: isovist based on radial ray casting; Top right: isovist based on radial sweep line algorithm; Bottom left: 360° isovist (left: radial ray casting, right: radial sweep line); Bottom right: partial isovist.
Three-dimensional isovists are generated in basically the same way as two-dimensional isovists, again as an approximation (radially casting rays) or by calculating geometry intersections for an accurate isovist representation of visible space.
Visibility Graph Generation
Conceptually and computationally, there is no difference between a two-dimensional and a three-dimensional visibility graph. In any case, it’s based on the mutual visibility of points. Thus, the whole space is usually divided into smaller same-sized parts. In other words, the sample points are evenly distributed in a grid-like structure over the entire domain (surface/volume). However, we can also specify a second set of points. Thus, it’s possible to use a very dense, high-resolution pointset as “viewpoints”, but to use considerably less points as “target points” for checking indivisibilities and constructing the graph. To get meaningful results for the analysis, the varying density is then compensated by a multiplication factor based on the spatial area/volume around each sample point.
Top left: accurate isovist; Top middle: approximated isovist; Top right: visible points (voxels) from a particular viewpoint; Amount of visible space (volume) visualized as points (bottom left) and as isosurfaces (bottom middle); Bottom right: Amount of visible space (volume) from sample points (viewpoints) at 1.7 m above floor level.
Currently, about 100 different local and global isovist and visibility graph measures can be calculated. These include many well know measures as proposed by various authors in the space syntax literature, such as area, circularity, drift, clustering coefficient, visual integration, etc., as well as less common measures such as revelation, angular correlation, fractal dimension, local symmetry, and so on. Each can be based on first and/or second order visibility relations and most work in both, two- and three-dimensional domains. In addition to already existing spatial descriptors, several new ones have been implemented. Some of them are shown below.
Similarity: Based on the visible neighbourhood of 0.5 m (left), 2.0 m (center) and the entire visible neighbourhood (right) per sample point.
Boundary Similarity: Based on solid and occluding edges. Similarty between continuous (middle) and single edges (right).
Local Symmetry: Degree of experienced symmetry from the ego-centric view (left). Sreamlines along the local (middle) and semi-global (right) symmetry vector.
Predictability: Based on the visible neighbourhood of 2.0 m (left) and the entire visible neighbourhood (right) per sample point.
Deflection: Local (left) and global (right) deflection
Conceptual and Methodological Framework
Although isovists and visibility graphs are both used for spatial analysis, they are fundamentally different from a conceptual and mathematical point of view, as mentioned earlier. Summarized the main differences are (isovist left, visibility graph right):
- Geometric representation of space
- Represents the shape of space
- Observer-centric and therefore (typically) local description of space
- Conceptually a continuous approach
- There is a strong relationship between the isovist geometry and psychological and emotional response
- Topological representation of space
- Represents the space in terms of spatial relations
- Typically global description of space
- Conceptually a discrete approach
- Conceptually, there are similarities to models of spatial memory from cognitive science
On a conceptual level, the general implementation largely follows Sophia Psarra and Sam McElhinney’s proposal to discard the distinction between isovists and visibility graphs, and instead reinterpret a combination of both concepts as a “relational framework” of geometric entities. In this context, the term “relational” refers not so much to the mutual visibility of points in the graph, but rather to how isovists relate to each other in terms of overlapping areas. To prioritize a purely geometric approach as much as possible, overlapping regions are therefore described by “sub-isovists” rather than by topological information based on the intervisibility of points. Conceptually, this method pursues a continuous approach and is thus independent from the number and distribution of sample points. Topology-based computations are thus largely replaced, not least to stay consistent with the conceptual and theoretical basis on which the implementation is built. Apart from this, it is quite satisfying to watch the isovists and subisovists changing continuously when moving from one position to another (animation below).
First and second order visibility relations between points and isovists.
Of course, this is not the only tool for visibility-based spatial analysis. The best known applications are most probably depthmapX by Tasos Varoudis and the Isovist app by Sam McElhinney. Both applications have been very helpful for comparing and cross-checking many analyses results. So, big thanks to Tasos and Sam for making both tools freely available. Following their example, I will make my tool available as well, as soon as I’ve cleaned up the coding-mess a bit.
Although all these methods originate mainly from architecture and urban planning research, they are also quite interesting for space planning in the generation of game environments. For example, they could be used to generate and/or optimize a spatial structure in terms of its spatial intelligibility from the egocentric perspective of a player. Take, for example, a maze. It could be generated to be highly differentiated and surprising at the local level (visible space from a particular point), but clearly structured and memorable at the global level (the overall structur of it). Or it could be the opposite.
For some related reading:
Turner A, Penn A (1999) Making isovists syntactic: Isovist integration analysis: Proceedings of the 2nd International Symposium on Space Syntax, vol. 3
Turner A (2001) Depthmap: A program to perform visibility graph analysis: 3rd International Symposium on Space Syntax, Georgia Institute of Technology
Benedikt ML (1979) To Take Hold of Space: Isovists and Isovist Fields. Environment and Planning B 6:47–65
S. Psarra, S. McElhinney (2014) Just around the corner from where you are: Probabilistic isovist fields, inference and embodied projection. The Journal of Space Syntax, vol 5
G. Franz, H.A. Mallot, J.M. Wiener (2005) Graph-based models of space in architecture and cognitive science – A comparative analysis
D. R. Montello (2007) THE CONTRIBUTION OF SPACE SYNTAX TO A COMPREHENSIVE THEORY OF ENVIRONMENTAL PSYCHOLOGY
Dalton N Synergy, inteligibility and revelation in neighbourhood places. Doctoral thesis, UCL (University College London)
Krukar J, Manivannan C, Bhatt M et al. (2021) Embodied 3D isovists: A method to model the visual perception of space. Environment and Planning B: Urban Analytics and City Science 48:2307–2325
Bhatia S, Chalup SK, Ostwald MJ (2013) Wayfinding: a method for the empirical evaluation of structural saliency using 3D Isovists. Architectural Science Review 56:220–231
One thought on “VISIBILITY-BASED ANALYSIS”
Glad to see you back in action! Even if i will very probably start to cry again when opening every of your post, thanks 🙂