Geometria Constructiva de Sòlids (CSG)
És un model de sòlids basat en una estructura en arbre amb
-
Nodes interiors: Operacions Booleanes (Unió, Intersecció,
Diferència)
-
Nodes terminals (fulles): objectes primitius parametritzats (cub, con,
esfera, cilindre, etc.)
Exemple:
 |
De vegades també s'inclou una transformació
lineal (matriu) associada als nodes o només a les fulles. En cas
contrari, les primitives han de ser parametritzades (radi, alçada,
posició, ...) Habitualment l'arbre és binari, però
per les operacions d'unió i intersecció no caldria.
Exemple d'expressions algebraiques que modelitzen l'objecte:
A := Bloc(a1,b1,c1); A := TG(A,M1)
B := Bloc(a2,b2,c2); B := TG(B,M2)
C := Cilindre(r,h); C := TG(C,M3)
Obj := (A-C) U B
|
Característiques del model:
-
No ambigu i vàlid, sempre que les operacions booleanes
siguin les regularitzades.
-
No únic. Per exemple, en la figura es podria haver canviat
l'ordre de la unió i la diferència ((AUB)-C) o haver
obtingut el perfil de la "L"com la diferència entre un bloc gran
i un de més petit.
-
Molt concís (objectes complexos es poden representar utilitzant
poca memòria).
-
Domini de representació: depèn de les primitives admeses.
En general, els objectes representables estaran sempre limitats per (fragments
de) superfícies de les primitives. Admet objectes que no siguins
2-varietat (non-manifold).
Operacions i interrogacions sobre el model:
-
Transformacions geomètriques: immediates,
modificant les matrius o els paràmetres. Fins i tot de part d´un
objecte.
-
Classificació punt-sòlid: implica
saber classificar un punt respecte a les primitives. Vegeu l'algorisme.
-
Classificació recta-sòlid: ray-casting
amb intèrvals de recta. Vegeu l'algorisme.
-
Càlculs de volums, etc: complicats.
Pot caldre avaluar el model. Es pot fer un càlcul aproximat
mitjançant ray-casting i llençant molts raigs.
-
Operacions booleanes: immediates!.
-
Edició (construcció): relativament
senzilla i fàcil de manegar (el model és bastant intuïtiu,
excepte potser l'operació d'intersecció).
-
Visualització: Existeixen algorismes
directes per ray-casting (algorisme de Roth), però si es
volen utilitzar les eines estàndard (z-buffer), cal avaluar el model.
Avaluar el model significa calcular exactament quines
cares, arestes i vèrtexs té, és a dir, transformar-lo
en B-Rep.
Algorisme de classificació punt-sòlid
CSG
funció
ClassificaPunt(P:punt, n:nodeCSG) retorna InOnOut
si EsFulla(n) llavors
cas (n.tipus)
Bloc: r:=ClassificaPuntBloc(P,n)
Cilindre: r:=ClassificaPuntCil(P,n)
Esfera: r:=ClassificaPuntEsf(P,n)
...
fcas
si no
r:=Combina(n.operacio,ClassificaPunt(P,n.fillDret),
ClassificaPunt(P,n.fillEsq))
fsi
retorna r
ffunció |
Combina(op, A, B)
| AUB |
in |
on |
out |
| in |
in |
in |
in |
| on |
in |
on |
on |
| out |
in |
on |
out |
| A^B |
in |
on |
out |
| in |
in |
on |
out |
| on |
on |
on |
out |
| out |
out |
out |
out |
| A-B |
in |
on |
out |
| in |
out |
on |
in |
| on |
out |
on |
on |
| out |
out |
out |
out |
|
|
|
Es pot optimitzar l'algorisme podant les branques que no cal explorar (per
exemple, si en fer una intersecció el resultat de la branca de l'esquerra
es "out", ja no cal explorar la branca dreta).
Algorisme de classificació recta-sòlid
CSG
En aquest cas, el resultat de l''operació
és més complicat, perquè cal representar una llista
d'intèrvals InOnOut. Si la recta r està parametritzada com
r= (P +lambda * v), els elements de la llista poden ser parelles
[lambda,classificació].
L'algorisme es idèntic al de la classificació d'un punt,
substituïnt "punt" per "recta".
La funció combina ha de combinar les dues
llistes d'intèrvals, fent servir les mateixes taules que en l'algorisme
anterior (La classificació d'un intèrval de
recta coincideix amb la
classificació de qualsevol dels seus punts, per exemple el punt mig).
En la llista resultant cal compactar intèrvals amb la
mateixa classificació. Per exemple (usem la notació l1 .. l4
pels quatre paràmetres lambda1 .. lambda4 d'intersecció):
|
|
Resultat de la unió : [l1,in] [l2,on] [l4,out]
(s'han hagut de compactar dos intèrvals "in")
|
Sòlid A : [l1,in] [l2,out]
Sòlid B : [l3,on] [l4,out]
|
Resultat de la intersecció : [l1,out] [l3,on] [l2,out]
(s'han hagut de compactar dos intèrvals "out")
|
|
|
Resultat de la diferència : [l1,in] [l3,on] [l2,out]
(s'han hagut de compactar dos intèrvals "out")
|