Includes bibliographical references (p. 51-57).

Habilitation - Universität, Stuttgart. / Description based on print version record. Includes bibliographical references (p. [249]-275) and index.

Habilitation - Universität, Stuttgart. / Description based on print version record. Includes bibliographical references (p. [249]-275) and index.

Includes bibliographical references (p. 106-115).

Habilitation - Universitat, Stuttgart. / Title from e-book title screen (viewed January 2, 2008). Includes bibliographical references (p. [249]-275) and index.

This dissertation deals with the problem of manipulating and storing an image using quadtrees. A quadtree is a tree in which each node has four ordered children or is a leaf. It can be used to represent an image via hierarchical decomposition. The image is broken into four regions. A region can be a solid color (homogeneous) or a mixture of colors (heterogeneous). If a region is heterogeneous it is broken into four subregions, and the process continues recursively until all subregions are homogeneous. The traditional quadtree suffers from dependence on the underlying grid. The grid coordinate system is implicit, and therefore fixed. The fixed coordinate system implies a rigid tree. A rigid tree cannot be translated, scaled, or rotated. Instead, a new tree must be built which is the result of one of these transformations. This dissertation introduces the independent quadtree. The independent quadtree is free of any underlying coordinate system. The tree is no longer rigid and can be easily translated, scaled, or rotated. Algorithms to perform these operations axe presented. The translation and rotation algorithms take constant time. The scaling algorithm has linear time in the number nodes in the tree. The disadvantage of independent quadtrees is the longer generation and display time. This dissertation also introduces an alternate method of hierarchical decomposition. This new method finds the largest homogeneous block with respect to the corners of the image. This block defines the division point for the decomposition. If the size of the block is below some cutoff point, it is deemed to be to small to make the overhead worthwhile and the traditional method is used instead. This new method is compared to the traditional method on randomly generated rectangles, triangles, and circles. The new method is shown to use significantly less space for all three test sets. The generation and display times are ambiguous. More time is taken for each node, but there are, on average, fewer nodes. The worst case is significantly worse.

Advances in hardware acceleration has resulted in development of a variety of hardware accelerated ray tracing libraries. The purpose of this bachelor thesis is to investigate if a simple ray tracer, based on a hardware accelerated ray tracing library, can achieve acceptable frame rates in rendering simple 3D game-related environments. Games are often associated with fast rasterization-based rendering techniques, but rasterization is limited where instead ray tracing holds many advantages. Background research was done to gain knowledge about related work, state-of-the-art in ray tracing and available hardware accelerated libraries. By using a method similar to Kanban and Scrum [36], the implementation was split up into different tasks, prioritizing the tasks of implementing basic functionalities of a ray tracer. A simple ray tracer was implemented based on the chosen library Embree, a framework developed at Intel Corporation. Results show that the scenes rendered in lower resolutions (800 x 600) are good candidates for having a stable frame rate of 30 FPS, which is not enough in order to render a real game. The standard of games today require high resolution (full HD 1920 x 1080) and complex scenes. Earlier studies show that Embree has potential of higher performance and looking back the performance of real-time ray tracing has improved, but is still limited to low resolutions and simple lighting and shading models. / Framsteg inom hårdvaruacceleration har resulterat i att en rad olika hårdvaruaccelererade bibliotek för strålföljning utvecklats. Syftet med denna kandidat-uppsats är att undersöka om en enkel strålföljare, baserad på ett hårdvaruaccelererat bibliotek för strålföljning, kan uppnå acceptabla bildfrekvenser vid rendering av enkla spel-relaterade miljöer i 3D. Datorspel förknippas ofta med snabba renderingstekniker. Rasteriseringsalgoritmen är dock begränsad där istället strålföljning har många fördelar. En litteraturstudie gjordes för att få kunskap om relaterade arbeten, state-of-the-art i strålföljning och tillgängliga hårdvaruaccelererade bibliotek. Genom att använda en metod som kan liknas vid Kanban och Scrum [36], blev implementationen uppdelad i olika uppgifter (eng. tasks), där implementationen av grundläggande funktioner av en strålföljare hade högsta prioritet. En enkel strålföljare implementerades med det valda biblioteket Embree, ett ramverk som utvecklas hos Intel Corporation. Resultaten visar att scenerna som renderas med lägre upplösningar (800 x 600) är goda kandidater för att uppnå en stabil bildfrekvens med 30 bilder per sekund (eng. frames per second), vilket inte är tillräckligt för att rendera ett riktigt spel. Standarden hos spel idag kräver hög upplösning (full HD 1920 x 1080) och komplexa scener. Tidigare studier visar att Embree har potential för högre prestanda och tidigare resultat visar att prestandan av interaktiv strålföljning har förbättrats, men att den fortfarande är begränsad till låga upplösningar och enklare belysningsmodeller.

published_or_final_version / Computer Science / Master / Master of Philosophy

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

In this thesis, we make several significant achievements towards defining a medial axis based shape descriptor which is compact, yet discriminative. First, we propose a novel medial axis spectral shape descriptor called the medial axis spectrum for a 2D shape, which applies spectral analysis directly to the medial axis of a 2D shape. We extend the Laplace-Beltrami operator onto the medial axis of a 2D shape, and take the solution to an extended Laplacian eigenvalue problem defined on this axis as the medial axis spectrum. The medial axis spectrum of a 2D shape is certainly more efficient to compute than spectral analysis of a 2D region, since the efficiency of solving the Laplace eigenvalue problem strongly depends on the domain dimension. We show that the medial axis spectrum is invariant under uniform scaling and isometry of the medial axis. It could also overcome the medial axis noise problem automatically, due to the incorporation of the hyperbolic distance metric. We also demonstrate that the medial axis spectrum inherits several advantages in terms of discriminating power over existing methods. Second, we further generalize the medial axis spectrum to the description of medial axes of 3D shapes, which we call the medial axis spectrum for a 3D shape. We develop a newly defined Minkowski-Euclidean area ratio inspired by the Minkowski inner product to characterize the geometry of the medial axis surface of a 3D mesh. We then generalize the Laplace-Beltrami operator to the medial axis surface, and take the solution to an extended Laplacian eigenvalue problem defined on the surface as the medial axis spectrum. As the 2D case, the medial axis spectrum of a 3D shape is invariant under rigid transformation and isometry of the medial axis, and is robust to shape boundary noise as shown by our experiments. The medial axis spectrum is finally used for 3D shape retrieval, and its superiority over previous work is shown by extensive comparisons. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy