More Related Content
Similar to Tesi2 (20)
Tesi2
- 1. RELATORE: Prof. Serafino Cicerone Studio e implementazione di algoritmi di approssimazione poligonale octilineare LAUREANDO: Andrea Marotta Laurea Triennale Ingegneria Informatica-Automatica
- 2. Contesto Una Printed Circuit Board in elettronica 竪 un componente adibito a fungere le seguenti funzioni principali: collegamento elettrico supporto meccanico per i componenti
- 3. Rumore nelle PCB Specifiche sempre pi湛 restrittive in termini di spazio e frequenza Impedenze, capacit o induttanze parassite, attraverso le quali il rumore si propaga Necessit di un modello
- 4. Cavity Model Permette di individuare fonti di capacit parassite generate da zone conduttive disposte su layer diversi della board
- 5. Cavity Identification Tool Strumento a supporto dei progettisti per lindividuazione di cavit nella board: Identificazione cavit Trasformazione cavit in dataset geometrico Elaborazione dataset geometrico Approssimazione del dataset geometrico Decomposizione in rettangoli e triangoli Calcolo capacit parassite (Cavity Solver)
- 6. Approssimazione dataset geometrico Serafino Cicerone and Matteo Cermignani. Fast and Simple Approach for Polygon Schematization. 12th International Conference on Computational Science and Applications (ICCSA'12), volume 7333 of Lecture Notes in Computer Science, pages 267-279. Springer, 2012. Esigenza di produrre poligoni octilineari: Sviluppo di un algoritmo Obiettivo del lavoro di tesi: Migliorare lalgoritmo preesistente Estenderne le capacit Confronto con altra soluzione presente in letteratura
- 7. Approssimazione Poligonale Problema affrontato in letteratura in virt湛 delle numerosissime applicazioni (Computer Grafica, GIS, ) Si definisce approssimazione di un poligono P = <p1,p2, p3,,pn> un altro poligono P = <p1, p2, p3, , pm> tale che m<<n e che lo scostamento delle linee di P da quelle di P sia minore di un errore prefissato secondo uno specifico criterio
- 8. Approssimazione Poligonale (2) Diversi approcci: Approssimazione Locale Sequential Split & Merge Dominant Point Approssimazione Globale Diverse specifiche di errore:
- 9. Formalizzazione del problema Approssimazione Octilineare Segmenti Orizzontali, Verticali, Diagonali Errore di tipo 1 Problema minimum number Minor numero di lati possibile in output Minor tempo esecuzione possibile Soluzione di tipo locale, euristica
- 10. Octilinear Schematization Algorithm Obiettivi: Velocizzare soluzione pre-esistente Generalizzare lapprossimazione (introduzione del parametro di densit k)
- 11. Octilinear Schematization Algorithm(2) Idea di base: quantizzazione del piano Cartesiano
- 12. Octilinear Schematization Algorithm(2) Sei passi modulari: 1. Compute Approx Point 2. Compute Possible Segment 3. Compute Meet 4. Collinear Merge 5. Compute Path 6. Polygon Choice
- 13. Compute Approx Point A ciascun punto del poligono in input viene associato un insieme di punti approssimante
- 14. Compute Possible Segments Vengono identificati segmenti canonici tra Box adiacenti. Laddove possibile si uniscono le 束frontiere損 di tali box
- 15. Compute Possible Segments(2) Se non 竪 possibile individuare segmenti canonici si esegue RoutineSegment:
- 16. Routine Segment
- 17. Compute Meet Vengono 束riempiti損 i box mediante lindividuazione di segmenti canonici in grado di attraversarli
- 18. Compute Collinear Merge Viene effettuata una scrematura dei segmenti approssimanti individuando segmenti collineari ed adiacenti. Introduce discontinuit nellinsieme dei segmenti approssimanti
- 19. Compute Path Differentemente dal metodo Compute Meet congiunge discontinuit non colmabili attraverso un solo segmento canonico
- 20. Polygon Choice Modellazione mediante grafo orientato G(V,E) Algortimo BFS Cammino minimo tra vertice sorgente vs e vertice finale vf suo adiacente
- 21. Confronto Input: board 923 poligoni, 40694 punti Quasi Orthogonal Path Schematization: Octilinear Schematization Algorithm: Perch竪?
- 22. Conclusioni L'algoritmo rispetta l'obiettivo prefissato mantenendo la capacit di semplificazione del precedente e migliorandone notevolmente le prestazioni. A seguito dei test si pu嘆 concludere che la possibilit di fornire una misura della densit dell'approssimazione comporti un incremento notevole del tempo di esecuzione senza aumentare notevolmente la qualit dell'approssimazione.
Editor's Notes
- #3: Il lavoro che andiamo a presentare si sviluppa nel contesto della progettazione di Printed Circuit Board (o circuiti stampati) che sono componenti che hanno il compito di collegare elettricamente le diverse componenti dei circuiti elettronici ed al tempo stesso di fornire per essi supporto meccanico. Per esercitare queste funzioni le PCB pi湛 evolute si sviluppano su pi湛 strati di materiale caratterizzati da zone conduttivie (in rame) e zone non conduttive come si pu嘆 vedere nellimmagine. Alcuni di questi strati hanno la funzione di trasportare lalimentazione mentre altri dei segnali contenenti informazione.. Il collegamento tra un layer ed un altro (via) si ottiene praticando dei fori che vengono poi placcati elettricamente.
- #4: Il contesto teconologico in cui evolve lo sviluppo delle PCB si trova a dover fronteggiare richieste sempre pi湛 restrittive in termini di spazio (riduzione dimensione dispositivi) e frequenza (per migliorarne le performance). Tali specifiche si traducono in una progettazione sempre pi湛 sofisticata delle Printed Circuit Board. E necessario porre occuparsi delle problematiche derivanti da fonti di rumore quali interferenze elettromagnetiche o cambi di stato (spike) nei circuiti digitali. Nelle PCB per la loro conformazione possono formarsi imp, capa, ind.. Ci嘆 ha portato alla necessit di sviluppare un modello per individuarne le fonti e valutarne limpatto sui circuiti.
- #5: Il cavity model 竪 un modello che si occupa esclusivamente delle capacit parassite. Come si vede possono essere generate da zone conduttive poste parallellamente su layer diversi che separate da un dielettrico danno vit ad una capacit. Ne emerge il fortissimo legame che c竪 tra questa problematica e la geometria delle zone conduttive della board.
- #6: Dataset geometrica trasfomrma le zone conduttive in poligoni. Il focus del lavoro di tesi 竪 posto sullapprossimazione del dataset geometrico Decomposizione in rettangoli e triangoli=> necessit che lapprossimazione produca poligoni octilineari