A Geometric relaxation solver for parametric constraint-based models

A Geome ic Relaxa ion Sol e o Pa ame ic Cons ain -Based Models Lluis Solano Albajes Pe e B une C osa Uni e si a Poli ` ecnica de Ca alunya Depa amen de Llengua ges i Sis emes In o m` a ics Secci´ o d’In o m` a ica G ` a ica A . Diagonal 647 plan a 8 (ETSEIB) 08029 Ba celona. Spain E-mail: [email p o ec ed].es E-mail: [email p o ec ed].es Abs ac In his pape , a new elaxa ion algo i hm o sol ing geome ic cons ain -based models is p oposed. The algo i hm s a s om a cons uc i e symbolic ep esen a ion o objec s (Cons uc i e Pa ame ic Solid Model, CPSM) and p oceeds by i e a i e e- laxa iono he geome iccons ain s. Models ha can be educed o dis ance and angle cons ain scanbehandled. A newalgo i hmbasedon ani e a i eglobalde o ma iono he sys em is p esen ed and discussed, and i s con e genceis p o ed. The pe o mance o hyb id algo i hms in ol ing global de o ma ion and indi idual cons ain elaxa ion is discussed on se e al p ac ical cases. 1 1 In oduc ion The e m CAD is e e ed o he use o compu e s as an aid o he en i e design p ocess, including c ea ion, modi ica ion, and isualiza ion o designed pa s. T adi ional CAD- sys ems ocus a he explici objec being designed. The cons uc ion p ocess and he ela ionships be ween he in ol ed elemen s a e no e lec ed in he inal design. Cons ain -based modeling allows he use o de ine amilies o objec (gene ic objec s) ha can be subsequen ly con e ed in o speci ic objec s by gi ing he alues o he gene ic objec pa ame e s and by sol ing he de ined cons ain s. The design p ocess using CAD-sys ems is in e ac i e: he use speci ies s ep-by-s ep a se- quence o ope a ions ha con e ges owa ds he inal objec . Use in e ac ion ispe o med h ough aG aphical Use In e ace. Modeling ope a ionsandgeome iccons ain s can be chosen by he use in o de o de ine he objec . Wi h he use o geome ic cons ain s i is possible o speci y he o ganiza ion o a design. In his sense i is easy o gene a e design a ia ions using cons ain s [Rol91]. Cons ain -based design is aimed a ep esen ing and cap u ing he designe ’s in end. I allows o design gene ic objec s mo e han explici ones and e en a amily o designs ins ead o a single one. The p oposed cons ain ep esen a ion is based on he Cons uc i e Pa ame ic Solid Model (CPSM) wich is a p ocedu al desc ip ion o he modeling ope a ions sequence and o he geome ic cons ain s pe o med by he use du ing he in e ac i e objec design [SoB93]. The CPSM is he ep esen a ion o a gene ic objec o he whole amily o objec s, and i keeps he inc emen al design p ocess. P e ious de ined models can be ins ancia ed when a design is in p og ess; 2D, 3D and 2D o 3D ope a ions a e suppo ed. The CPSM is an Edi able Rep esen a ion (EREP) sui able o s o age and ansmission, i suppo s bo h gene ic and speci ic designs, and eco ds he concep ual cons uc ion s eps [RBN89] [HoJ93]. Each s a emen ep esen s a modeling ope a ion o a geome ic cons ain , exp essedusingade ini ionlanguage[SoB94a]. Ino de omanageandkeep hegeome ic cons ain s a speci ic s uc u e called he In e nal Model Rep esen a ion is used. In his pape , a new elaxa ion algo i hm o sol ing geome ic cons ain -based models is p oposed. The algo i hm s a s om a cons uc i e symbolic ep esen a ion o he objec s (Cons uc i e Pa ame ic Solid Model, CPSM) and i p oceeds by i e a i e elaxa ion o he geome ic cons ain s. Models ha can be educed o dis ance and angle cons ain s can be handled. A new algo i hm based on an i e a i e global de o ma ion o he sys em is p esen ed and discussed, and i s con e gence is p o ed. The pe o mance o hyb id algo i hms in ol ing global de o ma ion and indi idual cons ain elaxa ion is discussed on se e al p ac ical cases. The pape is s uc u ed as ollows: he nex sec ion p esen s he model ha suppo s he cons ain s ep esen a ion called he In e nal Model Rep esen a ion. A e ha , o he geome ic cons ain s app oaches a e e iewed wi h special emphasis on ene gy me hods. Then he i e a i e global de o ma ion is explained and p o ed. I is also discussed how o ob ain models wi h dis ance cons ain s only om models wi h angle and dis ance 2 cons ain s. Finally, a cons ain sol e is p esen ed based on an i e a i e elaxa ion me hod in ol ing global and indi idual cons ain s. 2 The In e nal Model Rep esen a ion The In e nal Model Rep esen a ion (IMR) is he s uc u e used o manage and ep esen geome ic cons ain s [SoB94b]. In he design p ocess, he use can de ine dimensional cons ain s (dis ances and angles) be ween exis ing geome ic elemen s. The IMR keeps explici cons ain s, implici cons ain s and de aul cons ain s ha can be de ined while he design is in p og ess. Cons ain sa is ac ion uses he in o ma ion s o ed in he IMR. A se o basic geome ic elemen s ha can be used in modeling ope a ions and cons ain s includes 0D elemen s (poin s), 1D elemen s (lines and edges), 2D elemen s (planes, poly- gons and ci cles) and 3D elemen s (polyhed a, e c). All o hem mus be ins an ia ed and hey a e pa ame ically de ined. They ac as p imi i es wi hin he inal cons uc i e pa a- me ic solid model. Modeling ope a ions can ei he keep he dimension o he ope ands ( o ins ance, in he case o boolean se ope a ions be ween 3D elemen s) o inc ease i (like in sweep ope a ions ha ans o m a 2D elemen in o a solid). Modeling ope a ions can be pa ame ic ope a ions, ha is, he esul dependsno only on he ope ands bu also on he alue o a numbe o o mal pa ame e s. As a example, he CPSM desc ip ion o he 2D L-shape polygon in igu e 1-a would be, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ........................................................................................................................ .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . P0 P1 P2P3 P4P5 d Figu e 1: Example o 1D L-shape polygon MODEL L_pol ( loa d ) e u n model_id { P1 := Poin 3D (0., 0., 0.) P2 := Poin 3D (0., 10., 0.) ... ... 3 L_pol.OB1 := Closed_pol ( P1,P2,P3,P4,P5,P6, XY_REF()) Dis _2P (P1,P2,d) Dis _2P (P2,P3,d/2) Dis _2P (P3,P4,d-d/2) Dis _2P (P4,P5,d-d/2) Dis _2P (P5,P6,d/2) Dis _2P (P6,P1,d) Dis _2P (P6,P3,d) Dis _2P (P5,P2,d) Dis _2P (P1,P4,sq (2)*d) RETURN L_pol.OB1 } The polygon is modelled h ough a Closed pol ope a ion ha cons uc s a new polygon on he i s coo dina e plane o he e e ence XY REF(), om a gi en lis o 3D poin s P1..P6, p e iously de ined by he use h ough he use in e ac ion. In he second pa o he CPSM model desc ip ion, a se o cons ain s ha de ine he p ecise shape o he polygon a e lis ed. As an example, Dis 2P(P6,P1,d) indica es ha he dis ance be ween he bo om e ices o he polygon is d. F om a 2D polygon i is possible o gene a e a 3D objec by sweep ope a ion ( igu e 1-b). The nex p ocedu al desc ip ion show he 3D ex uded L-pa : MODEL L_pa ( loa d ) e u n model_id { L_pa .OB1 := Pa al_sweep ( L_polygon (d), 0.5*d ) e u n Mul _sweep (L_pa .OB1) } A pa allel sweep ha ins ancia es he p e ious de ined model o a 2D polygon is used in o de o ob ain he "L" shaped solid. Mo e p ecisely, he In e nal Model Rep esen a ion (IMR) can be de ined as, De ini ion 2.1. The In e nal Model Rep esen a ion is a g aph I = g aph h N C i such ha N is he se o nodes ha ep esen poin s o ec o s o he geome y and C is a se o edges ha ep esen cons ain s be ween nodes(dis ances be ween poin s, angles be ween ec o s). C  N  N Thus, he IMR keeps and manages cons ain s R be ween he exis ing geome ic elemen s G . I P is a poin o ec o o he model, hen 4 8 P 2 G i 9 c 2 R j c ( P ) ) P 2 N A g aph ha ep esen s he exis ing cons ain s be ween a se o elemen s is called con- s ain g aph. I can be seen ha all he modeling ope a ions and cons ain s ha a e possiblein heCPSM[SoB94a]can be ep esen edasdis ances be ween wopoin sandan- gles be ween wo ec o s. Geome ic cons ain s in he CPSM can be he e o e ansla ed in o dis ances and angles in o de o be ep esen ed in he IMR g aph. De ini ion 2.2. A CPSM model wi h n poin s 2D is well-cons ained i he e a e 2 n ; 3 cons ain s and he e doesn’ exis any subg aph G 0 wi h n 0 poin s wi h mo e han 2 n 0 ; 3 cons ain s [Lam70]. I a model is well-cons ained wi h dis ance and angle cons ain s i is always possible o exp ess he angle cons ain s as a unc ion o a se o dis ance cons ain s (sec ion 5). A model whe e he angle cons ain s ha e been con e ed o dis ance cons ain s is called a d- educed model. The IMR keeps he explici cons ain s ha ha e been de ined by he use , he implici cons ain s ha e lec he ela ionships be ween geome ic elemen s, such as a poin ha belongs o a polygon, and he de aul cons ain s which e lec he dimensions o he s a ing design o he p oduc . The sol e deals wi h his kind o cons ain s in a i e a i e way. 3 Geome ic Cons ain Sol e s In he li e a u e he e a e di e en app oaches o sol e geome ic cons ain s. The e a e wo main s a egies: he cons uc i e one and he equa ional one. In he cons uc i e app oach, he cons ain s be ween geome ic elemen s a e sol ed in an o de ha e lec s he cons uc ion p ocess. Cons uc i e me hods a e classi ied in o:  P ocedu al me hods [Rol91a] [Rol91b] [RBN89] [CFV88] [Emm90] [SoB94b]  G aph based me hods [Owe91] [BFHCP93] [FuH93]  Rule based me hods [Ald88] [Sun88] [SoB91c] [VSR92] [JoS97] In heequa ional me hods,cons ain s a e ansla ed in o ase o non-linea simul aneous equa ions. The sys em equa ions is sol ed by using di e en echniques such as:  New on-Raphson [LGL81] [Nel85] [SoB93]  Geome ic i e a ion [Bo 81] [HsB97]  Symbolic algeb aic me hods, as G ¨ obne basis [Buch88] o Wu-Ri [Wen86] me hod  P opaga ion me hods [Su 63] [S S80] 5 In o de o sol e he dis ance cons ain s i is also possible o wo k in e ms o ene gy minimiza ion [WFB87] [KaB90]. In his case, cons ain s a e elaxed in o de o dec ease he ene gy le el using g adien echniques. The main p oblem is ha he sys em can all in local minima (see nex sec ion). 4 Ene gy Minimiza ion Sol e s Ene gy models can be used in cons ain sa is ac ion [WFB87] [KaB90]. In hese ap- p oaches an ene gy con inuous unc ion is associa ed o each cons ain . In his way he modelhas a ce ain ene gy le el due o non sol ed cons ain s. The cons ain sa is ac ion is pe o med by using an op imiza ion which is usually based on he g adien me hod ha calcula es he new posi ions o he poin s in o de o dec ease he ene gy le el o he model. A ze o ene gy s a e means ha he cons ain s ha e been sa is ied. Thus, he ene gy app oaches y o minimize an e o unc ion. Gi en a 2D sys em wi h n poin s and m cons ain s m =2 n ; 3 , i is possible o s a e he ollowing de ini ions: S a eVec o ~ d : i con ains he ac ual alues o hepa ame e s in ol ed wi h he exis ing m cons ain s. dim ( ~ d )= m ~ d = 2 6 4 d 1 . . . d m 3 7 5 whe e d k is a dis ance cons ain be ween i s endnodes P k 1  P k 2  k 1 k 2 2 K ]K = n m = 2 n ; 3 in he plane. Equilib ium Vec o ~ d c : i con ains he a ge alues o he pa ame e s in ol ed wi h he m cons ain s de ined. dim ( ~ d c )= m ~ d c = 2 6 4 d c 1 . . . d c m 3 7 5 Di e ence Vec o ~  : i is he di e ence be ween he s a e ec o ~ d and he equilib ium ec o ~ d c . ~  = ~ d ; ~ d c Each cons ain C i be ween wo poin s P i 1 and P i 2 , has a cons ain ec o ~ F i jk de ined by, ~ F i 12 =  i ~u i =( d i ; d c i ) ~u i whe e ~u i = ~ P i 1 P i 2 = jj ~ P i 1 P i 2 jj 6 The e o e, each cons ain ec o has associa ed an ene gy le el ha can be exp essed as E i = 1 2 jj  i jj 2 = 1 2 jj ~ F i 12 jj 2 The o al ene gy le el o he sys em is gi en by E T = m X j =1 E j E e y cons ain de ined in a model, has an ac ual alue and a equilib ium alue. The euclidean no m o he di e ence ec o ~  is a measu e o he ene gy le el associa ed wi h he se o cons ain s. App oachesbasedonene gymodels indasolu ioninunde -cons ained andwell-cons ained cases. In o e -cons ained cases hese me hods ob ain a solu ion co esponding o a mini- mumene gyle el. Themainp oblema iseswhen hesys emcon e ges oalocalminimum ha is an unwan ed solu ion. In hese cases, [WFB87] p oposes ha he inal solu ion is in e ac i ely decided by he use . I he sys em cons ain alues a e compa ible i can be gua an eed ha he global minimum exis s. 5 The I e a i e Global De o ma ion Sol e This sec ion is es ic ed o 2D sys ems in ol ing only dis ance cons ain s. I is shown ha a geome ic elaxa ion algo i hm can be de i ed such ha he con e gence o one o he solu ions ~ d = ~ d c can be gua an eed. In o he wo ds, he elaxa ion sol e con e ges o a global minimum E T =0 o he ene gy unc ion. Con e gence in he case o 2D sys ems in ol ing dis ance and angle cons ain s will be discussed in he nex sec ion. 5.1 Relaxa ion o o ien ed cons ain s The geome ic elaxa ion algo i hm is based on he ollowing de ini ion o o ien ed con- s ain s: De ini ion 5.1. Fo eachdis ancecons ain d c i de inedbe ween wopoin s P i 1 = F i s P oin ( d i ) and P i 2 = S econdP oin ( d i ) , he o ien ed cons ain is de ined as he 2D ec o R i = P i 2 ; P i 1 d c i i =1 :::m The se o all o ien ed cons ain s will be no ed as R g . The e o e, R g = R 1 ::: R m . Ob iously, he se R g has a o al o 2 m =4 n ; 6 deg ees o eedom. The se o dis ances will be no ed as d g , d g = d 1 :::d m g 7 De ini ion 5.2. The se R I g is he se o n ; 1 o ien ed cons ain s R g = R k 1 ::: R k n ; 1 wi h indexes k 1 :::k n ; 1 such ha he se o model poin s P g = P 1 ::: P n g can be com- pu ed om R I g . (Wi hou loss o gene ali y, i is nex assumed ha P 1 =(0  0) and ( P 2 ; P 1 ) T  (0  1) = 0 ). Lemma 5.1. In awell cons ained 2D model wi h dis ance cons ain s, he cons ain s can always be numbe ed in a way such ha R 1 ::: R n ; 1 g is he se R I g . .. .. ... .. ... .. ... ... .. ... .. .. ... .. ... .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. . ... ............... .. . . . . . . .. . . . . . .. . . . . .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. ... .. .. . . . . .. . . . .. . . . .. .................... ... ... ... ... ... .. ... .... .. ... ... .... ... ..... .... ...... .................... ......... ...... ..... ..... .... .... .... .... .... .... .... .... ... .... .. .. .. ... ... . ... .. .. .. . .. . . .. .. . . .. . .. . . .. . . . .. . . . .. . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. .. .. . .. . .. . . .. . . .. . . .. . . .. . .. . ... .. . ... ... ... ... ...... ..... ...... ....... ....... ........ ......... ........... . ........... ......... .......... .......... ............... ............................ .......................... ................ ............ ....... ........ ..... .... .... .. ... ... ... .. .. .. ... .. . ... . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . .. . . .. . .. . . .. . . .. . . .. . . .. . . .. . . . .. . . . .. . . . .. . . .. . . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . P g 2 n ~ d g 2 n ; 3 R g 4 n ; 6 R I g 2 n ; 2 P 1 =(0  0) P 1 =(0  0) ( P 2 ; P 1 ) T  (0  1) = 0 Figu e 2: Rela ions be ween he di e en space ep esen a ion P oo . Le i s obse e ha a subse o o ien ed cons ain s R 1 ::: R n ; 1 g is a se R I g i e e y poin P k in he model can be eached om P 1 h ough a pa h only in ol ing a cs co esponding o cons ain s in he subse . In his case, e e y elemen o P g can be compu ed as a linea combina ion o elemen s o R I g . O cou se, he lemma is ue o n =2 and m =1 . Le assume ha i is ue o n poin s. In his case, any o he P k k =1 :::n poin s can be eached om P 1 h ough a pa h in ol ing only o ien ed cons ain s in R 1 ::: R n ; 1 g .Fo n +1 , he lemma emains ue p o ided ha he new elemen R n o be added o R I g is a cons ain be ween he new poin P n +1 and any o he p e ious n poin s P 1 ::: P n . This is ob iously always possible. As a conclusion, P g can be compu ed om R I g . On he o he hand, he se s d g and R g can be compu ed om P g a is shown in igu e 2 ( he se su ixes ep esen hei deg ees o eedom). Sol ing he dis ance cons ain s and eaching a solu ion ~ d = ~ d c can be unde s ood as an op imiza ion in he space R I g , which is a subspace o R g . The goal is o ob ain a se o independen o ien ed cons ain s R 1 ::: R n ; 1 g such ha jj R k jj 2 =1 o e e y R k 2 R g . In o he wo ds and de ining 4 k = jj R k jj 2 ; 1= ( d k =d c k ) 2 ; 1 ha can also be exp essed, 4 k = d k d c k 2 ; 1= ( d k + d c k )( d k ; d c k ) ( d c k ) 2 = d k + d c k ( d c k ) 2  k 8 A solu ion ~ d = ~ d c has been eached i 4 k =0 8 R k 2 R g . By de ini ion o 4 k , jj R k jj =1 ,4 k =0 ,  k = d k ; d c k =0 jj R k jj > 1 ,4 k > 0 ,  k > 0 jj R k jj < 1 ,4 k < 0 ,  k < 0 Thegeome ic elaxa ionsol e wo ksbydi e en iallymodi ying heindependen o ien ed cons ain s R k 2 R I g k =1 :::n ; 1 a each i e a ion. The algo i hm is based on he ollowing lemma, Lemma 5.2. Le assume ha o e e y o ien ed cons ain R k 2 R g , a di e en ial modi- ica ion d R k is pe o med such ha I jj R k jj < 1  R k  d R k > 0 I jj R k jj =1  R k  d R k =0 I jj R k jj > 1  R k  d R k < 0 Then, in he case he o al ene gy E T o he model is 0 i emains unchanged. On he o he hand, i he o al ene gy E T is posi i e, i dec eases. P oo . The p oo o he lemma is s aigh o wa d, and i is based on w i ing he o al ene gy E T o he sys em in e ms o he de ia ions o 4 k . In he case E T =0 , aking in o accoun ha E T = P i  2 i , i ollows ha  i =0 8 i . Then, 4 i =0 8 i and jj R i jj =1 8 i . Bu , d ( 4 i )= d ( R i R i ; 1) = 2 R i d R i =0 om he hypo hesis o he lemma. Now, d ( 4 i ) 8 i implies ha e e y 4 i =0 emains unchanged. Consequen ly,  i =0 8 i and E T =0 a e he di e en ial modi ica ion. In he case E T 6 =0 , d ( E T )=2 P i  i d (  i ) = =2 P i ( d c i ) 2 d i + d c i 4 i ( d c i ) 2 2 d i d ( 4 i ) = =2 P i ( d c i ) 4 2 d i ( d i + d c i ) 4 i d ( 4 i ) The i s e m o he suma o y is always posi i e and gi en ha d ( 4 i )= d ( R i R i ; 1) = 2 R i d ( R i ) I is possible o say ha all no null e ms o d ( E T ) a e nega i es since, by hypo hesis, 4 i has an opposi e sign o d ( 4 i ) 8 i . The e o e, d ( E T ) < 0 9 P oo . This is equi alen o p o e ha o any angle cons ain  i i be can ind a subs i- u ion dis ance d s i such ha 8  j 6 =  i 9 d s j j d educ ion (  j )= d s j and d s i 6 = d s j In a educ ion iangle he ollowing cases may appea : M (  1 d c 1 d c 2 d 1 )= M 0 ( d c 1 d c 2 d s 1 (  1 )) M (  1 d c 1 d 1 d 2 )= M 0 ( d c 1 d s 1 (  1 ) d 2 ) M (  1 d c 1 d 1 d 2 )= M 0 ( d c 1 d 1 d s 2 (  1 )) M (  1 d 1 d 2 d 3 )= M 0 ( d s 1 (  1 ) d 2 d 3 ) M (  1 d 1 d 2 d 3 )= M 0 ( d 1 d s 2 (  1 ) d 3 ) M (  1 d 1 d 2 d 3 )= M 0 ( d 1 d 2 d s 3 (  1 )) In all he cases, i is immedia e o check ha bo h models a e equi alen . The e o e, he applica ion o a simple d- educ ion always p oduces an equi alen model wi h he same solu ion han he ini ial one. P oposi ion 6.2. In a well-cons ained model o each educ ion iangle he e always exis sa leas oneo i s educ ion dis ances ha isno in ol edino he simpled- educ ions. P oo . In a gi en educ ion s ep, i he e is a educ ion iangle whe e all he educ ion dis ances a e cons ain s de ined in he model d c o subs i u ion dis ances d s o o he iangles, he model is o e -cons ained because he iangle is o e -cons ained wi h 4 cons ain s o e 3 poin s and i doesn’ ul il he Lambe p ope y. Howe e , his o e - cons ained model has been ob ained om he ini ial model h ough a sequence o simple d- educ ions ha p oduce equi alen models. As a consequence, he ini ial model mus be o e -cons ained. 6.2 4 P ; ang l e Model Con e sion o d ; educed o m In his sec ion hed- educ ion p ocess in 2D modelswi h dis ance cons ain s be ween wo poin s and angle cons ain s be ween wo ec o s wi h nocoinciden end poin is analyzed. In angle cons ain s he e a e in ol ed ou poin s a e in ol ed ( igu e 6). Le s a e he ollowing de ini ions: De ini ion 6.8. The ou poin s in ol ed in a angle cons ain be ween wo ec o s wi h a non common endpoin o m a quad ila e al polygon called educ ion quad ila e al De ini ion 6.9. The educ ion dis ances d o an angle cons ain a e each side dis ances and diagonal dis ances o he co esponding educ ion quad ila e al. 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . .. .. .. .. . .. .. . . . .. .. . .. . . .. . .. .. . . . .. .. . .. .. .. . .. .. . .. .. .. .. . .. . . .. . .. .. . . . .. .. . .. .. .. . .. .. . .. .. .. . .. .. p pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp pp p pp pp pp p pp pp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp pp .. ... ... .. ... ... ... . . ... ... ... .. ... ... .. ... .... ... . .... ... .. ... ... ... . . ... ... ... . pp ppp pp ppp ppp pp ppp ppp ppp pp ppp ppp pp ppp ppp pp ppp ppp pp ppp ppp pp ppp pp pp p pp pp p pp pp p pp pp p pp p pp pp p pp pp P1 P2  P4 P3 Figu e 6: Angle cons ain in ol ing 4 poin s On he basis o hese de ini ions i is possible o ex end he p ope ies o he 3 P ; ang l e , exposed in he las sec ion, o he 4 P ; ang l e Now, ins ead o educ ion iangle i will be alked abou educ ion quad ila e al. Simple d- educ ion can also be applied in he case o 4 P ; ang l e models. P ope y 6.3. I a model M is well-cons ained, in e e y educ ion quad ila e al he e exis s a leas wo ee educ ion dis ances d ha can be subs i u ion dis ances d s . P oo . In a quad ila e al he e a e 6 possible educ ion dis ances be ween he 4 in ol ed poin s P 1 P 2 P 3 P 4 , hese a e d 12 d 23 d 34 d 14 d 13 d 24 . Wi h 4 poin s wi h an angle con- s ain among hem,4dis ancecons ain s om he6possibleonesa eneeded. The e o e, a leas 2 o hem don’ ha e de ined cons ain s and hey can be subs i u ion dis ance. P ope y 6.4. In a d- educ ion p ocess, he applica ion o a simple d- educ ion on a 4 P ; angle model M p oduces an equi alen model M 0 ha has he same solu ion han M . P oo . Figu e7shows hepossiblecaseso educ iondis ances ha canappea subs i u ion dis ance in an angle in ol ing 4 poin s. In all cases, i is immedia e o check ha he applica ion o a simple d- educ ion always p oduces an equi alen model wi h he same solu ion han he ini ial one. In he igu e i is possible o obse e ha he d 2 and d 4 dis ance cons ain s can also be subs i u ion dis ance.In 4 P ; ang l e models he e a e p ima y subs i u ion dis ances as d 1 d 3 d 5 d 6 . I hese p ima y subs i u ion dis ances a e ee and hey a e no in ol ed in o he subs i u ions, hey should beused ins ead o he seconda y subs i u ion dis ances d 2 o d 4 . P ope y 6.5. In a well-cons ained model, o each educ ion quad ila e al he e always exis s a leas one o i s educ ion dis ances ha is no in ol ed in any o he simple d- educ ion. 17 . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . ... .. ... . .. ... ... .. . ... ... ... ... ... ... . .. ... .. ... . .. ... ... . .. ... ... .. . ... ... ... ... ... ... . .. ... .. ... . .. ... ... . .. . .. . .. .. . .. . . .. .. . .. . . .. .. . .. .. .. .. . .. .. . . .. . .. .. .. .. . .. .. . .. . . .. .. . .. . . .. .. . .. .. .. .. . .. .. . . .. . .. .. .. .. . .. .. . .. . . .. .. . .. . . .. .. . .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p p p pp pp p pp pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pp pp p pp pp pp p pp pp pp p pp pp pp p pp pp pppp pp p pp pp p pp pp p pp pp p pp pp p pp p pp pp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp pp p ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pppp ppp ppp ppp ppp ppp ppp ppp ppp ppp pp p ppp ppp ppp ppp ppp pppp ppp ppp pppp ppp pp ppp ppp pp ppp ppp pp ppp ppp pp ppp ppp pp ppp ppp pp ppp ppp pp ppp ppp .. . . .. . .. . .. . .. . .. . . .. . .. . .. . .. . .. . .. . . .. . .. . .. . .. . .. . .. . . .. . .. . .. . .. . .. . .. . . .. . .. . .. . .. . .. . .. . . .. . .. . .. .. . . .. . . . . . .. . . . . . .. . . . . . .. . . . . .. . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . . .. . . .. . . . ... . . . . .. . . . . .. . . . . .. . . . . .. . . . . .. . . . . .. . . . . .. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .. .. .. ... .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . .. . . .. . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .  d 1 d 2 d 3 d 4 d 5 d 6 P1 P2 P3 P4 d 1 d 3 d 5 d 6 d 2 d 4  P ima y Seconda y Figu e 7: Simple d- educ ion posibili ies in an angle on a 4 P ; angle model P oo . In a gi en educ ion s ep, i he e is a educ ion quad ila e al whe e all he e- duc ion dis ances a e cons ain s de ined in he model d c o subs i u ion dis ances d s o o he educ ion elemen , he model is o e -cons ained because he quad ila e al is o e - cons ained wi h 6 cons ain s o e 4 poin s and i doesn’ ul il he Lambe p ope y. Bu his o e -cons ained model has been ob ained om he ini ial model h ough a sequence o simpled- educ ions ha p oduce equi alen models. Asa consequence, he ini ial model mus be o e -cons ained. Theo em 6.1. Inawell-cons ained modelwi hangleanddis ance cons ain si isalways possible o ob ain a d- educed model such ha a e a d- educ ion p ocess all he angle cons ain s ha e been exp essed as dis ance cons ain s. P oo . F om he se o p ope ies seen be o e. Co ola ium 6.1. The con e gence demos a ions o he p oposed elaxa ion me hod in o de oachie econs ain sa is ac ion o d- educed modelsis alid o d- educible models. 6.3 The simple d- educ ion p ocess As i has been shown abo e, he d- educ ion p ocess is based on he i e a i e subs i u ion o e e y anglecons ain byoneo i ssubs i u iondis ance, such ha eachangle cons ain has i s co esponding di e en subs i u ion dis ance. Thescheme o ollowin o de oha e he cons ain sa is ac ion is: 1. Pe o m he d- educ ion p ocess i angle cons ain s exis in he model. 18 2. Sa is y by elaxa ion he d- educed model. A each i e a ion angle and subs i u ion dis ance alues a e calcula ed. The d- educ ion is pe o med in he ollowing way: Gi en a se o angle and he se o a alaible educ ion dis ances. Due o hese wo se a e disjoin s he ela ion be ween hemcan be ep esen edby a bipa i e g aph (big aph). The d- educ ion p ocess is a pe ec ma ching p oblem be ween he se o angle nodes and he se o dis ance nodes. Ape ec ma ching whe eeach angle  i has one educ ion dis ance d which is i s subs i u ion dis ance d s (  i ) . As a esul he pe ec ma ching is gene a ed ase o pai s < i d k > co esponding o he simple d- educ ions necessa ies o he d- educ ion p ocess. In he pe ec ma ching a educ ion dis ance o each angle is selec ed o be i s subs i u ion dis ance The pe ec ma ching p oblem can be sol ed using he algo i hm p oposed in [AHU83] in o de o ind maximal pa hs in a big aph. Howe e , i is possible o educed he sea ch space using a p ep ocess based on he ollowing p ope ies: P ope y 6.6. All angle node  i which in he big aph has only one a c o a dis ance node d i and he a cs in ol ed can be e ased om he big a because he ma ching (subs i u ion) o < i > and <d k > i is necessa y o achie e he pe ec ma ching s a e. P ope y 6.7. Alldis ance node d i which in hebig aphhasonlyonea c oadis ance node  i and he a cs in ol ed can be e ased om he big a because he ma ching (subs i u ion) o < i > by <d k > i is necessa y o achie e he pe ec ma ching s a e. Theapplica iono heabo ep ope iesasap epocesscansol e o ally hepe ec ma ching o i can esul ed a big a whe e he deg ee o he angle nodes is 2. In his case i is easy o achie e he pe ec ma ching s a e wi hou using he algo i hm p oposed by [AHU83]. 7 Single Poin , Single Cons ain and Hyb id Relaxa ion Sol e s Fo d ; educed sys emsacons ain sol e isnex p oposedbasedonani e a i e elaxa ion me hod. In his way, while jj ~  jj  " , a each i e a ion, he cons ain sol e wo ks o e poin s o o e cons ain s. This means ha he sol e in each s ep has o decide o selec one cons ain o elax o o pe o m a global de o ma ion in o de o mo e sligh ly all he poin s. We a e no using his case. Up o now he ollowing cases ha e been ad essed:  One-poin elaxa ion: On a poin P ,i he g ad ( ~  ) 6 =0 is no null, P can be mo ed in he di ec ion o he g adien ec o . In his way he maximum dec ease o jj ~  jj is achie ed. The p oblem aises when he e is a local minimum and he g adien ec o is null o all poin s. 19  One-cons ain elaxa ion: I is also possible o elax one cons ain d i . In his case local minima can be eached. I he cons ain elaxed d i has he maximum alue o j ~  j a good beha io o he con e gence o he sol e has been expe imen ally checked.  Global poin elaxa ion: In his case a space de o ma ion is applied in o de o p ese e he dec easing o jj ~  jj .  Global cons ain elaxa ion: This case would equi e o sol e all he cons ain s a he same ime. The e o e, i is una o dable. Cons ain Va ia ion Ma ix A = a ji ] : each ma ix elemen ep esen s he di e en ial a ia ion o he pa ame e associa ed wi h cons ain j acco ding o he a ia ion o he cons ain i ( i 6 = j ). So, a ji ep esen s, he di e en ial a ia ion o he pa ame e d j acco ding o he a ia ion o d i . dim ( A )= m  m A = 8 < : a ji =1 i i = j a ji =0 i i 6 = j and any change in d i doesn’ p oduces a a ia ion on d j a ji = @d j @d i i i 6 = jd i d j sha e a common endpoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ........ ....... ........ ........ ....... ........ ........ ....... ........ ........ ........ ....... ........ ........ ....... ........ ........ ....... ........ ........ ........ ....... ........ ........ ....... ........ ........ ....... ........ ........ ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p pp ppp pp pp ppp pp ppp pp ppp pp ppp pp ppp pp pppp pp ppp pp pp ppp pp ppp pp ppp pp ppp pp ppp pp ppp ppp pp ppp pp ppp pp ppp pp ppp pp ppp pp pp ppp pp pppp pp ppp pp ppp pp ppp pp ppp pp ppp pp pp ppp pp p p pp ppp pp pp ppp pp ppp pp ppp pp ppp pp ppp pp pppp pp ppp pp pp pp ppp pp ppp pp ppp pp ppp pp ppp pp p p pp ppp pp ppp pp ppp pp ppp pp ppp pp pp pp ppp pp pppp pp ppp pp ppp pp ppp pp ppp pp ppp pp pp ppp pp p P1 P2 P4 P5 d1 d2 d3 d4 d5 Figu e 8: Link be ween dis ance cons ain s Thema ix column k ep esen s heuni a ia ion o heo e allcons ain s ha a elinked o d k . Because he sol e wo ks wi h dis ance cons ain s he cons ain a ia ion ma ix is symme ic and i is easy o p o e ha j a ji j 1 . Using he one-cons ain elaxa ion, i can be shown [SoB98] ha he sol e con e ges o he solu ion i he cons ain  i is so ha  i = max j j  j j and he e exis s a posi i e alue L such ha , 20 X j (   )  j b ji  L> 0 (1) wi h 8 < : b ji = a ji p P j a 2 ji (   )  j = (   ) j (   ) i Theequa ion1canbeunde s oodasaglobalconco dance equi emen ,because he ela i e signs o (   ) j wi h espec o (   ) i , mus ag ee wi h he a ji signs. The equa ion 1 s a es ha he one-cons ain elaxa ion algo i hm con e ges in global conco dance cases. I 1 is no sa is ied he elaxa ion can all in o local minima and con e gence can no be ensu ed (Anyway, we ha e expe imen ally de ec ed a good con e gence beha iou also in hese cases). As a consequence, a hyb id i e a i e cons ain sol e has been de eloped. In i , he elaxa ion p ocess is pe o med in he ollowing way, Hyb id Cons ain elaxa ion. A each i e a ion a cons ain is elaxed o he whole se o poin s a e de o med. The ollowing algo i hm is used: I he sys em is no in a local minimum s a us hen - Choose a cons ain i . - Relax he cons ain i ( d i c  ) by making i close o he equilib ium alue d c i .A elaxa ion ac o is used. d i c  +1 = d i c  +  ( d c i ; d i c  ) - Upda e he cons ain s d j such ha a ji 6 =0 d j c  +1 = d j c  +  a ji  ( d c i ; d i c  +1 ) - Upda e he geome ic elemen alues ( ec o s, poin s, plane equa ions, _ ..) a ec ed by he modi ica ion o he cons ain alues. - Compu e he new ma ix alues o A and ~  . Else - Use a global de o ma ion in o de o mo e he whole se o poin s and dec ease jj ~  jj . 21 8 Examples and discussion In his sec ion a se o six poin s ha ini ially o m a egula hexagon is s udied. Be ween he poin s, he ollowing dis ance cons ain s ha e been de ined: d c 1 = dis ance ( P 1 P 2 ) d c 2 = dis ance ( P 1 P 4 ) d c 3 = dis ance ( P 1 P 6 ) d c 4 = dis ance ( P 2 P 3 ) d c 5 = dis ance ( P 5 P 6 ) d c 6 = dis ance ( P 3 P 4 ) d c 7 = dis ance ( P 4 P 5 ) d c 8 = dis ance ( P 3 P 6 ) d c 9 = dis ance ( P 2 P 5 ) In nex sec ions i is shown he beha io o he p oposed me hod wi h wo se o speci ic alues o he dis ance cons ain s using he p oposed global de o ma ion sol e and he hyb id algo i hm explained. In he second example and due o he cons ain alues used, he ini ial s a e is in a local minimum. 8.1 Example 1: L-shape In his example, he nine dis ance cons ain s a e ixed wi h he ollowing alues: d c 1 =2 d c 2 =1 : 4142 d c 3 =2 d c 4 =1 d c 5 =1 d c 6 =1 d c 7 =1 d c 8 =2 : 2360 d c 9 =2 : 2360 The igu e 9 shows he ini ial con igu a ion. On he o he hand, he igu e 10 p esen s he inal con igu a ion o he sys em. In igu e 11 he e olu ion o jj ~  jj a each i e a ion using he i e a i e global de o ma ion sol e is shown. In igu e 12 he e olu ion o jj ~  jj a each i e a ion using he one-cons ain 22 elaxa ion is p esen ed. In igu e 13 he e olu ion o jj ~  jj a each i e a ion using he p oposedhyb id me hodis p esen ed. In cases 11and 13 he local minima a e success ully a oided. O he wise, local inc eases o jj ~  jj can be obse ed in case 12. 8.2 Example 2: Double iangula shape In his example, he nine dis ance cons ain s a e ixed wi h he ollowing alues: d c 1 =2 d c 2 =1 d c 3 =2 d c 4 =2 d c 5 =2 d c 6 =2 d c 7 =2 d c 8 =1 d c 9 =1 The igu e 14 and 15 show he ini ial and he inal con igu a ion o he sys em. In igu es 16 and 18, he e olu ion o jj ~  jj a each i e a ion using he i e a i e global de o ma ion sol e and he hyb id me hod p oposed a e shown. In bo h cases he local minima a e also success ully a oided using he p oposed me hods. Figu e 17 show he e olu ion in one-cons ain elaxa ion case. 9 3D Ex ension and Conclusions A cons ain sol e ha wo ks on he In e nal Model Rep esen a ion and which is based only in dis ance cons ain s has been p esen ed. Th ough an i e a i e elaxa ion o con- s ain s a solu ion is ound. The con e gence o he sol e using a global elaxa ion can be gua an eed. The p oposed me hod in 2D can be also used in 3D sys ems. The elaxa ion p ocess s a s om he ini ial condi ions. In his way a mechanism is p o ided o each a solu ion which is close o he ini ial condi ions. In cases wi h se e al solu ions, by changing he ini ial condi ions i is possible o swi ch om one solu ion o he o he . The sol e can also be applied in unde -cons ained sys ems by keeping he use in en ion. 23 Re e ences [Ald88] B.Ald eld. Va ia ion o geome ies based on a geome ic- easoning me hod. CAD, ol.20, no.3, Ap il 1988. [AHO83] A.V.Aho, J.E.Hopc o , J.D.Ullman. Da a S uc u es and Algo i hms. Addison-Wesley Publishing Co., 1983. [Bo 81] A.H.Bo ning. The p og amming language aspec s o ThingLab, a con- s ained o ien ed simula ion labo a o y. ACM T ans. on P og. Lang. and Sys ems, ol.3, no.4, Oc obe 1981. [BFHCP93] W.Bouma,I.Fudos,CHo man,J.Cai,R.Paige.Ageome iccons ain sol e . Technical Repo , CSD-TR-93-054, Pu due Uni e si y, 1993. [Buch85] B.Buchbe ge . G ¨ obne Bases: An algo i hmic Me hod in Polynomial Ideal Theo y. In N.K.Bose, edi o , Mul idimensional Sys ems Theo y, pp.184-232. D.Reidel PublishingCo., 1985. [CFV88] U.Cugini, F.Folini,I.Vicini. AP ocedu al Sys em o heDe ini ion and S o - age o Technical D awings in Pa ame ic Fo m. P oceedings o Eu og aph- ics’88, pp.183-196, No h-Holland, 1988. [Emm90] M.J.G.M. an Emme ick. In e ac i e Design o Pa ame e ized 3D models by di ec manipula ion. PhD hesis, Del Uni e si y P ess, 1990. [FuH93] I.Fudos,C.Ho man.Co ec ness p oo o ageome iccons ain sol e .Tech- nical Repo CSD-93-076, Compu e Sciences Depa amen , Pu due Uni e - si y, Decembe 1993. [HoJ92] C.M.Ho mann,R.Juan.ERep.Anedi ablehigh-le el ep esen a ion o geo- me ic design and analysis. Technical Repo CSD-TR-92-055.CAPO Repo CER-92-24. Pu due Un e si y, Augus 1992. [HsB97] C.Hsu, B.D.B ¨ ude lin. A Hyb id Cons ain Sol e Using Exac and I e - a i e Geome ic Cons uc ions. In CAD Sys ems De olopmen : Tools and Me hods, D.Rolle and P.B une Eds, Sp inge Ve lag 1997, pp. 265-279 [JoS97] R.Joan-A inyo, A.So o.Rule-BasedGeome icCons ain Sol e .Compu e & G aphics, ol.21 no.5, 1997. [KaB90] D. Kal a, A.H. Ba . A Cons ain -Based Figu e-Make . P oceedings o Eu- og aphics’90, pp.413-424, No h-Holland, 1990. [Lam70] G.Laman. On G aphs and Rigidi y o Plane Skele al S uc u es. Jou nal o Enginee ing Ma hema ics, ol.4, no.4, Oc obe 1970. [LGL81] V.C.Lin, D.C.Gossa d, R.A.Ligh . Va ia ional Geome y in Compu e Aided Design. ACM Compu e G aphics, ol.15, no.3, Augus 1981. 24 [Nel85] G.Nelson. Juno, a cons ain -based g aphics sys em. SIGGRAPH’85, ol.19, no.3, pp.235-243, San F ancisco. July 22-26, 1985. [Owe91] J.C.Owen. Algeb aic Solu ion o Geome y om Dimensional Cons ain s. P oceedings o Symposium on Solid Modelling Founda ions and CAD/CAM Applica ions. J.Rossignac, J.Tu ne (eds). Aus in, June 5-7, pp.397-407, ACM P ess 1991. [RBN89] J.R.Rossignac, P.Bo el, L.R.Nackman. In e ac i e Design wi h Sequences o Pa ame e ized T ans o ma ions. In elligen CAD Sys ems II. V.Akman, P.J.W. en Hagen, P.J. Vee kamp (eds), pp.93-125, Sp inge -Ve lag, 1989. [Rol91a] D.Rolle . Ad anced Me hods o Pa ame ic Design. Geome ic Modelling. Me hods and Applica ions. H.Hagen, D.Rolle (eds), pp. 251-266, Sp inge - Ve lag, 1991. [Rol91b] D.Rolle . An app oach o compu e -aided pa ame ic design. CAD, ol.23, no.5, June 1991. [SoB91c] W. Soh , B.D.B ¨ ude lin. In e ac ion wi h cons ain s in 3D modeling. In- e na ional Jou nal o Compu a ional Geome y & Applica ions, ol.1, no.4, pp.405-425, 1991. [SoB93] L.Solano,P.B une .Asys em o cons uc i e cons ain -basedmodelling.In B.Falcidienoand T.Kunii,edi o s,Modelingin Compu e G aphics. Sp inge Ve lag, 1993. [SoB94a] L.Solano, P.B une . A language o cons uc i e pa ame ic solid modelling. Technical Repo LSI-94-43-R, Uni e si a Poli ecnica de Ca alunya, LiSI, 1994. [SoB94b] L.Solano, P.B une . Cons uc i e cons ain -based model o pa ame ic CAD sys ems. CAD, ol.26, no.8, pp.614-621, Augus 1994. [SoB98] L.Solano, P.B une . Geome ic Dis ance Cons ain Sa is ac ion by Cons ain - o-cons ain Relaxa ion (W i en in Ca alan). Technical Repo LSI-98-27-R, Uni e si a Poli ecnica de Ca alunya, LiSI, 1998. [S S80] G.L.S eele, G.L.Sussman. Cons ain - a language o exp essing almos - hie a chical desc ip ions. A i icial In elligence, pp.1-39, Janua y 1980. [Sun88] G.Sunde. Speci ica ion o Shape by Dimensions and O he Geome - ic Cons ain s. Geome ic Modelling o CAD Applica ions. M.J.Wozny, H.W.McLaughlin, J.L.Eca nacao (eds), pp.199-213, No h-holland 1988. [Su 63] I.Su he land. Ske chpad, a man-machine g aphical communica ion sys em. In P oc. o he Sp ing Join Comp. Con e ence, pp.329-345. IFIPS, 1963. [VSR92] A.Ve ous , F.Schonek, D.Rolle . Rule-o ien ed me hod o pa ame ized compu e aided design. CAD, ol.24, no.10, Oc obe 1992. 25