Miglior metodo di selezione della casella per un clone Minecraft

Question

Sto creando un clone di Minecraft come il mio primo progetto OpenGL e sono bloccato nella parte di selezione della casella. Quale sarebbe il metodo migliore per effettuare una selezione affidabile di scatole?

Ho eseguito alcuni algoritmi AABB, ma nessuno di loro spiega abbastanza bene quello che fanno esattamente (specialmente quelli super-ottimizzati) e non voglio usare cose che non capisco.

Dal momento che il mondo è composto da cubetti ho usato octrees di rimuovere qualche tensione sui calcoli del cast ray, in fondo l'unica cosa che serve è questa funzione:

float cube_intersect(Vector ray, Vector origin, Vector min, Vector max) 
{ 
    //??? 
} 

Il raggio e l'origine sono facilmente reperibili con

Vector ray, origin, point_far; 
double mx, my, mz; 

gluUnProject(viewport[2]/2, viewport[3]/2, 1.0, (double*)modelview, (double*)projection, viewport, &mx, &my, &mz); 
point_far = Vector(mx, my, mz); 
gluUnProject(viewport[2]/2, viewport[3]/2, 0.0, (double*)modelview, (double*)projection, viewport, &mx, &my, &mz); 
origin = Vector(mx, my, mz); 
ray = point_far-origin; 

min e max sono gli angoli opposti di un cubo.

Non sono nemmeno sicuro che questo sia il modo giusto per farlo, considerando il numero di cubi che dovrei controllare, anche con gli ocrees.

Ho anche provato gluProject, funziona, ma è molto inaffidabile e non mi dà la faccia selezionata del cubo.

---

EDIT

Quindi questo è quello che ho fatto: calcolare una posizione nello spazio con raggio:

float t = 0; 
for(int i=0; i<10; i++) 
{ 
    Vector p = ray*t+origin; 
    while(visible octree) 
    { 
     if(p inside octree) 
     { 
      // then call recursive function until a cube is found 
      break; 
     } 
     octree = octree->next; 
    } 
    if(found a cube) 
    { 
     break; 
    } 
    t += .5; 
} 

In realtà è sorprendentemente veloce e si ferma dopo il primo trovato cubo .

Come si può vedere il raggio deve andare trogolo più octrees prima che trovi un cubo (in realtà una posizione nello spazio) - c'è un mirino al centro dello schermo. Più basso è il passo di incremento, più precisa è la selezione, ma anche più lenta.

Answer 1

Il lavoro con le scatole come primitive è eccessivo nei requisiti di memoria e potenza di elaborazione. I cubi vanno bene per il rendering e anche lì puoi trovare algoritmi più avanzati che ti danno un'immagine finale migliore (cubetti in marcia). La grafica di Minecraft è molto primitiva in questo senso poiché il rendering di voxel è in circolazione da molto tempo e sono stati compiuti progressi significativi.

In pratica si dovrebbe sfruttare il fatto che tutte le caselle sono equidistanti e della stessa dimensione. Questi sono chiamati voxel. Il raycasting in una griglia è banale in confronto a quello che si ha: un test di stato AABB a fase ampia e una fase stretta. Vi suggerisco di cercare un po 'su voxel e voxel impostare il rilevamento/raycasting delle collisioni in quanto troverete sia algoritmi che sono più facili da implementare che più veloci.

Answer 2

Non è necessaria alcuna struttura di octree esplicita in memoria. Tutto ciò che serve è il byte [,,]. Basta generare 8 bambini di una casella pigramente durante la ricerca (come un motore di scacchi genera stati di gioco per bambini).

Answer 3

Vorrei anche sostenere che non è necessario affidarsi ai raycasts reali per determinare cosa eseguire il rendering. Dato che sei in una griglia predefinita, non sei davvero tenuto in ostaggio ai requisiti "esatti visibili".Se è possibile monitorare la posizione della fotocamera e allocare una bussola NSWE di alcune specie è anche possibile utilizzare che per determinare se il buffer GPU dovrebbe anche prendere in considerazione serie di vertici di per il rendering ..

copro questa teoria in dettaglio qui https://stackoverflow.com/a/18028366/94167

Ma usando il posizionamento di Octree e Camera + distanza/limiti della telecamera, in pratica sai cosa l'utente vede senza dover ricorrere a Raytrace (s) per gli esatti? Se è possibile consolidare i triangoli in quelli più grandi per scopi di rendering e quindi utilizzare una texture per rompere la visibilità del dorso di grandi dimensioni su una forma cubica (leggera della mano) si riduce significativamente il numero di vertici. Quindi è solo questione di scovare lo scafo e tenere traccia di quale sia la direzione della tua telecamera e dove si trova xyz puoi farla franca lasciando che alcuni volti non vengano visualizzati in quanto avrà un impatto minimo sulle prestazioni (specialmente se i tuoi shader fanno anche parte del lavoro)

Sto sperimentando ulteriormente rintracciando il punto centrale della telecamera per determinare il suo punto focale orizzontale e da quello puoi determinare l'angolo che a sua volta determina la profondità del pezzo che probabilmente vedrai nella direzione in cui si trova.