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.

We present a novel method for example-based simulation of fluid flow. We reconstruct fluid animation from physically based fluid simulation examples. Our framework shows how to decompose a given series of fluid motion example data into small units and then recompose them. We capture the properties of local fluid behavior by dicing the fluid motion example data into sequences of fragments, which have smaller volume and shorter length. We build a database out of these fragments, and propose a matching strategy to generate new fluid animation. To achieve highly efficient database query, we project our fragments onto lower dimensional subspace using Principal Component Analysis (PCA) approach, and construct our data structure as a kd-tree by treating each fragment as a point in this subspace. Our method has been implemented in synthesizing both two-dimensional (2D) and three-dimensional (3D) fluid’s velocity fields.

We present a novel method for example-based simulation of fluid flow. We reconstruct fluid animation from physically based fluid simulation examples. Our framework shows how to decompose a given series of fluid motion example data into small units and then recompose them. We capture the properties of local fluid behavior by dicing the fluid motion example data into sequences of fragments, which have smaller volume and shorter length. We build a database out of these fragments, and propose a matching strategy to generate new fluid animation. To achieve highly efficient database query, we project our fragments onto lower dimensional subspace using Principal Component Analysis (PCA) approach, and construct our data structure as a kd-tree by treating each fragment as a point in this subspace. Our method has been implemented in synthesizing both two-dimensional (2D) and three-dimensional (3D) fluid’s velocity fields.

We present a novel method for example-based simulation of fluid flow. We reconstruct fluid animation from physically based fluid simulation examples. Our framework shows how to decompose a given series of fluid motion example data into small units and then recompose them. We capture the properties of local fluid behavior by dicing the fluid motion example data into sequences of fragments, which have smaller volume and shorter length. We build a database out of these fragments, and propose a matching strategy to generate new fluid animation. To achieve highly efficient database query, we project our fragments onto lower dimensional subspace using Principal Component Analysis (PCA) approach, and construct our data structure as a kd-tree by treating each fragment as a point in this subspace. Our method has been implemented in synthesizing both two-dimensional (2D) and three-dimensional (3D) fluid’s velocity fields.

We present a novel method for example-based simulation of fluid flow. We reconstruct fluid animation from physically based fluid simulation examples. Our framework shows how to decompose a given series of fluid motion example data into small units and then recompose them. We capture the properties of local fluid behavior by dicing the fluid motion example data into sequences of fragments, which have smaller volume and shorter length. We build a database out of these fragments, and propose a matching strategy to generate new fluid animation. To achieve highly efficient database query, we project our fragments onto lower dimensional subspace using Principal Component Analysis (PCA) approach, and construct our data structure as a kd-tree by treating each fragment as a point in this subspace. Our method has been implemented in synthesizing both two-dimensional (2D) and three-dimensional (3D) fluid’s velocity fields.

Building maps within an unknown environment while keeping track of the current position is a major step to accomplish safe and autonomous robot navigation. Within the last 20 years, Simultaneous Localization And Mapping (SLAM) became a topic of great interest in robotics. The basic idea of this technique is to combine proprioceptive robot motion information with external environmental information to minimize global positioning errors. Because the robot is moving in its environment, exteroceptive data comes from different points of view and must be expressed in the same coordinate system to be combined. The latter process is called registration. Iterative Closest Point (ICP) is a registration algorithm with very good performances in several 3D model reconstruction applications, and was recently applied to SLAM. However, SLAM has specific needs in terms of real-time and robustness comparatively to 3D model reconstructions, leaving room for specialized robotic mapping optimizations in relation to robot mapping. After reviewing existing SLAM approaches, this thesis introduces a new registration variant called Kd-ICP. This referencing technique iteratively decreases the error between misaligned point clouds without extracting specific environmental features. Results demonstrate that the new rejection technique used to achieve mapping registration is more robust to large initial positioning errors. Experiments with simulated and real environments suggest that Kd-ICP is more robust compared to other ICP variants. Moreover, the Kd-ICP is fast enough for real-time applications and is able to deal with sensor occlusions and partially overlapping maps. Realizing fast and robust local map registrations opens the door to new opportunities in SLAM. It becomes feasible to minimize the cumulation of robot positioning errors, to fuse local environmental information, to reduce memory usage when the robot is revisiting the same location. It is also possible to evaluate network constrains needed to minimize global mapping errors.

