Rilevamento delle collisioni: Comprendere le intersezioni visive nella visione artificiale

Di Fouad Sabry

Che cos'è il rilevamento delle collisioni

Il rilevamento delle collisioni è il problema computazionale di rilevamento di un'intersezione di due o più oggetti spaziali, comunemente oggetti di grafica computerizzata. Ha applicazioni in vari campi informatici, principalmente nella computer grafica, nei giochi per computer, nelle simulazioni al computer, nella robotica e nella fisica computazionale. Il rilevamento delle collisioni è un classico problema di geometria computazionale. Gli algoritmi di rilevamento delle collisioni possono essere suddivisi in operazioni su oggetti spaziali 2D o 3D.

Come trarrai vantaggio

(I) Approfondimenti e convalide sui seguenti aspetti argomenti:

Capitolo 1: Rilevamento delle collisioni

Capitolo 2: Ray tracing (grafica)

Capitolo 3: Partizionamento binario dello spazio

Capitolo 4: Centroide

Capitolo 5: Ramo e limite

Capitolo 6: Punto di fuga

Capitolo 7: Quadtree

Capitolo 8: Delimitazione volume

Capitolo 9: Rilevamento del ciclo

Capitolo 10: Disposizione delle linee

(II) Rispondere alle principali domande del pubblico sul rilevamento delle collisioni.

(III) Esempi reali di utilizzo del rilevamento delle collisioni in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati , appassionati, hobbisti e coloro che vogliono andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di rilevamento delle collisioni.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 4 mag 2024

Anteprima del libro

Capitolo 1: Rilevamento delle collisioni

La sfida del computer di rilevare l'intersezione di due o più oggetti è nota come rilevamento delle collisioni. Il rilevamento delle collisioni è un problema classico della geometria computazionale e ha applicazioni in una varietà di domini informatici, in particolare la computer grafica, i giochi per computer, le simulazioni al computer, la robotica e la fisica computazionale. Le tecniche di rilevamento delle collisioni 2D e 3D possono essere distinte in base alle rispettive dimensioni dell'oggetto.

La simulazione fisica prevede l'esecuzione di test come giocare a biliardo. Sotto l'ombrello del movimento del corpo rigido e delle collisioni elastiche, la meccanica delle palle da biliardo che rimbalzano è ben compresa. Una prima descrizione della circostanza includerebbe una descrizione fisica dettagliata del tavolo da biliardo e delle palline, nonché le posizioni di partenza di ciascuna palla. Data una forza impartita alla bilia battente (spesso la conseguenza di un giocatore che colpisce la bilia con la sua stecca), desideriamo utilizzare un programma per computer per determinare le traiettorie, il movimento preciso e le posizioni di riposo finali di tutte le palline. Una simulazione di questo gioco richiederebbe più moduli, uno dei quali sarebbe responsabile del calcolo delle esatte collisioni tra le palle da biliardo. Una piccola imprecisione in qualsiasi calcolo si tradurrà in cambiamenti drammatici nella posizione finale delle palle da biliardo, come dimostrato da questo esempio.

I criteri per i videogiochi sono comparabili, con cambiamenti significativi. La simulazione al computer deve imitare la fisica del mondo reale nel modo più accurato possibile, mentre i giochi per computer devono simulare la fisica del mondo reale in modo accettabile, in tempo reale e con sufficiente resilienza. Finché la simulazione risultante è soddisfacente per i giocatori del gioco, i compromessi sono consentiti.

Diversi simulatori fisici rispondono in modo diverso alle collisioni. Alcuni usano la morbidezza del materiale per calcolare una forza che risolverà la collisione in fasi temporali successive, come farebbe nella realtà. A causa della durezza di alcuni materiali, ciò richiede una grande potenza di elaborazione. Alcuni simulatori stimano il tempo di collisione utilizzando l'interpolazione lineare, ripristinano la simulazione, quindi calcolano la collisione utilizzando approcci più astratti basati su principi di conservazione.

Alcuni iterano l'interpolazione lineare (approccio di Newton) per calcolare il tempo di collisione con una precisione significativamente maggiore rispetto al resto della simulazione. Utilizzando la coerenza temporale, il rilevamento delle collisioni consente fasi temporali sempre più precise senza aumentare significativamente la domanda di CPU, come nel controllo del traffico aereo.

Dopo una collisione anelastica possono verificarsi stati speciali di scorrimento e riposo e Open Dynamics Engine utilizza vincoli per modellarli. I vincoli impediscono l'inerzia e, di conseguenza, l'instabilità. L'implementazione del riposo tramite un grafico della scena impedisce la deriva.

In altre parole, i simulatori fisici in genere rilevano le collisioni a posteriori (dopo che si è verificata la collisione) o a priori (prima che si verifichi la collisione) (prima che si verifichi la collisione). Oltre alla distinzione tra a posteriori e a priori, praticamente tutti i recenti algoritmi di rilevamento delle collisioni sono organizzati gerarchicamente. Tipicamente, discreto e continuo sono usati invece di a posteriori e a priori.

Nell'istanza a posteriori, la simulazione fisica viene fatta avanzare di una piccola quantità e quindi viene determinato se gli oggetti si sovrappongono o sono visibilmente considerati intersecati. Ad ogni fase della simulazione, le posizioni e le traiettorie di tutti i corpi che si intersecano sono fisse per tenere conto della collisione. Questo metodo viene definito a posteriori poiché generalmente non rileva il momento esatto dell'impatto e lo rileva solo a posteriori.

Negli approcci a priori, esiste un algoritmo di rilevamento delle collisioni in grado di prevedere le traiettorie dei corpi fisici con grande precisione. Gli istanti di collisione sono calcolati con precisione, e i corpi fisici non si scontrano mai veramente. Questo è definito a priori perché il metodo di rilevamento delle collisioni calcola gli istanti di collisione prima di aggiornare la configurazione dei corpi fisici.

I principali vantaggi degli approcci a posteriori sono i seguenti. All'algoritmo viene fornito un semplice elenco di corpi fisici e il programma produce un elenco di corpi che si intersecano. La tecnica di rilevamento delle collisioni non richiede la conoscenza dell'attrito, delle collisioni elastiche o anelastiche o dei corpi deformabili. Inoltre, gli algoritmi a posteriori sono una dimensione più semplici delle loro controparti a priori. La variabile tempo è omessa dal problema a posteriori, che richiede un algoritmo a priori.

D'altra parte, gli algoritmi a posteriori presentano problemi durante la fase di correzione, in cui le intersezioni fisicamente errate devono essere riparate. Inoltre, se il passo discreto è troppo grande, la collisione potrebbe non essere riconosciuta, con il risultato che un oggetto passa attraverso un altro se è sufficientemente veloce o piccolo.

I vantaggi degli algoritmi a priori sono una maggiore precisione e coerenza. Separare la simulazione fisica dal metodo di rilevamento delle collisioni è difficile (anche se non impossibile). In tutte le circostanze, tranne le più semplici, tuttavia, il problema di prevedere quando due corpi si scontreranno (dati i dati iniziali) non ha una soluzione in forma chiusa: in genere è necessario un cercatore numerico di radici.

Ad esempio, un vaso appoggiato su un tavolo è in contatto di riposo, o collisione, ma non salta né si compenetra. Il contatto a riposo richiede sempre un trattamento specifico: se due elementi si scontrano (a posteriori) o scivolano (a priori) e la loro velocità relativa è inferiore a una soglia, l'attrito diventa attrito ed entrambi gli oggetti sono posizionati sullo stesso ramo del grafico della scena.

I metodi convenzionali per rilevare le collisioni tra diversi oggetti sono estremamente lenti. Ovviamente, confrontare ogni oggetto con ogni altro oggetto funzionerà, ma è uno spreco quando il numero di oggetti è significativo. Il controllo di oggetti a geometria complessa l'uno rispetto all'altro in modo convenzionale, confrontando ogni faccia con ogni altra faccia, è un processo che richiede molto tempo. Pertanto, sono stati condotti studi sostanziali per accelerare la soluzione del problema.

In molte applicazioni, la configurazione dei corpi fisici varia poco da una fase temporale all'altra. Molti degli oggetti possono essere immobili. Gli algoritmi sono stati creati in modo tale che i calcoli eseguiti in una fase temporale precedente possano essere utilizzati nella fase temporale corrente, risultando in un calcolo più veloce.

Al livello grossolano del rilevamento delle collisioni, l'obiettivo è identificare coppie di oggetti che potrebbero potenzialmente entrare in collisione. Queste coppie richiederanno ulteriori indagini. Usando riquadri di delimitazione allineati agli assi per tutti gli n corpi nell'immagine, Ming C. Lin dell'Università della California, Berkeley [1] ha creato un primo metodo con alte prestazioni per questo scopo.

Ogni casella è indicata dal prodotto di tre intervalli (cioè 1, 2 e 3), una casella sarebbe

I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]

).

Sweep and Prune è una tecnica tipica per il rilevamento delle collisioni dei riquadri di delimitazione.

Si osservi che ci sono due caselle di questo tipo, I_{1}\times I_{2}\times I_{3} e  si J_{1}\times J_{2}\times J_{3} intersecano se, così come se, I_{1} si intersecano J_{1} , I_{2} si intersecano J_{2} e I_{3} si intersecano J_3 .

Si prevede che, da un passo temporale al successivo, se I_{k} e J_{k} si intersecano, allora è molto probabile che continueranno a sovrapporsi al passo temporale successivo.

Allo stesso modo, se non si sono intersecati durante la fase temporale precedente, allora non lo faranno ora, quindi probabilmente continueranno a non farlo.

Pertanto, semplifichiamo la questione a quella del tracciamento, da immagine a immagine, di quali intervalli di intersezione esistono.

Abbiamo tre liste di intervalli (una per ogni asse) e tutte le liste hanno la stessa lunghezza (poiché ogni lista ha lunghezza n , la quantità di riquadri di confine. In ogni elenco, ogni intervallo può intersecarsi con ogni altro intervallo nell'elenco.

Quindi per ogni lista, avremo una n\times n matrice M=(m_{{ij}}) di zeri e uno: m_{ij} è 1 se gli intervalli i e j si intersecano, 0 se le due rette non si intersecano.

Secondo la nostra stima, la matrice M associata a una lista di intervalli rimarrà sostanzialmente invariata da un passo temporale all'altro.

Per utilizzare questo, in realtà, l'elenco degli intervalli viene mantenuto come un elenco di endpoint etichettati.

Ogni elemento dell'elenco contiene le coordinate finali di un intervallo, oltre a un numero intero distinto che identifica tale intervallo.

Quindi, l'elenco è ordinato in base alle coordinate e aggiorniamo la matrice M man mano che procediamo.

Se la configurazione dei riquadri di delimitazione non cambia molto da un passo temporale all'altro, non è difficile pensare che questo metodo verrà eseguito abbastanza rapidamente.

Nel caso di corpi deformabili, come