Modern rendering systems require fast and efficient acceleration structures in order to compute visibility in real time. I present several novel data structures and algorithms for computing visibility with high performance. In particular, I present two algorithms for improving heuristic based acceleration structure build. These algorithms, when used in a demand driven way, have been shown to improve build performance by up to two orders of magnitude. Additionally, I introduce ray tracing in perspective transformed space. I demonstrate that ray tracing in this space can significantly improve visibility performance for near-common origin rays such as eye and shadow rays. I use these data structures and algorithms to support a key hypothesis of this dissertation: “There is no silver bullet for solving the visibility problem; many different acceleration structures will be required to achieve the highest performance.” Specialized acceleration structures provide significantly better performance than generic ones and building many specialized structures requires high performance build techniques. Additionally, I present an optimization-based taxonomy for classifying acceleration structures and algorithms in order to identify which optimizations provide the largest improvement in performance. This taxonomy also provides context for the algorithms I present. Finally, I present several novel cost metrics (and a correction to an existing cost metric) to improve visibility performance when using metric based acceleration structures. / text

A fundamental operation in computer graphics is to determine for a given point and direction in a scene, which geometric surface is nearest this point from this direction and thus visible. Conceptually, the point and direction define a "ray". Z-buffer hardware can compute surface visibility for a set of rays with a common origin (i.e. eye point) and a regular pattern of directions in real-time. However, this hardware is much less efficient at performing other visibility computations such as those required to accurately render shadows. A more flexible solution to the visible surface problem is needed. This work introduces the irregular Z-buffer algorithm, which efficiently solves the visible surface problem for rays with a common origin and arbitrary directions. In addition, we identify several changes to classical graphics architectures needed for hardware acceleration of this algorithm. Though these modifications are incremental in nature (i.e. no new functional units are introduced), we show that they enable significant new capability. In tandem with the irregular Z-buffer algorithm, a GPU with these changes has applications in: shadow rendering, indirect illumination, frameless rendering, adaptive anti-aliasing, adaptive textures, and jittered sampling. We explore the performance of hard and soft shadow rendering in particular, by way of a detailed hardware simulator. / text

This report describes the architecture and implementation of a memory profiler for 3D graphics applications. The memory profiling is done for parts of the program which runs on the graphics processor and is responsible for rendering the image. The shaders are parsed and every memory instruction is instrumented with additional instruction for profiling. The results are then transferred from the video memory to CPU memory. Profiling is done for a frame and completes in less than three minutes. The report also describes various analyses that can be done using the results obtained from this profiler. The report discusses the design of an analytical cache model that can be used to identify candidate memory buffers suitable for caching among all the buffers used by an application. The profiler can segregate results for reads and writes separately, can handle all formats of texture access instructions and predicated instructions. / text

Volume rendering techniques can be powerful tools when visualizing medical data sets. The characteristics of being able to capture 3-D internal structures make the technique attractive. Scanning equipment is producing medical images, with rapidly increasing resolution, resulting in heavily increased size of the data set. Despite the great amount of processing power CPUs deliver, the required precision in image quality can be hard to obtain in real-time rendering. Therefore, it is highly desirable to optimize the rendering process. Modern GPUs possess much more computational power and is available for general purpose programming through high level shading languages. Efficient representations of the data are crucial due to the limited memory provided by the GPU. This thesis describes the theoretical background and the implementation of an approach presented by Patric Ljung, Claes Lundström and Anders Ynnerman at Linköping University. The main objective is to implement a fully working multi-resolution framework with two separate pipelines for pre-processing and real-time rendering, which uses the GPU to visualize large medical data sets.

Greitas asmeninių kompiuterių plitimas, kompiuterinių technologijų didėjantis prieinamumas gamyboje ir individualioje kūryboje paskatino naujos subkultūros atsiradimą. Atsirado protrūkis tradiciniam meniniam mąstyme, suvokime. Tai aiškiai matyti iš mokinių veiklos, jų vaizdų suvokimo ir pakitusio požiūrio į dabartinę aplinką. Problema. Bendrasis meninis ugdymas nėra pakankamai veiksmingas: tenkinamasi savaimine moksleivių saviraiška, per mažai ugdomi meniniai ir suvokimo gebėjimai. Todėl aktualu įvesti į dailės mokymą kompiuterinę grafiką, kaip būdą, padedantį suvokti dailės kalbą. Šiame darbe aptariamos kompiuterinės grafikos galimybės: kaip ir kur ją galima panaudoti meniniame ugdyme, mokant dailės kalbos, aptariamos pagrindinės jos didaktinės galimybės. Eksperimento metu gauti duomenys padės išsiaiškinti, kaip pakils mokinių dailės kalbos suvokimo lygis, jeigu kartu su tradiciniu dailės mokymu bus naudojama kompiuterinė grafika, kiek padidės mokinių kūrybinių galių diapazonas. Tyrimo objektas: Kompiuterinė grafika kaip dailės kalbos mokymo priemonė. Tyrimo tikslas: Nustatyti kompiuterinės grafikos galimybių įtaką, mokant paauglius suprasti dailės kalbą. Hipotezė: Dailės kalbos pažinimas taps efektyvesnis naudojant kompiuterines grafikos galimybes dailės pamokose. Tyrimo uždaviniai: 1. Apžvelgti kompiuterinės grafikos galimybių panaudojimą meninėje kūryboje ir dailės ugdymo procese.2.Išanalizuoti mokinių vizualios raiškos teorines žinias 3.Nustatyti kompiuterinės... [toliau žr. visą tekstą] / The rapid spread of personal computers, the use of computer technologies in mass production and individual creative work have encouraged the appearance of the new subculture. The traditional artistic thinking and awareness have to be changed. This is clearly understood seen in student’s activity, their imagination and a changed view of today’s environment. The problem. General art education is not sufficient enough: student’s self-expression is limited, artistic skills are not being well developed. That is the reason why computer graphics should be introduced in to school curriculum in art as a means helping to understand the language of art. This paper deals with computer graphics capabilities: how and where it can be used in the artistic education, what its basic didactic possibilities are. The data, got obtained as a result of the experiment, will help realize how the level of students’ understanding of the artistic language will rise if computer graphics is used alongside with traditional art education, how the range of students’ creative abilities will widen. Research subject: Computer graphics as a tool of art’s language teaching. Research objectives: The influence of possibilities of computer graphics wile teaching adolescents to understand art’s language. Hypothesis: The understanding of the language of art will become move effective by means of using computer graphics at art lesson. Research tasks: 1. To survey the employment of computer graphics possibilities in... [to full text]

