Simultaneous Localization and Mapping (SLAM) algorithms are used by autonomous robots to build or update maps of an environment while maintaining their position simultaneously. A fundamental open problem in SLAM is the e ective representation of the map in unknown, ambiguous, complex, dynamic environments. Representing such environments in a suitable manner is a complex task. Existing approaches to SLAM use map representations that store individual features (range measurements, image patches, or higher level semantic features) and their locations in the environment. The choice of how the map is represented produces limitations which in many ways are unfavourable for application in real-world scenarios. In this thesis, a new approach to SLAM is explored that rede nes sensing and robot motion as acts of deformation of a di erentiable surface. Distance elds and level set methods are utilized to de ne a parallel to the components of the SLAM estimation process and an algorithm is developed and demonstrated. The variational framework developed is capable of representing complex dynamic scenes and spatially varying uncertainty for sensor and robot models. / UOIT

Implicit surface modeling is attracting attention, because a complex object can be constructed easily and intuitively from some simple primitive objects, defined by primitive defining functions, using successive compositions of blending operations. Blending operations play a major role in implicit surfaces, because they can join intersecting primitive objects (operands) smoothly with transitions generated automatically by blending operators. Hence, this dissertation proposes three new methods: (1) the scale method, (2) field functions with adjustable inner and outer radii, and (3) the translation method, for developing blending operations that have blending range controls. That is, the proposed blending operations provide blending range parameters to adjust the size and shape of the transition of the blending surface freely, without deforming the shapes of blended primitives totally. The first and the third methods offer blending range controls by developing new blending operators, whereas the second method does the similar things by developing new primitive defining functions. The scale method is a generalized method. It provides a framework to transform any existing blending operators or arc-shaped curves into the blending operator that has the following properties: (1) Provides blending range and curvature parameters to adjust the size and shape of the transition of the blending surface, without deforming the shapes of blended primitives totally. (2) Behaves like Max/Min(x1,¡K,xk) operators in non-blending regions in the entire domain. As a result, it gives a more intuitive shape control on modeling its subsequent blends. (3) Possesses C1 continuity in the entire domain except the origin. As a result, it can prevent from generating non-smooth surfaces on sequential blends with overlapped blending regions. (4) Works to blend both non-zero and zero implicit surfaces. (5) Can be a new primitive in other blends, especially in Soft blending. (6) Applies for bulge elimination. Field functions with adjustable inner and outer radii provide parameters to adjust the inner and the outer radii of influence, respectively. This dissertation proposes four different transforms to develop this kind of field functions. Thus, using the proposed field functions as the new primitive defining functions of soft object modeling, Soft blending, R-functions, Ricci¡¦s super-ellipsoid blends and Perlin¡¦s set operations: (1) Can retain their low computing complexity. (2) Can perform the blending range controls, by adjusting the inner and the outer radii of influence of the proposed field functions. The translation method is also a generalized method. It offers a framework to transform any existing blending operators or arc-shaped curves into controllable blending operators for blending zero implicit surfaces. A controllable blending operator has the following properties: (1) Offers blending range and curvature parameters to adjust the size and shape of transition of the blending surface, without deforming the shapes of blended primitives completely. (2) Provides parameters mi, i=1,2,¡K,k, to behave like Max/Min(x1/m1,¡K,xk/mk) operators on non-blending regions in the entire domain, and its zero level blending surface remains unchanged, whatever mi, i=1,2,¡K,k, are set. As a result, by adjusting mi, i=1,2,¡K,k, a controllable blending operator has the following abilities to control its primitives¡¦ subsequent blends:

<p>The Particle Level set method is a successful extension to Level set methods to improve thevolume preservation in fluid simulations. This thesis will analyze how sparse volume data structures can be used to store both the signed distance function and the particles in order to improve access speed and memory efficiency. This Particle Level set implementation will be evaluated against Digital Domains current Particle Level set implementation. Different degrees of quantization will be used to implement particle representations with varying accuracy. These particles will be tested and both visual results and error measurments will be presented. The sparse volume data structures DB-Grid and Field3D will be evaluated in terms of speed and memory efficiency.</p>

This thesis presents a prototype system for generating animation control systems for isosurface-based characters that blurs the distinction between a skeletal rig and a particle system. Managing articulation and deformation set-up can be challenging for amorphous characters whose surface shape is defined at render time and can only be viewed as an approximation during the process of defining an animation performance. This prototype system utilizes conventional scripted techniques for defining animation control systems integrated with a graphical user interface that provides art directable control over surface contour, shape and silhouette for isosurface-based characters. Once animated, these characters can be rendered using Rendermans RIBlobby implementation and provide visual feedback of fluid motion tests. The prototype system fits naturally within common practices in digital character setup and provides the animator control over isosurface-based characters.

