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