The cube-like mesh shown in the images is a non-manifold mesh. Officially half edge data structures do not support such a topology. However, this case can be supported by continuing the boundary half edges through the non-manifold node. This is apparently the way it is done in 3DS Max, and also Blender. You can look at this article for several extension to the data structure to support non-manifold meshes.


Path tracing with Next event estimation and area lights auto occlusion

I am no expert in offline renderers, but I'll give it a go until someone else comes with a better answer :)
Shadow rays intersecting area light
It is very common to assign an extent to your rays. How to do so? Think about the parametric formula of a ray:
$$R(t) = O + t\vec{D}$$
it should immediately jumps out that how far $R(t)$ can be from the origin $O$ depends on how much we can travel in the direction $\vec{D}$, and this travelling is clearly governed by the parameter $t$.
Your problem here is that you don't want to let the ray travel indefinitely, but you want to stop just before it hits the source of the light, because otherwise, as you correctly noticed, everything will result occluded.
So how do you limit how much your ray can travel? You just have to limit the maximum value that $t$ can take. You have two option:

Probably the most intuitive one is to compute at what $t_{light}$ your light source lies. By using the same parametric formulation of the ray, if $L_p$ is the point you've chosen on the area light, then $t_{light}$ will be:

$$t_{light} = \frac{L_{p}[i] - O[i]}{\vec{D}[i]}$$
where $[i]$ represents the coordinate of your choice.  Given this, you want to stop your shadow ray to travel just before $t$ reaches $t_{light}$. If it goes over this value, report an unoccluded result.

Now while the option above is probably the first thing that comes to mind, it is wasteful as you'd need to both have $L_p$ around and perform some unneeded arithmetic operations if you have your light vector $\vec{D}$ as unnormalized around. In fact, this is none other than $L_p - O$ and in a case like this, the Light lies at exactly $t == 1$:

$$ O + 1 \times (L_p - O ) = L_p $$
So if you trace your shadow ray with an unnormalized direction $\vec{D}$, you can just set your maximum $t$ to be just under $1$. This is in fact what PBRT does, and as far as I am aware many other renderers.
Black dots (or NaNs)
Nothing to add over @Dan Hulme comment, so I'll just add it here for completeness of the answer:

"I think these are NaNs, will double check, but if you know common scenarios when this happens it'd be appreciated." The common scenario is that you're using floating-point and you have a bug in your code :-) You have to expect that you'll get NaNs during development, so you should either (a) make sure they get filtered out instead of propagated by the filter, or (b) show all NaNs as bright pink so it's immediately obvious when they're there. – Dan Hulme♦

and if I may add, you should expect some inf as well from time to time, so it's always good to account for these two special cases.
"Bright pixels"
With that, I assume you are talking about what is commonly referred to as fireflies. Fireflies avoidance is indeed quite a big topic and probably warrant its own question. However, just briefly.
Fireflies typically occur when you lots of your paths end in areas with low light and very few paths end up in very bright light.
There is lots of material on how to fight fireflies, a short google search will lead to a lot of techniques depending on your case.
Just to name drop a few:

Radiance clamping
Multiple Importance Sampling (especially if in presence of glossy/shiny surfaces)
Denoising techniques
Increment your sample count :-)
etc.

Also, generally increasing the size of the light source tends to help as well. Remember, the goal is always to hit those bright spot with higher probability!
A better solution to the problem is probably to use something like Bidirectional Path Tracing as this will have sub-paths starting from the light source as well, increasing the likelihood of sampling the bright areas.
Another cause of fireflies are caustics, but I don't want to make this answer longer, so if you are interested this is well worth an additional question.


16bit half-float linear HDR images as (diffuse/albedo) textures?

