Guió d'Operacions Booleanes

(entre objectes representats en BREP)

( Per a més detall, consulteu la pàgina de tests geomètrics ). També podeu consultar dos exemples detallats per a veure com treballa l'algorisme.

Graus de dificultat de l'algorisme:

• Cares planes, no coincidències.
• Cares planes, coincidències.
• Cares no planes: No coincidències / coincidències.
• Problemes de robustesa: casos de quasi coincidències.

Complexitat de l'algorisme:

• O(n*n), on n és el nombre de cares.

Algorisme basat en la classificació de cares (cares planes, sense coincidències)

( Per a més detall, consulteu la pàgina de tests geomètrics ):

• ALGORISME:

  IniLlistaCares(LC)
  Per cada cara c de A fer

  Tallar(c,B,LlistaCares)
  Afegir(LlistaCares,LC)

  fiper
  
  Per cada cara c de B fer

  Tallar(c,A,LlistaCares)
  Afegir(LlistaCares,LC)

  fiper
  
  IniSòlid(C)
  AfegirVèrtexs(LC,C)
  c:=PrimeraCara(LC)
  mentre no fi (LC) fer

  Cas
  unió  : Si c.tip = deAoutB ó c.tip = deBoutA llavors Afegir(c,C) fisi
  inters: Si c.tip = deAinB ó c.tip = deBinA llavors Afegir(c,C) fisi
  A-B : Si c.tip = deAoutB ó c.tip = deBinA llavors Afegir(c,C) fisi
  B-A : Si c.tip = deAinB ó c.tip = deBoutA llavors Afegir(c,C) fisi
  ficas
  c:= SeguentCara(LC)

  fimentre
  

• DADES:

  Els elements de la llista LC són tuples que contenen,

  • La geometria de la cara
  • La relació Cara->Llista de vèrtexs
  • El tipus de la cara: deAinB, deAoutB, deBinA, deBoutA

Algorisme basat en la classificació de vèrtexs (cares planes, sense coincidències)

( Per a més detall, consulteu la pàgina de tests geomètrics ). També podeu consultar dos exemples detallats per a veure com treballa l'algorisme.

• ALGORISME:

  IniLlistaVèrtexs(LV)
  AfegirVèrtexsSòlid(A,LV)
  AfegirVèrtexsSòlid(B,LV)
  
  Per cada aresta a de A fer

  Per cada cara c de B fer

  Si Intersecció(a,c) != NUL llavors Afegir(Intersecció(a,c),LV) fisi

  fiper

  fiper
  
  Per cada aresta a de B fer

  Per cada cara c de A fer

  Si Intersecció(a,c) != NUL llavors Afegir(Intersecció(a,c),LV) fisi

  fiper

  fiper
  
  IniSòlid(C)
  v:=PrimerVèrtex(LV)
  mentre no fi (LV) fer

  Si

  v.tip = NOU llavors Afegir(v,C)

  sino

  Cas
  unió  : Si v.tip = deAoutB ó v.tip = deBoutA llavors Afegir(v,C) fisi
  inters: Si v.tip = deAinB ó v.tip = deBinA llavors Afegir(v,C) fisi
  A-B : Si v.tip = deAoutB ó v.tip = deBinA llavors Afegir(v,C) fisi
  B-A : Si v.tip = deAinB ó v.tip = deBoutA llavors Afegir(v,C) fisi
  ficas
  

  fisi
  c:= SeguentVèrtex(LV)

  fimentre
  CanviRepresentacióInversaAJeràrquica(C)

• DADES:

  Els elements de la llista LV són tuples que contenen,

  • La geometria del vèrtex
  • La relació Vèrtex->Cara, amb les cares ordenades cíclicament
  • Informació sobre si les arestes que conflueixen al vèrtex són convexes / còncaves
  • El tipus de vèrtex: deAinB, deAoutB, deBinA, deBoutA, NOU