7/26/2019 Article 170

1/12

Dov Dori

i m e n S i O n i n

A u t o m a t i c

U n d e r s t a n d i n g

o f E n g i n e e r i n g D r a w i n g s

A m a c h i n e d r a w i n g c o n s is t s o f a d e s c r i p t io n o f o n e o r m o r e

p r i n c i p a l o r t h o g o n a l v i e w s ( p r o j e c ti o n s ) o f a n o b j e c t . T h e s e

p r o j e c t i o n s c a n b e u s e d t o r e c o n s t r u c t t h e 3 D s t r u c t u r e o f t h e

o b j e c t i n a v a r i e t y o f w a y s . T h e p r o b l e m o f s o l id r e c o n s t r u c t i o n

f r o m e n g i n e e r i n g d r a w i n g s d e a l s w i t h a s u b c la s s o f t h e c la s s

o f m u l t i v i e w l i n e d r a w i n g s , w h e r e t h e o b j e c t w o r l d i s n o t

r e s t r i c te d t o a f i n i t e s et o f p r o t o t y p e s . T h e i n t e r p r e t a t i o n o f

m u l t i v i e w l i n e d r a w i n g s h a s b e e n i n v e s t i g a t e d q u i t e i n t e n s i v e l y

[ 1, 7 , 8 , 1 2 , 1 3 , 1 4 , 1 5 , 1 6 , 1 8 ]. F o r s p e c i f i c w i r e f r a m e p r o j e c -

t i o n s t h i s i s k n o w n as t h e f l e s h i n g o u t p r o j e c t i o n s p r o b l e m

[ 19 ]. G i g u s a n d M a l i k [8] h a v e d e v e l o p e d a n a l g o r i t h m f o r

c o m p u t i n g t h e a s p e c t g r a p h f o r li n e d r a w i n g s o f p o l y h e d r a l

o b j e c t s . T h e y p r o v i d e s e v e ra l re f e r e n c e s fo r s u r v e y s o f c u r r e n t

a p p r o a c h e s f o r s o lv i n g th e 3 D o b j e c t r e c o g n i t i o n p r o b l e m .

S u g i h a r a [1 8] p r e s e n t s a c o m p u t a t i o n a l m e c h a n i s m f o r t h e

i n t e r p r e t a t io n o f l in e d r a w i n g s b y e n a b l i n g a m a c h i n e t o

r e c o n s t r u c t 3 D o b j e c t s t r u c t u r e s f r o m t h e i r p i c t u r e s d r a w n o n

a 2 D p l a n e . T h e o b j e c t s h e c o n s i d e r s a r e p o l y h e d r a , a n d t h e

l i n e d r a w i n g s a r e s i n g l e - v i e w o b j e c t s b o u n d e d b y p l a n a r f a c e s.

O n e p o t e n t i a l a p p l i c a t i o n s u g g e s t e d b y S u g i h a r a f o r hi s

m e c h a n i s m i s f le x i bl e h u m a n - m a c h i n e c o m m u n i c a t i o n . S i n ce

i t i s t e d i o u s w o r k f o r d e s i g n e r s t o c o n v e r t t h e i r t h o u g h t s i n t o

n u m e r i c a l f o r m s , a l l t h e y w i l l h a v e t o d o is d r a w p i c t u r e s o f

t h e i r d e s i g n e d o b j e c t s a n d g i v e a s m a l l n u m b e r o f a d d i t i o n a l

d a t a , s u c h a s l e n g t h s o f e d g e s a n d a n g l es b e t w e e n f ac e s. T h e

q u e s t i o n o f h o w t h is d a t a i s to b e p r o v i d e d i s n o t d i s c u s s e d .

Th e subclass of l ine drawings w e

are concerned with, mechanical

engineer ing drawings, usual ly con-

sists of top, front and side views.

Various approaches to the recon-

s t ruc t i on p rob l em have been pub-

lished in the l i terature. Broadly,

they can all be viewed as applica-

tions of constraints to various 2D

entities. W esley an d Marko wski [ 19]

have developed an a lgor i thm to

find all solid polyhedral objects

wi th a given se t of two dimen sional

projec t ions. These projec t ions may

conta in depth informat ion in the

form o f dashe d and solid lines, may

represent c ross sec t ions, and may

be overa l l or de ta i led views.

Hara l ick and Queeney [9] apply

constraints to the 2D primitive enti-

t ies, which are the l ines on the 2D

