vegard.wiki - User contributions [en]

GLSL snippets

2024-04-09T09:03:45Z

Vegard: /* Colours */ blue ice gradient

__TOC__

== Signed distance functions ==

=== Antialiasing ===

<source lang="GLSL">
const float scale = 100.;

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
vec2 uv = scale * (fragCoord - .5 * iResolution.xy) / iResolution.y;
float d = sd...(uv);
vec3 col = vec3(1) * smoothstep(-0., 1.5 * scale / iResolution.y, d);
fragColor = vec4(col, 1.);
}
</source>

The point here is to convert the length returned by the distance function into a number of pixels, and then we can smooth the outline over the precise number of pixels that we want (here 1.5).

== Ray marching ==

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
vec3 rayDirection(float fieldOfView, vec2 size, vec2 fragCoord) {
vec2 xy = fragCoord - size / 2.;
float z = size.y / tan(radians(fieldOfView) / 2.) / 2.;
return normalize(vec3(xy, -z));
}
</source>

Note: The original <tt>rayDirection()</tt> is missing the divide by 2 when calculating z. This causes the field of view parameter to be incorrect.

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
float castRay(const int scene, vec3 eye, vec3 dir,
float start, float end, float epsilon, int max_marching_steps,
out int material)
{
float depth = start;
for (int i = 0; i < max_marching_steps; i++) {
float d = sceneSDF(scene, eye + depth * dir, material);
if (d < epsilon)
return depth;

depth += d;
if (depth >= end)
break;
}

return end;
}
</source>

<source lang="GLSL">
// http://iquilezles.org/www/articles/normalsSDF/normalsSDF.htm
vec3 estimateNormal( const int scene, const float epsilon, in vec3 p )
{
int m;

const vec2 k = vec2(1,-1);
return normalize( k.xyy*sceneSDF( scene, p + k.xyy*epsilon, m ) +
k.yyx*sceneSDF( scene, p + k.yyx*epsilon, m ) +
k.yxy*sceneSDF( scene, p + k.yxy*epsilon, m ) +
k.xxx*sceneSDF( scene, p + k.xxx*epsilon, m ) );
}
</source>

== Matrix transformations ==

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glRotate.xml
mat4 rotate(float a, vec3 v)
{
float c = cos(a);
vec3 ci = (1. - c) * v;
vec3 s = sin(a) * v;

return mat4(
ci.x * v.x + c, ci.x * v.y + s.z, ci.x * v.z - s.y, 0,
ci.y * v.x - s.z, ci.y * v.y + c, ci.y * v.z + s.x, 0,
ci.z * v.x + s.y, ci.z * v.y - s.x, ci.z * v.z + c, 0,
0, 0, 0, 1
);
}
</source>

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glTranslate.xml
mat4 translate(vec3 v)
{
return mat4(
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
v.x, v.y, v.z, 1
);
}
</source>

== Noise ==

<source lang="GLSL">
// https://stackoverflow.com/questions/12964279/whats-the-origin-of-this-glsl-rand-one-liner
float rand(vec2 co)
{
return fract(sin(dot(co.xy, vec2(12.9898, 78.233))) * 43758.5453);
}
</source>

== Colours ==

=== HSV ===

==== Plain HSV ====

[[File:hsv2rgb.png|420px|thumb|<tt>hsv2rgb()</tt>]]

<source lang="GLSL">
// https://github.com/hughsk/glsl-hsv2rgb/blob/master/index.glsl
vec3 hsv2rgb(vec3 c) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = abs(fract(c.xxx + K.xyz) * 6. - K.www);
return c.z * mix(K.xxx, clamp(p - K.xxx, 0.0, 1.0), c.y);
}
</source>

==== Smooth variant ====

[[File:hsv2rgb2.png|420px|thumb|<tt>hsv2rgb2()</tt>]]

<source lang="GLSL">
// https://www.shadertoy.com/view/wlsSRB
vec3 hsv2rgb2(vec3 c, float k) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = smoothstep(0. + k, 1. - k,
.5 + .5 * cos((c.xxx + K.xyz) * radians(360.)));
return c.z * mix(K.xxx, p, c.y);
}
</source>

A good value for <code>k</code> is e.g. 0.07.

=== Gamma ===

{{Main|Gamma}}

<source lang="GLSL">
const float gamma = 2.2;

// convert from sRGB to RGB
vec3 col = pow(col, vec3(gamma));

// blending, etc.

// gamma correction (RGB to sRGB)
col = pow(col, vec3(1. / gamma));
</source>

=== Ice gradient ===

[[File:ice_gradient.png|420px|thumb|Blue ice gradient]]

<source lang="GLSL">
vec3 col = smoothstep(vec3(.2, .1, .0), vec3(1.2, 1.1, 1.0), vec3(x));
</source>

== Dithering ==

<source lang="GLSL">
/* https://en.wikipedia.org/wiki/Ordered_dithering */
const float bayer_matrix[64] = float[64](
-0.500000, 0.250000, -0.312500, 0.437500, -0.453125, 0.296875, -0.265625, 0.484375,
0.000000, -0.250000, 0.187500, -0.062500, 0.046875, -0.203125, 0.234375, -0.015625,
-0.375000, 0.375000, -0.437500, 0.312500, -0.328125, 0.421875, -0.390625, 0.359375,
0.125000, -0.125000, 0.062500, -0.187500, 0.171875, -0.078125, 0.109375, -0.140625,
-0.468750, 0.281250, -0.281250, 0.468750, -0.484375, 0.265625, -0.296875, 0.453125,
0.031250, -0.218750, 0.218750, -0.031250, 0.015625, -0.234375, 0.203125, -0.046875,
-0.343750, 0.406250, -0.406250, 0.343750, -0.359375, 0.390625, -0.421875, 0.328125,
0.156250, -0.093750, 0.093750, -0.156250, 0.140625, -0.109375, 0.078125, -0.171875
);

float dither(vec2 uv, float levels, float sharpness, float intensity)
{
int x = int(floor(uv.x)) & 7;
int y = int(floor(uv.y)) & 7;
float threshold = bayer_matrix[8 * y + x];
#if 0 // full dither
return round(levels * intensity + threshold) / levels;
#else // respect sharpness
float major = floor(levels * intensity);
float minor = float(fract(levels * intensity) > .5 + sharpness * threshold);
return (major + minor) / levels;
#endif
}
</source>

== Post-processing effects ==

=== Volumetric light scattering (God rays) ===

[[File:godrays.png|420px|thumb|Example of volumetric light scattering post-processing effect (with dithering).]]

<source lang="GLSL">
// https://developer.nvidia.com/gpugems/gpugems3/part-ii-light-and-shadows/chapter-13-volumetric-light-scattering-post-process
vec3 godrays(in vec2 ScreenLightPos, in vec2 fragCoord, out vec4 fragColor)
{
const int NUM_SAMPLES = 16;
const float Density = .7;
const float Weight = .3;
const float Decay = .88;
const float Exposure = .4;

vec2 texCoord = fragCoord / iResolution.xy;
vec2 deltaTexCoord = (texCoord - ScreenLightPos.xy);
deltaTexCoord *= 1.0f / float(NUM_SAMPLES) * Density;

vec3 color = texture(iChannel0, texCoord).rgb;
float illuminationDecay = 1.0f;

for (int i = 0; i < NUM_SAMPLES; i++) {
texCoord -= deltaTexCoord;

float dither = rand(fragCoord + vec2(200. * float(i), 23. * float(i)));
vec3 sample_ = texture(iChannel0, texCoord + deltaTexCoord * dither).rgb;
sample_ *= illuminationDecay * Weight;
color += sample_;
illuminationDecay *= Decay;
}

return color * Exposure;
}
</source>

Dithering suggested by Jessica Mak.

[[Category:Graphics programming]]

File:ice gradient.png

2024-04-09T09:02:56Z

Vegard: Blue ice gradient

== Summary ==
Blue ice gradient

Tone mapping

2022-12-20T21:55:51Z

Vegard: add ref

{{Stub}}

My own formula (https://www.shadertoy.com/view/Dlf3RM):

<code>
mix(v, vec3(1.), smoothstep(1., 4., dot(v, vec3(1.))));
</code>

== See also ==
* https://learnopengl.com/Advanced-Lighting/HDR
* http://filmicworlds.com/blog/filmic-tonemapping-operators/
* https://64.github.io/tonemapping/
* https://mynameismjp.wordpress.com/2010/04/30/a-closer-look-at-tone-mapping/

[[Category:Graphics programming]]

Tone mapping

2022-12-19T16:52:14Z

Vegard: add my formula + reference

GLSL snippets

2022-12-08T13:18:48Z

Vegard: /* Smooth variant */ fix again

__TOC__

== Signed distance functions ==

=== Antialiasing ===

<source lang="GLSL">
const float scale = 100.;

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
vec2 uv = scale * (fragCoord - .5 * iResolution.xy) / iResolution.y;
float d = sd...(uv);
vec3 col = vec3(1) * smoothstep(-0., 1.5 * scale / iResolution.y, d);
fragColor = vec4(col, 1.);
}
</source>

The point here is to convert the length returned by the distance function into a number of pixels, and then we can smooth the outline over the precise number of pixels that we want (here 1.5).

== Ray marching ==

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
vec3 rayDirection(float fieldOfView, vec2 size, vec2 fragCoord) {
vec2 xy = fragCoord - size / 2.;
float z = size.y / tan(radians(fieldOfView) / 2.) / 2.;
return normalize(vec3(xy, -z));
}
</source>

Note: The original <tt>rayDirection()</tt> is missing the divide by 2 when calculating z. This causes the field of view parameter to be incorrect.

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
float castRay(const int scene, vec3 eye, vec3 dir,
float start, float end, float epsilon, int max_marching_steps,
out int material)
{
float depth = start;
for (int i = 0; i < max_marching_steps; i++) {
float d = sceneSDF(scene, eye + depth * dir, material);
if (d < epsilon)
return depth;

depth += d;
if (depth >= end)
break;
}

return end;
}
</source>

<source lang="GLSL">
// http://iquilezles.org/www/articles/normalsSDF/normalsSDF.htm
vec3 estimateNormal( const int scene, const float epsilon, in vec3 p )
{
int m;

const vec2 k = vec2(1,-1);
return normalize( k.xyy*sceneSDF( scene, p + k.xyy*epsilon, m ) +
k.yyx*sceneSDF( scene, p + k.yyx*epsilon, m ) +
k.yxy*sceneSDF( scene, p + k.yxy*epsilon, m ) +
k.xxx*sceneSDF( scene, p + k.xxx*epsilon, m ) );
}
</source>

== Matrix transformations ==

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glRotate.xml
mat4 rotate(float a, vec3 v)
{
float c = cos(a);
vec3 ci = (1. - c) * v;
vec3 s = sin(a) * v;

return mat4(
ci.x * v.x + c, ci.x * v.y + s.z, ci.x * v.z - s.y, 0,
ci.y * v.x - s.z, ci.y * v.y + c, ci.y * v.z + s.x, 0,
ci.z * v.x + s.y, ci.z * v.y - s.x, ci.z * v.z + c, 0,
0, 0, 0, 1
);
}
</source>

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glTranslate.xml
mat4 translate(vec3 v)
{
return mat4(
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
v.x, v.y, v.z, 1
);
}
</source>

== Noise ==

<source lang="GLSL">
// https://stackoverflow.com/questions/12964279/whats-the-origin-of-this-glsl-rand-one-liner
float rand(vec2 co)
{
return fract(sin(dot(co.xy, vec2(12.9898, 78.233))) * 43758.5453);
}
</source>

== Colours ==

=== HSV ===

==== Plain HSV ====

[[File:hsv2rgb.png|420px|thumb|<tt>hsv2rgb()</tt>]]

<source lang="GLSL">
// https://github.com/hughsk/glsl-hsv2rgb/blob/master/index.glsl
vec3 hsv2rgb(vec3 c) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = abs(fract(c.xxx + K.xyz) * 6. - K.www);
return c.z * mix(K.xxx, clamp(p - K.xxx, 0.0, 1.0), c.y);
}
</source>

==== Smooth variant ====

[[File:hsv2rgb2.png|420px|thumb|<tt>hsv2rgb2()</tt>]]

