Operacions Booleanes entre objectes en BRep
Exemples

   Aquí teniu dos exemples d'operacions booleanes entre dos cubs, en que el primer d'ells dóna lloc a una indeterminació durant la reconstrucció de les cares de l'objecte final, mentre que el segon dóna lloc a una cara amb un forat.
  1. Vèrtexs i cares dels cubs de l'exemple
    2. OBJECTE A (les coordenades són iguals per ambdós exemples) 
    OBJECTE B (les coordenades són diferents per a cada exemple, però la representació és la mateixa) 
  2. Exemple 1:

    3.    Imaginem que tenim dos objectes (paral.lelepípeds) A i B. Per simplicitat, utilitzem un model de fronteres molt simple, en què per a cada cara només es guarda la relació C:{V} (els vèrtexs es disposen en ordre segons la regla del tirabuixó cap enfora de l'objecte), i per cada vèrtex es guarden les seves tres coordenades. Observeu també que no cal parlar de polígons ja que les cares no tenen forats. Si numerem els vertexs i cares de B a continuació dels de A per evitar confusions, el model de fronteres dels dos objectes és: 
           Objecte A                   Objecte B

   Cares     Vertexs           Cares         Vertexs

1:{3,4,8,7}  1:(0,0,0)     7:{11,12,16,15}   9:(1,2,2)  
2:{2,6,8,4}  2:(3,0,0)     8:{10,14,16,12}  10:(2,2,2)  
3:{1,5,6,2}  3:(0,0,3)     9:{ 9,13,14,10}  11:(1,2,5)  
4:{1,3,7,5}  4:(3,0,3)    10:{ 9,11,15,13}  12:(2,2,5)  
5:{5,7,8,6}  5:(0,3,0)    11:{13,15,16,14}  13:(1,4,2)  
6:{1,2,4,3}  6:(3,3,0)    12:{ 9,10,12,11}  14:(2,4,2)  
             7:(0,3,3)                      15:(1,4,5)  
             8:(3,3,3)                      16:(2,4,5)  
  3. Exemple 2:

    4.    Imaginem que tenim els dos objectes (paral.lelepípeds) A i B de manera que mantenim la posició de A pero hem traslladat el B segons l'eix y: 
           Objecte A                  Objecte B

   Cares      Vertexs         Cares           Vertexs

1:{3,4,8,7}  1:(0,0,0)     7:{11,12,16,15}   9:(1,1,2)  
2:{2,6,8,4}  2:(3,0,0)     8:{10,14,16,12}  10:(2,1,2)  
3:{1,5,6,2}  3:(0,0,3)     9:{ 9,13,14,10}  11:(1,1,5)  
4:{1,3,7,5}  4:(3,0,3)    10:{ 9,11,15,13}  12:(2,1,5)  
5:{5,7,8,6}  5:(0,3,0)    11:{13,15,16,14}  13:(1,2,2)  
6:{1,2,4,3}  6:(3,3,0)    12:{ 9,10,12,11}  14:(2,2,2)  
             7:(0,3,3)                      15:(1,2,5)  
             8:(3,3,3)                      16:(2,2,5)  
  4. Obtenció de la resta A - B amb l'algorisme de classificació de cares.
    1. Creació de la llista de cares LC
    2. Generació de les cares de l'objecte final a partir de les de la llista de cares LC.

      3. Com que l'objecte final es A - B, per obtenir les seves cares només cal recórrer la llista LC i seleccionar els elements de tipus DeAoutB i DeBinA.
    3. Generació dels vèrtexs de l'objecte final.

      4. Fixeu-vos que els vèrtexs de l'objecte final són simplement els vèrtexs de les cares que es generen a 4.2.
  5. Obtenció de la resta A - B amb l'algorisme de classificació de vèrtexs
    1. Creació de la llista de vèrtexs LV: Afegit dels vertexs dels dos objectes A i B. La llista LV queda de la següent manera (per a cada vèrtex, "xyz" vol indicar les seves coordenades, "{...}" es la llista de les seves cares, i "deX.." es el seu tipus. Observeu que les coordenades i la llista de cares veïnes es poden obtenir directament del model BRep de l'objecte):
      2.        Exemple 1                     Exemple 2 
 
V 1: xyz, {4,3,6},   deAoutB   V 1: xyz, {4,3,6},   deAoutB
V 2: xyz, {3,2,6},   deAoutB   V 2: xyz, {3,2,6},   deAoutB
V 3: xyz, {1,4,6},   deAoutB   V 3: xyz, {1,4,6},   deAoutB
V 4: xyz, {2,1,6},   deAoutB   V 4: xyz, {2,1,6},   deAoutB
V 5: xyz, {5,3,4},   deAoutB   V 5: xyz, {5,3,4},   deAoutB
V 6: xyz, {5,2,3},   deAoutB   V 6: xyz, {5,2,3},   deAoutB
V 7: xyz, {1,5,4},   deAoutB   V 7: xyz, {1,5,4},   deAoutB
V 8: xyz, {2,5,1},   deAoutB   V 8: xyz, {2,5,1},   deAoutB
V 9: xyz, {9,10,12}, deBinA    V 9: xyz, {9,10,12}, deBinA
V10: xyz, {9,8,12},  deBinA    V10: xyz, {9,8,12},  deBinA
V11: xyz, {7,10,12}, deBoutA   V11: xyz, {7,10,12}, deBoutA
V12: xyz, {8,7,12},  deBoutA   V12: xyz, {8,7,12},  deBoutA
V13: xyz, {11,9,10}, deBoutA   V13: xyz, {11,9,10}, deBinA
V14: xyz, {11,8,9},  deBoutA   V14: xyz, {11,8,9},  deBinA
V15: xyz, {7,11,10}, deBoutA   V15: xyz, {7,11,10}, deBoutA
V16: xyz, {8,11,7},  deBoutA   V16: xyz, {8,11,7},  deBoutA
      Encara que per evitar indeterminacions a la reconstrucció de les cares pot ser interessant usar criteris de ciclicitat més estrictes, aquí hem suposat que la llista de cares de cada vèrtex està ordenada cíclicament basant-nos en el fet que existeix una aresta entre cada cara i la seva següent a la llista, i que també existeix una aresta comuna entre la darrera cara i la primera de la llista. Pot ser interessant emmagatzemar també la convexitat o concavitat de cadascuna de les arestes al voltant dels vértexs. Vegeu la pàgina dels tests geomètrics per saber com calcular-la.
       
    2. Creació de la llista de vèrtexs LV: Afegim els vertexs nous

      3. A les següents llistes es pren el conveni que les dues primeres cares de cada vèrtex nou són les que comparteixen l'aresta que s'ha intersectat amb la cara de l'altre objecte, que és la tercera de la llista: 
             Exemple 1                     Exemple 2 

V17: xyz, {9,10,5}, Nou         V23: xyz, {10,11,1}, Nou
V18: xyz, {8,9,5},  Nou         V24: xyz, {11,8,1},  Nou
V19: xyz, {1,5,10}, Nou         V25: xyz, {10,12,1}, Nou
V20: xyz, {1,5,8},  Nou         V26: xyz, {12,8,1},  Nou
V21: xyz, {10,12,1},Nou
V22: xyz, {8,12,1}, Nou
      (el vèrtex 17, per exemple, es troba com intersecció de l'aresta V9-V13 de l'objecte B amb la cara 5 de l'objecte A. Les cares són les 9,10,5 perquè l'aresta 9-13 de l'objecte B limita amb les cares 9 i 10; el mateix passa amb les altres arestes)

       Fixeu-vos que les interseccions aresta - cara que cal fer en aquesta fase, donen com a subproducte el test de si hi ha coincidències entre A i B. Quan s'intersecta l'aresta a d'un objecte amb la cara c de l'altre, únicament cal comprovar la posició del punt d'intersecció P: Si el punt P coincideix amb un dels vèrtexs de l'aresta o bé si P pertany a una de les arestes dels polígons de la cara, podem afirmar que estem en un cas de coincidències i haurem de donar un missatge i aturar l'algorisme. Si en canvi, P es troba entre els dos vèrtexs de l'aresta i és interior a la cara haurem d'inserir aquest punt a la llista LV de vèrtexs. Recordeu que el test de punt interior a cara es pot fer en 2D a partir de les projeccions de P i c sobre un dels plans coordenats (vegeu la pàgina dels tests geomètrics). El càlcul de la convexitat o concavitat de les noves arestes que es crein al voltant d'aquests vèrtexs depèn tant sols de l'operació booleana que s'estigui realitzant, tal com es mostra a la pàgina dels tests geomètrics.
       
       

    3. Filtratge de la llista LV i obtenció de la llista de vèrtexs de l'objecte final

      4. Com que estem generant els vertexs de A - B, hem de generar la subllista que conté els vertexs deAoutB, els deBinA, i els nous: 
                     Exemple 1                     Exemple 2 

V 1: xyz, {4,3,6},   deAoutB   V 1: xyz, {4,3,6},   deAoutB
V 2: xyz, {3,2,6},   deAoutB   V 2: xyz, {3,2,6},   deAoutB
V 3: xyz, {1,4,6},   deAoutB   V 3: xyz, {1,4,6},   deAoutB
V 4: xyz, {2,1,6},   deAoutB   V 4: xyz, {2,1,6},   deAoutB
V 5: xyz, {5,3,4},   deAoutB   V 5: xyz, {5,3,4},   deAoutB
V 6: xyz, {5,2,3},   deAoutB   V 6: xyz, {5,2,3},   deAoutB
V 7: xyz, {1,5,4},   deAoutB   V 7: xyz, {1,5,4},   deAoutB
V 8: xyz, {2,5,1},   deAoutB   V 8: xyz, {2,5,1},   deAoutB
V 9: xyz, {9,10,12}, deBinA    V 9: xyz, {9,10,12}, deBinA
V10: xyz, {9,8,12},  deBinA    V10: xyz, {9,8,12},  deBinA
                               V13: xyz, {11,9,10}, deBinA
                               V14: xyz, {11,8,9},  deBinA

V17: xyz, {9,10,5}, Nou        V23: xyz, {10,11,1}, Nou
V18: xyz, {8,9,5},  Nou        V24: xyz, {11,8,1},  Nou
V19: xyz, {1,5,10}, Nou        V25: xyz, {10,12,1}, Nou
V20: xyz, {1,5,8},  Nou        V26: xyz, {12,8,1},  Nou
V21: xyz, {10,12,1},Nou
V22: xyz, {8,12,1}, Nou
    4. Construcció de les cares de l'objecte final

      5. Vegem només com es reconstuiria una de les cares de l'objecte final. Veurem la reconstrucció de la cara provinent de la cara 1 de A, ja que aquest cas ens permetrà discutir alguns casos interessants.

       El primer pas és sel.leccionar de la llista LV els vèrtexs que tenen la cara 1 a la seva llista de cares: 

                     Exemple 1                     Exemple 2 

V 3: xyz, {4,1,6}, deAoutB     V 3: xyz, {4,1,6}, deAoutB
V 4: xyz, {2,1,6}, deAoutB     V 4: xyz, {2,1,6}, deAoutB
V 7: xyz, {4,1,5}, deAoutB     V 7: xyz, {4,1,5}, deAoutB
V 8: xyz, {5,1,2}, deAoutB     V 8: xyz, {5,1,2}, deAoutB

V19: xyz, {10,1,5}, Nou        V23: xyz, {11,1,10}, Nou
V20: xyz, {8,1,5},  Nou        V24: xyz, {8,1,11},  Nou
V21: xyz, {12,1,10},Nou        V25: xyz, {12,1,10}, Nou
V22: xyz, {8,1,12}, Nou        V26: xyz, {8,1,12},  Nou
      Observació: per facilitar l'algorisme posterior de seqüenciar els vèrtexs, hem fet una rotació circular dins de cada llista de cares per tal que la cara que estem reconstruïnt (la cara 1) es trobi al mig. Si tinguéssim algun vèrtex amb més de tres cares a la seva llista, només caldria conservar-ne (en aquesta fase) tres: la cara que estem reconstruïnt i les seves cares anterior i posterior a la llista circular. Per tant, el resultat de l'extracció de vèrtexs de la llista LV sempre té l'estructura que presentem aquí, amb llistes reduïdes de tres cares per vèrtex.

       Observació per a qui vulgui aprofundir: Tot i que aquí no ho fem, si es vol evitar indeterminacions en la reconstrucció de les cares, és bo imposar un sentit coherent a la subllista de cares de cada vèrtex. El sentit és un de predeterminat (horari o antihorari) quan observem el vèrtex en l'objecte final i des de fora de l'objecte. Això comporta que en alguns casos cal invertir la llista cíclica de cares. Observeu que el sentit depèn de l'operació concreta que estem fent: un mateix vèrtex pot requerir sentits diferents a la llista de les seves cares segons si estem fent una operacio d'unió o una de diferència.
       
       

      1. Apliquem ara l'algorisme del "dòmino" a l'exemple 1: Podem formar la cadena (el que teniu a sota de cada fletxa es la cara que conecta els dos vèrtexs en l'algorisme del dòmino) següent:
        2. V3 ------> V4 ------> V8 ------> ?
   Cara 6     Cara 2     Cara 5
        El problema és que ara tenim tres vèrtexs candidats a ser els seguents de V8 compartint la cara 5: els 7, 19 i 20. Cal desfer la indeterminació. Aixo es pot fer de dues maneres:
        • Trobant el vèrtex més proper en la direcció i sentit de l'aresta que estem reconstruïnt (el sentit es pot trobar sabent els vectors normals de les cares adjacents i tenint la informacio de si l'aresta que estem reconstruïnt és convexa o còncava, vegeu la pàgina dels tests geomètrics).
        • Ordenant, a l'espai, els vèrtexs alineats que produeixen la indeterminació (l'ordenació es fa segons una de les seves coordenades o el valor del paràmetre en l'equació paramètrica de la recta de suport de l'aresta, vegeu la pàgina dels tests geomètrics): V8, V20, V19, V7 i agrupant per parelles els vèrtexs ordenats. Com que evidentment les arestes finals es corresponen amb aquestes parelles, podem concloure que tenim dues arestes alineades V8 - V20 i V19 - V7, i per tant el seguent de V8 es V20.
        Un cop sabem que el següent de V8 és V20, podem continuar la reconstrucció de la cara fins que tanquem el cicle de vèrtexs i tornem a V3: 
        V8 ------> V20 ------> V22 ------> V21 -------> V19 
   Cara 5      Cara 8     Cara 12      Cara 10   |
                                                 |
                                                 | Cara 5
                                                 |
                                                 |
                                V3 <------ V7 <--
                                    Cara 4
        Observeu que hem reconstruït una cara amb un sol polígon que té com a vèrtexs 
         V3, V4, V8, V20, V22, V21, V19 i V7.
      2. Apliquem ara l'algorisme del "dòmino" a l'exemple 2: Podem formar la cadena (el que teniu a sota de cada fletxa és la cara que connecta els dos vèrtexs en l'algorisme del dòmino) següent:

        3. V3 ------> V4 ------> V8 ------> V7 ------> V3
   Cara 6     Cara 2     Cara 5     Cara 4
        amb això hem tancat un cicle, pero el problema es que no hem passat per tots els vertexs de la subllista de la cara 1. Això ens indica que la nova cara de A - B que correspon a la cara 1 de A, té més d'un polígon. Continuem la reconstrucció amb els vèrtexs que ens queden: 
        V23 -------> V24 ------> V26 -------> V25 -------> V23
    Cara 11      Cara 8      Cara 12      Cara 10
        Observeu que hem reconstruït una cara amb dos polígons que tenen com a vèrtexs, 
                         V3, V4, V8 i V7

                 V23, V24, V26 i V25
        Finalment falta encara fer dues coses:
         
        • Cal comprovar que el sentit de les semiarestes a cada polígon és el correcte (en el cas que les llistes cícliques de cares estiguin orientades en sentit horari o antihorari des de fora de l'objecte final no cal fer aquesta comprovació ja que l'algorisme del dòmino ja ens dona el sentit correcte de les semiarestes). Observeu que el sentit del vector normal de les cares de l'objecte final és sempre el de la cara corresponent de A o B, excepte en el cas que sigui una cara de l'objecte sustraend B en una operació de resta A - B.
        • Cal comprovar que el sentit de les semiarestes a cada polígon és el correcte (en el cas que les llistes cícliques de cares estiguin orientades en sentit horari o antihorari des de fora de l'objecte final no cal fer aquesta comprovació). Observeu que el sentit del vector normal de les cares de l'objecte final és sempre el de la cara corresponent de A o B, excepte en el cas que sigui una cara de l'objecte sustraend B en una operació de resta A - B -- cal detectar quin polígon es l'extern de la cara i quin és el polígon forat. En aquest cas, el segon polígon es el poligon forat ja que podem comprovar que un vèrtex qualsevol - per exemple el V23 - és interior a l'altre polígon V3, V4, V8, V7 (vegeu la pàgina dels tests geomètrics).