projections. Ald efeld [ 1 starts from

closed loops of l ines and appl ies

rules or const ra ints to them. This

approach, a l though less genera l ,

may frequently be practical . Preiss

[12] also casts the problem into one

of const ra int propag at ion. His con-

trol structure arrives either at a

consistent const ra int ne t or a t a

9 2 October 1992/Vol.35, No.10/COMMUNICATIONS OF THE ACM

7/26/2019 Article 170

2/12

c o n c l u s i o n t h a t t h e r e i s n o c o n s i s -

t e n t n e t , t h u s e n a b l i n g a c e r t a i n v a l -

i d a t i o n o f t h e s e t o f 2 D p r o j e c ti o n s .

T h i s a l g o r i t h m h a n d l e s a l so c yl i n -

d r i c a l f a c e s , w h i c h a r e n o t t r e a t e d

in [19].

A s n o t e d [ 1 9 ], q u i t e a p a r t f r o m

t h e m a t h e m a t i c a l i n t e r e s t o f t h e se

f l e s h i n g o u t p r o j e c ti o n s a l g o -

r i t h m s , t h e y p r o v i d e a b a s i s f o r a u -

t o m a t i c c o n v e r s i o n o f a s e t o f 2 D

p r o j e c t i o n s t y p ic a l ly f o u n d i n m e -

c h a n i c a l e n g i n e e r i n g d r a w i n g s i n t o

s o l id v o l u m e t r i c r e p r e s e n t a t i o n s o f

o b j e c t s . T h e r e i s , h o w e v e r , a m a j o r

p r o b l e m w i t h t h e s e a n d o t h e r s i m i -

l a r a l g o r i t h m s t h a t c u r r e n t l y l i m i t s

t h e i r a p p l i c a b i l i t y . T h e a l g o r i t h m s

a s s u m e t h a t t h e r e e x i s t s a w e l l -

d e f i n e d , n o i s e - f r e e s et o f 2 D p r o -

j e c t i o n s , r e a d i l y a v a i l ab l e t o b e u s e d

a s i n p u t . T h u s t h e y o v e r l o o k th e

p r e s e n c e o f a n n o t a t i o n en t i t i e s in

p r a c t i c a l l y a l l e n g i n e e r i n g d r a w -

i n g s . T h e s e e n t i t i e s a r e a i m e d a t

p r o v i d i n g t h e d r a w i n g r e a d e r w i t h

i n f o r m a t i o n a b o u t t h e o b j e c t w h i c h

c a n n o t b e e x p r e s s e d b y i t s

g e o m e t r y

e n t i t i e s . W h i l e g e o m e t r y l i n e s d e -

s c r i b e c o n t o u r s o f f a c e t s i n t h e o b -

j e c t ' s p r o j e c t i o n s , a n n o t a t i o n a d d s

s u c h i n f o r m a t i o n a s d i m e n s i o n s

a n d t o l e r a n c e s , p r o d u c t i o n s p e c i f i -

c a t i o n s , a d m i n i s t r a t i v e i n s t r u c t i o n s

a n d s o fo r t h . R e c o n s t r u c t i o n a l g o -

r i t h m s p e r c e i v e t h is t y p e o f i n f o r -

m a t i o n a s ' n o is e . ' W h i l e o b t a i n i n g a

' n o i s e - f r e e ' s e t o f p r o j e c t i o n s m a y

b e r e l a t i v e l y e a sy f o r m o d e l s o f o b -

j e c t s w h o s e p r o j e c t i o n s w e r e o r i g i -

n a l ly c re a t e d u s i n g a C A D / C A M

s y s t e m , i t i s f a r f r o m b e i n g t r i v i a l

w h e n t h e s o u r c e is a p a p e r d r a w i n g ,

p r o d u c e d e i t h e r m a n u a l l y o r b y a

c o m p u t e r d r i v e n p l o t t e r . C u r r e n t l y

a v a i l a b l e C A D / C A M s y s t e m s l a c k

t h e a b i l i t y t o a u t o m a t i c a l l y i n c o r p o -

r a t e m a n u a l l y p r e p a r e d m a c h i n e

d r a w i n g s o r p a p e r d r a w i n g s , p l o t -

t e d as o u t p u t s o f o t h e r C A D / C A M

s y s t e m s , i n t o t h e i r d a t a b a s e . A

m a j o r r e a s o n f o r t h i s i s t h a t i t is d if -

f i c u l t t o a c h i e v e a c a p a b i l i t y o f d i s -

t i n g u i s h i n g b e t w e e n , a n d s e p a r a -

t i o n o f , g e o m e t r y a n d a n n o t a t i o n

e n t i t i e s , w h i c h i s b a s i c t o a n y a u t o -

m a t e d s y s t e m a i m e d a t u n d e r s t a n d -

i n g e n g i n e e r i n g d r a w i n g s . A p r e -

p r o c e s s i n g s t e p is r e q u i r e d i n o r d e r

t o s e p a r a t e t h e t w o t y p e s o f e n ti t i e s

a n d t o u se t h e a n n o t a t i o n e n t i t ie s t o

e n h a n c e t h e i n fo r m a t i o n e x p r e s s e d

b y t h e g e o m e t r i c o n e s b e f o r e r e -

m o v i n g t h e m . I t is t h e s c o p e o f a

M a c h i n e D r a w i n g U n d e r s t a n d i n g

S y s t e m ( M D U S ) t o c a r r y o u t t h i s

task [4, 5, 6] .

A l t h o u g h a d r a w i n g u s u a l l y c o n -

s is ts o f s e v e r a l ( n o r m a l l y t h r e e )

v i e w s , t o s i m p l i f y t h e a n a l y s i s w e

r e s t r i c t t h e d i s c u s s i o n t o 2 D o b j e c t s

( o b j e c t s t h a t h a v e c o n s t a n t w i d t h ) ,

f o r w h i c h a d r a w i n g t h a t c o n s i s ts o f

o n e v i e w is s u f f i c i e n t . T h e v i e w t h u s

c o n s t i t u t e s t h e t o p o f a t h r e e - l e v e l

h i e r a r c h y . T h e m i d d l e l ev e l is o c c u -

p i e d b y d i m e n s i o n - s e t s , w h i l e th e i r

c o m p o n e n t s a r e a t t h e b o t t o m o f

t h e h i e r a r c h y . T h e r e l a t i o n s h i p s

b e t w e e n t h e b o t t o m a n d m i d d l e

l e v e l s h a v e b e e n s t u d i e d i n [ 3 , 6 ] .

T h i s w o r k i s c o n c e r n e d w i t h t h e

r e l a t i o n s h i p b e t w e e n t h e m i d d l e

a n d t h e t o p l e v e l s ( i . e . , h o w d i m e n -

s i on - s et s a r e a r r a n g e d s o as t o m e e t

t h e d e m a n d s o f d r a f ti n g s t a n -

d a r d s ) .

P r o b l e m s w i t h p r o d u c t i n f o r m a -

t i o n e x c h a n g e a r e b y n o m e a n s l i m -

i te d t o t r a n s f e r o f i n f o r m a t i o n f r o m

m a n u a l l y p r e p a r e d d r a w i n g s t o i n -

t e r a c t i v e g r a p h i c C A D / C A M s y s -

t em s . E x c h a n g e o f i n f o rm a t i o n

a m o n g v a r i o u s t y p e s o f s u c h s ys -

t e m s h a s b e e n a d d r e s s e d b y m a n y

r e s e a r c h e r s a n d s t a n d a r d s o r g a n i -

z a t i o n s . T h e I n i t i a l G r a p h i c s Ex -

c h a n g e S p e c i f i c a t i o n ( I G ES ) [ 1 7 ] i s

a w i d e l y a c c e p t e d n e u t r a l f i l e f o r -

m a t t h a t e s t a b l i s h e s i n f o r m a t i o n

s t r u c t u r e s t o b e u s e d f o r t h e d i g i t al

r e p r e s e n t a ti o n a n d c o m m u n i c a t i o n

o f p r o d u c t d e f i n i t i o n d a t a u s e d b y

v a r i o u s C A D / C A M s y s t e m s . I n i t i -

a t e d i n la t e 1 9 7 9 , I G ES i s a m a t u r e

m e c h a n i s m t h a t p r o v i d e s a s t a b l e ,

s t a n d a r d i z e d , v e n d o r i n d e p e n d e n t

f o r m a t t o a i d i n t h e m a n a g e m e n t

a n d u s e o f d a ta f r o m C A D / C A M

s y s t e m s .

Ge o m e t ry , An n o t a t i o n , a n d

Dimensioning

D i m e n s i o n i n g c o n s t i t u t e s t h e c o r e

o f a n n o t a t i o n e n t it ie s . A d o p t i n g

I G E S c o n v e n t i o n , th e f u n d a m e n t a l

u n i t o f i n f o r m a t i o n is th e enti ty . T h e

D R A W I N G e n t it y (I G E S n o . 4 0 4 )

s p e c i f ie s a d r a w i n g a s a c o l l e c t i o n

o f a n n o t a t i o n e n t it i es a n d v i ew s

w h i c h , t o g e t h e r , c o n s t i t u t e a s i n g l e

r e p r e s e n t a t i o n o f a p a r t , i n t h e

s e n s e t h a t a n e n g i n e e r i n g d r a w i n g

c o n s t i t u t e s a s i n g l e r e p r e s e n t a t i o n

o f a p a r t i n s t a n d a r d d r a f t i n g p r a c -

t i ce [17] . I t a llows a se t o f v iews to

b e id e n t if i e d a n d a r r a n g e d f o r

h u m a n p r e s en t at io n . T h e V I E W

e n t i t y ( I G E S n o . 4 1 0 ) p r o v i d e s

c h a r a c t e r i s t i c s a s s o c i a t e d w i t h i n d i -

v idua l v iews .

D i m e n s i o n i n g i n e n g i n e e r i n g

d r a w i n g s p r o v i d e s a n e x a c t d e f i n i -

t io n o f t h e g e o m e t r y a p p r o x i m a t e d

b y t h e g e o m e t r y e n t i t i e s . T h e r e -

f o r e , r e c o g n i t i o n o f d i m e n s i o n s i s a

k e y c o m p o n e n t o f M D U S . T h i s a s -

s e r t i o n i s s u p p o r t e d b y t h e f a c t t h a t

o f t h e 1 5 a n n o t a t i o n e n t it ie s h a n -

d l e d b y I G E S , 1 0 a r e a s s o c i a t e d

w i t h d i m e n s i o n i n g . A s n o t e d i n

[ 1 0 ] , a n n o t a t i o n i n g e n e r a l , a n d

d i m e n s i o n i n g i n p a r t i c u l a r , i s a n

e x t r e m e l y t e d i o u s a r e a o f d a t a e x -

c h a n g e . T h e m a i n d i f f i c u l t y i s t h a t

g e o m e t r y a n d a n n o t a t i o n e n t i ti e s

l o o k e s s e n t i a l l y t h e s a m e , a s d e m -

o n s t r a t e d i n F i g u r e 1 , w h i c h i s a

v i ew o f a t y p i c al e n g i n e e r i n g d r a w -

i n g a n n o t a t e d u s i n g I S O s t a n d a r d .

B o t h g e o m e t r y a n d a n n o t a t i o n u s e

t h e s a m e b a s i c p r i m i t i v e s : t h e b a r

( s t r a i g h t l i n e s e g m e n t ) a n d t h e a r e .

E v e n t h e w i d t h s o f t h es e p r i m i t i v es

i n t h e t w o e n t i t y t y p e s a r e f r e -

q u e n t l y t h e s a m e . M o r e o v e r , t h e s e

t w o t y p e s o f e n t it i e s a r e u s u a l l y i n -

t e rl e a v ed i n a m a n n e r t h a t m a k e s

t h e t a s k o f s e p a r a t i n g t h e m e v e n

m o r e d i ff i c ul t . U n d e r s u c h c i r c u m -

s t a n c e s , p a t t e r n c l a s s i f i c a t i o n b a s e d

o n a n y f e a t u r e s p a c e i s p r a c t i c a l l y

i m p o s s ib l e . I t c a n o n l y b e u s e d , a n d

i n d e e d i s u s e d [ 5 ] , t o d e t e c t t h e t w o

o b j e c t - d i s s i m i l a r e n t i t i e s a r r o w h e a d

a n d

text.

T h e s e s e r v e a s a n c h o r s

t h a t e n a b l e t h e i n i t i a t i o n o f p a r s i n g .

A d i m e n s i o n - s e t is a s et o f e n ti -

t ie s t h a t d e n o t e t h e m e a s u r e ( l e n g t h

o r a n g l e ) b e t w e e n t w o g e o m e t r y

e n t i ti e s . A s e t o f d i m e n s i o n - s e t s i s

u s e d t o a c c u r a t e l y a n d c o m p l e t e l y

d e f i n e t h e g e o m e t r y o f t h e v ie w . A

t y p e o f a d i m e n s i o n - s e t d e f i n e s i ts

C O M M U N I C A T I O N S O F T H E

ACM/October 1992/Vo1.35, No.|0

93

7/26/2019 Article 170

3/12

I ~ ~ 2 0

I

I

L

L

k

0 _ i 6

I t o

- I I -

t y p e n a m e

l i n e a r

a n g u l a r

d i a m e t e r

o r d i n a t e

r a d i u s

p o i n t

s y m b o l

L

A

D

0

R

P

f u n c t i o n

( IGE S e n t i t y n o . )

Distance between

two geometry

entities (216)

Angle between

two lines or

planes (202)

Diameter of a

top-viewed body

of

r ev o l u t i on

(206 )

Distance from

datum line to

reference line

(218)

R ad i us o f a

c i r cl e o r an a rc

(222 )

G e n e r a l n o t e

re fer r ing to a

specified p o i n t

( 220 )

e x a m p l e

L 2 .75

[- ,--

-7___

0 are mu-

tually exclusive by definition.

Hence, at least one of either p or k

must be 0 at any iteration.

The number of normalons m

pushed onto s ta ck at any single iter-

at ion is m=p + 1- k. Figure 5

demonstrate s a situation where p =

2 and k = 0, such that m = 3. The

right hand side of Figure 5 shows

the 3 normalons that were pushe d

onto

s ta ck

after one iteration. The

rectangle added to

re c ta n g l e - l i s t

is

shaded.

9 6

October 1992/Vol.35,

No.10/COMMUNICATIONSOF TffE ACM

7/26/2019 Article 170

6/12

Let n i be the total numb er of hor-

izontal bars in all the normalons in

the stack at the end of iteration i,

and let

A ni = n i - 1 - n i ,

i.e. the dif-

ference between the number of

horizontal bars in the previous and

the current iteration. We show that

A ni E

{0, 1, 2} as follows:

A n i = 2

i f k= 1 (and hen cep =

0) because a rectangle disappears

from

stack

but no new normalon is

pushed onto

stack,

causing a net

decrease of 2 horizontal bars.

A n i

= 1 if p = k = 0, that is, whe n

one normaion is pushed onto stack.

The sweeping horizontal bar H

merges with the first horizontal bar

it meets, reducing

n i

by 1.

A n i = O i f p - - > 1 (and hencek=

0) because p + 1 horizontal bars

disappear: the one being swept, H,

and the p which 'floated' along H

when H coincided with these p hori-

zontal bars. But at the same itera-

tion p + 1 new horizonta l bars were

also created, each becoming the

topmost bar of one of the p + 1 new

normalons pushed onto stack.

For each iteration in which

A n i =

0 (called A n i = 0 type iteration ),

there is exactly one

A n i

---- 2 type it-

eration, because each new nor-

malon pushed onto

stack

eventually

becomes a rectangle and then dis-

appears in the iteration that follows

next. Therefor e, each iteration, ex-

cept for the very last one, eliminates

on the average exactly one horizon-

tal bar. Th e last iterati on eliminates

the two horizontal bars of the rec-

tangle which is part of the original

normalon and hence did not re-

quire a

A ni

-- 0 type iteration to be

pushed onto

stack.

Thus, if the orig-

inal nor ma lon has r horizontal bars,

then exactly r- 1 iterations are

required to complete its tessellation

into rectangles. Since each iter ation

adds exactly one rectangle to rec-

tangle-list,

the normalon is tessel-

lated into r - 1 rectang les.

THEOREM 2. ( E qu a l it y o f nu mb e r o f

hor i z on ta l an d v er ti c a l b ar - s e t s ): T he

nu m b er o f hor iz on ta l b ar-s e t s o f a nor-

ma l on i s eq u a l t o t he nu m b er o f it s ver t i-

cal bar-sets.

P r o o f :

We show that in each itera-

tion the number of horizontal and

vertical bars that are eliminated is

equal.

A n i - - 2

type iteration involves

the disappearance of a rectangle

from

stack,

causing a net decrease of

two vertical bars alon g with the two

horizontal ones.

A n i - -

1 type iteration, in which

one horizontal bar disappears, in-

volves sliding the edge of a horizo n-

tal bar al ong a vertical bar V until it

coincides for the first time with an

edge of another horizontal bar, at

which point V disappears because

its length is 0. Thus, if one ho rizon-

tal bar di sappear s in an iteration, so

does one vertical bar.

A ni = 0 type iteration, in which

no horizontal bar disappears, in-

volves sweeping a horiz ontal ba r H

parallel to itself until it coincides for

the first time with another horizon-

tal bar H' such that none of the

edges of H coincide with any edge

of H', so no vertical bar is elimi-

nated either.

Since in each iteration the num-

ber of horizontal and vertical bars

that are e limina ted is equal, and the

last iteration leaves us with zero

bars of both kinds, the number of

vertical bars in the original nor-

malon must be r, the number of

horizontal bars.

r is called the

r a n k

of the nor-

malon. Nr denotes a normalon of

rank r. Thus, N2 is a recta ngle --th e

simplest normalon and the only one

which is not concave. N3 may be

considered one of three possible

rectangles that unde rwen t an incre-

mental sweep. The total numb er of

sides in a no rm al on ArT is 2r. As

shown in Figure 4, the notational

conv enti on is that H] is the top most

horizontal side, V1 is the adjacent

(vertical) side in the clockwise direc-

tion, an d it is followed by H 2, g 2,

H3 V3 . . . Hr Vr.

All the dime nsion-se ts of a nor-

malon are of longitud inal type. A

dimension-set of a norm alon is

called horizontal (or vertical) if it

describes the distance between two

horizontal (or two vertical) sides.

Note that the leaders of a horizon-

tal dimension-set are vertical and

vice versa. Figure 6 illustrates one

of the many possible ISO-standard

based prop er dimension ings of the

normalon of Figure 4. Note that

both completeness and nonredun-

dancy are concurrently maintaine d;

the position of each bar is defined

with respect to all the others, while

at the same time ther e is exactly one

way to calculate this position.

Dimensioning Graphs

Since the terms 'horizontal ' and

'vertical' for the two bar-sets H a nd

V are int ercha ngeab le, we shall

henceforth refer to the horizontal

bar-set only, with the understand-

ing that everything defined and

proved for H is applicable to V just

as well. Adopting a graph-theoretic

approach, we define for each of the

two bar-sets the following three al-

ternative descriptions of a dimen-

sioning graph. Each description

stresses another aspect of a nor-

malon's dimensioning.

( l ) A s p a t i a l g r a p h d e s c r i p t i o n

Gs(Nr)

of a normalon

N r

is an r nod e

graph in which each bar

H k

in the

bar-set H is a node k spatially lo-

cated in the mid- point of

H k

and

each dimension-set

Dk , l

is an edge

connecting nodes k an d l.

( 2 ) A c o n c e p t u a l g r a p h d e s c r ip -

t i o n Gc(Nr)

of a norm alon Nr is an r

node g raph in which each bar H k in

the bar-set H is a node k and each

dimension-set Dk , t is an edge con-

necti ng nodes k and I. A concept ual

graph is thus a spatial graph in

which the requirement for spatial

location of nodes has been relaxed.

( 3 ) A p r o j e c t e d g r a p h d e s c r i p t i o n

Gp(Nr)

of a no rmalo n Nr is an r node

graph in which each bar

H k

in the

bar-set H is a node k repr ese nted by

a dashe d line colinear with Hk, and

each dimen sion- set Dk.l is an edge

connecting nodes k and l and per-

pendicula r to both. A projected

graph may be considered as a pro-

jection of the co rresp onding spatial

graph in the horizontal direction,

but since a total projection would

yield jus t a s traight line along which

the nodes are represented by

C O M M U N I C A T I O N S O F TH E ACM/Oc tobe r 1992 /Vo l .35 , No .10 97

7/26/2019 Article 170

7/12

F i g u r e 6 . O n e p o ss ib l e p r o p e r d i m e n s i o n i n g o f t h e n o r m a l o n o f

Figur e 4.

HI

Hs

H2

Hs

tD

tO

H8

H6

H1

O'

H71

H2

Ha

Hs

H4

points, the proj ection is only partial

so as to allow recognition of indi-

vidual dimension-sets.

G~(Nr), Gc(Nr),

and

Gp(Nr)

are dif-

ferent representations of the same

dimensioning graph of

N r ,

denoted

G( N r) .

To distinguish between hori-

zontal and vertical dimensioning

graphs of Nr they are denoted

Gh(Nr)

and

Gv(Nr) ,

respectively. Fig-

ure 7 shows the spatial, conceptual,

and projected gra ph descriptions of

the horizontal bar-set of the nor-

malon of Figure 6. In the earlier

definition we refer red only to H,

but, as noted, all three definitions

hold for V just as well. Figure 8

shows the same three representa-

tions of

G(NT)

for the vertical bar-

set of the same normalon.

P r o p e r D i m e n s i o n in g o f

N o r m a l o n s

The necessary and sufficien t condi-

tions that a no rma lon should satisfy

in order for it to be properly di-

mensioned are stated in the nor-

malon proper dimensioning theo-

rem. We first prove two lemmas

that are later used in the proof of

the theorem.

LEMMA 1:

Le t Dh ( N r b e t he s e t o f hor i -

zonta l d imension-sets in a nor ma lon Nr.

I f t he normal on i s p rop er l y d imens ioned ,

t hen t he nu mb er o f hor i z on ta l d imen-

sion-sets in Nr is IDh(Nr)l = r - 1.

P r o o f :

By induct ion; for a basis, the

number of horizontal dimension-

sets in a rectangle, for which r = 2,

is

]Dh(N2)I

= 2 - 1 = I. Sup pos e

now that ]Dh(Nr)l = r - 1 for Nr. We

