Colloquy Cycle on Thursday, December 5, 1996 - 16:15

Parallel implementation of sequential algorithms not only brings changes into the structure of programs, but also forces programmers to move their interest towards specific hardware platforms. Already known "best sequential" algorithms have to be sometimes changed so that their efficiency is reduced by additional overhead needed for synchronization and communication among processes. Unfortunately the ray-tracing algorithm is very time consuming and the cost of the computation of different parts of the images is not the same. There have been some approaches developed in the last years as space subdivision and image subdivision. Naturally they have some advantages and disadvantages and therefore the researches have tried to go further and decrease the shortcomings of parallel solutions. In this lecture the traditional approaches with their results will be outlined. Then the lecture will be devoted to the reasearch performed recently on ray-tracing of large scenes using data prefetching. The results achieved in our research team in Prague will be presented as well.

Constraints have been used from the early 60's and now they are a common feature of todays professional graphics modeling systems. Constraints define the relations between objects which have to be satisfied. With the growing speed of computer hardware, new algorithms for solving sets of constrains are developed, especially for geometric constraints. There have been developed some new approaches during the last years which nearly reach interactive speed. Faster algorithms for solving the CSP (Constraint solution problem) use additional information obtained by analyzing properties of the used constraints or by analyzing the graph structure of the CSP. Traditional approaches will be outlined in the lecture. Then we will talk about our new algorithm for solving constraints - the minimal change method. The lecture will cover some ideas to speed up the solving process using the analyzed graph of the CSP.