The GLuskap system for interactive three-dimensional graph drawing applies techniques of scientific visualization and interactive systems to the construction, display, and analysis of graph drawings. Important features of the system include support for large-screen stereographic 3D display with immersive head-tracking and motion-tracked interactive 3D wand control. A distributed rendering architecture contributes to the portability of the system, with user control performed on a laptop computer without specialized graphics hardware. An interface for implementing graph drawing layout and analysis algorithms in the Python programming language is also provided. This thesis describes comprehensively the work on the system by the author—this work includes the design and implementation of the major features described above. Further directions for continued development and research in cognitive tools for graph drawing research are also suggested. / viii, 110 leaves : ill. (some col.) ; 29 cm.

A 3D arrangement graph G is the abstract graph induced by an arrangement of planes in general position where the intersection of any two planes forms a line of intersection and an intersection of three planes creates a point. The properties of three classes of arrangement graphs — four, five and six planes — are investigated. For graphs induced from six planes, specialized methods were developed to ensure all possible graphs were discovered. The main results are: the number of 3D arrangement graphs induced by four, five and six planes are one, one and 43 respectively; the three classes are Hamiltonian; and the 3D arrangement graphs created from four and five planes are planar but none of the graphs created from six planes are planar. / x, 89 leaves : ill. (some col.) ; 29 cm

No description available.

In current online games, player positions are synchronized by means of continual broadcasts through the server. This solution is expensive, forcing any server to limit its number of clients. With a hybrid networking architecture, player synchronization can be distributed to the clients, bypassing the server bottleneck and decreasing latency as a result. Synchronization in a decentralized fashion is difficult as each player must communicate with every other player. The communication requirements can be reduced by computing and exploiting frontier sets: For a pair of players in an online game, a player's frontier is the region of the game space where the player may move without seeing (and without communicating to) the other player. A pair of frontiers is called a frontier set. This thesis describes the first fast and space-efficient method of computing frontier sets in large terrains. Frontier sets are computed by growing regions in a connected set of quads in a hierarchical decomposition of the terrain. The solution involves the precomputation of a potentially visible set (PVS) for each quad in the decomposition, which stores all the quads potentially visible from any point within the current quad. Since the memory needed to store the PVSs for all the quads is quite large, a compression technique is introduced which controls the size of each PVS. A PVS merging algorithm, with both lossless and lossy variations, is also described which permits adding the PVS of a point or quad to the PVS of a growing region. The new algorithm is compared to a simple region growing approach where frontiers are grown along the individual terrain points. Using similar merging techniques, the new algorithm performs better, producing larger frontier sets with faster execution times. / Thesis (Master, Computing) -- Queen's University, 2010-05-25 14:53:24.375

Visibility culling is a means of accelerating the graphical rendering of geometric models. Invisible objects are efficiently culled to prevent their submission to the standard graphics pipeline. It is advantageous to preprocess scenes in order to determine invisible objects from all possible camera views. This information is typically saved to disk and may then be reused until the model geometry changes. Such preprocessing algorithms are therefore used for scenes that are primarily static. Currently, the standard approach to visibility preprocessing algorithms is to use a form of approximate solution, known as conservative culling. Such algorithms over-estimate the set of visible polygons. This compromise has been considered necessary in order to perform visibility preprocessing quickly. These algorithms attempt to satisfy the goals of both rapid preprocessing and rapid run-time rendering. We observe, however, that there is a need for algorithms with superior performance in preprocessing, as well as for algorithms that are more accurate. For most applications these features are not required simultaneously. In this thesis we present two novel visibility preprocessing algorithms, each of which is strongly biased toward one of these requirements. The first algorithm has the advantage of performance. It executes quickly by exploiting graphics hardware. The algorithm also has the features of output sensitivity (to what is visible), and a logarithmic dependency in the size of the camera space partition. These advantages come at the cost of image error. We present a heuristic guided adaptive sampling methodology that minimises this error. We further show how this algorithm may be parallelised and also present a natural extension of the algorithm to five dimensions for accelerating generalised ray shooting. The second algorithm has the advantage of accuracy. No over-estimation is performed, nor are any sacrifices made in terms of image quality. The cost is primarily that of time. Despite the relatively long computation, the algorithm is still tractable and on average scales slightly superlinearly with the input size. This algorithm also has the advantage of output sensitivity. This is the first known tractable exact solution to the general 3D from-region visibility problem. In order to solve the exact from-region visibility problem, we had to first solve a more general form of the standard stabbing problem. An efficient solution to this problem is presented independently.