have to prove that

IDh(Nr+I)] = r.

To convert N r into Nr+ 1 we p erf orm

an inc rementa l sweep: one of the

horizontal bars, say Hi , has to be

divided into two bars, Hi and H~',

such that

H i '

remains where

H i

was,

and H is swept in a direction per-

pendicular to Hi . In order for the

new normalon,

N r+] ,

to remain

properly dimensioned, exactly one

horizontal dimension-set has to be

added to denote the distance by

F i g u r e 7 . S p a t ia l ( le f t ) , c o n c e p -

t u a l ( b o t t o m ) , a n d p r o j e c t e d

( r ig h t ) h o r i z o n t a l d i m e n s i o n i n g

g r a p h d e s c r i p t io n s o f t h e n o r -

m a l o n o f F i g u r e 6

9 8 October 1992/Vo].35, No.10/COMMUNIGATIONSOF THE ACM

7/26/2019 Article 170

8/12

w h i c h H w a s s w e p t w i th r e s p e c t t o

H i ' ,

s o

IOh(Nr+l) l = ]Oh(Nr)l + 1 = r.

L E M M A 2 :

L e t G ( N r ) b e th e g r a p h o f a

norm al on N r . I f N r i s p rop er ly d im en-

s ioned, then Gc(NT) is connected.