Implicit surfaces offer many advantages for sketch-based modeling systems, such as blending, CSG, and a procedural object hierarchy. Free-form deformation (FFD) is also extremely useful in this context, however existing FFD approaches do not support implicit surface representations, and FFD lattice manipulation is time-consuming compared to sketch-based techniques. In this thesis, an FFD technique suitable for implicit surface representations is described. To enhance real-time feedback, the problem is split into an approximate formulation used during interactive deformation, and a more robust variational technique which preserves desirable scalar field properties. As an interface to manipulate the deformation, a sketch-based volumetric peeling interface is introduced. The user's task is to draw a curve on the surface, and pull or push the surface to the desirable position via the curve. Subsequently, the deformation is automatically defined. This technique has been implemented in a prototype implicit FFD system called Taco. Results created in Taco show that a desirable deformation can be easily achieved while preserving implicit properties.

Digital games are based on interactive virtual environments where graphics and audio are combined. In many of these games there is lot of effort put into graphics while leaving the audio part underdeveloped. Audio in games is important in order to immerse the player in the virtual environment. Where a high level of emulated reality is needed graphics and audio should be combined on a similar level of realism. To make this possible a sophisticated method for audio simulation is needed. In the audio simulation field previous attempts at using ray tracing methods were successful. With methods based on ray tracing the sound waves are traced from the audio source to the listener in the virtual environment, where the environment is based on a scene consisting of implicit surfaces. A key part in the tracing computations is finding the intersection point between a sound wave and the surfaces in the scene. Sphere tracing is an alternative method for finding the intersection point and has been shown to be feasible for real-time usage on the graphics processing unit (GPU). To be interactive a game environment runs in real-time, this fact puts a time constraint on the rendering of the graphics and audio. The time constraint is based on the time window to render one frame in the synchronized rendering of graphics and audio based on the frame rate of the graphics. Consumer computer systems of today are in general equipped with a GPU, if an audio simulation can use the GPU in real-time this is a possible implementation target in a game system. The aim of this thesis is to investigate if audio simulation with the ray tracing method based on sphere tracing is possible to run in real-time on the GPU. An audio simulation system is implemented in order to examine the possibility for real-time usage based on computation time. The results of this thesis show that audio simulation with implicit surfaces using sphere tracing is possible to use in real-time with the GPU in some form. The time consumption for an audio simulation system like this is small enough to enable it for real-time usage. Based on an interactive graphics frame rate the time consumption allows the graphics and audio computations to use the GPU in the same frame time.

The Particle Level set method is a successful extension to Level set methods to improve thevolume preservation in fluid simulations. This thesis will analyze how sparse volume data structures can be used to store both the signed distance function and the particles in order to improve access speed and memory efficiency. This Particle Level set implementation will be evaluated against Digital Domains current Particle Level set implementation. Different degrees of quantization will be used to implement particle representations with varying accuracy. These particles will be tested and both visual results and error measurments will be presented. The sparse volume data structures DB-Grid and Field3D will be evaluated in terms of speed and memory efficiency.

