Struttura dati per determinare l'intersezione tra linea e poligono in 3D

Question

Struttura dati per determinare l'intersezione tra linea e poligono in 3D

#1 da (2 voti)
#2 da (1 voti)

7

Ho una collezione di poligoni semplici non sovrapposti a sé P. In realtà, sono triangoli 2D nello spazio 3D.

Sto cercando una struttura dati che, data una linea L, abbia una ricerca relativamente veloce per tutti i poligoni p in P con cui L interseca. Se può darmi il punto di intersezione, questo è un bonus, ma posso calcolarlo da solo se ottengo solo i poligoni, in ogni caso.

Ho già usato alberi kd e alberi rosso-neri, ma come quelli che trattano i punti, spero che ci sia una struttura dati più adatta al mio problema. Mi aspetto che sia una sorta di albero BSP, ma sono aperto ad altri suggerimenti.

algorithms graphics 3d

posta elsurudo 07.04.2016 - 12:53

fonte

2 risposte

Leggi altre domande sui tag algorithms graphics 3d

Come organizzare il lavoro per un team che fornisce 3 prodotti connessi ma distinti e resta agile I task intensivi / dati intensivi della CPU appartengono al server

score 2 · Answer 1

Potresti provare a utilizzare un ottetto per questo. Questo non ti darà esattamente il set di poligoni che stai cercando, ma un superset che potrebbe essere significativamente più piccolo dell'intero set di poligoni (ovviamente, quanto bene funzioni dipende dai poligoni e da come sono distribuiti nello spazio).

Scegli una certa "profondità massima" per l'albero che è appropriata per la scala del tuo problema. Associa ad ogni cubo "foglia" i poligoni la cui casella di delimitazione tocca quel cubo. Quando si cercano i poligoni, determinare i cubi foglia che vengono toccati dalla linea e prendere in considerazione solo i poligoni associati.

score 1 · Answer 2

Se la tua scena è statica (cioè i tuoi triangoli non si muovono, quindi puoi ammortizzare la costruzione della tua infrastruttura di accelerazione su tutte le linee), allora credo che l'albero di kd ottimizzato in modo ottimale è ancora allo stato dell'arte per questo scopo. Poiché hanno un'estensione finita, i tuoi triangoli potrebbero sovrapporsi a più di un ramo dell'albero kd-tree; tuttavia, ciò vale per qualsiasi struttura di accelerazione di tipo BSP.

Una classe alternativa di struttura di accelerazione è esemplificata dalla R-tree . Come il kd-tree, i nodi R-tree hanno caselle di delimitazione allineate all'asse; tuttavia, in un albero R, le caselle di delimitazione dei nodi fratelli potrebbero sovrapporsi.

In senso generale, le strutture di accelerazione più conosciute sono simili a R-tree o BSP.