P r o o f :

B y c o n t r a d i c t i o n ; s u p p o s e

Gc(Nr)

i s d i s c o n n e c t e d , t h e n i t c o n -

t a i n s a t l e a s t t w o n o d e s k a n d l , b e -

t w e e n w h i c h t h e r e i s n o p a t h . T h i s

i m p l i e s t h a t t h e r e i s n o w a y t o c o m -

p u t e t h e d i s t a n c e b e t w e e n

H k

a n d

H t

i n N r , b u t s i n c e N r is p r o p e r l y

d i m e n s i o n e d w e g e t a c o n t r a d i c -

t i o n .

T H E O R E M 3 .

( N o r m a l o n P r o p e r

D i m e n s i o n i n g T h e o r e m ) : Le t N ~ b e

a d imens ioned normal on or o rder r , l e t

Gh( N O an d G v (N r) b e it s hor i z on ta l an d

vert ical dim ensi on ing graphs, respec-

t ively . L et H(Dk,~) = { H~ Ht} be the set

o f two hor i z on ta l b ars , Hk a nd Ht , b e -

tw een w hich a d imension-set D~,t exis ts ,

an d let V(Dk,t) = {Vk, Vz} be the an alo-

go us set of two vert ical bar s . N~ is prop -

er l y d imens ioned i f an d on l y i f t he f o l -

l owing two c ond i t i ons ho l d :

( 1 ) B o th Gh( N r) and Gc ( N r) a re

t r e e s ,

a n d

(2 ) 6 H (D k, l ) = H an d

k , l = 1

k # l

V ( D k , l ) = V ,

k , l = 1

k # l

i . e ., t he u n io n o f a l l p a i rs o f hor iz on ta l

an d v er t i ca l b ars b e tween wh ic h an ex -

pl ic i t d imension exis ts is the ent ire hori-

zontal and vert ical bar-set , respect ively .

P r o o f :

D u e t o t h e s y m m e t r y o f H

a n d V w e r e f e r o n l y t o H . F o r e a c h

o f t h e t w o c o n d i t i o n s s t a t e d i n t h e

t h e o r e m w e n e e d t o p r o v e t w o

t h i n g s . F i r s t, g iv e n t h a t t h e d i m e n -

s i o n i n g i s p r o p e r , w e h a v e t o s h o w

t h a t t h e c o n d i t i o n i s m e t . S e c o n d , i f

c o n d i t i o n ( 1) is m e t , t h e n w e s h o w

t h a t t h e d i m e n s i o n i n g i s n o n r e d u n -

d a n t ( i .e ., n o t o v e r d e t e r m i n e d ) , a n d

i f c o n d i t i o n ( 2) i s m e t , t h e n w e s h o w

t h a t t h e d i m e n s i o n i n g i s c o m p l e t e

( i. e. , n o t u n d e r d e t e r m i n e d ) . T h e

c o e x i s t e n c e o f th e s e t w o p r o p e r t i e s

i m p l i e s t h a t t h e d i m e n s i o n i n g i s

p r o p e r b y d e f i n it i o n .

T o p r o v e t h e f i r st p a r t o f t h e

i I

2 .6 i '

[ q b; i

i ~ ' , 5 . 8

i 1.2

= : 1.5 '

i : = 0 . 8 [

" [ i

i

t

l

D ~

Vl

V5 V 7

V3 ~

F i g u r e 8 . S p a t i a l

( u p l e f t) , c o n c e p t u a l ( r i g h t ) ,

a n d p r o j e c t e d

v e r t i c a l

d i m e n s i o n i n g g r a p h s o f t h e n o r m a l o n o f F i g u r e 6

t w o - w a y s t a t e m e n t f o r c o n d i t i o n

( 1 ), w e a s s u m e t h a t t h e n o r m a l o n i s

p r o p e r l y d i m e n s i o n e d a n d n e e d t o

p r o v e t h a t th e d i m e n s i o n i n g g r a p h

i s a t r e e . W e n o t e t h a t a g r a p h i s a

t r e e i f a n d o n l y i f i t sa t i s f ie s t h e f o l -

l o w i n g t w o r e q u i r e m e n t s : ( a) i f n

a n d e a r e t h e n u m b e r s o f it s n o d e s

a n d e d g e s , r e s p e c t i v e l y , t h e n e =

n - 1 , a n d ( b) t h e g r a p h is c o n -

n e c t e d .

L e t N r be a p r o p e r l y d i m e n -

s i o n e d n o r m a l o n . I n Gh(Nr) t h e

n o d e s a r e t h e r h o r i z o n t a l b a r s o f

t h e b a r - s e t H , a n d t h e e d g e s a r e t h e

d i m e n s i o n - s e t s c o n n e c t i n g s e l e c t e d

p a i rs o f e l e m e n t s o f H . B y

L e m m a 1 ,

IDh(Nr)l

= r - 1 , w h i c h

s a ti s fi e s r e q u i r e m e n t ( a) a b o v e , a n d

b y L e m m a 2 ,

Gh(Nr)

i s c o n n e c t e d ,

w h i c h s a t i sf i es r e q u i r e m e n t ( b)

a b o v e . T h u s N ~ i s a t r e e .

W e n o w p r o v e t h e s e c o n d p a r t o f

t h i s tw o - w a y s t a t e m e n t f o r c o n d i -

t i o n ( 1 ) . S i n c e t h e a s s u m p t i o n i s

t h a t t h e d i m e n s i o n i n g g r a p h i s a

t r e e , i t h a s n o c y c l e s, so t h e d i s t a n c e

b e t w e e n a n y t w o b a r s c a n b e c a l c u -

l a t e d b y o n e w a y a t t h e m o s t , w h i c h

i s f o l l o w i n g t h e o n l y p a t h b e t w e e n

t h e t w o n o d e s i n t h e t r e e r e p r e s e n t -

i n g t h e t w o b a r s b e t w e e n w h i c h t h e

d i s t a n c e i s s o u g h t . T h i s s a t i s f i e s t h e

n o n r e d u n d a n c y r e q u i r e m e n t o f

p r o p e r d i m e n s i o n i n g .

T o p r o v e t h e f i r st p a r t o f c o n d i -

t i o n ( 2) , w e a s s u m e t h a t t h e d i m e n -

s i o n i n g is p r o p e r a n d w e n e e d t o

s h o w t h a t

Vp 3 { H p E H ) / %

( / - / p

6 n(Dk,l) )}.

k,l= 1

k # l

S i n c e p r o p e r d i m e n s i o n i n g i m -

p l i es c o m p l e t e n e s s , e a c h b a r

I l k

is

r e l a t e d b y a d i m e n s i o n - s e t t o a t

l e a s t o n e o t h e r p a r a l l e l b a r

H i ,

s o

i s H , t h e s e t o f a l l t h e h o r i -

k , l = 1

k # l

z o n t a l b a r s .

F o r t h e s e c o n d p a r t o f c o n d i t i o n

( 2 ) , w e a r e g i v e n t h a t

H(Dk,l) = H,

k,l= 1

k # l

a n d w e n e e d t o s h o w t h a t t h e d i -

m e n s i o n i n g i s c o m p l e t e . I f i t i s n o t

c o m p l e t e , t h e n t h e r e e x i s t s a t l e as t

o n e b a r H p s u c h t h a t t h e r e i s n o

d i m e n s i o n - s e t b e tw e e n i t a n d a n y

o t h e r b a r p a r a l l e l to i t. T h i s i m p l i e s

COMMUNICATIONSOF THE

A C M / O c t o b e r 1 9 9 2 / V o l. 3 5 , N o. 1 0

99

7/26/2019 Article 170

9/12

O

(Dk, l) ~ H,

k , l = 1

c o n t r a r y t o t h e o r i g i n a l a s s u m p t i o n .

T h i s c o m p l e t e s t h e p r o o f .

T h e n o r m a l o n p r o p e r d i m e n -

s i o n i ng t h e o r e m c a n b e r e p h r a s e d

m o r e c o m p a c t l y as th e f o l l o w i n g

c o r o l l a r y :

A norm alon o f rank r i s d im ens ioned

proper ly i f and only i f each o f i ts hor i-

zonta l and ver t ica l d im en s ion ing graphs

is an r node t r ee .

T h e r e q u i r e m e n t t h a t t h e g r a p h

b e a t r e e t a k e s c a r e o f t h e

n o n r e d u n -

dancy

o f t h e d i m e n s i o n i n g , w h i le

= 2 .6

L

6

~ t

Y

1.2

5 . 8

I

I

1 0 8 t

1.5

, p .

P I

f

Ho

H a

3.5

Hs

F i g u r e | . I m p r o p e r d i m e n s i o n -

i n g o f t h e n o r m a l o n o f F i g u r e 4

F i g u r e 1 0 . S p a t i a l (l e f t) a n d con-

cep tua l d i m e n s i o n i n g g r a p h s of

t h e n o r m a l o n o f F i g u r e

9.

F i g u r e 1 1 . A n o t h e r p o s s i b l e

u n d e r d i m e n s i o n e d n o r m a l o n

H2

~ .~)-

~ , ' ,,'~oJ ] _ H 3

