Editing Rendering (computer graphics) (section)

=== Ray casting ===
{{Main|Ray casting}}

One of the simplest ways to render a 3D scene is to test if a [[Line (geometry)#Ray|ray]] starting at the viewpoint (the "eye" or "camera") intersects any of the geometric shapes in the scene, repeating this test using a different ray direction for each pixel. This method, called ''ray casting'', was important in early computer graphics, and is a fundamental building block for more advanced algorithms. Ray casting can be used to render shapes defined by ''[[constructive solid geometry]]'' (CSG) operations.{{r|RayTracingGems_1|p=8-9}}{{r|IntroToRTCh6|pp=246-249}}

Early ray casting experiments include the work of Arthur Appel in the 1960s. Appel rendered shadows by casting an additional ray from each visible surface point towards a light source. He also tried rendering the density of illumination by casting random rays from the light source towards the object and [[Plotter|plotting]] the intersection points (similar to the later technique called ''[[photon mapping]]'').{{r|Appel1968}}

[[File:Mandelbulb_p8a.jpg|thumb|[[Ray marching]] can be used to find the first intersection of a ray with an intricate shape such as this [[Mandelbulb]] fractal.]]
When rendering scenes containing many objects, testing the intersection of a ray with every object becomes very expensive. Special [[data structure]]s are used to speed up this process by allowing large numbers of objects to be excluded quickly (such as objects behind the camera). These structures are analogous to [[database index]]es for finding the relevant objects. The most common are the ''[[bounding volume hierarchy]]'' (BVH), which stores a pre-computed [[bounding volume|bounding box or sphere]] for each branch of a [[Tree (data structure)|tree]] of objects, and the ''[[k-d tree]]'' which [[Recursion (computer science)|recursively]] divides space into two parts. Recent [[GPU]]s include hardware acceleration for BVH intersection tests. K-d trees are a special case of ''[[binary space partitioning]]'', which was frequently used in early computer graphics (it can also generate a rasterization order for the [[painter's algorithm]]). ''[[Octree]]s'', another historically popular technique, are still often used for volumetric data.{{r|RealTimeRayTracing|pp=16-17}}{{r|RayTracingGems_Forword_Stich}}{{r|IntroToRTCh6}}{{r|Hughes2014|loc=36.2}}

Geometric formulas are sufficient for finding the intersection of a ray with shapes like [[sphere]]s, [[polygon]]s, and [[polyhedron|polyhedra]], but for most curved surfaces there is no [[Closed-form expression#Analytic expression|analytic solution]], or the intersection is difficult to compute accurately using limited precision [[Floating-point arithmetic|floating point numbers]]. [[Root-finding algorithm]]s such as [[Newton's method]] can sometimes be used. To avoid these complications, curved surfaces are often approximated as [[Triangle mesh|meshes of triangles]]. [[Volume rendering]] (e.g. rendering clouds and smoke), and some surfaces such as [[fractal]]s, may require [[ray marching]] instead of basic ray casting.{{r|IntroToRTCh2}}{{r|RayTracingGems_1|p=13}}{{r|AkenineMöller2018|loc=14, 17.3}}