<source lang="GLSL">
// https://www.shadertoy.com/view/wlsSRB
vec3 hsv2rgb2(vec3 c, float k) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = smoothstep(0. + k, 1. - k,
.5 + .5 * cos((c.xxx + K.xyz) * radians(360.)));
return c.z * mix(K.xxx, p, c.y);
}
</source>

A good value for <code>k</code> is e.g. 0.07.

=== Gamma ===

{{Main|Gamma}}

<source lang="GLSL">
const float gamma = 2.2;

// convert from sRGB to RGB
vec3 col = pow(col, vec3(gamma));

// blending, etc.

// gamma correction (RGB to sRGB)
col = pow(col, vec3(1. / gamma));
</source>

== Dithering ==

<source lang="GLSL">
/* https://en.wikipedia.org/wiki/Ordered_dithering */
const float bayer_matrix[64] = float[64](
-0.500000, 0.250000, -0.312500, 0.437500, -0.453125, 0.296875, -0.265625, 0.484375,
0.000000, -0.250000, 0.187500, -0.062500, 0.046875, -0.203125, 0.234375, -0.015625,
-0.375000, 0.375000, -0.437500, 0.312500, -0.328125, 0.421875, -0.390625, 0.359375,
0.125000, -0.125000, 0.062500, -0.187500, 0.171875, -0.078125, 0.109375, -0.140625,
-0.468750, 0.281250, -0.281250, 0.468750, -0.484375, 0.265625, -0.296875, 0.453125,
0.031250, -0.218750, 0.218750, -0.031250, 0.015625, -0.234375, 0.203125, -0.046875,
-0.343750, 0.406250, -0.406250, 0.343750, -0.359375, 0.390625, -0.421875, 0.328125,
0.156250, -0.093750, 0.093750, -0.156250, 0.140625, -0.109375, 0.078125, -0.171875
);

float dither(vec2 uv, float levels, float sharpness, float intensity)
{
int x = int(floor(uv.x)) & 7;
int y = int(floor(uv.y)) & 7;
float threshold = bayer_matrix[8 * y + x];
#if 0 // full dither
return round(levels * intensity + threshold) / levels;
#else // respect sharpness
float major = floor(levels * intensity);
float minor = float(fract(levels * intensity) > .5 + sharpness * threshold);
return (major + minor) / levels;
#endif
}
</source>

== Post-processing effects ==

=== Volumetric light scattering (God rays) ===

[[File:godrays.png|420px|thumb|Example of volumetric light scattering post-processing effect (with dithering).]]

<source lang="GLSL">
// https://developer.nvidia.com/gpugems/gpugems3/part-ii-light-and-shadows/chapter-13-volumetric-light-scattering-post-process
vec3 godrays(in vec2 ScreenLightPos, in vec2 fragCoord, out vec4 fragColor)
{
const int NUM_SAMPLES = 16;
const float Density = .7;
const float Weight = .3;
const float Decay = .88;
const float Exposure = .4;

vec2 texCoord = fragCoord / iResolution.xy;
vec2 deltaTexCoord = (texCoord - ScreenLightPos.xy);
deltaTexCoord *= 1.0f / float(NUM_SAMPLES) * Density;

vec3 color = texture(iChannel0, texCoord).rgb;
float illuminationDecay = 1.0f;

for (int i = 0; i < NUM_SAMPLES; i++) {
texCoord -= deltaTexCoord;

float dither = rand(fragCoord + vec2(200. * float(i), 23. * float(i)));
vec3 sample_ = texture(iChannel0, texCoord + deltaTexCoord * dither).rgb;
sample_ *= illuminationDecay * Weight;
color += sample_;
illuminationDecay *= Decay;
}

return color * Exposure;
}
</source>

Dithering suggested by Jessica Mak.

[[Category:Graphics programming]]

GLSL snippets

2022-12-08T13:14:09Z

Vegard: /* Smooth variant */ fix saturation/value

__TOC__

== Signed distance functions ==

=== Antialiasing ===

<source lang="GLSL">
const float scale = 100.;

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
vec2 uv = scale * (fragCoord - .5 * iResolution.xy) / iResolution.y;
float d = sd...(uv);
vec3 col = vec3(1) * smoothstep(-0., 1.5 * scale / iResolution.y, d);
fragColor = vec4(col, 1.);
}
</source>

The point here is to convert the length returned by the distance function into a number of pixels, and then we can smooth the outline over the precise number of pixels that we want (here 1.5).

== Ray marching ==

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
vec3 rayDirection(float fieldOfView, vec2 size, vec2 fragCoord) {
vec2 xy = fragCoord - size / 2.;
float z = size.y / tan(radians(fieldOfView) / 2.) / 2.;
return normalize(vec3(xy, -z));
}
</source>

Note: The original <tt>rayDirection()</tt> is missing the divide by 2 when calculating z. This causes the field of view parameter to be incorrect.

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
float castRay(const int scene, vec3 eye, vec3 dir,
float start, float end, float epsilon, int max_marching_steps,
out int material)
{
float depth = start;
for (int i = 0; i < max_marching_steps; i++) {
float d = sceneSDF(scene, eye + depth * dir, material);
if (d < epsilon)
return depth;

depth += d;
if (depth >= end)
break;
}

return end;
}
</source>

<source lang="GLSL">
// http://iquilezles.org/www/articles/normalsSDF/normalsSDF.htm
vec3 estimateNormal( const int scene, const float epsilon, in vec3 p )
{
int m;

const vec2 k = vec2(1,-1);
return normalize( k.xyy*sceneSDF( scene, p + k.xyy*epsilon, m ) +
k.yyx*sceneSDF( scene, p + k.yyx*epsilon, m ) +
k.yxy*sceneSDF( scene, p + k.yxy*epsilon, m ) +
k.xxx*sceneSDF( scene, p + k.xxx*epsilon, m ) );
}
</source>

== Matrix transformations ==

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glRotate.xml
mat4 rotate(float a, vec3 v)
{
float c = cos(a);
vec3 ci = (1. - c) * v;
vec3 s = sin(a) * v;

return mat4(
ci.x * v.x + c, ci.x * v.y + s.z, ci.x * v.z - s.y, 0,
ci.y * v.x - s.z, ci.y * v.y + c, ci.y * v.z + s.x, 0,
ci.z * v.x + s.y, ci.z * v.y - s.x, ci.z * v.z + c, 0,
0, 0, 0, 1
);
}
</source>

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glTranslate.xml
mat4 translate(vec3 v)
{
return mat4(
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
v.x, v.y, v.z, 1
);
}
</source>

== Noise ==

<source lang="GLSL">
// https://stackoverflow.com/questions/12964279/whats-the-origin-of-this-glsl-rand-one-liner
float rand(vec2 co)
{
return fract(sin(dot(co.xy, vec2(12.9898, 78.233))) * 43758.5453);
}
</source>

== Colours ==

=== HSV ===

==== Plain HSV ====

[[File:hsv2rgb.png|420px|thumb|<tt>hsv2rgb()</tt>]]

<source lang="GLSL">
// https://github.com/hughsk/glsl-hsv2rgb/blob/master/index.glsl
vec3 hsv2rgb(vec3 c) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = abs(fract(c.xxx + K.xyz) * 6. - K.www);
return c.z * mix(K.xxx, clamp(p - K.xxx, 0.0, 1.0), c.y);
}
</source>

==== Smooth variant ====

[[File:hsv2rgb2.png|420px|thumb|<tt>hsv2rgb2()</tt>]]

<source lang="GLSL">
// https://www.shadertoy.com/view/wlsSRB
vec3 hsv2rgb2(vec3 c, float k) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = smoothstep(0. + k, 1. - k,
.5 + .5 * cos((c.xxx + K.xyz) * radians(360.)));
return c.z * mix(K.www, p, c.y);
}
</source>

A good value for <code>k</code> is e.g. 0.07.

=== Gamma ===

{{Main|Gamma}}

<source lang="GLSL">
const float gamma = 2.2;

// convert from sRGB to RGB
vec3 col = pow(col, vec3(gamma));

// blending, etc.

// gamma correction (RGB to sRGB)
col = pow(col, vec3(1. / gamma));
</source>

== Dithering ==

<source lang="GLSL">
/* https://en.wikipedia.org/wiki/Ordered_dithering */
const float bayer_matrix[64] = float[64](
-0.500000, 0.250000, -0.312500, 0.437500, -0.453125, 0.296875, -0.265625, 0.484375,
0.000000, -0.250000, 0.187500, -0.062500, 0.046875, -0.203125, 0.234375, -0.015625,
-0.375000, 0.375000, -0.437500, 0.312500, -0.328125, 0.421875, -0.390625, 0.359375,
0.125000, -0.125000, 0.062500, -0.187500, 0.171875, -0.078125, 0.109375, -0.140625,
-0.468750, 0.281250, -0.281250, 0.468750, -0.484375, 0.265625, -0.296875, 0.453125,
0.031250, -0.218750, 0.218750, -0.031250, 0.015625, -0.234375, 0.203125, -0.046875,
-0.343750, 0.406250, -0.406250, 0.343750, -0.359375, 0.390625, -0.421875, 0.328125,
0.156250, -0.093750, 0.093750, -0.156250, 0.140625, -0.109375, 0.078125, -0.171875
);

float dither(vec2 uv, float levels, float sharpness, float intensity)
{
int x = int(floor(uv.x)) & 7;
int y = int(floor(uv.y)) & 7;
float threshold = bayer_matrix[8 * y + x];
#if 0 // full dither
return round(levels * intensity + threshold) / levels;
#else // respect sharpness
float major = floor(levels * intensity);
float minor = float(fract(levels * intensity) > .5 + sharpness * threshold);
return (major + minor) / levels;
#endif
}
</source>

== Post-processing effects ==

=== Volumetric light scattering (God rays) ===

[[File:godrays.png|420px|thumb|Example of volumetric light scattering post-processing effect (with dithering).]]

<source lang="GLSL">
// https://developer.nvidia.com/gpugems/gpugems3/part-ii-light-and-shadows/chapter-13-volumetric-light-scattering-post-process
vec3 godrays(in vec2 ScreenLightPos, in vec2 fragCoord, out vec4 fragColor)
{
const int NUM_SAMPLES = 16;
const float Density = .7;
const float Weight = .3;
const float Decay = .88;
const float Exposure = .4;

vec2 texCoord = fragCoord / iResolution.xy;
vec2 deltaTexCoord = (texCoord - ScreenLightPos.xy);
deltaTexCoord *= 1.0f / float(NUM_SAMPLES) * Density;

vec3 color = texture(iChannel0, texCoord).rgb;
float illuminationDecay = 1.0f;

for (int i = 0; i < NUM_SAMPLES; i++) {
texCoord -= deltaTexCoord;

float dither = rand(fragCoord + vec2(200. * float(i), 23. * float(i)));
vec3 sample_ = texture(iChannel0, texCoord + deltaTexCoord * dither).rgb;
sample_ *= illuminationDecay * Weight;
color += sample_;
illuminationDecay *= Decay;
}

return color * Exposure;
}
</source>

Dithering suggested by Jessica Mak.

[[Category:Graphics programming]]

User:Vegard/Profiles

2022-11-30T07:34:24Z

Vegard: Twitter -> Mastodon

<div style="-moz-column-width: 30em; -webkit-column-width: 30em; column-width: 30em;">
* Mastodon: https://mastodon.social/@vegard
* Blog: http://www.vegardno.net/
* GitHub: https://github.com/vegard/
* Shadertoy: https://www.shadertoy.com/user/vegardno
* Keybase: https://keybase.io/vegardno
* E-mail: <tt>vegard.nossum@gmail.com</tt>
* <del>Twitter: https://twitter.com/vegard_no</del>
</div>

SSE routines

2022-11-22T08:54:26Z

Vegard: add link from saidwho12

=== Boilerplate ===

<source lang="C">
#include <emmintrin.h>
</source>

=== Get length of string prefix consisting of letters and underscore ===

This can be useful for e.g. parsing identifiers.

The string does not need to be aligned, but beware that up to 15 bytes after the NUL terminator may be loaded from memory, so if these cross a page boundary you can get spurious page faults.

