The characteristics of irregular algorithms make a parallel implementation difficult, especially for PC clusters or clusters of SMPs. These characteristics may include an unpredictable access behavior to dynamically changing data structures or strong irregular coupling of computations. Problems are an unknown load distribution and expensive irregular communication patterns for data accesses and redistributions. Thus the parallel implementation of irregular algorithms on distributed memory machines and clusters requires a special organizational mechanism for a dynamic load balance while keeping the communication and administration overhead low. We propose task pool teams for implementing irregular algorithms on clusters of PCs or SMPs. A task pool team combines multithreaded programming using task pools on single nodes with explicit message passing between different nodes. The dynamic load balance mechanism of task pools is generalized to a dynamic load balance scheme for all distributed nodes. We have implemented and compared several versions for task pool teams. As application example, we use the hierarchical radiosity algorithm, which is based on dynamically growing quadtree data structures annotated by varying interaction lists expressing the irregular coupling between the quadtrees. Experiments are performed on a PC cluster and a cluster of SMPs.

No description available.

Techn. Universiẗat, Diss., 2003--Darmstadt.

BARRETO, Isaac Moreira. Cálculo do Fator-de-Forma exato entre Áreas Diferencial e Finita Usando CSG. 2008. 55 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2008. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T17:52:27Z No. of bitstreams: 1 2008_dis_imbarreto.pdf: 752627 bytes, checksum: 2c1a97d41785e527e97633cc6c7e9756 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T17:56:22Z (GMT) No. of bitstreams: 1 2008_dis_imbarreto.pdf: 752627 bytes, checksum: 2c1a97d41785e527e97633cc6c7e9756 (MD5) / Made available in DSpace on 2016-07-01T17:56:22Z (GMT). No. of bitstreams: 1 2008_dis_imbarreto.pdf: 752627 bytes, checksum: 2c1a97d41785e527e97633cc6c7e9756 (MD5) Previous issue date: 2008 / The Ray-Tracing and Radiosity methods are the main representatives of the method that solve the global illumination problem. In both mthods it is necessary to know the energy tranfer ratio between two areas. This ratio, called form factor, is one of the key concepts in Radiosity methods and is being more frequently used in Ray-Tracing methods with finite area light sources. There are many methods for the computation of the form factor, most of them are approximative due to a matter of performance, but, in some specific cases, the extra computational effort needed to compute the exact value of the form factor can improve the overall performance of the illumination method. In general, in these cases, the computational effort needed to obtain an acceptable approximation of the form factor outweighs the effort necessary to compute the exact value. Furthermore there are situation, for example, shadow boundary shading, in which a high precision is far more important than a performance gain. In this work we present a method to compute the exact form factor between a finite area and a differential area which uses CSG techniques to identify the ooccluded areas of the source. / Os métodos de Ray-Tracing e Radiosidade são os principais representantes dos métodos existentes para resolver o problema de iluminação global. Em ambos os métodos se faz necessário saber a taxa de transferência de energia luminosa entre duas áreas. Essa taxa de transferência, chamada de fator-de-forma, é um dos pontos principais no método de Radiosidade e vem sendo usado cada vez com mais frequência em métodos de Ray-Tracing com fontes luminosas de área finita. Existem vários métodos para o cálculo do fator-de-forma, a maioria deles são aproximativos por uma questão de desempenho. Porém, em casos específicos, o trabalho extra para calcular o valor exato do fator-de-forma pode melhorar o desempenho global do método. Em geral, nesses casos, o esforço necessário para se obter uma aproximação aceitável do valor do fator-de-forma supera o esforço necessário para calcular o valor exato em si. Além disso, existem situações, tais como a renderização nas áreas de fronteiras de sombras, em que uma alta precisão é mais importante do que um ganho no desempenho. Nessas situações, é desejável que o método tenha ao seu dispor uma maneira de calcular o valor exato do fator-de-forma. Neste trabalho é apresentado um método para calcular o fator-de-forma exato entre uma área finita e uma área diferencial que utiliza de técnicas CSG para identificar as áreas ocluídas do polígono emissor.

