Spatial 3D Analysis of Built-up AreasOren GAL and Yerach DOYTSHER, Israel
1) This paper is written by Oren Gal and Yerach Doytsher and has been successfully peer reviewed for the FIG Working Week May 2012 in Rome, Italy. The paper presents a unique solution to the 3D visibility problem in built-up areas and will be presented in the session TS08H - 3D Principles and Technology. Yerach Doytsher is also chair of FIG Commission 3. Key words: 3D visibility, spatial analysis, efficient algorithms, spatial information management SUMMARYThe paper presents a unique solution to the 3D visibility problem in built-up areas. A 3D visibility algorithm based on an analytic solution for basic building structures is introduced. A building structure is presented as a continuous parameterization approximating of the building’s corners. The algorithm quickly generates the visible surfaces' boundary of a single building. Using simple geometric operations of projections and intersections between visible pyramid volumes, hidden surfaces between buildings are rapidly computed. The algorithm, demonstrated with a schematic structure of an urban built-up environment and compared to the Line of Sight (LOS) method, demonstrates the computation time efficiency. Whereas the common visibility methods (LOS approach) require scanning all the object’s points, the presented solution, by applying the continuous parameterization approximating of the building’s corners, is successfully avoiding the need to handle each point separately. As a result, the performance of the presented solution is much better than the common methods and for the analyzed samples the improvement time ratio was about 1000 times. The basic building structure can be modified to complex urban structures by merging together a number of basic structures. The main contribution of the presented method in this paper is that it does not require special hardware, and is suitable for on-line computations based on the algorithms' performances. The visibility solution is exact, defining a simple problem that can be a basic form of other complicated environments. 1. INTRODUCTIONIn the last few years, the 3D GIS domain has developed rapidly, and has become increasingly accessible to different disciplines. 3D Spatial analysis of Built-up areas seems to be one of the most challenging topics in the communities currently dealing with spatial data. One of the most basic problems in spatial analysis is related to visibility computation in such an environment. Visibility calculation methods aim to identify the parts visible from a single point, or multiple points, of objects in the environment. The visibility problem has been extensively studied over the last twenty years, due to the importance of visibility in GIS and Geomatics, computer graphics and computer vision, and robotics. Accurate visibility computation in 3D environments is a very complicated task demanding a high computational effort, which can hardly been done in a very short time using traditional well-known visibility methods (Chrysanthou, 1996; Plantinga and Dyer, 1990). The exact visibility methods are highly complex, and cannot be used for fast applications due to the long computation time. Previous research in visibility computation has been devoted to open environments using DEM models, representing raster data in 2.5D (Polyhedral model), and do not challenge or suggest solutions for dense built-up areas. Most of these works have focused on approximate visibility computation, enabling fast results using interpolations of visibility values between points, calculating point visibility with the LOS method (Doytsher and Shmutter, 1994; Franklin and Ray, 1994). Other fast algorithms are based on the conservative Potentially Visible Set (PVS) (Durand, 1999). These methods are not always completely accurate, as they may include hidden objects' parts as visible due to various simplifications and heuristics. A vast number of algorithms have been suggested for speeding up the process and reducing the computation time (Nagy, 1994). Franklin (2002) evaluates and approximates visibility for each cell in a DEM model based on greedy algorithms. An application for siting multiple observers on terrain for optimal visibility cover was introduced in (Franklin and Vogt, 2004). Wang et al. (1996) introduced a Grid-based DEM method using viewshed horizon, saving computation time based on relations between surfaces and Line Of Sight (LOS), using a similar concept of Dead-Zones visibility (Cohen-Or and Shaked, 1995). Later on, an extended method for viewshed computation was presented, using reference planes rather than sightlines (Wang et al., 2000). One of the most efficient methods for DEM visibility computation is based on shadow-casting routine. The routine cast shadowed volumes in the DEM, like a light bubble (Ratti, 2005). Other methods related to urban design environment and open space impact treat abstract visibility analysis in urban environments using DEM, focusing on local areas and approximate openness (Fisher-Gewirtzman and Wagner, 2003; Yang et al., 2007). Extensive research treated Digital Terrain Models (DTM) in open terrains, mainly Triangulated Irregular Network (TIN) and Regular Square Grid (RSG) structures. Visibility analysis on terrain was classified into point, line and region visibility, and several algorithms were introduced based on horizon computation describing visibility boundary (De Floriani and Magillo, 1994; De Floriani and Magillo, 1999). Only a few works have treated visibility analysis in urban environments. A mathematical model of an urban scene, calculating probabilistic visibility for a given object from a specific viewcell in the scene, has been presented by (Nadler et al., 1999). This is a very interesting concept, which extends the traditional deterministic visibility concept. Nevertheless, the buildings are modeled as circles, and the main challenges of spatial analysis and building model were not tackled. Other methods were developed, subject to computer graphics and vision fields, dealing with exact visibility in 3D scenes, without considering environmental constraints. Plantinga and Dyer (1990) used the aspect graph – a graph with all the different views of an object. Shadow boundaries computation is a very popular method, studied by (Teller, 1992; Drettakis and Fiume, 1994; Stewart and Ghali, 2000). All of these works are not applicable to a large scene, due to computational complexity. As mentioned, online visibility analysis is a very complicated task. Recently, off-line visibility analysis, based on preprocessing, was introduced. Cohen-Or et al. (1998) used a ray-shooting sample to identify occluded parts. Schaufler et al. (2000) use blocker extensions to handle occlusion. In this paper, we introduce a new fast and exact solution to the 3D visibility problem from a viewpoint in urban environment, which does not suffer from approximations. We consider a 3D urban environment building modeled as a cube (3D box) and present analytic solution to the visibility problem. The algorithm computes the exact visible and hidden parts from a viewpoint in urban environment, using an analytic solution, without the expensive computational process of scanning all objects' points. The algorithm is demonstrated by a schematic structure of an urban environment, which can also be modified for other complicated urban environments, with simple topological geometric operators. In such cases, computation time grows linearly. Our method uses simple geometric relations between the objects and the lines connecting the viewpoint and the objects' boundaries by extending the visibility boundary calculation from 2D to a 3D environment by using approximated singular points (Elber et al., 2005). The spatial relationship between the different objects is computed by using fast visible pyramid volumes from the viewpoint, projected to the occluded buildings. The current research tackles the basic case of a single viewpoint in an urban environment, which consists of buildings that are modeled as cubes. More complex urban environments can be defined as a union between the basic structures of several cubes. Further research will focus on modeling more complex urban environments, and facing multiple viewpoints for optimal visibility computation in such environments. 2. PROBLEM STATEMENTWe consider the basic visibility problem in a 3D urban environment, consisting of 3D buildings modeled as 3D cubic parameterization
Computes:
This problem seems to be solved by conventional geometric methods, but as mentioned before, it demands a long computation time. We introduce a fast and efficient computation solution for a schematic structure of an urban environment that demonstrates our method. 3. ANALYTIC VISIBILITY COMPUTATION3.1 Analytic Solution for a Single Object In this section, we first introduce the visibility solution from a single point to a single 3D object. This solution is based on an analytic expression, which significantly improves time computation by generating the visibility boundary of the object without the need to scan the entire object’s points. Our analytic solution for a 3D building model is an extension of the visibility chart in 2D introduced by Elber et al. (2005) for continuous curves. For such a curve, the silhouette points, i.e. the visibility boundary of the object, can be seen in Figure 1:
The visibility chart solution was originally developed for dealing with the Art Gallery Problem for infinite viewpoint; it is limited to 2D continuous curves using multivariate solver (Elber et al., 2005), and cannot be used for on-line application in a 3D environment. Based on this concept, we define the visibility problem in a 3D environment for more complex objects as:
where 3D model parameterization is
A three-dimensional urban environment consists mainly of rectangular buildings, which can hardly be modeled as continuous curves. Moreover, an analytic solution for a single 3D model becomes more complicated due to the higher dimension of the problem, and is not always possible. Object parameterization is therefore a critical issue, allowing us to find an analytic solution and, using that, to generate the visibility boundary very fast. 3.1.1 3D Building Model Most of the common 3D City Models are based on object-oriented topologies, such as 3D Formal Data Structure (3D FDS), Simplified Spatial Model (SSS) and Urban Data Model (UDM) (Zlatanova et al., 2002). These models are very efficient for web-oriented applications. However, the fact that a building consists of several different basic features makes it almost impossible to generate analytic representation. Modeling a 3D urban environment can be done by dividing and simplifying the environment using a set of grammar rules consisting of basic shape vocabulary of mass modeling (Stiny, 1982; Wonka et al., 2003; Duarte., 2002). By that, one can simply create and analyze 3D complex urban environments by using computerized algorithms. A three-dimensional building model should be, on the one hand, simple enabling analytic solution, and on the other hand, as accurate as possible. We examined several building object parameterizations, and the preferred candidate was an extended n order sphere coordinates parameterization, even though such a model is a very complex, and will necessitate a special analytic solution. We introduce a model that can be used for analytic solution of the
current problem. The basic building model can be described as: This mathematical model approximates building corners, not as singular points, but as continuous curves. This building model is described by equation (2), with the lower order badly approximating the building corners, as depicted in Figure 2. Corner approximation becomes more accurate using n = 350 or higher. This approximation enables us to define an analytic solution to the problem.
We introduce the basic building structure that can be rotated and extracted using simple matrix operators (Figure 3). Using a rotation matrix does not affect our visibility algorithm, and for simple demonstration of our method we present samples of parallel buildings. 3.1.2 Analytic Solution for a Single Building In this part we demonstrate the analytic solution for a single 3D building model. As mentioned above, we should integrate building model parameterization to the visibility statement. After integrating eq. (1) and(2):
where the visibility boundary is the solution for these coupled equations. As can be noticed, these equations are not related to Z axis, and the visibility boundary points are the same ones for each x-y surface due to the model's characteristics. Later on, we treat the relations between a building's roof and visibility height in our visibility algorithm, as part of the visibility computation. The visibility statement leads to two polynomial order equations, which appear to be a complex computational task. The real roots of these polynomial equations are the solution to the visibility boundary. These equations can be solved efficiently by finding where the polynomial equation changes its sign and cross zero value; generating the real roots in a very short time computation (these functions are available in Matlab, Maple and other mathematical programs languages). Based on the polynomial cross zero solution, we can compute a fast and exact analytic solution for the visibility problem from a viewpoint to a 3D building model. This solution allows us to easily define the Visible Boundary Points. Visible Boundary Points (VBP) - we define VBP of the object as
a set of boundary points
Roof Visibility – The analytic solution in equation (3) does
not treat the roof visibility of a building. We simply check if
viewpoint height
Two simple cases using the analytic solution from a visibility point to a building can be seen in Figure 4. The visibility point is marked in black, the visible parts colored in green, and the invisible parts colored in purple. The visible volumes are computed immediately with very low computation effort, without scanning all the model’s points, as is necessary in LOS-based methods for such a case. 3.2 Visibility Computation in Urban Environments In the previous sections, we treated a single building case, without considering hidden surfaces between buildings, i.e. building surface occluded by other buildings, which directly affect the visibility volumes solution. In this section, we introduce our concept for dealing with these spatial relations between buildings, based on our ability to rapidly compute visibility volume for a single building generating VBP set. Hidden surfaces between buildings are simply computed based on intersections of the visible volumes for each object. The visible volumes are defined easily using VBP, and are defined, in our case, as Visible Pyramids. The invisible components of the far building are computed by intersecting the projection of the closer buildings' VP base to the far building's VP base as described in 3.2.2. 3.2.1 The Visible Pyramid (VP) Visible Pyramid (VP) - we define
The intersection of VPs allows us to efficiently compute the hidden surfaces in urban environments, as can be seen in the next sub-section. 3.2.2 Hidden Surfaces between Buildings As we mentioned earlier, invisible parts of the far buildings are
computed by intersecting the projection of the closer buildings' VP to
the far buildings' VP base. For simplicity, we demonstrate the method
with two buildings from a viewpoint
As can be seen in Figure 6, in this case, we first compute VBP for
each building separately,
In the case of a third building, in addition to the buildings introduced in Figure 7 (b), the projected VP will only be the visible ones, and the VBP and VP of the second building will be updated accordingly (as is described in the next sub-section - stage 2.3.4.3) . We demonstrated a simple case of an occluded building. A general algorithm for more a complex scenario, which contains the same actions between all the combinations of VP between the objects, is detailed in section 3.3. Projection and intersection of 3D pyramids can be done with simple computational geometry elements, which demand a very low computation effort.
3.4 Visibility Algorithm – Complexity Analysis We analyze our algorithm complexity based on the pseudo code
presented in the previous section, where represents the number of
buildings. In the worst case, n buildings hide each other.
Visibility complexity consists of generating VBP and VP for n
buildings,
We analyze the visibility algorithm complexity of the LOS methods,
where n represents the number of buildings and k
represents the resolution of the object. The exact visibility
computation requires scanning each object and each object’s points,
4. RESULTSWe have implemented the presented algorithm and tested some urban environments on a 1.8GHz Intel Core CPU with Matlab. From the different tested scenes, only two are shown below. First, we analyzed the versatility of our algorithm on these scenes with different occluded elements. After that, we compared our algorithm to the basic LOS visibility computation, to prove accuracy and computational efficiency. 4.1 Test Scenes
4.2 Computation Time and Comparison to LOS The main contribution of this research focuses on a fast and accurate visibility computation in urban environments. We compare our algorithm time computation with common LOS visibility computation demonstrating algorithm's computational efficiency. 4.2.1 Visibility Computation Using LOS The common LOS visibility methods require scanning all objects'
points. For each point, we check if there is a line connecting the
viewpoint to that point which does not cross other objects. We used LOS2
Matlab function, which computes the mutual visibility between two points
on a Digital Elevation Model (DEM). We converted our second test scene
with one to twelve buildings to a DEM, operated LOS2 function, and
measured the CPU time for the visibility computation. Each building
within the DEM was modeled homogenously by 50 points. The visible parts
using the LOS method were the exact parts computed by our algorithm.
Obviously, the total computation time of LOS method was more than 1000
times longer than our analytic solution (3160 seconds vs. 2.9 seconds).
Running times of our analytic solution and the LOS method are depicted
in Figure 10.
5. CONCLUSIONS AND FUTURE WORKWe have presented an efficient algorithm for visibility computation in a built-up environment where the built-up environments are represented by basic structures. The basic structure is modelled with a mathematical approximating of the buildings’ corners. Our algorithm is based on a fast visibility boundary computation for a single building, and on computing the hidden surfaces between buildings by using projected surfaces and intersections of the visible pyramids. One of the most important issues of visibility computation relates to the computational complexity. Complexity analysis of our algorithm has been presented, as well as a comparison of running times between our algorithm and the LOS visibility solution, showing a significant improvement of time performance. The significant improvement in running time of our algorithm (vs. the LOS method) - shows that its performances are suitable for on-line and close to real-time applications. The main contribution of the presented method in the paper is an exact mathematical solution for the challenging visibility problem without the need to use any special hardware. The solution which is based on defining a basic form of urban structures can be applied to other complicated environments. Further research will focus on modelling more complex urban environments and facing multi viewpoints for optimal visibility computation in such environments, generalizing the presented building model for more complex ones. REFERENCES
BIOGRAPHICAL NOTESOren Gal received his B.Sc. in Aerospace Engineering, from the Technion - Israel Institute of Technology in 2004. At 2009 he received his M.Sc. in Mechanical Engineering also from the Technion. He is currently PhD candidate in Mapping and Geo-information Engineering at the Technion. His research interests include spatial analysis of 3D environments, motion planning in dynamic environments, and Multi-Agents. Oren's PhD research is entitled "Visibility Analysis in 3D for Multi-Agent Trajectory Planning". Prof. Yerach Doytsher graduated from the Technion – Israel Institute of Technology in Civil Engineering in 1967. He received a M.Sc. (1972) and D.Sc. (1979) in Geodetic Engineering also from Technion. Until 1995 he was involved in geodetic and mapping projects and consultations within the private and public sectors in Israel and abroad. Since 1996 he is a faculty staff member in Civil Engineering and Environmental at the Technion, and heads the Geodesy and Mapping Research Center at the Technion. He is the Chair of FIG Commission 3 on Spatial Information Management for the term 2011-2014, and is the President of the Association of Licensed Surveyors in Israel. CONTACTSOren Gal Prof. Yerach Doytsher
|
(1) 
, and the
viewpoint is given as
using
cross-product characters. 
(2) 
(3) 
of the visible
surfaces of the object, from viewpoint
(4) 
is
lower or higher than the building height
and use this to
decide if the roof is visible or not:
(5)
of the object
as a 3D pyramid generated by connecting VBP of specific surface j
to a viewpoint 
for a single object is three. VP boundary, colored with red arrows, can
be seen in Figure 5. 
one (denoted as
the first one) of which hides, fully or partially, the other (the second
one). 
; based on these
VBPs, we generate VPs for each building,
. After that, we
project 
base to
base plane, as
seen in Figure 7 (a), if existing. At this point, we intersect the
projected surface in
and
hidden by the first building, which is marked in black in Figure 7 (b).
complexity.
Projection and intersection are also
where usually
.
, and, above all, the solution is an approximate one.
