Partició binària de l'espai

El procés de fer un arbre de BSP

Partició binària de l'espai (BSP de l'anglés Binary Space Partitioning) és en informàtica un mètode per subdividir recursivament un espai a dos conjunts convexs mitjançant l'ús d'hiperplans com a particions. Aquest procés de subdivisió dona lloc a una representació d'objectes dins de l'espai en forma d'una estructura de dades en arbre coneguda com a arbre de BSP.

El particionament d'espai binari es va desenvolupar en el context de gràfics per ordinador 3D el 1969. L'estructura d'un arbre de BSP és útil en rendering perquè pot proporcionar informació espacial de manera eficient sobre els objectes d’una escena, com ara que s’ordenen objectes de davant a darrere respecte a un visor en una ubicació determinada. Altres aplicacions de BSP inclouen: realitzar operacions geomètriques amb formes (geometria sòlida constructiva) en CAD, detecció de col·lisió en robòtica i videojocs 3D, traçat de raigs i altres aplicacions que impliquen el maneig d’escenes espacials complexes, així com la creació d'arbres de decisió.

Visió general

La partició d'espai binari és un procés genèric de dividir recursivament una escena en dues fins que la partició compleix un o més requisits. Es pot veure com una generalització d'altres estructures d'arbres espacials, com ara K-d_trees i arbres quadtrees, una on els hiperplans que divideixen l'espai poden tenir qualsevol orientació, en lloc d'estar alineats amb els eixos de coordenades ja que es troben en arbres K-d o quadtrees. Quan s'utilitzen en gràfics per ordinador per representar escenes compostes per polígons plans, els plans de partició s'escullen sovint perquè coincideixin amb els plans definits pels polígons de l'escena.

L'elecció específica del pla de partició i el criteri per finalitzar el procés de partició varia en funció de la finalitat de l'arbre BSP. Per exemple, en la representació de gràfics per ordinador, l'escena es divideix fins que cada node de l'arbre BSP només conté polígons que es poden representar en ordre arbitrari. Quan s'utilitza l'eliminació de cara posterior, cada node, per tant, conté un conjunt convex de polígons, mentre que quan es representen polígons de doble cara, cada node de l'arbre BSP conté només polígons en un únic pla. En la detecció de col·lisions o el traçat de raigs, una escena es pot dividir en primitives sobre les quals les proves de col·lisió o intersecció de raigs són senzilles.

La partició de l'espai binari va sorgir de la necessitat d'infografia per dibuixar ràpidament escenes tridimensionals compostes per polígons. Una manera senzilla de dibuixar aquestes escenes és l'algorisme del pintor, que produeix polígons per ordre de distància de l'espectador, de darrere a davant, pintant sobre el fons i polígons anteriors amb cada objecte més proper. Aquest enfocament té dos inconvenients: el temps necessari per ordenar els polígons en ordre de darrere a davant i la possibilitat d'errors en els polígons superposats. Fuchs i els seus coautors van demostrar que la construcció d'un arbre BSP va resoldre tots dos problemes proporcionant un mètode ràpid d'ordenació de polígons respecte a un punt de vista determinat (lineal en el nombre de polígons de l'escena) i subdividint els polígons superposats a evitar errors que es poden produir amb l'algoritme del pintor. Un desavantatge de la partició de l'espai binari és que generar un arbre BSP pot consumir molt de temps. Per tant, normalment es realitza una vegada en geometria estàtica, com a pas previ al càlcul, abans de la representació o d'altres operacions en temps real en una escena. La despesa de construir un arbre BSP fa que sigui difícil i ineficient implementar directament objectes en moviment en un arbre.

Els videojocs en 3D utilitzen sovint els arbres BSP, especialment els shooters en primera persona i aquells amb entorns interiors. Els motors de joc que utilitzen arbres BSP inclouen els motors Doom (id Tech 1), Quake (variant id Tech 2), GoldSrc i Source. En ells, els arbres BSP que contenen la geometria estàtica d'una escena s'utilitzen sovint juntament amb un buffer Z, per combinar correctament objectes mòbils com ara portes i personatges a l'escena de fons. Tot i que la partició de l'espai binari proporciona una manera convenient d'emmagatzemar i recuperar informació espacial sobre polígons d'una escena, no resol el problema de la determinació de la superfície visible .

Generació

