__Keywords:__cone step mapping raycasting heightmap mip-pyramid

S.A. Mikhailov, R.V. Sapronov

The article discusses several effective ways to reduce build-time of support structures for long-term progressive ray-tracing method, known as method of projecting conical.
The article consists of several sections, beginning with a brief overview of the method of cone step of mapping, consisting of a series of steps, whose purpose is to find a point of intersection of the ray tracing and surface. In carrying out the method in real time using an auxiliary structure that contains at each point the ratio of the radius r to height h at a given point, within which we can move without fear of intersection with the traced surface. The essence of the problem is in build-time of this support structure. An original algorithm for the construction of this structure is described. We present an algorithm for constructing the said shortcomings in terms of execution time and number of operations. For this reason you can not use the algorithm in its original form because of its unprofitable in terms of execution time. Next, we consider two proposed approach, the first of which is called the method jumps.
The method is based the principle of minimizing the number of iterations depending on the topology of the surface. The algorithm is a heuristic, so it runs in the worst case execution time corresponds to the first method, in this case revealed the following deficiencies:
a computational speed of the algorithm is still low;
contains some errors due to the fact that in some cases, the algorithm skips the fine structures.
To eliminate these shortcomings has been developed a second method, called the nested cones method, which meets all of the above conditions. In its implementation the number of iterations was reduced by 4 orders of magnitude, while it is performed using features built into the graphics accelerator, which provides an acceptable speed for cone step mapping method for real-time applications using height maps of arbitrary resolution

References: