Semiau oma ic de ec ion o loo opology om CAD
a chi ec u al d awings
B. Dom´ıngueza,∗,´
A.L. Ga c´ıaa, F.R. Fei oa
aDepa amen o de In o m´a ica, Uni e sidad de Ja´en - Campus de Las Lagunillas s/n. - 23071 Ja´en
(SPAIN)
Abs ac
A me hod o he semiau oma ic de ec ion o he opology o building loo s ep e-
sen ed as CAD d awings s o ed in ec o ile o ma is p esen ed in his pape . This
me hod in ol es he de ec ion o walls and join poin s amid walls and openings, and he
sea ch o in e sec ion poin s amid walls.
To gi e suppo o he wall de ec ion p ocess, his pape in oduces he wall adjacency
g aph (WAG), a da a s uc u e c ea ed o de ec walls om se s o plana segmen s con-
ained in a chi ec u al loo plans. Wall adjacency g aphs allow us o ob ain a consis en
and exhaus i e se o walls e y quickly (less han one second o eal loo plans). A
gene alized e sion o he wall adjacency g aph is also p esen ed o deal wi h some o
he limi a ions o he ini ial WAG. Algo i hms o he de ec ion o join poin s and wall
in e sec ion poin s a e p esen ed as well, based on he analysis o he geome y om he
inpu CAD d awings. Mo eo e , all his p ocess wo ks app op ia ely wi h bo h s aigh
and ci cula segmen s.
The ob ained loo opology can la e be used as inpu o gene a e 3D models o
buildings, which a e widely used on i ual ci ies, BIM sys ems and GIS.
Keywo ds: Building In o ma ion Models, CAD d awings, Compu a ional Geome y,
G aph Theo y
1. In oduc ion
The e is li le doub abou he e olu ion o he way humans in e ac wi h compu e s.
Yea a e yea , new ad ances in ha dwa e and so wa e a e leading us o new and
amazing senso y expe iences in which i ual en i onmen s a e combined wi h o he
kinds o da a in o de o ul ill all he in o ma ional needs o he use s. Mo eo e , he
compu e pe o mance/p ice a io is con inuously g owing, and nowadays he use s can
a o d compu e s able o handle mos o hese ea u es easily.
∗Co esponding au ho
Email add esses: [email p o ec ed] (B. Dom´ınguez), [email p o ec ed] (´
A.L. Ga c´ıa),
[email p o ec ed] (F.R. Fei o)
P ep in submi ed o Compu e -Aided Design June 15, 2016
The popula i y o na iga ion h ough i ual 3D en i onmen s is apidly g owing,
hanks o applica ions and de elopmen pla o ms like Google Ea h c
o Mic oso Vi -
ual Ea h c
, which allow use s o no only explo e ae ial and sa elli e pho og aphs all
o e he wo ld, bu also examine h ee-dimensional econs uc ions o buildings and mon-
umen s (when a ailable). While mos o hese ools a e in ended o ou doo na iga ion,
he e also exis websi es which o e in e ac i e indoo 3D na iga ion in o de o le he
use s enjoy i ual ou s h ough he acili ies o a company, a museum, a uni e si y,
e ce e a. These in e ac i e i ual ou s usually ely on a hi d pa y plugin, and use
VRML, X3D [1], COLLADA [2], and o he echnologies ela ed o Web3D [3] o desc ibe
he geome y and appea ance o he scenes as well as he beha iou o hei elemen s.
A chi ec u al 3D indoo scenes a e ypically de eloped om sc a ch, o comme cial
applica ions like Au odesk c
3ds Max c
a e used o pe o m some kind o 2D- o-3D con-
e sion using he loo plan o he scene as inpu , bu his p ocess is no s aigh o wa d,
and he use mus modi y he p elimina y esul in o de o ob ain he inal geome y.
I is he e o e desi able o ha e au oma ic ools which can ake a 2D loo plan as inpu ,
and gene a e a 3D model in a o ma gene al enough o be used o di e en pu poses.
As a i s s ep o his au oma ic p ocess, his pape is ocused on ex ac ing opological
in o ma ion om 2D ec o loo plans composed o low-le el geome ic p imi i es. This
aim implies he de elopmen o algo i hms o analyze geome y and ob ain seman ic
ea u es ha can be used on Building In o ma ion Model (BIM) sys ems, GIS and ci y
models [4, 5, 6, 7].
The es o he pape is s uc u ed as ollows: i s , some p e ious wo ks a e summa-
ized in sec ion 2. Sec ions 3 o 7 explain he wall de ec ion p ocess using wall adjacency
g aphs (WAG’s). Sec ion 8 desc ibes he de ec ion o join poin s amid walls and open-
ings and he sea ch o in e sec ion poin s amid walls. Finally, sec ions 9 and 10 p esen
he esul s, conclusions and u u e wo k.
2. P e ious wo k
The e a e se e al s udies ela ed o he p ocessing o a chi ec u al loo plans. They
can be g ouped acco ding o he kind o inpu and he goals o he p ocess:
•Some in e es ing wo ks in oduce me hods o ecognize special symbols om a loo
plan. These me hods ypically apply Compu e Vision and Pa e n Recogni ion
echniques on scanned loo plans o ob ain hei esul s. Ah-Soon and Tomb e [8]
use ne wo ks o cons ain s on geome ical ea u es o ind symbols ha ep esen
doo s and windows, de ining a o mal g amma o desc ibe wha ha e o be ecog-
nized. On he o he hand, Dosch e al. [9] desc ibe a comple e sys em o symbol
ecogni ion in ol ing Compu e Vision ools such as segmen a ion, ec o iza ion
and ea u e de ec ion; he esul is used o c ea e a 3D econs uc ion o he loo
(wi hou opology in o ma ion) by means o ex uding he ecognized 2D geome-
y. O he in e es ing wo ks include he one om Llad´os e al. [10], who apply he
Hough ans o m o ecognize symbols om hand-d awn a chi ec u al loo plans,
and he one om Lu e al. [11], who deal wi h he ecogni ion o s uc u al objec s
and he classi ica ion o wall shapes.
•CAD ec o d awings a e he inpu da a conside ed by o he esea che s ha p o-
pose me hods o gene a e 3D building models. These include he wo k om Ho na
2
e al. [12], who de ine he gene alized-maps o ep esen adjacency ela ions amid
geome ic elemen s, and use hem o ex ac 2D opology and 3D olumes om a
loo plan, gi en some assump ions on he quali y o he loo plan and some con-
side a ions abou he s uc u e o a building ha allow hem o de ine cons ain s
on he geome y; occasionally, he use in e en ion can be necessa y o p o ide
seman ic associa ions o he geome y, and cu ed walls a e conside ed as polylines.
As a as we know, no u he ad ances on his app oach ha e been published up o
now. O he wo ks a e he one by Mas and Besuie sky [13], based on he ex usion
o plana polygons om CAD ec o d awings o gene a e 3D building models used
o ligh simula ion, and he one by Paoluzzi e al. [14], who use 3D econs uc ion
o secu i y modelling o c i ical in as uc u es.
•A hi d g oup o wo ks in oduce me hods o e ie e opological in o ma ion om
CAD ec o d awings, like he one om Medjdoub and Yannou [15], who use g aphs
o s o e adjacency ela ions amid loo s, ooms and s ai s du ing he design s age.
O he ela ed wo k is he one om Zhi e al. [16], who build a opology g aph o
desc ibe he dis ibu ion o walls and openings in a loo plan, and sea ch o a se
o undamen al loops o ind co ido s and ooms, so ha an e acua ion plan can
be c ea ed om ha in o ma ion; his wo k emphasizes he loop sea ch, bu gi es
e y ew de ails on he g aph building p ocess.
3. P oblem o e iew
The p oblem we ace he e is he ex ac ion o opological in o ma ion om a building
loo plan. Typically, building designs a e s o ed as ec o d awings c ea ed wi h CAD
so wa e applica ions and composed o low le el g aphical p imi i es, like lines, polylines,
ci cula a cs, e ce e a. Op ionally, blocks can be c ea ed as combina ions o p imi i es
and/o o he blocks; his allow he use o easily c ea e and ins an ia e ep esen a ions
o common elemen s like doo s, windows o u ni u e.
Mo eo e , CAD applica ions allow he designe o spli he g aphical in o ma ion in
laye s o g oup ela ed elemen s oge he , and whose isibili y can be swi ched on o o
in o de o emphasize wha is eally impo an in e e y si ua ion.
In o de o ge he opology om a loo plan, i is necessa y o ob ain he in o ma ion
abou he walls and openings i con ains. Al hough he e exis se e al s anda ds on how
he laye s should be o ganized in a chi ec u al design [17, 18, 19], CAD applica ions
do no o ce he use s o ollow any o hese s anda ds, and he e o e i is possible o
ind CAD d awings whe e he in o ma ion ega ding walls and openings is mixed wi h
o he da a o di ided in o se e al laye s. The second si ua ion is easily sol ed by mixing
he con en s o he laye s ha keep he desi ed in o ma ion, whe eas he i s si ua ion
is s ill an open p oblem, because ypically he e is no addi ional da a (apa om line
a ibu es like colo o hickness) o suppo au oma ic ex ac ion o p imi i es om he
laye s wi hou in ol ing he use . He e we conside ha he walls a e s o ed in one o
se e al laye s, bu mixed wi h no hing else han (op ionally) he openings, and ha he
openings a e ep esen ed by blocks.
One addi ional p oblem ha appea s some imes when p ocessing CAD ec o d aw-
ings is ela ed wi h p ecision: o e lapping segmen s o duplica ed e ices can appea i
he use is no ca e ul enough when c ea ing he loo plan. These si ua ions ha e o be
3
de ec ed and co ec ed by checking all he geome y and me ging aul y e ices and seg-
men s, and may equi e he use in e en ion o se a p ecision h eshold. To be p ecise,
he ollowing asks ha e been implemen ed success ully in ou es aplica ion [20]: seg-
men s wi h ze o leng h a e emo ed om he loo plan, pa ially o e lapping segmen s
a e eplaced by a unique segmen ob ained by me ging hem, and in hose cases whe e
he e a e wo copies o he same segmen , one o hem is emo ed. Occasionally, hese
changes may p oduce new p ecision ela ed p oblems; he e o e, he p ocess o checking
and co ec ing hese si ua ions has o loop au oma ically o e he geome y un il he e
a e no mo e changes o be applied.
E e y wall in a ec o d awing o a loo plan is ep esen ed by wo pa allel line
segmen s, bu he mapping be ween pai s o segmen s and walls is no bijec i e, i.e. wo
consecu i e walls may sha e one segmen (see Figu e 1).
Figu e 1: The mapping be ween pai s o segmen s and walls is no bijec i e, e.g. he walls ab and ac
sha e he segmen a.
Fu he mo e, he e is no in o ma ion abou which segmen s ma ch o make up a wall.
The e o e, he wall de ec ion p ocess in ol es sea ching o wall-p one pai s o segmen s
using a h eshold ε(maximum wall hickness), and spli hem in o de o ob ain wall
pai s. The ollowing de ini ions cla i y hese concep s:
De ini ion 1 (Wall-p one pai o line segmen s). Le aand bbe line segmen s in
R2. Le and sbe he lines con aining aand b espec i ely, and a′and b′ he p ojec ions
o aand bon o sand . Gi en a ixed h eshold ε, he pai (a, b)is wall-p one ( ep esen ed
by he p edica e p one(a, b, ε)) i and only i all hese condi ions a e held:
C1. aand ba e pa allel: akb
C2. a′and b(and he e o e b′and a) o e lap: a′∩b6=∅
C3. The dis ance be ween and sis less han o equal o he h eshold: d( , s)≤ε
No e: In his wo k line segmen s a e conside ed open ( hei end poin s do no belong
o hem), o a oid he special case whe e wo line segmen s wi h consecu i e p ojec ions
hold condi ion C2.
De ini ion 2 (Wall pai o line segmen s). Two line segmen s aand ba e said o
o m a wall pai , gi en a ixed h eshold ε( ep esen ed by he p edica e wall(a, b, ε)), i
hey hold he condi ions o be a wall-p one pai , and hei p ojec ions on o he line ha
con ain each o he ma ch. The e o e, a new, mo e es ic i e condi ion is added o C1,C2
and C3:
C4. a′and b(and he e o e b′and a) a e he same: a′=b
4
Some p ope ies o hese p edica es a e inmedia e:
•p one does no depend on he segmen o de : p one(a, b, ε)⇔p one(b, a, ε)
•wall does no depend on he segmen o de : wall(a, b, ε)⇔wall(b, a, ε)
•wall is a es ic ion o p one:wall(a, b, ε)⇒p one(a, b, ε)
Gi en he abo e de ini ions, his is he ou line o he algo i hm o compu e he walls
ep esen ed by a se o segmen s in a loo plan (see example in Figu e 2):
Figu e 2: I e a ion o he algo i hm. (1) Ini ial se o segmen s and ela ions. (2) P ojec ion o he end
poin s. (3) Segmen spli ing and wall ex ac ion. (4) Upda ed segmen s and ela ions
(1) Find all he wall-p one pai s. In Figu e 2.1, hese pai s a e (a, c), (a, d) and (b, d).
(2) Fo each wall-p one pai , apply he ollowing s eps (in his example, we ake he
pai (a, d)):
(2.a) Compu e he p ojec ions o he end poin s o one segmen on he o he seg-
men . Applying his s ep o he wall-p one pai (a, d) esul s in poin s 1 and
2, as shown in Figu e 2.2.
(2.b) Spli each segmen using he compu ed p ojec ions and check he new se o
segmen s o wall pai s: some segmen s will o m wall pai s while he es will
become single ( hei p ojec ions do no o e lap). In Figu e 2.3, he esul ing
segmen s a e a1,a2,d1and d2. The new de ec ed wall pai is (a2, d1), and
he single segmen s a e a1and d2.
(2.c) Upda e he se o segmen s by emo ing he old segmen s (aand din his
case) and adding he single ones (a1and d2). Then, upda e he wall-p one
pai se ; in his example, wall-p one pai s (a1, c) and (b, d2) a e added, as
shown in Figu e 2.4.
In o de o make he p ocessing o wall and wall-p one ela ions amid segmen s easie ,
and keep eco d o he hie a chical ela ions be ween each line segmen and he pieces i
is spli in o, he Wall Adjacency G aph is p oposed as a da a s uc u e o gi e suppo
o his p ocess. The ollowing sec ions gi e a de ailed desc ip ion o his s uc u e and
i s applica ion o he p oblem.
5
4. The Wall Adjacency G aph
The Wall Adjacency G aph (WAG) is a g aph whose nodes ep esen he line segmen s
om a loo plan ha a e in ol ed in he ep esen a ion o walls, and whose edges
ep esen ela ions be ween hose segmen s. In o de o ep esen he walls d awn in a
loo plan, h ee kind o ela ions be ween segmen s a e de ined as ollows:
De ini ion 3 (Wall-p one ela ion). Gi en a ini e se o line segmen s Aand a ixed
h eshold ε, he wall-p one ela ion o e Ais de ined as he se
P R(A, ε) = {(a, b)∈ A × A | p one(a, b, ε)}
De ini ion 4 (Wall ela ion). Gi en a ini e se o line segmen s Aand a ixed h esh-
old ε, he wall ela ion o e Ais de ined as he se
W(A, ε) = {(a, b)∈ A × A | wall(a, b, ε)}
As he ela ions de ined abo e a e based on De ini ions 1 and 2, he ollowing p op-
e ies hold:
•P R(A, ε) is symme ic: (a, b)∈P R(A, ε)⇔(b, a)∈P R(A, ε)
•W(A, ε) is symme ic: (a, b)∈W(A, ε)⇔(b, a)∈W(A, ε)
•W(A, ε)⊆P R(A, ε)
As he wall-p one pai s a e being p ocessed, hei segmen s a e spli in o pieces. Fo
each segmen a, he se o pieces i is spli in o o m a pa i ion P(a) o ha segmen ,
because hey do no o e lap.
In o de o s o e in he Wall Adjacency G aph he in o ma ion abou pa i ions, one
mo e ela ion is de ined as ollows:
De ini ion 5 (Hie a chical ela ion). Gi en a ini e se o line segmen s A, he hi-
e a chical ela ion o e Ais de ined as he se
H(A) = {(a, b)∈ A × A | b∈P(a)}
Unlike he wall and wall-p one ela ions, he hie a chical ela ion is ob iously no
symme ic.
Once all he elemen s ha a e in ol ed in he Wall Adjacency G aph a e de ined, a
o mal de ini ion o his s uc u e ollows:
De ini ion 6 (Wall Adjacency G aph). Gi en a ini e se o line segmen s Aand
a ixed h eshold ε, he Wall Adjacency G aph (WAG) associa ed wi h Ais a g aph
G(A, ε) = (A, P R(A, ε)∪H(A)).
Fo a gi en loo plan, i s WAG is he e o e o med by he line segmen s i con ains,
oge he wi h he ela ions amid hem. A WAG is no necessa ily connec ed, and his is
no a equi emen o he algo i hms o wo k success ully.
Due o he ac ha W(A, ε)⊆P R(A, ε), i is necessa y o dis inguish he se o
s ic wall-p one segmen pai s ha do need o be p ocessed o ge wall pai s; he e o e,
6
he se W(A, ε) is de ined as he complemen o W(A, ε) wi h espec o P R(A, ε), i.e.
W=P R(A, ε) W(A, ε).
F om now on, WAG edges ep esen ing wall and wall-p one ela ions will be no a ed
(when necessa y) as uno de ed pai s {a, b}, as hese ela ions a e symme ic; simila ly,
WAG edges ep esen ing hie a chical ela ions will be no a ed as o de ed pai s (a, b).
Example 1 (Ini ial WAG). Figu e 3 shows an example o (a) an ini ial se o line
segmen s and (b) i s associa ed WAG. Edges ep esen ing wall-p one ela ions a e d awn
wi h single lines, while edges ep esen ing wall ela ions appea as double lines. The
elemen s de ining he WAG a e:
A={a1, a2, a3, a4, a5}
P R(A, ε) = {{a1, a4},{a2, a4},{a3, a5}}
H(A) = ∅
The pai s in P R(A, ε)can be g ouped in o wall and wall-p one se s:
W(A, ε) = {{a3, a5}}
W(A, ε) = {{a1, a4},{a2, a4}}
a1a2a3
a4a5
(a) (b)
ε
a4a2
a1a3a5
Figu e 3: Example o (a) a se o line segmen s (b) i s associa ed WAG using a h eshold ε. Single lines
ep esen wall-p one ela ions, while double lines ep esen wall ela ions.
5. Wall de ec ion algo i hm
In sec ion 3, an ou line o he wall de ec ion algo i hm was desc ibed. Now ha
desc ip ion will be e ised, including he WAG as unde lying da a s uc u e o his
algo i hm.
The inpu o his p ocess is he se o line segmen s ha ep esen he walls in a
ec o d awing o a loo plan. As men ioned in sec ion 3, hese segmen s a e conside ed
as he unique con en s o one laye o he d awing, o al e na i ely, he unique esul o
he mix u e o se e al ones. Gi en his se , i is possible o es ima e au oma ically he
alue o he h eshold εas desc ibed in [21], o he use can be equi ed o ix his alue,
as i is essen ial o he es o he p ocess.
As a p elimina y s ep, i is necessa y o build he ini ial WAG o he segmen s. I s
elemen s (A,P R(A, ε) and H(A) ) a e assigned as ollows:
• A is de ined as he ini ial se o segmen s.
7
•H(A) is emp y.
•To build he ini ial se o wall-p one ela ions P R(A, ε), each possible pai o line
segmen s (a, b) has o be analyzed o de e mine whe he i holds he condi ions o
be a wall o a wall-p one pai . Fo he con enience o he wall de ec ion algo i hm,
his se is subdi ided in o he subse s W(A, ε) and W(A, ε), de ined in sec ion 4.
Once he WAG has been c ea ed, he wall-p one pai s om he subse W(A, ε) a e
p ocessed in u n o ob ain wall pai s. The e a e nine possible ypes o wall-p one pai s;
he way hey a e p ocessed will be de ailed la e .
The p ocessing o each wall-p one pai esul s in a se ies o changes in he WAG:
•As desc ibed in sec ion 3, i could be necessa y o di ide he segmen s om he
pai and use hei pieces o build new wall and wall-p one pai s; new nodes would
he e o e be added o he WAG o ep esen hese pieces. The se o added nodes
will be no a ed as A+.
•Including new nodes in he WAG implies changing g aph edges o ep esen he
new wall and wall-p one pai s ha a e c ea ed. This esul s in he dele ion o some
wall-p one edges and he addi ion o new ones. The se s P R−and P R+ ep esen
hese edges. Mo eo e , a wall-p one pai is always dele ed o p oduce a wall pai ,
and he e o e a wall edge whas also o be added o he WAG.
•In o de o keep ack o he o igin o each node, edges ep esen ing he hie a chical
ela ion be ween he nodes co esponding o he segmen s ha a e spli and he
nodes ep esen ing he pieces hey a e spli in o a e added o he g aph. The se
H+ ep esen s hese edges.
A he end o he p ocess, he e only exis wall pai s in he s uc u e, he e o e
P R(A, ε)≡W(A, ε). Algo i hm 1 o mally desc ibes he wall de ec ion p ocedu e using
he WAG as suppo ing da a s uc u e.
Algo i hm 1 Wall de ec ion algo i hm
Inpu : A, ε
Build W(A, ε) = {{a, b} | a, b ∈ A ∧ p one(a, b, ε)∧ ¬wall(a, b, ε)}
Build W(A, ε) = {{a, b} | a, b ∈ A ∧ wall(a, b, ε)}
Build H(A) = ∅
o all {a, b} ∈ W(A, ε)do
S udy he layou o 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 o
e u n G= (A, W (A, ε)∪H(A))
8
a
b
(a) (b) (c) (d)
(e) ( ) (g) (h) (i)
aa a
a a a a a
bb b
bb
bbb
Figu e 4: Possible layou s when p ocessing wall-p one pai s o line segmen s: (a) in e sec ion1, (b)
in e sec ion2, (c) con ained1, (d) con ained2, (e) common1, ( ) common2, (g) common3, (h) common4
and (i) ma ching
The esul o he p ocessing o each wall-p one pai depends on he ela i e posi ion
be ween he segmen s ha o m he pai . Figu e 4 shows he nine possible cases ha
may appea . The changes ha ha e o be applied o he WAG di e om one case o
he o he . In o de o make he desc ip ion o hese changes easie , he se o wall-p one
edges inciden o a node awill be no a ed as E(a), while he se o nodes adjacen o a
node awill be no a ed as V(a). The o mal de ini ion o hese se s ollows:
E(a) = {{a, x} ∈ W(A, ε)}
V(a) = {x∈ A | {a, x} ∈ W(A, ε)}
Figu e 5 shows how he segmen s om each pa icula layou a e spli o ge wall pai s.
The nodes ep esen ing segmen s in g een in he igu e a e connec ed using he new
wall edges ha a e added o he WAG, while he nodes ep esen ing segmen s in ed in
he igu e a e connec ed wi h he wall-p one edges ha a e modi ied. Table 1 shows a
de ailed desc ip ion o he con en s o A+,P R−,P R+,wand H+ o each pa icula
case.
9
Figu e 10: Up: pai s o ci cula a cs. Down: de ec ed walls
associa ed o he loo plan segmen s. Howe e , he walls a e no he only elemen ha
o ms he opology o a loo , since he openings ( ypically doo s and windows) also
play an impo an opological ole as links be ween he spaces de ined by he walls.
Mo eo e , he in e sec ions amid walls a e no de ec ed by he algo i hm, and he e o e
i is necessa y o p ocess he de ec ed walls o build hese in e sec ions.
In o de o ge a simpli ied ep esen a ion o a loo plan ha ep esen s i s opology,
each de ec ed wall is ep esen ed by a single segmen placed in-be ween i s co esponding
wall pai o segmen s. In o de o keep he cohe ence o his ep esen a ion, he openings
ha e o be also ep esen ed by single segmen s. The p ocess o inding he openings in
a loo plan and compu ing he endpoin s o he segmen s ha opologically ep esen
hem is desc ibed below. A e ha , he s eps o compu e he in e sec ions amid walls
will be de ailed.
8.1. Openings
Openings a e ypically ep esen ed in a ec o CAD d awing o a loo plan as in-
s ances o blocks, de ined as composi ions o single p imi i es (lines, polylines, ci cula
a cs, e ce e a) and/o o he blocks. Block componen s a e gi en coo dina es wi h espec
o he e e ence poin o he block, which can be eely loca ed by he designe ; he e o e,
each block has i s own coo dina e sys em and a name.
When a block ins ance is inse ed in a CAD d awing, he designe de ines i s posi ion,
o a ion and size. These ans o ma ions a e applied o he block coo dina e sys em,
and hen i s componen s a e ansla ed, o a ed and scaled as necessa y. All he block
ins ances sha e he same block name.
In o de o add he in o ma ion o he openings o he loo opology ep esen a ion, i
is necessa y o de ine a segmen o each block ep esen ing an opening in he loo plan.
The use in e en ion may be necessa y o selec he name o he blocks ha ep esen
openings in he loo plan, as cu en CAD applica ions do no o ce he designe s o use
s anda dized names.
Once he blocks ep esen ing he openings ha e been selec ed, i is no enough o ind
he in e sec ions be ween he block ins ances and he walls d awing, as his may lead o
w ong poin s (see Figu e 11). Ins ead o ha , he ollowing s eps a e applied o compu e
he ep esen a i e segmen o each block ins ance:
1. Compu e he bounding box o he block ins ance. This can be done by applying
he ins ance ans o ma ions o he bounding box o he geome y o he block
de ini ion.
16
Figu e 11: Ins ance o a window block (in yellow). Black lines ep esen walls and hei opological
ep esen a ion. The desi ed endpoin s o he ep esen a i e segmen o he block a e d awn in g een,
while ed poin s a e in e sec ion poin s be ween he block and he walls d awing
2. Gi en he cen e o he bounding box, no a ed P, sea ch o he nea es endpoin
o a opology segmen ha ep esen s a wall. This poin will be no a ed as Q1,
and will be conside ed as he i s endpoin o he new segmen .
3. Compu e he ec o −→
1=Q1−P
4. Sea ch he endpoin s o he opology segmen s o he nea es poin Q2such ha
gi en he ec o −→
2=Q2−P, he cosine o he angle be ween −→
1and −→
2is less
han ze o.
5. C ea e he segmen ha opologically ep esen s he opening using Q1and Q2as
endpoin s.
8.2. Wall in e sec ions
The join esul o he wall de ec ion algo i hm and he p ocessing o he opening
blocks is a se o segmen s, mos o hem a e al eady connec ed in o polylines ep esen ing
opology. Howe e , due o he way he wall de ec ion algo i hm wo ks, he in e sec ions
amid walls a e s ill no ound (see Figu e 12). I is he e o e necessa y o p ocess he
polylines ep esen ing he opology o compu e hese in e sec ion poin s and comple e
he opological ep esen a ion o he loo plan.
(a) (b)
Figu e 12: (a) Resul o he wall de ec ion p ocess. (b) In e sec ion poin ha has o be compu ed
The p oposal p esen ed he e di ides he p ocess o compu ing he wall in e sec ions
in wo s eps: i s o all, a eas wi h a high concen a ion o polyline endpoin s a e sough
in he opology ep esen a ion; a e ha , a ep esen a i e poin is compu ed o each o
hese a eas, as he opological ep esen a ion o he wall in e sec ion.
In o de o de ec high endpoin concen a ion a eas, he use in e en ion can be
necessa y o de ine a sea ch adius (al hough a ixed alue o one me e gi es good
esul s o ypical loo plans). Then, he dis ances be ween e e y wo endpoin s a e
compu ed, and hose endpoin s placed a a close dis ance han he sea ch adius a e
included in o he same se . In he end, he se s wi h mo e han one endpoin ep esen
high concen a ion a eas. Algo i hm 2 summa izes his p ocess.
17
Algo i hm 2 De ec ion o high endpoin concen a ion a eas
Inpu : a se L={L1, ..., Ln}o npolylines ep esen ing opology; a sea ch adius ρ
Build a se o each endpoin o he polylines in L
o i=1 o n−1do
{p1, p2} ← endpoin s(Li)
o j=i+1 o ndo
{q1, q2} ← endpoin s(Lj)
o all (p, q)∈ {p1, p2} × {q1, q2}do
i dis (p, q)< ρ hen
me ge he se s pand qbelong o
end i
end o
end o
end o
e u n he emaining se s o endpoin s
The sea ch adius has o be big enough o a oid p oblems due o he p esence o
columns in he loo plan, as shown in Table 3 and Figu e 12.
Once he high endpoin concen a ion a eas ha e been de ec ed, i is necessa y o
compu e a opological in e sec ion poin o each o hese. Depending on he loo plan
layou , he in e sec ion poin s a e compu ed in a di e en way (see Table 3):
•T-c ossing amid walls
Th ee opology segmen s appea in an o hogonal posi ion, as shown in Figu e 12.a.
The in e sec ion poin is compu ed as he in e sec ion o he lines ha con ain he
segmen s. Figu e 12.b shows he esul o his si ua ion.
•L-c ossing be ween walls
In his layou , wo opology segmen s a e placed in an o hogonal posi ion, ep e-
sen ing a co ne in he wall s uc u e o he loo . The in e sec ion poin is hen
compu ed as he in e sec ion o he lines ha con ain he walls.
•X-c ossing amid walls
In his case, ou walls mee o hogonally in a poin , making up a c oss-like in e -
sec ion. The ep esen a i e wall in e sec ion poin is compu ed as he in e sec ion
poin be ween he lines ha con ain he wall segmen s.
•I-c ossing be ween walls
This kind o c ossing is due o he p esence o a column in-be ween wo pa s
o he same wall. When he wall de ec ion algo i hm p ocesses his geome y, wo
unconnec ed wall segmen s a e de ec ed, and i is necessa y o join hem o o m he
opology ep esen a ion o he o iginal wall. The e o e, ins ead o a wall in e sec ion
poin , a new wall segmen is c ea ed o his pu pose using he endpoin s o he
high concen a ion a ea.
•De aul case
18
Case Layou Wall in e sec ion poin
T-c ossing
L-c ossing
X-c ossing
I-c ossing
De aul (cen oid)
Table 3: Cases and solu ions.
19
I he wall layou does no co espond o any o he cases desc ibed abo e, he
ep esen a i e wall in e sec ion poin is compu ed as he cen oid o he se o
poin s included in he high concen a ion a ea.
Once he wall in e sec ion poin s ha e been compu ed, he endpoin s o he opology
polylines a e eplaced by he in e sec ion poin s ob ained om he high concen a ion
a eas hey belong o, so ha a comple ely connec ed ep esen a ion o he opology o
he loo plan is ob ained.
9. Resul s
A s andalone Ja a applica ion has been de eloped as a pla o m o es all he algo-
i hms ha ha e been desc ibed [20]. The applica ion is able o load and show a DXF
ile con aining he ec o d awing o a loo plan, and p o ides he use wi h ools o
ix some p ecision ela ed p oblems as desc ibed in Sec ion 3, selec he laye (o laye s)
wi h he walls and openings in o ma ion, choose he alues o he pa ame e s o he
de ec ion algo i hms and show and s o e he esul ing opology ep esen a ion.
The algo i hms ha e been es ed in a compu e wi h a 2.4 GHz In el R
Co eTM2
Quad p ocesso wi h 4 GB o RAM using eal loo plans o buildings o ou uni e si y.
Figu e 13 shows h ee o he loo plans used and he esul o applying he wall de ec ion
algo i hm o hem; he de ec ed walls a e d awn in blue. Al hough he algo i hm has
been only applied o he ep esen a ion o walls, o he laye s a e shown wi h di e en
colo s o gi e a be e unde s anding o he loo plans.
Table 4 shows some nume ical esul s ob ained in ou es s using di e en h eshold
alues ( he esul s appea in he same o de he esul s a e shown in Figu e 13). Fo each
es , he able shows how many s aigh segmen s and ci cula a cs we e used as inpu
o he algo i hm, he alue o he h eshold εused, he amoun o wall and wall-p one
edges in he ini ial gene alized WAG ha link espec i ely segmen s and a cs, he inal
numbe o wall edges a he end o he algo i hm execu ion, he pe cen age o segmen s
and a cs ha do no belong o any wall in he esul , he ime spen o build he ini ial
gene alized WAG and he ime he algo i hm ook o de ec he walls. As can be seen,
1 millisecond is he lowe limi o he execu ion o he wall de ec ion algo i hm. The
inal numbe o wall edges is equal o he sum o he ini ial numbe o wall edges and he
numbe o wall-p one edges; his was he expec ed esul , gi en he way he algo i hm
wo ks.
The ime spen in he cons uc ion o he ini ial WAG is in gene al less han a second
o loo plans wi h no mo e han 1700 segmen s, al hough he complexi y o he d awing
has a signi ican in luence on his ask. Figu e 14 shows he ep esen a ion o he opology
o a po ion o a eal loo plan as ob ained wi h he algo i hms desc ibed in his pape ,
while Figu e 15 shows he opology ep esen a ion on op o he o iginal loo plan.
I is in e es ing o ema k ha using di e en alues o he h eshold εp oduces
signi ican changes in he esul s: he bigge he h eshold, he mo e complex is he
s uc u e o he gene alized WAG, because he numbe o ele an pai s o segmen s
inc eases, and he ime spen o build and p ocess he g aph is he e o e highe . On he
o he hand, he numbe o segmen s and a cs ha a e no conside ed as pa o a wall
pai a he end o he wall de ec ion algo i hm dec eases as he alue o he h eshold
20
Figu e 13: Real loo plans used o es ou algo i hms, oge he wi h he esul s o applying he wall
de ec ion algo i hm. De ec ed walls a e d awn in blue. The laye s con aining windows and doo s a e
shown, bu ha e no been p ocessed
21
TABLE LEGEND
A1-A2. Numbe o segmen s/a cs in he loo plan espec i ely
ε. Th eshold used o o m segmen pai s
B1-B2. Numbe o ini ial wall-p one edges linking segmen s/a cs espec i ely
C1-C2. Numbe o ini ial wall edges linking segmen s/a cs espec i ely
D1-D2. Numbe o inal wall edges linking segmen s/a cs espec i ely
E1-E2. Segmen s/a cs ha do no o m walls espec i ely (%)
F. WAG building ime (milliseconds)
G. WAG p ocessing ime (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: Nume ical da a om he wall de ec ion es s wi h eal loo plans
inc eases. I could be in e es ing o s udy mo e ca e ully his issue in o de o ind a way
o compu e dinamically he op imum alue o he h eshold o each loo plan.
10. Conclusions and u u e wo k
A me hod o ex ac opological in o ma ion om 2D CAD ec o loo plans has
been p esen ed. The p oblem is di ided in o se e al s ages: i s o all, he wall de ec-
ion algo i hm p oduces he basic wall opology; a e ha , he blocks ep esen ing he
openings a e p ocessed in o de o link hei ep esen a ion o he wall opology; inally,
he wall in e sec ions a e compu ed o comple e he opology ep esen a ion o he loo .
The Wall Adjacency G aph (WAG) has been p esen ed as he suppo ing da a s uc-
u e o he wall de ec ion algo i hm. I s o es he opological ela ions amid he segmen s
( ep esen ed as g aph nodes) ha compose he d awing o he wall s uc u e o he loo
plan, using h ee kind o edges: wall, wall-p one and hie a chical edges. An ini ial WAG
is di ec ly buil om he loo plan; hen, he wall de ec ion algo i hm p ocesses he
g aph in linea ime wi h espec o he numbe o wall-p one edges. The opological
in o ma ion abou walls is ob ained di ec ly om he inal WAG in an easy way. All his
p ocess ypically akes less han one second using eal loo plans.
In o de o handle app op ia ely some pa icula cases, a gene alizazed, less es ic i e
e sion o he WAG has been p esen ed ha allows a mo e lexible de ec ion p ocess.
22
Figu e 14: Topology ep esen a ion om a po ion o a CAD ec o loo plan
Fu u e wo k include he de ec ion o addi ional elemen s like s ai ligh s, he use o
spa ial indices o speed up he WAG building p ocess, he s udy o a way o compu e
he op imum h eshold alue o a gi en loo plan, as well as he inclusion o seman ic
in o ma ion in he same p ocess, so ha he use in e en ion can be minimized. The
long e m goal is o in eg a e he opology de ec ion p ocess in o a comple e sys em o
3D building econs uc ion.
Acknowledgemen s
This wo k has been pa ially suppo ed by he Andalusian Go e nmen , he Spanish
Minis y o Science and Inno a ion and he Eu opean Union ( ia ERDF unds) h ough
he esea ch p ojec s P07-TIC-02773 and TIN2007-67474-C03.
Re e ences
[1] D. B u zman, L. Daly, X3D. Ex ensible 3D g aphics o web au ho s, Mo gan Kau mann, 2007.
[2] R. A naud, M. Ba nes, COLLADA. Sailing he gul o 3D digi al con en c ea ion, A.K. Pe e s,
2006.
[3] A. E. Walsh, M. Bou ges-S´e enie , Co e Web3D, P en ice Hall PTR, Uppe Saddle Ri e , NJ, USA,
ISBN 0-13-085728-9, 2001.
[4] Y. Li, Z. He, 3D Indoo Na iga ion: a F amewo k o Combining BIM wi h 3D GIS, in: 44 h
ISOCARP Cong ess, 2008.
[5] J. Benne , A. Geige , K. Leinemann, Flexible Gene a ion o Seman ic 3D Building Models, in:
P oceedings o he 1s In e na ional Wo kshop on Nex Gene a ion 3D Ci y Models, 2005.
[6] P. M¨ulle , P. Wonka, S. Haegle , A. Ulme , L. Van Gool, P ocedu al modeling o buildings, ACM
T ans. G aph. 25 (3) (2006) 614–623, ISSN 0730-0301.
[7] J. W. Choi, D. Y. Kwon, J. E. Hwang, J. Le lakkhanakul, Real- ime managemen o spa ial in o -
ma ion o design: A space-based loo plan ep esen a ion o buildings, Au oma ion in Cons uc ion
16 (4) (2007) 449–459.
[8] C. Ah-Soon, K. Tomb e, A chi ec u al symbol ecogni ion using a ne wo k o cons ain s, Pa e n
Recogn. Le . 22 (2) (2001) 231–248, ISSN 0167-8655.
[9] P. Dosch, K. Tomb e, C. Ah-Soon, G. a. Masini, A comple e sys em o he analysis o a chi ec u al
d awings, In e na ional Jou nal on Documen Analysis and Recogni ion V3 (2) (2000) 102–116.
23
Figu e 15: Topology ep esen a ion on op o he o iginal CAD ec o loo plan
[10] J. Llad´os, J. L´opez-K ahe, E. Ma ´ı, A sys em o unde s and hand-d awn loo plans using subg aph
isomo phism and Hough ans o m, Mach. Vision Appl. 10 (3) (1997) 150–158, ISSN 0932-8092.
[11] T. Lu, H. Yang, R. Yang, S. Cai, Au oma ic analysis and in eg a ion o a chi ec u al d awings, In .
J. Doc. Anal. Recogni . 9 (1) (2007) 31–47, ISSN 1433-2833.
[12] S. Ho na, D. Mene eaux, G. Damiand, Y. Be and, Consis ency cons ain s and 3D building
econs uc ion, Compu e Aided Design 41 (1) (2009) 13–27.
[13] A. Mas, G. Besuie sky, Au oma ic a chi ec u al 3D model gene a ion wi h sunligh simula ion, in:
Ibe o-Ame ican Symposium on Compu e G aphics, 37–44, 2006.
[14] A. Paoluzzi, F. Milicchio, G. Sco zelli, M. Vicen ino, F om 2D Plans o 3D Building Models o
Secu i y Modeling o C i ical In as uc u es, In e na ional Jou nal o Shape Modeling 14 (1) (2008)
61–78.
[15] B. Medjdoub, B. Yannou, Sepa a ing opology and geome y in space planning, Compu e -Aided
Design 32 (1) (2000) 39 – 61, ISSN 0010-4485.
[16] G. Zhi, S. Lo, Z. Fang, A g aph-based algo i hm o ex ac ing uni s and loops om a chi ec u al
loo plans o a building e acua ion model, Compu e -Aided Design 35 (1) (2003) 1–14.
[17] Na ional CAD S anda d, .4.0, h p://www.na ionalcads anda d.o g, 2008.
[18] ISO 13567: O ganiza ion and naming o laye s o CAD, ISO (In e na ional O ganiza ion o S an-
da diza ion), h p://www.iso.o g, 1998.
[19] N. Da ies, e al., AEC (UK) CAD S anda d o basic laye naming, .2.4, h p://www.aec-uk.o g,
2005.
[20] B. Dom´ınguez, F. Conde, ´
A.L. Ga c´ıa, F. R. Fei o, On he speci ica ion and in e ace design o a
semiau oma ic ool o he de ec ion o seman ic elemen s in a loo plan, Tech. Rep., Depa amen o
de In o m´a ica. Uni e sidad de Ja´en, 2011.
[21] B. Dom´ınguez, A. L. Ga c´ıa, F. R. Fei o, An Open Sou ce App oach o Semiau oma ic 3D Scene
Gene a ion o In e ac i e Indoo Na iga ion En i onmen s, in: P oceedings o IV Ibe o-Ame ican
Symposium on Compu e G aphics, 131–138, 2009.
24
