Shortest path ray tracing on parallel GPU devices

Method

The velocity model is represented as a weighted graph $G=(V,E,W)$ where $V$ is the set of vertices, $E$ the set of edges and $W$ the set of edge weights. Each vertex depicts a location $(x,z)$ in the velocity model in such a way that all locations form a regular rectangular grid that covers the velocity model extension. Figure 1 shows a three layer velocity model. The black dots are the vertex locations. We can also set a double index $(i,k)$ to each vertex based in its column and row in the rectangular grid. As there is a one to one correspondence between vertices and indices, hereafter we will not distinguish between them. The horizontal and vertical separations between locations are $dx$ and $dz$, respectivelly. For simplicity, we will set $dx=dz$.

velmodel
Figure 1. Rectangular grid of vertices in a velocity model.

Graph edges are defined between neighboring vertices. There are various ways to accomplish this. One way is to choose a rectangular neighborhood around the current vertex and define an edge between every other vertex inside the neighborhood and the current one. In Figure 2 displays two of such neighborhoods, one of radius $1$ and the other of radius $2$. A neighborhood with radius $r$ contains $(2r+1)^2-1$ vertices.

order1neigh,order2neigh
Figure 2. Two vertex neighborhoods. (a) radius 1 (b) radius 2.

Shortest path ray tracing on parallel GPU devices