4 ms·

> the result is probably wanted by the CPU -- I think this is a good reason to do it in the CPU. > its not an obvious candidate for offloading the the GPU -- H

> the result is probably wanted by the CPU -- I think this is a good reason to do it in the CPU. > its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind.

willvarfar 10y ago
> its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind. I'm not following your meaning here ;) My blog post describes how to do it in a sweep rather than 'shooting lines', for the performance reasons given in the blog post. 'Shooting lines' is pretty poor for performance because of data locality and cache pressure. In general, locality is the big performance problem with 'ray tracing' in general. All attempts at speeding up ray tracing are about trying to make 'bundles' of adjacent rays flying in close formation that can be combined or computed together so as to try and give some locality to the problem. My scanline approach (line as in cache array of adjacent memory, not line as in line-of-sight between eye and obstacle) is good for CPUs and good for GPUs. If you want to offload viewshed computation to the GPU, you ought strive for a scanline approach rather than 'shooting a ray to every vertex' too. My code ought be straightforward to port to a shader.
- legends2k 10y ago
  My bad! Of course ray tracing in the GPU would be costly; I dunno where I got that. I think my mind is still stuck on 2D after this, need to go back to 3D :) When I had to do picking on a 3D terrain, I did a scanline approach too (https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terrain/Picking/ https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terra...)
PavlovsCat 10y ago
I did something even worse with WebGL, shooting a ray from every light source and view point to every pixel on the screen in the pixel shader (so something has to be in LOS and and lit to be seen). http://i.imgur.com/ZJhr4Ll.png http://i.imgur.com/ZJhr4Ll.png The "player" is sitting on the "wall" of a room, to the right of it there are stairs going "downwards", it's all just a heightmap. Needless to say it's kinda slow, but I was surprised how neat it came out considering how little I put in. I'm sure someone who knows what they're doing (which isn't me) could do the same a lot faster and prettier, since I really did it in the most plump way possible.
- MonkeyDan 10y ago
  Me too. Though it's just rendered as a 2D raster: http://monkeybrains.net/viewshed http://monkeybrains.net/viewshed I'm trying to build something that can be used across the DSM we have of SF for better planning our wireless links.
  - PavlovsCat 10y ago
    Oh, interesting! Shouldn't it be possible to then feed that into a fitness function and randomly "evolve" the "perfect" distribution, or is that silly?
    - MonkeyDan 10y ago
      Totally possible. Though getting data out of WebGL can be hairy. And actually getting on the rooftops of the ideal buildings is a whole nother story.
      - PavlovsCat 10y ago
        Make ease of access (and how much it's wanted there, and so on) part of the fitness function, too :) And future configurations could also take into account how many things you'd have to move, or whatnot (I have no idea about what you're doing, I just imagine that's not something you do once and never change, right?).

willvarfar 10y ago

> its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind. I'm not following your meaning here ;) My blog post describes how to do it in a sweep rather than 'shooting lines', for the performance reasons given in the blog post. 'Shooting lines' is pretty poor for performance because of data locality and cache pressure. In general, locality is the big performance problem with 'ray tracing' in general. All attempts at speeding up ray tracing are about trying to make 'bundles' of adjacent rays flying in close formation that can be combined or computed together so as to try and give some locality to the problem. My scanline approach (line as in cache array of adjacent memory, not line as in line-of-sight between eye and obstacle) is good for CPUs and good for GPUs. If you want to offload viewshed computation to the GPU, you ought strive for a scanline approach rather than 'shooting a ray to every vertex' too. My code ought be straightforward to port to a shader.

legends2k 10y ago
My bad! Of course ray tracing in the GPU would be costly; I dunno where I got that. I think my mind is still stuck on 2D after this, need to go back to 3D :) When I had to do picking on a 3D terrain, I did a scanline approach too (https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terrain/Picking/ https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terra...)

PavlovsCat 10y ago

I did something even worse with WebGL, shooting a ray from every light source and view point to every pixel on the screen in the pixel shader (so something has to be in LOS and and lit to be seen). http://i.imgur.com/ZJhr4Ll.png http://i.imgur.com/ZJhr4Ll.png The "player" is sitting on the "wall" of a room, to the right of it there are stairs going "downwards", it's all just a heightmap. Needless to say it's kinda slow, but I was surprised how neat it came out considering how little I put in. I'm sure someone who knows what they're doing (which isn't me) could do the same a lot faster and prettier, since I really did it in the most plump way possible.

MonkeyDan 10y ago
Me too. Though it's just rendered as a 2D raster: http://monkeybrains.net/viewshed http://monkeybrains.net/viewshed I'm trying to build something that can be used across the DSM we have of SF for better planning our wireless links.
- PavlovsCat 10y ago
  Oh, interesting! Shouldn't it be possible to then feed that into a fitness function and randomly "evolve" the "perfect" distribution, or is that silly?
  - MonkeyDan 10y ago
    Totally possible. Though getting data out of WebGL can be hairy. And actually getting on the rooftops of the ideal buildings is a whole nother story.
    - PavlovsCat 10y ago
      Make ease of access (and how much it's wanted there, and so on) part of the fitness function, too :) And future configurations could also take into account how many things you'd have to move, or whatnot (I have no idea about what you're doing, I just imagine that's not something you do once and never change, right?).