How to branchless-transform this piece of code?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By AlbGD

I’ve done a vertex shader effect, but couldn’t figure out how to avoid an if statement. (You can also take a look at the entire code on Github).

The method:
-I find a common center to all connected vertices with this arithmetic sequence.
(n is a value I’m looping through from 0 to 159)
originalCenter + (centerOffset * mod(n, widthSize))

vec2 calculatedCenter = vec2(uFirstCenter.x + (uCentersOffset.x * mod(float(n), uGridSize.x)), uFirstCenter.y + (uCentersOffset.y * mod(float(n), 2.0)) + (floor(float(n) / uGridSize.x) * (2.0 * uCentersOffset.y)));

-Compare the distance of vertex to calculated center and store n value if it’s the minimum distance possible. (This is where I’m having trouble)

if (distance(vec2(VERTEX.x, -VERTEX.z), vec2(calculatedCenter.x, calculatedCenter.y)) < closestCenterDistance){
  centerToUse = float(n);
  closestCenterDistance = distance(vec2(VERTEX.x, -VERTEX.z), vec2(calculatedCenter.x, calculatedCenter.y));

This code works as it is, but I don’t really like that if statement for possible performance issues. And it also needs GLSL 3.0 which renders my HTML version invisible for some reason.

What I have tried:
I use the next formula to convert the condition into a 0 or 1, so then I can add that to centerToUse. At the end of the for loop it should give me the nearest n center.

centerToUse += (sign(closestCenterDistance - distance(vec2(VERTEX.x, -VERTEX.z), calculatedCenter)) + 1.0) * 0.5;

closestCenterDistance = min(closestCenterDistance, distance(vec2(VERTEX.x, -VERTEX.z), calculatedCenter));

What I really need
I know my explanation skills are lacking so don’t worry if this seems super complicated.
What I really need is to know what vertices are connected so they all behave the same way, depending on the distance to the player.

Of course, if you need more info to help me, I’ll be happy to provide it.

if i read this code correctly you are stepping to the whole grid of hexagons and calculate the center of the hexagons, then your are checking this against the vertex position to find the closest hex center to this vertex? So i assume that the hexagons are not touching, if this where the case the verticies couldnt be seperated by there hexagon.

If thats the case, i think there must be a way to directly calculate the coresponding hex center without looping through the grid.

klaas | 2020-08-25 22:09

Hey! thank you very much for the reply.

Yes, you are correct about the logic. I’m looping through all possible centers and then choosing the closest one. You are also correct about the hexagons not touching each other, they have a very small gap in between, so it’s easier to identify them individually.

My math skills are failing me, so up until now I haven’t found the correct relationship between the vertex position and it’s center. What I’ve found however, is this answer from stackoverflow, which I haven’t tried yet. I’m hoping it solves our grid problem. I’ll keep everyone updated, if I find a solution.

AlbGD | 2020-08-26 02:19

have a look at this …

do you see the pattern?

Now for some pseudocode

var rx = x rounded to grid 0.5
var ry = rounded to grid 0.866
var cx #cell center x
var cy # cell center y
if is_even(rx) and is_odd(ry):
    if rx >  x and ry > y:
       #upper left corner
       cx = rx + 1
       cy = ry + 1
    elif rx > x and ry < y:
       #lower left corner
       cx = rx + 1
       cy = ry -1
    elif rx < x:
        #center left corner
        cx = rx - 2
        cy = ry

if is_odd(rx) and is_even(ry):
     # do the same as above for this case

var realCenter = Vector(cx*grid_x_steps,cy*grd_y_steps)

make this branchless

#now branchless
var cond1 = is_even(rx) * is_odd(ry):
var cond2 = is_odd(rx) * is_even(ry):

var subCond1 = cond1 * (rx > x) * (ry > y)
var subCond2 = cond1 * (rx > x) * (ry < y)
var subCond3 = cond1 * (rx < x) * equal(ry, y) # approx check here

cx = rx + subCond1 * 1 + subCond2 * 1 + subCond3 * -2
cy = ry + subCond1 * 1 + subCond2 * -1

have’nt tested … just from my imagination

klaas | 2020-08-26 06:58

Hey, You nailed it!
I did a simpler test with only four hexagons, and it worked like a charm.
Thank you very much for your help klaas :D, I’ll update the github repo on a few days, and I’ll give you credit for this improved method.

How do I choose your comment as the best answer?

AlbGD | 2020-08-27 20:03

Nice to hear!
so it seems to work
there is a litle flaw but that seems to cause no problem

to make a propper if elseif you have to multiply by the inverse of the previous subcondition (i think)

var subCond1 = cond1 * (rx > x) * (ry > y)
var subCond2 = not(subCond1) * cond1 * (rx > x) * (ry < y)
var subCond3 = not(subCond2) * cond1 * (rx < x) * equal(ry, y) # approx check here

I have no idea how to make it the best answer

klaas | 2020-08-27 20:12