Welcome to the public account: Sumsmile, image vision, mobile development ~~
Follow up a “graphics rendering 5- ray tracing”, to optimize the intersection algorithm.
Implementation effect
The rabbit model below is made up of 4968 triangles
Ignore the background. Vscode previews 3d models. By default, there is a background, which cannot be removed.
Note: A bunny is a baby language.
BVH acceleration
In raytrace rendering, every pixel, the light actually hits the surface of the object and is reflected back into the scene. (In the actual case of spontaneous light, this section simplifies the model and only considers diffuse reflection)
Why is it accelerating
There may be many objects in the scene, and the light of a single pixel needs to be intersected with these objects one by one, and finally the nearest intersection point is obtained by comparison. Other intersection points are ignored if they are occluded.
The rabbit model in the figure above has 4968 triangles, one point in a frame requires nearly 5000 times of rendering, and a rendering of a window of 1280 * 720 requires 4968 * (1280 * 480) times of rendering, which is still a relatively simple model scene.
It’s easy to think, take a cube, surround a single model, cross the cube first, and then cross the geometry that’s inside. Of course, the model can be further divided into n triangles, wrapped in a cube.
There are many forms of bounding box, the most commonly used bounding box length, width, height and x, Y, Z parallel, convenient calculation.
What is a BVH
BVH: Bounding Volume Hierarchy. Surround the box hierarchy.
All models in the scene are split into pieces, the most common forms are space based and object based split. In this paper, objects are divided, iterated continuously, and split into a binary tree. The middle node stores the bounding box, and the child node stores the real object.
The use of BVH
-
Create bounding boxes: Walk through the objects in the scene and split the bounding boxes according to certain rules. You can cut along the longest axis, and there is a limit to the extent to which you can no longer split, you can define it yourself, for example, if there are less than 5 triangles in a bounding box, you can no longer split.
-
Ray intersection: Traverse each node from top to bottom according to the tree traversal mode. Of course, first judge whether the bounding box of the parent node intersects the ray, and then traverse the child nodes if the condition is met. In this way, the algorithm complexity of ray tracing is greatly optimized.
Code core logic
Although it is only a demo, there is the core logic of soft renderer, there is object-oriented encapsulation, there is rendering algorithm.
- Scene (scenario)
- Light (Light)
- Renderer
- Model(geometric Model)
- Utility class
Complete code:
Github.com/summer-go/g…
supplement
- An algorithm for judging the intersection of ray and bounding box
- Ob-loader is a lightweight 3D loading tool
- The model has only diffuse reflection and uses Feng illumination to calculate the color. The rabbit itself has no color and is written as (0.0, 0.5, 0.0) green
Welcome to the public account: Sumsmile, image vision, mobile development ~~
References:
[1]…
[2] ray – box – intersection computes: www.scratchapixel.com/lessons/3d-…
[3] OBJ – Loader: github.com/Bly7/OBJ-Lo…