Hierarchical Methods forFiltering and VisualizationBased on Graphics HardwareVon der Fakultat¨ Informatik, Elektrotechnik undInformationstechnik der Universitat¨ Stuttgartzur Erlangung der Wurde eines Doktors der¨Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlungvorgelegt vonMatthias Hopfaus Munchen¨Hauptberichter: Prof. Dr. Thomas ErtlMitberichter: Prof. Dr. Martin RumpfTag der mundlichen¨ Prufung:¨ 27.05.2004Institut fur¨ Visualisierung und Interaktive Systemeder Universitat¨ Stuttgart20043To my beloved parents and my dear friends.4G’Kar: (to Sakai)Narns, Humans, Centauri ...we all do what we do for the same reason:because it seems like a good idea at the time.Babylon 5, Mind WarContentsAcknowledgments 9Abstract and Chapter Summaries 13Zusammenfassung und Kapitelubersicht¨ 171 Introduction 211.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.1.1 Hierarchical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.1.2 Graphics Hardware Based Algorithms . . . . . . . . . . . . . . . . . . . 231.2 Context and Cooperation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 Background 252.1 3D Graphics Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.1.1 The Rendering Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.1.2 Vertex Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.1.