This report treats the implementation of collision detection algorithms for Boundary representations (BREPs) consisting of connected trimmed surfaces, mainly Non Uniform Rational Basis Spline (NURBS) surfaces. Using the OpenNurbs software package, complicated geometries created in CAD program Space Claim were imported to the physics engine AgX, where dynamic simulations were carried out. Collision detection algorithms for the geometry pairs BREP-line, BREP-plane and BREP-sphere have been developed and investigated. In the case of BREP-sphere collision detection, experiments have been carried out which show that BREP-shape representation exceeds trimesh-shape representation both in computational performance and in collision accuracy. The conclusion is that BREP representation has the potential to replace trimesh representation for some complex geometries with higher computational performance and more accurate simulations as a result.

Avec le développement de systèmes robotiques avancés et de tâches de téléopération complexes, le besoin pour la réalisation de simulations en amont des opérations sur les systèmes réels se fait de plus en plus ressentir. Cela concerne en particulier les tests de faisabilité, d’entrainement d’opérateurs humains, de planification de mouvement, etc. Ces simulations doivent généralement être réalisées avec une précision importante des phénomènes physiques, notamment si l’opérateur humain est supposé faire face aux mêmes comportements mécaniques dans le monde réel que sur la scène virtuelle. La détection de collision, c’est à dire le calcul de points de contact et des normales de contact entre des objets rigides en mouvement et susceptibles d’interagir, occupe une portion significative des temps de calcul pour ce type de simulations. La précision ainsi que le niveau de continuité de ces informations de contact sont d’importance premières afin de produire des comportements réalistes des objets simulés. Cependant, la qualité des informations de contact ainsi calculées dépend fortement de la représentation géométrique des parties de la scène virtuelle directement impliquées dans la simulation mécanique. D'une part, les représentations géométriques basées sur des volumes discrets ou des tessellations permettent une génération de contacts extrêmement rapide, mais en contrepartie introduisent des artefacts numériques dus à l’approximation des formes en contact. D'autre part, l’utilisation de représentations surfaciques lisses (composées de courbes et surfaces lisses) produites par les modeleurs CAO permet d’éliminer ce problème d’approximations. Cependant, ces approches sont actuellement considérées trop lentes en pratique pour des applications en temps réel.Cette thèse est dédiée au développement d’une premier framework de détection de collision entre solides modélisés par représentation surfacique lisses suffisamment efficace pour offrir des performances temps-réel pour certaines applications industrielles nécessitant un niveau de précision élevé. Ces applications prennent typiquement la forme de la simulation d’opérations d’insertion avec faible jeu. L’approche proposée est basée sur une hiérarchie de volumes englobants et tire profit de caractéristiques clef des composants mécaniques industriels dont les surfaces sujettes à des contacts fonctionnels sont généralement modélisées par des surfaces canoniques (cylindres, sphères, cônes, plans, tores). Les contacts sur des surfaces d’interpolation telles que les NURBS sont généralement accidentels et rencontrés lors d’opérations de maintenance et de fabrication. Cette hiérarchie de volumes englobants est améliorée par l’identification d'entités supermaximales afin d’éviter la localisation redondante de points de contacts entre surfaces canoniques parfois découpées en plusieurs entités distinctes. De plus, le concept de cônes polyédrique de normales est défini afin d’établir des bornes de normales plus précises que les cônes de normales de révolution existants. Additionnellement, le framework ainsi développé est étendu afin de supporter des configurations incluant des câbles modélisés par des courbes de Bézier dilatées. Enfin, l’exploitation de la cohérence temporelle, ainsi que la parallélisation de l’ensemble du framework permet l’exécution en temps réel de certains scénarios industriels. / With the development of advanced robotic systems and complex teleoperation tasks, the need to perform simulations before operating on physical systems becomes of increasing interest for feasibility tests, training of the human operators, motion planning, etc. Such simulations usually need to be performed with great accuracy of physical phenomena if, e.g., the operator is expected to face the same ones in the real world and in the virtual scene. Collision detection, i.e., the computation of contact points and contact normals between interacting rigid bodies, occupies a time-consuming part of such a physical simulation. The accuracy and smoothness of such contact information is of primary importance to produce a realistic behavior of the simulated objects. However, the quality of the computed contact information strongly depends on the geometric representation of the parts of the virtual scene directly involved in the mechanical simulation. On the one hand, discrete volumes-based and tessellation-based geometric representations allow very fast contacts generation at the cost of the potential introduction of numerical artifacts due to the approximation of the interacting geometrical shapes. On the other hand, the use of boundary representations (issued by CAD modelers) composed of smooth curve and surfaces removes this approximation problem but is currently considered being too slow in practice for real-time applications.This Ph.D focuses on developing a first complete collision detection framework on solids with smooth boundary representations that achieves real-time performances. Our goal is to allow the real-time simulation of industrial scenarios that require a high level of accuracy. Typical applications are insertion tasks with small mechanical clearances. The proposed approach is based on a bounding-volume hierarchy and takes advantage of key features of industrial mechanical components which are often modeled with surfaces describing functional contacts with canonical surfaces (cylinder, sphere, cone, plane, torus) while contacts over free-form surfaces like B-Splines are mostly accidental and encountered during operations of maintenance and manufacturing. We augment this hierarchy with the identification of supermaximal features in order to avoid redundant exact localization of contact points on canonical surfaces that may be represented as distinct features of the CAD model. In addition, we define polyhedral normal cones that offer tighter bounds of normals than existing normal cones of revolution. Moreover, we extend our method to handle configurations that involve beams modeled as deformable dilated Bézier curves. Finally, parallelization of the full approach allows industrial scenarios to be executed in real-time.

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.

