清华大学：《计算机图形学基础》课程教学资源（授课教案）光线跟踪加速方法

RayTracingAcceleration(光线跟踪加速·RayTracing- As we mentioned in previous course, ray tracingis one of the most important techniques incomputer graphics. Using ray tracing techniques.we could generate impressive images including alot of visual effects, such as hard/soft shadows,transparence(透明),translucence(半透明)reflection, refraction, texture and so on

Ray Tracing Acceleration(光线跟踪加速) • Ray Tracing – As we mentioned in previous course, ray tracing is one of the most important techniques in computer graphics. Using ray tracing techniques, we could generate impressive images including a lot of visual effects, such as hard/soft shadows, transparence(透明), translucence(半透明), reflection, refraction, texture and so on

Recursive Ray Tracing

Recursive Ray Tracing

Recursive Ray TracingIntersectcolor( vBeginPoint, vDirection){Determine IntersectPoint;Color = ambient color;for each lightColor += local shading term;if(surface is reflective)color += reflect Coefficient *IntersectColor(IntersecPoint, Reflect Ray);else if ( surface is refractive)refract Coefficient *color +=IntersectColor(IntersecPoint, Refract Ray);return color;1

Recursive Ray Tracing IntersectColor( vBeginPoint, vDirection) { Determine IntersectPoint; Color = ambient color; for each light Color += local shading term; if(surface is reflective) color += reflect Coefficient * IntersectColor(IntersecPoint, Reflect Ray); else if ( surface is refractive) color += refract Coefficient * IntersectColor(IntersecPoint, Refract Ray); return color; }

. Effects of ray tracing

• Effects of ray tracing

Ray Tracing Acceleration. Motivation (Limitation of ray tracing- The common property of all ray tracingtechniques is their high time and spacecomplexity.（时空复杂性高）- They spend much time repeatedly for visibilitycomputations, or doing ray object intersectiontesting（主要时间用于可见性计算和求交测试）

Ray Tracing Acceleration • Motivation (Limitation of ray tracing) – The common property of all ray tracing techniques is their high time and space complexity.（时空复杂性高） – They spend much time repeatedly for visibility computations, or doing ray object intersection testing（主要时间用于可见性计算和求交测试）

Ray Tracing Acceleration· How to accelerate?- We will look at spatial(空间的) data structures·Hierarchical（层次性）BoundingVolumes（包围盒·UniformGrids（均匀格点）·Quadtree/Octree（四叉树/八叉树）·K-dtree/BSPtree（空间二分树）- Good spatial data structures could speed up raytracing by 10-100 times

Ray Tracing Acceleration • How to accelerate? – We will look at spatial(空间的) data structures • Hierarchical (层次性) Bounding Volumes (包围盒) • Uniform Grids (均匀格点) • Quadtree/Octree (四叉树/八叉树) • K-d tree / BSP tree (空间二分树) – Good spatial data structures could speed up ray tracing by 10-100 times

RayIntersection- Given a model, and a ray direction, as shown inthe right figure, how to test whether the rayintersect with the model.and how to compute wherethe intersection pointis?

Ray Intersection – Given a model, and a ray direction, as shown in the right figure, how to test whether the ray intersect with the model, and how to compute where the intersection point is?

Ray IntersectionBrute Force methodbooleanIslntersect(Ray r,Modelm)Foreachtriangletin mif IsIntersect(t,r)return trueEndForreturn false-However,thisbruteforce method is costlyneeds O(n) time complexity, n is thenumberoftriangles

Ray Intersection • Brute Force method – However, this brute force method is costly, needs O(n) time complexity, n is the number of triangles boolean IsIntersect(Ray r, Model m) For each triangle t in m if IsIntersect(t,r) return true End For return false

BoundingVolumes(包围盒）· Wrap(包住) things that are hard to test forintersection in things that are easy to test- Example: wrap a complicated triangle mesh in a box- Ray can't hit the real object unless it hits the box- Adds some overhead, but generally pays for itself. Most common bounding volume types:一bounding box(包围盒)and bounding sphere（包围球）一boundingboxcouldbe axis-aligned(和坐标轴平行)ornot

Bounding Volumes(包围盒) • Wrap(包住) things that are hard to test for intersection in things that are easy to test – Example: wrap a complicated triangle mesh in a box – Ray can’t hit the real object unless it hits the box – Adds some overhead, but generally pays for itself • Most common bounding volume types: – bounding box(包围盒) and bounding sphere（包围球） – bounding box could be axis-aligned(和坐标轴平行) or not

BoundingVolumes(包围盒)·Bounding Volume Examplesbounding- Before test ray/objectsphereintersect, First test theray for an intersectionwith the bounding volume:non-aligned: If the ray does not intersectboundingboxwith the bounding volume,axis-alignedtheraywould not intersect withthe objectboundingbor(Easy reject). If intersected, further test ray/objectintersection

Bounding Volumes(包围盒) • Bounding Volume Examples – Before test ray/object intersect, First test the ray for an intersection with the bounding volume: • If the ray does not intersect with the bounding volume, the ray would not intersect with the object. (Easy reject) • If intersected, further test ray/object intersection