Orientadores: Anamaria Gomide, Jorge Stolfi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-13T10:58:35Z (GMT). No. of bitstreams: 1 Pereira_DanilloRoberto_M.pdf: 891270 bytes, checksum: 71a9debc6a10f8de7083dd3e33c649a6 (MD5) Previous issue date: 2009 / Resumo: A geração de imagens fotorrealisticas e um desafio importante em computação gráfica. Um ingrediente critico para a obtenção do realismo esta o modelo de iluminação. Em 1986, Jim Kajiya apresentou uma equação integral que define o fluxo de luz (radiosidade) num ambiente de maneira precisa; contudo, ate recentemente, os métodos conhecidos para a resolução dessa equação tinham custo computacional e complexidade de implementação elevados. Em 2008, Jaako Lehtinen desenvolveu uma técnica relativamente simples e eficiente para o calculo da iluminação global em cenas virtuais, usando elementos finitos definidos por pontos de amostragem. Neste projeto de Mestrado, implementamos esse método, e comparamos o resultado usando três tipos diferentes de bases: uma base radial, uma base radial normalizada e uma base de Shepard. Alem da comparação visual, calculamos a radiosidade "exata" para uma cena simples e comparamos quantitativamente esse resultado com os resultados do método de Lehtinen com cada uma das três bases. / Abstract: The generation of realistic images is a major challenge in computer graphics. A critical ingredient for realistic rendering is the lighting model. In 1986, Jim Kajiya presented an integral equation that precisely defines the light flow (radiosity) in a virtual environment; however, until recently, the known methods for solving that equation had high computational cost and implementation complexity. In 2008, Jaako Lehtinen developed a relatively simple and efficient technique for the computation of global illumination in virtual scenes, using finite elements defined by sampling points. In this Masters project, we implemented that method, and compared the results using three different types of bases: a radial basis, a normalized radial basis, and a Shepard basis. Besides visual comparison, we computed the "exact" radiosity for a simple scene and compared quantitatively that result with the results obtained by Lehtinen's method with each of the three bases. / Mestrado / Computação Grafica / Mestre em Ciência da Computação

Universidade Federal do Cearà / Os mÃtodos de Ray-Tracing e Radiosidade sÃo os principais representantes dos mÃtodos existentes para resolver o problema de iluminaÃÃo global. Em ambos os mÃtodos se faz necessÃrio saber a taxa de transferÃncia de energia luminosa entre duas Ãreas. Essa taxa de transferÃncia, chamada de fator-de-forma, à um dos pontos principais no mÃtodo de Radiosidade e vem sendo usado cada vez com mais frequÃncia em mÃtodos de Ray-Tracing com fontes luminosas de Ãrea finita. Existem vÃrios mÃtodos para o cÃlculo do fator-de-forma, a maioria deles sÃo aproximativos por uma questÃo de desempenho. PorÃm, em casos especÃficos, o trabalho extra para calcular o valor exato do fator-de-forma pode melhorar o desempenho global do mÃtodo. Em geral, nesses casos, o esforÃo necessÃrio para se obter uma aproximaÃÃo aceitÃvel do valor do fator-de-forma supera o esforÃo necessÃrio para calcular o valor exato em si. AlÃm disso, existem situaÃÃes, tais como a renderizaÃÃo nas Ãreas de fronteiras de sombras, em que uma alta precisÃo à mais importante do que um ganho no desempenho. Nessas situaÃÃes, à desejÃvel que o mÃtodo tenha ao seu dispor uma maneira de calcular o valor exato do fator-de-forma. Neste trabalho à apresentado um mÃtodo para calcular o fator-de-forma exato entre uma Ãrea finita e uma Ãrea diferencial que utiliza de tÃcnicas CSG para identificar as Ãreas ocluÃdas do polÃgono emissor. / The Ray-Tracing and Radiosity methods are the main representatives of the method that solve the global illumination problem. In both mthods it is necessary to know the energy tranfer ratio between two areas. This ratio, called form factor, is one of the key concepts in Radiosity methods and is being more frequently used in Ray-Tracing methods with finite area light sources. There are many methods for the computation of the form factor, most of them are approximative due to a matter of performance, but, in some specific cases, the extra computational effort needed to compute the exact value of the form factor can improve the overall performance of the illumination method. In general, in these cases, the computational effort needed to obtain an acceptable approximation of the form factor outweighs the effort necessary to compute the exact value. Furthermore there are situation, for example, shadow boundary shading, in which a high precision is far more important than a performance gain. In this work we present a method to compute the exact form factor between a finite area and a differential area which uses CSG techniques to identify the ooccluded areas of the source.