I ~ . ; , , 4 . , , ~ i

I .. & - : $

- /

H s

t h e r e q u i r e m e n t t h a t t h e t r e e h a s

e x a c t l y r n o d e s g u a r a n t e e s t h e d i -

m e n s i o n i n g ' s

completeness.

A p p l i c a t io n s o f t h e T h e o r e m

T h e p r o p e r d i m e n s i o n i n g th e o r e m

p r o v i d e s a s o u n d t h e o r e t i c a l b a si s

f o r a v a r i e t y o f o p e r a t i o n s i n t h e

v i e w - le v e l a n a l y s is p h a s e o f e n g i -

n e e r i n g d r a w i n g u n d e r s t a n d i n g .

(1 )

Annota t ion r em oval as a preproc-

essing stage fo r 3 D reconstruct ion.

B y

c o n s t r u c t i n g t h e 2 D g r a p h s

Gh(Nr)

a n d

Gv(Nr)

o f a n o r m a l o n

N ,

i t i s

p o s s i b l e t o d e t e r m i n e i f t h e s e t D =

H U V o f d i m e n s i o n - s e t s d e t e c t e d

b y t h e s y n t a c t i c p h a s e o f M D U S i s

b o t h c o m p l e te a n d n o n r e d u n d a n t .

T o p e r f o r m t h i s w e f i r st v e r i f y t h a t

I I- II = I v l = r - 1 ,

t h a t i s, t h e n u m b e r o f e a c h o f t h e

h o r i z o n t a l a n d v e r t i c a l d e t e c t e d

d i m e n s i o n - s e t s is r - 1 . I f s o - - e a c h

o f t h e t w o s e t s H a n d V o f r - 1 d i -

m e n s i o n - s e t s i s c h e c k e d a s t o

w h e t h e r o r n o t b o t h

Gh(Nr)

a n d

Gv(Nr)

a r e t r e e s .

F i g u r e 9 i s a n e x a m p l e o f a n

i m p r o p e r d i m e n s i o n i n g o f t h e n o r -

m a l o n o f F i g u r e 4 , i n w h i c h o n l y

t h e f i r s t c o n d i t i o n i s m e t . I n s p i t e o f

the fac t tha t ]H I = IV ] = 8 - 1 = 7 ,

t h e d i m e n s i o n i n g i s i n c o m p l e t e a n d

t h e r e f o r e i m p r o p e r . T h i s i s v e r i fi e d

b y o b s e r v i n g t h a t o n o n e h a n d , o n e

o f t h e t h r e e d i m e n s i o n - s e t s w h o se

v a l u e s a r e 1 . 0 , 2 . 5 , a n d 3 . 5 , i s r e -

d u n d a n t , w h i le o n t h e o t h e r h a n d ,

o n e d i m e n s i o n - s e t i s m i s s i n g , c a u s -

i n g d i s c o n n e c t e d n e s s o f t h e c o r r e -

s p o n d i n g g r a p h . T h u s , e v e n

t h o u g h t h e n u m b e r o f d im e n s i o n -

s e t s i s 7 , a s i t s h o u l d b e , t h e c o r r e -

s p o n d i n g d i m e n s i o n i n g g r a p h i n

F i g u r e 1 0 i s d i s c o n n e c t e d - - i t c o n -

s i st s o f o n e t r e e a n d o n e g r a p h

w h i c h h a s a l o o p ( t r i a n g l e ) , r a t h e r

t h a n a t r e e , a n d i s t h e r e f o r e i m -

p r o p e r . F i g u r e 1 1 d e m o n s t r a t e s

t h a t t h e d i m e n s i o n i n g i n F i g u r e 9 is

u n d e r d e t e r m i n e d b y sh o w i ng o n e

m e m b e r o f a n i n f i n i te l y l a r g e f a m -

i ly o f n o r m a l o n s , a l l o f w h i c h a r e

p o s si b le d u e t o t h e i m p r o p e r d i -

m e n s i o n i n g o f t h e n o r m a l o n i n Fi g -

u r e 9 . I f t h e d i m e n s i o n i n g i s

1 0 0

October 1992/Vol.35,

N o . 1 0 / C O M M U N I C A T IO N S O F T H E A C M

7/26/2019 Article 170

10/12

p r o p e r , t h e n s i n c e D = H tO V ,

I I - I I = l V t = r - 1, a n d H f / V = 0 ,

w e ge t ]D [ = IH I + IV l = 2 ( r - 1 ) . I f

a l l t h e a n n o t a t i o n i n t h e d r a w i n g i s

j u s t d i m e n s i o n i n g , t h e n r e m o v i n g

a l l 2 ( r - 1 ) d i m e n s i o n - s e t s i s h i g h l y

l i k el y t o p r o d u c e a c l e a n , n o i s e - f r e e

n o r m a l o n t o b e u s e d a s i n p u t t o a n y

3 D r e c o n s t r u c t i o n a l g o r i t h m .

I f a n o r m a l o n i s f o u n d b y t h e

a u t o m a t i c s y s te m t o b e i m p r o p e r l y

d i m e n s i o n e d , t h e n e i t h e r t h e o r i g i -

n a l d r a w i n g i s i m p r o p e r l y d i m e n -

s i o n e d o r t h e s y n t a c t i c p h a s e o f

M D U S h a s f a i l e d t o e x t r a c t t h e c o r -

r e c t s e t o f d i m e n s i o n - s e t s . S i n c e t h e

s e c o n d p o s s i b i l i t y i s m o r e l i k e l y , t h i s

t e s t s e r v e s a s a g o o d i n d i c a t i o n a s t o

t h e g l o b a l su c c es s o f d i m e n s i o n - s e t

p a r s i n g .

I f th e n u m b e r o f d e t e c te d d i -

m e n s i o n - s e t s i s s m a l l e r b y k t h a n

t h e e x p e c t e d r - 1 , t h e n p r o b a b l y k

d i m e n s i o n - s e t s w e r e o v e r l o o k e d b y

t h e s y s t em , a n d s h o u l d b e s e a r c h e d

u s i n g d i f f e r e n t a p p r o a c h e s , s u c h a s

r e l a x a t io n o f p a r a m e t e r s u s e d t o

d e t e c t a r ro w h e a d s i n th e d r a w i n g

[ 5] . F u r t h e r m o r e , i f k = 1 , t h e n t h e

d i m e n s i o n i n g g r a p h c o n s i s ts o f t w o

d i s c o n n e c t e d c o m p o n e n t s , a n d t h e

s e a r c h c a n b e g u i d e d b y t h e f a c t

t h a t t h e m i s s i n g d i m e n s i o n - s e t

s h o u l d d e n o t e t h e d i s t a n c e b e t w e e n

a b a r in o n e c o m p o n e n t o f t he

g r a p h a n d a b a r i n t h e o t h e r c o m -

p o n e n t .

I f , o n t h e o t h e r h a n d , t h e n u m -

b e r o f d e t e c t e d d i m e n s i o n - s e t s is

g r e a t e r t h a n t h e e x p e c t e d r - 1 b y

k , t h e n p r o b a b l y k d i m e n s i o n - s e t s

h a v e b e e n m i s i d e n ti f i e d a n d s h o u l d

b e e x c l u d e d f r o m t h e s e t. I f t h e r e

a r e k l o o p s in t h e g r a p h , t h e n k d i -

m e n s i o n - s e t s s h o u l d b e d e l e t e d

f r o m t h e g r a p h , o n e f r o m e a c h

l o o p , su c h t h a t t h e g r a p h b e c o m e s a

t r e e . T h e d e c i s i o n a s t o w h i c h d i -

m e n s i o n - s e t s h o u l d b e d e l e t e d i s

b a s e d o n t h e r e l a t i v e l i k e l i h o o d o f

e a c h d i m e n s i o n - s e t t o b e m i s -

d e t e c t e d a n d o n w h e t h e r o r n o t i ts

r e m o v a l c h a n g e s t h e c o n n e c t i v i t y o f

t h e d i m e n s i o n i n g g r a p h .

(2 ) Determine implicit dimensions: A n

i m p l i c i t d i m e n s i o n i s t h e d i s t a n c e

b e t w e e n t w o p a r a l l e l b a r s t h a t a r e

n o t c o m p o n e n t s o f t h e s a m e d i -

m e n s i o n -s e t . A n i m p o r t a n t p r o p -

e r t y o f a t r e e i s t h a t t h e r e e x i s t s e x -

a c t ly o n e p a t h f r o m e a c h n o d e i to

a n y o t h e r n o d e j i n t h e tr e e . T h i s

i m p l i e s t h a t t h e r e i s e x a c t ly o n e w a y

t o c a l c u l a te t h e i m p l i c i t d i m e n s i o n

b e t w e e n a n y p a i r o f e l e m e n t s o f H

w h i c h d o n o t s h a r e a c o m m o n d i -

m e n s i o n - s e t . U s i n g t h e d i m e n s i o n -

i n g t r ee o f a p r o p e r l y d i m e n s i o n e d

n o r m a l o n , i t is p o s si b l e to d e t e r -

m i n e t h e d i s t a n c e d(Hi, Hi) b e t w e e n

a n y t w o h o r i z o n t a l s i d e s Hi a n d Hj

o f t h e n o r m a l o n . T o d o s o w e h a v e

t o f i n d t h e ( u n i q u e ) p a t h i n t h e t r e e

b e t w e e n Hi a n d Hj.

L e t t h e l e n g t h o f t h e p a t h b e k ;

2 -< k - < r - 1 , a n d l e t t h e p a t h p a s s

t h r o u g h

H i = H m o , H m l , H m 2 . . .

H,nk Hj,

w h e r e f o r e a c h p a i r H , , p _ l ,

H mp; 1 < p -< k , the re ex is t s an ex-

p l i c i t d i m e n s i o n - s e t Dmp_~mp,w h o s e

v a l u e i s

d(Hmp_l, Hint,) = Omt,_lm .

T h e

i m p l ic i t d i m e n s i o n b e t w e e n H i a n d

H j i s t h e n :

d(Hi, Hj) = I d H m o ,H m , ) +

