|
Modelatge Geomètric amb Computador |
|
|
|
Modelatge Geomètric amb Computador |
|
Comprovar si un punt p és interior
a un sòlid es pot fer de diverses maneres. La que proposem consisteix
en comptar la paritat del nombre d'interseccions entre el sòlid
i una semirecta amb origen en el punt donat; si el nombre d'interseccions
és parell, el punt és exterior, altrament és interior
al sòlid.
Cal intersectar la semirecta amb totes les cares
de l'objecte, trobant el punt p' d'intersecció entre el pla
de suport de la cara i la semirecta i cridant a PuntDinsCara3D.
Aquesta rutina comprova si el punt p' és interior
a la cara, és a dir, si efectivament és interior al polígon
contorn però no cau dins de cap forat de la cara. Per tant, és
recomanable dissenyar una altra rutina, PuntDinsPolígon3D,
que comprova si un punt és interior a un polígon. Aquest
test es pot fer projectant el polígon i el punt en 2D, segons la
direcció més influent de la normal del pla de suport.
Aquest test caldrà realitzar-lo sobre dos tipus diferents d'arestes: les arestes velles, ja existents en un dels dos sòlids a operar (fase 1 de l'algorisme) i les arestes noves, creades com a intersecció entre un pla d'un dels sòlids a operar i una aresta de l'altre (fase 2 de l'algorisme).
En el cas de les arestes velles,
seran convexes si l'orientació Vi-Vf coincideix amb la del producte
vectorial  d x e,
essent
Vi el vèrtex inicial de la semiaresta, Vf el vèrtex final de la semiaresta, d el pla de la cara dreta de la
aresta i
e el pla de la cara esquerra de
l'aresta. |
 |
 |
En el cas de les arestes noves,
la convexitat/concavitat de l'aresta tan sols depèn de l'operació
booleana que s'estigui realitzant:
La intersecció crea noves arestes convexes (la intersecció de dos semiespais sempre deixa regions convexes); la unió crea arestes noves còncaves (per la raó contrària); les noves arestes creades per una diferència també són convexes. |
Com en el cas del test de convexitat d'una aresta,
també distingim entre vèrtexs vells (provinents de la fase
1) i vèrtexs nous (provinents de la fase 2).
L'ordenació de les cares al voltant d'un
vèrtex vell es pot extreure de la informació enmagatzemada
en l'estructura B-Rep, tan sols cal tenir en compte que si el vèrtex
era d'un sòlid restant B (d'una diferència A-B) caldrà
invertir l'ordre de les cares.
 |
En el cas dels vèrtexs
nous, com que hem suposat que sempre provenen de la intersecció
d'una semiaresta d'un sòlid amb una cara de l'altre sòlid,
només hi ha dues possibles ordenacions ( C1 Ce Cd o
Cd Ce C1 en el dibuix). L'ordenació es pot decidir en funció
de si el vèrtex inicial de la semiaresta Vi, és interior
o exterior del pla de la cara C1.() |
i l'operació booleana és una intersecció, l'orientació
serà Cd-Ce-C1; si Vi és exterior a ,
l'orientació resultant serà la contrària, C1-Ce-Cd.
La seguent figura mostra aquestes dues possibles configuracions:
La tercera fase de l'algorisme d'operacions booleanes
implica trobar el següent vèrtex sobre una aresta donada en
una determinada direcció. Quan existeixen més d'un vèrtex
candidats, cal realitzar un senzill test geomètric per determinar
quin és el més proper en la direcció de l'aresta.
Aquest test geomètric es pot fer de dues
maneres:
Mètode
A: Ordenant tots els vèrtexs
sobre l'aresta (no només els candidats, sinó tots els que
estan sobre l'aresta). Com que a cada vèrtex li ha de correspondre
una parella, la parella del vèrtex actual Vact ha de ser el següent
vèrtex buscat.
L'ordenació es fa en
funció del paràmetre 
de l'equació
paramètrica de la recta de suport de l'aresta, 
+ Vact.
, la direcció
de l'aresta, es pot trobar bé fent el producte vectorial del
vector normal al pla de la cara que s'està reconstruïnt, ,
amb el vector normal de la cara següent de Vact, seg,
o bé restant a Vact qualsevol dels altres vèrtexs sobre l'aresta.
Mètode B: L'altre mètode implica tenir enmagatzemada la informació de concavitat / convexitat de les arestes al voltant dels vèrtexs candidats, per poder calcular el sentit de la semiaresta que estem reconstruïnt (no només la direcció).
En aquest cas, el vector es calcula a partir
del producte vectorial xseg,
i si l'aresta -seg al
voltant de Vact era còncava, cal invertir el sentit de .
El vèrtex buscat serà el de valor del paràmetre
minim no negatiu en l'equació
+ Vact, és a dir, el més proper a Vact en la direcció
de .
Un cop realitzat el dòmino, haurem format una sèrie de cicles sobre la cara que estem reconstruïnt i cal diferenciar entre cicles externs, que formaran una cara independent, i cicles interns, que seran forats d'alguna cara.
 |
Per simplificar aquesta classificació,
podeu suposar que no hi haurà ni cares internes a altres cares ni
cicles interns a d'altres cicles també interns, és a dir,
que la situació dels cicles C1 C2 C3 de la figura no es donarà
perquè només existeix un nivell d'imbricació.
Com que sabem que els cicles d'arestes no s'intersecten (altrament no estariem realitzant bé l'operació booleana), els tests de cicle interior a un altre es tradueixen en simples tests de PuntDinsPolígon3D d'un vèrtex qualsevol del primer cicle respecte al segon cicle. |
L'algorisme general és un procés iteratiu que a cada iteració clasifica els cicles no interiors a cap altre com a externs(cares) o interns (forats) depenent de la paritat del nombre d'iteracions que s'hagin realitzat:
paritat=CERTAquest procés es pot realitzar alhora que es van creant les noves cares i forats i afegint-se a l'objecte final resultat de l'operació booleana. Cal tenir en compte que l'ordre de les arestes dels forats és l'invers al dels polígons exteriors.
C:=conjunt de cicles sobre la cara
mentre C!=Ø fer { /* mentre quedin cicles per tractar */
D:=Ø
per cada cicle Cx de C fer
si Cx és interior a algun cicle Cy de C-{Cx}
llavors classificar-lo com a forat de Cy
altrament afegir-lo a D
fsi
fper
si paritat llavors els cicles de D són cares exteriors
altrament els cicles de D són forats
fsi
paritat:=no paritat
C:=C-D
fmentre
|
|
Marc Vigo i Pere Brunet |
|