How to count DPI of an image (challenge)?

They are not "very similar images". They have quite different aspect ratios. The first one has a 5:6 aspect ratio, while the other has a 3:4 ratio.

If you try to print a 5:6 image at 8x10, what you find is that if the width is 8, then a 5:6 image would have a height of 9.6, which is less than 10. So that means the 5:6 image can fit into the 8x10 region with its full width; some of the height will go unused.

However, a 3:4 aspect ratio image at 8x10 doesn't do that. If the width is 8, then the 3:4 aspect ratio would require a height of 10.6. That would exceed the maximum available height, so the width cannot be full width. Instead, it uses the full height of 10, and the width used will only be 7.5.

You will find that this is the case for all of the ones where you noted such a difference.

The "DPI" its computing is essentially the number of pixels in the dimension that isn't the maximum. For the 3:4 image at 8x10, it takes the image width (1000) and divides by the area width (8). For the 5:6 image at 8x10, it takes the image height (1200) and divided by the area height (10).

This number only makes sense if we assume that the image is being scaled independently in width and height to fit the page. That is, the aspect ratio of the image is not being preserved when printed. So a 5:6 image is being transformed into a 4:5 aspect ratio image when printed at 8x10.

Since each dimension is being scaled differently, each dimension has its own DPI. The lowest DPI will be for the dimension being stretched the most. And that's what this formula seems to be computing.

Of course... who cares? Stretching images creates obvious visual distortion, and should pretty much never be done when printing something you actually want to have a paper copy of. So I would declare this computation algorithm to be bogus and move to something that actually makes sense with a reasonable printing methodology.


How does notch's new graphics engine work?

Notch's engine most likely works using volume raymarching in a volume field. This means that you shoot rays that move a certain distance and check whether they are inside and object or not. Once they are, they return the position of the colission and some other data.

You can either advance rays by a set amount per step until you hit something or refine the final collision position by doing a binary search along the last walked ray segment once you hit something. Both of these aproaches have the problem that they can overshoot, missing small geometry, or take a large amount of steps to traverse empty space where there is no geometry to hit.

Binary search can add precision and reduce overshoots somewhat but comes at an extra runtime cost for doing a binary search per ray.

Signed distance fields are essentially 3d arrays  tell you how far away from any surface you are. This allows you to do raymarching with ray step sizes equal to that number and being sure that you wont overshoot, as well as stepping through large empty spaces quite quickly. This greatly enhances performance and reduces overshoots from a regular step size or binary search based approach.

This last technique trades off runtime speed for precompute time and extra memory. So it is not always adequate for rendering exteriors or large scenes. Its memory usage an runtime speed can be further improved by using a hierachical data structure that gets re built every so often with more detail and data density near the camera and less further away from it.

EDIT: Oh it seems i misread density for distance

I really have no idea what a signed density field is. I've never heardthe term before. A quick goolge search throws results that talk about signed distance fields. I would guess it was either a mistake to write that, some obscure tech or something that Notch made up himself.


Why do red, green, and blue make up all the colors?

Let's reminds ourselves what light is.

Radio waves, micro waves, X rays and gamma rays are all electromagnetic radiation and they only differ by their frequency. It just so happens that the human eye is able to detect electromagnetic radiation between ~400nm and ~800nm, which we perceive as light. The 400nm end is perceived as violet and the 800nm end is perceived as red, with the colors of the rainbow in between.

A ray of light can be a mix of any of those frequencies, and when light interacts with matter, some frequencies are absorbed while other might not: this is what we perceive as the colors of objects around us. Unlike the ear though, which is able to distinguish between a lot of sound frequencies (we can identify individual notes, voices and instruments when listening to a song), the eye is not able to distinguish every single frequency. It can generally only detect four ranges of frequencies (there are exceptions like daltonism or mutations).

This happens in the retina, where there are several kinds of photo-receptors. A first kind, called "rods", detects most frequencies of the visible light, without being able to tell them apart. They are responsible for our perception of brightness.

A second kind of photo-receptors, called "cones", exists in three specializations. They detect a narrower range of frequencies, and some of them are more sensitive to the frequencies around red, some to the frequencies around green, and the last ones to the frequencies around blue.

Because they detect a range of frequencies, they cannot tell the difference between two frequencies within that range, and they cannot tell the difference between a monochromatic light and a mix of frequencies within that range either. The visual system only has the inputs from those three detectors and reconstruct a perception of color with them.

For this reason, the eye cannot tell the difference between a white light made of all the frequencies of the visible light, and the simple mix of only red green and blue lights. Thus, with only three colors, we can reconstruct most colors we can see.

By the way, rods are a lot more sensitive than cones, and that's why we don't perceive colors in the night.


Alan Wolfe is pretty spot on, but I will sum up any way :)

render the back-faces of your "unit"-sized-box, [-1;1]
sample the zbuffer and transform into light-local coordinates (see our slides for a fast way to do that).
early-out of the pixelshader if outside of the box, i.e. if any coordinate in the local-position is outside of -1;1.
then do the dot-product between the normal and the lightdir, in whatever space is convenient (you can extract the worldspace-lightdir from the object-to-world matrix).
projecting a texture is easy, the UV-coordinates are simply the localspace xy (moved to [0;1])
using a falloff texture is eays, the coordinate is simply the localspace z (moved to [0;1])

In an actual game, you of course want to use some sort of acceleration to discard early; we used old-school stencil culling (and should have used depthbounds), but likely tiled culling, clustered culling or similar is better.

You could use zgreater testing to discard pixels where background is entirely behind the light, but iirc on most modern GPUs this will not actually be an advantage, as there will be no early-discard due to the hierarchical zbuffer being primed in the direction of zless.


Yes, in the simple case, primary rays conform to the frustum. If you're doing depth-of-field optically, then the rays don't quite conform to the frustum, because you need to vary the ray origins slightly as well as the directions. How exactly the variation works depends on how closely you're simulating the lens system and aperture. You can picture it as sampling from several frustums, one for each pinhole camera you're averaging.

I've never done full Monte Carlo for ray sampling: generating the rays according to a uniform distribution is bad at distributing them usefully around the image. Popular options include:

You can generate the ray directions according to a space-filling curve on the image plane, and then adaptively supersample once you have enough samples to estimate contrast.
Start with a regular grid that goes through the centre of each pixel, but randomly jitter the directions within each pixel. This was popular for many years but (done naively) it's still slightly biased because you're too likely to sample the corners of pixels.
Start with a uniform random sampling but use Poisson discs to avoid putting rays too close together. This is closer to a pure random sampling, and it has the advantage you can keep using the technique as you refine/supersample the image by decreasing the disc radius over time.


Average point on sphere between 3 other points (spherical triangle)

If i read you right, you have a triangular patch which is on the surface of a sphere - so the triangle isn't really a true triangle in that it isn't flat, but instead is just made up of 3 points on a sphere connected by lines across the spheres surface.

Also if I understand you correctly, you have a point on this triangle that you want to get the normal at.

If all that is right, the way to get the normal is to subject subtract the origin from your point on the triangle (since it is also a point on the sphere) and normalize it.

The normal at any point on a sphere is parallel to the point from the center of the sphere to that point on the surface.


A pseudocode to parallelize a path tracer?

An easy way to parallelize a path tracer is to have different threads (or machines!) work on different parts of the image.

For instance, you could break the image into a 20x20 grid and have each thread grab a tile, render it, and try to grab another tile.

A way I like to divy out this work is to use an atomic integer. Each thread atomically increments the integer and uses the value as an index into the work to do. They repeat this process until the atomic integer goes out of bounds.


glOrtho() in fixed function pipeline - Unable to see change in z-axis

This projection is a 2d projection, with the Z axis pointing into your screen. When both vertices with the same X&Y are projected to screen space they will occupy the same screen coordinate so your line will either be 1 pixel or invisible.

If you are expecting a difference in screen position from those 2 coordinates then you need a perspective projection.


Calculate Normals of Boolean Operation for Ray Tracer

My code is setup to calculate the intersection points of each of the spheres with any given ray and spit out the correct points to be rendered to the screen based on the type of boolean operation being performed (Union, Difference or Intersection).

Then you need to do the exact same thing with the normals. Indeed, you would typically do this operation with all of the appropriate parametric values for the various leaf surfaces.

However, you need to take into account how the operations affect the meaning of the intersections. With positions, an intersection is used to determine if you're inside an object or outside of it. An OR operation (union) makes any intersection of the two objects considered "inside", with "outside" only happening if you're outside of all of them. An AND operation (intersection) only makes the composite object "inside" if you're inside all of the AND'd objects.

A negation reverses the meaning of inside and outside for the object. So an AND with a negation (difference) means that the only part that is inside of the composite object is the part of the first object which is not also inside of the second.

