Semiautomatic detection of floor topology from CAD architectural drawings

Semiautomatic detection of floor topology from CAD architectural drawings B. Dom´ıngueza,∗,´ A.L. Garc´ıaa, F.R. Feitoa aDepartamento de Inform´atica, Universidad de Ja´en - Campus de Las Lagunillas s/n. - 23071 Ja´en (SPAIN) Abstract A method for the semiautomatic detection of the topology of building floors represented as CAD drawings stored in vector file format is presented in this paper. This method involves the detection of walls and joint points amid walls and openings, and the search of intersection points amid walls. To give support to the wall detection process, this paper introduces the wall adjacency graph (WAG), a data structure created to detect walls from sets of planar segments contained in architectural floor plans. Wall adjacency graphs allow us to obtain a consistent and exhaustive set of walls very quickly (less than one second for real floor plans). A generalized version of the wall adjacency graph is also presented to deal with some of the limitations of the initial WAG. Algorithms for the detection of joint points and wall intersection points are presented as well, based on the analysis of the geometry from the input CAD drawings. Moreover, all this process works appropriately with both straight and circular segments. The obtained floor topology can later be used as input to generate 3D models of buildings, which are widely used on virtual cities, BIM systems and GIS. Keywords: Building Information Models, CAD drawings, Computational Geometry, Graph Theory 1. Introduction There is little doubt about the evolution of the way humans interact with computers. Year after year, new advances in hardware and software are leading us to new and amazing sensory experiences in which virtual environments are combined with other kinds of data in order to fulfill all the informational needs of the users. Moreover, the computer performance/price ratio is continuously growing, and nowadays the users can afford computers able to handle most of these features easily. ∗Corresponding author Email addresses: [email protected] (B. Dom´ınguez), [email protected] (´ A.L. Garc´ıa), [email protected] (F.R. Feito) Preprint submitted to Computer-Aided Design June 15, 2016 The popularity of navigation through virtual 3D environments is rapidly growing, thanks to applications and development platforms like Google Earth c or Microsoft Virtual Earth c , which allow users to not only explore aerial and satellite photographs all over the world, but also examine three-dimensional reconstructions of buildings and monuments (when available). While most of these tools are intended for outdoor navigation, there also exist websites which offer interactive indoor 3D navigation in order to let the users enjoy virtual tours through the facilities of a company, a museum, a university, etcetera. These interactive virtual tours usually rely on a third party plugin, and use VRML, X3D [1], COLLADA [2], and other technologies related to Web3D [3] to describe the geometry and appearance of the scenes as well as the behaviour of their elements. Architectural 3D indoor scenes are typically developed from scratch, or commercial applications like Autodesk c 3ds Max c are used to perform some kind of 2D-to-3D conversion using the floorplan of the scene as input, but this process is not straightforward, and the user must modify the preliminary result in order to obtain the final geometry. It is therefore desirable to have automatic tools which can take a 2D floorplan as input, and generate a 3D model in a format general enough to be used for different purposes. As a first step of this automatic process, this paper is focused on extracting topological information from 2D vector floor plans composed of low-level geometric primitives. This aim implies the development of algorithms to analyze geometry and obtain semantic features that can be used on Building Information Model (BIM) systems, GIS and city models [4, 5, 6, 7]. The rest of the paper is structured as follows: first, some previous works are summarized in section 2. Sections 3 to 7 explain the wall detection process using wall adjacency graphs (WAG’s). Section 8 describes the detection of joint points amid walls and openings and the search of intersection points amid walls. Finally, sections 9 and 10 present the results, conclusions and future work. 2. Previous work There are several studies related to the processing of architectural floor plans. They can be grouped according to the kind of input and the goals of the process: •Some interesting works introduce methods to recognize special symbols from a floor plan. These methods typically apply Computer Vision and Pattern Recognition techniques on scanned floor plans to obtain their results. Ah-Soon and Tombre [8] use networks of constraints on geometrical features to find symbols that represent doors and windows, defining a formal grammar to describe what have to be recognized. On the other hand, Dosch et al. [9] describe a complete system for symbol recognition involving Computer Vision tools such as segmentation, vectorization and feature detection; the result is used to create a 3D reconstruction of the floor (without topology information) by means of extruding the recognized 2D geometry. Other interesting works include the one from Llad´os et al. [10], who apply the Hough transform to recognize symbols from hand-drawn architectural floor plans, and the one from Lu et al. [11], who deal with the recognition of structural objects and the classification of wall shapes. •CAD vector drawings are the input data considered by other researchers that propose methods to generate 3D building models. These include the work from Horna 2 et al. [12], who define the generalized-maps to represent adjacency relations amid geometric elements, and use them to extract 2D topology and 3D volumes from a floor plan, given some assumptions on the quality of the floor plan and some considerations about the structure of a building that allow them to define constraints on the geometry; occasionally, the user intervention can be necessary to provide semantic associations to the geometry, and curved walls are considered as polylines. As far as we know, no further advances on this approach have been published up to now. Other works are the one by Mas and Besuievsky [13], based on the extrusion of planar polygons from CAD vector drawings to generate 3D building models used for light simulation, and the one by Paoluzzi et al. [14], who use 3D reconstruction for security modelling of critical infrastructures. •A third group of works introduce methods to retrieve topological information from CAD vector drawings, like the one from Medjdoub and Yannou [15], who use graphs to store adjacency relations amid floors, rooms and stairs during the design stage. Other related work is the one from Zhi et al. [16], who build a topology graph to describe the distribution of walls and openings in a floor plan, and search for a set of fundamental loops to find corridors and rooms, so that an evacuation plan can be created from that information; this work emphasizes the loop search, but gives very few details on the graph building process. 3. Problem overview The problem we face here is the extraction of topological information from a building floor plan. Typically, building designs are stored as vector drawings created with CAD software applications and composed of low level graphical primitives, like lines, polylines, circular arcs, etcetera. Optionally, blocks can be created as combinations of primitives and/or other blocks; this allow the user to easily create and instantiate representations for common elements like doors, windows or furniture. Moreover, CAD applications allow the designer to split the graphical information in layers to group related elements together, and whose visibility can be switched on or off in order to emphasize what is really important in every situation. In order to get the topology from a floor plan, it is necessary to obtain the information about the walls and openings it contains. Although there exist several standards on how the layers should be organized in architectural design [17, 18, 19], CAD applications do not force the users to follow any of these standards, and therefore it is possible to find CAD drawings where the information regarding walls and openings is mixed with other data or divided into several layers. The second situation is easily solved by mixing the contents of the layers that keep the desired information, whereas the first situation is still an open problem, because typically there is no additional data (apart from line attributes like color or thickness) to support automatic extraction of primitives from the layers without involving the user. Here we consider that the walls are stored in one or several layers, but mixed with nothing else than (optionally) the openings, and that the openings are represented by blocks. One additional problem that appears sometimes when processing CAD vector drawings is related with precision: overlapping segments or duplicated vertices can appear if the user is not careful enough when creating the floor plan. These situations have to be 3 detected and corrected by checking all the geometry and merging faulty vertices and segments, and may require the user intervention to set a precision threshold. To be precise, the following tasks have been implemented successfully in our test aplication [20]: segments with zero length are removed from the floor plan, partially overlapping segments are replaced by a unique segment obtained by merging them, and in those cases where there are two copies of the same segment, one of them is removed. Occasionally, these changes may produce new precision related problems; therefore, the process of checking and correcting these situations has to loop automatically over the geometry until there are no more changes to be applied. Every wall in a vector drawing of a floor plan is represented by two parallel line segments, but the mapping between pairs of segments and walls is not bijective, i.e. two consecutive walls may share one segment (see Figure 1). Figure 1: The mapping between pairs of segments and walls is not bijective, e.g. the walls ab and ac share the segment a. Furthermore, there is no information about which segments match to make up a wall. Therefore, the wall detection process involves searching for wall-prone pairs of segments using a threshold ε(maximum wall thickness), and split them in order to obtain wall pairs. The following definitions clarify these concepts: Definition 1 (Wall-prone pair of line segments). Let aand bbe line segments in R2. Let rand sbe the lines containing aand brespectively, and a′and b′the projections of aand bonto sand r. Given a fixed threshold ε, the pair (a, b)is wall-prone (represented by the predicate prone(a, b, ε)) if and only if all these conditions are held: C1. aand bare parallel: akb C2. a′and b(and therefore b′and a) overlap: a′∩b6=∅ C3. The distance between rand sis less than or equal to the threshold: d(r, s)≤ε Note: In this work line segments are considered open (their end points do not belong to them), to avoid the special case where two line segments with consecutive projections hold condition C2. Definition 2 (Wall pair of line segments). Two line segments aand bare said to form a wall pair, given a fixed threshold ε(represented by the predicate wall(a, b, ε)), if they hold the conditions to be a wall-prone pair, and their projections onto the line that contain each other match. Therefore, a new, more restrictive condition is added to C1,C2 and C3: C4. a′and b(and therefore b′and a) are the same: a′=b 4 Some properties of these predicates are inmediate: •prone does not depend on the segment order: prone(a, b, ε)⇔prone(b, a, ε) •wall does not depend on the segment order: wall(a, b, ε)⇔wall(b, a, ε) •wall is a restriction of prone:wall(a, b, ε)⇒prone(a, b, ε) Given the above definitions, this is the outline of the algorithm to compute the walls represented by a set of segments in a floor plan (see example in Figure 2): Figure 2: Iteration of the algorithm. (1) Initial set of segments and relations. (2) Projection of the end points. (3) Segment splitting and wall extraction. (4) Updated segments and relations (1) Find all the wall-prone pairs. In Figure 2.1, these pairs are (a, c), (a, d) and (b, d). (2) For each wall-prone pair, apply the following steps (in this example, we take the pair (a, d)): (2.a) Compute the projections of the end points of one segment on the other segment. Applying this step to the wall-prone pair (a, d) results in points 1 and 2, as shown in Figure 2.2. (2.b) Split each segment using the computed projections and check the new set of segments for wall pairs: some segments will form wall pairs while the rest will become single (their projections do not overlap). In Figure 2.3, the resulting segments are a1,a2,d1and d2. The new detected wall pair is (a2, d1), and the single segments are a1and d2. (2.c) Update the set of segments by removing the old segments (aand din this case) and adding the single ones (a1and d2). Then, update the wall-prone pair set; in this example, wall-prone pairs (a1, c) and (b, d2) are added, as shown in Figure 2.4. In order to make the processing of wall and wall-prone relations amid segments easier, and keep record of the hierarchical relations between each line segment and the pieces it is split into, the Wall Adjacency Graph is proposed as a data structure to give support to this process. The following sections give a detailed description of this structure and its application to the problem. 5 4. The Wall Adjacency Graph The Wall Adjacency Graph (WAG) is a graph whose nodes represent the line segments from a floor plan that are involved in the representation of walls, and whose edges represent relations between those segments. In order to represent the walls drawn in a floor plan, three kind of relations between segments are defined as follows: Definition 3 (Wall-prone relation). Given a finite set of line segments Aand a fixed threshold ε, the wall-prone relation over Ais defined as the set P R(A, ε) = {(a, b)∈ A × A | prone(a, b, ε)} Definition 4 (Wall relation). Given a finite set of line segments Aand a fixed threshold ε, the wall relation over Ais defined as the set W(A, ε) = {(a, b)∈ A × A | wall(a, b, ε)} As the relations defined above are based on Definitions 1 and 2, the following properties hold: •P R(A, ε) is symmetric: (a, b)∈P R(A, ε)⇔(b, a)∈P R(A, ε) •W(A, ε) is symmetric: (a, b)∈W(A, ε)⇔(b, a)∈W(A, ε) •W(A, ε)⊆P R(A, ε) As the wall-prone pairs are being processed, their segments are split into pieces. For each segment a, the set of pieces it is split into form a partition P(a) of that segment, because they do not overlap. In order to store in the Wall Adjacency Graph the information about partitions, one more relation is defined as follows: Definition 5 (Hierarchical relation). Given a finite set of line segments A, the hierarchical relation over Ais defined as the set H(A) = {(a, b)∈ A × A | b∈P(a)} Unlike the wall and wall-prone relations, the hierarchical relation is obviously not symmetric. Once all the elements that are involved in the Wall Adjacency Graph are defined, a formal definition of this structure follows: Definition 6 (Wall Adjacency Graph). Given a finite set of line segments Aand a fixed threshold ε, the Wall Adjacency Graph (WAG) associated with Ais a graph G(A, ε) = (A, P R(A, ε)∪H(A)). For a given floor plan, its WAG is therefore formed by the line segments it contains, together with the relations amid them. A WAG is not necessarily connected, and this is not a requirement for the algorithms to work successfully. Due to the fact that W(A, ε)⊆P R(A, ε), it is necessary to distinguish the set of strict wall-prone segment pairs that do need to be processed to get wall pairs; therefore, 6 the set W(A, ε) is defined as the complement of W(A, ε) with respect to P R(A, ε), i.e. W=P R(A, ε)\W(A, ε). From now on, WAG edges representing wall and wall-prone relations will be notated (when necessary) as unordered pairs {a, b}, as these relations are symmetric; similarly, WAG edges representing hierarchical relations will be notated as ordered pairs (a, b). Example 1 (Initial WAG). Figure 3 shows an example of (a) an initial set of line segments and (b) its associated WAG. Edges representing wall-prone relations are drawn with single lines, while edges representing wall relations appear as double lines. The elements defining the WAG are: A={a1, a2, a3, a4, a5} P R(A, ε) = {{a1, a4},{a2, a4},{a3, a5}} H(A) = ∅ The pairs in P R(A, ε)can be grouped into wall and wall-prone sets: W(A, ε) = {{a3, a5}} W(A, ε) = {{a1, a4},{a2, a4}} a1a2a3 a4a5 (a) (b) ε a4a2 a1a3a5 Figure 3: Example of (a) a set of line segments (b) its associated WAG using a threshold ε. Single lines represent wall-prone relations, while double lines represent wall relations. 5. Wall detection algorithm In section 3, an outline of the wall detection algorithm was described. Now that description will be revised, including the WAG as underlying data structure for this algorithm. The input of this process is the set of line segments that represent the walls in a vector drawing of a floor plan. As mentioned in section 3, these segments are considered as the unique contents of one layer of the drawing, or alternatively, the unique result of the mixture of several ones. Given this set, it is possible to estimate automatically the value for the threshold εas described in [21], or the user can be required to fix this value, as it is essential for the rest of the process. As a preliminary step, it is necessary to build the initial WAG for the segments. Its elements (A,P R(A, ε) and H(A) ) are assigned as follows: • A is defined as the initial set of segments. 7 •H(A) is empty. •To build the initial set of wall-prone relations P R(A, ε), each possible pair of line segments (a, b) has to be analyzed to determine whether it holds the conditions to be a wall or a wall-prone pair. For the convenience of the wall detection algorithm, this set is subdivided into the subsets W(A, ε) and W(A, ε), defined in section 4. Once the WAG has been created, the wall-prone pairs from the subset W(A, ε) are processed in turn to obtain wall pairs. There are nine possible types of wall-prone pairs; the way they are processed will be detailed later. The processing of each wall-prone pair results in a series of changes in the WAG: •As described in section 3, it could be necessary to divide the segments from the pair and use their pieces to build new wall and wall-prone pairs; new nodes would therefore be added to the WAG to represent these pieces. The set of added nodes will be notated as A+. •Including new nodes in the WAG implies changing graph edges to represent the new wall and wall-prone pairs that are created. This results in the deletion of some wall-prone edges and the addition of new ones. The sets P R−and P R+represent these edges. Moreover, a wall-prone pair is always deleted to produce a wall pair, and therefore a wall edge whas also to be added to the WAG. •In order to keep track of the origin of each node, edges representing the hierarchical relation between the nodes corresponding to the segments that are split and the nodes representing the pieces they are split into are added to the graph. The set H+represents these edges. At the end of the process, there only exist wall pairs in the structure, therefore P R(A, ε)≡W(A, ε). Algorithm 1 formally describes the wall detection procedure using the WAG as supporting data structure. Algorithm 1 Wall detection algorithm Input: A, ε Build W(A, ε) = {{a, b} | a, b ∈ A ∧ prone(a, b, ε)∧ ¬wall(a, b, ε)} Build W(A, ε) = {{a, b} | a, b ∈ A ∧ wall(a, b, ε)} Build H(A) = ∅ for all {a, b} ∈ W(A, ε)do Study the layout of aand b Build A+,P R−,P R+,wand H+depending on aand b A ← A ∪ A+ W(A, ε)←W(A, ε)∪ {w} W(A, ε)←W(A, ε)\P R− W(A, ε)←W(A, ε)∪P R+ H(A)←H(A)∪H+ end for return G= (A, W (A, ε)∪H(A)) 8 a b (a) (b) (c) (d) (e) (f) (g) (h) (i) aa a a a a a a bb b bb bbb Figure 4: Possible layouts when processing wall-prone pairs of line segments: (a) intersection1, (b) intersection2, (c) contained1, (d) contained2, (e) common1, (f) common2, (g) common3, (h) common4 and (i) matching The result of the processing of each wall-prone pair depends on the relative position between the segments that form the pair. Figure 4 shows the nine possible cases that may appear. The changes that have to be applied to the WAG differ from one case to the other. In order to make the description of these changes easier, the set of wall-prone edges incident to a node awill be notated as E(a), while the set of nodes adjacent to a node awill be notated as V(a). The formal definition of these sets follows: E(a) = {{a, x} ∈ W(A, ε)} V(a) = {x∈ A | {a, x} ∈ W(A, ε)} Figure 5 shows how the segments from each particular layout are split to get wall pairs. The nodes representing segments in green in the figure are connected using the new wall edges that are added to the WAG, while the nodes representing segments in red in the figure are connected with the wall-prone edges that are modified. Table 1 shows a detailed description of the contents of A+,P R−,P R+,wand H+for each particular case. 9 Figure 10: Up: pairs of circular arcs. Down: detected walls associated to the floor plan segments. However, the walls are not the only element that forms the topology of a floor, since the openings (typically doors and windows) also play an important topological role as links between the spaces defined by the walls. Moreover, the intersections amid walls are not detected by the algorithm, and therefore it is necessary to process the detected walls to build these intersections. In order to get a simplified representation of a floor plan that represents its topology, each detected wall is represented by a single segment placed in-between its corresponding wall pair of segments. In order to keep the coherence of this representation, the openings have to be also represented by single segments. The process of finding the openings in a floor plan and computing the endpoints of the segments that topologically represent them is described below. After that, the steps to compute the intersections amid walls will be detailed. 8.1. Openings Openings are typically represented in a vector CAD drawing of a floor plan as instances of blocks, defined as compositions of single primitives (lines, polylines, circular arcs, etcetera) and/or other blocks. Block components are given coordinates with respect to the reference point of the block, which can be freely located by the designer; therefore, each block has its own coordinate system and a name. When a block instance is inserted in a CAD drawing, the designer defines its position, rotation and size. These transformations are applied to the block coordinate system, and then its components are translated, rotated and scaled as necessary. All the block instances share the same block name. In order to add the information of the openings to the floor topology representation, it is necessary to define a segment for each block representing an opening in the floor plan. The user intervention may be necessary to select the name of the blocks that represent openings in the floor plan, as current CAD applications do not force the designers to use standardized names. Once the blocks representing the openings have been selected, it is not enough to find the intersections between the block instances and the walls drawing, as this may lead to wrong points (see Figure 11). Instead of that, the following steps are applied to compute the representative segment for each block instance: 1. Compute the bounding box of the block instance. This can be done by applying the instance transformations to the bounding box of the geometry of the block definition. 16 Figure 11: Instance of a window block (in yellow). Black lines represent walls and their topological representation. The desired endpoints for the representative segment of the block are drawn in green, while red points are intersection points between the block and the walls drawing 2. Given the center of the bounding box, notated P, search for the nearest endpoint of a topology segment that represents a wall. This point will be notated as Q1, and will be considered as the first endpoint for the new segment. 3. Compute the vector −→ v1=Q1−P 4. Search the endpoints of the topology segments for the nearest point Q2such that given the vector −→ v2=Q2−P, the cosine of the angle between −→ v1and −→ v2is less than zero. 5. Create the segment that topologically represents the opening using Q1and Q2as endpoints. 8.2. Wall intersections The joint result of the wall detection algorithm and the processing of the opening blocks is a set of segments, most of them are already connected into polylines representing topology. However, due to the way the wall detection algorithm works, the intersections amid walls are still not found (see Figure 12). It is therefore necessary to process the polylines representing the topology to compute these intersection points and complete the topological representation of the floor plan. (a) (b) Figure 12: (a) Result of the wall detection process. (b) Intersection point that has to be computed The proposal presented here divides the process of computing the wall intersections in two steps: first of all, areas with a high concentration of polyline endpoints are sought in the topology representation; after that, a representative point is computed for each of these areas, as the topological representation of the wall intersection. In order to detect high endpoint concentration areas, the user intervention can be necessary to define a search radius (although a fixed value of one meter gives good results for typical floor plans). Then, the distances between every two endpoints are computed, and those endpoints placed at a closer distance than the search radius are included into the same set. In the end, the sets with more than one endpoint represent high concentration areas. Algorithm 2 summarizes this process. 17 Algorithm 2 Detection of high endpoint concentration areas Input: a set L={L1, ..., Ln}of npolylines representing topology; a search radius ρ Build a set for each endpoint of the polylines in L for i=1 to n−1do {p1, p2} ← endpoints(Li) for j=i+1 to ndo {q1, q2} ← endpoints(Lj) for all (p, q)∈ {p1, p2} × {q1, q2}do if dist(p, q)< ρ then merge the sets pand qbelong to end if end for end for end for return the remaining sets of endpoints The search radius has to be big enough to avoid problems due to the presence of columns in the floor plan, as shown in Table 3 and Figure 12. Once the high endpoint concentration areas have been detected, it is necessary to compute a topological intersection point for each of these. Depending on the floor plan layout, the intersection points are computed in a different way (see Table 3): •T-crossing amid walls Three topology segments appear in an orthogonal position, as shown in Figure 12.a. The intersection point is computed as the intersection of the lines that contain the segments. Figure 12.b shows the result for this situation. •L-crossing between walls In this layout, two topology segments are placed in an orthogonal position, representing a corner in the wall structure of the floor. The intersection point is then computed as the intersection of the lines that contain the walls. •X-crossing amid walls In this case, four walls meet orthogonally in a point, making up a cross-like intersection. The representative wall intersection point is computed as the intersection point between the lines that contain the wall segments. •I-crossing between walls This kind of crossing is due to the presence of a column in-between two parts of the same wall. When the wall detection algorithm processes this geometry, two unconnected wall segments are detected, and it is necessary to join them to form the topology representation of the original wall. Therefore, instead of a wall intersection point, a new wall segment is created for this purpose using the endpoints of the high concentration area. •Default case 18 Case Layout Wall intersection point T-crossing L-crossing X-crossing I-crossing Default (centroid) Table 3: Cases and solutions. 19 If the wall layout does not correspond to any of the cases described above, the representative wall intersection point is computed as the centroid of the set of points included in the high concentration area. Once the wall intersection points have been computed, the endpoints of the topology polylines are replaced by the intersection points obtained from the high concentration areas they belong to, so that a completely connected representation of the topology of the floor plan is obtained. 9. Results A standalone Java application has been developed as a platform to test all the algorithms that have been described [20]. The application is able to load and show a DXF file containing the vector drawing of a floor plan, and provides the user with tools to fix some precision related problems as described in Section 3, select the layer (or layers) with the walls and openings information, choose the values of the parameters for the detection algorithms and show and store the resulting topology representation. The algorithms have been tested in a computer with a 2.4 GHz Intel R CoreTM2 Quad processor with 4 GB of RAM using real floor plans of buildings of our university. Figure 13 shows three of the floor plans used and the result of applying the wall detection algorithm to them; the detected walls are drawn in blue. Although the algorithm has been only applied to the representation of walls, other layers are shown with different colors to give a better understanding of the floor plans. Table 4 shows some numerical results obtained in our tests using different threshold values (the results appear in the same order the results are shown in Figure 13). For each test, the table shows how many straight segments and circular arcs were used as input for the algorithm, the value of the threshold εused, the amount of wall and wall-prone edges in the initial generalized WAG that link respectively segments and arcs, the final number of wall edges at the end of the algorithm execution, the percentage of segments and arcs that do not belong to any wall in the result, the time spent to build the initial generalized WAG and the time the algorithm took to detect the walls. As can be seen, 1 millisecond is the lower limit for the execution of the wall detection algorithm. The final number of wall edges is equal to the sum of the initial number of wall edges and the number of wall-prone edges; this was the expected result, given the way the algorithm works. The time spent in the construction of the initial WAG is in general less than a second for floor plans with no more than 1700 segments, although the complexity of the drawing has a significant influence on this task. Figure 14 shows the representation of the topology of a portion of a real floor plan as obtained with the algorithms described in this paper, while Figure 15 shows the topology representation on top of the original floor plan. It is interesting to remark that using different values for the threshold εproduces significant changes in the results: the bigger the threshold, the more complex is the structure of the generalized WAG, because the number of relevant pairs of segments increases, and the time spent to build and process the graph is therefore higher. On the other hand, the number of segments and arcs that are not considered as part of a wall pair at the end of the wall detection algorithm decreases as the value of the threshold 20 Figure 13: Real floor plans used to test our algorithms, together with the results of applying the wall detection algorithm. Detected walls are drawn in blue. The layers containing windows and doors are shown, but have not been processed 21 TABLE LEGEND A1-A2. Number of segments/arcs in the floor plan respectively ε. Threshold used to form segment pairs B1-B2. Number of initial wall-prone edges linking segments/arcs respectively C1-C2. Number of initial wall edges linking segments/arcs respectively D1-D2. Number of final wall edges linking segments/arcs respectively E1-E2. Segments/arcs that do not form walls respectively (%) F. WAG building time (milliseconds) G. WAG processing time (milliseconds) Plan A1 A2 εB1 B2 C1 C2 D1 D2 E1 E2 F G 1 643 0 0.4 193 0 56 0 249 0 36.10 0 118.50 1.09 0.5 199 0 58 0 257 0 35.00 0 119.17 1.10 0.6 203 0 60 0 263 0 33.90 0 122.03 1.16 0.7 236 0 62 0 298 0 26.59 0 136.92 1.35 2 1148 14 0.4 482 9 159 0 641 9 32.50 11.10 612.21 3.99 0.5 549 9 206 0 755 9 25.10 11.10 755.40 5.08 0.6 628 9 244 0 872 9 16.00 11.10 937.65 6.38 0.7 692 9 287 0 979 9 10.10 11.10 1161.43 8.37 3 1678 79 0.4 442 20 93 0 535 20 47.73 54.43 696.45 4.45 0.5 455 20 104 0 559 20 45.76 54.43 785.69 4.91 0.6 637 33 176 0 813 33 26.04 26.58 922.89 5.21 0.7 667 33 190 0 857 33 22.76 26.58 957.27 5.56 Table 4: Numerical data from the wall detection tests with real floor plans increases. It could be interesting to study more carefully this issue in order to find a way to compute dinamically the optimum value of the threshold for each floor plan. 10. Conclusions and future work A method to extract topological information from 2D CAD vector floor plans has been presented. The problem is divided into several stages: first of all, the wall detection algorithm produces the basic wall topology; after that, the blocks representing the openings are processed in order to link their representation to the wall topology; finally, the wall intersections are computed to complete the topology representation of the floor. The Wall Adjacency Graph (WAG) has been presented as the supporting data structure of the wall detection algorithm. It stores the topological relations amid the segments (represented as graph nodes) that compose the drawing of the wall structure of the floor plan, using three kind of edges: wall, wall-prone and hierarchical edges. An initial WAG is directly built from the floor plan; then, the wall detection algorithm processes the graph in linear time with respect to the number of wall-prone edges. The topological information about walls is obtained directly from the final WAG in an easy way. All this process typically takes less than one second using real floor plans. In order to handle appropriately some particular cases, a generalizazed, less restrictive version of the WAG has been presented that allows a more flexible detection process. 22 Figure 14: Topology representation from a portion of a CAD vector floor plan Future work include the detection of additional elements like stair flights, the use of spatial indices to speed up the WAG building process, the study of a way to compute the optimum threshold value for a given floor plan, as well as the inclusion of semantic information in the same process, so that the user intervention can be minimized. The long term goal is to integrate the topology detection process into a complete system for 3D building reconstruction. Acknowledgements This work has been partially supported by the Andalusian Government, the Spanish Ministry of Science and Innovation and the European Union (via ERDF funds) through the research projects P07-TIC-02773 and TIN2007-67474-C03. References [1] D. Brutzman, L. Daly, X3D. Extensible 3D graphics for web authors, Morgan Kaufmann, 2007. [2] R. Arnaud, M. Barnes, COLLADA. Sailing the gulf of 3D digital content creation, A.K. Peters, 2006. [3] A. E. Walsh, M. Bourges-S´evenier, Core Web3D, Prentice Hall PTR, Upper Saddle River, NJ, USA, ISBN 0-13-085728-9, 2001. [4] Y. Li, Z. He, 3D Indoor Navigation: a Framework of Combining BIM with 3D GIS, in: 44th ISOCARP Congress, 2008. [5] J. Benner, A. Geiger, K. Leinemann, Flexible Generation of Semantic 3D Building Models, in: Proceedings of the 1st International Workshop on Next Generation 3D City Models, 2005. [6] P. M¨uller, P. Wonka, S. Haegler, A. Ulmer, L. Van Gool, Procedural modeling of buildings, ACM Trans. Graph. 25 (3) (2006) 614–623, ISSN 0730-0301. [7] J. W. Choi, D. Y. Kwon, J. E. Hwang, J. Lertlakkhanakul, Real-time management of spatial information of design: A space-based floor plan representation of buildings, Automation in Construction 16 (4) (2007) 449–459. [8] C. Ah-Soon, K. Tombre, Architectural symbol recognition using a network of constraints, Pattern Recogn. Lett. 22 (2) (2001) 231–248, ISSN 0167-8655. [9] P. Dosch, K. Tombre, C. Ah-Soon, G. a. Masini, A complete system for the analysis of architectural drawings, International Journal on Document Analysis and Recognition V3 (2) (2000) 102–116. 23 Figure 15: Topology representation on top of the original CAD vector floor plan [10] J. Llad´os, J. L´opez-Krahe, E. Mart´ı, A system to understand hand-drawn floor plans using subgraph isomorphism and Hough transform, Mach. Vision Appl. 10 (3) (1997) 150–158, ISSN 0932-8092. [11] T. Lu, H. Yang, R. Yang, S. Cai, Automatic analysis and integration of architectural drawings, Int. J. Doc. Anal. Recognit. 9 (1) (2007) 31–47, ISSN 1433-2833. [12] S. Horna, D. Meneveaux, G. Damiand, Y. Bertrand, Consistency constraints and 3D building reconstruction, Computer Aided Design 41 (1) (2009) 13–27. [13] A. Mas, G. Besuievsky, Automatic architectural 3D model generation with sunlight simulation, in: Ibero-American Symposium on Computer Graphics, 37–44, 2006. [14] A. Paoluzzi, F. Milicchio, G. Scorzelli, M. Vicentino, From 2D Plans to 3D Building Models for Security Modeling of Critical Infrastructures, International Journal of Shape Modeling 14 (1) (2008) 61–78. [15] B. Medjdoub, B. Yannou, Separating topology and geometry in space planning, Computer-Aided Design 32 (1) (2000) 39 – 61, ISSN 0010-4485. [16] G. Zhi, S. Lo, Z. Fang, A graph-based algorithm for extracting units and loops from architectural floor plans for a building evacuation model, Computer-Aided Design 35 (1) (2003) 1–14. [17] National CAD Standard, v.4.0, http://www.nationalcadstandard.org, 2008. [18] ISO 13567: Organization and naming of layers for CAD, ISO (International Organization for Standardization), http://www.iso.org, 1998. [19] N. Davies, et al., AEC (UK) CAD Standard for basic layer naming, v.2.4, http://www.aec-uk.org, 2005. [20] B. Dom´ınguez, F. Conde, ´ A.L. Garc´ıa, F. R. Feito, On the specification and interface design of a semiautomatic tool for the detection of semantic elements in a floor plan, Tech. Rep., Departamento de Inform´atica. Universidad de Ja´en, 2011. [21] B. Dom´ınguez, A. L. Garc´ıa, F. R. Feito, An Open Source Approach to Semiautomatic 3D Scene Generation for Interactive Indoor Navigation Environments, in: Proceedings of IV Ibero-American Symposium on Computer Graphics, 131–138, 2009. 24