L'ús canònic d'un arbre BSP és per representar polígons (que són de doble cara, és a dir, sense reduir la cara posterior) amb l'algorisme del pintor. Cada polígon es designa amb un costat frontal i un darrere que es podrien triar arbitràriament i només afecten l'estructura de l'arbre, però no el resultat requerit. Aquest arbre es construeix a partir d’una llista sense classificar de tots els polígons d’una escena. L'algorisme recursiu per a la construcció d'un arbre BSP a partir d'aquesta llista de polígons és:

1. Trieu un polígon P de la llista.
2. Feu un node N a l’arbre BSP i afegiu P a la llista de polígons d’aquest node.
   1. Per a cada polígon de la llista:
      1. Si aquest polígon es troba completament al davant del pla que conté P, moveu aquest polígon a la llista de nodes que hi ha davant de P.
      2. Si aquest polígon es troba completament darrere del pla que conté P, moveu aquest polígon a la llista de nodes que hi ha darrere de P.
      3. Si aquest polígon està tallat pel pla que conté P, dividiu-lo en dos polígons i moveu-los a les respectives llistes de polígons darrere i davant de P.
      4. Si aquest polígon es troba al pla que conté P, afegiu-lo a la llista de polígons del node N.
3. Apliqueu aquest algorisme a la llista de polígons davant de P.
4. Apliqueu aquest algorisme a la llista de polígons darrere de P.

El diagrama següent il·lustra l'ús d'aquest algorisme per convertir una llista de línies o polígons en un arbre BSP. En cadascun dels vuit passos (i.-viii.), l'algorisme anterior s'aplica a una llista de línies i s'afegeix un nou node a l'arbre.

	Comenceu amb una llista de línies (o en 3D, polígons) que componen l'escena. Als diagrames d'arbre, les llistes es denoten amb rectangles arrodonits i els nodes de l'arbre BSP amb cercles. En el diagrama espacial de les línies, la direcció escollida per ser el "front" d'una línia es denota amb una fletxa.	</img>
i.	Seguint els passos de l'algorisme anterior, Triem una línia, A, de la llista i,. . . ...afegiu-lo a un node. Dividim les línies restants de la llista en les del davant de A (és a dir B2, C2, D2), i els de darrere (B1, C1, D1). Primer processem les línies davant de A (en els passos ii–v),. . . ...seguit pels darreres (en els passos vi–vii).	</img>
ii.	Ara apliquem l'algorisme a la llista de línies davant A (que conté B2, C2, D2). Triem una línia, B2, l'afegim a un node i dividim la resta de la llista en aquelles línies que estan davant de B2 (D2) i les que hi ha darrere (C2, D3).	</img>
iii.	Trieu una línia, D2, de la llista de línies davant de B2 i A. És l'única línia de la llista, de manera que després d'afegir-la a un node, no cal fer res més.	</img>
iv.	Hem acabat amb les línies davant de B2, així que considereu les línies darrere de B2 (C2 i D3). Trieu un d'aquests (C2), afegiu-lo a un node i col·loqueu l'altra línia de la llista (D3) a la llista de línies davant de C2.	</img>
v.	Ara mireu la llista de línies davant de C2. Només hi ha una línia (D3), així que afegiu-la a un node i continueu.	</img>
vi.	Ara hem afegit totes les línies davant d'A a l'arbre BSP, de manera que ara comencem a la llista de línies darrere d'A. Escollint una línia (B1) d'aquesta llista, afegim B1 a un node i dividim la resta de la llista en línies davant de B1 (és a dir D1), i les línies darrere de B1 (és a dir C1).	</img>
vii.	Primer processant la llista de línies davant B1, D1 és l'única línia d'aquesta llista, així que afegiu-la a un node i continueu.	</img>
viii.	Mirant a continuació la llista de línies darrere de B1, l'única línia d'aquesta llista és C1, així que afegiu-ho a un node i l'arbre BSP s'haurà completat.	</img>

