Modern High-Performance Ray Casting toolkits, such as the Intel Embree library, which is a de facto industry standard, are a cornerstone of the high- performance levels seen in current CPU rendering. The purpose of Embree is an easy integration into professional image synthesis environments to ac- celerate rendering scenes with complex geometry, usually composed of many primitives. Unfortunately, Embree does not offer support for rendering con- structive solid geometry (CSG), solids composed of a manageable amount of primitive solids by using set operations. This is a significant drawback since CSG modeling is an intuitive and powerful option for describing com- plex geometry. In this thesis, we describe the integration of Embree into the predictive rendering system ART and propose a method for rendering CSG by combining the traversal of Embree's and ART's internal ray acceler- ation data structures. The tests we conducted with virtual scenes containing CSG not being constructed from triangle meshes showed that our method is competitive with the original ART renderer and often even faster. 1

Thesis advisor: William Ames / This thesis deals with the problem of visibility culling in interactive three-dimensional environments. Included in this thesis is a discussion surrounding the issues involved in both constructing and rendering three-dimensional environments. A renderer must sort the objects in a three-dimensional scene in order to draw the scene correctly. The Binary Space Partitioning (BSP) algorithm can sort objects in three-dimensional space using a tree based data structure. This thesis introduces the BSP algorithm in its original context before discussing its other uses in three-dimensional rendering algorithms. Constructive Solid Geometry (CSG) is an efficient interactive modeling technique that enables an artist to create complex three-dimensional environments by performing Boolean set operations on convex volumes. After providing a general overview of CSG, this thesis describes an efficient algorithm for computing CSG expression trees via the use of a BSP tree. When rendering a three-dimensional environment, only a subset of objects in the environment is visible to the user. We refer to this subset of objects as the Potentially Visible Set (PVS). This thesis presents an algorithm that divides an environment into a network of convex cellular volumes connected by invisible portal regions. A renderer can then utilize this network of cells and portals to compute a PVS via a depth first traversal of the scene graph in real-time. Finally, this thesis discusses how a simulation engine might exploit this data structure to provide dynamic collision detection against the scene graph. / Thesis (BA) — Boston College, 2004. / Submitted to: Boston College. College of Arts and Sciences. / Discipline: Computer Science. / Discipline: College Honors Program.

Ray tracing acceleration methods are usually applied to scenes defined by triangle meshes.These scenes contain a large number of triangles. In contrast, CSG scenes contain orders of magnitude less more complex primitives primitives. In this thesis we will present the Operation KD-tree. This acceleration method applies the KD-tree --- modern acceleration method developed for triangle meshes --- directly to the CSG scene. This is done on the premise, that the huge reduction in primitive count will yield enhanced performance, when rendering a scene using CSG instead of triangle meshes.

The Coalition Structure Generation (CSG) problem requires finding an optimal partition of a set of n agents. An optimal partition means one that maximizes global welfare. Computing an optimal coalition structure is computationally hard especially when there are externalities, i.e., when the worth of a coalition is dependent on the organisation of agents outside the coalition. A number of algorithms were previously proposed to solve the CSG problem but most of these methods were designed for systems without externalities. Very little attention has been paid to finding optimal coalition structures in the presence of externalities, although externalities are a key feature of many real world multiagent systems. Moreover, the existing methods, being non-heuristic, have exponential time complexity which means that they are infeasible for any but systems comprised of a small number of agents. The aim of this research is to develop effective heuristic methods for finding optimal coalition structures in systems with externalities, where time taken to find a solution is more important than the quality of the solution. To this end, four different heuristics methods namely tabu search, simulated annealing, ant colony search and particle swarm optimisation are explored. In particular, neighbourhood operators were devised for the effective exploration of the search space and a compact representation method was formulated for storing details about the multiagent system. Using these, the heuristic methods were devised and their performance was evaluated extensively for a wide range of input data.

A new approach to image-space hardware-based rendering of Constructive Solid Geometry (CSG) models is presented. The work is motivated by the evolving functionality and performance of computer graphics hardware. This work is also motivated by a specific industrial application --- interactive verification of five axis grinding machine tool programs. The goal is to minimise the amount of time required to render each frame in an animation or interactive application involving boolean combinations of three dimensional shapes. The Sequenced Convex Subtraction (SCS) algorithm utilises sequenced subtraction of convex objects for the purpose of interactive CSG rendering. Concave shapes must be decomposed into convex shapes for the purpose of rendering. The length of Permutation Embedding Sequences (PESs) used as subtraction sequences are shown to have a quadratic lower bound. In many situations shorter sequences can be used, in the best case linear. Approaches to s ubtraction sequence encoding are presented including the use of object-space overlap information. The implementation of the algorithm is experimentally shown to perform better on modern commodity graphics hardware than previously reported methods. This work also examines performance aspects of the SCS algorithm itself. Overall performance depends on hardware characteristics, the number and spatial arrangement of primitives, and the structure and boolean operators of the CSG tree.

Different tracing techniques of the subperiosteal and endosteal contours (manual, automatic, semi-automatic) or their combinations taken along femoral length in adult individuals can produce different values of cross-sectional geometric (CSG) parameters. Various tracing techniques are widely used in CSG studies of non-adult individuals as well, however, the accuracy of CSG parameters estimated along femoral diaphysis is not yet known for non-adult individuals. In this study, we investigate whether the manual tracing of the subperiosteal and endosteal contours taken at 80% of the femoral diaphyseal length in non-adult individuals can be replaced by another type of tracing in relation to CSG parameters estimation. We examine the effect of anatomical localization on accuracy of the CSG parameters estimated in non-adult individuals femora. We digitized the subperiosteal and endosteal contours in the micro-CT scans from femoral diaphyseal cross-sections in Early Medieval sample of non-adult individuals (N = 46). The digitization and computation of CSG parameters were made in Fiji software with EPJMacro implementation. The assessment of estimates' accuracy was expressed by percentage prediction error (%PE) and limits of agreement. Five percent of CSG parameter obtained from manually traced contours was...

L'objet de cette thèse porte sur la conversion d'un modèle CSG vers un modèle BRep d'une scène définie par des quadriques. Cet algorithme est composé de quatre étapes : (i) le paramétrage de chaque courbe d'intersection entre quadriques ; (ii) la détermination des points d'intersection entre au moins trois quadriques ; (iii) la détection des segments ainsi obtenus qui bornent une face du modèle BRep sur chacune des quadriques séparément ; (iv) l'identification et le regroupement des chaînes de segments qui délimitent une même face sur chaque quadrique séparément (certaines faces peuvent avoir des <>, et par conséquent être constituées par au moins deux chaînes de segments). Les deux premières étapes ont été résolues grâce à deux algorithmes de la littérature. Les deux étapes restantes sont traitées par des algorithmes que nous avons conçus : respectivement VE (Visible Edges) et CA (Chains Assembling). Notre algorithme est robuste au sens où tous les cas dégénérés sont traités dans le paradigme du calcul géométrique exact. Il résout intégralement le problème de conversion CSG-BRep de scènes définies par des quadriques. Sa complexité dans le pire des cas s'élève à $O(n^4)$ où $n$ est le nombre de quadriques. Une implantation partielle a été effectuée et des tests préliminaires réalisés.

<p>We present a method for stable buildup of snow on surfaces of</p><p>arbitrary topology and geometric complexity. This is achieved by</p><p>tracing quantities of snow, so-called snow packages,</p><p>through a dynamic wind field. Dual compact level sets are used to</p><p>represent geometry as well as accumulated snow. The level sets</p><p>have also proven to be well suited for the internal boundaries for</p><p>our Navier-Stokes solver, which produces a wind field that changes</p><p>according to snow buildup. Our method is different from previous</p><p>work in that all the addition of snow is done by local operations,</p><p>avoiding computationally expensive global refinement procedures.</p><p>The main contribution of this work is a dual level set method for</p><p>particle interaction with level sets.</p>

We present a method for stable buildup of snow on surfaces of arbitrary topology and geometric complexity. This is achieved by tracing quantities of snow, so-called snow packages, through a dynamic wind field. Dual compact level sets are used to represent geometry as well as accumulated snow. The level sets have also proven to be well suited for the internal boundaries for our Navier-Stokes solver, which produces a wind field that changes according to snow buildup. Our method is different from previous work in that all the addition of snow is done by local operations, avoiding computationally expensive global refinement procedures. The main contribution of this work is a dual level set method for particle interaction with level sets.

This thesis brings an overview about scene rendering using the ray tracing method. It describes aspects used when creating the application which uses this method such as intersection computation, lighting and shading models etc. It also describes the basic algorithm used for rendering one frame. Each class of the object oriented design is described. There is also detail explanation what is the purpose of the each class in the model and what are the most important used methods. The work also contains demonstration application showing the usage of model in practice.