<div>In Divide & Recombine (D&R), data are divided into subsets, analytic methodsare applied to each subset independently, with no communication between processes;then the subset outputs for each method are recombined. For big data, this providesalmost all of the analytic tasking needed when data are analyzed. It also provideshigh computational performance because typically most of the computation is em-barrassingly parallel, the simplest parallel computation.</div><div><br></div><div>Another kind of tasking must address computational performance and numericaccuracy: the computing of functions of all of the data, or “statistics”. For data bigand small, it is often important to compute such statistics for all of the data, whichcan be summaries of the data, such as sample quantiles of continuous variables, orcan process the data into a form that helps analysis, such as dividing the data intorepresentative subsets. Development of computational methods to compute thesestatistics can be challenging.</div><div><br></div><div>D&R can be a very effective framework for computing statistics. To supportthis, we introduce the concept of embarrassingly parallel (EP) statistics, both weakand strong. The concept of EP statistics is not entirely new, but has had littledevelopment. The existing methodology is mainly sums of sums. For example, this isdone when computing the necessary statistics for least squares where sums of productsand cross productions are carried out on subsets then summed across subsets. Ourtreatment of EP statistics has taken the concept much further. The outcome is abilityto use EP statistics in conjunction with the use a Fourier series to approximate an optimization criteria. The series terms, which are strongly EP statistics, are summedacross subsets, and the result is optimized. These are EP-F computational methods.</div><div><br></div><div>We have so far developed two EP-F computational methods for two widely usedstatistic computations. EP-F-Quantile is for quantiles of big data, and EP-F-KDtreeis for KD-trees. Speed and accuracy of EPF-Quantile are compared with that of thewell-known binning method, which also can be formulated in terms of EP statistics. EPF-KDtree is the first parallel KD-tree computational method of which we areaware. EP and EPF computational methods have potentially many other applicationsto computing statistics.</div>

Denna studie gick ut på att jämföra tre olika algoritmer som har använts för bred kollisionsdetektering, dessa algoritmer var Kd-tree, Octree och Sweep and prune. Kd-tree och Octree är spatiala datastrukturer, d.v.s. att de hanterar objekt inom specifika volymer. Sweep and prune använder istället listor för att ta reda på om objekt kolliderar. Fokus låg på att se hur stor skillnad algoritmernas exekveringstid hade jämfört med ’brute force’-implementationen och jämfört med varandra. Det utfördes ett antal olika experiment på algoritmerna med ett antal olika inställningar för att kunna utvärdera hur de presterar i olika situationer. Dessa inställningar var t.ex. antalet boids, deras hastighet och hur långt de kunde se. Resultatet visade att Sweep and prune presterade bäst med en liten mängd boids medans de andra algoritmerna kom ikapp och presterade bättre när antalet objekt ökade, då Kd-tree presterade bäst överlag. Studien kan vara till hjälp med att välja vilken bred kollisionsdetekteringsalgoritm som kan tänkas implementeras för en applikation.

Context. Ray tracing has always been a simple but effective way to create a photorealistic scene but at a greater cost when expanding the scene. Recent improvements in GPU and CPU hardware have made ray tracing faster, making more complex scenes possible with the same amount of time needed to process the scene. Despite the improvements in hardware ray tracing is still rarely run at a interactive speed. Objectives. The aim of this experiment was to implement a new kdtree generation algorithm using DirectX 11 compute shaders. Methods. The implementation created during the experiment was tested using two platforms and five scenarios where the generation time for the kd-tree was measured in milliseconds. The results where compared to a sequential implementation running on the CPU. Results. In the end the kd-tree generation algorithm implemented did not run within our definition of real-time. Comparing the generation times from the implementations shows that there is a speedup for the GPU implementation compared to our CPU implementation, it also shows linear scaling for the generation time as the number of triangles in the scene increase. Conclusions. Noticeable limitations encountered during the experiment was that the handling of dynamic structures and sorting of arrays are limited which forced us to use less memory efficient solutions.

This term project addresses the construction of kD tree acceleration structures and parallelization of this construction using GPU. At the beginning, there is an introduction of the reader into CUDA platform for parallel programming. There is a decription of generic principles as well as specific features that will be used in this thesis. Following that the reader is put into the issue of acceleration structures for Ray tracing. These structures are described and the kD tree acceleration structure and its variants are portrayed in detail. After that the analysis of chosen kD tree variant is broken down and the problems and issuse of its parallel implementation are adressed. As a part of implementation discription, there is a short descripton of CPU variant and detailed specifications of the CUDA kernels. The testing section brings the results of implementation in form of CPU vs GPU comparison, as well as evaluation of how much the metric set in design was fulfilled. In the end there is a summary of achieved goals and results followed by possible future improvements for the implementation.