What is the fastest shading algorithm (CPU only)?

Question

Suppose I have a three-dimensional model:

The model is defined as vertices, faces (all triangles) and normal vectors. The model may have holes and / or transparent parts.

For an arbitrarily placed light source at infinity, I must determine:

• [ required ] whose triangles are (partially) obscured by other triangles

Then for partially shaded triangles:

• [ bonus ] what part of the area of ​​the triangle is shaded
• [ superbone ] came up with a new grid that accurately describes the shape of the shadows

My latest application should run on headless machines, i.e. they don't have a GPU . Therefore, all the standard things from OpenGL, OpenCL, etc. May not be the best choice.

What is the most efficient algorithm for determining these things, given this limitation?

Answer 1

Do you have one grid or more grids?

Meaning if the shadow is projected onto a single surface of the earth or looks more like a room’s walls or even nearby objects. According to this information, the decisions are very different.

• for flat ground / wall surfaces

  usually the best way to project this surface onto the projected

  

  the direction of the camera is the opposite of normal light, and the screen is a render to the surface. The surface is usually not perpendicular to the light, so you need to use the projection to compensate ... For each target surface, 1 pass is required for visualization, so it is not suitable if the shadow is projected onto the nearest grid (only for ground / walls).

• for more complex scenes

  You need to use a more advanced approach. There are a lot of them, and each of them has its advantages and disadvantages. I would use a Voxel map , but if you are limited to a space, it is best to use a stencil / vector approach. Of course, all these methods are quite expensive and without a GPU I would not even try to implement them.

  Here's what the Voxel card looks like:

  

  if you just want to “shade” then the size of the voxel map can only be some bounding box around your grid, in which case you don’t include the entire grid volume instead of projecting each pixel in the direction of the light (ignore the first voxel ...) to avoid shadow on the illuminated surface