The paper considers an original approach to the semi-synchronous calculation of the luminance of caustic and indirect illumination for the group of methods based on the bidirectional stochastic ray tracing with backward photon maps. The designed parallelization method uses the two-level threads hierarchy. The low level of this thread hierarchy is synchronous calculations of the part of the whole image defined by a randomly generated pixel mask which is applied to the whole image. The top level is semi-synchronous parallelization level that consists groups of the low level threads which of them calculate own part of the whole image in a way similar to asynchronous calculations. As the top level is semi-synchronous it means that when calculating the luminance of the caustic and indirect illumination, the threads of the low level have access to the data accumulated in the backward photon maps of the other parallel threads of the semi-synchronous level. A special algorithm for organizing an access to data of the upper-level threads avoids delays associated with data synchronization. The comparison of the developed solution with purely synchronous and asynchronous parallelization methods is presented.
Realistic rendering is a significant component that is commonly used in the modern realistic visualization, virtual prototyping and virtual reality systems. In addition, it is used to solve a wide range of applied problems, including the realistic images forming, optical effects simulation, virtual prototyping of complex optical systems, etc. With increasing computing power and computation architecture complexity of modern computer systems, both the complexity of tasks for virtual prototyping and the required accuracy of calculations raise. The tasks of virtual prototyping, solved by physically correct realistic visualization methods, include modeling the illumination of optical systems, modeling the human perception of synthesized images formed by complex optical systems, such as, for example, virtual or mixed reality systems, indicators on the windshield, and others.
Traditionally realistic rendering algorithms are based on the Monte-Carlo ray tracing
methods which are used to calculate the luminance. These ray tracing methods can be
forward, backward or bidirectional. The most universal of these method for calculating
the physically correct luminance of indirect and caustic illumination are the methods
based on the use of photon maps [
There are existing solutions aimed on parallelizing the photon mapping rendering
algorithms using synchronous calculations on multi-core CPU [
In the scope of the current research we used the method based on bidirectional ray
tracing with backward photon mapping [
The Two-Level Semi-Synchronous Parallelization Method 3 3. Forward ray tracing when forward rays from light sources are generated and traced in the scene. By intersecting with previously formed backward photon maps, the indirect and caustic luminance is accumulated. 4. Final image forming when the luminance accumulated in backward photon maps is added to corresponding pixels of the image and weighted. The image accuracy is estimated and if the required accuracy is not achieved then calculation continue from the first step. The traditional parallelization methods used for ray tracing-based rendering are synchronous and asynchronous calculations. Both traditional methods were implemented and tested on 12 cores of the Intel Xeon 6230 CPU and standard Cornell box scene. Ray tracing and processing speedup test results are presented on Fig. 2 and Tables 1 and 2.
Synchronous calculations method for parallelizing the rendering process on a
multicore system is using all available cores in a synchronous way. In this case all threads
share the same memory pool and render the same scene in synchronous way. The main
problem of this approach is presence of the non-parallelizable parts of the algorithm
that according to the Amdahl’s law [
In opposite to the synchronous calculations method the asynchronous calculations use one main thread and a group of computation threads. Each of these computation thread performs the independent rendering of the whole image, and the main thread is used to control the computation threads and gather rendering results from the computation threads. Due to asynchronous nature of calculation all computation threads use their own private memory and as result it multiplies the memory usage of the whole rendering process by number of computation threads. As result as it can be seen from the presented graph the number of traced and processed rays growth linearly when increasing the number of the used cores. At the same time after 10 minutes of calculations using all computation cores the synchronous method achieved the accuracy of 3.9%, while asynchronous method achieved the accuracy of 5.1%. So even if asynchronous method traces and processes more rays the accuracy attained after 10 minutes of calculations of the same scene is lower comparing to synchronous calculations. The main reason of this slowdown is that in case of the asynchronous calculations the whole available memory is split between threads and as result rays are processed in smaller groups resulting in less connections made between light sources and camera pixels.
2.3
The research goal was to unite the scalability of the asynchronous calculations with higher accuracy of the synchronous calculations in the most effective way. So, in the scope of the current research the semi-synchronous parallelization method was developed. This method consists of two parallelization levels: synchronous and semi-synchronous.
The first parallelization level is synchronous rendering of the part of the whole scene image defined by the random mask, mainly of 32x32 pixels size. This mask defines image pixels that are used at the backward ray tracing step for the backward photon map forming. Each rendering step is parallelized independently in a synchronous way with one main thread that controls the rendering method workflow. The synchronous parallelization level is shown on the Fig. 3.
The second parallelization level is semi-synchronous that unites several of synchronous thread groups to render the whole scene in semi-synchronous way. Each group of synchronous threads have their own random mask. These masks are generated by the main thread so that they cover all image pixels and at the same time do not intersect with each other. Once in a several number of rendering phases all threads are synchronized, the whole rendered image is formed, and masks are re-randomized. This re-randomization is required to guarantee that all synchronous thread groups have about equal load and all image pixels are processed equally. Each of the synchronous thread groups uses their own backward photon maps as result multiplying the memory usage required to store maps by the number of synchronous thread groups, however the size of each of these maps can be made smaller comparing to a map built for the whole image. The semi-synchronous parallelization level is shown on the Fig. 4. It is possible that at the forward ray tracing step of the rendering method the forward ray traced by one synchronous group of threads do not find an intersection with the own backward photon maps, however this ray might result in the luminance forming in backward photon maps of the other synchronous groups of threads. To increase the ray processing ratio of the traced forward rays it is required provide an access to all backward photon maps that exist at the moment. This means that some flag should be maintained by the backward photon maps owner indicating that maps are available and open for other threads to be used. At the same time these maps should not be closed and deleted while some other thread is using them. The workflow of the rendering process in a synchronous group of threads with opening and closing an access to the own backward photon maps is shown on the Fig. 5.
This opening and closing the access to the own backward photon maps should be performed without interrupting the calculation process and without using the critical sections. So, in the scope of the current research the algorithm of asynchronous access to the backward photon maps was developed. This algorithm uses only atomic operations both to open and close the access to the own backward photon maps and to gain and release access to the other thread’s backward photon maps.
For these needs the backward photon maps active thread counter is stored along with along with each of the backward photon maps. This counter shows how many independent threads are currently accessing corresponding map. If this counter is equal to zero that means that maps either do not exist or are not open for access by not-owner thread. If the counter is more than zero, then maps are available for other threads to be used. Only the thread that created photon maps can increase the counter from zero state. The owner thread can decrease the corresponding counter to zero only if it is equal to 1 that means that no other thread is currently using these maps. To open and close the access to the own backward photon maps at the beginning and end of the forward ray tracing step the following algorithm is used: 1. Increase the own backward photon maps active thread counter by 1 with an atomic increment operation. This would mark the own backward photon maps as ready to be used during forward ray tracing step for indirect and caustic luminance calculation by other threads. 2. Proceed to the forward ray tracing along with indirect and caustic illumination calculation using both own backward photon maps and backward photon maps of the other threads that are open for access at the moment. 3. When the desired number of forward rays are traced and processed try to perform the atomic compare-and-swap operation to decrease the own backward photon maps active thread counter from 1 to 0. a. If the compare-and-swap operation succeeds, then it means that the current thread was the last one accessing these backward photon maps and new access is successfully closed for other threads. b. If the compare-and-swap operation fails it means that some other thread is still accessing current backward photon maps and they cannot be closed at the moment. In this case more forward rays are traced and processed until this compareand-swap operation can be successfully completed.
As result the thread that created the backward photon maps performs the forward ray tracing and processing until two conditions are fulfilled: first the desired number of forward rays are traced and second the access to the own backward photon map can be successfully closed. To guarantee that thread do not get stuck in the forward ray tracing step the forward ray tracing step the thread stops using other backward photon maps after the required number of forward rays is reached. The workflow of the algorithm of opening ang closing an access to the own backward photon maps at the forward ray tracing step is shown on the Fig. 6.
The forward ray tracing step is also modified to account the indirect and caustic luminance that might be formed in backward photon maps of the other threads that are available at the moment of the forward ray tracing. To gain the access to the backward photon maps of the other threads it should temporary increase the other thread’s backward photon maps active thread counter to let it know that it is currently being used. The following operations are performed: 1. First of all, it should check the required backward photon maps active thread counter.
If it is equal to zero, then maps are not available and should not be processed when calculating the indirect and caustic luminance formed by the current ray. 2. If the backward photon maps active thread counter is more than zero, then try to increment it by 1 with an atomic compare-and-swap operation. 3. If the compare-and-swap operation failed, then access was not granted, and this map is ignored when processing current forward ray. 4. If the compare-and-swap operation was successful, that means that access to the other thread’s backward photon maps was successfully granted. 5. If an access was granted, then intersection of forward ray with other thread’s backward photon maps is analyzed and in case of success the indirect and caustic luminance are accounted in corresponding backward photons. Also, the forward ray is accounted in the total energy processed by this backward photon map.
All operations related to increasing the luminance accumulated in the backward photon map and corresponding ray counters are implemented using solely atomic operations to ensure correct luminance accumulation from concurrent threads. The workflow of the forward ray tracing with accounting luminance in all available backward photon maps is shown on the Fig. 7.
As result at the step when the forward ray tracing is performed the thread’s own backward photon maps are available for other threads to accumulate indirect and caustic luminance and all backward photon maps that are available at the moment of tracing the forward ray are used to account the ray’s luminance. As only atomic operations are used in the backward photon maps access algorithms no special synchronization between threads is required that gives linear scalability of the rendering process when increasing the number of cores. Due to the uniform task distribution between different synchronous thread groups this overlapping is quite high and results in more effective forward ray tracing along with indirect and caustic luminance accumulation. 3
The presented parallelization method was implemented and integrated in Lumicept
light simulation software [
As it can be seen the proposed approach have the same linear scalability of traced and process rays with the asynchronous calculation. After 10 minutes of calculations with the Cornell box test scene the synchronous calculations method achieved the accuracy of 3.9%, asynchronous calculation achieved the accuracy of 5.1% and the proposed semi-synchronous calculations achieved the accuracy of 2.6% as result of more effective usage of the backward photon maps formed by different computation threads.
The similar acceleration was achieved not only on Cornell box test scene, but also on scenes with light guiding optical systems, scenes containing volume scattering and others. Corresponding test scenes rendered images are shown on Fig. 10. The developed two-level semi-synchronous parallelization method for the caustic and indirect luminance calculation can significantly increase the efficiency of calculating these luminance components on multicore systems. This approach allowed us to increase the rendering efficiency in non-parallelizable or poorly parallelizable algorithm sections and, when using small number of lower-level computation threads, to achieve an almost linear dependence of the rendering performance on the number of cores used. In addition, two-level semi-synchronous parallelization allows reducing the size of the backward photon maps in the upper-level threads, which makes it possible to speed up the process of maps voxelization and search of intersections with traced rays. The developed approach can be used as a part of a distributed rendering system, providing high performance on a remote server service.