La génération d'images de synthèse pour la production cinématographique n'a cessé d'évoluer durant ces dernières décennies. Pour le non-expert, il semble que les effets spéciaux aient atteint un niveau de réalisme ne pouvant être dépassé. Cependant, les logiciels mis à la disposition des artistes ont encore du progrès à accomplir. En effet, encore trop de temps est passé à attendre le résultat de longs calculs, notamment lors de la prévisualisation d'effets spéciaux. La lenteur ou la mauvaise qualité des logiciels de prévisualisation pose un réel problème aux artistes. Cependant, l'évolution des cartes graphiques ces dernières années laisse espérer une potentielle amélioration des performances de ces outils, notamment par la mise en place d'algorithmes hybrides rasterisation/ lancer de rayons, tirant profit de la puissance de calcul de ces processeurs, et ce, grâce à leur architecture massivement parallèle. Cette thèse explore les différentes briques logicielles nécessaires à la mise en place d'un pipeline de rendu complexe sur carte graphique, permettant une meilleure prévisualisation des effets spéciaux. Différentes contributions ont été apportées à l'entreprise durant cette thèse. Tout d'abord, un pipeline de rendu hybride a été développé (cf. Chapitre 2). Par la suite, différentes méthodes d'implémentation de l'algorithme de Path Tracing ont été testées (cf. Chapitre 3), de façon à accroître les performances du pipeline de rendu sur GPU. Une structure d'accélération spatiale a été implémentée (cf. Chapitre 4), et une amélioration de l'algorithme de traversée de cette structure sur GPU a été proposée (cf. Section 4.3.2). Ensuite, une nouvelle méthode de décorrélation d'échantillons, dans le cadre de la génération de nombres aléatoires a été proposée (cf. Section 5.4) et a donné lieu à une publication [Dufay et al., 2016]. Pour finir, nous avons tenté de combiner l'algorithme de Path Tracing et les solutions Many Lights, toujours dans le but d'améliorer la prévisualisation de l'éclairage global. Cette thèse a aussi donné lieu à la soumission de trois mémoires d'invention et a permis le développement de deux outils logiciels présentés en Annexe A. / Image synthesis for movie production never stopped evolving over the last decades. It seems it has reached a level of realism that cannot be outperformed. However, the software tools available for visual effects (VFX) artists still need to progress. Indeed, too much time is still wasted waiting for results of long computations, especially when previewing VFX. The delays or poor quality of previsualization software poses a real problem for artists. However, the evolution of graphics processing units (GPUs) in recent years suggests a potential improvement of these tools. In particular, by implementing hybrid rasterization/ray tracing algorithms, taking advantage of the computing power of these processors and their massively parallel architecture. This thesis explores the different software bricks needed to set up a complex rendering pipeline on the GPU, that enables a better previsualization of VFX. Several contributions have been brought during this thesis. First, a hybrid rendering pipeline was developed (cf. Chapter 2). Subsequently, various implementation schemes of the Path Tracing algorithm have been tested (cf. Chapter 3), in order to increase the performance of the rendering pipeline on the GPU. A spatial acceleration structure has been implemented (cf. Chapter 4), and an improvement of the traversal algorithm of this structure on GPU has been proposed (cf. Section 4.3.2). Then, a new sample decorrelation method, in the context of random number generation was proposed (cf. Section 5.4) and resulted in a publication [Dufay et al., 2016]. Finally, we combined the Path Tracing algorithm with the Many Lights solution, always with the aim of improving the preview of global illumination. This thesis also led to the submission of three patents and allowed the development of two software tools presented in Appendix A.