d(Hm,,

Hm2)+ . .

+d(Hmk_,, H , . l

= S l D m o n q + 1 2 D m l m 2 +

. +$kOmk_lra~

k

= Z s p l )m p_ l m p

p=l

w h e r e st,, t h e sign s y m b o l i s ,

f

+ 1, i f t h e d i r e c t i o n f r o m

H m - p - 1 t o

Hm-p

i s t h e s a m e a s t h e

d i r e c ti o n f r o m H i t o H j ;

sp = - 1 , i f t h e d i r e c t i o n f r o m

H m - p - 1 t o Hm-p

i s o p p o s i t e t o t h e

d i r e c ti o n f r o m Hi t o Hi.

T h e d e f i n i ti o n o f Sp i s s u c h t h a t

el(Hi, Hi)

i s al w a y s p o s i t i v e , e l i m i n a t -

i n g t h e n e e d f o r a b s o l u t e v a l u e .

T h e d i r e c t i o n i s m o s t e a s il y d e t e r -

m i n e d b y e x a m i n i n g t h e p r o j e c t e d

h o r i z o n t a l t r e e . F o r e x a m p l e , t o

f i n d t h e d i s t a n c e b e t w e e n H 4 a n d

/-/6 i n t h e n o r m a l o n o f F i g u r e 8 ,

u s i n g th e d i m e n s i o n i n g g r a p h w e

f i n d t h a t t h e p a t h i s

(H4, H5, H3,

H 6 ) . T h e r e f o r e , ( m 0 , m b m 2 , m 3 ) =

(4 , 5 , 3 , 6 ) , and

(sbs2, s3)

= ( - 1 , + 1 ,

- 1 ) F o r e x a m p l e , S l = - 1 b e c a u s e

t h e d i r e c t i o n f r o m H 4 t o H 5 i s o p -

p o s it e to t h e d ir e c t i o n f r o m / / 4 t o

H 6 . T h u s ,

D(H4,

H 6 ) =

d(H4,

H 5 ) +

d(H5, H~) +

d(H3, H 6 ) =

3

p = l

(--1)D4,5 + (+ 1)D5,3 +

( - l ) D s , 6 : - 1 . 1 + 3 . 9 - 2 . 1 = 0 .7 .

(3 ) Provide for automatic dimensioning

of normalons:

C A D / C A M s y s t e m s

a r e u s u a l l y n o t e q u i p p e d w i t h a n

i n t e l l i g e n t m e c h a n i s m f o r a u t o -

m a t i c d i m e n s i o n i n g o f d e s i g n e d

o b j e c t s d u e t o t h e v a r i e t y a n d c o m -

p l e x i t y o f i s s u e s th a t n e e d t o b e

a d d r e s s e d : e n g i n e e r i n g c o n s i d e r a -

t i o n s , t o l e r a n c e a c c u m u l a t i o n , a n d

p h y s i c a l l o c a t i o n .

T h e p r o p e r d i m e n s i o n i n g th e o -

r e m c a l l s f o r a s e a r c h f o r t w o o r -

t h o g o n a l s p a n n i n g t r e e s , o n e f o r

t h e h o r i z o n t a l b a r - s e t a n d o n e f o r

t h e v e r t i c a l b a r - s e t , w h i l e t a k i n g

i n t o a c c o u n t t h e e f f e c t s o f t h e f o l -

l o w i n g p o i n t s .

E n g i n e e r i n g c o n s i d e r a t io n s :

F r e q u e n t l y , t h e h u m a n d e s i g n e r

h a s in m i n d r e q u i r e m e n t s a s t o

w h i c h d i m e n s i o n s s h o u l d b e e x p l i c -

i tl y d i m e n s i o n e d . T h e s e p r e f e r -

e n c e s a r e i n f l u e n c e d b y t h e f o l lo w -

i n g t w o f a c t o r s :

1)

Functionality:

T h e i m p o r t a n c e o f

t h e a c c u r a c y o f d i s t a n c e b e t w e e n

t w o g e o m e t r y e n t i t i e s o f t h e o b j e c t

t o t h e p r o p e r o p e r a t i o n o f th e

p r o d u c t , o f w h i c h t h e o b j e c t is a

p a r t .

2 )

Measurability:

T h e a b i l it y t o c a r r y

o u t d i r e c t q u a l i ty a s s u r a n c e m e a -

s u r e m e n t s o f t h e e x p li c i t d i m e n -

s i o n. T h e d e s i g n e r u s u a l l y a s s ig n s a

v a l u e f o r g e n e r a l ( d e f a u l t ) t o l e r -

a n c e d e m a n d w h i c h t h e m a n u f a c -

t u r e d p a r t h a s t o m e e t i n o r d e r t o

f u n c t i o n , u s u a l l y a s a p a r t o f a n a s -

s e m b l y . I n m a n y i n s t a n c e s , t h e

c h o i c e o f a p a r t i c u l a r d i s t a n c e t o b e

e x p l i c i tl y d i m e n s i o n e d i s a c c o m p a -

n i e d b y a d e m a n d f o r t o le r a n c e

w h i c h i s m o r e t i g h t t h a n t h e g e n -

e r a l t o l e r a n c e .

F r e q u e n t l y , t h e o r i g i n a l d i m e n -

s i o n i n g a s s i g n e d b y t h e d e s i g n e r i s

COMMUNICATIONSOF THE

ACM /October 19921Vol.35, No.10

101

7/26/2019 Article 170

11/12

a l t er e d o n c e b y t h e m a n u f a c t u r i n g

e n g i n e e r f o r p r o d u c i b i l i ty a n d y e t

a n o t h e r t i m e b y th e q u a l i t y a s su r -

a n c e e n g i n e e r t o e n a b l e q u a l i t y

c h e c k s . T h e u n d e s i r e d c u m u l a t i v e

e f f ec t o f t h e se r e d i m e n s i o n i n g o p -

e r a t i o n s i s t h a t t h e e n d p r o d u c t

m a y d e v i a t e f r o m t h e o r i g i n a l in -

t e n t o f t h e d e s i g n e r. T h e d e c i s i o n s

a s t o w h a t a r e t h e m o s t i m p o r t a n t

d i m e n s i o n s f o r b o t h f u n c t i o n a l i ty

a n d m e a s u r a b i l i t y r e q u i r e a h i g h

l ev e l u n d e r s t a n d i n g o f th e p r o d u c t

a n d i t s m a n u f a c t u r i n g p r o c e s s , a n d

a r e t h e r e f o r e l e f t t o t h e d e s i g n ,

m a n u f a c t u r i n g , a n d t e st i ng p e r s o n -

n e l a t t h i s s t a g e . O n c e t h e s e c r u c i a l

d i m e n s i o n s a r e d e t e r m i n e d ,

t h o u g h , t h e p r o p e r d i m e n s i o n i n g

t h e o r e m c a n b e u ti l iz e d t o a u t o m a t e

t h e r e s t o f th e d i m e n s i o n i n g p r o -

c e s s . I n t e l l i g e n t a u t o m a t i c d i m e n -

s i o n i n g i s d i s c u s s e d i n m o r e d e t a i l

