<p>why not building a bounding box (or spheres) hierarchy ?</p>

<p>(but for a shadertoy implementation, the lack of dynamic loop length might spoil the gain ).</p>

CC BY-SA 3.0
2016-02-08T02:40:57.633Z
Do you see that working well when you have N grid cells, each of which may or may not have a sphere in it that you need to test your ray against?  Maybe a bvh would be better when the grid is mostly empty, but have a worse worst case? Hrm..
Alan Wolfe
CC BY-SA 3.0
2016-02-08T03:13:24.527Z
I was thinking using it for the (real) sphere set only, after a first cut to the plate "skin", as you said.

Note that dynamics loops are not totally an issue as long as they are bounded; you can break/return/continue using an if inside. only the longest length for a given warp will be applied to all of its pixel.s The only issue is the code length, since loops and functions are unrolled.
Fabrice NEYRET
CC BY-SA 3.0
2016-02-08T02:09:01.450Z
2016-02-08T02:09:01.450Z
Fabrice NEYRET
<p><a href="https://i.sstatic.net/MZosQ.png" rel="noreferrer"><img src="https://i.sstatic.net/MZosQ.png" alt="enter image description here"></a></p>

<p>I'm working on a shadertoy "snake" game, using the new multi pass rendering abilities to save game state between frames.</p>

<p>I'm using raytracing to render the board (an AABB), and am planning on using spheres to render sections of the snake's body.</p>

<p>The game board is a 16x16 grid and each grid can either have a sphere there (a segment of the snake's body) or not.  Snake body segments don't move, they are just either there on the grid or not.  When the snake moves, a new sphere appears in the front and an old sphere disappears from the back.</p>

<p>The problem I'm trying to solve is how to render the snake body spheres.</p>

<p>For instance, a naive approach would be to store a 16x16 grid in pixels specifying whether there was a snake body in that grid cell or not.</p>

<p>I would then do a ray vs sphere check for up to 256 different spheres within my pixel shader, which seems like a no go.</p>

<p>Another method might be to figure out where the ray begins and ends on the game board (when it's between the high and low height values of where the spheres are) and then use something like bressenham line algorithm to go from the start to the end of the line the ray takes on the board, and check only the grid cells that the ray hits.</p>

<p>The problem there is that it requires a dynamic loop.</p>

<p>Maybe a more practical solution would be to make the camera have a nearly top down view and where the ray enters the playable game world, test any sphere in the cell it hits as well as the 8 neighboring cells.</p>

<p>I'm betting there are some much better solutions that I'm not thinking of.</p>

<p>Does anyone know of any interesting techniques or creative solutions?</p>

<p>Thanks!</p>

<p>Edit: here is an older version of this game i made, which was CPU / software rendered, to give an idea of what I'm planning.</p>

<p><a href="https://i.sstatic.net/y7OLJ.png" rel="noreferrer"><img src="https://i.sstatic.net/y7OLJ.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2016-01-14T00:09:16.400Z
What's the problem with doing a dynamic loop? That seems like the natural way to solve this kind of problem. If the board has a fixed 8x8 size, the longest ray would only pass through 16 squares at most, so it's not a crazy iteration count. And if you restrict the camera angles like you said, so that people can't look straight across the board, you can cut down the longest ray length considerably.
Nathan Reed
CC BY-SA 3.0
2016-01-14T00:17:58.143Z
I've been going down that route without having a better solution, so it's nice to hear your support of it, thanks Nathan.
Alan Wolfe
CC BY-SA 3.0
2016-01-16T06:24:50.037Z
Have you tried using raymarching instead of raytracing? Raytracing is more of a CPU/software rendering oriented algorithm, whereas raymarching with signed distance fields is much more easy to implement on a GPU, IMO.
EvilTak
CC BY-SA 3.0
2016-01-16T06:35:37.547Z
For sphere and axis aligned box, directly finding the intersection with raytracing is the better way to go.  For more complex shapes, sure, ray marching is definitely a nice option.  Ray marching exists to get around having to analytically solve line segment vs arbitrary shape.
Alan Wolfe
<raytracing><real-time><glsl><pixel-shader>
Methods for grid traversal in a glsl pixel shader?
Alan Wolfe
# Methods for grid traversal in a glsl pixel shader?

(Asked by: username_0 on 2016-01-12)

[![enter image description here](https://i.sstatic.net/MZosQ.png)](https://i.sstatic.net/MZosQ.png)

I'm working on a shadertoy "snake" game, using the new multi pass rendering abilities to save game state between frames.

I'm using raytracing to render the board (an AABB), and am planning on using spheres to render sections of the snake's body.

The game board is a 16x16 grid and each grid can either have a sphere there (a segment of the snake's body) or not. Snake body segments don't move, they are just either there on the grid or not. When the snake moves, a new sphere appears in the front and an old sphere disappears from the back.

The problem I'm trying to solve is how to render the snake body spheres.

For instance, a naive approach would be to store a 16x16 grid in pixels specifying whether there was a snake body in that grid cell or not.

I would then do a ray vs sphere check for up to 256 different spheres within my pixel shader, which seems like a no go.

Another method might be to figure out where the ray begins and ends on the game board (when it's between the high and low height values of where the spheres are) and then use something like bressenham line algorithm to go from the start to the end of the line the ray takes on the board, and check only the grid cells that the ray hits.

The problem there is that it requires a dynamic loop.

Maybe a more practical solution would be to make the camera have a nearly top down view and where the ray enters the playable game world, test any sphere in the cell it hits as well as the 8 neighboring cells.

I'm betting there are some much better solutions that I'm not thinking of.

Does anyone know of any interesting techniques or creative solutions?

Thanks!

Edit: here is an older version of this game i made, which was CPU / software rendered, to give an idea of what I'm planning.

[![enter image description here](https://i.sstatic.net/y7OLJ.png)](https://i.sstatic.net/y7OLJ.png)

**Tags:** raytracing, real-time, glsl, pixel-shader

> **Comments:**
> **username_1**: What's the problem with doing a dynamic loop? That seems like the natural way to solve this kind of problem. If the board has a fixed 8x8 size, the longest ray would only pass through 16 squares at most, so it's not a crazy iteration count. And if you restrict the camera angles like you said, so that people can't look straight across the board, you can cut down the longest ray length considerably.  
> **username_0**: I've been going down that route without having a better solution, so it's nice to hear your support of it, thanks username_1.  
> **username_2**: Have you tried using raymarching instead of raytracing? Raytracing is more of a CPU/software rendering oriented algorithm, whereas raymarching with signed distance fields is much more easy to implement on a GPU, IMO.  
> **username_0**: For sphere and axis aligned box, directly finding the intersection with raytracing is the better way to go.  For more complex shapes, sure, ray marching is definitely a nice option.  Ray marching exists to get around having to analytically solve line segment vs arbitrary shape.  

---

## 1 answers

### Answer by username_3 on 2016-02-08. Score: 1 | Accepted answer

why not building a bounding box (or spheres) hierarchy ?

(but for a shadertoy implementation, the lack of dynamic loop length might spoil the gain ).

> **Comments:**
> **username_0**: Do you see that working well when you have N grid cells, each of which may or may not have a sphere in it that you need to test your ray against?  Maybe a bvh would be better when the grid is mostly empty, but have a worse worst case? Hrm..  
> **username_3**: I was thinking using it for the (real) sphere set only, after a first cut to the plate "skin", as you said.  Note that dynamics loops are not totally an issue as long as they are bounded; you can break/return/continue using an if inside. only the longest length for a given warp will be applied to all of its pixel.s The only issue is the code length, since loops and functions are unrolled.  

---