The aim of the research project that is the subject of this thesis is to apply mathematical techniques, especially those in the area of operations research, to the problem of maritime minefield transit. We develop several minefield models applicable to different aspects of the minefield problem. These include optimal mine clearance, shortest time traversal and time constrained traversal. We hope the suite of models and tools developed will help make mine field clearance and traversal both safer and more efficient and that exposition of the models will bring a clearer understanding of the mine problem from a mathematical perspective. In developing the solutions to mine field models, extensive use is made of network path planning algorithms, particularly the Weight Constrained Shortest Path Problem (WCSPP) for which the current state-of-the-art algorithm is extended. This is done by closer integration of Lagrangean relaxation and preprocessing to reduce the size of the network. This is then integrated with gap-closing algorithms based on enumeration to provide optimal or near optimal solutions to the path planning problem. We provide extensive computational evidence on the performance of our algorithm and compare it to other algorithms found in the literature. This tool then became fundamental in solving various separate minefield models. Our models can be broadly separated into obstacle models in which mine affected regions are treated as obstacles to be avoided and continuous threat in which each point of space has an associated risk. In the later case, we wish to find a path that minimizes the integral of the risk along the path while constraining the length of the path. We call this the Continuous Euclidean Length Constrained Minimum Cost Path Problem (C-LCMCPP), for which we present a novel network approach to solving this continuous problem. This approach results in being able to calculate a global lower bound on a non-convex optimization problem.

No description available.

