Search code examples
glslhlsl

HLSL/GLSL Find range for integer

Assuming I have a few hundred varying size adjoining ranges 0-100,101-300,301-1000,1001-2000 etc. What would be the fastest way for me to find which range a given integer falls into using HLSL/GLSL?

The ranges will be stored in a constant buffer and I need to find the range from within a vertex shader.

The current brute force approach I am using is far too slow.

int index = 0;
int count = Lookup[index].count;
while (integer > count){
    count += Lookup[index++].count;
}
return index;

Anyone have any ideas?

Solution

  • I would suppose to use binary search instead of linear. This would improve the speed from O(n) to O(log n). The only condition would be that your ranges are sorted and it would be much faster.

    Wikipedia-Entry for binary search