In film production, we almost never use 8-bit textures for color/albedo, because of banding, etc. (JPEG is especially problematic since by spec, it's sRGB rather than linear values.) We either use 'half' (16 bit float) or 16-bit unsigned integer values for color/albedo textures.


If I have more than enough memory, can it still be beneficial to use compressed textures?

Because memory bandwidth is not free.

No matter how much RAM you have, it takes less time to read 1024 bytes than it does to read 1024 KB. Compressed textures, relative to 32-bpp, can offer compression ratios of 4:1 or better. That's at least one quarter of the memory bandwidth costs of fetching the texture.

If your rendering uses lots of textures, reducing bandwidth pressure can improve performance.

Alternatively, the more memory you have available, the more memory you can use. If you consider 1GB to be "plenty of memory", then using compressed textures allows you to store the equivalent of maybe 2-3GB worth of textures. So now your textures can be larger, more detailed, or more varied, all within the same "plenty of memory" space. Or you can use some of that reclaimed storage for more meshes.

There's never enough memory; there's only a question of how much you're willing/able to use.


Linear interpolation on Plane (Marching Cubes)

P1 and P2 in this case represent the actual coordinates of the vertices of the cube in your output mesh. These might be the same as the input coordinates of the function you're using, or they might not be, it's entirely up to you how you output them. A simple way to map them would be to just use integer coords, biased by half the resolution of your sample volume - so a mesh spanning 100^3 cubes would have coordinates from -50 to 50 on each axis.

So in the formula you describe, (iso - V1) / (V2 - V1) gives you the amount to interpolate by, and (P2 - P1) is a vector representing a single cube lattice edge along the axis you want.

Let's assume we're using unit sized cubes, +Y is up, and +Z is 'into' the screen.

In your cube above, you will have crossings on the three edges coming from the left-bottom-front corner. On the X and Z edges you will interpolate by 0.25 : (0 - (-1)) / (3 - (-1)) , and on the Y edge you will interpolate by 0.5.

So if the left-bottom-front corner is at the origin, your three mesh vertices will be at
<0.25, 0, 0> ,
<0, 0.5, 0> and
<0, 0, 0.25>.

Apply the same formula to the right-top-back corner and you get <0.5, 1, 1>, <1, 0.5, 1> and <1, 1, 0.5>

The only difference is the left-bottom-front corner values will be P1 and V1 in your formula as it is at the 'negative' end of the edges to be interpolated, and the right-top-back values will be P2 and V2 as it is at the 'positive' end.

Hope that all makes sense.


OpenGL specular shading - Gradient banding issues

This is a common problem with very subtle gradients. The problem is that the image is displayed with 8 bits per component and this is not quite enough precision to make a gradient that is smooth to the eye under these conditions.

However, the underlying calculations being done in the shader are at higher precision (e.g. float = 24 effective bits of mantissa), so you can apply dithering to improve the appearance of the image.

You can do this by adding a slight amount of random noise to the value of each pixel in the shader. The noise can come from a texture, filled with random grayscale values in [0, 1] and mapped 1:1 to screen pixels. In the shader you remap this to the range [−0.5/255, 0.5/255] and add it to the output color.

Here's a Shadertoy demonstrating this. The left side has no dithering; the right side uses the procedure just described. As you can see, the banding vanishes on the right.

Dithering effectively allows you to represent intermediate values between 8-bit integer levels. For instance, an area that the shader computes as 82.3 (out of 255) would normally be uniformly rounded down to 82, but with dithering it will come out as a random mix with 70% of the pixels set to 82, and 30% set to 83. The eye averages over this very slight, high-frequency noise and it becomes practically invisible.


How to derive a perspective projection matrix from its components?

The second matrix translates the eye [...]

You don't do that in a projection matrix. You do that with your view matrix:

Model (/Object) Matrix transforms an object into World Space
View Matrix transforms all objects from world space to Eye (/Camera) Space (no projection so far!)
Projection Matrix transforms from Eye Space to Clip Space

Therefore you don't do any matrix multiplications to get to a projection matrix. Those multiplications happen in the shader, where you do $Projection\cdot View \cdot Model$$^1$ Matrix (for example in the vertex shader to specify your position output).

Also, remember that a perspective projection changes angles (i.e. parallel lines won't be parallel anymore). As far as I can see that is missing in your derivation.

Edit

As to how you actually derive it, I'll largely use the explanation byEtay Meiri. It has some additional information and illustration, so you may want to check it, if something seems unclear.

First, your camera is (as mentioned earlier) positioned in the origin.
Now assume, you will only project onto a plane of distance $d$ and the plane you project onto is bounded by the aspect ration $ar$ (that is $ar = \frac{window\text{ }width}{window\text{ }height}$ in positive and negative $x$ direction and by $1$ in positive and negative $y$ direction.

You can now determine $d$ by your vertical field of view $\alpha$ (since looking from the side, your camera, the center at the top of your projection plane and the center of the bottom of your projection plane build a triangle and your vertical field of view is the angle at your camera):

$\frac{1}{d} = \tan(\frac{\alpha}{2})\\
\implies d = \frac{1}{\tan(\frac{\alpha}{2})}$

Now you go about calculating projected points. Assume you have an arbitrary point $v = (v_x, v_y, v_z)$, and you want to calculate the point on your plane $p = (p_x, p_y, d)$. Looking at it from the side again, the triangle with your camera, your projection plane top center point and your projected point is similar to the triangle with your camera, your projection plane top center prolonged to have the same z coordinate, as your point $v$ and the point $v$, i.e. they have the same angles$^2$. Therefore, you can now calculate the projected $p_x$ and $p_y$ coordinate:

$
\frac{p_y}{d} = \frac{v_y}{v_z} \implies p_y = \frac{v_y\cdot d}{v_z} = \frac{v_y}{v_z \cdot \tan(\frac{\alpha}{2})}\\
\frac{p_x}{d} = \frac{v_x}{v_z} \implies p_x = \frac{v_x\cdot d}{v_z} = \frac{v_x}{v_x \cdot \tan(\frac{\alpha}{2})}
$

To additionally take into account, that the projection plane ranges from $-ar$ to $ar$ in $x$ direction, you would add $ar$ to the denominator in order to make the projected $x$ range be $\left[-1, 1\right]$:

$
p_x = \frac{v_x}{ar \cdot v_x \cdot \tan(\frac{\alpha}{2})}
$

If you think about applying this to a matrix now, you need to take into account the division by $z$, which is different for any point with differing $z$ value. Therefore, the division by z is deferred until after the projection matrix is applied (and is done without any code of you, i.e. for OpenGL you'd specify the gl_Position in Clip Space ($\implies$ after projection) and the division is done for you).

The depth test (Z-Test) still needs the $z$ value though, so it needs to be "safed" from the $z$ divide. Therefore you copy your $z$ value to the $w$ component (which is what you got right in your assumption) and end up with the following matrix:

$\left(
\begin{array}{cccc}
\frac{1}{ar\cdot\tan(\frac{\alpha}{2})}&0&0\\
0&\frac{1}{\tan(\frac{\alpha}{2})}&0&0\\
0&0&0&0\\
0&0&1&0
\end{array}
\right)$

The next step is to not project onto a plane, but into a $z$ range of $\left[-1, 1\right]$ (this range is for correct clipping, as is the same range when handling the $x$ and the $y$ coordinate). To be more specific, you don't want all points to end up in that range, but all points between your near and your far plane, so you map $[n, f]$ to $[-1, 1]$.
The resulting range is $2$, so you first scale your near-to-far range to $2$. Then you move it to be $[-1, 1]$:

$
f(z) = A\cdot z + B
$

And now taking into account that we want to safe the $z$ value from $z$ divide, we get to

$f(z) = A + \frac{B}{z}$

Mapping this scaling to $[-1, 1]$ is a little bit of leg work: you know that any point with $z = n$ (on your near plane) will be projected to $p_z = -1$ and any point with $z = f$ (on your far plane) will be projected to $p_z = 1$. This leads to the following equation system:

$
A + \frac{B}{n} = -1\\
A + \frac{B}{f} = 1
$

Solving this for $A$ and $B$ leads to$^3$:

$
A = \frac{-n-f}{n-f}\\
B = \frac{2fn}{n-f}
$

Your third row of the projection matrix must produced the (undivided) $p_z$ (projected) z value. Therefore, you can now choose the individual elements of said row $(\begin{array}{cccc}a&b&c&d\end{array})$ such that the correct $z$ value is produced when multiplying with your point. The correct $p_z$ value is (as established earlier):
$p_z = A\cdot z + B$

Therefore this must be the right hand side of your multiplication. Assume your point to project is $(x, y, z, w)$, then
you must achieve the following:

$
a \cdot x + b \cdot y + c \cdot z + d \cdot w = A \cdot z + B
$

Obviously, your point's $x$ and $y$ coordinate should not influence the projected $z$ coordiante, so you can set $a$ and $b$ to $0$.

$
c \cdot z + d \cdot w = A \cdot z + B
$

Since you know that $w$ for any point is $1$, you're left with

$
c \cdot z + d = A \cdot z + B
$

And thus, you have $c = A$ and $d = B$.

Now your matrix is complete for projection

$\left(
\begin{array}{cccc}
\frac{1}{ar\cdot\tan(\frac{\alpha}{2})}&0&0\\
0&\frac{1}{\tan(\frac{\alpha}{2})}&0&0\\
0&0&\frac{-n-f}{n-f}&\frac{2fn}{n-f}\\
0&0&1&0
\end{array}
\right)$

Obviously, the tutorial works a little differently in projecting with the vertical field of view, so we can take a look at how you can additionally get to that (with the help of Eric Lengyel:

Instead of projecting onto a plane at $z = d$, we will project onto the near plane, and thus get for a point $v = (v_x, v_y, v_z)$ the projected point $p = (p_x, p_y, n)$:

$
p_x = \frac{v_x \cdot n}{v_z}
$

Additionally, you want to map any point with $l\leq x \leq r$ to $\left[-1, 1\right]$, as before.
Thus you get

$f(x) = (x-l) \frac{2}{r-l}-1$

Combine those two and you achieve

$p_x = \frac{2n}{r-l}\left(-\frac{v_x}{v_y}\right)- \frac{r+l}{r-l}$

Now put this (and the term for $y$) into the matrix and you get to the first row, first column being  $\frac{2n}{r-l}$, and the first row, third column being $\frac{r+l}{r-l}$. Since you may assume $r$ and $l$ to be different, here you can see why those two matrices differ. $r$ and $l$ are guaranteed to be the same in the tutorial's matrix and therefore you get $r+l = ar-ar = 0$ in the denominator, making the third row first column (and second column accordingly) $0$.

$^1$Assuming you have Column-Major matrices like in OpenGL$

$^2$For the $x$ calculation, you will need to take a different point of your projection plane of course, but the idea is the same

$^3$The differences of the sign come from how you orient your camera: in your assumption it is along the negative $z$ axis, whereas in the tutorial it is along the positive $z$ axis


How enlarge parts of a video like snapchat lens filter

The answer is surprisingly simple: You move the vertices of the face-geometry.

To elaborate, the white wireframe mesh on the left of your image is placed so the geometry aligns with the photo. It is then texture-mapped with the photo, meaning that for each vertex in the mesh, a texture-coordinate is assigned (the point on the photo that should map to the vertex).

With every vertex assigned a texture-coordinate you can deform the mesh, doing ordinary texture-sampling at the interpolated texture-coordinates to have the image stretch - as if it was painted onto the head.

If you need to do this in realtime, you can use your graphics-card to do this; texture mapping is one of the things GPUs are really good at.

Now, if you want to do this on a video, you need to track the facial features to continuously align the geometry to the video. This is not an easy task, but you can probably find a wealth of libraries to help you out.

I am a bit uncertain which of the above would be difficult, so please feel free to ask any questions.


In a path tracer, when tracing a ray to a light with a shape other than a point ("area light" is the usual terminology), you generally select a random point on the surface of the light. When enough samples are taken, this results in both softer specular highlights and softer shadow penumbras: light will be reflected off a surface from a random distribution of incoming directions, and rays cast towards an area light with an obstruction in the way may or may not intersect the obstruction depending on which point on the light was sampled.

In real time, approximations to area lights are used. This Unreal Engine 4 white paper describes some of the considerations. One possibility is the "representative point" method, which per-pixel selects a point in the light's volume (brightest or nearest) and uses that as though it was a point light. Another option is modifying the roughness that is fed into the specular calculation based on a cone that approximates the area light (in the paper as "Specular D Modification").


How does Texture Cache work in Tile Based Rendering GPU

Whether it's a tile based GPU or not doesn't really affect the texture cache architecture. The memory layout of texture will look like some flavor of Morton order or Hilbert curve in all GPUs.

As a result, it's more efficient to render triangles that are close to equilateral triangles because GPU memory system fetches cache lines of texels.

So obviously on tile borders, it may happen that you have to fetch texels twice. This has a small cost as tile borders are only "few" pixels.

Arguably desktop GPUs behave identically to tile based GPUs as experiments such as the following demonstrate:
http://www.g-truc.net/post-0597.html

The size of the tiles differ but both architecture actually process fragments into a hierarchy of tiles of different sizes.

When coding for tile based GPUs my recommendation is to always have in mind:

Don't switch framebuffer objects unless you really need to.
When binding a new framebuffer object, if you don't need to save the content of the current framebuffer, discard it. If don't want to load content of the new framebuffer, then you should clear the framebuffer.


How to approximate the heightmap of processed wood?

A sine wave remapped to [0, 1] and raised to a power will give you periodic ridges: (Desmos graph)

That could be a good place to start. It will make perfectly straight, even ridges; but you could then perturb the X position where the sine is evaluated using low-frequency Perlin noise, which will make the ridges bend and waver while still going mostly along the original axis. You could use noise to fluctuate the power that the sine is raised to as well, making the ridges smoother and sharper in different places.


How to encode/decode buffer data in glTF?

The information you're looking for is defined in the 'accessors' and 'bufferViews' near the top of the source file you linked.

Bufferviews simply divide the buffer up into sub ranges and define broadly what kind of data lives there using some obscure shortcodes. In this case, target 34963 means index data and 34962 means vertex data. So from the other parameters in the bufferviews you can see that the first 72 bytes are indices and the remaining 576 bytes are vertex data.

The accessors are what actually define the format of the data and again use weird codes for "componentType" - 5123 is an unsigned short (2 bytes) and 5126 is single precision float (4 bytes). They also define whether they should be read singly ("SCALAR") or in vector groups (e.g. "VEC3"), and also a starting offset into the bufferview and "stride" between the start of data points like regular OpenGL vertex buffer bindings.

Putting it all together, the first 72 bytes are 36 shorts representing the indices (3 * 12 triangles). The next 576 bytes are two consecutive sets of 24 vec3 (4 per square face, 12 bytes per vec3) representing vertex data. Since the first set are clamped to + or - 1/2 and the second set to + or - 1, I'm guessing first set are positions, second set are normals.

The base 64 encoding just takes the raw bit stream, splits it into groups of 6 rather than 8, and maps each unique 6-bit combination onto a character. You can see this is quite wasteful as each character takes at least 8 bits to store, quite possibly 16 or more depending on the encoding used.


The blog post that you talked about, is not about generating bokeh for a computer generated image. It is instead about generating a believable depth of field effect from an image captured by a smartphone camera, as the effect is desired for portraits to make the subject stand out. It generally works by splitting the image in to two parts. One part is the subject, which should not be blurred. The other part is the background, which should be blurred but the pixels of the subject should have no influence and would thus have a weight of zero. Slightly more sophisticated algorithms may make the blur kernel size variable across an image to create a smoother transition, but the subject's pixels would still be ignored.

In games and CGI, post process depth of field is done differently. There are multiple ways for it. A simple google search shows multiple. You could do depth of field like you have, and simply ignore the pixels which should not be blurred to remove the ghosting. However, this is not true to how depth of field occurs inside of a camera. So, in order to get a good algorithm to simulate depth of field, I will first try to explain how you get the depth of field effect in an actual camera.

Let us say, that we have an object, a single lens and an image sensor. We look at them from the side.

Light scatters in many different directions when hitting the object. To simplify we only take one point. From this point, I will show the light that would hit the lens as a gray solid.

The lens bends the light towards a single point. That is the focal point.

You can see that the focal point is in front of the sensor. This causes the light from that single point on the object, to fall on a large portion of the sensor. If the focal point is behind the sensor, the same would happen. But, if the focal point lies on the sensor, there would only be one point on the sensor where the light falls on. This area where the light falls on the sensor, is called the circle of confusion (CoC). This is also the cause of the depth of field effect.

One important thing to know, is that when the point on the object moves around, the focal point also moves around. If the point moves closer to the lens, the focal point moves closer to the lens, which would alter the size of the circle of confusion. This gives you the gradual change in blurriness that you have with depth of field, since the circle of confusion gradually becomes larger when an object moves away from the area in focus.

If we add in an aperture we simply block out a part of the light, which causes the circle of confusion to be smaller. This allows us to determine how much light to let in (to make the image brighter or darker), and how strong the depth of field effect is.

From this, we can conclude a few things on how we should implement depth of field.

Every point whose light enters the camera lens, has a circle of confusion.
The circle of confusion is the area where the light, from that point, falls on.
The circle of confusion changes size when the point moves closer to or further away from the lens, or when the aperture changes size.
The area of the circle of confusion has no falloff. Every point inside the circle of confusion has the same weight. This results in a box blur.
If a point is in focus, its circle of confusion would be either zero or something so small, that it is not noticed.

The algorithm is quite simple. For each pixel in the image, we use the depth to calculate the circle of confusion. Then, we add the colour of that pixel to all the other pixels that lie in the circle of confusion. However, if that other pixel is closer to the camera (a lower depth value), it would block the light from our pixel, and we should not add the colour of our pixel to the blocking pixel.

In pseudo code it would look something like this;

// for each pixel in the all-focus image
for(x = 0; x < width; x++){
    for(y = 0; y < height; y++){
        // How much blur? Zero or close to it if it should be in focus.
        float CoCRadius = calcCoCRadius(depth(x, y));

        // For every pixel in the square with the size of CoCRadius.
        for(i = x - CoCRadius; i <= x + CoCRadius; i++){
            for(j = y - CoCRadius; j <= y + CoCRadius; j++){
                // Discard pixels outside of the shape. Square -> Circle
                if(isInBokehShape(i - x, j - y)){
                    // Discard pixels that would block it.
                    if(depth(i, j) >= depth(x, y){
                        // Add the colour.
                        newColour[i, j] += colour(x, y);
                        // Add the weight, for normalizing.
                        weight[i, j] += 1.0f;
                    }
                }
            }
        }

    }
}
//Normalize the values with the weight.
for(x = 0; x < width; x++){
    for(y = 0; y < height; y++){
        newColour[x, y] /= weight[x, y];
    }
}

This would give you a depth of field effect that is quite true, and does not give you the ghosting effect. $calcCoCRadius$ is a method that calculates the radius in pixels of the circle of confusion. It could be anything, but if you want it as true to an actual camera, then you can use the formula from this Wikipedia page. $isInBokehShape$ is a method which returns a boolean on whether the point is inside the bokeh shape. With the two for loops we just get a square, but if we want to get a circle shaped bokeh, we need to discard the pixels that would lie outside of the circle. This discarding is also the reason why we keep track of the weights and normalize afterwards with the weight, since we do not know how many pixels we need to discard. The weight is also useful if you do want a falloff in the circle of confusion, for example if you want a gaussian blur.

Another important thing to know, is that the implementation listed here, is not very optimal. The problem is basically that you write to multiple different pixels. This causes race conditions. Instead, it is better to rework the algorithm so that you only need one write. Basically, you loop through every pixel and you then you check all other pixels (or pixels inside of a maximum CoC radius) whether their CoC radius is large enough that they contribute to the pixel's colour. This way, you can also put the normalizing of the values inside the first loop over all the pixels instead of having to do that later.

This should be a fairy good way of implementing depth of field as a post processing effect. There are also other ways, but this is one.


After asking around a bit on Twitter, I found that what you're trying to solve seems to be an instance of the assignment problem. In general, the assignment problem is to take two sets and assign elements of one to the other, in such a way that a cost function is minimized.

In your case the two sets would be the stars in each galaxy, and the cost function would be the distances between stars. An optimal solution to the assignment problem would then minimize the total distance between corresponding stars, summed over all the stars in the galaxies.

A classic algorithm for solving the assignment problem is called the Hungarian algorithm. If you google around, you'll some explanations of how it works. There's even a Python module implementing this algorithm, called Munkres.

A warning: this algorithm runs in $O(n^3)$ time, so it will be rather slow for large point sets. You might want to do some further research on fast algorithms for the assignment problem. It may be that you can find a faster, approximate algorithm if you don't require a perfectly optimal solution. Or maybe there are specialized algorithms for the case of point clouds that can do better.


GLSL Compute Shader Setting "shared" memory buffer size

GLSL has no mechanism to change the "size" of shared memory. Indeed, GLSL is structurally incapable of such a thing.
You can't get a pointer to shared memory. Indeed, "shared memory" doesn't really exist in GLSL; there are only shared variables. And variables have a compile-time fixed size. So GLSL wouldn't even have a good way of allowing you to affect how much "shared memory" gets used from outside of the shader.
The closest you might get to this is to have some kind of shared variable array whose size is determined from outside of the shader. But even then, you're not influencing the size of memory in total; you're influencing the size of just that array.
And you can sort of do that. SPIR-V in OpenGL allows specialization constants. These are values specified by the outside world during the compilation process for the shader object. Such constants can be used as the size for a shared variable array. Of course, this means that changing it requires a full recompile/relink process.


Skeletal animation: What is the purpose of multiplying interpolated bone matrix with parent's matrix?

The bone transforms are relative to their parent in the hierarchy. That's the point of the hierarchy, i.e. when you move your arm, your hand and fingers go along with it. So when an animation (or whatever) changes the transform of A, then bones B and C are supposed to move along with it.

This is accomplished by defining bone B relative to A, and C relative to B, and so on.

Therefore, to get the final transform from bone local space to world space, you have to combine all the transforms from the current bone up the hierarchy to the root.

To put it another way:

The localTransform of C takes you to B's local space.
Then the localTransform of B takes you to A's local space.
Then the localTransform of A takes you to world space (since A is the root).


Its not actually possible to do. Because that paper you print on needs to have properties not avalialbe. The color on the edge are very pure and can not be mixed. I dont also see any way they could be reflected either. Also the xy diagram is not the full color space just a slice of it.


Getting from the default view volume to an image on the screen

The mapping from NDC space to screen space is orthographic.

The x is mapped linearly from [-1, 1] to [0,viewport width], same with y and viewport height.

This mapping happens after the projection matrix has been applied and the divide by w happened.


How to decompose a complex mesh to simple geometry shape programmatically?

It might be a bit of an overkill, but you could use spatial partitioning, such as Octrees.

Once you have it built, you can start evaluating partitions, given a max depth level of your choice, and form bounding volumes with the vertices inside each partition.

You can test all of your shapes for each partition and choose the one that approximates the best all vertices you are enclosing in it (you can measure this by, for example, the volume which, while enclosing all vertices, takes up the less volume).

PS: I've never tried anything like this, is purely theoretical


Tweaking a glow shader to make it look better

Sigma and kernel size of Gaussian filter

Regarding how to choose the sigma and the kernel size (pixels) of the Gaussian: you set the sigma based on how wide of a blur you want (judging it visually) and then choose the kernel size based on the sigma. It's a game of finding a kernel size that captures enough of the (mathematically infinite) bell curve to look good, while not being too expensive.

As a rule of thumb, the kernel size should be at least 6 times the sigma. Then the kernel extends out to 3 sigmas in each direction, which is enough to cover almost all the weight of the mathematical bell curve. It's also nice to round up the pixel size to the next odd number so the filter will be symmetrical. So for example, with sigma = 1.5 px, you'd use a 9-pixel filter; with sigma = 2.0 px, use a 13-pixel filter, etc.

Alternatively, if you have performance limitations that control how big a kernel size you can use, then divide by 6 to get the maximum sigma you can get away with. (Note that sigma can be fractional, as it's just an input to the bell curve equation.)

By the way, a trick to get better performance on large Gaussian blurs is to downsample the image, perform a smaller blur, then upsample. For instance, to get an effective 13-pixel blur, you could downsample the image by 2x (using bilinear filtering), then perform a 7-pixel blur, and then upsample (using bilinear filtering). It will look almost as good as the 13-pixel blur, but will be considerably faster.

Creating a good-looking glow filter

A common trick with these is to use multiple Gaussians of different radius, added together. It makes a better glow effect than any single Gaussian by itself. For example, here's a mockup in Photoshop created with three layers additively blended together. The three Gaussians are of size 3px, 5px and 11px (corresponding to sigma = 0.5px, 0.83px, 1.83px respectively).

You can also add even larger Gaussians to further increase the apparent radius of the glow. This is how the standard "bloom" effect is implemented in 3D game engines.

If performance is a concern, the smallest Gaussian can be replaced by a copy of the unblurred original image; the resulting effect will look sharper, not so soft, but will still have a glow surrounding it. As mentioned previously, larger Gaussians can be done by downsampling, blurring, and upsampling; and the upsampling can be done using hardware bilinear filtering, folded into the pass that blends the layers together.

Jaggies

You'll notice that jaggies are still visible in some areas of the above image. Unfortunately, blurring is not very effective at hiding jaggies unless the blur radius is quite large. There's no easy way to use a post-process get rid of jaggies: the best way to avoid them is not to render them in the first place. :)

I hear you that you can't use MSAA for performance reasons, but may be another option.  Depending on how you render the glow trails, you might be able to slightly increase their size, and write a shader that applies a gradient to fade out the color within a couple pixels of the edge. That should help them look smoother. Here's a shadertoy that demonstrates a 1px-wide edge falloff used for antialiasing a procedural shape.


Determining Rational Quadratic Bezier Curve Weights for Circle

Check out the section on Circular Arcs and Circles, from Ching-Kuang Shene's excellent computational geometry course notes:

[G]iven three control points P0, P1 and P2 such that P0P1 = P1P2 holds, if we choose w, the weight for P1, to be sin(a), where a is the half angle at control point P1, the resulting rational Bézier curve is a circle.

The second diagram on that page is particularly useful. If P0 is at (0,0), P1 is at (1,0), and P2 is at (1,1), then the angle at P1 is 90 degrees; half that is 45, so assigning weights w0 = w2 = 1 and w1 = sin(45) = 1/sqrt(2) will produce a circle.
EDIT: To actually implement this from your code: The three points are [a,b,c]. If you know that the distance from a to b is the same as the distance from b to c, then you can set w1 and w3 to 1, and w2 to the sine of half the angle between them. Look up the half-angle formula for sine to see that sin(x/2) = sqrt((1 - cos x) / 2). The cosine of the angle between two vectors is the normalized dot product, i.e. cos x = dot(a-b,c-b) / (a-b)^2. Thus, you can do something like
ba = a - b
bc = c - b
cosx = ba.Dot(bc) / ba.Dot(ba);
w2 = math.sqrt(0.5 * (1 - cosx));

Again, this will only work if the distances ba and bc are the same. (You can still make a circle otherwise, but the weights will be more compilcated.)


Extracting the green-screen region borders

Here is a brute force algorithm. This requires some temporary storage (another image, an array, etc.) to record the visited pixels.

Start at the first pixel and continue iterating over the image until you find a green pixel. Mark each read pixel as "visited".
Extract the set of green neighbor pixels and record them. Also tag them as "visited". The idea is to find all the green pixels connected to the one found in [1].
If any pixels in the source image are left, go back to [1].

This will give you a set of contiguous green pixel regions where each pixel appears 1 or 0 times.


What is the simplest way to create basic 3d/isometric style images programatically like autocad/blender

Since your actuallyu doing a PDF file you should do this as a vector drawing not a image format. This makes for way more clearer end results. I will generate a image in EPS, EPS is easy to build into your PDF file with say distiller, ghostscript, sent to printer or injected into TeX (though then you may want to use Tix or or PStricks) .
Ok first you have to undertsand that EPS is a full programing language (Postscript), in addition to being a vector format (the Encapsulation part). I will be uisng the features to remove repetition. The file begins with a encapsulation marker so that you can more easily insert it programmatically.
So frist draw the thing form a overhead view, then we will transform that into isometric with a affine transform:

Image 1: Preview of listing 1
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 538 300
%%Title: listing 1
%%Creator: joojaa
%%CreationDate:  2020-09-23
%%EndComments

% postscript style shorthand relative
/m {moveto} def
/rm {rmoveto} def
/rl {rlineto} def

10 10 translate % add some padding
72 25.4 div 100 div  dup scale  % draw in  1:100
70 setlinewidth %0.7 mm technical pen

newpath  % coordinates and ops follow
0 4100 m
0 5500 rl
9000  0 rl
0 -4000 rl
4000 0 rl
0 -1300 rl
0 -800 rm
0 -1000 rl
stroke

%%EOF

Ok then we transform the entire thing to isometric

Image 2: Image after Listing 2. Only stroke changed
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 538 300
%%Title: listing
%%Creator: joojaa
%%CreationDate:  2020-09-23
%%EndComments

% postscript style shorthand relative
/m {moveto} def
/rm {rmoveto} def
/rl {rlineto} def

10 10 translate % add some padding
72 25.4 div 100 div  dup scale  % draw in  1:100
70 setlinewidth %0.7 mm technical pen

newpath  % coordinates and ops follow
0 4100 m

0 5500 rl
9000  0 rl
0 -4000 rl
4000 0 rl
0 -1300 rl
0 -800 rm
0 -1000 rl

%changed stroke to this
gsave
 false upath
  9600 60 sin mul 0 translate
  [60 sin 60 cos -60 sin -60 cos 0 0] concat
  ustroke
grestore
%eof changed

%%EOF

Then we duplicate this and offset

Image 3: After offsetting
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 538 300
%%Title: listing 3
%%Creator: joojaa
%%CreationDate:  2020-09-23
%%EndComments

% postscript style shorthand relative
/m {moveto} def
/rm {rmoveto} def
/rl {rlineto} def

10 10 translate % add some padding
72 25.4 div 100 div  dup scale  % draw in  1:100
70 setlinewidth %0.7 mm technical pen

newpath  % coordinates and ops follow
0 4100 m

0 5500 rl
9000  0 rl
0 -4000 rl
4000 0 rl
0 -1300 rl
0 -800 rm
0 -1000 rl

gsave
 false upath
  9600 60 sin mul -1100 translate
  [60 sin 60 cos -60 sin -60 cos 0 0] concat
  ustroke
grestore

gsave
 false upath
  9600 60 sin mul 10 translate
  [60 sin 60 cos -60 sin -60 cos 0 0] concat
  ustroke
grestore

%%EOF

Next draw connecting lines

Image 4: Listing 4 result
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 538 300
%%Title: listing 4
%%Creator: joojaa
%%CreationDate:  2020-09-23
%%EndComments

% postscript style shorthand relative
/m {moveto} def
/rm {rmoveto} def
/rl {rlineto} def
%draw connecting line

/tf { 9600 60 sin mul 10 translate
    [60 sin 60 cos -60 sin -60 cos 0 0] concat} def

/dc {gsave
    newpath
    9600 60 sin mul 10 translate
    [60 sin 60 cos -60 sin -60 cos 0 0]
    concat m -1100 -1100 rl
    stroke
    grestore
     } def

10 10 translate % add some padding
72 25.4 div 100 div  dup scale  % draw in  1:100
70 setlinewidth %0.7 mm technical pen

newpath  % coordinates and ops follow

0 4100 m
0 5500 rl
9000  0 rl
0 -4000 rl
4000 0 rl
0 -1300 rl
0 -800 rm
0 -1000 rl

%drawing no need to change
gsave
 false upath
  tf
ustroke
grestore

gsave
 false upath
  0 -1100 translate
  tf
  ustroke
grestore

{dc} {dc} {} {} pathforall

%%EOF

Todoo:

Change stroke to round
Draw in paperspace
Draw distances.
Compute bound and center
Etc.

I might return later


This refers to the order of vertices within a face. Typically in 3D graphics, faces are wound counterclockwise, so that if you're looking from outside of the tetrahedron/mesh, all the front faces will have their vertices in counterclockwise order. (See here and here for more explanation.) This is a "right-hand rule" in that if the fingers of your right hand curl in the winding direction of the vertices, then your thumb points toward the outside of the mesh.


Data structure and algorithm for clipping triangulation with leaf nodes of an octree

Rather than making one spatial subdivision structure do double duty in representing both the voxels and the triangles, I would suggest creating a separate BVH for the mesh. You can find many articles and papers about BVH-building algorithms on the web. It's likely to be a more efficiently queryable representation of the mesh than the octree would be.

Given the BVH, it's easy to determine whether a given voxel might intersect the mesh by starting at the BVH root and traversing to child nodes that intersect the voxel box. Depending on the quality of the BVH, i.e. how tightly it fits the mesh, many voxels (or even higher-level octree nodes) may be able to be eliminated with only a few checks. For voxels that do intersect the mesh surface, the BVH traversal will reach down to the leaves, where you can accumulate the triangles into a list for clipping.

If the BVH is built in the mesh's local space, the mesh can easily be moved or transformed without needing to update the octree. (If translation is the only transform needed, then the BVH nodes will always be axis-aligned relative to the voxels, which simplifies the intersection test to an AABB overlap test; if more general transforms are needed, you'd have to use a more general OBB vs OBB test.)

However, note that a BVH doesn't lend itself that well to determining whether a things are inside versus outside a watertight mesh. If that's important to you (it wasn't clear to me whether it is), then you might want to look into using a BSP tree instead of a BVH. A BSP tree can be used for intersection testing similarly to a BVH, but additionally can represent the exact boundary of the mesh so that it can be used to determine whether a point (or voxel) is inside or outside. This property of BSP trees is widely used for collision detection.

An alternate approach to determining inside/outsideness is to use raycasting and count the number of intersections with the mesh (even = outside, odd = inside). The raycasting can be accelerated by the BVH as well.


Just like for any reduction or drawing, if you scale one part and not the other, their relative proportion is changed, so yes, aesthetic, matching, functionality are affected: scale everything in the same proportion. Nothing specific to 3D printing here.


What if we don't mention Modelview and projection matrix?

Your screen isn't 3D, so how do you display 3D objects on it? You need to map 3D coordinates into 2D space. This also explains why your OpenGL code is not behaving how you're expecting it to. Sorry if parts of this answer are things you already know (just trying to be comprehensive).

What do the model view and projection matrices do?

The model view matrix is actually two matrices (multiplied together): the model matrix and the view matrix. This is important to understanding because these are two transformations into different spaces.

The model matrix transforms model space into world space. This means that say you have a vertex is at an offset from the center of a model. If you want that vertex to be in world space, it must use the scale, rotation, and position of the model to determine this. The model matrix accomplishes this.

The view matrix transforms the world space into the camera space. Does world move or does the camera move in a 3D application? Well, actually the world moves around the camera. The camera is always at the origin, so the view matrix moves the world to this point.

The projection matrix might be the trickiest to visualize. Screens are 2D (technicalities aside), so how do we show 3D objects here? A projection matrix converts 3D coordinates into 2D coordinates (with depth, so still technically 3D). You end up with Normalized Device Coordinates (NDCs). Each vertex on screen is represented by three values:
* x (horizontal) ranging from [-1, 1]
* y (vertical) ranging from [-1, 1]
* z (depth) ranging from [-1, 1]

Why don't you need model-view and projection matrices?

It's not that you don't need them, it's just that you are using as explained in the last step above. Otherwise, you are effectively just rendering 2D graphics. Right now you are drawing a quad.

Look at the coordinates that you are providing. You are basically treating the vertices as 2D vertices for 2D graphics since you are directly specifying their coordinates in NDC space. Remember, the coordinates you picked are between -1 and 1 for x and y, so you are effectively treating them as NDCs. You directly send them to the rasterizer in your example.

Further Reading

Tutorial 3 : Matrices | opengl-tutorial.org
Coordinate Systems | LearnOpenGL.com
OpenGL Projection Matrix | songho.ca


Is there a way to draw spherical objects without triangles?

A standard technique is to use a ray/sphere intersection test inside a pixel shader. One draws a billboard large enough cover the area the sphere could appear on the screen (or drawing a bounding cube) to reduce the number of wasted intersection tests (other geometric shapes could be used). The fragment is killed if the intersection test fails; if an intersection occurs, the appropriate depth value is calculated in the pixel shader and output for further visibility tests.


Why there's no z-fighting for coincident planes if the camera look perpendicular at them?

Even if two triangles aren't coincident...
Z fighting happens because of floating point quantization, this results from all the math the shader does to compute vertex positions such as: $glPosition = Projection*View*Model*vertex\_position$
When the vertices are all the same distance and angle from the camera then all the floating points values are effectively the same and the tiny error that crops up is so close that the Z fighting appears to go away.
On the other hand if you change the angle of the camera even a little bit then all the floating point values for each vertex are now slightly different and so is the quantization. This results in the z fighting that you are seeing.
But keep moving the camera back, and the results for the perfectly aligned camera will eventually begin to exhibit the same behavior. The camera position is also a floating point value and subject to floating point error so no matter how perfectly the camera is aligned, it will still, eventually, have enough error to cause the same issue.


Acceleration techniques for CPU soft-shadow calculation in light mapper

You could try to optimize the calculation by first casting a smaller number of "feeler rays" (say 32) to check for penumbra, and cast the remaining rays if the result is in penumbra according to the rays. Of course this can give you false negatives, but you could then try to improve the heuristics by checking the results of nearby feeler rays.


OBJ files typically contain vertex positions, texture coordinates (also known as UVs), and normals, as well as face data. There are other kinds of things they can contain but those are the most common (see here for a fuller specification).
Vertex positions are specified with the v command, texture coordinates with vt, and normals with vn. The faces then reference those values by index using something like f 1/2/3 4/5/6 7/8/9, where each grouping of values represents a vertex on the face, and the numbers separated by slashes are the position/texture/normal indices.
The texture coordinates are the part that tell you what point in the texture image (jpg) goes with that vertex. If you've downloaded or exported a model that has a texture mapping, you should be able to see those vt commands in the obj file.
If a model doesn't have texture coordinates, though, then it most likely needs the help of a human 3D modeler. It is not easy to create usable texture coordinates for a model automatically (this is a big research topic). 3D modeling applications have various tools to help the modeler set up a texture layout, but it still usually needs some hand-tweaking to work well.


What happens to float values written to UNSIGNED_BYTE texture?

Unsigned byte textures in a graphics API are usually "normalized"—the byte values are interpreted as ranging from 0.0 to 1.0, with a byte of 255 mapping to 1.0. So no, they aren't truly floating-point values, but the hardware will automatically convert them to/from float when you read/write the texture. If you try to write a value outside the [0, 1] range, it will be clamped.

As for the precision highp part, it doesn't directly affect the texture, but it can certainly affect any calculations of values you write to the texture. For example, to calculate an 8-bit texture you certainly want a minimum of 8 bits of mantissa precision (i.e. lowp)—and you probably want more than that, depending on what calculations you're doing. I'd advise you to check what the actual precision levels are on your device, since they vary widely depending on what GPU you have. See this question for more.


How physically-based is the diffuse and specular distinction?

To start, I highly suggest reading Naty Hoffman's Siggraph presentation covering the physics of rendering. That said, I will try to answer your specific questions, borrowing images from his presentation.

Looking at a single light particle hitting a point on the surface of a material, it can do 2 things: reflect, or refract. Reflected light will bounce away from the surface, similar to a mirror. Refracted light bounces around inside the material, and may exit the material some distance away from where it entered. Finally, every time the light interacts with the molecules of the material, it loses some energy. If it loses enough of its energy, we consider it to be fully absorbed.

To quote Naty, "Light is composed of electromagnetic waves. So the optical properties of a substance are closely linked to its electric properties." This is why we group materials as metals or non-metals.

Non metals will exhibit both reflection and refraction.

Metallic materials only have reflection. All refracted light is absorbed.

It would be prohibitively expensive to try to model the light particle's interaction with the molecules of the material. We instead, make some assumptions and simplifications.

If the pixel size or shading area is large compared to the entry-exit distances, we can make the assumption that the distances are effectively zero.
For convenience, we split the light interactions into two different terms. We call the surface reflection term "specular" and the term resulting from refraction, absorption, scattering, and re-refraction we call "diffuse".

However, this is a pretty large assumption. For most opaque materials, this assumption is ok and doesn't differ too much from real-life. However, for materials with any kind of transparency, the assumption fails. For example, milk, skin, soap, etc.

A material's observed color is the light that is not absorbed. This is a combination of both the reflected light, as well as any refracted light that exits the material. For example, a pure green material will absorb all light that is not green, so the only light to reach our eyes is the green light.

Therefore an artist models the color of a material by giving us the attenuation function for the material, ie how the light will be absorbed by the material. In our simplified diffuse/specular model, this can be represented by two colors, the diffuse color, and the specular color. Back before physically-based materials were used, the artist would arbitrarily choose each of these colors. However, it should seem obvious that these two colors should be related. This is where the albedo color comes in. For example, in UE4, they calculate diffuse and specular color as follows:

DiffuseColor = AlbedoColor - AlbedoColor * Metallic;
SpecColor = lerp(0.08 * Specular.xxx, AlbedoColor, Metallic)

where Metallic is 0 for non-metals and 1 for metals. The 'Specular' parameter controls the specularity of an object (but it's usually a constant 0.5 for 99% of materials)


If I blur the whole image and apply the result on the sphere, the white background will bleed onto the sphere shape and I want to avoid that. I also don't want that the blue (3) and yellow (4) sphere merges with the red (1) and green (2) ones. But I would like that the green and red ones merges. Again This could be done using the depth but if you have more precision about how to do it it would be interesting.

You will need to blurr in multiple passes to achieve this:
once for the blue and once for the yellow, as well as once for the red and green (together). That is: you need to render to texture, you need three textures in this instance to render to, you need to blur the individual textures and then combine them in another render pass.
If you know beforehand that the green and red spheres may blur together, you can just hardcode it, otherwise you need to come up with a way of determining, which spheres may blur together, and group your spheres to render into the same texture.

If you do this, keep in mind that for combining the three individual blurred textures, you need z-values for correct visibility determination.

  I would like to blur the content of those 4 spheres using the same offset no mater their position. If I apply the same blur on all objects, far object's content will appear more blurry than ones on the foreground and I want to avoid that. I think that the depth make could help but any precision would help me.

Yes, you can scale your blur filter with a depth value (where you should "invert" the value to make the blurriness scale to larger effects on closer proximities, i.e. smaller depths). For a box filter, you take ratios of the pixels neighbourhoods, but you need to make sure that those ratios add up to one. For this, you'd ideally increase the ratio for the center pixel based on the proximity and reduce the ratio for the neighbouring pixels accordingly.

  performances and quality : Kawase blur, Box blur and two pass Gaussian blur.

As to performance, I can't say anything about the three. As to quality, the Box Filter is rather simple, but that doesn't mean it doesn't suffice for your specific need. Just test them against each other.


How can I use 3d animation to create a character that uses sign language?

This is quite a broad topic, so I can only give a general overview. If you've never done any interactive animation before, this might be too big a challenge to start with, and maybe you should think of something smaller to do first.

You first need to model and rig your character, or try to find an existing model online that's rigged with enough control over the fingers. You then need to define a "dictionary" of animations or poses for each item of vocabulary in the language. To create the poses, it is probably easiest to use motion-capture technology to record a proficient sign-language speaker.

All of the above needs to be done in a 3D modelling and animation tool. Maya is very popular for character animation.

To get natural sign-language, you'll also need to write an algorithm to understand the way places in space are used as pronouns, and a fall-back that spells things out using letters when you don't have a vocab item for them. Based on next to no knowledge of sign language, I'd guess the algorithm will end up a little more complicated than a normal text-to-speech algorithm.

You've already mentioned Unity 3D in your question, and that might be a good choice for the real-time part of the system (assuming you want to render the character in real-time). If you use that, you can write the algorithm in C#. You would import the animation/pose dictionary into your system in Unity, and have your algorithm compute the transitions from one pose or animation to the next. In Unity itself, you can define the camera and lighting layout for your model and the backdrop to draw it in front of.


Is there a way to achieve the look of a distant flock or shoal without full simulation?

One way that might work is to have boids but render each boid as a group of birds.  This way the simulation is still simple but the rendering makes it seem complex.  You might even allow a little drift per bird in the boid to make it look so obviously rigid.


I have never done this so this is just my best guess. I think you are on the track with the slope but I'm going to expand it little with some calculus. If you parameterize your curve by some variable t:

x(t) = ...

y(t) = ...

Then you can compute dx/dt and dy/dt which is how much x or y changes as you change t. This runs into some problems on a general purpose curve though. For example dx/dt might be a function of t. This means that the rate of change of x itself is changing as you move along the curve. But then you can also find dx/dt^2 (rate of change of the rate of change) and so on. This method is known as forward differencing.

Then what you can do is have an x, y starting point and draw a pixel there. Then you add the first order difference (dx/dt, dy/dt) to x and y. Then you add the second order difference to the first order difference and so on.

Here is a link I found on forward differencing:
http://www.nptel.ac.in/courses/122104018/node103.html

I haven't read it but it looks promising.

--edit--

Here's an example that was derived in my computer graphics class:
Some of the algebra can be tricky so it may or may not be correct.

Q(t) = a*t^3 + b*t^2 + c*t + k
0 < t < 1
segment size d
num segments: 1/d

Q1(t) = Q(t + d) - Q(t)
= 3*a*d*t^2 + 3*a*t*d^2 + a*d^3 + 2*b + d + b*d^2 + c*d

Q2(t) = Q1(t + d) - Q1(t)
= b*a*t*d^2 + 6*a*d^3 + 2*b*d^2

Q3(t) = Q2(t + d) - Q2(t)
= b*a*d^3      <==== no longer depends on t!

Iterate:

init variables:
Q  = Q(0)  = k
Q1 = Q1(0) = a*d^3 + b*d^2 + c*d
Q2 = Q2(0) = b*a*d^3 + 2*b*d
Q3 = Q3(0) = b*a*d^3

repeat 1/d times:
    drawLine(Q, Q + Q1)
    Q  += Q1
    Q1 += Q2
    Q2 += Q3

Q is just for one of the x or y variables. You could have a QX, QX1, ... and QY, QY1, ... and forward difference them both in the same loop. Then draw using (QX, QY) and (QX + QX1, QY + QY1). You could also extend this into as many dimensions as you like.


Why is pixel 0,0 at the top left of some formats and bottom left of others?

It comes down to history. The original interfaces for drawing stuff on the screen were for text, not images. Since the people who designed those early computers spoke languages that are read left-to-right, top-to-bottom, it made sense for the first glyph to be the top-left one. This also works conveniently with how the image was transmitted to the display. TV signals also start in the top-left, so those CRT displays also started displaying a frame with the top-left pixel. When computers added "graphics modes" to their "text modes", it made sense for the origin to stay in the same place.

This all changed with packages specifically designed for mathematical and scientific computing. Charts are usually drawn with (0,0) at the bottom-left, so scientists wanted their co-ordinate system to work that way.

This is why we have two common options. Generally for an image format, it depends on the use-case the format was originally designed to satisfy, and what kind of people worked on it. Image formats are usually designed by engineers with experience of low-level graphics implementation, so top-down is more popular, but some formats support both for flexibility.


Two things come to mind:

When generating your smaller mip map levels try to avoid using a simple 2x2 box filter because, though cheap and cheerful, they do a really poor job of removing high frequency information (that exceeds the Nyquist limit) as well as over filtering some of the lower frequency information you need to keep. (Also, as an aside, you need to perform the MIP map generation in linear space. If your source data is sRGB, you thus need to map to and from linear).  FWIW, In Williams' original paper on MIP mapping, he said he used a "box (Fourier) window" to generate the prefiltered levels, which would be a sinc function in image space.
Standard Trilinear filtering will also over- and under-filter parts of the texture. If you don't like the aliasing you may have to a) adjust the bias to increase the filtering (which will increase blurring) and/or b) try using anisotropic filtering.


"Artist Friendly Metallic Fresnel" reversible?

I wasn't really expecting that, no. The formula in the paper is not the most elegant - there's quite a few parentheses in there. In this case I think it's just a matter of shuffling the parentheses around a little in the get_k implementation - both terms should be divided by (1-r):

    float get_k(float r, float n) {
        return std::sqrt( 1.0/(1.0-r) * ( r*std::pow(n+1.0, 2) - std::pow(n-1.0, 2) ));
    }


Why is the half vector not used in diffuse BRDF Fresnel calculations?

I finally figured out a flaw in my argumentation to use the half vector for the diffuse part.
tl;dr version:
$\alpha_{hi}$ and $\alpha_{ho}$ are not equal, this assumption only works for the specular part. Therefore the energyconservation is not given.
More correct: Per definition $\alpha_{hi} = \alpha_{ho}$, but you are not allowed to use them in the equation, you need to use the microfacet normals instead of the half vectors. The microfacet normal and the half vector are however not generally equal.
long version:
The diffuse BRDF (like the specular one) is an integration over all possible microfacet normals. The generalized BRDF form is:
(1)
$f = \int_{\Omega} \frac{\rho_m * D * G * \cos(\alpha_{hi}) * \cos(\alpha_{ho})}{ \cos(\theta_i) * \cos(\theta_o)}$
where $\rho_m$ is the behaviour of light when it reaches a microfacet, $D$ is the normal distribution function, $G$ is the geometry function and the rest is normalization [PBR, p.16-25][HEI, p.61f.]
Now for the specular BRDF, the behaviour is perfect reflection. This means, only microfacets where the microfacet normal $\omega_m$ equals the half vector $\omega_h$ between light ($\omega_i$) and view ($\omega_o$) direction reflect light from the light direction to the view direction. Mathematically, this translates to a Dirac Delta function $\delta(\omega_h)$. The amount of light reflected is determined by Fresnel $F$. With accounting for integration domain changes[PBR, p.31-41], this leads to ($\rho_{m,s}$ being the specular specific reaction of microfacets for the specular part):
(2)
$\rho_{m,s} = \frac{\delta(\omega_h) * F }{4*\alpha_{hi}*\alpha_{ho}}$
Plug this into (1) and you integrate over any $\omega_m$, but the dirac delta function makes you ignore anything where $\omega_m \neq \omega_h$. This is the nice thing about those dirac delta functions, the "cancel" the integral. Therefore, you come to the well known BRDF [PBR, p.43]
(3)
$f_s = \frac{F * D * G}{4 * \cos(\theta_i) * \cos(\theta_o)}$
and here you can savely assume $\alpha_{hi} = \alpha_{ho}$. The Fresnel part makes this one side of a linear interpolation (seeing as this is the ratio of light being specularly reflected).
On the other side though, you still have an integral and you can't "cancel" it with anything. Let $\theta_{mi}$ be the angle between the microfacet normal and the light dir, $\theta_{mo}$ between the microfacet normal and the view dir (as opposed to $\alpha_{hi}$ and $\alpha_{ho}$, which specifically are defined for the half angle!).That means 2 important things:
(4)
$\theta_{mi} \neq \alpha_{hi} = \alpha_h = \alpha_{ho} \neq \theta_{mo} \forall \omega_m \neq \omega_h$
and $\rho_{m,d}$ (as the diffuse reaction of light when reaching microfacets) is depended upon Fresnel, it can only use non reflected parts, but you cannot just assume EVERY microfacet normal diffusley reflects all the light that was not specularly reflected (i.e. $(1-F(\alpha_h))$).
So the problem now is, you have one side of that linear interpolation being the analytically solvable specular BRDF without an integral. On the other side, you have the interpolation factor within the integral, and thus you would use it for any microfacet normal. This is not energy conserving anymore, if you model $\rho_{m,d}$ with a lambertian term.
If you manage to pull the $1-F$ part out of the integral, then and only then can you use the half vector for both specular and diffuse BRDFs, otherwise you need to handle it differently.
If you still want to use the half vector for the "Fresnelinterpolation", then you need to normalize.
$f = F(\alpha_h) * r_s + (1-F(\alpha_h)) * r_d * k$
With $k$ being chosen, such that
$r_d * k = 1$
Note that $r_d$ still includes an integral over all possible microfacet normals.
Using $\theta_i$ and $\theta_o$
I guess I should add a sentence about the actually used angles, because the question I originally posed was not just "why not $\alpha_h$" but also "why $\theta_i$ and $\theta_o$". So for the poeple wondering if this is correct: No. It is just an approximation.

Instead, we can modify the matte term to be a simple approximation that captures the important qualitative angular behavior[...].
[SHI, p.46]

Discussion on why this is so hard to figure out
Now [DIS, p.14] and [PBR, p.100,184] quoted [SHI] and [ASH] on this, where [ASH] uses [SHI], so it boils down to the model of the latter. And seeing as [DIS] and [PBR] are non-scientific (though pretty well thought through) publications, I can't fault them too much, but really, a better way of quoting papers or an extra explanation might have helped and saved me about 2 weeks of thinking, reading and almost starting a paper on why everybody is (supposedly) wrong.
Furthermore, neither of them really explains their diffuse approximations, [PBR, p.193] just mentions trying different functions until he saw one he liked.
Additionally, [SHI, p.46] actually quoted [SCH, p.10f.] who used the linear interpolation between $F(\alpha_h)$ and $1-F(\alpha_h)$. However, [SHI, p.46] quoted him incorrectly, they said he used $F(\theta_i)$ and $1-F(\alpha_h)$. Assuming this, they are of course right in thinking [SCH] is not energy conserving, but this lead me to believe that $F(\alpha_h)$ and $1-F(\alpha_h)$ would be. Their mistake might've come from them using $F(\theta_i)$ themselves, I can't say.
Literature

[ASH] An anisotropic phong BRDF model, in Journal of Graphics Tools Vol. 5, No. 2, Michael Ashikhmin and Peter Shirley, 2000
[SCH] An Inexpsensive BRDF Model for Physically-based Rendering, in Computer Graphics Forum Vol. 13, No. 3, Christophe Schlick, 1994
[SHI] A Practitioners' Assessment of Light Reflection Models, in The Fifth Pacific Conference on Computer Graphics and Applications, 1997. Proceedings, Peter Shirley,  Helen Hu, Brian Smits and Eric Lafortune, 1997
[DIS] Physically-Based Shading at Disney, at SIGGRAPH 2012 Course: Physically Based Shading in Film and Game Production, Brent Burley, 2012
[HEI] Understanding the Masking-Shadowing Function in Microfacet-Based BRDFs, in Journal of Computer Graphics Techniques Vol. 3, No. 2, Eric Heitz, 2014
[PBR] PBR Diffuse Lighting for GGX+Smith Microsurfaces, at GDC2017, Earl Hammon Jr., 2017


Range of integers returned by glGenBuffers?

According to the OpenGL spec, any integer other than zero can be a potential name. Zero is the only value that's guaranteed not to be an object name.
Relevant quote from the spec:

2.6.1.1    Name Spaces, Name Generation, and Object Creation
Each object type has a corresponding name space.  Names of objects are represented by unsigned integers of type uint.  The name zero is reserved by the GL; for some object types, zero names a default object of that type, and in others zero will never correspond to an actual instance of that object type.
Names of most types of objects are created by generating unused names using commands starting with Gen followed by the object type.  For example, the command GenBuffers returns one or more previously unused buffer object names.


Determining input color space primaries from spectrum data

I vaguely understand your question, so this response should be taken more of a long comment rather than an answer.

If I have an output device, for which I have a known spectrum data for each of it's primaries, I should be able to calculate the CIEXYZ of its primaries using using the integral equations together with the CIE color matching functions. I can then calculate its respective CIExyY values, which for output device are always inside the boundary if the xyY spectral locus - the chromaticity diagram.

This is correct in general but note that reference CIE spectral power distribtions are defined for a standard observer.
The term input primaries is a little vague, are you refering to the spd of the light source inside the input device or the combined result produced by the object's spectral reflectance factor (also an spd) multiplied by the spd of the light source of the input device ?
If you know the spectral reflectance factor of the object and the color matching function and the resulting trichromatic value, you should be able to express the spd of the light source as a vector equation something like:
$x_1 \begin{matrix}a_1 \\ a_2 \\ \vdots \\ a_{\lambda}\end{matrix}+x_2 \begin{matrix}a_1 \\ a_2 \\ \vdots \\ a_{\lambda}\end{matrix}+...+x_{\lambda} \begin{matrix}a_1 \\ a_2 \\ \vdots \\ a_{\lambda}\end{matrix} = \begin{matrix}b_1 \\ b_2 \\ \vdots \\ b_{\lambda}\end{matrix}$ where $x$ is from your light source spd and the others are obtained from the remaining (you can for example distribute trichromatic value uniformly to $b$ vector, and fill $a$'s with zeros for non corresponding wave lengths and use the multiplied value for the corresponding wave length), but this is more or less an educated guess rather than a tested solution.
Notice that the expression is a linear system which might help you finding a solution.


First steps towards CAD standard curve fitting

Since you have a limited set of tools you are not actually doing a classical fitting. What you have is a discrete problem. And since you are looking for a somewhat easily drawn fit, no more than twice segmented for example.

One way to approach this is to find all the points that match your curvature requirements. Then find the point x units away from point on both ends for all of these and see how well it matches. If the curvature match at the endpoint is too much off then this isn't a good candidate. If you don't find a good candidate split the problem into two. Once you have found a goodish candidate slide the result to see if relaxing the thing makes the error more symmetric.

Some things to note. Since your french curve is accelerating from one end to another you need to split beziers and b-splines at each span where the curve changes direction. Also once you've found good endpoints be sure to check that the halfway isn't too much off.

Now if you want to do a classical fitting like approach then you need to parametrize the sliding and scale of your curve. This is not likely useful since you in fact can not scale your rules at whim.

Or then you could just get a spline, you know one of those things that were used before computers and stuff, and write instructions on how to set up the spline.


Here's an example on how to do this with Python, Numpy and Matplotlib.
Image on the right has been averaged (row by row), while the left is the original.

EDITED: As suggested by @Nathan Reed, I avoided flipping colors when row average is 0. Rows with an average of 0 now get a value of 0.5 (128). The dark image encountered previously was due to values higher than 1 (255) due to scaling, that were represented as white in matplotlib's image renderer. I fixed this by setting the max value in any pixel to be 1.

import numpy as np
from matplotlib import image as mpimg
from matplotlib import pyplot as plt

def rgb2gray(rgb):
    return np.dot( rgb[...,:3], [0.299, 0.587, 0.144] )

imgPath = "C:/myImg.jpg"

im = mpimg.imread( imgPath )
gs = rgb2gray( im )

averaged = gs.copy()

for row in averaged:
    rowAvg = sum( row ) / len( row )
    if rowAvg == 0:
        row = 0.5
    else:
        # Scale each row by ratio between 128 and current row avg
        row *= 0.5 / rowAvg

    # Make sure that no pixel has a higher value than 1
    if rowAvg > 0: row[row>1] = 1

plt.subplot( 1, 2, 1 ), plt.imshow( gs,       'gray' )
plt.subplot( 1, 2, 2 ), plt.imshow( averaged, 'gray' )

plt.show()

Here's another test with a simple gradient image (left is the original):


Yes. If you're compounding operations to make a matrix, then the inverse matrix will be the compound of the inverse operations, in the reverse order. So if $C = AB$ then $C^{-1} = B^{-1}A^{-1}$

Think of it geometrically. Taking a 2D example, if you have an object at the origin, and you want to move it +2 units in X then rotate around the origin by +45 degrees. To undo this transformation, you need to first rotate by -45 degrees then translate by -2 units in X.


What is the difference in overlay and framebuffer?

As you've understood, the framebuffer is an array in memory that holds all the pixels to display on the screen. On a desktop PC, it's probably special memory on the graphics card, but in a SoC with one memory shared by GPU and CPU, it's probably a normal memory allocation that the display controller uses DMA to read from.

The display controller is a piece of hardware that reads pixels from the frame buffer and displays them on the physical screen.

Many display controllers support the use of an overlay, which is like a very simple window. Sometimes they're fixed-size, but sometimes they're masked off. In this case, then there might be a secondary framebuffer that covers the whole screen. When the display controller reads a pixel of a particular colour from the primary framebuffer, then instead of displaying that pixel, it substitutes the corresponding pixel from the secondary framebuffer. It's like the chroma key or green screen technique used in movie effects and weather forecasts.

That's one particular configuration: sometimes the secondary framebuffer is much smaller than the primary framebuffer, and a particular register in the display controller controls the dimensions and offset.

The overlay technique is commonly used for displaying video streams. The frames of video might be coming from camera hardware or from video decoder hardware. Using an overlay means that this hardware and the GPU that's producing the rest of the screen (such as camera or playback GUI) aren't trying to access the same memory at once. The overlay might also be in a different pixel format to the primary framebuffer.

The overlay technique only lets you do this simple substitution, though (and maybe some scaling), not anything complicated. You can't make the frame of video spin around and shrink to an icon when you're transitioning between different applications. You can't alpha-blend the video with the primary framebuffer. Also, the number of overlays is limited by the hardware: usually one, but some controllers support two.

Composition in this context refers to something the window manager does. It takes the frames from each application on the screen (the system GUI is also an application), and produces the final frame. On a smartphone, this usually means just taking the current foreground app and the system GUI (notification bar and navigation bar) and drawing them next to each other. But when there are transitions between apps, or if you use the "recent tasks" button, the situation is more complicated. The compositor also has to handle choreographing applications so the screen gets updated at 60 Hz even if applications are drawing at different rates.

Surface Flinger is Android's compositor. It uses OpenGL ES to do the things described in the previous paragraph. It's also in charge of creating a framebuffer for each application to render into. (These framebuffers show up as textures inside Surface Flinger, using EGLImage.)

Android also detects when there are simple cases that the display controller on the phone can handle as an overlay, so that it can switch to the faster, more energy-efficient path of using the overlay instead of using Surface Flinger's full GLES-based composition.


You are correct, when they are talking about taking the inverse-transpose they are talking about the 3x3 part of the affine transformation leaving the translation since it doesn't affect the normal vector.

Check : Normal / Transforming Normals | Wikipedia

About how or why is it the inverse transpose, a simple explanation, that is also given in the book "Essential Mathematics for Games" is

Suppose we have a Point $P$ and a normal vector $n$ both represented by column matrix. Then we know that
$$
n^T P = 0
$$
This is the same as the dot product.
Now if we apply a transformation matrix $M$ to point $P$, we'll have to apply some sort of transformation matrix $Q$ to $n$ also.
$$
\begin{eqnarray}
(Q n)^T M P & = & 0 \\
n^T Q^T M P & = & 0
\end{eqnarray}
$$

One solution is
$$
\begin{eqnarray}
Q^T M & = & I \\
Q & = & {M^{-1}}^T
\end{eqnarray}
$$
Hence the inverse transpose. This stands for any sort of transformation matrix $M$ be it scaling, rotation etc. Also for pure rotation matrix, since they are orthogonal, the matrix transforming the normals is the same as that of the vertices. as ${M^T}^T = M$


That completely depends on how you are computing the shading. If you are then just linearly interpolating the shaded colours across the triangle, i.e. Gouraud shading then, clearly, the answer is "no".

However, if you are doing per-pixel shading by, say, interpolating normals and light directions, then you can easily get a brighter area away from the vertices.


How to create a patterned object with variable pattern density in real-time?

In order to ensure that the pattern shapes are always either wholly present or absent, never cut off, it's necessary to ensure that the same p value is used for all texels within the shape. In your example of circles, all the texels in a given circle need to agree on p.

I assume that you have some way of evaluating p at a given point on the surface (whether it is looked up from a texture or calculated from some function). Then one way to ensure a group of texels all get the same p value is to ensure they all look it up from the same point.

The UVs of this evaluation point could be stored in extra channels of the pattern texture. For instance, you could have the red and green channels store the UV coordinates at which to evaluate p, the blue channel store the threshold at which to turn on that pattern element, and the alpha store the antialiased gray level of the pattern to display. The UV+threshold data could also be in a separate, secondary texture if desired.

To generate this UV+threshold texture, starting from an input pattern texture, you could programmatically find connected components (e.g. by searching for black pixels and flood-filling). Set the evaluation point for all texels in each component to the UV of the component's center, and generate a random threshold for it. Then, when rendering, use a pixel shader that first samples this texture, then looks up p at the given evaluation point and compares it to the given threshold.

That way, each pattern shape will see a uniform p value and threshold, and will either turn on or turn off fully. As p increases, more of the shapes will pass their threshold and appear, giving the impression of a continuously varying density.


What is the purpose of the projected solid angle $dA^\perp$ term in the definition of Radiance?

Your main idea is more or less correct. The cosine hidden in the projected area measure $dA^\perp = dA\cos(θ)$ compensates the weakening of irradiance due to incident angle (the Lambert's cosine law). This makes radiance independent from the incident angle. My guess is that the main motivation was to make it more practical to work with.

The cosine in the rendering equation comes from the definition of BRDF:

$$
f_{r}\left(\omega_{i}\rightarrow\omega_{o}\right) =\frac{\mathrm{d}L_{o}\left(\omega_{o}\right)}{\mathrm{d}E\left(\omega_{i}\right)} =\frac{\mathrm{d}L_{o}\left(\omega_{o}\right)}{L_{i}\left(\omega_{i}\right)\mathrm{d}\sigma^{\bot}\left(\omega_{i}\right)} =\frac{\mathrm{d}L_{o}\left(\omega_{o}\right)}{L_{i}\left(\omega_{i}\right)\cos\theta_{i}\mathrm{d}\omega_{i}}
$$

Which can be rewritten as

$$
\mathrm{d}L_{o}\left(\omega_{o}\right)
=f_{r}\left(\omega_{i}\rightarrow\omega_{o}\right) L_{i}\left(\omega_{i}\right) \cos\theta_{i} \mathrm{d}\omega_{i}
$$

Which can be integrated over the hemisphere the get the radiance reflected in a given direction $\omega_o$

$$
\int_\Omega f_{r}\left(\omega_{i}\rightarrow\omega_{o}\right) L_{i}\left(\omega_{i}\right) \cos\theta_{i} \mathrm{d}\omega_{i}
$$

Voila, the rendering equation!

Conclusion: Althought both cosines come from the same fundamental priciple, they serve different purposes.


Reading thesis on cone tracing, did the author make a mistake?

It’s kind of inaccurately stated—by comparing the SDF with a linearly increasing radius, the shape that’s being traced out is a cone with a hemisphere on the end, something like this:

At any point along the horizontal center line, if the distance to the nearest surface is less than the current test radius, the cone-plus-hemisphere has intersected that surface.


How is this normals map supposed to work?

Yeah, that doesn’t look like any bump, height, or normal map I’ve ever seen—as you’ve identified, there’s only information about the surface contour along a single axis. If anything, it looks like it’s meant to be overlaid on a texture as a cheap form of fake bump-mapping in an era where it was too expensive to do it for real.


BSP is a classic for computational geometry tasks involving polygons. However, polygonal meshes are subject to a dismaying list of pathologies such as degenerate polygons, inconsistent winding order, T-junctions, coincident vertices, cracks or holes, self-intersecting geometry, loss of coplanarity or collinearity due to roundoff error, and other such things. Making computational geometry robust on arbitrary polygon meshes is Quite Difficult™.

It worked in Doom/Quake/Half-Life days because the base level geometry (made of brushes and constructed in a level editor, as opposed to a 3D modeling tool), was relatively simple, mostly axis-aligned, and all vertices were snapped to grids. More recently, the trend seems to be for level design seems to be done by creating mesh pieces in 3D modeling tools, then sticking together a bunch of instances of them to form a level. This kind of construction is a lot less friendly to BSP-type algorithms—especially as the geometric complexity rises.

An alternative approach for connectivity questions is voxelization. In short, you voxelize all your level geometry at some reasonably small resolution, like 10–30 cm per voxel or so. The voxelization wipes away any geometric errors smaller than the voxel size, and it gets rid of all those annoying pathologies mentioned earlier. You can use an octree or brickmap etc. to avoid voxelizing empty space.

Once you have the voxel representation of the level, you can then do all sorts of connectivity queries on it very easily because of the regular structure of the voxels. For instance, determining if a level is watertight or finding connected-components at the voxel level is basically a flood-fill. These kinds of algorithms can also be done hierarchically using the octree etc. to avoid the expense of a global flood-fill over a huge number of voxels.

For more reading, there was a 2011 SIGGRAPH talk Making Game Worlds From Polygon Soup, from some engineers at Bungie who used voxelization techniques on Halo Reach levels to build nav meshes, precompute visibility cells and portals, and so on.


Performance difference in OpenGL compute shader vs Vulkan Compute Shader vs Cuda/OpenCL and others

In general, you should not see significant performance differences running identical compute shaders via one API vs. another; in the end they’re running the same instructions on the same hardware. It’s possible for vendor-provided toolkits like CUDA or MetalPerformanceShaders to have more efficient implementations of a given algorithm on that vendor’s hardware than a more generic version of the algorithm, because they’ve been designed and tuned for the strengths of that hardware, but there’s nothing in principle that would prevent you from developing the same efficiencies on your own with enough optimization work.
Long story short: work with whichever API you find easiest to use, and invest some time in learning how to profile and tune your code for the hardware you plan to run it on.


Rendering a volume that might be completely clipped in OpenGL

First, regarding the specific problem of bits of the geometry being lost to the near and far planes, this can be solved by using depth clamping instead of depth clipping. This disables clipping against the near and far planes, in favor of clamping the output depth values to [0, 1]. (Geometry behind the camera will still be clipped though.) Given this, instead of a fullscreen quad you could render the light volume with inverted culling, depth testing inverted (to cull pixels behind the volume), and use depth clamping to prevent losing parts of the volume to the far clip plane.
(Depth clamping is also handy for shadow maps, as it lets you contract the shadow map depth bounds to bracket the view frustum, without losing geometry between the view frustum and the light source.)
In a broader sense, though, this doesn't really solve the problem of shading pixels within a given convex volume. The problem is that you need two depth tests: front of volume < pixel depth < back of volume. The approaches discussed so far can only do one of these tests at a time. You can switch which one you're doing by swapping culling and depth-testing modes, but you can't do both at once, which leaves performance on the table.
One approach to address this is to use the stencil buffer in concert with depth testing. Basically this works by testing scene depth against the front of the light volume first, storing that to the stencil buffer, then doing a second pass that tests scene depth against the back of the light volume, and combining that with the stencil result from the first pass. This has the advantage of getting tight culling (no pixels shaded outside the volume), but you need to draw each light volume twice, plus making a lot of state changes to switch back and forth, which can be inefficient for both CPU and GPU (though you can batch up to 8 lights together using 1 stencil bit per light).
Finally, using EXT_depth_bounds_test, if available, can be a good solution. This enables a form of depth test that checks whether the pixel already in the framebuffer (not the geometry being rasterized) is within a certain range. With this, you set the depth bounds to the min/max depth of your light volume, then draw the geometry with inverted culling, no depth test, and depth clamping enabled. This will shade all pixels within a sort of prism aligned with the view frustum, that bounds the actual volume reasonably tightly in most cases (though long narrow spotlights can be bad), and it does it in only one pass. However, this extension isn't universally available; it seems to be found on current NVIDIA and AMD GPUs, but not Intel ones (see OpenGL Hardware Database).
All of this difficulty is one reason that most game engines since the early 2010s have switched to compute-shader tiled culling instead of using the rasterizer to decide which lights to shade at which pixel.


What does it mean by a Constraint-based Graphics System?

If you have a geometric drawing with measurements you can solve what the shape has to be. This is valuable for example in engineering as it allows you specify the requirements and the computer can then solve the constrained drawing via a solver.

Image 1: Constraint solver in action, red constraints are fixed while blue ones are free to change.

There are several ways how the solver might work, it could be a numeric nonlinear based on gradient descent. Or it can be fully algebraic. Usually its a gradient descent solver as this is easier to implement, and possibly faster.


How to handle Half edge boundary edge iteration from vertex?

It depends a little on your actual data structure and how it even encodes boundary edges. What I find more useful than representing the boundary with a null half edge pointer, and thus having this situation of a half edge without an opposite and thus a hard stop for any such iteration, is instead encoding the boundary with a full half edge pair too, but with one of the half edges having a null face pointer.

So the boundary edge actually does have an opposite (or pair pointer) and that opposite is fully integrated into the pointer structure, complete with next pointer and everything. Just that its face pointer in null, thus denoting an empty face or hole. So basically every hole is represented by a null face with half edges going around it.

In addition to being able to iterate around vertices regardless of the starting point, this also has the advantage that you can easily iterate around boundary curves. And you can even have more than one hole at a vertex (although, that can still be problematic in other situations). Of course you might still have to handle the boundary half edges specially in some situations, especially when you're using the face pointers, but you won't get around that anyway if your mesh can have holes.

If that is too much of a hassle to restructure your data and algorithms this way, though, maybe you can instead adjust your vertex starting edge pointers to always point to the boundary edge if there is one. You'd of course have to make sure that stays consistent, but if you can assume that as a precondition, you can just start iterating from there. And you can also check immediately if the vertex is at a boundary without having to iterate.


With modern fillrates and deferred rendering, is occlussion culling still relevant?

Yes, occlusion culling is still worth it.

At minimum, a draw call that you skipped due to culling is a draw call that doesn't have to run the vertex shader. Triangle count goes up as quickly as GPUs start supporting more triangles, because why not? With unified architectures, vertex shaders use the exact same hardware that pixel shaders do, so every vertex that you skip because of culling is more compute time for the stuff that you can see. Not to mention all the other stuff you're skipping (CPU draw call processing, and throwing the tris far enough through the pipeline that the rasterizer realizes that it doesn't need to shade them).

There was a great presentation from two Ubisoft studios at SIGGRAPH 2015 about GPU-driven rendering pipelines. On the surface it's about some of the things you mentioned: batching and instancing, reducing draw call counts. But one of the major advantages they get out of a GPU-driven pipeline is incredibly fine-grained occlusion culling: better culling than you would normally see at the draw-call level. It's all in the service of asymptotically approaching the goal: processing only what you can see, which means that what you can see looks better.

(Also: consider console, mobile, VR, and desktop-without-the-latest-and-greatest-GPU-that-money-can-buy. Even if all your tris disappear into the gaping maw of your top-of-the-line GPU, you may not be the primary target.)


A key rule of thumb for high-performance code in general, and graphics in particular, is to batch large amounts of work together rather than doing it in small chunks. In your case, rather than sending one quad's worth of data at a time and drawing one quad at a time, it will be far more efficient to send many quads' data in a large batch, and draw many quads together in a single draw call.

A good way to accomplish both is instancing. You would have a 4-point vertex buffer for the corners of a quad, and a second vertex buffer for the values that are per-quad (what you're putting in your uniform buffer now). This second buffer would be large enough to hold the data for all the quads at once, not just one quad. To populate the vertex buffer, you can map the whole thing, write all the data, and unmap. Then do a single instanced draw call to render all the quads at once.

However, if instancing can't be used for some reason (for instance if each quad needs a different texture, and it's not possible or desirable to put them together in an atlas), you can still upload all the data in one batch. Create a uniform buffer large enough to hold an array of all the quads' data; map/write/unmap it all in one big batch as before; then before each draw call, use glBindBufferRange to select one quad's data from that large buffer.

Batching can also be used when you don't know the number of quads in advance. Just pick a "reasonably large" batch size (say, 1024 quads) and size your buffers for that number. Accumulate quads into the buffer until you reach the size limit, then draw them all, and start over (using the GL_MAP_INVALIDATE_BUFFER_BIT flag with glMapBufferRange to get a fresh copy of the buffer). You'll also need to do a partial draw at the end of this process to handle any left-over quads that didn't reach the size limit.


You can ray trace the distance to the second surface. This may be conceptually easiest, but not necessarily fastest method*.

But there is a neat trick, you can multi pass render a depth map to the water surface from the camera. The distance in water is now pixel depth minus the depth map depth. This does not work in all situations such as when you exit water and re-enter later. But should work in many cases, like the one depicted. You can even use same technique for Boolean operations.

Image 1: Render depth map, consult depth map when shading the bottom of your pond.

* It might be in certain cases.


Use big frame buffer to control a small display

As stated, the question is a bit generic. It all depends on what part you want to display in the 512x512 display. If you have a 1024x1024 frame buffer from some source and only want to display 1/4 of the information, by all means copy the first 512 elements from the first 512 lines. If you want to support panning, you'll start at a different index in a different line. If you want to support scaling (with or without filter), you'll use a bigger or smaller set of source pixels.

It also depends on the type of the buffer. If it's just raw bytes, your suggested approach is basically the only way to go, but if it's a DirectX/OpenGL texture, or part of some other graphics API (Windows Bitmap, graphics engine, etc), there are usually specialized approaches to get a rectangular subset of a buffer.