<source lang="C">
int nr_alpha(const char *s)
{
const char *start = s;

__m128i ch_A = _mm_set1_epi8('A' - 1);
__m128i ch_Z = _mm_set1_epi8('Z');
__m128i ch_underscore = _mm_set1_epi8('_');

while (1) {
__m128i ch = _mm_loadu_si128((__m128i *) s);
__m128i b = _mm_and_si128(ch, _mm_set1_epi8(~0x20));
b = _mm_or_si128(_mm_and_si128(_mm_cmpgt_epi8(b, ch_A),
_mm_cmplt_epi8(b, ch_Z)),
_mm_cmpeq_epi8(ch, ch_underscore));

unsigned int ffs = __builtin_ffs(~_mm_movemask_epi8(b)) - 1;
s += ffs;

if (ffs < 16)
return s - start;
}
}
</source>

=== Get length of string prefix consisting of whitespace ===

(See caveats above.)

<source lang="C">
int nr_whitespace(const char *s)
{
const char *start = s;

while (1) {
__m128i ch = _mm_loadu_si128((__m128i *) s);
__m128i b = _mm_or_si128(_mm_cmpeq_epi8(ch, _mm_set1_epi8(' ')),
_mm_cmpeq_epi8(ch, _mm_set1_epi8('\t')));
b = _mm_or_si128(b, _mm_cmpeq_epi8(ch, _mm_set1_epi8('\r')));
b = _mm_or_si128(b, _mm_cmpeq_epi8(ch, _mm_set1_epi8('\n')));

unsigned int ffs = __builtin_ffs(~_mm_movemask_epi8(b)) - 1;
s += ffs;

if (ffs < 16)
return s - start;
}
}
</source>

== See also ==

* https://software.intel.com/sites/landingpage/IntrinsicsGuide/
* https://woboq.com/blog/utf-8-processing-using-simd.html

[[Category:Programming]]
[[Category:C]]
[[Category:C++]]
[[Category:x86]]

MediaWiki:Copyright

2022-11-13T20:15:30Z

Vegard: add a link to my mastodon profile

GLSL snippets

2022-10-24T22:56:27Z

Vegard: /* Smooth variant */

__TOC__

== Signed distance functions ==

=== Antialiasing ===

<source lang="GLSL">
const float scale = 100.;

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
vec2 uv = scale * (fragCoord - .5 * iResolution.xy) / iResolution.y;
float d = sd...(uv);
vec3 col = vec3(1) * smoothstep(-0., 1.5 * scale / iResolution.y, d);
fragColor = vec4(col, 1.);
}
</source>

The point here is to convert the length returned by the distance function into a number of pixels, and then we can smooth the outline over the precise number of pixels that we want (here 1.5).

== Ray marching ==

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
vec3 rayDirection(float fieldOfView, vec2 size, vec2 fragCoord) {
vec2 xy = fragCoord - size / 2.;
float z = size.y / tan(radians(fieldOfView) / 2.) / 2.;
return normalize(vec3(xy, -z));
}
</source>

Note: The original <tt>rayDirection()</tt> is missing the divide by 2 when calculating z. This causes the field of view parameter to be incorrect.

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
float castRay(const int scene, vec3 eye, vec3 dir,
float start, float end, float epsilon, int max_marching_steps,
out int material)
{
float depth = start;
for (int i = 0; i < max_marching_steps; i++) {
float d = sceneSDF(scene, eye + depth * dir, material);
if (d < epsilon)
return depth;

depth += d;
if (depth >= end)
break;
}

return end;
}
</source>

<source lang="GLSL">
// http://iquilezles.org/www/articles/normalsSDF/normalsSDF.htm
vec3 estimateNormal( const int scene, const float epsilon, in vec3 p )
{
int m;

const vec2 k = vec2(1,-1);
return normalize( k.xyy*sceneSDF( scene, p + k.xyy*epsilon, m ) +
k.yyx*sceneSDF( scene, p + k.yyx*epsilon, m ) +
k.yxy*sceneSDF( scene, p + k.yxy*epsilon, m ) +
k.xxx*sceneSDF( scene, p + k.xxx*epsilon, m ) );
}
</source>

== Matrix transformations ==

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glRotate.xml
mat4 rotate(float a, vec3 v)
{
float c = cos(a);
vec3 ci = (1. - c) * v;
vec3 s = sin(a) * v;

return mat4(
ci.x * v.x + c, ci.x * v.y + s.z, ci.x * v.z - s.y, 0,
ci.y * v.x - s.z, ci.y * v.y + c, ci.y * v.z + s.x, 0,
ci.z * v.x + s.y, ci.z * v.y - s.x, ci.z * v.z + c, 0,
0, 0, 0, 1
);
}
</source>

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glTranslate.xml
mat4 translate(vec3 v)
{
return mat4(
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
v.x, v.y, v.z, 1
);
}
</source>

== Noise ==

<source lang="GLSL">
// https://stackoverflow.com/questions/12964279/whats-the-origin-of-this-glsl-rand-one-liner
float rand(vec2 co)
{
return fract(sin(dot(co.xy, vec2(12.9898, 78.233))) * 43758.5453);
}
</source>

== Colours ==

=== HSV ===

==== Plain HSV ====

[[File:hsv2rgb.png|420px|thumb|<tt>hsv2rgb()</tt>]]

<source lang="GLSL">
// https://github.com/hughsk/glsl-hsv2rgb/blob/master/index.glsl
vec3 hsv2rgb(vec3 c) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = abs(fract(c.xxx + K.xyz) * 6. - K.www);
return c.z * mix(K.xxx, clamp(p - K.xxx, 0.0, 1.0), c.y);
}
</source>

==== Smooth variant ====

[[File:hsv2rgb2.png|420px|thumb|<tt>hsv2rgb2()</tt>]]

<source lang="GLSL">
// https://www.shadertoy.com/view/wlsSRB
vec3 hsv2rgb2(vec3 c, float k) {
return smoothstep(0. + k, 1. - k,
.5 + .5 * cos((vec3(c.x) + vec3(3., 2., 1.) / 3.) * radians(360.)));
}
</source>

A good value for <code>k</code> is e.g. 0.07.

=== Gamma ===

{{Main|Gamma}}

<source lang="GLSL">
const float gamma = 2.2;

// convert from sRGB to RGB
vec3 col = pow(col, vec3(gamma));

// blending, etc.

// gamma correction (RGB to sRGB)
col = pow(col, vec3(1. / gamma));
</source>

== Dithering ==

<source lang="GLSL">
/* https://en.wikipedia.org/wiki/Ordered_dithering */
const float bayer_matrix[64] = float[64](
-0.500000, 0.250000, -0.312500, 0.437500, -0.453125, 0.296875, -0.265625, 0.484375,
0.000000, -0.250000, 0.187500, -0.062500, 0.046875, -0.203125, 0.234375, -0.015625,
-0.375000, 0.375000, -0.437500, 0.312500, -0.328125, 0.421875, -0.390625, 0.359375,
0.125000, -0.125000, 0.062500, -0.187500, 0.171875, -0.078125, 0.109375, -0.140625,
-0.468750, 0.281250, -0.281250, 0.468750, -0.484375, 0.265625, -0.296875, 0.453125,
0.031250, -0.218750, 0.218750, -0.031250, 0.015625, -0.234375, 0.203125, -0.046875,
-0.343750, 0.406250, -0.406250, 0.343750, -0.359375, 0.390625, -0.421875, 0.328125,
0.156250, -0.093750, 0.093750, -0.156250, 0.140625, -0.109375, 0.078125, -0.171875
);

float dither(vec2 uv, float levels, float sharpness, float intensity)
{
int x = int(floor(uv.x)) & 7;
int y = int(floor(uv.y)) & 7;
float threshold = bayer_matrix[8 * y + x];
#if 0 // full dither
return round(levels * intensity + threshold) / levels;
#else // respect sharpness
float major = floor(levels * intensity);
float minor = float(fract(levels * intensity) > .5 + sharpness * threshold);
return (major + minor) / levels;
#endif
}
</source>

== Post-processing effects ==

=== Volumetric light scattering (God rays) ===

[[File:godrays.png|420px|thumb|Example of volumetric light scattering post-processing effect (with dithering).]]

<source lang="GLSL">
// https://developer.nvidia.com/gpugems/gpugems3/part-ii-light-and-shadows/chapter-13-volumetric-light-scattering-post-process
vec3 godrays(in vec2 ScreenLightPos, in vec2 fragCoord, out vec4 fragColor)
{
const int NUM_SAMPLES = 16;
const float Density = .7;
const float Weight = .3;
const float Decay = .88;
const float Exposure = .4;

vec2 texCoord = fragCoord / iResolution.xy;
vec2 deltaTexCoord = (texCoord - ScreenLightPos.xy);
deltaTexCoord *= 1.0f / float(NUM_SAMPLES) * Density;

vec3 color = texture(iChannel0, texCoord).rgb;
float illuminationDecay = 1.0f;

for (int i = 0; i < NUM_SAMPLES; i++) {
texCoord -= deltaTexCoord;

float dither = rand(fragCoord + vec2(200. * float(i), 23. * float(i)));
vec3 sample_ = texture(iChannel0, texCoord + deltaTexCoord * dither).rgb;
sample_ *= illuminationDecay * Weight;
color += sample_;
illuminationDecay *= Decay;
}

return color * Exposure;
}
</source>

Dithering suggested by Jessica Mak.

[[Category:Graphics programming]]

ftrace

2022-10-07T14:37:04Z

Vegard: add category

== Trace a single system call ==

This generates a function graph trace of a specific function and its callees:

<source lang="Bash">
# function to trace
func=ksys_mount

cd /sys/kernel/debug/tracing/
echo 0 > tracing_on
echo function_graph > current_tracer
echo $func > set_graph_function
echo 1 > tracing_on
echo > trace

# do thing here

echo 0 > tracing_on
echo nop > current_tracer

# save trace
cp trace /tmp/trace.txt
</source>

[[Category:Linux kernel]]

mkinitrd

2022-10-07T14:36:55Z

Vegard: add ftrace link

A handy way to run a program as init without a filesystem:

<source lang="Bash">
#! /bin/bash

set -e
set -u
set -x

rm -rf initrd/
mkdir initrd/
g++ -static [...] -o initrd/init main.cc

(cd initrd/ && (find | cpio -o -H newc)) \
| gzip -c \
> initrd.gz
</source>

=== Mounting filesystems ===

Sometimes it can be useful to have <tt>/proc</tt>, <tt>/sys</tt>, <tt>/dev</tt>, etc. around:

<source lang="C">
#include <sys/mount.h>
#include <sys/stat.h>
#include <sys/types.h>

#include <errno.h>
#include <error.h>
#include <unistd.h>

static void mkdirp(const char *name)
{
if (mkdir(name, 0777) == -1 && errno != EEXIST)
error(EXIT_FAILURE, errno, "mkdir()");
}

int main(int argc, char *argv[])
{
pid_t self = getpid();
if (getpid() == -1)
error(EXIT_FAILURE, errno, "getpid()");

if (self == 1) {
// We're init! Do some basic setup.

mkdirp("/proc");
if (mount("nodev", "/proc", "proc", 0, "") == -1)
error(EXIT_FAILURE, errno, "mount(/proc)");

mkdirp("/sys");
if (mount("nodev", "/sys", "sysfs", 0, "") == -1)
error(EXIT_FAILURE, errno, "mount(/sys)");

mkdirp("/dev");
if (mount("nodev", "/dev", "devtmpfs", 0, "") == -1)
error(EXIT_FAILURE, errno, "mount(/dev)");

if (mount("nodev", "/sys/kernel/tracing", "tracefs", 0, "") == -1)
error(EXIT_FAILURE, errno, "mount(/sys/kernel/tracing)");
}

...
}
</source>

=== ftrace ===

To trace something with ftrace (and dump the trace), use something like:

