Come trovare se un oggetto 3D si adatta a un altro oggetto 3D (il contenitore)?

Dato due oggetti 3d, come posso trovare se uno si inserisce all'interno del secondo (e trovare la posizione dell'oggetto nel contenitore).Come trovare se un oggetto 3D si adatta a un altro oggetto 3D (il contenitore)?

L'oggetto deve essere tradotto e ruotato per adattarsi al contenitore, ma non modificato diversamente.

complicazioni aggiuntive:

La stessa situazione - ma cercare la migliore soluzione in forma, anche se non è una partita corretta (ridurre al minimo il volume dell'oggetto che non rientra nel contenitore)
supporto per gli oggetti elastici - trovare la soluzione migliore, riducendo al minimo la "distorsione" negli oggetti

Questa è una domanda abbastanza generale - e non mi aspetto una soluzione completa. Eventuali riferimenti a documenti pertinenti \ articoli \ librerie \ strumenti sarebbero utili

fonte

2013-01-12 Ophir Yoktan

Soluzione ingenua: controllare tutte le possibili coppie di facce per le intersezioni. –

Non ero abbastanza chiaro - il primo oggetto dovrebbe essere spostato \ ruotato per adattarsi al contenitore –

Ah. Allora questo è complicato! –

Ecco un metodo forse meno ideale.

Si potrebbe provare a fissare la posizione (nello spazio 3D) di 1 forma. Posizionando l'altra forma sopra quella forma. Quindi creare collegamenti che collegano un punto di forma a un punto nell'altra forma. Quindi simulare cosa succede quando i collegamenti vengono tirati in modo uguale. Causando il punto che non è fisso per ruotare e tradurre fino a quando non è stabile.

Se la posizione è sufficientemente ampia, è possibile utilizzare solo 3 collegamenti (il numero minimo di collegamenti per il 3D) e provare tutte le possibili combinazioni. Tuttavia, per un fit più aderente, avrai bisogno di più collegamenti, forse abbastanza per posizionarli su ogni punto della forma con il minor numero di punti. Il che significa che avrai un metodo per determinare come posizionare i link, il che non è banale.

fonte

2013-01-13 00:07:18 Nuclearman

Si presuppone che io sappia quale punto nell'oggetto dovrebbe essere vicino a un punto specifico nel contenitore –

Ed è per questo che non è l'ideale, poiché determinare ciò non è facile, quindi perché è necessario provare ogni combinazione limitata. I due metodi (il secondo che utilizza tutti i punti del punto più piccolo) che ho descritto richiedono le combinazioni O (N^3) più tutto ciò che serve per fare tutte le simulazioni, e troverà le misure che sono "sciolte" (pensa un quadrato all'interno di un ottagono) o "stretto" (si pensi a un quadrato all'interno di un quadrato leggermente più grande), ma potrebbe non funzionare sulle cose intermedie. Anche se, penso che potrei sottovalutare l'algoritmo tight fit, in quanto potrebbe essere sufficiente da solo. – Nuclearman

Poi di nuovo, se hai 100.000+ punti, O (N^3) o O (N^2) (vestibilità stretta nuda minima), probabilmente non è pratico. In tal caso, si spera che qualcuno conosca un metodo migliore. – Nuclearman

Questo sembra un problema abbastanza difficile. L'approccio probabile è quello di avere un certo euristico per suggerire la trasformazione e che il controllo è buono. Se la trasformazione sposta l'oggetto solo leggermente all'esterno (ad esempio su una parte) piuttosto che adattarsi leggermente alla trasformazione e testarla. Se l'oggetto è "molto" fuori (ad esempio sullo stesso asse/tutti su entrambi i lati) di fare una nuova ipotesi euristica.

Solo un'idea generale per un euristico. Crea una rasterizzazione di un oggetto con le stesse dimensioni dei pixel. Può essere l'ottano di un volume di oggetto. Crea un grafico di connettività tra i pixel. Controlla l'isomorfismo del sottografo tra i grafici. Se c'è un sottografo di quella posizione è per un test.

Questo approccio supporta anche rotazione di 90 gradi.

Alcuni test possono essere eseguiti anche su grafici. Se tutti i vicini di volume di un sottografo si trovano in un grafico più grande, rispetto all'oggetto.

In generale, questo è l'approccio del riquadro di confine 'raffinato'.

fonte

2013-01-13 13:21:04 Ante

Un'altra soluzione consiste nel proiettare un numero uguale di punti su entrambi gli oggetti e fare i minimi quadrati che si adattano meglio ai set di punti. Gli insiemi di punti probabilmente non saranno ordinati allo stesso modo, quindi iterando tra il miglior adattamento dei minimi quadrati e un riordino dei punti in modo che i punti su entrambi gli oggetti siano vicini allo stesso ordine. Lo sviluppo dell'equazione per questo è molto algebrico ma non concettualmente complicato.

fonte

2014-02-03 19:24:50 JimR

Considera un poligono (triangolo) nell'oggetto di destinazione. Per questo poligono, trova il poligono equivalente nell'altra geometria (sorgente), es.la lunghezza dei lati, l'angolo tra i bordi, l'area dovrebbe essere la stessa. Se c'è una sola corrispondenza, trova la matrice di trasformazione rigida, che altera i vertici in questo modo: X' = M*X. Poiché X' E X sono noti per tutti i punti sui poligoni corrispondenti, ciò dovrebbe essere possibile con l'algebra lineare.

Se si desidera una mappatura one-one tra i vertici del poligono, attraversare i bordi dei poligoni nello stesso ordine e creare una tabella di ricerca che mappa ciascun vertice da un poli a un vertice in un altro. Se hai un half edge data structure del tuo oggetto 3d che semplificherà questo processo molto.

Se si trova più di un poligono corrispondente, attraversare il poligono di origine da entrambi i punti e mantenere la corrispondenza dei poligoni adiacenti con i poligoni di destinazione. Continua fino a quando una di esse si interrompe, dopodiché puoi eseguire gli stessi passaggi della versione a una sola partita.

Ci sono soluzioni più serie che sono elencate here, ma penso che il metodo sopra funzionerà pure.

fonte

2014-02-03 23:08:25

Come trovare se un oggetto 3D si adatta a un altro oggetto 3D (il contenitore)?

risposta

Problemi correlati