What is the fastest shadowing algorithm (CPU only)?

Question

Suppose I have a 3D model:

The model is given in the form of 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 have to determine:

• [required] which triangles are (partially) shadowed by other triangles

Then, for the partially shadowed triangles:

• [bonus] what fraction of the area of the triangle is shadowed
• [superbonus] come up with a new mesh that describe the shape of the shadows exactly

My final application has to run on headless machines, that is, they have no GPU. Therefore, all the standard things from OpenGL, OpenCL, etc. might not be the best choice.

What is the most efficient algorithm to determine these things, considering this limitation?

Answer 1

Do you have single mesh or more meshes ?

Meaning if the shadow is projected on single 'ground' surface or on more like room walls or even near objects. According to this info the solutions are very different

1. for flat ground/wall surfaces

   is usually the best way a projected render to this surface

   

   camera direction is opposite to light normal and screen is the render to surface. Surface is not usually perpendicular to light so you need to use projection to compensate... You need 1 render pass for each target surface so it is not suitable if shadow is projected onto near mesh (just for ground/walls)

2. for more complicated scenes

   You need to use more advanced approach. There are quite a number of them and each has its advantages and disadvantages. I would use Voxel map but if you are limited by space than some stencil/vector approach will be better. Of course all of these techniques are quite expensive and without GPU I would not even try to implement them.

   This is how Voxel map looks like:

   

   if you want just self shadowing then voxel map size can be only some boundig box around your mesh and in that case you do not incorporate whole mesh volume instead just projection of each pixel into light direction (ignore first voxel...) to avoid shadow on lighted surface