In this dissertation, the problem of planning the motion of m Unmanned Vehicles (UVs) (or simply vehicles) through n points in a plane is considered. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial location(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q(≤ m) UVs and find their motion plans so that all the points are visited and the total cost of the tours of the chosen vehicles is a minimum amongst all the possible choices of vehicles and their tours. This problem is a generalization of the wellknown Traveling Salesman Problem (TSP) in many ways: (1) each UV takes the role of salesman (2) motion constraints of the UVs play an important role in determining the cost of travel between any two locations; in fact, the cost of the travel between any two locations depends on direction of travel along with the heading at the origin and destination, and (3) there is an additional combinatorial complexity stemming from the need to partition the points to be visited by each UV and the set of UVs that must be employed by the mission. In this dissertation, a sub-optimal, two-step approach to motion planning is presented to solve this problem:(1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited is specified, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of Held-Karp’s method. We modify the Lagrangian heuristics for finding a close sub-optimal solution. In the later chapters of the dissertation, we relax the assumption that all vehicles are homogenous. The motivation of heterogenous variant of Multi-depot, Multiple Traveling Salesmen Problem (MDMTSP) derives form applications involving Unmanned Aerial Vehicles (UAVs) or ground robots requiring multiple vehicles with different capabilities to visit a set of locations.

The construction of dams and hydro-power stations are some of the most common anthropogenic changes of watercourses and rivers. While being important to humans and society by providing electricity, these obstructions of watercourses can have severe consequences for the aquatic ecosystems. One consequence is that dams often hinder the important movement of migrating fish species between habitats. This can lead to decline and even extinction of important fish populations. To prevent these negative effects, a number of different fish passage systems, including nature-like fishways, have been developed. Nature-like fishways mimic natural streams in order to function as a natural corridor for a wide range of species. Planning and construction of a nature-like fishway is a complex task that often involves many different interests. In the present study a combination of multi-criteria decision analysis and least-cost path analysis is used for determining the best location for a nature-like fishway past Strömdalen dam in Gavleån, Sweden. An anisotropic least-cost path algorithm is applied on a friction-layer and a digital elevation model, and the least-cost path for a nature-like fishway is determined. The results show that the method is useful in areas of varying topography and steep slopes. However, because low slope is a very important factor when constructing a nature-like fishway, slope becomes the dominating factor in this analysis at the expense of e.g. distance to roads. Combining the methods with results from biological studies of fish behavior and detailed hydrological modelling would provide a very strong tool for the planning of nature-like fishways.

No description available.

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés. / Let G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture.

Approved for public release; distribution is unlimited / Unmanned vehicle technology has matured significantly over the last two decades. This is evidenced by its widespread use in industrial and military applications ranging from deep-ocean exploration to anti-submarine warefare. Indeed, the feasiblity of short-range, special-purpose vehicles (whether aunonomous or remotely operated) is no longer in question. The research efforts have now begun to shift their focus on development of reliable, longer-range, high-endurance and fully autonomous systems. One of the major underlying technologies required to realize this goal is Artificial Intelligence (AI). The latter offers great potential to endow vehicles with the intelligence needed for full autonomy and extended range capability; this involves the increased application of AI technologies to support mission planning and execution, navigation and contingency planning. This thesis addresses two issues associated with the above goal for Autonomous Underwater Vehicles (AUV's). Firstly, a new approach is proposed for path planning in underwater environments that is capable of dealing with uncharted obstacles and which requires significantly less planning time and computer memory. Secondly, it explores the use of expert system technology in the planning of AUV missions.

Failure Independent Path-Protecting (FIPP) p-Cycles is a recently proposed protection architecture for transport networks that extends the properties of mesh-like efficiency and ring-like speed of span-protecting p-cycles to path protection. FIPP pcycles provide shared end-to-end protection to working paths and exhibit properties of pre-connection, end-node activation and failure independence. In his thesis we advance the state of the art in FIPP p-cycle networking. We first introduce two new methods for FIPP p-cycle network design: FIPP column generation (CG) and FIPP iterative heuristic (IH). This is followed by the introduction of a new method for joint capacity placement design called FIPP disjoint route set (DRS) joint capacity placement (JCP) which is followed by an in-depth investigation on the effects of jointness in FIPP p-cycle designs. Next we introduce a series of comparative case studies involving several pre-connected network survivability architectures in the context of transparent optical networking. These studies include topics of single, dual and node failure restorability, minimum wavelength assignment and transparent reach analysis. The final contribution of this thesis is the investigation of the capital expenditure associated with the implementation of FIPP p-cycle designs using optical transport networking equipment as described in the NOBEL cost model. A new method called FIPP maximize unit path straddlers (MUPS) is introduced as part of this final study in order to utilize the property of same wavelength protection. This new approach is motivated by opportunities for cost reduction discovered in the initial costing exercise of the NOBEL cost model investigation.

A partir da abertura comercial brasileira em 1990, verifica-se a ascensão de processos comerciais dinâmicos trazidos pela globalização. Assim, o fenômeno da multiterritorialidade surge como alternativa a estudos como o da internacionalização de empresas. Para atuar neste sentido, as organizações deparam-se com espaços físicos e simbólicos, de onde emergem os elementos de mesma ordem. Porém, poucos são os estudos acerca do fenômeno multiterritorial, tampouco sobre os elementos físicos e simbólicos. Além disso, tendo em vista que o estudo trata de uma trajetória histórica verificada através da análise de path dependence, estes elementos estarão presentes nas ações referentes a uma parceria entre organizações, as quais serão observadas através da ótica de seus respectivos stakeholders. A revisão teórica, portanto, focou-se na relação existente entre path dependence, e o desdobramento de um processo de projeção histórica sobre a multiterritorialidade, bem como acerca dos elementos físicos e simbólicos que a cercam. Deste modo, a teoria dos stakeholders veio auxiliar na categorização dos diferentes tipos de grupos ou indivíduos envolvidos, podendo afetar ou ser afetados, pelas organizações. Foi elaborado um estudo de caso diante da parceria de uma empresa multinacional à jusante da cadeia coureiro-calçadista, com uma empresa agente de exportação de calçados, da cidade brasileira de Novo Hamburgo, localizada no polo regional calçadista do Vale do Rio dos Sinos. Os dados primários foram coletados por meio de entrevistas semi-estruturadas com stakeholders das duas empresas. Os principais dados secundários das empresas foram, respectivamente, na empresa multinacional, o website, o código de conduta na produção de calçados e apresentações documentais sobre a mesma, ao passo em que na empresa agente, o conteúdo pertinente foi alcançado através de publicações próprias e documentos oficiais, como o manual de qualidade empresarial. Os resultados apontam que a estrutura de análise da presente pesquisa foi um mecanismo válido para a identificação, observação e, estudo dos elementos físicos e simbólicos na trajetória multiterritorial da parceria internacional. Evidenciam também, os elementos que receberam mais atenção dos entrevistados, são eles: mudanças de sistemas, mudanças de processos, mudanças de práticas, mudanças de estilos de gestão, padronização, adesão a mudanças, interesses econômicos, abertura de mercados, declínio de mercado, impactos econômicos, impactos sociais e redução de operações. Estes elementos regem o fenômeno multiterritorial. Além disso, um resultado relevante encontrado na pesquisa foi a predominância de elementos de origem simbólica, o que deve ser ressaltado diante de pesquisas que não consideram tais elementos com tamanha importância na comparação com elementos materiais ou físicos. Na análise entre stakeholders do Brasil e EUA, os elementos físicos tiveram razoável importância e os simbólicos, muita importância, para ambos os países. Já na análise entre diferentes categorias de stakeholders, foi dada razoável importância aos elementos físicos por todos eles e, muita importância para os simbólicos por stakeholders e stakekeepers; contudo, para os stakewatchers, os elementos simbólicos são apenas importantes. Assim, a presente pesquisa poderá servir como alternativa para estudos que envolvam parcerias organizacionais e mudança territorial. Percebe-se a oportunidade obtida para o desenvolvimento exploratório acerca de elementos simbólicos que permeiam esses temas. Portanto, pode-se analisar ainda mais a percepção de stakeholders com relação a estes elementos simbólicos. / Since the opening of the brazilian international trade in 1990, there is the rise of dynamic business processes introduced by globalization. Thus, the phenomenon of multi-territoriality is an alternative to studies such as the internationalization of companies. To act in this way, organizations are faced with physical and symbolic spaces, from which emerge the elements of the same order. However, there are few studies about the multi-territory phenomenon, nor on the physical and symbolic elements. Moreover, considering that the study is reflected in a historical trajectory verified by path dependence analysis, these elements will make part of actions related to a partnership between organizations, which will be seen through the perspective of their respective stakeholders. The theoretical review, therefore, focused on the relationship between path dependence, and the development of a historical projection process about multi-territoriality, and about the physical and symbolic elements that surround it. Thus, the theory of stakeholders came assist in categorizing the different types of groups or individuals involved, which may affect or be affected by organizations. A case study was prepared for analyzing the partnership of a multinational in downstream of the leather footwear chain, with a business agent for export of shoes, located in the brazilian city of Novo Hamburgo, in the regional shoes cluster of Vale do Rio dos Sinos. Primary data were collected through semi-structured interviews with stakeholders of both companies. The main secondary data of the companies were, respectively, in the multinational company, the website, the code of conduct in the production of footwear, and the documentary presentations, while that in the agent company, the content has been achieved through its own publications and official documents, such as the corporate quality manual. The results indicate that the structure of analysis of this research was a valid mechanism for identification, observation and study of physical and symbolic elements in the multi-territory trajectory of international partnership. Also highlight the elements that received the most attention from respondents, they are: changes of systems, changes of processes, changes of practices, changes of management styles, standardization, adherence to changes, economic interests, opening markets, declining of market, economic impacts, social impacts and reduction of operations. These elements guide the multi-territorial phenomenon. Moreover, a relevant result found in the research was the predominance of symbolic origin’s elements, what should be emphasized since there are researches that do not consider such elements with this importance in comparison with material or physical elements. Analyzing stakeholders from Brazil and USA, the physical elements were considered reasonably important, and the symbolic very important, for both countries. In the analysis among different categories of stakeholders, has been given reasonable importance to the physical elements by all of them, and the symbolic elements were considered very important by stakeholders and stakekeepers; although, for stakewatchers, the symbolic elements are merely important. Thus, this research may serve as an alternative to studies involving organizational partnerships and territorial change. This can be seen as the opportunity for exploratory development on the symbolic elements that permeate these themes. Therefore, the perception of stakeholders can be even more analyzed, regarding these symbolic elements.