Finding Ray/Triangle intersection points in GLSL

Started by
9 comments, last by dpadam450 7 years, 10 months ago
Greetings
I am currently trying to figure out what would be the best/fastest method to get information
from a triangle/ray intersection and hit point calculation done in GLSL.
I am currently rendering the Utah teapot (just under 10K triangles) with a simple OpenGL
shader program composed of a vertex shader, geometry shader (for a single pass wireframe)
and a fragment shader.
The geometry shader could do the calculations of the ray/triangle to see if the invocation
(current triangle) is hit and the hit location. But how can I store this information so that the
application can retrieve the closest triangle hit and its hit location ?
I'd like to take advantage of the parallelism of the GPU to avoid iterating through all triangles
and testing them one by one (as on CPU) (in the event I am testing millions of triangles).
Oh, the only constraint, I have to avoid using the Compute Shader.
Thanks for any advice !
Daniel
Advertisement

What information do you need from the intersection, just the point or the triangle index?

NBA2K, Madden, Maneater, Killing Floor, Sims http://www.pawlowskipinball.com/pinballeternal

Hi, ultimately I would need to find the closest hit point from all triangles that were intersected, from a start point in world space.

The index of the triangle is not so important.

The issue I am running into is that there are no shared variables that I can use (like in the Compute shader), so I must be able to store the hit information somehow.

I am currently trying to figure out what would be the best/fastest method to get information
from a triangle/ray intersection and hit point calculation done in GLSL.

To go back to this, there really is no fast way to do this. One way you could do this is to put a camera at the start point of the ray and then look down the ray. Then render the cube, glReadPixels(centerScreenPixel). Then you have the depth from where the center of the camera hit. You can use glUnproject() to get the actual position it hit.

That is of course terrible, I think all ways relative to a graphics card performing raycasting is bad. Compute Shaders would be the way to go for GPU. Otherwise just get download a physics engine or a raytracing engine like Intel Embree, and do a raycast on the CPU. All bullets in big game worlds are done on the CPU and they have many more than 10,000 triangles.

NBA2K, Madden, Maneater, Killing Floor, Sims http://www.pawlowskipinball.com/pinballeternal

Thanks for the advice dpa, an interesting concept, I am new to shading so any tips is helpful.

I've tried using the Transform Feedback, creating a buffer to store if a hit is present and another to store a world space hit locations.

It works great, but the glGetBufferSubData(), to get data back to the app, is just so expensive, nearly 0.8ms just for that call, all other work is lighting fast.

Right now I am looking to see if I can store the hit locations calculated in the Geometry shader ( the ray/triangle intersection algorithm is done there) into an image with the imageStore() and access it from the app per frame, not sure if or how well this will work. I'll give an update on this,

Cheers

I would look at getting a physics engine integrated(PhysX, Bullet, Newton) and using a cpu side raycast.

NBA2K, Madden, Maneater, Killing Floor, Sims http://www.pawlowskipinball.com/pinballeternal

I've tried using the Transform Feedback, creating a buffer to store if a hit is present and another to store a world space hit locations.
It works great, but the glGetBufferSubData(), to get data back to the app, is just so expensive, nearly 0.8ms just for that call, all other work is lighting fast.

Not sure if you tried it, but keep in mind that TF (AKA stream out) can write a varying arount of data to a buffer. So your GS can either not output anything, or output hit depth and triangle index, which would greatly reduce the amount of data to be read back.

Depending on thr number of triangles in the mesh and the accuracy required, you could also use a second pass on the GPU to find the minimum-depth element in that TF buffer. Use a VS that outputs every TF-buffer entry at a hard-coded point location in the middle of a 1x1 pixel render target of 32bit unit format. Use a PS that outputs fixed point depth in the high bits and triangle ID in the low bits (e.g. 16&16). Set the blend mode to MIN (and pre-clear the texture to 0xFFFFFFFF) to get the smallest depth result, along with the corresponding triangle ID encoded in its low bits. Then there's only a single pixel texture to read back to the CPU.

Now though, read backs, no matter how small, are always stupidly expensive if done on the same frame as the commands that produced the data. To maintain high throughput, GPUs have very high command latency and very long pipelines. This latency is usually one to three frames, or in the dozens of milliseconds. Whenever you issue a GL command and immediately try to read back the results, you're asking the driver to flush this long pipeline and stall until it's empty. Not only will this take a dozen ms, but you're got a lovely pipeline bubble when you start using the GPU again afterwards.

