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?

Theophrastus

You can use OpenGL without a GPU, see #7311385 – Lashondra

@PaulR: ...but is that optimal? Does the underlying algorithm, when used that way, not make assumptions about the hardware that could make it less effective on a CPU than strictly necessary? – Theophrastus

I'm not qualified to answer the full question - I just wanted to correct the earlier false assumption that OpenGL could not be used without a GPU. – Lashondra

Just to make sure I understand the question: Given the picture provided, the algorithm would return a few triangles that are just behind the lid handle, some behind the bottom part of the spout and perhaps some near the bottom part of the handle, right? – Hearst

@Marian: yes, plus the entire backside, of course :) So, to put it differently: which triangles are (partially) invisible when viewed from a parallel-ray light source? – Theophrastus

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

Morelock

(1) there are multiple meshes, (2) there are no walls, floors, etc. (my real object is a spacecraft), I'm only interested in self-shadowing of these meshes, (3) ...so basically you're saying ~O(N²) algorithms are really the best known, and it's just because of specialized hardware that these sorts of calculations can be done real fast in things like games? – Theophrastus

there are shortcuts like Voxel map (you render whole scene just twice) or projection polygons (you create projection of each of your mesh onto plane perpendicular to light, polygonize/triangulate it and then while real rendering pass add test if rendered pixel is inside any shadow polygon) for both if rendered pixel is inside shadow just change color to darker one ... Voxel map is fastest by mine opinion but need a lot memory for more precission... but is very easy to implement ... and with trilinear filtering the memory consumption is not that high ... – Morelock

@RodyOldenhuis Actually its not that easy. Theoretically raytracing is a O(log(n)) per sample algorithm its just that practical implementation of rasterizing is blindingly fast O(n) per sample. Also you often raytrace for more than one sample depth. But yeah depth mapping is easy since its jut one trivial rasterization per light for a z-map – Stylet

for each rendered pixel for your mesh surface draw line in light direction from that pixel/voxel position until map boundary and leave the first pixel of this line unrendered. also if you find that rendered Voxel is already in max shadow then stop. the line is simple for loop ... and if the map is not too big (256*256*256 is good enough I thing). it is much faster in comparison to polygonize + projection onto surfaces ... – Morelock