Finite Element Shader

Question

I am working on a geometric wrapper for a space jet exhaust impingement solver. A key part of the solution is determining what the jet can "see" and therefore hit. My model is grouped with nodes or grids arranged in 3 or 4 sided elements which are further grouped into bodies. Shading for bodies is handled via outward facing normals and runs very fast, ie backside detection. Shading body to body is currently done by projecting all visible points to the plane of an element and shading the points contained inside the outline of that element provided the z value is greater than the distance to the element. This operation is slow.

My current benchmark is processing only about 3000 elements per second. I know there must be terrible inefficiencies in my code but I feel like this is because of poor approach. I basically check each point until it either is shaded or I run out of elements so it's visible. Loop within loop and another looping check for self-shadowing.

I have looked into 3D Convex Hull and Direct Visibility of Point Sets. Also I looked into Hidden Point Removal. As expected most of the discussion is about 3D rendered applications. I do not have this. All the information is being processed by the CPU and never rendered.

I need suggestions for ways to effectively build/approach such a shader. What things work well, what things to avoid. I do not have access to graphics hardware on the machines that will run the final solution. If it matters I am currently working in C/C++ on Linux systems.

Answer 1

I'm sure you will get other good answers, but in my experience (with ray-tracing) it always helps to see exactly what takes time, and this it the technique I and others use.

Over and above obvious fixes like eliminating needless memory management, what I have found is the sequence of decisions and computations from one ray to the next has strong similarity. That similarity can be exploited to massively speed things up. Chances are something similar can be done in your case.

Answer 2

After researching various ways to do culling and hidden point removal it turns out that my approaches were good. The problem was dividing the space such that I wasn't constantly looking at every point for every surface. The technique I settled on using is called the Octree. The Octree works for my case because I have a large central model that is unchanging and few small items that can move. The large model is divided ahead of time into volume elements. If there are enough points and elements inside a given volume it is subdivided into 8 volumes along the center planes. Using the tree is just a matter of tracing the ray from the source to the point and checking each intersected volume for elements that block the ray. This eliminates the vast majority of the calculations. Volume elements that are not intersected are ignored. Introduction to Octrees, Wikipedia