دانلود ترجمه مقاله الگوریتم موازی سریع با الگوی مثلثی مبتنی بر پردازنده گرافیکی – مجله الزویر

بخشی از ترجمه:

چکیده

از آن جایی که تلاقی مثلثی الگوریتم رهگیری پرتو سهم به سزایی در محاسبات دارد، بنابراین افزایش سرعت محاسبه نور و تلاقی مثلثی نقش مهمی در بالا بردن عملکرد الگوریتم رهگیری پرتو دارد. در این مقاله یک الگوریتم موازی تلاقی مثلثی و نوری سریع مبتنی بر GPU ارائه می­شود. این الگوریتم میزان محاسبات آزمون تلاقی مثلثی را با روش تفکیک فضا در ساختار درخت هشت تایی کاهش داده و آزمون تلاقی مثلثی را با استفاده از مختصات گرانیگاهی مثلثی ساده­تر می‌کند. براساس نتایج تجربی، این X-(نسبت به نتایج محاسبه شده در CPU سرعت بیش‌تری دارد.

۱٫ مقدمه
از آن جایی که مسیرهای نوری (اپتیکال) برگشت­پذیر هستند، اکثر الگوریتم‌های رهگیری پرتو نور از طریق مسیریابی نور ساطع شده را از نقطه دید شبیه­سازی می‌کنند. رهگیری هر نور ساطع شده از نقطه دید مستلزم آزمون‌های تلاقی بسیاری است. الگوریتم رهگیری پرتو، در مقایسه با الگوریتم خط اسکن قدیمی با حدود ۷۵% تا ۹۵% محاسبات به کار رفته در عملیات تلاقی به محاسبات بیشتری نیاز دارد. بنابراین، افزایش سرعت آزمون تلاقی در الگوریتم رهگیری پرتو نقش مهمی در بهبود کارایی کلی الگوریتم رهگیری پرتو ایفاء می‌کند. از آن جایی که هر یک از پرتوها مستقل از یکدیگر هستند و هر مسیر مثلثی نیز مستقل است، بنابراین امکان پردازش موازی وجود دارد.

بخشی از مقاله انگلیسی:

۱٫Introduction

Ray tracing algorithm plays an important role in generating 3D realistic graphics. It can reproducenatural light reflection and refraction in the scene, and calculate the total intensity of its role, resulting inrealistic visual effects. Currently, the algorithm has been widely used in various games, commercialanimation software.Since the optical paths are reversible, most of the ray tracing algorithms simulate light via trackinglight emitted from the point of view. Tracking each light emitted from the point of view invokes a largenumber of intersection tests. Compared to traditional scan line algorithm, ray tracing algorithm needs avery large amount of computation with about 75% to 95% of the amount used to calculate theintersection operation. Therefore, speeding up the intersection testing in ray tracing algorithm plays animportant role in improving the overall efficiency of the ray tracing algorithm. Because each light isindependent of each other and each triangular patch is also independent, it is possible for parallel

۲٫Research Status

Today the technologies of realistic rendering mainly include the following[3][8][9] : rasterization,ray casting, radiosity algorithm, ray tracing algorithm. Of these rendering technologies, ray tracingalgorithm can simulate the reflection, refraction, scattering, dispersion and other advanced optical effects,which is hard for other rendering technologies.Ray tracing algorithm is a computationally intensive algorithm, which includes following steps, lightgeneration, space traversal, intersection testing, rendering[7]. Among these steps, intersection testingneeds the most large amount of calculation. In ray tracing, improving the speed of rendering is often atthe expense of realism results[10]. To overcome this problem, many studies have focused on hardwareacceleratedalgorithm[7]. As a result, in recent years the use of GPU-accelerated ray tracing algorithm hasbecome an important trend.

۳٫Ray and Triangle Intersection Acceleration

۳٫۱٫Theory of GPU Computation

GPU and CPU architectures vary widely. GPU has an astonishing ability to handle floating-pointoperations with relatively less functional modules which makes most of transistors composed of varioustypes of dedicated circuit, numbers of pipelines.Compared to CPU, GPU has more memory bandwidth and has a larger number of execution units.We use CUDA as a programming tool, which is NVIDIA GPGPU model. In the CUDA architecture, theprogram is divided into two parts, namely host side and device side. The smallest unit of execution atdevice side is thread and several threads form a block. Threads under the same block can access the sameshared memory, and can be synchronized quickly.3.2.Algorithm OverviewWe use octree spatial subdivision algorithm to subdivide the space of the scene. The algorithmdivides the space cube in three directions which contains the entire scene, into eight sub grid, or boundingbox, organized into an octree. A further subdivision will be done if the number of vertices the boundingbox contains is more than a given threshold. This process will continue until the number of vertices eachleaf node contains is less than a given threshold and the leaf node holds the information of triangularpatches surrounded by vertices. When the light goes through the scene, a simple bounding boxintersection operation can be done to skip those bounding boxes which has nothing to do with the trackinglight, reducing the number of intersection operations. As a result, the computation time can be reduced.Once we find the leaf node intersected with the tracking light, the intersection computation operation canbe done with the tracking light and triangular patches contained in the leaf node. The vertices in thetriangular patches can be represented in the form of triangle barycentric coordinates. By computing theintersection point with tracking light and the triangular patch, we can known whether the tracking lightintersects with the triangular patch according to that whether the intersection point is within the triangle.