This thesis treats how to generate collision information for multibody simulations in AgX Dynamicswhere the geometries are described with the data structure boundary representation, BREP. BREP is adata structure that contains the exact mathematical description of each individual surface. To describecomplex surfaces exact and efficient non uniform rational basis spline, NURBS, is used and for trivialsurfaces like planes or spheres simpler equations is used. Since all surfaces in a BREP is described veryaccurate, the accuracy for the collision information can be set high without affecting the amount of dataneeded to describe the geometries.To make AgX Dynamics able to calculate forces in a multibody simulation, collision informationabout were and how much two geometries are intersecting is required. The collision information containswere the overlap between two geometries is, how much the objects have penetrated each other and thedirection for which the objects have to separate. To find the penetration depth and the overlap theNewton Raphson method were used. The experiments conducted, showed that it is possible to useBREPs as a description of geometries to produce the collision information needed for the physics engineused by AgX Dynamics to handle collisions. A comparison between trimesh and BREP for producingthe collision information, shows that data usage is much lower for the representation of geometries withBREPs than trimesh. The results also shows that the accuracy can be significantly higher than fortrimesh as the data usage for trimesh becomes non practical to handle when the required accuracy ishigh. With the high accuracy and with the smooth surfaces used with the BREP the artificial friction isalmost negligible except for cases were intersection points could not be found all around the intersectioncurves due to limitations in the algorithm. / Detta examensarbete behandlar hur man skapar kollisionsinformation för flerkropps simuleringar i AgXDynamics där geometrier beskrivs med datastrukturen boundary representation, BREP. BREP är endatastruktur som innehåller den exakta matematiska beskrivningen för varje enskild yta. Att beskrivakomplexa ytor exakta och effektivt med non uniform rationell basis spline, NURBS, används och förtriviala ytor som plan eller sfärer kan enklare ekvationer används. Eftersom alla ytor i en BREP beskrivsexakt, kan noggrannheten för kollisions informationen sättas högt utan att påverka den mängd data sombehövs för att beskriva geometrier.För att göra AgX Dynamics kunna beräkna krafter i en flerkroppssimulering, krävs kollisions informationom var och hur mycket två geometrier kolliderar. Kollisions informationen innehåller varöverlappningen mellan två geometrier är, hur mycket objekten har penetrerat varandra och den riktningsom föremålen ska separeras. För att hitta penetrationsdjup och överlapp användes Newton Raphsonsmetod. De experiment som utförts, visade att det är möjligt att använda BREPs som en beskrivning avgeometrier för att producera kollisions information som behövs för att den fysikmotor som används avAGX Dynamics ska kunna hantera kollisioner. En jämförelse mellan trimesh och BREP för att producerakollisionen informationen, visar att dataanvändning är mycket lägre när geometrier representeras medBREPs än trimesh. Resultaten visar också att noggrannheten kan vara väsentligt högre för BREP änför trimesh eftersom dataanvändning för trimesh blir opraktiskt att hantera när noggrannheten är hög.Med hög noggrannhet och med de släta ytor som används med BREP blev den artificiella friction nästanförsumbar, utom i fallen där skärningspunkter inte kunde hittas runt hela skärningskurvor på grund avbegränsningar i algoritmen.

Inspections of bridges are today performed ocularly by an inspector at arm’s lengths distance to evaluate damages and to assess its current condition. Ocular inspections often require specialized equipment to aid the inspector to reach all parts of the bridge. The current state of practice for bridge inspection is therefore considered to be time-consuming, costly, and a safety hazard for the inspector. The purpose of this thesis has been to develop a method for automated modeling of bridges from point cloud data. Point clouds that have been created through photogrammetry from a collection of images acquired with an Unmanned Aerial Vehicle (UAV). This thesis has been an attempt to contribute to the long-term goal of making bridge inspections more efficient by using UAV technology. Several methods for the identification of structural components in point clouds have been evaluated. Based on this, a method has been developed to identify planar surfaces using the model-fitting method Random Sample Consensus (RANSAC). The developed method consists of a set of algorithms written in the programming language Python. The method utilizes intersection points between planes as well as the k-Nearest-Neighbor (k-NN) concept to identify the vertices of the structural elements. The method has been tested both for simulated point cloud data as well as for real bridges, where the images were acquired with a UAV. The results from the simulated point clouds showed that the vertices were modeled with a mean deviation of 0.13− 0.34 mm compared to the true vertex coordinates. For a point cloud of a rectangular column, the algorithms identified all relevant surfaces and were able to reconstruct it with a deviation of less than 2 % for the width and length. The method was also tested on two point clouds of real bridges. The algorithms were able to identify many of the relevant surfaces, but the complexity of the geometries resulted in inadequately reconstructed models. / Besiktning av broar utförs i dagsläget okulärt av en inspektör som på en armlängds avstånd bedömer skadetillståndet. Okulär besiktning kräver därmed ofta speciell utrustning för att inspektören ska kunna nå samtliga delar av bron. Detta resulterar i att det nuvarande tillvägagångssättet för brobesiktning beaktas som tidkrävande, kostsamt samt riskfyllt för inspektören. Syftet med denna uppsats var att utveckla en metod för att modellera broar på ett automatiserat sätt utifrån punktmolnsdata. Punktmolnen skapades genom fotogrammetri, utifrån en samling bilder tagna med en drönare. Uppsatsen har varit en insats för att bidra till det långsiktiga målet att effektivisera brobesiktning genom drönarteknik. Flera metoder för att identifiera konstruktionselement i punktmoln har undersökts. Baserat på detta har en metod utvecklats som identifierar plana ytor med regressionsmetoden Random Sample Consensus (RANSAC). Den utvecklade metoden består av en samling algoritmer skrivna i programmeringsspråket Python. Metoden grundar sig i att beräkna skärningspunkter mellan plan samt använder konceptet k-Nearest-Neighbor (k-NN) för att identifiera konstruktionselementens hörnpunkter. Metoden har testats på både simulerade punktmolnsdata och på punktmoln av fysiska broar, där bildinsamling har skett med hjälp av en drönare. Resultatet från de simulerade punktmolnen visade att hörnpunkterna kunde identifieras med en medelavvikelse på 0,13 − 0,34 mm jämfört med de faktiska hörnpunkterna. För ett punktmoln av en rektangulär pelare lyckades algoritmerna identifiera alla relevanta ytor och skapa en rekonstruerad modell med en avvikelse på mindre än 2 % med avseende på dess bredd och längd. Metoden testades även på två punktmoln av riktiga broar. Algoritmerna lyckades identifiera många av de relevanta ytorna, men geometriernas komplexitet resulterade i bristfälligt rekonstruerade modeller.

La physique de la lumière ainsi que les outils géométriques pour la Conception Assistée par Ordinateur sont à la base des logiciels de simulation des phénomènes lumineux pour la fabrication des systèmes optiques. Ce n'est pas sans difficulté que les industriels conçoivent ces logiciels dont un des principaux handicaps est que les simulations sont très coûteuses en temps. L'objectif principal de ce travail est de rechercher et développer des algorithmes de calcul plus performants. Dans un premier temps, on décrit précisément le modèle du transport des photons dans ce contexte, composé de l'équation de Boltzmann accompagné de conditions de bord, et qui, dans le cas de milieux homogènes par morceaux, se ramène à l'équation de radiosité. Ensuite, on présente les outils géométriques utilisés dans le modeleur hybride CSG (Constructive Solid Geometry) et BRep (Boundary Representation) ainsi que les algorithmes de base nécessaires à la recherche d'intersections entre des demi-droites et des objets géométriques. Puis, un tour d'horizon des méthodes d'accélération des calculs en radiométrie par localisation spatiale est présenté. En tenant compte des contraintes industrielles, une telle méthode d'accélération est alors adaptée au contexte puis développée dans un environnement logiciel existant. Des expérimentations numériques montrent l'efficacité des nouvelles bibliothèques. Enfin, une étude théorique des complexités en temps et en mémoire liées aux méthodes de localisation spatiale, faisant intervenir les sommes de Minkowski d'ensembles géométriques, débouche sur une stratégie consistant à minimiser la complexité en temps pour choisir les paramètres de localisation.