<source lang="C">
#define tracing_set(name, value) \
{ \
FILE *fp = fopen("/sys/kernel/tracing/" #name, "w"); \
if (!fp) \
error(EXIT_FAILURE, errno, "fopen(" #name ")"); \
fprintf(fp, "%s\n", #value); \
fclose(fp); \
}

int main(int argc, char *argv[])
{
// ...

tracing_set(current_tracer, function_graph);
tracing_set(tracing_on, 1);

// insert traced code here

tracing_set(tracing_on, 0);

// dump trace
{
FILE *fp = fopen("/sys/kernel/tracing/trace", "r");
while (fp && !feof(fp)) {
char buf[1024];
size_t len = fread(buf, 1, sizeof buf, fp);
fwrite(buf, 1, len, stdout);
}
fclose(fp);
}
}
</source>

See also: [[ftrace]].

[[Category:Linux kernel]]

ftrace

2022-10-07T14:14:15Z

Vegard: fixes

ftrace

2022-10-07T14:09:46Z

Vegard: fix

== Trace a single system call ==

This generates a function graph trace of a specific function and its callees:

<source lang="Bash">
# function to trace
func=ksys_mount

cd /sys/kernel/debug/tracing/
echo 0 > tracing_on
echo function_graph > current_tracer
echo $func > set_graph_function
echo 1 > tracing_on

# do thing here

echo 0 > tracing_on

# save trace
cp trace /tmp/trace.txt
</source>

ftrace

2022-10-07T14:08:34Z

Vegard: new page

== Trace a single system call ==

This generates a function graph trace of a specific function and its callees:

<source lang="Bash">
# function to trace
func=ksys_mount

cd /sys/kernel/debug/tracing/
echo 0 > tracing_on
echo function_graph > current_tracer
echo set_graph_function > set_graph_function
echo $func > set_graph_function
echo 1 > tracing_on

# do thing here

echo 0 > tracing_on

# save trace
cp trace /tmp/trace.txt
</source>

Frame analysis

2022-01-20T06:53:53Z

Vegard: add God of War

This is a list of "frame analysis" blog posts, i.e. posts which dissect how a game does its rendering.

== Engines ==

=== AnKi 3D ===

* http://anki3d.org/anatomy-of-a-frame-in-anki/

== Games ==

=== A Plague Tale: Innocence ===

* https://gamingbolt.com/a-plague-tale-innocence-graphics-analysis-one-of-the-best-looking-games-of-this-gen

=== Batman: Arkham Knight ===

* http://morad.in/2020/04/03/unmasking-arkham-knight/

=== Battlefield 3 ===

* https://www.slideshare.net/DICEStudio/directx-11-rendering-in-battlefield-3

=== Battlefield 4 ===

* https://www.slideshare.net/DevCentralAMD/rendering-battlefield-4-with-mantle-yuriy-o-donnell

=== BioShock Infinite ===

* https://solid-angle.blogspot.com/2014/03/bioshock-infinite-lighting.html

=== Castlevania: Lords of Shadow 2 ===

* https://www.elopezr.com/castlevania-lords-of-shadow-2-graphics-study/

=== Deus Ex: Human Revolution ===

* http://www.adriancourreges.com/blog/2015/03/10/deus-ex-human-revolution-graphics-study/

=== Doom 2016 ===

* http://www.adriancourreges.com/blog/2016/09/09/doom-2016-graphics-study/

=== Doom Eternal ===
* https://simoncoenen.com/blog/programming/graphics/DoomEternalStudy.html

=== Far Cry 5 ===

* https://www.gdcvault.com/play/1025480/Terrain-Rendering-in-Far-Cry

=== Gears of War 5 ===

* https://www.eurogamer.net/articles/digitalfoundry-2019-gears-5-tech-interview

=== Ghost of Tsushima ===

* https://blog.selfshadow.com/publications/s2020-shading-course/patry/slides/

=== God of War ===

* http://www.mamoniem.com/behind-the-pretty-frames-god-of-war/

=== GTA V ===

* http://www.adriancourreges.com/blog/2015/11/02/gta-v-graphics-study/

=== Killzone 2 ===

* https://www.guerrilla-games.com/read/deferred-rendering-in-killzone-2

=== League of Legends ===

* https://technology.riotgames.com/news/trip-down-lol-graphics-pipeline

=== Metal Gear Solid V ===

* http://www.adriancourreges.com/blog/2017/12/15/mgs-v-graphics-study/

=== Metro Exodus ===

* https://aschrein.github.io/2019/08/11/metro_breakdown.html

=== Middle Earth: Shadow of Mordor ===

* http://www.elopezr.com/the-rendering-of-middle-earth-shadow-of-mordor/

=== Ni No Kuni 2 ===

* https://blog.thomaspoulet.fr/ninokuni2-frame/

=== Red Dead Redemption 2 ===

* https://imgeself.github.io/posts/2020-06-19-graphics-study-rdr2/

=== Resident Evil 2 ===

* https://aschrein.github.io/2019/08/01/re2_breakdown.html

=== Rise of the Tomb Raider ===

* http://www.elopezr.com/the-rendering-of-rise-of-the-tomb-raider/

=== Supreme Commander ===

* http://www.adriancourreges.com/blog/2015/06/23/supreme-commander-graphics-study/

=== The Witcher 3 ===

* https://astralcode.blogspot.com/2018/11/reverse-engineering-rendering-of.html

=== The Witness ===

* https://blog.thomaspoulet.fr/the-witness-frame-part-1/
* https://blog.thomaspoulet.fr/the-witness-frame-part-2/

=== Total War ===

* https://gpuopen.com/anatomy-total-war-engine-part/
* https://gpuopen.com/anatomy-total-war-engine-part-2/
* https://gpuopen.com/anatomy-total-war-engine-part-3/
* https://gpuopen.com/anatomy-total-war-engine-part-4/
* https://gpuopen.com/anatomy-total-war-engine-part-5/

=== Wind Waker ===

* https://polycount.com/discussion/104415/zelda-wind-waker-tech-and-texture-analysis-picture-heavy

[[Category:Graphics programming]]

GLSL snippets

2021-12-30T11:02:01Z

Vegard: /* Ray marching */ fix rayDirection()

__TOC__

== Signed distance functions ==

=== Antialiasing ===

<source lang="GLSL">
const float scale = 100.;

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
vec2 uv = scale * (fragCoord - .5 * iResolution.xy) / iResolution.y;
float d = sd...(uv);
vec3 col = vec3(1) * smoothstep(-0., 1.5 * scale / iResolution.y, d);
fragColor = vec4(col, 1.);
}
</source>

The point here is to convert the length returned by the distance function into a number of pixels, and then we can smooth the outline over the precise number of pixels that we want (here 1.5).

== Ray marching ==

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
vec3 rayDirection(float fieldOfView, vec2 size, vec2 fragCoord) {
vec2 xy = fragCoord - size / 2.;
float z = size.y / tan(radians(fieldOfView) / 2.) / 2.;
return normalize(vec3(xy, -z));
}
</source>

Note: The original <tt>rayDirection()</tt> is missing the divide by 2 when calculating z. This causes the field of view parameter to be incorrect.

<source lang="GLSL">
// http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/
float castRay(const int scene, vec3 eye, vec3 dir,
float start, float end, float epsilon, int max_marching_steps,
out int material)
{
float depth = start;
for (int i = 0; i < max_marching_steps; i++) {
float d = sceneSDF(scene, eye + depth * dir, material);
if (d < epsilon)
return depth;

depth += d;
if (depth >= end)
break;
}

return end;
}
</source>

<source lang="GLSL">
// http://iquilezles.org/www/articles/normalsSDF/normalsSDF.htm
vec3 estimateNormal( const int scene, const float epsilon, in vec3 p )
{
int m;

const vec2 k = vec2(1,-1);
return normalize( k.xyy*sceneSDF( scene, p + k.xyy*epsilon, m ) +
k.yyx*sceneSDF( scene, p + k.yyx*epsilon, m ) +
k.yxy*sceneSDF( scene, p + k.yxy*epsilon, m ) +
k.xxx*sceneSDF( scene, p + k.xxx*epsilon, m ) );
}
</source>

== Matrix transformations ==

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glRotate.xml
mat4 rotate(float a, vec3 v)
{
float c = cos(a);
vec3 ci = (1. - c) * v;
vec3 s = sin(a) * v;

return mat4(
ci.x * v.x + c, ci.x * v.y + s.z, ci.x * v.z - s.y, 0,
ci.y * v.x - s.z, ci.y * v.y + c, ci.y * v.z + s.x, 0,
ci.z * v.x + s.y, ci.z * v.y - s.x, ci.z * v.z + c, 0,
0, 0, 0, 1
);
}
</source>

<source lang="GLSL">
// https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glTranslate.xml
mat4 translate(vec3 v)
{
return mat4(
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
v.x, v.y, v.z, 1
);
}
</source>

== Noise ==

<source lang="GLSL">
// https://stackoverflow.com/questions/12964279/whats-the-origin-of-this-glsl-rand-one-liner
float rand(vec2 co)
{
return fract(sin(dot(co.xy, vec2(12.9898, 78.233))) * 43758.5453);
}
</source>

== Colours ==

=== HSV ===

==== Plain HSV ====

[[File:hsv2rgb.png|420px|thumb|<tt>hsv2rgb()</tt>]]

<source lang="GLSL">
// https://github.com/hughsk/glsl-hsv2rgb/blob/master/index.glsl
vec3 hsv2rgb(vec3 c) {
vec4 K = vec4(3. / 3., 2. / 3., 1. / 3., 3.);
vec3 p = abs(fract(c.xxx + K.xyz) * 6. - K.www);
return c.z * mix(K.xxx, clamp(p - K.xxx, 0.0, 1.0), c.y);
}
</source>

==== Smooth variant ====

[[File:hsv2rgb2.png|420px|thumb|<tt>hsv2rgb2()</tt>]]

<source lang="GLSL">
// https://www.shadertoy.com/view/wlsSRB
vec3 hsv2rgb2(vec3 c, float k) {
return smoothstep(0. + k, 1. - k,
.5 + .5 * cos((vec3(c.x) + vec3(3., 2., 1.) / 3.) * radians(360.)));
}
</source>

=== Gamma ===

{{Main|Gamma}}

<source lang="GLSL">
const float gamma = 2.2;

// convert from sRGB to RGB
vec3 col = pow(col, vec3(gamma));

// blending, etc.

// gamma correction (RGB to sRGB)
col = pow(col, vec3(1. / gamma));
</source>

== Dithering ==

<source lang="GLSL">
/* https://en.wikipedia.org/wiki/Ordered_dithering */
const float bayer_matrix[64] = float[64](
-0.500000, 0.250000, -0.312500, 0.437500, -0.453125, 0.296875, -0.265625, 0.484375,
0.000000, -0.250000, 0.187500, -0.062500, 0.046875, -0.203125, 0.234375, -0.015625,
-0.375000, 0.375000, -0.437500, 0.312500, -0.328125, 0.421875, -0.390625, 0.359375,
0.125000, -0.125000, 0.062500, -0.187500, 0.171875, -0.078125, 0.109375, -0.140625,
-0.468750, 0.281250, -0.281250, 0.468750, -0.484375, 0.265625, -0.296875, 0.453125,
0.031250, -0.218750, 0.218750, -0.031250, 0.015625, -0.234375, 0.203125, -0.046875,
-0.343750, 0.406250, -0.406250, 0.343750, -0.359375, 0.390625, -0.421875, 0.328125,
0.156250, -0.093750, 0.093750, -0.156250, 0.140625, -0.109375, 0.078125, -0.171875
);

float dither(vec2 uv, float levels, float sharpness, float intensity)
{
int x = int(floor(uv.x)) & 7;
int y = int(floor(uv.y)) & 7;
float threshold = bayer_matrix[8 * y + x];
#if 0 // full dither
return round(levels * intensity + threshold) / levels;
#else // respect sharpness
float major = floor(levels * intensity);
float minor = float(fract(levels * intensity) > .5 + sharpness * threshold);
return (major + minor) / levels;
#endif
}
</source>

== Post-processing effects ==

=== Volumetric light scattering (God rays) ===

[[File:godrays.png|420px|thumb|Example of volumetric light scattering post-processing effect (with dithering).]]

<source lang="GLSL">
// https://developer.nvidia.com/gpugems/gpugems3/part-ii-light-and-shadows/chapter-13-volumetric-light-scattering-post-process
vec3 godrays(in vec2 ScreenLightPos, in vec2 fragCoord, out vec4 fragColor)
{
const int NUM_SAMPLES = 16;
const float Density = .7;
const float Weight = .3;
const float Decay = .88;
const float Exposure = .4;

vec2 texCoord = fragCoord / iResolution.xy;
vec2 deltaTexCoord = (texCoord - ScreenLightPos.xy);
deltaTexCoord *= 1.0f / float(NUM_SAMPLES) * Density;

vec3 color = texture(iChannel0, texCoord).rgb;
float illuminationDecay = 1.0f;

for (int i = 0; i < NUM_SAMPLES; i++) {
texCoord -= deltaTexCoord;

float dither = rand(fragCoord + vec2(200. * float(i), 23. * float(i)));
vec3 sample_ = texture(iChannel0, texCoord + deltaTexCoord * dither).rgb;
sample_ *= illuminationDecay * Weight;
color += sample_;
illuminationDecay *= Decay;
}

return color * Exposure;
}
</source>

Dithering suggested by Jessica Mak.

[[Category:Graphics programming]]

Blur filter

2021-12-28T12:42:31Z

Vegard: new page

Best practices:

* Scale down before applying filter to increase blur radius
* Separate into horizontal + vertical passes to reduce number of texture lookups
* Use hardware filtering to reduce number of texture lookups
* Make sure blending happens in [[Gamma|linear RGB]] to avoid darkening

== See also ==

* https://www.codeproject.com/Articles/839187/An-investigation-of-fast-real-time-GPU-based-image
* https://iquilezles.org/www/articles/gamma/gamma.htm

Gamma

2021-12-28T10:21:17Z

Vegard: add link

Quick rules of thumb, since I can never remember which is which:
* RGB = linear space
* sRGB = gamma space
* most image files store sRGB
* sRGB is unfit for blending, blurring, etc.

The corollary is:
* Image files loaded as textures should be converted from sRGB to RGB (but some decoders do this for you!)
* Since alpha is linear, [[Premultiplied alpha|alpha premultiplication]] should happen in linear space, i.e. after converting to RGB [http://ssp.impulsetrain.com/gamma-premult.html]
* The shader responsible for putting the final pixels on the screen should have a gamma correction step doing:
:<source lang="GLSL">
const float gamma = 2.2;

out vec4 color;

void main()
{
// ...

color = pow(color, 1. / gamma);
}
</source>

Note, however, that OpenGL may also perform this step for you on any on-screen framebuffers (i.e. the default framebuffer) if you do <code>glEnable(GL_FRAMEBUFFER_SRGB)</code>.

== See also ==
* https://blog.johnnovak.net/2016/09/21/what-every-coder-should-know-about-gamma/
* https://stackoverflow.com/questions/23026151/do-i-need-to-gamma-correct-the-final-color-output-on-a-modern-computer-monitor
* https://www.khronos.org/opengl/wiki/Framebuffer#Colorspace
* https://en.wikipedia.org/wiki/Gamma_correction
* https://www.cambridgeincolour.com/tutorials/gamma-correction.htm
* http://chilliant.blogspot.com/2012/08/srgb-approximations-for-hlsl.html
* https://unlimited3d.wordpress.com/2020/01/08/srgb-color-space-in-opengl/
* https://mynameismjp.wordpress.com/2012/10/24/msaa-overview/ ("Working with HDR and Tone Mapping")
* https://iquilezles.org/www/articles/gamma/gamma.htm

[[Category:Graphics programming]]

Tone mapping

2021-12-26T14:27:18Z

Vegard: new page

{{Stub}}

== See also ==
* https://learnopengl.com/Advanced-Lighting/HDR
* http://filmicworlds.com/blog/filmic-tonemapping-operators/

[[Category:Graphics programming]]

Point-triangle intersection

2021-12-09T13:01:28Z

Vegard: new page

{{Stub}}

=== See also ===

* https://twitter.com/SebAaltonen/status/1468674844510330882
* [[Barycentric coordinates]]
* [[Ray-triangle intersection]]

Ray-triangle intersection

2021-12-08T08:13:59Z

Vegard: add link

<source lang="C++">
// https://twitter.com/brunolevy01/status/1229664999179726848
// "(Moller-Tumblore). A, B, C is the triangle, O, D is the ray."
// gives barycentric coordinates and normal for free.
bool ray_triangle_intersection(vec3 A, vec3 B, vec3 C, vec3 O, vec3 D)
{
vec3 E1 = B - A;
vec3 E2 = C - A;
vec3 N = cross(E1, E2);
float det = -dot(D, N);
vec3 AO = O - A;
vec3 DAO = cross(AO, D);
float u = dot(E2, DAO) / det;
float v = -dot(E1, DAO) / det;
float t = dot(AO, N) / det;
return (t > 0. && u > 0. && v > 0. && (u + v) < 1.);
}
</source>

=== See also ===

* [[Barycentric coordinates]]
* https://twitter.com/BrunoLevy01/status/1229665598273150979
* https://stackoverflow.com/questions/42740765/intersection-between-line-and-triangle-in-3d/42752998#42752998

[[Category:Graphics programming]]
[[Category:Geometry]]

Ray-triangle intersection

2021-12-08T08:13:36Z

Vegard: new page

<source lang="C++">
// https://twitter.com/brunolevy01/status/1229664999179726848
// "(Moller-Tumblore). A, B, C is the triangle, O, D is the ray."
// gives barycentric coordinates and normal for free.
bool ray_triangle_intersection(vec3 A, vec3 B, vec3 C, vec3 O, vec3 D)
{
vec3 E1 = B - A;
vec3 E2 = C - A;
vec3 N = cross(E1, E2);
float det = -dot(D, N);
vec3 AO = O - A;
vec3 DAO = cross(AO, D);
float u = dot(E2, DAO) / det;
float v = -dot(E1, DAO) / det;
float t = dot(AO, N) / det;
return (t > 0. && u > 0. && v > 0. && (u + v) < 1.);
}
</source>

=== See also ===

* [[Barycentric coordinates]]
* https://stackoverflow.com/questions/42740765/intersection-between-line-and-triangle-in-3d/42752998#42752998

[[Category:Graphics programming]]
[[Category:Geometry]]

Nanite

2021-06-15T06:55:27Z

Vegard: add link

* [https://www.unrealengine.com/en-US/blog/understanding-nanite---unreal-engine-5-s-new-virtualized-geometry-system "Understanding Nanite - Unreal Engine 5's new virtualized geometry system"]
* [https://docs.unrealengine.com/5.0/en-US/RenderingFeatures/Nanite/ "Nanite Virtualized Geometry"]
* [http://www.elopezr.com/a-macro-view-of-nanite/ "A macro view of Nanite"]
* [https://www.ezdlc.com/128181/nanite-presentation-how-it-works/ "Nanite presentation: How it works"]
* [https://www.notion.so/Brief-Analysis-of-Nanite-94be60f292434ba3ae62fa4bcf7d9379 "Brief Analysis of Nanite"]
* [https://www.notion.so/Brief-Analysis-of-Nanite-GPU-Culling-6ea4a7b8a3574f31bb4095901fc8e309 "Brief Analysis of Nanite GPU Culling"]
* https://zhuanlan.zhihu.com/p/376786001

[[Category:Graphics programming]]

Nanite

2021-06-08T13:36:35Z

Vegard: new article

* [https://www.unrealengine.com/en-US/blog/understanding-nanite---unreal-engine-5-s-new-virtualized-geometry-system "Understanding Nanite - Unreal Engine 5's new virtualized geometry system"]
* [https://docs.unrealengine.com/5.0/en-US/RenderingFeatures/Nanite/ "Nanite Virtualized Geometry"]
* [http://www.elopezr.com/a-macro-view-of-nanite/ "A macro view of Nanite"]
* [https://www.ezdlc.com/128181/nanite-presentation-how-it-works/ "Nanite presentation: How it works"]
* [https://www.notion.so/Brief-Analysis-of-Nanite-94be60f292434ba3ae62fa4bcf7d9379 "Brief Analysis of Nanite"]
* https://zhuanlan.zhihu.com/p/376786001

[[Category:Graphics programming]]

Category:Floating-point

2021-06-08T05:57:24Z

Vegard: new category

Herbie

2021-06-08T05:57:12Z

Vegard: new page

"Herbie rewrites floating point expressions to make them more accurate. Floating point arithmetic is inaccurate; even 0.1 + 0.2 ≠ 0.3 for a computer. Herbie helps find and fix these mysterious inaccuracies."

http://herbie.uwplse.org/

[[Category:Floating-point]]
[[Category:Programming]]

Float to byte quantisation

2021-06-08T05:52:56Z

Vegard: add category

{{Stub}}

[[File:quantization.png]]

== See also ==

* https://stackoverflow.com/questions/1914115/converting-color-value-from-float-0-1-to-byte-0-255
* https://twitter.com/rygorous/status/1249876256599846912

[[Category:Graphics programming]]
[[Category:Floating-point]]
[[Category:Programming]]

Bit-twiddling hacks

2021-04-19T11:01:24Z

Vegard: new page

== See also ==

* https://graphics.stanford.edu/~seander/bithacks.html
* http://www.csl.sri.com/users/tiwari/papers/pldi2011-bitvector.pdf

[[Category:C]] [[Category:Assembly]] [[Category:Programming]]

Buffer iteration

2021-02-26T09:06:48Z

Vegard: new page

{{Stub}}

In order:
* https://fgiesen.wordpress.com/2011/11/21/buffer-centric-io/
* https://twitter.com/pervognsen/status/1260381122887737344
* https://gist.github.com/pervognsen/744066869da509a15c4e08fc9408207e
* https://gist.github.com/vurtun/192cac1f1818417d7b4067d60e4fe921
* https://gist.github.com/pervognsen/d57cdc165e79a21637fe5a721375afba

[[Category:C]] [[Category:Programming]]

Random number generators

2021-02-20T15:36:33Z

Vegard: categorise

== pcg32() ==

<source lang="C">
// https://twitter.com/zeuxcg/status/1363143368033755136
uint32_t pcg32(uint64_t* s) {
uint32_t x = ((*s >> 18u) ^ *s) >> 27u;
uint32_t r = *s >> 59u;
*s = *s * 6364136223846793005ULL + 1;
return (x >> r) | (x << ((-r) & 31));
}
</source>

== See also ==

* PCG paper: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

[[Category:C]] [[Category:Programming]]

Random number generators

2021-02-20T15:35:35Z

Vegard: new page

Gamma

2020-11-28T08:58:47Z

Vegard: add link

Quick rules of thumb, since I can never remember which is which:
* RGB = linear space
* sRGB = gamma space
* most image files store sRGB
* sRGB is unfit for blending

The corollary is:
* Image files loaded as textures should be converted from sRGB to RGB (but some decoders do this for you!)
* Since alpha is linear, [[Premultiplied alpha|alpha premultiplication]] should happen in linear space, i.e. after converting to RGB [http://ssp.impulsetrain.com/gamma-premult.html]
* The shader responsible for putting the final pixels on the screen should have a gamma correction step doing:
:<source lang="GLSL">
const float gamma = 2.2;

out vec4 color;

void main()
{
// ...

color = pow(color, 1. / gamma);
}
</source>

Note, however, that OpenGL may also perform this step for you on any on-screen framebuffers (i.e. the default framebuffer) if you do <code>glEnable(GL_FRAMEBUFFER_SRGB)</code>.

== See also ==
* https://blog.johnnovak.net/2016/09/21/what-every-coder-should-know-about-gamma/
* https://stackoverflow.com/questions/23026151/do-i-need-to-gamma-correct-the-final-color-output-on-a-modern-computer-monitor
* https://www.khronos.org/opengl/wiki/Framebuffer#Colorspace
* https://en.wikipedia.org/wiki/Gamma_correction
* https://www.cambridgeincolour.com/tutorials/gamma-correction.htm
* http://chilliant.blogspot.com/2012/08/srgb-approximations-for-hlsl.html
* https://unlimited3d.wordpress.com/2020/01/08/srgb-color-space-in-opengl/
* https://mynameismjp.wordpress.com/2012/10/24/msaa-overview/ ("Working with HDR and Tone Mapping")

[[Category:Graphics programming]]

sRGB

2020-11-28T07:58:13Z

Vegard: create redirect

#REDIRECT [[Gamma]]

Gamma

2020-11-28T07:57:52Z

Vegard: add link

B-tree

2020-10-29T17:17:20Z

Vegard: make it extra clear that I'm not the author

By [https://twitter.com/pervognsen/ Per Vognsen]:

<source lang="C++">
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INLINE inline
#define CopyMemory memcpy
#define Allocate malloc
#define Free free
#define Assert assert

typedef unsigned int Key;
typedef unsigned long Value;

// find where to insert the given key to maintain the sorted array
uint32_t SearchKeys(Key *keys, uint32_t length, Key key)
{
for (uint32_t i = 0; i < length; ++i) {
if (key <= keys[i])
return i;
}

return length;
}

template<typename T>
void Array_Insert(T *array, uint32_t length, uint32_t index, T value)
{
// shift everything up
for (uint32_t i = length ; i-- > index; )
array[i + 1] = array[i];

array[index] = value;
}

template<typename T>
void Array_Delete(T *array, uint32_t length, uint32_t index)
{
// shift everything down
for (uint32_t i = index + 1; i < length; ++i)
array[i - 1] = array[i];
}

// --- https://gist.github.com/pervognsen/2d48ef9757ee3fd579179239febc817e
// Per Vognsen, public domain

enum { BMAX = 32, BMIN = BMAX / 2, BHEIGHT = 6 };

struct BNode {
uint32_t length;
Key keys[BMAX];
union {
BNode *children[BMAX];
Value values[BMAX];
};
};

static void BNode_Initialize(BNode *node, uint32_t length, Key *keys, void *children) {
node->length = length;
CopyMemory(node->keys, keys, length * sizeof(Key));
CopyMemory(node->children, children, length * sizeof(BNode *));
}

static BNode *BNode_Create(uint32_t length, Key *keys, void *children) {
BNode *node = (BNode *)Allocate(sizeof(BNode));
BNode_Initialize(node, length, keys, children);
return node;
}

static void BNode_Destroy(BNode *node, uint32_t height) {
for (uint32_t index = 0; index < node->length; index++) {
if (height > 1) {
BNode_Destroy(node->children[index], height - 1);
}
Free(node->children[index]);
}
}

static INLINE Key BNode_GetMaxKey(BNode *node) {
Assert(node->length > 0);
return node->keys[node->length - 1];
}

static BNode *BNodeLeaf_Insert(BNode *leaf, Key key, Value value) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
leaf->values[index] = value;
return 0;
}
BNode *new_sibling = 0;
if (leaf->length == BMAX) {
new_sibling = BNode_Create(BMIN, leaf->keys + BMIN, leaf->values + BMIN);
leaf->length = BMIN;
if (index >= BMIN) {
leaf = new_sibling;
index -= BMIN;
}
}
Array_Insert(leaf->keys, leaf->length, index, key);
Array_Insert(leaf->values, leaf->length, index, value);
leaf->length++;
return new_sibling;
}

static BNode *BNode_Insert(BNode *node, Key key, Value value, uint32_t height) {
Assert(height > 0);
Assert(node->length > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
index--;
node->keys[index] = key;
}
BNode *new_child;
if (height == 1) {
new_child = BNodeLeaf_Insert(node->children[index], key, value);
} else {
new_child = BNode_Insert(node->children[index], key, value, height - 1);
}
BNode *new_sibling = 0;
if (new_child) {
if (node->length == BMAX) {
new_sibling = BNode_Create(BMIN, node->keys + BMIN, node->children + BMIN);
node->length = BMIN;
if (index >= BMIN) {
node = new_sibling;
index -= BMIN;
}
}
node->keys[index] = BNode_GetMaxKey(node->children[index]);
Array_Insert(node->keys, node->length, index + 1, BNode_GetMaxKey(new_child));
Array_Insert(node->children, node->length, index + 1, new_child);
node->length++;
}
return new_sibling;
}

static bool BNodeLeaf_Delete(BNode *leaf, Key key) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
Array_Delete(leaf->keys, leaf->length, index);
Array_Delete(leaf->values, leaf->length, index);
leaf->length--;
return leaf->length == 0;
}
return false;
}

static void BNode_Delete(BNode *node, Key key, uint32_t height) {
Assert(height > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index < node->length) {
if (height == 1) {
if (BNodeLeaf_Delete(node->children[index], key) && node->length > 1) {
Free(node->children[index]);
Array_Delete(node->keys, node->length, index);
Array_Delete(node->children, node->length, index);
node->length--;
}
} else {
BNode_Delete(node->children[index], key, height - 1);
}
}
}

struct BTree {
uint32_t height;
BNode root;
};

void BTree_Initialize(BTree *tree) {
Assert(BMAX == 2 * BMIN);
Assert(sizeof(BNode *) == sizeof(Value));
tree->height = 0;
tree->root.length = 0;
}

void BTree_Destroy(BTree *tree) {
if (tree->height > 0) {
BNode_Destroy(&tree->root, tree->height);
}
}

Value *BTree_Find(BTree *tree, Key key) {
uint32_t height = tree->height;
BNode *node = &tree->root;
for (;;) {
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
return 0;
}
if (height == 0) {
return (node->keys[index] == key) ? (node->values + index) : 0;
}
height--;
node = node->children[index];
}
}

void BTree_Insert(BTree *tree, Key key, Value value) {
BNode *root = &tree->root;
BNode *new_root_sibling;
if (tree->height == 0) {
new_root_sibling = BNodeLeaf_Insert(root, key, value);
} else {
new_root_sibling = BNode_Insert(root, key, value, tree->height);
}
if (new_root_sibling) {
BNode *old_root = BNode_Create(root->length, root->keys, root->children);
Key keys[2] = {BNode_GetMaxKey(old_root), BNode_GetMaxKey(new_root_sibling)};
BNode *children[2] = {old_root, new_root_sibling};
BNode_Initialize(root, 2, keys, children);
tree->height++;
}
}

void BTree_Delete(BTree *tree, Key key) {
if (tree->height == 0) {
BNodeLeaf_Delete(&tree->root, key);
} else {
BNode_Delete(&tree->root, key, tree->height);
}
}
</source>

=== See also ===
* https://gist.github.com/pervognsen/2d48ef9757ee3fd579179239febc817e

[[Category:Programming]]
[[Category:C++]]
[[Category:Data structures]]

B-tree

2020-10-29T17:15:12Z

Vegard: make source clearer

<source lang="C++">
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INLINE inline
#define CopyMemory memcpy
#define Allocate malloc
#define Free free
#define Assert assert

typedef unsigned int Key;
typedef unsigned long Value;

// find where to insert the given key to maintain the sorted array
uint32_t SearchKeys(Key *keys, uint32_t length, Key key)
{
for (uint32_t i = 0; i < length; ++i) {
if (key <= keys[i])
return i;
}

return length;
}

template<typename T>
void Array_Insert(T *array, uint32_t length, uint32_t index, T value)
{
// shift everything up
for (uint32_t i = length ; i-- > index; )
array[i + 1] = array[i];

array[index] = value;
}

template<typename T>
void Array_Delete(T *array, uint32_t length, uint32_t index)
{
// shift everything down
for (uint32_t i = index + 1; i < length; ++i)
array[i - 1] = array[i];
}

// --- https://gist.github.com/pervognsen/2d48ef9757ee3fd579179239febc817e
// Per Vognsen, public domain

enum { BMAX = 32, BMIN = BMAX / 2, BHEIGHT = 6 };

struct BNode {
uint32_t length;
Key keys[BMAX];
union {
BNode *children[BMAX];
Value values[BMAX];
};
};

static void BNode_Initialize(BNode *node, uint32_t length, Key *keys, void *children) {
node->length = length;
CopyMemory(node->keys, keys, length * sizeof(Key));
CopyMemory(node->children, children, length * sizeof(BNode *));
}

static BNode *BNode_Create(uint32_t length, Key *keys, void *children) {
BNode *node = (BNode *)Allocate(sizeof(BNode));
BNode_Initialize(node, length, keys, children);
return node;
}

static void BNode_Destroy(BNode *node, uint32_t height) {
for (uint32_t index = 0; index < node->length; index++) {
if (height > 1) {
BNode_Destroy(node->children[index], height - 1);
}
Free(node->children[index]);
}
}

static INLINE Key BNode_GetMaxKey(BNode *node) {
Assert(node->length > 0);
return node->keys[node->length - 1];
}

static BNode *BNodeLeaf_Insert(BNode *leaf, Key key, Value value) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
leaf->values[index] = value;
return 0;
}
BNode *new_sibling = 0;
if (leaf->length == BMAX) {
new_sibling = BNode_Create(BMIN, leaf->keys + BMIN, leaf->values + BMIN);
leaf->length = BMIN;
if (index >= BMIN) {
leaf = new_sibling;
index -= BMIN;
}
}
Array_Insert(leaf->keys, leaf->length, index, key);
Array_Insert(leaf->values, leaf->length, index, value);
leaf->length++;
return new_sibling;
}

static BNode *BNode_Insert(BNode *node, Key key, Value value, uint32_t height) {
Assert(height > 0);
Assert(node->length > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
index--;
node->keys[index] = key;
}
BNode *new_child;
if (height == 1) {
new_child = BNodeLeaf_Insert(node->children[index], key, value);
} else {
new_child = BNode_Insert(node->children[index], key, value, height - 1);
}
BNode *new_sibling = 0;
if (new_child) {
if (node->length == BMAX) {
new_sibling = BNode_Create(BMIN, node->keys + BMIN, node->children + BMIN);
node->length = BMIN;
if (index >= BMIN) {
node = new_sibling;
index -= BMIN;
}
}
node->keys[index] = BNode_GetMaxKey(node->children[index]);
Array_Insert(node->keys, node->length, index + 1, BNode_GetMaxKey(new_child));
Array_Insert(node->children, node->length, index + 1, new_child);
node->length++;
}
return new_sibling;
}

static bool BNodeLeaf_Delete(BNode *leaf, Key key) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
Array_Delete(leaf->keys, leaf->length, index);
Array_Delete(leaf->values, leaf->length, index);
leaf->length--;
return leaf->length == 0;
}
return false;
}

static void BNode_Delete(BNode *node, Key key, uint32_t height) {
Assert(height > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index < node->length) {
if (height == 1) {
if (BNodeLeaf_Delete(node->children[index], key) && node->length > 1) {
Free(node->children[index]);
Array_Delete(node->keys, node->length, index);
Array_Delete(node->children, node->length, index);
node->length--;
}
} else {
BNode_Delete(node->children[index], key, height - 1);
}
}
}

struct BTree {
uint32_t height;
BNode root;
};

void BTree_Initialize(BTree *tree) {
Assert(BMAX == 2 * BMIN);
Assert(sizeof(BNode *) == sizeof(Value));
tree->height = 0;
tree->root.length = 0;
}

void BTree_Destroy(BTree *tree) {
if (tree->height > 0) {
BNode_Destroy(&tree->root, tree->height);
}
}

Value *BTree_Find(BTree *tree, Key key) {
uint32_t height = tree->height;
BNode *node = &tree->root;
for (;;) {
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
return 0;
}
if (height == 0) {
return (node->keys[index] == key) ? (node->values + index) : 0;
}
height--;
node = node->children[index];
}
}

void BTree_Insert(BTree *tree, Key key, Value value) {
BNode *root = &tree->root;
BNode *new_root_sibling;
if (tree->height == 0) {
new_root_sibling = BNodeLeaf_Insert(root, key, value);
} else {
new_root_sibling = BNode_Insert(root, key, value, tree->height);
}
if (new_root_sibling) {
BNode *old_root = BNode_Create(root->length, root->keys, root->children);
Key keys[2] = {BNode_GetMaxKey(old_root), BNode_GetMaxKey(new_root_sibling)};
BNode *children[2] = {old_root, new_root_sibling};
BNode_Initialize(root, 2, keys, children);
tree->height++;
}
}

void BTree_Delete(BTree *tree, Key key) {
if (tree->height == 0) {
BNodeLeaf_Delete(&tree->root, key);
} else {
BNode_Delete(&tree->root, key, tree->height);
}
}
</source>

=== See also ===
* https://gist.github.com/pervognsen/2d48ef9757ee3fd579179239febc817e

[[Category:Programming]]
[[Category:C++]]
[[Category:Data structures]]

B-tree

2020-10-29T17:14:20Z

Vegard: new page

<source lang="C++">
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INLINE inline
#define CopyMemory memcpy
#define Allocate malloc
#define Free free
#define Assert assert

typedef unsigned int Key;
typedef unsigned long Value;

// find where to insert the given key to maintain the sorted array
uint32_t SearchKeys(Key *keys, uint32_t length, Key key)
{
for (uint32_t i = 0; i < length; ++i) {
if (key <= keys[i])
return i;
}

return length;
}

template<typename T>
void Array_Insert(T *array, uint32_t length, uint32_t index, T value)
{
// shift everything up
for (uint32_t i = length ; i-- > index; )
array[i + 1] = array[i];

array[index] = value;
}

template<typename T>
void Array_Delete(T *array, uint32_t length, uint32_t index)
{
// shift everything down
for (uint32_t i = index + 1; i < length; ++i)
array[i - 1] = array[i];
}

// --- https://gist.github.com/pervognsen/2d48ef9757ee3fd579179239febc817e
// Per Vognsen, public domain

enum { BMAX = 32, BMIN = BMAX / 2, BHEIGHT = 6 };

struct BNode {
uint32_t length;
Key keys[BMAX];
union {
BNode *children[BMAX];
Value values[BMAX];
};
};

static void BNode_Initialize(BNode *node, uint32_t length, Key *keys, void *children) {
node->length = length;
CopyMemory(node->keys, keys, length * sizeof(Key));
CopyMemory(node->children, children, length * sizeof(BNode *));
}

static BNode *BNode_Create(uint32_t length, Key *keys, void *children) {
BNode *node = (BNode *)Allocate(sizeof(BNode));
BNode_Initialize(node, length, keys, children);
return node;
}

static void BNode_Destroy(BNode *node, uint32_t height) {
for (uint32_t index = 0; index < node->length; index++) {
if (height > 1) {
BNode_Destroy(node->children[index], height - 1);
}
Free(node->children[index]);
}
}

static INLINE Key BNode_GetMaxKey(BNode *node) {
Assert(node->length > 0);
return node->keys[node->length - 1];
}

static BNode *BNodeLeaf_Insert(BNode *leaf, Key key, Value value) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
leaf->values[index] = value;
return 0;
}
BNode *new_sibling = 0;
if (leaf->length == BMAX) {
new_sibling = BNode_Create(BMIN, leaf->keys + BMIN, leaf->values + BMIN);
leaf->length = BMIN;
if (index >= BMIN) {
leaf = new_sibling;
index -= BMIN;
}
}
Array_Insert(leaf->keys, leaf->length, index, key);
Array_Insert(leaf->values, leaf->length, index, value);
leaf->length++;
return new_sibling;
}

static BNode *BNode_Insert(BNode *node, Key key, Value value, uint32_t height) {
Assert(height > 0);
Assert(node->length > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
index--;
node->keys[index] = key;
}
BNode *new_child;
if (height == 1) {
new_child = BNodeLeaf_Insert(node->children[index], key, value);
} else {
new_child = BNode_Insert(node->children[index], key, value, height - 1);
}
BNode *new_sibling = 0;
if (new_child) {
if (node->length == BMAX) {
new_sibling = BNode_Create(BMIN, node->keys + BMIN, node->children + BMIN);
node->length = BMIN;
if (index >= BMIN) {
node = new_sibling;
index -= BMIN;
}
}
node->keys[index] = BNode_GetMaxKey(node->children[index]);
Array_Insert(node->keys, node->length, index + 1, BNode_GetMaxKey(new_child));
Array_Insert(node->children, node->length, index + 1, new_child);
node->length++;
}
return new_sibling;
}

static bool BNodeLeaf_Delete(BNode *leaf, Key key) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
Array_Delete(leaf->keys, leaf->length, index);
Array_Delete(leaf->values, leaf->length, index);
leaf->length--;
return leaf->length == 0;
}
return false;
}

static void BNode_Delete(BNode *node, Key key, uint32_t height) {
Assert(height > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index < node->length) {
if (height == 1) {
if (BNodeLeaf_Delete(node->children[index], key) && node->length > 1) {
Free(node->children[index]);
Array_Delete(node->keys, node->length, index);
Array_Delete(node->children, node->length, index);
node->length--;
}
} else {
BNode_Delete(node->children[index], key, height - 1);
}
}
}

struct BTree {
uint32_t height;
BNode root;
};

void BTree_Initialize(BTree *tree) {
Assert(BMAX == 2 * BMIN);
Assert(sizeof(BNode *) == sizeof(Value));
tree->height = 0;
tree->root.length = 0;
}

void BTree_Destroy(BTree *tree) {
if (tree->height > 0) {
BNode_Destroy(&tree->root, tree->height);
}
}

Value *BTree_Find(BTree *tree, Key key) {
uint32_t height = tree->height;
BNode *node = &tree->root;
for (;;) {
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
return 0;
}
if (height == 0) {
return (node->keys[index] == key) ? (node->values + index) : 0;
}
height--;
node = node->children[index];
}
}

void BTree_Insert(BTree *tree, Key key, Value value) {
BNode *root = &tree->root;
BNode *new_root_sibling;
if (tree->height == 0) {
new_root_sibling = BNodeLeaf_Insert(root, key, value);
} else {
new_root_sibling = BNode_Insert(root, key, value, tree->height);
}
if (new_root_sibling) {
BNode *old_root = BNode_Create(root->length, root->keys, root->children);
Key keys[2] = {BNode_GetMaxKey(old_root), BNode_GetMaxKey(new_root_sibling)};
BNode *children[2] = {old_root, new_root_sibling};
BNode_Initialize(root, 2, keys, children);
tree->height++;
}
}

void BTree_Delete(BTree *tree, Key key) {
if (tree->height == 0) {
BNodeLeaf_Delete(&tree->root, key);
} else {
BNode_Delete(&tree->root, key, tree->height);
}
}
</source>

[[Category:Programming]]
[[Category:C++]]
[[Category:Data structures]]

Fur shells

2020-10-11T19:25:53Z

Vegard: new page

{{Stub}}

See: https://twitter.com/MarioBrothBlog/status/1314996377605361664

[[Category:Graphics programming]]

Frame analysis

2020-09-08T21:23:24Z

Vegard: Doom Eternal

This is a list of "frame analysis" blog posts, i.e. posts which dissect how a game does its rendering.

== Engines ==

=== AnKi 3D ===

* http://anki3d.org/anatomy-of-a-frame-in-anki/

== Games ==

=== A Plague Tale: Innocence ===

* https://gamingbolt.com/a-plague-tale-innocence-graphics-analysis-one-of-the-best-looking-games-of-this-gen

=== Batman: Arkham Knight ===

* http://morad.in/2020/04/03/unmasking-arkham-knight/

=== Battlefield 3 ===

* https://www.slideshare.net/DICEStudio/directx-11-rendering-in-battlefield-3

=== Battlefield 4 ===

* https://www.slideshare.net/DevCentralAMD/rendering-battlefield-4-with-mantle-yuriy-o-donnell

=== BioShock Infinite ===

* https://solid-angle.blogspot.com/2014/03/bioshock-infinite-lighting.html

=== Castlevania: Lords of Shadow 2 ===

* https://www.elopezr.com/castlevania-lords-of-shadow-2-graphics-study/

=== Deus Ex: Human Revolution ===

* http://www.adriancourreges.com/blog/2015/03/10/deus-ex-human-revolution-graphics-study/

=== Doom 2016 ===

* http://www.adriancourreges.com/blog/2016/09/09/doom-2016-graphics-study/

=== Doom Eternal ===
* https://simoncoenen.com/blog/programming/graphics/DoomEternalStudy.html

=== Far Cry 5 ===

* https://www.gdcvault.com/play/1025480/Terrain-Rendering-in-Far-Cry

=== Gears of War 5 ===

* https://www.eurogamer.net/articles/digitalfoundry-2019-gears-5-tech-interview

=== Ghost of Tsushima ===

* https://blog.selfshadow.com/publications/s2020-shading-course/patry/slides/

=== GTA V ===

* http://www.adriancourreges.com/blog/2015/11/02/gta-v-graphics-study/

=== Killzone 2 ===

* https://www.guerrilla-games.com/read/deferred-rendering-in-killzone-2

=== League of Legends ===

* https://technology.riotgames.com/news/trip-down-lol-graphics-pipeline

=== Metal Gear Solid V ===

* http://www.adriancourreges.com/blog/2017/12/15/mgs-v-graphics-study/

=== Metro Exodus ===

* https://aschrein.github.io/2019/08/11/metro_breakdown.html

=== Middle Earth: Shadow of Mordor ===

* http://www.elopezr.com/the-rendering-of-middle-earth-shadow-of-mordor/

=== Ni No Kuni 2 ===

* https://blog.thomaspoulet.fr/ninokuni2-frame/

=== Red Dead Redemption 2 ===

* https://imgeself.github.io/posts/2020-06-19-graphics-study-rdr2/

=== Resident Evil 2 ===

* https://aschrein.github.io/2019/08/01/re2_breakdown.html

=== Rise of the Tomb Raider ===

* http://www.elopezr.com/the-rendering-of-rise-of-the-tomb-raider/

=== Supreme Commander ===

* http://www.adriancourreges.com/blog/2015/06/23/supreme-commander-graphics-study/

=== The Witcher 3 ===

* https://astralcode.blogspot.com/2018/11/reverse-engineering-rendering-of.html

=== The Witness ===

* https://blog.thomaspoulet.fr/the-witness-frame-part-1/
* https://blog.thomaspoulet.fr/the-witness-frame-part-2/

=== Total War ===

* https://gpuopen.com/anatomy-total-war-engine-part/
* https://gpuopen.com/anatomy-total-war-engine-part-2/
* https://gpuopen.com/anatomy-total-war-engine-part-3/
* https://gpuopen.com/anatomy-total-war-engine-part-4/
* https://gpuopen.com/anatomy-total-war-engine-part-5/

=== Wind Waker ===

* https://polycount.com/discussion/104415/zelda-wind-waker-tech-and-texture-analysis-picture-heavy

[[Category:Graphics programming]]

Frame analysis

2020-09-01T13:21:16Z

Vegard: Ghost of Tsushima

This is a list of "frame analysis" blog posts, i.e. posts which dissect how a game does its rendering.

== Engines ==

=== AnKi 3D ===

* http://anki3d.org/anatomy-of-a-frame-in-anki/

== Games ==

=== A Plague Tale: Innocence ===

* https://gamingbolt.com/a-plague-tale-innocence-graphics-analysis-one-of-the-best-looking-games-of-this-gen

=== Batman: Arkham Knight ===

* http://morad.in/2020/04/03/unmasking-arkham-knight/

=== Battlefield 3 ===

* https://www.slideshare.net/DICEStudio/directx-11-rendering-in-battlefield-3

=== Battlefield 4 ===

* https://www.slideshare.net/DevCentralAMD/rendering-battlefield-4-with-mantle-yuriy-o-donnell

=== BioShock Infinite ===

* https://solid-angle.blogspot.com/2014/03/bioshock-infinite-lighting.html

=== Castlevania: Lords of Shadow 2 ===

* https://www.elopezr.com/castlevania-lords-of-shadow-2-graphics-study/

=== Deus Ex: Human Revolution ===

* http://www.adriancourreges.com/blog/2015/03/10/deus-ex-human-revolution-graphics-study/

=== Doom 2016 ===

* http://www.adriancourreges.com/blog/2016/09/09/doom-2016-graphics-study/

=== Far Cry 5 ===

* https://www.gdcvault.com/play/1025480/Terrain-Rendering-in-Far-Cry

=== Gears of War 5 ===

* https://www.eurogamer.net/articles/digitalfoundry-2019-gears-5-tech-interview

=== Ghost of Tsushima ===

* https://blog.selfshadow.com/publications/s2020-shading-course/patry/slides/

=== GTA V ===

* http://www.adriancourreges.com/blog/2015/11/02/gta-v-graphics-study/

=== Killzone 2 ===

* https://www.guerrilla-games.com/read/deferred-rendering-in-killzone-2

=== League of Legends ===

* https://technology.riotgames.com/news/trip-down-lol-graphics-pipeline

=== Metal Gear Solid V ===

* http://www.adriancourreges.com/blog/2017/12/15/mgs-v-graphics-study/

=== Metro Exodus ===

* https://aschrein.github.io/2019/08/11/metro_breakdown.html

=== Middle Earth: Shadow of Mordor ===

* http://www.elopezr.com/the-rendering-of-middle-earth-shadow-of-mordor/

=== Ni No Kuni 2 ===

* https://blog.thomaspoulet.fr/ninokuni2-frame/

=== Red Dead Redemption 2 ===

* https://imgeself.github.io/posts/2020-06-19-graphics-study-rdr2/

=== Resident Evil 2 ===

* https://aschrein.github.io/2019/08/01/re2_breakdown.html

=== Rise of the Tomb Raider ===

* http://www.elopezr.com/the-rendering-of-rise-of-the-tomb-raider/

=== Supreme Commander ===

* http://www.adriancourreges.com/blog/2015/06/23/supreme-commander-graphics-study/

=== The Witcher 3 ===

* https://astralcode.blogspot.com/2018/11/reverse-engineering-rendering-of.html

=== The Witness ===

* https://blog.thomaspoulet.fr/the-witness-frame-part-1/
* https://blog.thomaspoulet.fr/the-witness-frame-part-2/

=== Total War ===

* https://gpuopen.com/anatomy-total-war-engine-part/
* https://gpuopen.com/anatomy-total-war-engine-part-2/
* https://gpuopen.com/anatomy-total-war-engine-part-3/
* https://gpuopen.com/anatomy-total-war-engine-part-4/
* https://gpuopen.com/anatomy-total-war-engine-part-5/

=== Wind Waker ===

* https://polycount.com/discussion/104415/zelda-wind-waker-tech-and-texture-analysis-picture-heavy

[[Category:Graphics programming]]

Frame analysis

2020-06-24T19:10:23Z

Vegard: /* Games */ Red Dead Redemption 2

This is a list of "frame analysis" blog posts, i.e. posts which dissect how a game does its rendering.

== Engines ==

=== AnKi 3D ===

* http://anki3d.org/anatomy-of-a-frame-in-anki/

== Games ==

=== A Plague Tale: Innocence ===

* https://gamingbolt.com/a-plague-tale-innocence-graphics-analysis-one-of-the-best-looking-games-of-this-gen

=== Batman: Arkham Knight ===

* http://morad.in/2020/04/03/unmasking-arkham-knight/

=== Battlefield 3 ===

* https://www.slideshare.net/DICEStudio/directx-11-rendering-in-battlefield-3

=== Battlefield 4 ===

* https://www.slideshare.net/DevCentralAMD/rendering-battlefield-4-with-mantle-yuriy-o-donnell

=== BioShock Infinite ===

* https://solid-angle.blogspot.com/2014/03/bioshock-infinite-lighting.html

=== Castlevania: Lords of Shadow 2 ===

* https://www.elopezr.com/castlevania-lords-of-shadow-2-graphics-study/

=== Deus Ex: Human Revolution ===

* http://www.adriancourreges.com/blog/2015/03/10/deus-ex-human-revolution-graphics-study/

=== Doom 2016 ===

* http://www.adriancourreges.com/blog/2016/09/09/doom-2016-graphics-study/

=== Far Cry 5 ===

* https://www.gdcvault.com/play/1025480/Terrain-Rendering-in-Far-Cry

=== Gears of War 5 ===

* https://www.eurogamer.net/articles/digitalfoundry-2019-gears-5-tech-interview

=== GTA V ===

* http://www.adriancourreges.com/blog/2015/11/02/gta-v-graphics-study/

=== Killzone 2 ===

* https://www.guerrilla-games.com/read/deferred-rendering-in-killzone-2

=== League of Legends ===

* https://technology.riotgames.com/news/trip-down-lol-graphics-pipeline

=== Metal Gear Solid V ===

* http://www.adriancourreges.com/blog/2017/12/15/mgs-v-graphics-study/

=== Metro Exodus ===

* https://aschrein.github.io/2019/08/11/metro_breakdown.html

=== Middle Earth: Shadow of Mordor ===

* http://www.elopezr.com/the-rendering-of-middle-earth-shadow-of-mordor/

=== Ni No Kuni 2 ===

* https://blog.thomaspoulet.fr/ninokuni2-frame/

=== Red Dead Redemption 2 ===

* https://imgeself.github.io/posts/2020-06-19-graphics-study-rdr2/

=== Resident Evil 2 ===

* https://aschrein.github.io/2019/08/01/re2_breakdown.html

=== Rise of the Tomb Raider ===

* http://www.elopezr.com/the-rendering-of-rise-of-the-tomb-raider/

=== Supreme Commander ===

* http://www.adriancourreges.com/blog/2015/06/23/supreme-commander-graphics-study/

=== The Witcher 3 ===

* https://astralcode.blogspot.com/2018/11/reverse-engineering-rendering-of.html

=== The Witness ===

* https://blog.thomaspoulet.fr/the-witness-frame-part-1/
* https://blog.thomaspoulet.fr/the-witness-frame-part-2/

=== Total War ===

* https://gpuopen.com/anatomy-total-war-engine-part/
* https://gpuopen.com/anatomy-total-war-engine-part-2/
* https://gpuopen.com/anatomy-total-war-engine-part-3/
* https://gpuopen.com/anatomy-total-war-engine-part-4/
* https://gpuopen.com/anatomy-total-war-engine-part-5/

=== Wind Waker ===

* https://polycount.com/discussion/104415/zelda-wind-waker-tech-and-texture-analysis-picture-heavy

[[Category:Graphics programming]]

Sphere tesselation

2020-06-16T10:41:34Z

Vegard: new page

{{Stub}}

== See also ==

* https://stackoverflow.com/a/7687312
* https://medium.com/game-dev-daily/four-ways-to-create-a-mesh-for-a-sphere-d7956b825db4
* https://scitepress.org/papers/2007/20747/20747.pdf

[[Category:Graphics]]

Self-running source

2020-05-25T11:24:32Z

Vegard:

== C ==

Set the executable bit on the following polyglot C/shell source file:

<source lang="C">
#if 0
gcc -Wall $0 && exec ./a.out; exit 1
#endif

#include <stdio.h>

int main(int argc, char *argv[])
{
printf("Hello world!\n");
return 0;
}
</source>

This is my favourite version because:
* readable (e.g. no multiline comments)
* minimal boilerplate
* only runs the program if it compiled successfully
* exits with 1 if there was an error

== See also ==

* https://coderwall.com/p/e1htcg/self-compiling-source-code
* https://twitter.com/dannas_/status/1238066416286400512
* https://twitter.com/_monoid/status/1264858552440586248

[[Category:C]]
[[Category:Programming]]
[[Category:C preprocessor snippets]]

Regex syntax

2020-05-20T08:14:56Z

Vegard: fix bug

{{Stub}}

I can never remember which programs use which regex variants, so here's a quick recap sheet.

{| class="wikitable"
|+
!
! grep (GNU)
! sed (GNU)
! vim
! less (GNU)
! python
|+
| capture
| <tt>$</tt> ... <tt>$</tt>
| <tt>$</tt> ... <tt>$</tt>
| <tt>$</tt> ... <tt>$</tt>
| <tt>(</tt> ... <tt>)</tt>
| <tt>(</tt> ... <tt>)</tt>
|+
| option
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>|</nowiki></tt>
| <tt><nowiki>|</nowiki></tt>
|+
| word boundary
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\b</tt>
|+
| zero or one
| <tt>\?</tt>
| <tt>\?</tt>
| <tt>\?</tt>
| <tt>?</tt>
| <tt>?</tt>
|+
| zero or more
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
|+
| zero or more (non-greedy)
|
|
| <tt>\{-}</tt>
| (unknown)
| <tt>*?</tt>
|+
| one or more
| <tt>\+</tt>
| <tt>\+</tt>
| <tt>\+</tt>
| <tt>+</tt>
| <tt>+</tt>
|+
| one or more (non-greedy)
|
|
| <tt>\{-1,}</tt>
| (unknown)
| <tt>+?</tt>
|}

== References ==

* https://www.gnu.org/software/grep/manual/html_node/Regular-Expressions.html
* http://vimregex.com/
* https://docs.python.org/3/library/re.html

[[Category:Programming]]
[[Category:Cheat sheets]]

Regex syntax

2020-05-20T08:00:22Z

Vegard:

{{Stub}}

I can never remember which programs use which regex variants, so here's a quick recap sheet.

{| class="wikitable"
|+
!
! grep (GNU)
! sed (GNU)
! vim
! less (GNU)
! python
|+
| capture
| <tt>$</tt> ... <tt>$</tt>
| <tt>$</tt> ... <tt>$</tt>
| <tt>$</tt> ... <tt>$</tt>
| <tt>(</tt> ... <tt>)</tt>
| <tt>(</tt> ... <tt>)</tt>
|+
| option
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>|</nowiki></tt>
| <tt><nowiki>|</nowiki></tt>
|+
| word boundary
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\b</tt>
|+
| zero or one
| <tt>\?</tt>
| <tt>\?</tt>
| <tt>\?</tt>
| <tt>?</tt>
| <tt>?</tt>
|+
| zero or more
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
|+
| zero or more (non-greedy)
|
|
| <tt>\{-}</tt>
| (unknown)
| <tt>*?</tt>
|+
| one or more
| <tt>\+</tt>
| <tt>\+</tt>
| <tt>\+</tt>
| <tt>+</tt>
|+
| one or more (non-greedy)
|
|
| <tt>\{-1,}</tt>
| (unknown)
| <tt>+?</tt>
|}

== References ==

* https://www.gnu.org/software/grep/manual/html_node/Regular-Expressions.html
* http://vimregex.com/
* https://docs.python.org/3/library/re.html

[[Category:Programming]]
[[Category:Cheat sheets]]

Regex syntax

2020-05-20T07:59:55Z

Vegard: less

{{Stub}}

I can never remember which programs use which regex variants, so here's a quick recap sheet.

{| class="wikitable"
|+
!
! grep (GNU)
! sed (GNU)
! vim
! less
! python
|+
| capture
| <tt>$</tt> ... <tt>$</tt>
| <tt>$</tt> ... <tt>$</tt>
| <tt>$</tt> ... <tt>$</tt>
| <tt>(</tt> ... <tt>)</tt>
| <tt>(</tt> ... <tt>)</tt>
|+
| option
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>\|</nowiki></tt>
| <tt><nowiki>|</nowiki></tt>
| <tt><nowiki>|</nowiki></tt>
|+
| word boundary
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\<</tt> or <tt>\></tt>
| <tt>\b</tt>
|+
| zero or one
| <tt>\?</tt>
| <tt>\?</tt>
| <tt>\?</tt>
| <tt>?</tt>
| <tt>?</tt>
|+
| zero or more
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
| <tt>*</tt>
|+
| zero or more (non-greedy)
|
|
| <tt>\{-}</tt>
| (unknown)
| <tt>*?</tt>
|+
| one or more
| <tt>\+</tt>
| <tt>\+</tt>
| <tt>\+</tt>
| <tt>+</tt>
|+
| one or more (non-greedy)
|
|
| <tt>\{-1,}</tt>
| (unknown)
| <tt>+?</tt>
|}

== References ==

* https://www.gnu.org/software/grep/manual/html_node/Regular-Expressions.html
* http://vimregex.com/
* https://docs.python.org/3/library/re.html

[[Category:Programming]]
[[Category:Cheat sheets]]

Mesh simplification

2020-05-16T06:14:53Z

Vegard: new page

{{Stub}}

See:
* https://github.com/zeux/meshoptimizer
* https://github.com/dougbinks/BunnyLOD

[[Category:Graphics programming]]

Buffer-centric IO

2020-05-13T09:45:30Z

Vegard: new page

{{Stub}}

See: https://fgiesen.wordpress.com/2011/11/21/buffer-centric-io/

[[Category:Programming]]

MediaWiki:Copyright

2020-05-02T21:19:35Z

Vegard: update year