Normals use the same rules as positions, with one exception. When used with a difference operation, if the ray enters the negated object (and thus is still outside of the composite), then enters the primary object (but is still outside of the composite because it's still inside of the negated one), and then leaves the negated object, that intersection represents a visible point.

Except that the normal is backwards, since you're using the inside of the negative surface to define the surface of the composite object.

When you negate a surface, you invert the meaning of its normals. So when you do a difference operation, you have to negate the normals of any intersections with the negative surface.


Well, for the first octant you can either step EAST or NORTH-EAST. Depending on the distance to the actual line you choose the appropriate. In many integer implementations, this is done with regard to the sign of D.


Rasterization: How does hardware disambiguate identical Z values at silhouette edges?

If you are taking about this occurring within a single draw call for a single object then you are talking about rasterization not Z fighting.  So the real question is, "how are two triangles rasterized that are right next to each other". And the answer to that question boils down to rasterization rules. Which must be enforced, on GPU's that happens in hardware, for your software rasterizer you need to pick a rule set, then enforce it in code. Generically a rasterizer can leave no holes, and each pixel is only drawn once. You may want to always add colors when drawing your triangles, start with a color of zero and just add new colors drawn to that pixel, this will make your overdraw stand out like a sore thumb.
The most widely know rule set for handling this is the "top left rule" which states: The center of every pixel must lie completely inside the triangle, (you are computing pixel centers right?) or it center lies exactly on a triangle edge or on multiple edges in the case of corners, and a left edge is a non-horizontal edge that is on the left side of the triangle.
This last bit is directly from Wikipedia.


Difference betwen Rendering Equation, Lighting model, Ray Tracing, Global Illumination and Shadows?

The rendering equation aims to describe what the light distribution for a specific scene is, under several assumptions. The most important assumption is that we are working in a geometrical optics framework - so we do not consider the wave properties of light - meaning no diffraction for example, we also do not consider quantum effects, such as phosphorescence. If the rendering equation is not in its spectral form, then there's also no dispersion.

There are additional constraints on top of what we have for geometrical optics, like light travels instantaneously, light rays traveling in straight paths from surface to surface (no spatially continuously varying indices of refraction), no polarization, etc. Many of the constraints can be removed in more general formulations (which are also available), but usually that incurs heavier computations.

So the rendering equation serves as an approximation to how light works in the real world, but since we want to model only a subset of light effects, various simplification are made in order to make the problem easier to solve.

Let us consider the commonly shown formulation:

The above images are linked from: Raytracing - Rendering Equation Insight

I believe these images are fairly self-explanatory. The function $f_r$ referred to as the BRDF (or more generally the BSDF) describes the interaction of materials with light. Often in real-time graphics this is referred to as the illumination or reflectance model - one such example is the Blinn–Phong reflection model, there is the Cook-Torrance model too, and several others. All of those are brdfs/bsdfs, or constituent parts of brdfs/bsdfs.

Flat, Gouraud, and Phong shading (or more correctly Gouraud and Phong interpolation) is really referring to how the normals of a model are treated (interpolated).

Flat shading simply uses the actual normals of an object. If we could render objects made up of infinitely many triangles, even flat shading would be ideal. However, as for most things in graphics, efficiency is key, so we cannot use infinitely may triangles. For that reason people have chosen to modify the surface normals of objects, in order to get a smoother appearance - as if they used a lot more triangles. How is this achieved? Well, one can find per-vertex normals, that are a weighted sum of the face normals, so that a smooth like appearance is achieved. For example by using approaches such as the one described in the following publication: Weights for Computing Vertex Normals from Facet Normals.

Gouraud shading (Gouraud interpolation), refers to computing the illumination per vertex, using these normals, and then interpolating the resulting color over the triangle - this explains why it has discontinuities at edges and vertices.

Phong shading (Phong interpolation) interpolates the normals over the triangle (by using barycentric coordinates) and then computes the shading using those per-pixel which results in an overall smoother appearance. Note that discontinuities at the outline of the object can still be visible - this modifies only the shading of the object, and not its actual geometry.

One can go further and use bump mapping, derivative mapping, or normal mapping, in order to further enrich the shading information over an otherwise flat surface, by modifying the normals.

All of those normal modifications (Gouraud and Phong interpolation; bump, derivative, and normal mapping) produce normals which are commonly referred to as shading normals. Note that those violate energy conservation principles in general, and may cause various artifacts. But obviously this is the trade-off for performance. So all of those techniques fall under the umbrella of normals modification and are not illumination models in their own right (but those normals are used in the brdf and the rendering equation to compute shading - where the shading part in the terms goes - I still believe interpolating is a better naming).

To understand the shadow conundrum, let's look at the solution of the rendering equation. The rendering equation in mathematics is known as a Fredholm integral equation of the second kind, under some assumptions, its solution is given through the sum of increasingly dimensional integrals: Liouville–Neumann series. I will avoid writing out the integrals explicitly, since it will get ugly very quickly, you can find the expansion in Veach's thesis however. I will just use the operator formulation of the rendering equation. Let $L = L_o$, and $T$ be that integral from the images. Then the rendering equation can be written concisely as:

$$L = L_e + L_r = L_e + TL$$
$$L-TL = L_e$$
$$(I-T)L = L_e$$
$$L = (I-T)^{-1}L_e = \sum_{k=0}^{\infty}T^kL_e$$

The last equality holds due to the Liouville-Neumann expansion that I talked about. This is a sum of increasingly dimensional integrals similar to the one you had in the rendering equation (with a few additions) - usually this is also done with respect to the area formulation of the rendering equation (the images here provide the solid angle formulation). Informally $T^k$ means that there were $k$ bounces before reaching the light source, so it's a sum of the energy coming from paths starting at the eye and ending at a light source, of length $1, 2, 3, ..., \infty$. Let's look at the area formulation of the rendering equation:

$$L(\pmb{x}_0\leftarrow\pmb{x}_1) = L_e(\pmb{x}_0\leftarrow\pmb{x}_1) + \\ \int_{\mathcal{M}}f_r(\pmb{x}_0\leftarrow\pmb{x}_1\leftarrow\pmb{x}_2)L(\pmb{x}_1\leftarrow\pmb{x}_2)\frac{\cos\theta_{\pmb{x}_1}\cos\theta_{\pmb{x}_2}}{\|\pmb{x}_2-\pmb{x}_1\|^2_2}V(\pmb{x}_1,\pmb{x}_2)\,d\pmb{x}_2$$

Here $\mathcal{M}$ is the set of all surface points of the scene (including lights), $L(\pmb{x}_0\leftarrow\pmb{x}_1)$ gives you the radiance traveling from surface point $\pmb{x}_1$ to $\pmb{x}_0$, $L_e(\pmb{x}_0\leftarrow\pmb{x}_1)$ gives you the emission from $\pmb{x}_1$ towards $\pmb{x}_0$. To relate the brds to the previous formulation, one can set: $\omega_o = \frac{\pmb{x}_0-\pmb{x}_1}{\|\pmb{x}_0-\pmb{x}_1\|}$, $\omega_i = \frac{\pmb{x}_2-\pmb{x}_1}{\|\pmb{x}_2-\pmb{x}_1\|}$, and $\pmb{x} = \pmb{x}_1$. Furthermore, $\cos\theta_{\pmb{x}_1} = \omega_i \cdot \pmb{n}$, where $\pmb{n}$ is the surface normal at $\pmb{x}_1$, similarly $\cos\theta_{\pmb{x}_2} = -\omega_i \cdot \pmb{n}_{\pmb{x}_2}$, where $\pmb{n}_{\pmb{x}_2}$ is the surface normal at $\pmb{x}_2$. The squared Euclidean distance in the denominator is due to the inverse-square law (it's implicitly encoded in the solid angle formulation). Finally, $V(\pmb{x}_1,\pmb{x}_2)$ is the visibility function - it is equal to $1$ if there is nothing between $\pmb{x}_1$ and $\pmb{x}_2$ (no occlusion), and $0$ otherwise (it is also implicit in the solid angle formulation) - this is the function that encodes shadows. Approximations, that do not produce shadows, have simply thrown away or modified that visibility function (one such modification is replacing $V$ with the ambient occlusion or with information from a shadow map). This is done for efficiency reasons once again, as instead you would have to trace a ray from $\pmb{x}_1$ to $\pmb{x}_2$ and intersect against the scene to check for occlusion.

Let us consider the simplifications that are usually made in real-time graphics. Most implementations, simply cut the Neumann sum to the 2nd term:

$$L = L_e + TL_e + T^2L_e + ... \approx L_e + TL_e$$

So anything beyond direct illumination and emission is thrown away. This has important implications - such as: no indirect illumination or scattering effects. Let's consider what this amounts to:

$$L = L_e + TL_e$$

$$L(\pmb{x}_0\leftarrow\pmb{x}_1) = L_e(\pmb{x}_0\leftarrow\pmb{x}_1) + \\ \int_{\mathcal{M}}f_r(\pmb{x}_0\leftarrow\pmb{x}_1\leftarrow\pmb{x}_2)L_e(\pmb{x}_1\leftarrow\pmb{x}_2)\frac{\cos\theta_{\pmb{x}_1}\cos\theta_{\pmb{x}_2}}{\|\pmb{x}_2-\pmb{x}_1\|^2_2}V(\pmb{x}_1,\pmb{x}_2)\,d\pmb{x}_2$$

There is one small difference compared to the area formulation, and that is the fact that we have $L_e$ in the integral and not $L$, so it is not a recursive integral anymore. It is still an integral however, which implies an infinite sum - this is currently not very fast to compute, unless you have specialized hardware like RTX, especially for more complex scenes. Note that the integral is over all surface points emitting light, so you would in general need to sum up the light coming from area lights, skyboxes etc.

So the next simplification that is usually done, is using point lights. Point lights have the computationally efficient property, that they are represented through Dirac delta functions. A Dirac delta function, essentially allows you to get rid of the integral - the light comes only from a single direction. Then your integral turns into a finite sum over all point lights in the scene (a similar argument may be made for directional or spot lights, note that the light cosine term disappears, since informally there's no normal to speak of):

$$L(\pmb{x}_0\leftarrow\pmb{x}_1) = L_e(\pmb{x}_0\leftarrow\pmb{x}_1) + \\ \sum_{k=1}^{N}f_r(\pmb{x}_0\leftarrow\pmb{x}_1\leftarrow\pmb{y}_k)L_k(\pmb{x}_1\leftarrow\pmb{y}_k)\frac{\cos\theta_{\pmb{x}_1}}{\|\pmb{y}_k-\pmb{x}_1\|^2_2}V(\pmb{x}_1,\pmb{y}_k)$$

Where $L_e$ is generally constant, $L_k$ is the radiance of light source $k$ and $\pmb{y}_k$ is the position of light source $k$. If your material is diffuse then $f_r$  and the radiance of the point light do not change with directions, then $L_i$ and $f_r$ are also constant so you get the (possibly) familiar expression:

$$L = L_e + \sum_{k=1}^{N}f_rL_k\cos\theta_k V(\pmb{x}_1,\pmb{y}_k)$$
$$color = emission + \sum_{k=1}^{N}ObjectColor * LightColor * \cos\theta_k * VisibilityFromLight\_k$$

The only thing that is usually not there is the $V$ term, since it requires tracing rays through the scene, which standard rasterization algorithms don't do. So it's either set to $1$, or replaced with information from a shadow map (for each summand the shadow map from this light's perspective ought to be used for semi-correct results). Often times the remaining terms that were cut off $T^2L_e + T^3L_e + ... + T^{\infty}L_e$ are substituted with a constant ambient light term or with an ambient occlusion term.

Path tracing usually solves the rendering equation without any of the above simplifications (but requires a lot more computational power), that is the reason why images produced by it look so realistic.

Whole books may be written on this matter. But I hope I managed to clarify at least some things regarding Gouraud, Phong interpolation, shadows, and how all of this ties into the rendering equation.


Is there an algorithm to bold an outline font?

The best way to do proper outlines, is unfortunately, also the hardest. It involves calculating an offset curve, usually from the medial axis or straight skeletons, which are non-trivial to calculate. Once you have those, you can calculate the distance of any point from the input object and decide whether to draw the outline or bolding, or not.

A simpler way to do it, which doesn't look quite as nice, is to use a MinMax filter. This is a sliding 2D box filter that calculates either the minimum or maximum value within the box at each input pixel. If you have black text on a white background, you can use the min filter to generate an outline. Use the max if it's white text on a black background. Other shapes, such as a circular area will produce different results that may be better for some fonts. In most cases, you'll end up either rounding off or squaring off corners as the size of the filter increases.


The actual color of a pixel, outputted on a monitor, does not linearly depend on the applied voltage signal for that pixel. For CRT monitors, the actual color is approximately proportional to the applied voltage raised to the power of a so-called gamma value, which depends on the monitor. This gamma value typically lies between 2.2 and 2.5 for CRT monitors. (Hence, the ubiquitous appearances of the magical constant 2.2 in rendering applications.)
$$L_\mathrm{actual} \sim V^\gamma$$
To bypass this gamma value in your computations, you need to gamma correct the computed colors of each pixel before presenting. By raising the computed color to a power of the reciprocal of that same gamma value, the computed color becomes proportional to the actual color.
$$V \sim L_\mathrm{computed}^{1/\gamma} \\
L_\mathrm{actual} \sim L_\mathrm{computed}$$
So in general gamma correction is a technique that adapts the computed colors to the transfer function of the monitor used for outputting. Both CRT and non-CRT monitors each have their own transfer function. This means that the final rendering pass should adapt the computed colors, based on the used monitor, to obtain correct actual colors.
These linear-to-gamma color space conversions seem like unnecessary overhead from a monitor construction point of view. It is physically perfectly possible to construct a CRT monitor with a gamma value of exactly one, ensuring that the computed color is already proportional to the actual color, and eliminating the need for gamma correction.
From a perceptual point of view, removing the need for gamma correction and using a monitor where computed colors are proportional to the corresponding actual colors is actually a bad idea. Typically, actual colors are represented with 8 (or 10) bits for each of the red, green and blue channel. This quantization only supports 256 (or 1024) different colors. Here, a 0 value represents completely black and a 255 (or a 1023) value represents completely white. But what about the intermediate values? If a linear encoding is used (i.e. a gamma value of 1), the majority of values would be perceptually very close to white and a very small minority would be perceptually close to black. By using a gamma encoding (e.g., a gamma value of 2.2), the distribution is perceptually more linear (i.e. equidistant intervals between black and white).


Components that can be used for 3d shadow analysis, sunhours of surfaces throughout the year in a 3d model?

I use Nvidia OptiX for Ray casting and tracing purposes. It is based on CUDA and gives you a library that runs on GPU and is capable of building and traversing efficient acceleration structures. You just supply a few programs such as intersection tests and shading and OptiX does the rest.
I personally think it is really easy to work with it but your milage may vary.
With this it should be very doable to make your project and even with decent running speed.


Is the demoscene a source of advancements in computer graphics?

The demo scene has been doing Ray marching for a long time, but only recently have main stream AAA games started using it.  The main use I've seen it for is for screenspace reflections, raymarching against the zbuffer (killzone, call of duty).  Also, shadertoy was made by inigo quillez, who is from the demo scene.  People are now using shadertoy to prototype and share graphics technique research.  So I'd say the answer is yes, but I'd like to hear more examples if other people have any (:


No, he's talking about subtracting the position of the cube from the vertex positions, so that your cube is positioned at the origin.

If you positioned the cube at (10, 30, 15), you subtract that value from every vertex.

Next, you rotate the vertices.

Lastly, you add the position to the vertices again so the box goes back to where it was, but the vertices have been rotated around the location of the box.

Doing rotation like this makes an object spin in place.

If you didn't subtract the position before rotating, the object would orbit the origin, instead of spinning in place.


Edit: changed the answer according to new images and clarification.

for every control point p(k, n)
   p'(k, n) = ( p(k, n) - p(k) ) * d * l(k) + p(k, n)

where k is the row index and n is the column index of control point. l is the elevation factor and is equal to {-1, -1/3, 1/3, 1}. p(k) is the center of the k'th row.

Rationale:

From the new images, red and blue lines are drawn from the center of the line (p(k) which is basically (k, 0)) to that point. On the first line, all control points, including the ones on the graph (red lines) are moved to the same point on that line. p(k, n) - p(k) gives the vector which moves a point from p(k) to p(k, n) which now should be applied to the other way, moving the point to the desired location. On your graphs, d = 1 so that all first line points would be moved to the center. You can easily solve the equation to verify this. d * l(0) is -1, so it would be -p(k, n) + p(k) + p(k, n) which would give p(k).

On the second line, your blue line is again from point to the center, but this time it stopped before reaching it. I cannot tell if it really is cut from 1/3 but that would be a good starting point. So the same formula still applies. l is -1/3 d is 1, so the point would be moved in 1/3 of the way. 3rd is the same as the second but it now moves outwards, thus l is 1/3.

On the final line, all control points are moved out from the center point of that line. This is quite clear since your lines meet up at that center.

The only problem this formula can have is assumption of 1/3, other than that I do not see the reason why it should fail.

Note: I used row, column while indexing, thus if you are using x, y you should switch their locations.


Why does some text on my laptop have only gray-scale pixels while other text has color pixels?

It's called subpixel rendering (there are different solutions on different platforms). Microsoft's one is called ClearType, just google for it, Wikipedia has a nice description.

Earlier, simple edge smoothing was used, antialising, that resulted in gray pixels added to the jagged lines to mask them, and although it technically created a more blurred outline, due to the way our brain works, we perceived the resulting forms more pleasing, more natural, easier to read.

Colored subpixels arrived when monitor technology moved from CRT screens to LCD where the RGB components making up a pixel are much more uniform. Very simply put, we treat our monitors as having thrice as many pixels horizontally than they actually do. When we render a character glyph, the body will be black, so no difference there. But if we calculate to need just a subpixel more to the left of a complete pixel, we will use that extra subpixel. Similarly, if we need to go just a subpixel to the right, we will use that.

But, using these individual subpixels rather than full pixels as with antialising, we will have color fringe inevitably because these subpixels are physically colored. Just look at your sample: all left edges have the same color fringe, yes, because that's the color of the last subpixel of the previous pixel. And right edges, similarly, have the color of the first subpixel of the next pixel.

What you can see in the screenshot is that the display sent to the monitor is pre-manipulated with the anticipation of the colored subpixels and displayed accordingly. Pixel colors are modified so that when they light up on the monitor screen, only those subpixels will be lit that are required by the calculations.

Monitors might be different and, more importantly, individual sensitivity to this effect is different from person to person. Apple, using only their own monitors and in line with their usual stance of "we tell you how to use it", only offers a way to switch this effect on or off in their user interface (although there is a way to select from a limited list of three different settings using the Terminal app and appropriate commands).

In Windows or Linux, where the hardware selection is much broader and people don't normally accept to be allowed only a single way, ClearType can be adjusted to your individual needs. Depending on the settings you selected, the actual color fringes will be very different.

This is just a compromise. In order to display text to be more legible, we sacrifice chrominance for luminance. Differences in intensity are more noticeable to the human brain than differences in color. So, even if it introduces color variations (which is absolutely not the intention but an inevitable consequence of the subpixels being colored), what we really see are the intensity differences. In simpler words, most of us will only perceive at that resolution and physical viewing distances that there is an extra subpixel, not that it has a different color.

And as to the final question of why gray in some places and colored in others, it's very probably a software issue. The browser you mentioned might have its own graphics rendering engine that simply works differently from what you normally have in the operating system. It's quite possible that it doesn't use the operating system's services to render text but renders everything by itself, pictures and texts as well, as a complete image and uses its own settings and techniques in the process.


According to the article, a half is basically a 16 bit float and an snorm is a signed float dividied by 65535. Therefore, they are basically the same

No, they're not, and you do the article a great disservice by suggesting that it says such a thing.

Yes, Half-floats are 16-bit floats. But they are floating point numbers, as defined in IEEE-754. Which means that they can express a relatively large range of values.

Normalized integers can only directly express values in the range [0, 1] (for unsigned) and [-1, 1] (for signed). Floating-point numbers can extend beyond this range. 16-bit floats can express numbers approximately on the range [-6.55*104, 6.55*104], and it can handle decimal values in-between them.

  Why do they give a "good precision" and are "evenly distributed" (as opposed to the half)?

Because that's how IEEE-754 works. After all, normalized 16-bit values and 16-bit float values have the same size. 16-bits of storage gives you 65536 different values, no matter how you interpret them. Therefore, to get the range of values outside of [-1, 1], 16-bit floats sacrifice some bits to define additional values.

16-bit floats give you about 3 decimal digits of precision. Normalized 16-bit values give you at most 5 (though the closer to zero you get, the fewer significant digits you get, unlike floating-point values).

  why use the magic number 64 if I don't want to calculate it?

No reason; it's just a made-up number.

  Is it common to have models that don't exceed this specific value?

Not particularly.

  If I get good precision with half (or xnorm respectively) to save bandwidth, but in my application actually need really large position values, can I leverage the better precision of xnorm with a multiplication for "full" float and save myself from using double variables?

No.

Generally speaking, model space positions do not need "really large position values". They're in model space, so they're generally expressed relative to a center position that's quite close to them. They don't really have to be in scale with the rest of the world either.

However, if your model space positions really do need "really large position values", then you have to use whatever gives you the precision you need. That's pretty much never double.


Correct way to think about Fresnel effect

I will answer based on my experience with Fresnel models. Due to Kirchhoff's law of thermal radiation, in an opaque material the emissivity plus reflectivity plus absorptivity equals to one for every direction in thermal equilibrium. If the BRDF model you are using is physically-based, it should preserve energy conservation. That means that for a given viewing angle, the integral of the equation for the entire hemisphere should be equal to 1. It may be possible the reflectivity value near the normal is low, but that means that most of its contribution is elsewhere. For example, for a near-normal viewing direction, you can have a really low specular reflectivity but a much higher diffuse component. That may be the case of your model.


The first things I would try is to see if smartphone pixels are visible (if the photo is high res) or if strange aliasing occurs (your example image shows both).

Another classical test (but not adapted to any scenes) is to detect perspective bias: if the camera is not exactly parallel to the smartphone screen, then 3D objects projected on the image on screen are projected again to the camera captor through a slightly different perspective. If the scene contains spheres, discs (physical or as reflects, for instance), perpendicular angles, or any similar invariant, then you can detect this.   (this kind of trick is also used to detect images photoshoped by composition of several images).


Ambient occlusion cannot be physically based no matter what algorithm you use to calculate it. It's a simplification of global illumination that assumes all occluders only block light and are themselves completely black, which isn't true and generally makes corners darker than they should be.

Ideally, you would be using some kind of global illumination method, but they generally don't have enough resolution to capture the effect ambient occlusion simulates and screen space global illumination tends to be too expensive.

That means ambient occlusion is still a reasonable choice, even if it's not entirely physically correct. Screen space ambient occlusion methods are the fastest, but suffer from the limited information they have access to, which can lead to artifacts like halos around objects in the foreground and the edges of the screen. Having more information about the scene to calculate the AO from, like VXAO does, eliminates those artifacts, but it again comes at a performance cost.

In the end, it depends on your perf budget. The more time you can spend calculating global illumination and ambient occlusion, the better the results are going to look. This seems to be a solid resource about screen space ambient occlusion algorithms in particular. I've personally had good results with Alchemy AO accelerated for large radii with a depth mip-chain similar to the Scalable Ambient Obscurance paper.

For an alternative to traditional AO, there's Bent Normals and Cones in Screen-Space that I've heard a lot about. As far as I understand it, the key difference is that instead of just calculating how much a point in space is occluded, it also captures information about what directions in particular are occluded. This information is then later used for lighting, where only light coming from the unoccluded directions is considered. It's still not what you'd call physically based, but in my opinion it comes closer than the usual ambient occlusion.


The way that NURBS curves are typically split at an arbitrary point is by knot insertion. You insert knots at the split point until it is at maximum multiplicity, at which point you can just read off the two split curves.

However, you may not want to split at an arbitrary point. If the ultimate goal is to draw the curves or something like that, then it's worth splitting the curve at the existing knot points (that is, performing knot insertion until all knots are at maximum multiplicity) rather than inserting new ones.

This process splits the NURBS into uniform rational B-splines. Once you have that, you can use de Boor's algorithm to split further.

The number of knots in the knot vector is:

numKnots = degreeOfCurve + numControlPoints + 1

or if you prefer:

numKnots = orderOfCurve + numControlPoints

Inserting a knot thus increases the number of control points by one.

As you travel along a NURBS curve, each knot represents a place where one control point "drops out" and another one "enters". If a knot value is repeated, this means that more than one control point is replaced at this place.

For a curve of degree greater than 1, the and last knots are repeated multiple times for one simple reason: you need to bring in more than one point to start and you need to eject more than one point to end.

Let's think about cubic curves for the moment, just to keep things simple.

A curve with the knot vector [0,0,1,1] is a uniform B-spline curve.

A curve with the knot vector [0,0,1,1,2,2] is non-uniform, but can be thought of as two uniform B-spline curves which connect at t=1, one corresponding to [0,0,1,1] and one corresponding to [1,1,2,2]. You can do this because the multiplicity of the knots is enough to "start" and "end" a cubic curve.

If you're faced with a curve with a knot vector like [0,0,1,2,2], you can insert a knot at 1 without changing the shape of the curve (this is the knot insertion procedure). This increases the number of control points by one; the knot insertion procedure adjusts the points around the new knot to accommodate it. But once you've done that, you have two uniform B-spline curves.

Knot insertion won't create overlapping control points unless you insert too many knots at the same place, and by "too many", I mean the degree of the curve. So for a non-uniform cubic curve, you'd insert knots so that every knot had multiplicity 2. That gives you a number of abutting uniform cubic curves, which you can then use de Boor's algorithm to split further.


Yes, the 0 in there represents the texture unit that the sampler references. So in order for a texture to be referenced by textureVar in the shader, it should be bound to texture unit 0 (e.g. by glActiveTexture(GL_TEXTURE0); glBindTexture(GL_TEXTURE_2D, ...) or any other means you can bind a texture to a texture unit.

However, note that it doesn't actually matter which texture unit is active when setting that uniform, nor what texture is bound to that unit. Effectively to the outside world the sampler uniform is just an integer value specifying the texture unit to take its texture and sampler information from. It can be set to that texture unit whenever you want and the texture can be bound to that unit whenever you want (in fact in GLSL 4.20+ you can actually initialize the uniform right in the shader with e.g. layout(binding=0) uniform sampler2D textureVar). All that matters is that at the point the shader gets invoked (i.e. when actually glDraw...ing something) the sampler is set to the proper unit and the texture is bound to that unit.

For more information on the matter, take a look at the corresponding section in the OpenGL Wiki.


No, a point does not have a length. A point is only a location - it has no extent in any direction.

You are correct in guessing that the function vSize() returns the distance from the origin to the point. The other function, vSize2() returns the square of that distance. This is used in calculating the distance, and in some cases it may be useful to work directly with the square of the distance instead of the distance. This avoids calculating square roots, so can lead to improvements in speed and accuracy.

Note that as Nero points out, the functions are using only ints (integer variables and return values). The distance between a point and the origin is not in general an integer value, even if the coordinates of the point are all integers. The distance squared returned by vSize2() will be accurate, but the distance itself returned by vSize() will be accurate only to the nearest integer.


Is doing multiple Gaussian blurs the same as doing one larger blur?

If I did two Gaussian blurs of size N, would that be the same mathematically as doing one Gaussian blur of size 2N?

Almost. Applying two Gaussian blurs is equivalent to doing one Gaussian blur, but with a slightly different size calculation.

Applying a Gaussian blur to an image means doing a convolution of the Gaussian with the image. Convolution is associative: Applying two Gaussian blurs to an image is equivalent to convolving the two Gaussians with each other, and convolving the resulting function with the image.

As it happens, the convolution of two Gaussians with each other is another Gaussian, whose variance is the sum of variances of the two original Gaussians. A Gaussian of N pixel width has variance $N^2$; applying it twice is equivalent to a Gaussian with variance $2\cdot N^2$, which corresponds to a width of $\sqrt{2}\cdot N$ pixels.

In the same vein, applying a Gaussian of width $2\cdot N$ is equivalent to applying a Gaussian of width $N$ four times.


What is the typical use case for rendering to an image through imageStore?

I've used imageStore as part of compute shaders doing surface extraction. I've only ever used it in compute shaders, to store the calculated data in a texture to be consumed by another shader - I know it's possible to do imageStore in a fragment shader as well but I haven't come across a use case for it yet.

I also haven't used imageLoad at all, since apparently texelFetch is often faster (benefits from using the texture cache), and at worst no slower, so I simply bound the same texture to both an image and a texture unit, and used imageStore for writes and texelFetch for reads.

The code to get it all working looked something like this (using OpenGL 4.5 and DSA, and assuming cShdr holds a compute program that does imageStore on channel 0, cShdr2 is a second compute program that samples the generated texture on channel 0, and rShdr is a rendering program that samples the texture on channel 0 - of course, if you don't want to hardcode the texture channel in the shader you can use glGetUniformLocation):

//setting up texture and binding to image unit 0
GLuint tex;
glCreateTextures(GL_TEXTURE_2D, 1, &tex);
glTextureStorage2D(tex, 1, GL_RGBA32F, 256, 256)
glBindImageTexture(0, tex, 0, GL_FALSE, 0, GL_WRITE_ONLY, GL_RGBA32F);

//Dispatch a compute shader to imageStore to the texture
//wait for completion before allowing sampling
glDispatchCompute(cShdr, numX, numY, numZ);
glMemoryBarrier(GL_TEXTURE_FETCH_BARRIER_BIT);

//code that samples the texture in render loop
glBindVertexArray(vao);
glBindTextureUnit(0, tex);
glUseProgram(rShdr);
glDrawArrays(GL_TRIANGLES, 0, numVerts);

//or if consuming data in second compute shader using texelFetch
glBindTextureUnit(0, tex);
glDispatchCompute(cShdr2, numX, numY, numZ);

The first 3 parameters to glBindImageTexture are image unit, texture, and mip level. The next two deal with binding arrays of textures, and should just be set to GL_FALSE, 0 when binding a single texture. The final two are access and format (for stores).

Note that although I've used the GL 4.5-specific functions for creating textures and binding the texture unit, the glBindImageTexture works with every version that supports load/store - 4.2 and above.


Determining Vanishing Points of edges of Triangle using given Point

Vanishing points are "points at infinity" in projective geometry, which are represented by $w = 0$ in homogeneous coordinates. You can construct the vanishing point of a ray or line by taking its $xyz$ direction vector and adjoining $w = 0$. (For a line, use the direction vector and its negation to get vanishing points in both directions.)

Then you can transform this homogeneous vector by your view/projection matrices as usual, and divide out $w$ from the result to find where the point lies in screen space. (If the result has $w \leq 0$ then it's behind the camera or off to the side.)


How does the GPU know whether to magnify/minify?

Minification vs magnification is an extension of mipmap selection. When you calculate the desired mip level, it can come out to be less than 0 (or in general, less than the sampler's configured minimum LOD). In that case you're doing magnification of the lowest mip level. If the desired level comes out to a value greater than 0 then you're doing minification.
Mipmap selection works by calculating differences of the UV coordinates between adjacent pixels on screen (see shader derivative functions). Since the GPU is always shading pixels in 2×2 quads, it can look at the set of UVs input to the sampling operation across all those pixels. Those derivative vectors establish what the pixel footprint in texel space is, and their lengths are used to calculate which mip level to sample.
The details of how these calculations work exactly can be found in the OpenGL spec, section 8.14 "Texture Minification"


Phong and the Rendering Equation: What's with the cosine?

The cosine term in the rendering equation is to account the amount of light reaching the surface, and leaving it out from the rendering equation is what he refers as "complete nonsense", which is right. The original Phong model didn't have the cosine term in the rendering equation, so if you want to model the original nonsensical Phong with proper rendering equation, you need to hack it by adding the cosine denominator to the Phong BRDF.


Repeating alpha over/under operation multiple times

So taking source over as an example, the math works out to:

  dst = a * src + (1 - a) * dst

Taking Nathan Reed's suggestion of replacing (1 - a) with b, that gives us:

  dst = a * src + b * dst

If we perform the next iteration, it becomes:

  dst = a * src + ab * src + b^2 * dst

Doing it again, we get:

  dst = a * src + ab * src + ab^2 * src + b^3 * dst

And then:

  dst = a * src + ab * src + ab^2 * src + ab^3 * src + b^4 * dst

The pattern appears to be:

int exponent;
for (exponent = 0; exponent < numIterations; exponent++)
{
    newDst += a * pow(b, exponent) * src;
}
newDst += pow(b, exponent) * dst;


What is the state of art in geometric LOD in games?

For the geometry LOD most games simply switch between a number of predefined LOD meshes. For example "Infamous: Second Son" uses 3 LOD meshes (Adrian Bentley - "inFAMOUS: Second Son engine postmortem", GDC 2014) and "Killzone: Shadow Fall" uses 7 LOD meshes per character (Michal Valient - "Killzone: Shadow fall demo postmortem", Devstation2013). Most of them are generated, but more important ones (like main character) can be hand made. Meshes are often generated using a popular Simplygon middleware, but sometimes they are simply generated by graphics artists in their favorite 3D package.

Games with a large draw distance additionally use imposters for foliage, trees and high buildings (Adrian Bentley - "inFAMOUS: Second Son engine postmortem", GDC 2014). They also employ hierarchical LODs, which replace a set of objects with one. For example in "Just Cause 2" trees are first rendered individually as normal LOD meshes, then individually as imposters and finally as a single merged forest mesh (Emil Persson, Joel de Vahl - "Populating a Massive Game World", Siggraph2013) and in "Sunset Overdrive" distant parts of the world are replaced by single automatically offline generated mesh (Elan Ruskin - "Streaming Sunset Overdrive's Open World", GDC2015).

Another component of a LOD system is simplification of materials and shaders. For example "Killzone: Shadow Fall" disables tangent space and normal mapping for the distant LODs (Michal Valient - "Killzone: Shadow fall demo postmortem", Devstation2013). This usually is implemented by disabling globally a set of shader features per LOD, but for engines with shader graphs, where artists can create custom shaders, this needs to be done manually.

For the LOD transitions some games simply switch meshes and some use dithering for smooth LOD transitions - at the LOD switch two meshes are rendered: first gradually fades out and second fades in (Simon schreibt Blog - "Assassins Creed 3 – LoD Blending"). Classic CPU progressive mesh techniques aren't used as they require a costly mesh update and upload to GPU. Hardware Tessellation is used in a few titles, but only for the refinement of a most detailed LOD, as it's slow and in general case it can't replace predefined geometry LODs.

Terrain LODs are handled separately in order to exploit it's specific properties. Terrain geometry LOD is usually implemented using clipmaps (Marcin Gollent - "Landscape creation and rendering in REDengine 3"). Terrain material LODs either are handled similarly to mesh LODs or using some kind of a virtual texture Ka Chen - "Adaptive Virtual Texture Rendering In Far Cry 4.

Finally if you are interested to see real game LOD pipelines then just browse through documentation of any of the modern games engines: Unreal Engine 4 - "Creating and Using LODs", CryEgnine - Static LOD and Unity - LOD.


Issue with loading a texture on the GPU with OpenGL 4.1 Core profile

You seem to not change GL_TEXTURE_MIN_FILTER and not fill all the mipmap layers. This will usually result in the texture not being applied, since by default the filter uses mipmapping.


Sphere's don't have edges like the ones in that picture. The "silhouette" should be a circle. This is because the sphere was rendered as triangles and rasterized. Triangles can only approximate a sphere.

Compare this to ray casting for instance. Where we can directly test the intersection between a sphere and ray thus no need to approximate a sphere with other primitives.

What smooth shading lets us do is interpolate values across the face of a triangle to cheat and make something appear smoother. In reality a sphere (a uv sphere) would look like this:

There are two common ways to make the above sphere look smooth without adding anymore geometry. Both of which involve linearly interpolating values across the face of a triangle. Like barycentric interpolation. With barycentric interpolation, given values at 3 points (on a triangle) and a point we want to know the value for we can calculate a mix between the 3 values at the corners such that it smoothly varies across the face of the triangle.

In rasterization there are two popular ways to smooth shade. The later being used more often.

Gouraud: We calculate the post-lighting (shaded) color at each vertex and interpolate the color across the face of the triangle.

Phong: We calculate the shaded color at every pixel across the triangle, interpolating things like normals across the triangle.

EDIT: The difference between gouraud and phong is that gouraud assumes the color and light intensity change linearly with the normal. Whereas phong does not. For a simple light intensity = dot(normal, lightDir) = cos(angle between normal and lightDir) we can see the relationship between intensity and the normal is nonlinear. This can be well illustrated with the below image (see the seams on the specular highlight. This is the consequence of our linear interpolation):


Compute area (not surface area) and perimeter of a mesh

There's a small problem with your method. When the mesh self shadows then part of the model will be counted twice.

You can get the projection of a mesh onto an arbitrary plane by finding the rotation from the normal of the plane to the Z axis and rotating the mesh with it. After that you discard the Z component.

However it's more straightfoward to simply draw the mesh with appropriate projection and counting how many pixels it takes up.

An edge can be part of the perimeter only when both the triangles that make it are projected onto the same side of the projected line.

You can use that to walk around the perimeter. Start with the negative x most point after the rotation and follow the lines. When another potential perimeter line crosses the current line you start following that one instead.


What is missing in this image that stops it from looking like a photograph?

The hair seems to have sampling noise or aliasing in it. This might be poor jpeg compression but it does not look like it.
I've never seen hair part that way (could just be me).
The neck looks a little too regular (I'm no modeler though).
The skin's subsurface scattering falls a bit short. Perhaps it's not that but there is something slightly off about the skin.
The shirt has a slight plastic feel to it.

Most of this is entirely subjective of course. I think it's fairly good but falls short of the state of the art in many areas.


Using transformations to get from A to B image

Just use linear algebra.

Since parallel lines have remained parallel (i.e. meaning we can probably assume the w component of homogeneous coordinates is always 1), we can just pick 3 starting points and their destinations, e.g.

(0,0,1)->(3,2,1),  (0,1,1)->(1,3,1), and  (1,0,1)->(5,3,1),

define M to be your (homogeneous) transformation matrix as

$$ M =\begin{bmatrix}
a & b & c \\
d & e & f \\
0 & 0 & 1\\
\end{bmatrix}  $$
and then we have
$$ M.\begin{bmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 1 & 1\\
\end{bmatrix} =
\begin{bmatrix}
3 & 1 & 5 \\
2 & 3 & 3 \\
1 & 1 & 1\\
\end{bmatrix}
 $$

You just need to find the inverse of the 'starting point' matrix (which is left as an exercise for the reader ) and rearrange to compute...
$$ M=
\begin{bmatrix}
3 & 1 & 5 \\
2 & 3 & 3 \\
1 & 1 & 1\\
\end{bmatrix}
.\begin{bmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 1 & 1\\
\end{bmatrix}^{-1}$$

To be really thorough, you could also then check that all the remaining points are transformed correctly by your result.

If you don't want to work through the maths yourself, the resulting matrix is

   $ M= \begin{bmatrix} 2 & -2 & 3 \\ 1 & 1 & 2 \\ 0 & 0 & 1\\ \end{bmatrix}$


How does this app pull off fast, high radius HDR

At CEDEC and GDC in the early 2000s, Masaki Kawase has presented a series of fast post-processing based lens effects, including large bloom.

This presentation from GDC 2003, Frame Buffer Postprocessing Effects in DOUBLE-S.T.E.A.L (Wreckless) (see slides 15 and upwards: "Bloom"), gives a first version of the bloom. It consists in doing a Gaussian blur by sampling at exponentially increasing distances.

In this presentation from GDC 2004, Practical Implementation of High Dynamic Range Rendering (see slides 44 and upward: "Glare generation"), he updates the technique. Instead of varying the sampling distance, he uses downsized versions of the original image, using a carefully crafted equation to achieve a large yet spiky Gaussian blur.


Paper for the approximation formula provided by Brian Karis

I do not have a derivation but i can explain the reasoning behind its usage.

On the left side is a (monte carlo) estimator for the rendering equation. It states the very same thing that the rendering equation states but on a finite number of discrete samples.

on the right side we have the $L_i(l_k)$ factor separated and "integrated" on its own.
This approximation holds true when $L_i(l_k)$ is a constant, since $\sum_{k}f(k)\times n = n \times\sum_{k}f(k)$ - and, likewise, $\int_{k}f(k)\times n\space dk = n\times\int_{k}f(k)dk$ - when $n$ is a constant.

$L_i(l_k)$ can be though of the colour of the incoming light and $\int_{k}f(l_k,v)dk$ can be thought of as the intensity of the reflected light. multiplying those together you get that now you can precompute $\int_{k}L_i(l_k)dk$, saving a lot of time in either texture lookups (in the case of sky / environment lighting / screen space ray marching) or raytracing calculations.

However, since $L_i(l_k)$ is usually not a constant, this integral is not separable. Yet, in some cases (like when dealing with diffuse lighting or, more specifically, diffuse ambient lighting), the information that $f(l_k,v)$ carries is low-frequency enough that it can reasonably be approximated as a constant with respect to the distribution of $L_i(l_k)$. Experimentally, it can be shown that the final result is not too different from what you would expect.


OpenGL : How to translate an object with it's own axis

You can put the translation first, and then the rotation, but have the translation happen in the direction of the cow's head. To do that, you need a vector from the center of the cow to its head. Then you need the length of the translation. You can then do the translation in that direction. Like this:

float direction_x;
float direction_y;
float direction_z;
direction_x = cow_head_x - cow_center_x;
direction_y = cow_head_y - cow_center_y;
direction_z = cow_head_z - cow_center_z;

// find the length of the direction vector
float dir_length = sqrt(direction_x * direction_x + direction_y * direction_y + direction_z * direction_z);

// normalize the direction vector by dividing by the length
direction_x /= dir_length;
direction_y /= dir_length;
direction_z /= dir_length;

// Create a new vector pointing in the correct direction with the same
// length as the drag
float cow_translate_x = direction_x * drag_length;
float cow_translate_y = direction_y * drag_length;
float cow_translate_z = direction_z * drag_length;

// Do the transformation
glTranslatef(cow_translate_x, cow_translate_y, cow_translate_z);
glRotate(angle, rotate_x, rotate_y, rotate_z);

You could also get the direction vector by converting the angles to a direction. For example, if the rotation is only around the Y-axis, you could calculate it by doing the following:

float direction_x;
float direction_y;
float direction_z;
direction_x = cos(angle);
direction_y = 0.0; // since we're rotating around the Y axis
direction_z = sin(angle);

In this case, the direction vector is already normalized.

If you do have rotations around all 3 axes, you can calculate the direction vector using spherical coordinates:

direction_x = sin(angle) * cos(phi);
direction_y = sin(angle) * sin(phi);
direction_z = cos(angle);

where angle is the rotation around the y axis and phi is the angle above/below the x/z plane. The direction should already be normalized in this case, too.


Parallax/relief mapping with gl_FragDepth and conservative depth

Unfortunately, gl_FragDepth won't enable you to write outside of the rasterized triangle's screen-space bounds. All it enables is to modify the values written to the depth buffer within the triangle, replacing the triangle's true depth with a shader-calculated value.

What you're seeing in the screenshot in the Unity forum thread you linked to is two intersecting parallax-mapped surfaces, where the depth output enables occlusion between the two surfaces to be correctly resolved in the screen-space region they both cover. But if you look at the right side of the screenshot, you can see the straight-line edge of the bottom brick polygon.

However! You might still be able to accomplish the goal of getting correct silhouette edges by using discard in the fragment shader when the parallax ray gets outside the bounds of the original polygon. This would involve modifying the ray-march code to check if the march has crossed a triangle edge, and exit with discard if so, rather than continuing to march.

You'd have to find a way to get the information about triangle edges into the fragment shader, though, as this isn't provided by OpenGL. Maybe make your vertex/index buffers available via SSBOs; then you can use gl_PrimitiveID in the fragment shader to index into them and lookup the vertex data.

Unfortunately I don't know offhand of any implementation of something like this, although I'm sure someone out there must have tried it before.


What's the difference between two code in shader?

I don't have enough rep to comment :(

Hi,

It looks like with (2), fs_in.TexCoords is == vec2(0.0,0.0). Do you keep both in VS_OUT {}/ out VS_OUT {} and out vec2/in vec2 ? If so, it's possible that as both have the same name (TexCoords) the compiler is confused. Try using only one of the two options.


VR requires a much higher resolution and framerate, and a much lower latency (start of draw to showing on screen).

If any of those things are missing then people tend to get nauseated.

All of those require much higher bandwidth and compute power than Apple's cards are supposed to be able to handle.


3d Math Primer book equation derivation - Projecting One vector onto another

Since v∥ is parallel to n, it can be expressed as some multiple of n. The multiple is the ratio of the length of v∥ to the length of n. The n vector doesn’t have to be normalized, but if it is, then |n| is 1, so the equation becomes v∥ = n * |v∥|.


Why are oct trees so much more common than hash tables?

Lots of things here.

"When reading papers". What papers? If the topic of the paper is about something other than the spatial partitioning structure, it could be fair to use whatever knowing that the basic ideas will translate to other structures. Or not, hard to say.
"For example for ray tracing an oct tree, near misses will cause you to iterate through a binary tree substructure, which is O(nlogn) whereas the hash table is O(n)". Big O notation means nothing at all in this context. You are dealing with a particular technology at a particular scale when you talk about things that depend on implementation details. An O(nlogn) algorithm might be much slower than an O(n) one for the "n" that is realistic today, it happens all the times. And while you might say, in 10 years that might change, sure, that might be the case, but in the same 10 years your GPU might look completely different and thus the state of the art algorithms need to change regardless. That's common, if you look at GPU algorithms (and GPUs specifically are still evolving quite a bit)
What octree? What hash table? There are lots of choices there. For example "...as they do not require any logical position in memory other than their hash position". That's true only if you have no hash collisions, yes? If you have collisions then whatever strategy you use (probing or linked lists) you'll need to synchronize between threads, so the build is not so easy to implement on a GPU. Conversely, for octrees if you wanted to "overallocate" as you suggest then you could allocate a full tree, and indexing would then be equally only dependent on position. In fact, if you do some math you can see that in such cases octrees become just a way to swizzle a grid (e.g. compare the van Ende Boas layout with a grid in Morton order... nice exercise).

There are lots of other things I could say, but let me cut to the chase here.

For raytracing specifically, neither Octrees nor Hash tables are -that- popular. BVHs of AABBs are the way to go.
The main benefit of Octrees over hashed grid is that your cell resolution adapts to the geometry. Grids won't, you have to chose a cell size and that might be too small in certain parts of the scene and too big in certain others.
There are a -lot- of variants and a -lot- of implementation details. Naive octrees should probably never be used in practice as they are too deep / not wide enough. If you make an octree "larger" by having say, a 4x4x4 grid with 4x4x4 grids nested in each non-empty cells, you create what it's called a hierarchical grid. So grids and octrees exist on a spectrum, where octrees are the most "deep", grids are the most "shallow" (just one level, a single grid globally in the scene), and hierarchical grids can trade between the two
This might help! http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf ;)


How to properly combine the diffuse and specular terms?

Using two Fresnel terms is correct in the sense that any given diffuse path will pass through the surface twice. If you're solving diffusion by tracing a path through the medium until it bounces out again then that you will get two (or more) Fresnel terms for that path as it interacts with the surface.

However, that's not what you're doing with a diffuse BRDF. A diffuse BRDF is intended to represent the average of all those possible diffusion paths. In the case of an Lambertian that average is modeled as uniform reflection and a single albedo value measuring the internal energy loss during diffusion, but more complicated models are possible. Crucially: a diffuse BRDF will already include the aggregate effect of some paths being reflected back into the medium to diffuse further and some passing out immediately. $1 - F_{out}$ is already "baked in" to the BRDF¹ and you do not need factor it in again.

What the Lambertian term does not include is the portion of energy that is lost by being reflected before light enters the medium of diffusion. This is view-dependent, but depends on the precise glossy lobe above it. There is no energy loss at a (non-metallic) surface interface so everything that isn't reflected will be refracted, meaning that what you actually want is to integrate the total energy loss at the surface over all outgoing directions, i.e. $1 - \int \texttt{glossy_bsdf}(\texttt{in}, \texttt{out}) \: \mathrm{d} \texttt{out}$.

It's possible to pre-compute approximations to that integral for specific BRDFs. The end result will in general depend on view direction, material roughness and IOR at least. As a first approximation you can assume that the glossy lobe is a perfectly specular reflector. That gives a weighting of $1 - \int \texttt{glossy} \: \mathrm{d}\texttt{out} = 1 - F_{in}$, which is exactly what you first suggested.

Additionally, note that the Lambertian BRDF is the albedo divided by $\pi$ and that the cosine term is a measure of how attenuated the incoming light is on the surface; it applies to both glossy and diffuse reflectance.

So, roughly:

// Assuming for example:
//   diffuse = albedo / PI;
//   specular = my_favorite_glossy_brdf(in_dir, out_dir, roughness);
//   fresnel = f0 + (1.0 - f0) * pow(1.0 - dot(E, H), 5.0);
//   total_surface_reflection = fresnel
color = lightIntensity * dot(L, N) * Lerp(diffuse, specular, total_surface_reflection);

¹ Really the integral of $F$ over all possible incident internal diffusion exit paths that result in your out direction, but I digress.


Path tracing is a common method for making photo realistic images.  If I were you, I'd start off doing a google image search for path tracing to find some images.

You may get lucky and find a site that has a lot of them.

Here are a few examples I found doing that:


How to calculate position from depth pass of the ZED camera?

zed2-camera-datasheet.pdf tells the

Baseline is 120mm
Focal length is 2.12mm

such that based on the fx,fy, you can find the pixel to mm ratio.
You have the local length, baseline, the object coordinates, the principle coordinates. The triangulation is formed, and the depth estimation can be found using ZED depth formula


Find the longest straight line between two points on surface of polygon

I don't have an exact answer for this, as the answer is far from trivial. I would suggest that you have a look into computational geometry as this clearly is a visibility problem - my guess is that a solution already exist. My own idea would be: for each line segment in polygon find the visible parts of the other line segments and then pick the pair of points that are furthest apart. Inspirational link: Wikipedia on 'visibility polygon'.


Suggested image preprocessing before applying threshold

In your case, I don't think a pre-processing is necessary. You may find the Hough transform useful in your case.

Since your image is big, it can be difficult to have a straight line due to the noise and blur.

This is what I got using a sobel contour detection with a smaller version of your image.

This is maybe a good start to use a line detection algorithm.

A second solution would be to use color segmentation. If you assume that your screen would always have black border you can work something in the LAb or HSV color space.


You should separate your line drawing logic from your calculation logic.
In general you should try to have a generic line drawing function that would accept any number of points and draw a line from one point to the next.
The simplest implementation for this would be to have dense points and draw a circle at each point.

If you however absolutely have to calculate the color of a pixel as a function of the X coordinate you'll have to calculate the value multiple times.
Lets say you want thickness of 3 pixels, you will have to calculate this for [X-1, X, X+1] and then check if the current pixel is close to any of the values.
A big downside to this is that you have many duplicate calculations.


The issue is, that you considered that the rays coming from the camera to be the light carrying rays. Instead, the rays bounce off the surface, and return to the light source (which you have decided to position at the camera). This means that your light direction is not $\pmb{d}$ but rather $-\pmb{d}$, then $\cos\theta = - \pmb{d} \cdot \pmb{n}$, provided that both vectors are normalized.

Also, you really want to try to retirn the correct normal, as it is, your current code will return the wrong normal if the camera is inside the sphere. So your normal should be:
n = dot(n,d)<0 ? n : -n;, where n is the normal returned by your surface, and d is the ray direction for the ray that intersected the surface.


Determining the Bounding Box values of a glTF file

There isn't a bounding box for the whole glTF file, but individual primitives have POSITION accessors that indicate min and max values.  This is specified in the Meshes section, with the following text:

  POSITION accessor must have min and max properties defined.

For a concrete example of this, take a look at the Box sample model, which assigns accessor 2 as POSITION

"meshes": [
    {
        "primitives": [
            {
                "attributes": {
                    "NORMAL": 1,
                    "POSITION": 2
                },
                "indices": 0,
                "mode": 4,
                "material": 0
            }
        ],
        "name": "Mesh"
    }
],

The accessor at index 2 (the third one in the list) looks like this:

"accessors": [
    { ... },
    { ... },
    {
        "bufferView": 1,
        "byteOffset": 288,
        "componentType": 5126,
        "count": 24,
        "max": [
            0.5,
            0.5,
            0.5
        ],
        "min": [
            -0.5,
            -0.5,
            -0.5
        ],
        "type": "VEC3"
    }

In this accessor, min and max are arrays of x, y, z raw position data of the primitive.  This particular sample model is a unit cube, with values ranging from -0.5 to 0.5 along each axis.

To understand how this affects the whole model though, one must walk the tree of scene nodes, and look at how these mesh primitives are being transformed by the nodes.  Also, if there are any animations or morph targets taking effect, they can influence the final positions of these meshes as well.


The math you need is linear interpolation. I think of a player sprite which moves from position X to position Y. Pseudocode:

playerSprite.x = Y.x + t * (X.x - Y.x)
playerSprite.y = Y.y + t * (X.y - Y.y)

where t is a value between 0.0 and 1.0 (floating point). Instead of incrementing the position components of Y you increment t till it reaches 1. When it reaches 1 the playerSprite reached point X. If t is 0, then the playerSprite is at position Y.


If a 3D scene is rendered onto a hemispherical display, will there still be warping near the edges?

There will be no distortion as long as you project the scene properly onto your virtual camera.

In traditional raster graphics the scene is projected onto a plane.

This makes it so that two equal solid angles to the camera can take up vastly different amounts of space on the screen.

Thus, the distortion does not come from the screen itself but from the projection used. Now, if you render your scene using a hemisphere projection, you should have no warping whatsoever. However, rendering using such projection might prove to be non trivial or straight up imposible using common methods (an exception to this is ray-tracing/marching/casting where all you need to change is how you generate your camera rays).

An alternative is to render various views (one facing the front, one facing upwards, etc) rendered in the classic flat projection and then "stitch" those together by mapping them to the screen somehow.

Here is a github repository of such a thing: https://github.com/shaunlebron/blinky

TL;DR : The display has little to do with how distorted an image appears. It is the projection used by the software that creates warping. Therefore, Even when using a curved display, the image will still appear distorted, unless this is compensated for in software.


One very simple way to do it is to just find the straight line distance between the points A and C. Divide that distance by the number of points you want to subdivide+1. Then starting at A moving along the line formed between A and C add that distance for each subdivision. This gives a nice even subdivision without having to argue with PI.
To get the point on the circle, just take the normalized vector between B and your new point and multiply it by the radius of the circle. The result is a subdivision point on your circle/sphere.
float distanceAC = length(C-A);
float stepLength = distanceAC/(SubdivisionsCount+1); // 4 in this case
vector v = C-A; // gives a vector pointing from A to C
v = normalize(v);
for( int i=1; i<SubdivisionCount+1; i++ ){
     point pointOnLine = A + v*i*stepLength; // Need steplength*i steps along v
     point subdivisionLocation = normalize(pointOnLine-B)*radius;
     // save the subdivision location
}

This has the plus of being simple, but the negative is that if you want to do to many steps or you want your steps to be extremely accurate, or you want to subdivide over a very large arc, then accuracy suffers.


Stumped on GLSL error C5041 (cannot located suitable resources to bind variable... possibly large array

This is strange though because an int mvoc = GL_MAX_VERTEX_OUTPUT_COMPONENTS returns 37,154.

That's the value of the enumerator; it's a static, compile-time value. The actual runtime limit is queried from the implementation using that enumerator. Typically via glGetIntegerv(GL_MAX_VERTEX_OUTPUT_COMPONENTS, &mvoc).

  tell me that can't be right...

Why not? Sending 128 components per vertex is plenty.

You shouldn't be doing transformations into light-space in your VS; that should happen in your fragment shader. You should be sending the basic information to the FS needed for it to do its job: normals (and tangent/bitangent as needed), texture coordinates, etc.

If you find that your FS's performance is not what it needs to be, then the best thing you can do is reduce the number of FS executions. You can use a depth pre-pass to eliminate overdraw, so the only FS executions that happen are those which produces an actual visible element. Or you can go to full-on deferred rendering.

But this method of pre-computing large quantities of data per-vertex is not going to work. Interpolation of vertex data is not free, nor are the caches between the VS and the rasterizer.


Find closest point on surface interpolated by 2d matrix of points

This is only a rough idea, though I hope it may inspire better answers.

The closest point on a surface is as far as I know always forms together with the red point a line that is orthogonal to the surface.

If you know which yellow vertices form the surface that the green point lies on, this is easy. You could just formulate the normal form of the surface (which is piecewise linear so it works out) formulate the orthogonal line to the surface that goes through the red point and solve for the intersection point. Though I don't have the exact math here, this step should be easy to look up.

Now the problem is: Which linear piece of your surface is the closest one.
Either you calculate the green-point candidates for all linear pieces and also the distance and take the closest one, or you find some other possibly faster way for this.
For that I don't have a more clever idea.


The first step in your existing code calculates the orientations of one line segment relative to each of the two end points of the other line segment, using the cross product. This allows testing whether the other line segment has one end point anticlockwise and the other end point clockwise from the first line segment, indicating that the line on which the first segment lies cuts the other segment.

Rather than writing a new test, you can use these same orientations to test for line segments that overlap (including partial overlap). If both segments lie on the same line, then all four orientations calculated in your first step will be zero, because none of the end points are either clockwise or anticlockwise from the line, since they are on the line. Then it remains only to check whether the two segments on the same line overlap, by checking whether either of them has an end point between the end points of the other segment.


How to match Blenders polynomial lens distortion model with GLSL?

Not sure what's wrong with your implementation, but it looks like the blender's distortion model is not proportional to the image aspect ratio, producing equal curvature in both axis..

Can you compare the input coordinates between the two implementations?


What is the most physically accurate representation of color possible in computer graphics?

The most physically accurate way would be to have a $l(\theta)$ which for each possible color frequency has a certain value.

Converting to RGB would then need a frequency responce function for each channel and the result is then $\int_{infrared}^{ultraviolet} l(\theta)F_{red}(\theta)d\theta$.

Reflected light then has a 2 dimensional response function: $L_{reflected}(\theta) = \int l_{incoming}(\phi)R(\phi,\theta)d\phi$. (ignoring the BRDF here for simplicity)

Drawbacks are that instead of just 3 color channels you now have infinite channels to worry about.


Vec3 v = myPoint - pointOnPlane;
float vDotPlaneNormal = dot(v, planeNormal)
if (vDotPlaneNormal == 0)
    printf("point on plane");
else if (vDotPlaneNormal > 0)
    printf("point above somehow...");
else
    printf("point under sadly...");

If you wonder what is pointOnPlane. In fact it can be any point that lies on the plane. Imagine this as a sheet of paper; draw two lines on this sheet to define the center of the piece of paper, imagine that this point is aligned with the world coordinate system origin and that sheet is in xz plane of that coordinate system (in which y defines the up vector). So the paper is horizontal in a way. Now move the sheet around. The pointOnPlane can be the coordinates of the point you drew in the center of the sheet of paper with respect to the world origin.
All you have to do is rotate that sheet of paper. That rotation is given to you by the plane's normal.
The rest is basic trig. If the point P is one the plane, the dot product between the vector defined by (P - PointOnPlane) and the plane's normal will be equal to 0. The dot product tells you whether two vectors are orthogonal, on the same side of the plane or point in opposite directions.
FASTER SOLUTION - EDIT
As mentioned by SimonF in a comment, you don't really need the pointOnPlane parameter and save the subtraction between this point and the tested point:

As you imply, a plane can be represented by its normal, $N$, and a scalar, $d$.
A point X is on the plane if $N \cdot X+d = 0$. As for inside and
outside typically you define a rule, e.g., that the normal points
"out" from the plane which just means that if $N \cdot X + d > 0$, then
$X$ is above the plane, while $N \cdot X + d < 0$, implies it's below.

You can test/use both techniques.


is utilizing multiple GPUs better than using one for all software?

This is more of a long comment than an answer.
As with most yes or no questions in graphics, the answer is "it depends on the task". However, one particular task that you might find having multiple gpu's useful is debugging. For example if you are using cuda-gdb for debugging your CUDA application, it would be nice to have multiple gpu's, one for your application, the other for the display manager of your system. Note that cuda-gdb also works on a single gpu as well, but I had problems with it when I run the debugger and the display manager of the system on a single gpu (screen tends to freeze, no response from the system, etc).

Update 19-01-2021 with respect to comment.
Here is the main criteria that I would use for deciding if the use of single or multiple gpus are better for the task.
GPUs simply execute one task after another, so if you send a heavy task, it will do only that during the process and you won't be able to do anything else with it.
This usually means that your system would freeze until the gpu is done with your task.
If you are going to launch the task and won't plan to do anything with the machine until it is finished, then sure, the use of multiple gpus would get it done quicker. If you plan to use the machine during the process for other stuff, then it would be more reasonable to allocate a single gpu for the task.
If you are setting up some kind of rendering server where the server would do only gpu related computation, it depends on the type of request you are planning to process by the server.


How do correlated samples influence the behavior of a Monte Carlo renderer?

There is one important distinction to make.

Markov Chain Monte Carlo (such as Metropolis Light Transport) methods fully acknowledge the fact that they produce lots of highly correlated, it is actually the backbone of the algorithm.

On other hand there are algorithms as Bidirectional Path Tracing, Many Light Method, Photon Mapping where the crucial role plays Multiple Importance Sampling and its balance heuristics. Optimality of balance heuristic is proven only for samples that are independent. Many modern algorithms have correlated samples and for some of them this causes troubles and for some it doesn't.

The problem with correlated samples was acknowledged in the paper Probabilistic Connections for Bidirectional Path Tracing. Where they have altered balance heuristics to take into account the correlation. Have a look at figure 17 in the paper to see the result.

I would like to point out that correlation is "always" bad. If you can afford to make brand new sample than do it. But most of the time you can't afford it so you hope that the error due to the correlation is small.

Edit to explain the "always": I mean this in the context of MC integration

Where you measure the error with variance of the estimator

If the samples are independent that the covariance term is zero. Correlated samples make always this term nonzero thus increasing variance of the final estimator.

This is at first sight somewhat contradictory what we encounter with stratified sampling because stratification lowers the error. But you can't prove that stratified sampling converges to the desired result just from the probabilistic point of view, because in the core of stratified sampling there is no probability involved.

And the deal with stratified sampling is that it is basically not a Monte Carlo method. Stratified sampling comes from standard quadrature rules for numerical integration which works great for integrating smooth function in low dimensions. This is why it is used for handling direct illumination which is low dimensional problem, but its smoothness is disputable.

So stratified sampling is yet different kind of correlation than for example correlation in Many Light methods.


Display that supports full CIE xyY color space

No, most likely these kinds of displays do not exist, at the time of writing this post. Although the negative is hard to prove. And in this case i don't have deep enough understanding of the lore.

Reason for me saying this is that usable displays need some serious miniaturization. The miniaturization process is quite expensive and requires some serious investment. There should be quite massive patent trail if this was indeed true. So we should look in patent databases for this trail.

Second, having such tech probably will not yield full color space, at least initially. Because the filter can only filter out colors that the back light can generate. Most probably therefore this is some kind of projector technology at first. Also filters probably have a practical limit to how much they can be tuned.

Third, if/when such tech is available it must recuperate the development cost by selling enough units to overcome the capital investment. There is a likelihood that this is one of those things that can not be produced without the miniaturization step like digital cameras. So keep a lookout for a killer application for this tech.

Some major downsides of this kind of tech is the fact that you filter out light. This means it eats up part of the energy input. This leads to a heat dissipation problem, which for perfect narrow band filters is actually pretty huge part of the emitted light. Lot of energy goes wasted, and needs to be engineered around.


What prevents older GPUs from supporting Vulkan?

So, I'll start by saying I'm not a driver developer, but I have read many comments and docs in this regard.
First of all, we can see how Khronos's own slides on presentation day were mentioning some rather vague "any OpenGL ES 3.1 GPU" (or desktop 4.X). This means something added around that mark would be the secret to it. Compute shaders are definitively [at least one of] the things, being confirmed here, by an Intel developer, and in the spec with no possible unsupported value for MaxComputeWorkGroupSize and this likely smoking gun:

If an implementation exposes any queue family that supports graphics
operations, at least one queue family of at least one physical device
exposed by the implementation must support both graphics and
compute operations.

In addition to that though, it could also be there are other mandatory capabilities (such as indirect draws or load&store, mentioned in the comments above too). But I have some slight difficulty interpreting the document. With the exception of robustBufferAccess, it seems like just about anything else big you could imagine is optional (from anisotropic filter, to geometry and tessellation shaders, to any special number format other than good old float32)
This being the most hypothetically simple case then, doesn't mean it's all fine and dandy. Not having virtual memory will make your life a hell for example, and lack of other architectural features may basically nullify whatever theoretical advantage in speed the API has.
These links should also answer your wonders about ATi cards. Likely same story for NVidia then (aside of perhaps some microbenchmarks, I'm not sure how much really workable Fermi's 2-years-delayed bare-bones DX12 support eventually is). As for Intel, I don't know what you are talking about, Gen8 is supported since Day1 and in fact even Gen7 shakily works now.
Going even further back, I guess if any the question becomes "what's so special about compute shaders again".
And, well, the thing isn't probably the very specific feature itself (because it's not that you couldn't already do some sort of general purpose calculation even before the unified shader model), but more like the whole general GPU architecture needed to support it. Check this for some backstory.
Before DX11 raised the bar for example, just think that you couldn't even run more than a single "task" on a Tesla GPU, without having to call a context switch (with comparable limitations also likely existing for TeraScale 1 and Gen6). And may God save us from when pixel and vertex units were separated hardware.
fun fact: it turns out that if you are a low-end kind-of-modern mobile gpu (rather than an old desktop card from a time when certain concepts hadn't even been invented yet), engineers can cut you down so much that even if you just sport D3D 9_3 feature level that's still potentially enough to support Vulkan.
EDIT: for such somewhat twisted reasons, it can also happen that while you are just GLES 2.0 compliant (and compute shaders themselves aren't supported atm, even though the architecture would be capable) a restricted version of Vulkan could also be possible. It doesn't give you everything, but it can still lead to benefits over just "old apis".


Ordering a set of unorganized points along a curve

You have an instance of a problem called curve reconstruction from unorganized points. Now that you know what to search for you'll find several methods, such as the crust, NN-crust, etc. Here are a few links:

The Crust Curve Reconstruction Applet
Curve Reconstruction by Tamal Dey
Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, book by Tamal K. Dey, Cambridge University Press, 2006

Since you're dealing with curves and the samples are dense, I suggest you compute an Euclidean minimal spanning tree.


Is it possible to override or disable blending per pixel

You seem to be using additive blending against its purpose. Additive blending is supposed to represent light from multiple sources being combined. It is not physically possible for one source of light to eclipse another.

Furthermore, even if you hack an alpha of exactly 1 to mean "opaque", you will get a strange circumstance where an alpha of 0.99 is quite far from "nearly opaque". So if you're animating "opacity", then you're going to get a sudden jump from appearing to be transparent to completely opaque.

Lastly, opacity with blending can only be achieved if you render the objects in the correct order. So even if you use this hack on the pink square, it will only eclipse the sphere if the sphere is rendered before the square. Using this hack will lose you the order-independency of additive blending.

That last part makes what you want essentially impossible.

However, if you wish to persist in this, there is a way to do what you've asked for. You need to use dual-source blending (which means you can only be rendering to a single render target). This is a technique whereby you output two values from the FS to the same render target:

layout(location = 0, index = 0) out vec4 outputColor0;
layout(location = 0, index = 1) out vec4 outputColor1;

Both values can be used in the blending equation. This means there are two source colors. The index zero source color is the source color used directly in the additive blending equation. The index one source color is how you turn off the destination color and achieve opacity:

glBlendFunci(0, GL_ONE,  GL_SRC1_ALPHA);

With this blend function, if you want a fragment shader's output to be opaque, you set outputColor1.a to 0. Otherwise you set it to 1. The other components are irrelevant.

Of course, you must still suffer the limitations of dual-source blending. Namely, that you can only render to a single render target on most hardware.