i n [ 4] . T h e p r o b l e m o f r e d i m e n -

s i o n in g c a n b e a p p r o a c h e d b y in -

c o r p o r a t i n g g l o b a l , h i g h - l e v e l p r o -

d u c i b i l i t y a n d m e a s u r a b i l i t y

c o n s i d e r a t i o n s i n t o t h e s y s t e m .

T o l e r a n c e a c c u m u l a t i o n :

A s

n o t e d i n A N S I Y 1 4 . 5 M s t a n d a r d

[ 2 ], t o a v o i d a c c u m u l a t i o n o f d e v i a -

t i o n s f r o m t h e n o m i n a l d i m e n s i o n ,

t h e n u m b e r o f ex p l ic i t d i m e n s i o n s

t h a t h a v e t o b e a d d e d a n d / o r s u b -

t r a c t e d i n o r d e r t o c a l c u l a t e a n y

i m p l i c i t d i m e n s i o n s h o u l d b e m i n i -

m i z e d . I n t e r m s o f t h e d i m e n s i o n -

i n g g r a p h , t h is r e q u i r e m e n t i m p l ie s

t h a t t h e d e p t h o f th e s p a n n i n g t r e e

o f t h e g r a p h , d ~ x , ( i. e. , t h e l e n g t h

o f t h e l o n g e s t p a t h i n t h e t r e e )

s h o u l d b e a s s m a l l a s p o s s i b l e .

I d e a l l y , f o r Nr wit h r -> 3

min(dmo~) = 2 , in wh ich case i t i s

p o s s i b l e t o c a l c u l a t e t h e d i s t a n c e

b e t w e e n a n y t w o b a r s o f a b a r- s e t b y

a d d i n g o n l y tw o n u m b e r s . T h e

s p a n n i n g t r e e i n t h i s c a s e h a s t h e

s h a p e o f a st a r. I n p r a c t i c e , h o w -

e v e r , s u c h a d i m e n s i o n i n g i s f r e -

q u e n t l y i m p o s s i b l e b e c a u s e i t c o n -

t r a d i c t s e n g i n e e r i n g a n d / o r

p h y s i c a l l o c a t i o n c o n s i d e r a t i o n s .

P h y s i c a l l o c a t i o n : T h e l a y o u t o f

d i m e n s i o n - s e t s h a s t o b e d e s i g n e d

s o t h a t t h e y w i l l n o t i n t e r f e r e w i t h

o n e a n o t h e r a n d w i l l e n a b l e t h e

h u m a n d r a w i n g r e a d e r t o d i st in -

g u i s h b et w e e n g e o m e t r y a n d a n n o -

t a t i o n e n t i t i e s . L e a d e r s s h o u l d n o t

c r o s s a n y o t h e r l i n e , b e it g e o m e t r y

o r a n n o t a t i o n , w h i l e p e r p e n d i c u l a r

w i t n es s e s o f d i f f e r e n t d i m e n s i o n -

s e ts m a y c r o s s e a c h o t h e r , a l t h o u g h

s u c h c r o s s i n g s h o u l d b e a v o i d e d a s

m u c h a s p o ss i bl e . A n n o t a t i o n i n s id e

t h e c o n t o u r d r a w n b y t h e g e o m e t r y

e n t i t i e s s h o u l d a l s o b e a v o i d e d a s

m u c h a s p os s ib l e. E v e n i f w e c o n -

s i d e r o n l y n o r m a l o n s t h a t j u s t u s e

d i m e n s i o n - s e t s o f l o n g i t u d i n a l t y p e ,

f o r e a c h p a i r o f b a rs b e t w e e n w h i c h

a d i m e n s i o n - s e t s h o u l d e x i s t , d e c i -

s i o n s h a v e t o b e m a d e a s t o t h e

n u m b e r o f w it n es se s t h a t o u g h t t o

b e u s e d ( z e r o, o n e , o r t w o ; i f o n e -

w h i c h o f t h e t w o ? ) a n d a s t o t h e

k i n d o f d im e n s i o n - s e t t h a t s h o u l d

b e u s e d ( s y m m e t r i c o r a s y m m e t r i c ,

r e g u l a r o r i r r e g u l a r ? [ 3 ] )

D i s c u s s i o n a n d O p e n P r o b l e m s

T h i s a r t i c l e h a s p r e s e n t e d a p r e -

p r o c e s s i n g s t e p w h i c h s h o u l d p r e -

c e d e t h e a p p l i c a t i o n o f a n y 3 D r e -

c o n s t r u c t i o n a l g o r i t h m f r o m a s e t

o f v i ew s p r o v i d e d b y a n y m a n u a l l y

o r a u t o m a t i c a l l y p r e p a r e d e n g i -

n e e r i n g m a c h i n e d r a w i n g . T h i s i s

o n e t a s k o f a M a c h i n e D r a w i n g

U n d e r s t a n d i n g S y s te m ( M D U S ) .

O p e n p r o b l e m s t h a t o u g h t t o b e

c o n s i d e r e d a r e :

M a n a g i n g t h e c o m b i n a t o r i a l

e x p l o s i o n . T h e n u m b e r o f po s si b le

p r o p e r d i m e n s i o n i n g s o f a n o r -

m a l o n Nr , Z ( Nr ) , i s e x t r e m e l y b i g

e v e n f o r n o r m a l o n s o f m o d e s t

o r d e r r , a n d e v e n i f w e i g n o r e t h e

d i f f e r e n t p h y s i c a l p o s i t i o n s o f a

d i m e n s i o n - s e t b e t w e e n t w o g i v e n

b a r s . S i n c e h o r i z o n t a l a n d v e r t i c a l

d i m e n s i o n i n g s a r e i n d e p e n d e n t o f

e a c h o t h e r , i f w e d e n o t e b y S( r) t h e

n u m b e r o f s p a n n i n g t r e e s o f a

g r a p h w i t h r n o d e s , t h e n Z ( N T ) =

(S(r )) 2. T h e s i t u a t i o n g e t s m u c h

m o r e c o m p l e x i f w e c o n s i d e r n o n -

n o r m a l o n s a n d m u l t i p l e v i e w s .

S o m e g o o d h e u r i s t i c s o u g h t t o b e

f o u n d i n o r d e r t o e f f i c i e n t l y r e d u c e

t h e s e a r c h s p a c e a n d s t i l l c o m e u p

w i t h a r e a s o n a b l e , i f n o t o p t i m a l ,

d i m e n s i o n i n g s c h e m e .

G e n e r a l i z a t i o n w i t h i n t h e s i n g l e

2 D v i e w . T h e c la ss o f n o n r e d u n -

d a n t n o r m a l o n s s h o u l d b e a u g -

m e n t e d t o a n y s i n g l e 2 D s h a p e b y

g r a d u a l l y a l l o w i n g f o r r e d u n d a n t

n o r m a l o n s , p r e s e n c e o f b a r s t il t ed

a t a n y a n g l e , a r c s , a n d s p l i n e s . H o w

s h o u l d t h e s e v a r i o u s e l e m e n t s b e

i n c o r p o r a t e d i n t o t h e c u r r e n t d a t a

s t r u c t u r e , i . e . , t h e d i m e n s i o n i n g

g r a p h ?

G e n e r a l i z a t i o n t o m u l t i p l e o r -

t h o g o n a l v i e w s . T h e s i n g l e 2 D v i e w

c o n s i d e r e d i n t h i s r e s e a r c h s h o u l d

b e g e n e r a l i z e d t o m u l t i p l e o r t h o g o -

n a l v i e w s ( u s u a l l y t h r e e i n e n g i -

n e e r i n g d r a w i n g s ) , a x o n o m e t r i c

v i e w s a n d c r o s s s e c t i o n s . T h e c h a l -

l e n g e t o p r o p e r d i m e n s i o n i n g h e r e

i s t h a t t h e s e t o f d i m e n s i o n - s e t s i s

d i s tr i b u te d a m o n g t h e o r t h o g o n a l

v i e w s , c a l l i n g f o r a r e v i s i o n i n t h e

d e f in i t io n o f p r o p e r d i m e n s i o n i n g

o f a s in g l e v ie w a n d i n t h e d e r i v e d

d a t a s t r u c t u r e .

E x p l o i t a t io n o f d i m e n s i o n - s e t

i n f o r m a t i o n . R a t h e r t h a n t r e a t i n g

d i m e n s i o n - s e t s a s n o i s e t h a t n e e d s

t o b e r e m o v e d f r o m t h e d r a w i n g ,

r e c o g n i z e t h e c o n t e n t o f t h e i r t e x t

a n d u s e it t o e n h a n c e t h e a c c u r a c y

o f t h e 2 D v i ew s a n d t h e 3 D m o d e l

d e r i v e d t h e r e o f , t '4

R e f e r e n c e s

1. Aldefeld, B. On automatic recogni-

t ion o f 3D s t ruc tu res f rom 2D rep-

resentations. Comput . Aided Design

15, 2 (1983), 59-64.

2. AN SI Y14.5M.

Dimensioning and

Tolerancing. Amer ican Nat iona l

Standard, Engineering Drawings