Modéliser avec des squelettes est une alternative très séduisante aux "points de contrôle" souvent placés à l'extérieur des formes : cette approches, analogue à un fil de fer dans une forme modelée, permet de créer des modèles de toutes géométries et topologies. Pour cela, il faut que les formes définies par chacun des squelettes soient capable de se mélanger de manière lisse. Introduites en informatique graphique dans les années 90, les surfaces implicites sont la principale solution à ce problème. Elles constituent un modèle puissant à la fois pour la modélisation d'objets tridimensionnels et pour leur animation : leur construction par squelette et leurs capacités de mélange par sommation des champs potentiels qui les définissent permettent en effet la conception progressive et le stockage compact d'objets volumiques, ainsi que l'animation de déformations pouvant comprendre des changements de topologie. Les surfaces implicites, et plus particulièrement les surfaces de convolution, forment donc un modèle particulièrement adapté à la modélisation par squelette. Toutefois, elles présentent un certain nombre de défaut qui les ont rendu inutilisable en pratique. Cette thèse propose de nouveaux modèles implicites à squelettes, s'inspirant de la convolution mais basés aussi sur des déformations de l'espace. Ils permettent : – une génération plus aisée de forme le long de squelettes formés de courbes (des arc d'hélices), – un meilleur contrôle des formes tant au niveau de leur épaisseur que de leur mélange, notamment nos modèles sont invariant par homothétie ce qui les rend plus intuitif, – la génération de surfaces ayant une topologie plus proche de celle des squelettes, – la génération de détail fins engendrés par un bruit procédural, les détails se comportant de manière cohérentes avec la surface (et les squelettes) sous-jacente. / Modeling with skeleton is an attractive alternative to "control points" usually placed outside a shape in order to model it : this paradigm, similar to a wire inside the modeled shape, enables to create model of arbitrary geometry and topology. In order to do so, shapes defined by skeletons should be able to smoothly blend together. Introduced in computer graphics in the 90's, implicit surfaces are one of the main solution to this problem. They are powerful both for the modeling of 3D models and their animations : their construction from a skeleton and their blending capacity by simply summing their scalar field provide an easy way to incrementally create shapes and store them in a compact way, it also ease the animation containing changes in topology. Implicit surfaces, and more specifically Convolution surfaces, are therefore particularly well adapted to skeleton-based modeling. However, they present a number of drawback that make them unusable in practice. This thesis propose new skeleton-based implicit models, inspired not only by convolution but also from space deformations. They enable : – an easier generation of shape along curve skeletons (arcs of helix), – a better control of generated shape both in term of thickness and blending, in particular our model are scale-invariant that make them more intuitive, – the generation of shape which topology better reflects the topology of its skeleton, – the generation of small scale details from a procedural texture, the details behave in a coherent way with the underlying surface (and its skeleton).

This dissertation contains a study about plane curves and surfaces. The two most common way to define this elements are reviewed: the parametric and the implicit definition, with emphasis on the latter. An analysis of some methods to represent plane curves and surfaces is made. One notices that this job is relatively simple when the parametric definition is used, however with the implicit definition this requires a larger number of operations. This works also presents some methods to find approximations of curves and surfaces implicitly defined that preserves the topology and that generate objects smooth enough. This is achieved basically by a subdivision of the plane (respectivelly the space), which is used to find a piecewise linear approximation of the curve (respectivelly the surface), then this approximation is subdivided to make the result smooth. In the case of surfaces the output is a triangular mesh. Some treatments are also made to improve the quality of the mesh. / Fundação de Amparo a Pesquisa do Estado de Alagoas / Esta dissertação contém um estudo a respeito de curvas planas e superfícies. São vistas as duas formas mais usuais de se definirem estes elementos: a definição paramétrica e a implícita, com ênfase nesta última. São analisadas algumas formas de representação de curvas planas e superfícies, o que vem a ser uma tarefa relativamente simples ao se utilizar a definição paramétrica, porém com a definição implícita isto exige um maior número de operações. São apresentados alguns métodos para encontrar aproximações de curvas e superfícies definidas implicitamente que mantenham a sua topologia e que geram objetos suaves o suficiente. Isto é feito basicamente subdividindo-se o plano (respectivamente o espaço), que é utilizado para aproximar a curva (respectivamente a superfície) de forma linear por partes, e então subdivide-se essa aproximação para que o resultado seja suave. No caso das superfícies a saída é uma malha triangular. São realizados também tratamentos para aumentar a qualidade desta malha.

Les fonctions de champ scalaire sont un outil mathématique puissant pour la représentation de surfaces en informatique graphique. Malgré l'information de volume qu'elles offrent, combiné aux modèles de composition qui les accompagnent, les fonctions de champ scalaire ne sont encore utilisées que dans très peu d'applications en raison de leurs limitations, telles qu'une interaction utilisateur lente et un contrôle de la forme de la surface difficile.Dans cette thèse, nous étudions ces modèles de composition dans le but de les développer, de les améliorer et de faire en sorte qu'ils soient efficaces et pertinents pour l'informatique graphique. Pour cela, nous nous intéressons à deux applications.La première est la modélisation géométrique, où les fonctions de champ scalaire représentent des composants d'objets qui sont assemblés par paires dans un processus de création incrémental pour construire des objets complexes. Nous proposons une représentation unifiée des fonctions de champ scalaire et du modèle de composition afin d'obtenir un processus de modélisation plus stable et sans artefacts.La deuxième application à laquelle nous nous intéressons est la simulation et la reconstruction de fluides basées particules. Ici, les fonctions de champ scalaire représentent les contributions des particules qui échantillonnent le volume du fluide. Ces contributions sont alors combinées d'un coup pour reconstruire la surface du fluide. Nous proposons dans ce cadre de prendre en compte la topologie de la surface reconstruite dans la simulation, évitant ainsi un comportement inapproprié des particules, et donc du fluide ainsi simulé. / Field functions are a powerful mathematical tool for surface representation in computer graphics. Despite the volume information they provide, combined with the composition models accompanying them, field functions are still used in only a few number of applications due to their limitations such as slow user interactions and a difficult shape control.In this thesis we study these composition models in order to develop and improve them and make them efficient and relevant for computer graphics. We do so through two applications.The first one is geometric modelling, where field functions represent object compounds that are combined pairwisely in an iterative creation process to design complex objects. We propose to unify and make consistent both the field function representation and the composition model to provide a more stable and artefact-free modelling process.The second one is fluid simulation and reconstruction based on particles. Here, field functions represent contributions of the particles sampling the fluid volume. These contributions are then combined in a row to build the fluid surface. In this application, we propose to take the topology of the reconstructed surface into account when running the fluid simulation, thus avoiding an inappropriate behavior of the particles, and then of the simulated fluid.