To avoid this, you have to also pipeline your GPU queries, such as with double buffering. Ever frame you issue GL commands to generate a result into resource A, and then attempt to read back the results from last frame that are in resource B. Hopefully this avoids flushing the pipeline. To get more certainty, add more frames of buffering to make your pipeline longer...

I don't remember the GL details off the top of my head, but in D3D you can make DEFAULT resources that live on the GPU, and staging resources that live on the CPU. You would issue commands to generate data into GPU_A and commands to copy GPU_A into CPU_A. A frame later, you'd then map CPU_A to read your result.


As above though, why not just use a CPU raytrace? Instead of brute forcing the answer, you'd use a BVH/etc to quickly discard most triangles and then only check a handful.

Those are great explanations Hodgman, i'll be looking into this.

My Utah teapot example is simply a mid-step investigation on how to get the closest ray/triangle intersection point.
I should have explained my whole objective earlier.
My complete objective is somewhat more involved:
I am rendering a dynamic terrain using displacement mapping and viewpoint LOD on tessellation.
I have a Program that contains all shader stages, the Vert/tessC/tessE/Geom/Frag
Multiple co-planar quad patches representing tiles a fed to the pipeline, using a single glDrawArrays().
the Vertex Shader is a simple pass through,
the Tess. Control determins inner outter levels for each tile,
the Tess. Eval does displacement mapping from a 4096x4096 texture.
the Geom. Shader does some visual wireframe calculations (single pass).
the Frag. Shader does normal lighting.
Everything runs very nicely and under 2ms for nealy 200K shaded triangles, I can also do per frame updating of a sub-region of the displacement map (100x100pixels) for a very small cost in frame time (under 0.3ms).
Now I need to be able to ray trace from a single world space position and direction (app level) into the terrain and extract the exact position on the first triangle hit (ray/triangles intersection calculations done in the Geom shader stage seems a very suitable place). Viewpoint dependent tessellation is done in this gl program, the triangles are generated in the pipeline. In order to try to optimize the entire application, I though that calculating the closest hit point there would be best (using the single pass).
I've just tested out the GLSL imageStore/imageRead and the glGetTexImage()x2 (for my simpler teapot example) and again I am able to get the correct closest hit point result, but it's even slower then the TF. I could try out an atomic operation on the image so I would only need a single pixel RGBA32F to contain my hit location (not entire buffer(s)), but I fear that, just like you mentioned, this will still be an expensive operation just to retrieve this single pixel.
I am not too familiar with PBOs, perhaps this could something I look into?
Thanks again for any comments/feedback.
Cheers,
DanielL

I am rendering a dynamic terrain using displacement mapping and viewpoint LOD on tessellation.

Well you want to get away from using displacement that pushes vertices really high away from their triangle, this way you can just raycast against the triangle, then find what pixel maps to that location of the triangle and then offset it. To get the exact displacement depends on your setup. You can always raycast against the actual heightmap of the terrain (that is what I do). You always just raycast againt the heightmap, not the tessellation detail. Again, physics engines usually have a raycast heightmap function which will do this for you. Tessellation is still based upon the height map.

Now if you were tessellation really strangely and the triangles were shifting so much that a hillside moves down drastically, when then yes, you could have something floating above that part of the hill, but your other option is that you have a ton of objects popping up and down all the time.

NBA2K, Madden, Maneater, Killing Floor, Sims http://www.pawlowskipinball.com/pinballeternal

I tested a different mechanism using the atomic operation on images, with interesting results :

Now I do not need 2 buffers of size 10K each (1 buffer for if triangle is hit or not, 1 buffer containing hitPoint locations) for the Transform Feedback OR the GLSL imageLoad()/ImageStore() functions.

I only need a buffer of 1 single unsigned int that will contain "t" the hit distance to a triangle (I use a glTexImage1D of size 1 for now).

The equation for the hit location is "Hit = Start + t*dir ", the "Start" point and "dir" direction are uniforms. Using the atomic operation, I can update the "t" using the imageAtomicMin(), so each geometry shader invocation will securely update this "t" if the result is smaller than the current one held in the image (the single uint).

The application can then get this single "t" and calculate the hit point.

Again, unfortunately the glGetTexImage() I use to retrieve this single uint (4 bytes) is "stupidly expensive" ;o) , costing around 1ms, but the complexity of the setup to find the hit point is drastically reduced.

DanielL

This topic is closed to new replies.

Advertisement