El número final dels polígons o les línies en un arbre és sovint més gran (de vegades molt més gran) que la llista original, des de línies o polígons que travessen el pla de partició ha de ser partit a dos. És desitjable de minimitzar aquest augment, però també per mantenir equilibri raonable en l'arbre final. L'elecció del qual el polígon o la línia és utilitzat com a pla de partició (al pas 1 de l'algoritme) és per això important dins creant un arbre de BSP eficaç.

Recorregut

Un arbre BSP es recorregut en un temps lineal, en un ordre determinat per la funció particular de l'arbre. De nou, utilitzant l'exemple de representació de polígons de doble cara mitjançant l'algorisme del pintor, per dibuixar correctament un polígon P cal dibuixar primer tots els polígons darrere del pla P, després el polígon P i finalment els polígons davant de P. Si aquest ordre de dibuix es compleix per a tots els polígons d'una escena, tota l'escena es renderitza en l'ordre correcte. Aquest procediment es pot implementar recorrent recursivament un arbre BSP utilitzant el següent algorisme. Des d'una ubicació de visualització determinada V, per representar un arbre BSP,

1. Si el node actual és un node fulla, renderitzeu els polígons al node actual.
2. En cas contrari, si la ubicació de visualització V és davant del node actual:
   1. Representeu l'arbre BSP fill que conté polígons darrere del node actual
   2. Representeu els polígons al node actual
   3. Representeu l'arbre BSP fill que conté polígons davant del node actual

3. En cas contrari, si la ubicació de visualització V es troba darrere del node actual:

1. Representeu l'arbre BSP fill que conté polígons davant del node actual
2. Representeu els polígons al node actual
3. Representeu l'arbre BSP fill que conté polígons darrere del node actual

4. En cas contrari, la ubicació de visualització V ha d’estar exactament al pla associat al node actual. Després:

1. Representeu l'arbre BSP fill que conté polígons davant del node actual
2. Representeu l'arbre BSP fill que conté polígons darrere del node actual

L'aplicació d'aquest algorisme de forma recursiva a l'arbre BSP generat anteriorment dona com a resultat els passos següents: L'arbre és recorregut en temps lineal i es pinten els polígons en un ordre llunyà-a-proper (D1, B1, C1, Un, D2, B2, C2, D3) adequat per l'algoritme del pintor.

Història dels arbres BSP

• 1969: Schumacker et al. publicar un informe que descrivia com es podrien utilitzar els plans col·locats amb cura en un entorn virtual per accelerar l'ordenació de polígons. La tècnica va utilitzar la coherència de profunditat, que estableix que un polígon a l'extrem del pla no pot, de cap manera, obstruir un polígon més proper. Això es va utilitzar en simuladors de vol fets per GE, així com per Evans i Sutherland. No obstant això, la creació de l'organització de dades poligonal la va realitzar manualment el dissenyador d'escenes.
• 1980: Fuchs et al. varen estendre la idea de Schumacker a la representació d'objectes 3D en un entorn virtual mitjançant l'ús de plans que coincideixen amb polígons per particionar recursivament l'espai 3D. Això va proporcionar una generació totalment automatitzada i algorítmica d'una estructura de dades poligonal jeràrquica coneguda com a arbre de partició de l'espai binari (Arbre BSP). El procés es va dur a terme com un pas de preprocessament fora de línia que es va realitzar una vegada per entorn/objecte. En temps d'execució, l'ordenació de la visibilitat depenent de la vista es va generar travessant l'arbre.
• 1981: Naylor's Ph.D. La tesi va proporcionar un desenvolupament complet dels dos arbres BSP i un enfocament teòric de grafs utilitzant components fortament connectats per a la visibilitat prèvia a la computació, així com la connexió entre els dos mètodes. Es van destacar els arbres BSP com a estructura de cerca espacial independent de la dimensió, amb aplicacions per a la determinació de superfícies visibles. La tesi també incloïa les primeres dades empíriques que demostraven que la mida de l'arbre i el nombre de nous polígons eren raonables (utilitzant un model del transbordador espacial).
• 1983: Fuchs et al. van descriure una implementació de microcodi de l'algorisme d'arbre BSP en un sistema de memòria intermèdia d'Ikonas. Aquesta va ser la primera demostració de la determinació de superfícies visibles en temps real mitjançant arbres BSP.
• 1987: Thibault i Naylor descriure com es poden representar poliedres arbitraris utilitzant un arbre BSP en oposició a la tradicional b-rep (representació de límits). Això va proporcionar una representació sòlida enfront d'una representació basada en la superfície. Les operacions de conjunt sobre poliedres es van descriure mitjançant una eina que permetia la geometria sòlida constructiva (CSG) en temps real. Aquest va ser el precursor del disseny de nivell BSP amb " pinzells ", introduït a l'editor Quake i recollit a l'Editor Unreal.
• 1990: Naylor, Amanatides i Thibault van proporcionar un algorisme per fusionar dos arbres BSP per formar un nou arbre BSP a partir dels dos arbres originals. Això proporciona molts avantatges, com ara la combinació d'objectes en moviment representats per arbres BSP amb un entorn estàtic (també representat per un arbre BSP), operacions CSG molt eficients sobre poliedres, detecció exacta de col·lisions en O (log n * log n) i un ordre adequat de transparents. superfícies contingudes en dos objectes que s'interpenetren (s'ha utilitzat per a un efecte de visió de raigs X).
• 1990: Teller i Séquin van proposar la generació fora de línia de conjunts potencialment visibles per accelerar la determinació de la superfície visible en entorns 2D ortogonals.
• 1991: Gordon i Chen [CHEN91] van descriure un mètode eficaç per realitzar una representació frontal a posterior des d'un arbre BSP, en lloc de l'enfocament tradicional d'esquena a davant. Van utilitzar una estructura de dades especial per registrar, de manera eficient, les parts de la pantalla que s'han dibuixat i les que encara s'han de representar. Aquest algorisme, juntament amb la descripció dels arbres BSP al llibre de text estàndard de gràfics per ordinador del moment (Computer Graphics: Principles and Practice) va ser utilitzat per John Carmack en la creació de Doom (videojoc).
• 1992: Teller 's Ph.D. La tesi va descriure la generació eficient de conjunts potencialment visibles com un pas de preprocessament per accelerar la determinació de superfícies visibles en temps real en entorns poligonals 3D arbitraris. Això es va utilitzar a Quake i va contribuir significativament al rendiment d'aquest joc.
• 1993: Naylor va respondre a la pregunta de què caracteritza un bon arbre BSP. Va utilitzar models de casos esperats (en lloc d'anàlisi del pitjor dels casos) per mesurar matemàticament el cost esperat de cercar un arbre i va utilitzar aquesta mesura per construir bons arbres BSP. Intuïtivament, l'arbre representa un objecte de manera multiresolució (més exactament, com un arbre d'aproximacions). Es dibuixen paral·lels amb codis Huffman i arbres de cerca binaris probabilistes.
• 1993: Hayder Radha Doctorat. La tesi va descriure mètodes de representació d'imatges (naturals) utilitzant arbres BSP. Això inclou el desenvolupament d'un marc de construcció d'arbre BSP òptim per a qualsevol imatge d'entrada arbitrària. Aquest marc es basa en una nova transformació d'imatge, coneguda com a transformació LPE (Least-Square-Error) de la línia de particions (LPE). La tesi d'H. Radha també va desenvolupar un marc òptim de compressió d'imatges amb distorsió de velocitat (RD) i enfocaments de manipulació d'imatges utilitzant arbres BSP.

Bibliografia

• Naylor, B.; Amanatides, J.; Thibualt, W. «Merging BSP Trees Yields Polyhedral Set Operations». ACM SIGGRAPH Computer Graphics, 24, 4, 8-1990, pàg. 115–124. DOI: 10.1145/97880.97892.
• Naylor, B. «Constructing Good Partitioning Trees». Graphics Interface, 5-1993.
• Chen, S.; Gordon, D. «Front-to-Back Display of BSP Trees». IEEE Computer Graphics & Algorithms, 11, 5, 9-1991, pàg. 79–85. DOI: 10.1109/38.90569.
• Radha, H.; Leoonardi, R.; Vetterli, M.; Naylor, B. «Binary space partitioning tree representation of images». Journal of Visual Communications and Image Processing, 2, 3, 1991, pàg. 201–221. DOI: 10.1016/1047-3203(91)90023-9.
• Radha, H.M.S. «Efficient image representation using binary space partitioning trees». Signal Processing, 35, 2, 1994, pàg. 174–181. DOI: 10.1016/0165-1684(94)90047-7.
• Radha, H.; Vetterli, M.; Leoonardi, R. «Image compression using binary space partitioning trees». IEEE Transactions on Image Processing, 5, 12, 12-1996, pàg. 1610–24. Bibcode: 1996ITIP....5.1610R. DOI: 10.1109/83.544569. PMID: 18290079.https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract
• de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O. «§12: Binary Space Partitions». A: Computational Geometry. 2a edició. Springer-Verlag, 2000, p. 251–265. ISBN 978-3-540-65620-3.  Describes a randomized Painter's Algorithm..
• Ericson, Christer. «8. BSP Tree Hierarchies». A: Real-Time collision detection. Morgan Kaufmann, 2005, p. 349–382. ISBN 1-55860-732-3. 

Vegeu també

• Octree
• Quadtree