and Related Documentat ion Prac-

t ices. Th e A merican Society for

Mechanical Engineers, New York,

1982.

3. Dori, D. A syntactic/geometric ap-

proach to recogni t ion o f d imen-

sions in engineering machine draw-

ings. Comput . Vis ion, Graph. Image

Process. 47

(1989), 271-291.

4. Dori , D. Intel l igent automatic di-

mens ion ing of CAD engineer ing

mach ine drawings. I n Proceedings of

The Internat ional Society or M ini and

Microcomputers Conference on Com-

1 0 2

October 1992/Vo1.35,

No.10/COMMUNICATION OF T H E A C M

7/26/2019 Article 170

12/12

purer Applications in Design, Simula-

tion, and Analysis,

(R en o , Nev . , Feb .

2 2 - 2 4 ) . I S M M / M I M I , A n a h e im ,

C a l i f . : A C TA Pre ss , 1 9 8 9, p p . 1 3 7 -

140.

5 . D o r i , D . S y n t a x e n h a n c e d p a r a m e -

t e r l e a r n i n g f o r r e c o g n i t i o n o f d i -

m e n s i o n s i n e n g i n e e r i n g m a c h i n e

d raw i n g s .

In t . J . Robot ics and Auto-

mation

5, 2 (May 1990).

6 . D o r i , D . a n d P n u e l i , A . T h e g r a m -

m a r o f d i m e n s i o n s i n m a c h i n e

d raw i n g s .

Comput. Vision, Graph.

Image Process . 42

(1 9 8 8 ) , 1 -1 8 .

7 . Fr eem an , H . A n a l y s is o f l in e d raw -

i n g s . In

Digital Processing and Analy-

s is , J .C . S i mo n an d A . R o sen fe l d

E d s . , No o rd h o f f , Ley d en , 1 9 7 7 .

8 . G i g u s , Z . an d Ma l i k , J . C o mp u t i n g

t h e a s p e c t g r a p h f o r l i n e d r a w i n g s

o f p o l y h ed ra l o b j ec t s .

IEEE Trans .

Pat tern Analys is and Machine In te l l .

PA M I-1 2 , 2 (Feb . 1 9 90) , 1 1 3 -1 2 2 .

9 . H a r a l i c k , R . M . a n d Q u e e n e y , D .

U n d e r s t a n d i n g e n g i n e e r i n g d r aw -

ings.

Comput. Graph. Image Process.

20 ,

3 (1 9 8 2 ) , 2 4 2 -2 5 8 .

1 0 . Ke l l y , J .C . , Pa rk s , R .E . an d Say l o rs ,

D . B . C A D C A M - 0 0 5 : A n i n t r o d u c -

t i o n t o t h e d a t a e x c h a n g e p r o c e s s

u s i n g

I G E S .

S A N D I A R e p .

S A N D 8 6 - 2 5 6 4 . U C - 3 2 , 1 9 8 7 .

1 1 . Ki n g , A .K. A n ex p e r t sy s t em fac i l i -

t a te s u n d e r s t a n d i n g t h e p a p e r e n g i -

n e e r i n g d r a w i n g s . I n

Proceedings,

IAS TED In terna t ional Symposium

Expert Sys tems Theory and Their Appl i-

cations

(Lo s A n g e l e s , C a l i f . D ec .

1 9 88 ) , A C TA Pre ss , p p . 1 6 9 -1 7 2 .

1 2 . Pre i s s , K . C o n s t ru c t i n g t h e so l i d

r e p r e s e n t a t i o n f r o m e n g i n e e r i n g

p ro j ec t i o n s .

Comput. Graphics 8, 4

(1 9 8 4 ) , 3 8 1 -3 8 9 .

1 3 . Sh ap i ra , R . A t ech n i q u e fo r t h e re -

co n s t ru c t i o n o f a s t ra i g h t -ed g e ,

w i r e - f r a m e o b j e c t f r o m t w o o r m o r e

cen t ra l p ro j ec t i o n s .

C o mp. G ra ph .

Image Process., 3

(1 9 7 4 ) , 3 1 8 -3 2 6 .

1 4 . Sh ap i ra , R . Th e u se o f o b j ec t s ' f a ce s

i n i n t e rp re t i n g l i n e d raw i n g s ,

1EEE

Tram. Pat tern Analys is and Machine

lntell.

PA MI -6 (1 98 4 ), 7 8 9 - 7 9 8 .

1 5. S h a p i r a , R . M o r e a b o u t p o l y h e d r a - -

i n t e r p r e t a t i o n t h r o u g h c o n s t r u c -

t i o n i n t h e i mag e p l an e .

I E E E Tra m.

Pat tern Analys is and Machine In teU.

P A M I - 7 ( 19 8 5 ), 1 - 1 6 .

1 6. S h a p i ra , R . a n d F r e e m a n , H . T h e

C y c li c O r d e r P r o p e r t y o f V e r t i c es a s

an A i d i n Scen e A n a l y s i s .

Commun.

A C M 2 2

(1 9 7 6 ) , 3 6 8 -3 7 5 .

1 7 . Smi t h , B . an d W e l l i n g t o n , J .

In i t ia l

Graphics Exchange Specification

(IGES) , Vers ion 3 .0 ,

U . S . D e p a r t -

m e n t o f C o m m e r c e , N a t i o n a l I n s ti -

t u ti o n o f S t an d a r ds , N B S I R 8 6 -

3359, Apr. 1986.

1 8 . Su g i h a ra , K .

Machine In terpreta t ion

of L ine Drawings .

T h e M I T P r e s s ,

Cambridge, Mass. , 1986.

1 9 . W es l ey , M.A . an d Mark o w sk i , G .

F l e sh i n g o u t p ro j ec t i o n s .

I B M J .

Res. Develop. 25

6 , (1 9 8 1 ) 9 3 4 -9 5 3 .

C R C a t e g o r i e s a n d S u b j e c t D e s c r i p -

t o r s : 1 . 3 .5 [ C o m p u t e r G r a p h i c s ] : C o m -

p u t a t i o n a l G e o m e t r y a n d O b j e c t M o d -

e l i n g - cu rv e a n d o b j e c t re pre se n ta t io n s,

geometric algorithms;

1.4.5 [ I m a g e P r o -

c e s s i n g ] : R e c o n s t r u c t i o n - - c u r v e a n d

o b j e c t r e p r e s en t a t i o n s , g e o m e t r i c a l g o-

r i t h m s

G e n e r a l T e r m s : D o c u m e n t a t i o n

S t a n d a r d i z a t i o n

A d d i t i o n a l K e y w o r d s a n d P h r a s es :

A n n o t a ti o n , C A D / C A M , d o c u m e n t

a n a l y s i s , d o c u m e n t a t i o n a u t o m a t i o n .

e n g i n e e r i n g d r a w i n g s , g r a p h r e p r e s e n -

t a t i o n , p r o p e r d i m e n s i o n i n g .

A b o u t t h e A u t h o r :

D O V D O R I is a S e n i o r L e c t u r e r o f in -

d u s t r i a l e n g i n e e r i n g a n d m a n a g e m e n t

a t t h e T e c h n i o n , I s r a e l I n s t i t u t e o f

T e c h n o l o g y . H i s c u r r e n t r e s e a r c h i n t e r -

e s t s i n c l u d e i m a g e p r o c e s s i n g , p a t t e r n

r e c o g n i t i o n , i m a g e u n d e r s t a n d i n g , g e o -

m e t r i c m o d e l i n g , a n d o b j e c t - o r i e n t e d

a n a l ys i s. A u t h o r s P r e s e n t A d d r e s s :

F a c u l t y o f I n d u s t r i a l E n g i n e e r i n g a n d

M a n a g e m e n t , T e c h n i o n , I s r a e l I n s t i t u t e

o f T e c h n o l o g y , T e c h n i o n C i ty , H a i f a

3 2 000 , I s rae l ; ema i l : i e rd o r i @t ech

n i o n .b i t n e t .

Permission to copy withou t fee all or part of

this material is granted provided that the

copies are not m ade or d is t r ibuted for d i rect

comm ercia l advantage, the AC M copyright

notice and the t i tle of the publication and its

date appear, and notice is given that copying

is by permission of the Association for

Com puting M achinery. To copy otherwise, or

to republish, requires a fee and/or specific

permission.

@ A CM 0002-0782/92/1000-092 $1.50

T h e G i f t o f L i f e

S i n c e S t. J u d e C h i l d r e n ' s R e s e a r c h H o s p i t a l o p e n e d i n

1 96 2, i t h a s f o r g e d n e w t r e a t m e n t s f o r c h i l d h o o d c a n c e r

a n d h a s h e l p e d s a v e t h o u s a n d s o f c h i l d r e n . B u t t h e b a t t le

h a s j u s t b e g u n . Y o u c a n j o i n

t h e f i g h t . T o f i n d o u t h o w , - ~ E ~ . ~ t ~ C ~ILn~vdW S

~ R F ~ E A R C H H O S P tF A L

c a l l 1 - 8 0 0 - 8 7 7 - 5 8 3 3 . ,~,,,,~.~o,,~ Founder