Shortest path ray tracing on parallel GPU devices

Weight precalculation

The weight of each edge is the traveltime between its adjacent vertices. This traveltime is calculated by integrating the velocity model along the spatial location of the edge. As the graph weights are going to be used several times during the ray tracing we choose to precalculate them. Algorithm 1 is a kernel function that performs this precalculation concurrently.

As this kernel is launched for each vertex, the first step is to obtain the indices $(col,row)$ of the current thread. Next we calculate the traveltime from vertex $(col,row)$ to each of its neighbors $(i,k)$. The array $w$ will keep these values.