The characteristics of irregular algorithms make a parallel implementation difficult, especially for PC clusters or clusters of SMPs. These characteristics may include an unpredictable access behavior to dynamically changing data structures or strong irregular coupling of computations. Problems are an unknown load distribution and expensive irregular communication patterns for data accesses and redistributions. Thus the parallel implementation of irregular algorithms on distributed memory machines and clusters requires a special organizational mechanism for a dynamic load balance while keeping the communication and administration overhead low. We propose task pool teams for implementing irregular algorithms on clusters of PCs or SMPs. A task pool team combines multithreaded programming using task pools on single nodes with explicit message passing between different nodes. The dynamic load balance mechanism of task pools is generalized to a dynamic load balance scheme for all distributed nodes. We have implemented and compared several versions for task pool teams. As application example, we use the hierarchical radiosity algorithm, which is based on dynamically growing quadtree data structures annotated by varying interaction lists expressing the irregular coupling between the quadtrees. Experiments are performed on a PC cluster and a cluster of SMPs.

Cette thèse traite de la reconstruction 3D par stéréophotométrie, qui consiste à utiliser plusieurs photographies d'une scène prises sous le même angle, mais sous différents éclairages. Nous nous intéressons dans un premier temps à des techniques robustes pour l'estimation des normales à la surface, et pour leur intégration en une carte de profondeur. Nous étudions ensuite deux situations où le problème est mal posé : lorsque les éclairages sont inconnus, ou lorsque seuls deux éclairages sont utilisés. La troisième partie est consacrée à l'étude de modèles plus réalistes, à la fois en ce qui concerne les éclairages et la réflectance de la surface. Ces trois premières parties nous amènent aux limites de la formulation classique de la stéréophotométrie : nous introduisons finalement, dans la partie 4, une reformulation variationnelle et différentielle du problème qui permet de dépasser ces limites. / This thesis tackles the photometric stereo problem, a 3D-reconstruction technique consisting in taking several pictures of a scene under different lightings. We first focus on robust techniques for estimating the normals to the surface, and for integrating these normals into a depth map. Then, we study two situations where the problem is ill-posed: when lightings are unknown and when only two images are used. Part 3 is devoted to more realistic models, in terms of lightings and of surface reflectance. These first three parts bring us to the limits of the usual formulation of photometric stereo: we eventually introduce in Part 4 a variational and differential reformulation of this problem which allows us to overcome these limits.

Die vorliegende Arbeit beschäftigt sich mit dem schnellen Lösen von Randintegralgleichungen auf polygonalen oder polygonal approximierten Oberflächen basierend auf Wavelet-Galerkinverfahren. Ein besonderes Augenmerk gilt dabei der speziellen Problematik der diffusen Beleuchtungsgleichung. Während traditionelle Ansätze für Randintegralgleichungen zu vollbesetzten Systemmatrizen und damit zu einem quadratischen Aufwand führen, nutzen Waveletverfahren spezielle Multiskalenbasen, die eine Kompression der Systemmatrix zu einer dünnbesetzten Matrix und damit einen linear-logarithmischen Aufwand ermöglichen. In der Arbeit wird das H^2-Waveletverfahren als effiziente Umsetzung der Waveletverfahren auf polygonal approximierten Oberflächen basierend auf den Tausch-White-Wavelets entwickelt. Es stellt eine Kombination aus H^2-Techniken, bekannt von dem Gebiet der hierarchischen Matrizen, und rekusiven Wavelettechniken dar. Zum besseren Verständnis werden dazu innerhalb der Arbeit in eigenen Kapiteln das Wichtigste zu den Tausch-White-Wavelets, zu dem allgemeinen Waveletverfahren und der Waveletkompression sowie zu den H^2-Matrizen präsentiert, bevor das H^2-Waveletverfahren detailiert hergeleitet und der entsprechende linear-logarithmische Aufwand bewiesen wird. Der zweite Schwerpunkt der Arbeit liegt auf der diffusen Beleuchtungsgleichung. Die in ihr enthaltene Sichbarkeitsproblematik verhindertete bis jetzt die Anwendung moderner schneller Verfahren und die Reduktion der Kosten auf linear-logarithmischen Aufwand. Mit Hilfe der in dieser Arbeit neu entwickelten speziell auf die diffuse Beleuchtungsgleichung angepassten Waveletkompression ist es jedoch möglich ein dünnbesetzte Systemmatrix aufzustellen und im Bereich des Speichers den gewünschten linear-logarithmischen Aufwand zu erreichen. Alle in der Arbeit entwickelten Algorithmen sind detailiert dargestellt und mit numerische Ergebnissen unterlegt.

No description available.