   GPU Ray Casting against Triangles - help to understand
  Hi !I`m trying to develop a small raytracer on GPU, and so I`ve set my first goal to create a crude ray caster. It`s only purpose is to generate rays (which I`ve already coded) and test them against triangle data - this is the real problem for me.So what is the hard part, u ask ??Well, as far as I know pixel shaders are run for every "visible" pixel - which means that if I want to render to texture with 512x512 size, I have to have a window matching this size with rendered quad as stream generator. That`s how I`m generating ray directions.But the question is, how to test this rays against triangles ? For example, how should I test 512x512 ray data against 2x2 face data, containing information about two faces ? On CPU it was preety straightforward - for every pixel loop over every face, but as far as I know, using loops on GPU is nothing but effective.I`ve read tons of PDFs about realtime raytracing but I didn`t find any examples showing how to implement classical ray tracing, or it`s first part - ray casting, on GPU without using spatial data structures.So can anybody help me or point in right direction ?Help is really appreciated ;)   
  For what you want, the GPU doesn't "know" about the geometry.  The only thing you're "rasterizing" on the GPU is a quad covering the screen.  (In that case, every fragment drawn is visible.)  All the rest is up to you in the pixel shader.First Google hit:http://gpurt.sourceforge.net/DA07_0405_Ray_Tracing_on_GPU-1.0.5.pdf   ;  Slightly OT: I can't wait til intel's larabee cards come out.Hopefully they'll get popular.I'd LOVE to write straight C++ for my vid card, questions like this wouldnt even need to be asked (:   ;  I highly recommend you to use CUDA::drivers API look at the CUDA programming guideits far easier than messing around with GLSL.Also be aware that only the primary and maybe the secondary rays can be cast efficiently on the GPU, all other rays require you to resort them on the CPU to ray bundles, but I guess you have read this up already   ;Quote:Original post by EmergentFirst Google hit:http://gpurt.sourceforge.net/DA07_0405_Ray_Tracing_on_GPU-1.0.5.pdfAs I`ve said before, I`ve read tons of PDFs - including this one. But, as any other implementation i found it uses uniform grid - and what i need is the simplest ray casting.Quote:Original post by BasirorI highly recommend you to use CUDA::drivers API look at the CUDA programming guideits far easier than messing around with GLSL.I`ve thought about that, but I want to use HLSL.   ;  CUDA can interoperate with D3D and you have access to pointers and you can read and write to memory, with HLSL you are bound to write to a limited number of render targets, whereas CUDA allows you to write to some arbitrary memory that you have allocated, which allows you to use many targets as you wish.This greatly simplifies the calculation of child rays.For each ray intersection you insert a couple of children rays into a list managed by the current CUDA thread (on the GPU) and pre sort themThis is familiar with a merge sort, it first splits up the list into tiny lists of 2 elements, sorts them according to some metric and merges them back.The merge could then be applied to ray lists. Lets say you have 4000 rays and each ray spawns 10 children, so you allocate memory for a) the color buffer to output the ray's contributionb) a buffer to store < numrays * rays>If you don t spawn a ray you need to mark each possible ray in the list as invalid and make sure its placed at the end of your sorted ray array according to your metricThe case that you have hit nothing with a ray could be handled by inserting the current ray at the top of the ray list and mark the rest as invalidThere are parallel versions of merge sort, worth a look.Thus all you do on the CPU is1. run one pass (new rays presorted at the end)2. merge the sorted lists into one huge buffer3. examine the the ray buffer to load the required data sets onto the GPUrepeat 1 until some convergency criteria is fulfilledWhat you need is a hierarchical data structure that you traverse with each rayand the results are evaluated on the CPU to stream in the appropriate data chunks to preceedHave a look at this paper, they are doing ray tracing of volume datasets,but the technique of traversion of the hierarchy is identical.http://artis.imag.fr/Publications/2009/CNLE09/   ;Quote:Original post by w17chm4nAs I`ve said before, I`ve read tons of PDFs - including this one. But, as any other implementation i found it uses uniform grid - and what i need is the simplest ray casting.I`ve thought about that, but I want to use HLSL.It is possible, but uniform grid is highly recommended. Lets say you have stored triangles in texture (texture in format (F.e. 3 pixels wide):triangle1.vertex1.xyz, triangle1.vertex2.xyz, triangle1.vertex3.xyz,triangle2.vertex1.xyz, triangle2.vertex2.xyz, triangle2.vertex3.xyz, ...).Okay imagine that you have 512 triangles, so you need somehow to generate rays on GPU (but thats easy, you have fullscreen quad - so you just generate direction from camera to vertices of fullscreen quad - you'll have to use imaginary Z for camera - computed to have correct FOV).Then you'll have to do loop (pixel shader works on every pixel in scene - so you have ray direction and ray origin (camera point)) - you'll loop through all 512 triangles (which is overkill, because GPUs aren't build for such huge loops - thats why they use grids), and test ray against each of that triangles (use F.e. barycentric coordinate test - of course written in shader).Anyway as most people said in HLSL, GLSL or CG it's damn complicated. Using CUDA or OpenCL it's much easier.Although I personally prefer ray tracing on CPU, because IMHO it can achieve higher speed than on GPU (With optimizations of course - really good optimized BIH or KD-tree, SIMD assembly for intersection (using packet tracing), optimized oversampling to just edges = antialiasing must be :D, lights in BIH or BVH structure (gives huge boost to shading) and really fast shading (best written in SIMD) and of course heavily optimized code) with this you can achieve on quadcore really good performance.   