Is there a tool capable of drawing a triangular linear gradient fill? I need to draw some shapes filled with linear gradients starting from every point and blending smoothly between points, like an OpenGL standard shading (I guess it is called GL_LINEAR or VERTEX_COLOR), i.e. GIMP / Illustrator / Krita / Paint3D, etc. Something fast and simple.
required result:

Most 2D graphics programs are able to do linear gradients with arbitrary orientations. If you don't mind a little work, it is possible to set this up to imitate the 2D linear interpolation across a triangle.
Set up two layers:

Pick two of the colors, say red and green, and set up a linear gradient between those two colors along the red-green edge.
In a second layer, set up a linear gradient between blue and transparent-blue (i.e. the same color with alpha = 0). Orient it perpendicular to the red-green edge.


Stumped on GLSL error C5041 (cannot located suitable resources to bind variable... possibly large array I have an OpenGL based graphics engine coming along quite nicely, but I'm currently stumped on a problem that arose after adding a new vertex shader output array.

The vertex shader is outputing the usual things one would calculate per vertex to minimise fragment processing - eg fragment locations in tangent and light space etc which are done on a per light basis with currently an 8 light max per lighting zone.  Structure as below.

#version 460
const int cMaxZoneLightCount = 8;

out vData
{
    vec3 vFragmentLocationWorld;  //  This vertice's location in world coords
    vec2 vTextureUV;
    vec4 vNormal;
    vec4 vFragmentLocationLightSpace[cMaxZoneLightCount];  // Light space location per light (up to 8)
    vec4 vFragmentLocationTextureSpace[cMaxZoneLightCount]; //  Transform for projective texture lights
    vec4 vViewLocationTangent;
    vec4 vFragmentLocationTangent;  //  Tangent space transforms for normal mapping
    vec4 vLightLocationTangent[cMaxZoneLightCount];  // Light locations in tangent space (up to 8)
    vec4 vLightMRPTangent[cMaxZoneLightCount];  //  MRP for tube lights in tangent space (up to 8)
    vec4 vTangent;
    vec4 vBitangent;  //  Pre computed vertex tangent/bitangent data.
}   vDataOut;

Everything was working fine until I added the vLightMRPTangent[cMaxZoneLightCount] array.  Adding that brings the total number of vertex outputs to 153 and I receive error C5041 when the shader compiles - "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.

Now, the interesting thing is - if I make vLightMRPTangent[2] instead of 8, this brings the number of vertex shader outputs down to 129 and it works.  Similarly, a vLightMRPTangent[3] which would put it up to 133 output components generates a different but verbose and nasty link failure message.

So it's looking a lot like my still formidible GTX970 only wants to send 128 components down the pipeline!! (tell me that can't be right...)

I'm developing on Windows 10 with GLEW v2.1 and the November 2019 nVidia driver.  I'm not using any other extensions/libraries, eg glm/glut (doing all my matrix work myself).

I can get around this by implementing subsequent features per pixel rather than per vertex, but that's a real pain because its going to result in sub-optimal efficiency which could become a big problem later.

Any ideas anyone?

Cheers,
MWS

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.


MipMaps for Signed Distance Field Is there some algorithm that keeps details when creating mipMaps for SDF?
For example group of 4 pixels when only one is above threshold will lose this pixel with bilinear and creating mipMaps with 'max' of those values will add noise.
When purpose of SDF is keeping the same image in lower resolution what is the best way to downsample this image?

For generating SDF i use 8SSEDT

When you are making an SDF, you commonly have infinitely detailed data (like, bezier curves making up a letter) that you are making into an SDF image of a specific size.

If you make one that is 64x64, the first mip will be 32x32. The right way to make that mip is to do the original process of creating the SDF texture from the source data, but do it at 32x32 instead of 64x64. Repeat for the other mips.

It will break down at lower resolutions though, but that is just the nature of how SDFs work. The more correct, but slower way is to do super sampling. Take multiple samples at different places in the pixel and average the result.


How to calculate ray In ray-tracing technique critical point is to calculate rays which came out from eye $E$ to target $T$ through pixel $P_{ij}$ on viewport. The "viewport" is represented as rectangle divided to square pixels - this rectangle is perpendicular to line which go through points $E$, $C$ (viewport center) and $T$. The ray (red line on image) is represented by point $E$ and unit  vector $r_{ij}$ (not shown in picture but it lay on red line) - below is picture which show "geometry" - but what are the formulas to calculate $r_{ij}$?

The given input values are:

eye position $E$,
target position $T$,
field of view $\theta$ (angle, for human eye $\approx 90^\circ$),
number of square pixels $k$ (horizontal direction) and $m$ (vertical direction).
$i,j$ processed pixel indexes where $1\leq i\leq k$ and $1\leq j\leq m$
we also know vertical $w$ vector usually equal to $w=[wx,wy,wz]=[0,1,0]$ (not shown on picture) which indicate where is up and where is down

The orthogonal vectors $v$ and $b$  (and $t$) on picture are determined by $w$ and $t=T-E$ and maybe will useful in $r_{ij}$ calculations. The $d$ and pixel size is arbitrary and don't change the result because of fixed $\theta$.

Question: How to calculate unit vector $r_{ij}$ knowing input values described above?

Read up on the basics for ray-tracing here,
Usually we don't mess up with viewports and stuff in raytracing, So I'm just telling you for the case where viewport equals the Image Width and Height.
There are two cases when the field of view changes. Either you move the image plane back and forth or you increase the size. We choose to change $d$ ( former approach).
Calculating ray is simple when the camera is aligned with the world, all you have to do is
$d = 1/tan(\theta_{fov}/2))$
$P_x = P_x + 0.5$
$P_y = P_y + 0.5$
$aspect\_ratio = width/height$
$ray.dir.x = aspect\_ratio *(2*P_x/width) -1$
$ray.dir.y = (2*P_y/height) - 1$
$ray.dir.z = d$
The $Z$ coordinate should be negative or positive depending on whether you are using a right handed or left handed coordinate system. $P_x$ and $P_y$ are pixel coordinates offset by $0.5$ to get the center of the pixel.
The process is simple. You first map your image to NDC space (-1, 1). However to account for non-square images we scale the $X$ coordinate by Aspect ratio so it's $[-a, a]$ in $X$ and $[-1,1]$ in Y. The ray's direction through the pixel is then given by above formulas. You might have to flip the $Y$ coordinate if the image coordinate's origin is top left instead of bottom left.
Note however the link bases all their coordinate systems and space names on RenderMan which is quite different from OpenGL. For camera that isn't aligned with the world coordinate you have to multiply by the transformation matrix as described by bernie in his answer
EDIT:-
First of all let's clear up on -ve and +ve $d$. For right handed coordinate systems you always set $ray.dir.z = -d$ and for left handed $ray.dir.z = d$ This is because in camera space there is no concept of half rays having -ve Z and half +ve, that happens in world space. When you multiply by the transformation matrix it takes care of these cases for you since the transformation matrix is designed keeping in mind whether you are working on a left handed or right handed system. I know i said that you always set it to +ve $d$ but i was wrong in the comments, sorry.
Now coming to your other question. You need the vectors $b,v,t$ and $E$ for creating a transformation matrix. Usually in raytracing you create your camera and initialize its transformation matrix to the standard case (aligned with world space) Then when you move your mouse or something you create a respective rotation matrix and transform the original camera matrix to keep up with these changes. Then when calculating the ray you multiply it as I said above to get ray direction easily. So you probably need to manage your own Camera first.
Since you aren't managing in this case you explicitly need to find these vectors. You mention you have the $w$ vector which is global up. $t$ is easy to find as you say
$t = T-E$
However remember this is the viewing direction not the basis vector. For right handed coordinate systems, the basis vector for $Z$ is $-V_{dir}$
For $b$ which is Camera's right vector. You do,
$ w \times t = b$
This gets you the Camera's up vector. Then you do,
$ t \times b = v$
to get the Camera's up vector. This works as long as $t$ doesn't equal $w$ which is the global up.
So after you have these you can create a camera transformation matrix with $c_1, c_2, c_3, c_4 = b, v, t, E$ respectively.
EDIT2:-
Instead of following above approach you can also do Gram-Schmidt orthogonalization which is more standard in this case. Using this you get the Camera's up vector $v$ as
$v = w - (t.w)\hat{t}$
Then side vector as,
$b = v \times t$
For right handed systems. For left handed systems you need to change the ordering of cross products.


Physically Based Shading for Diffuse surfaces So I am currently in the process of implementing Physically based Shading in my pathtracer using microfacet models and I'm quite stuck at comprehending light interaction with diffuse surfaces.

First of all I want to get a clear concept of how surfaces actually get their color. We all know that the color of any surface is due to their property to absorb light of certain wavelength in the Visible region of the spectrum. More specifically, according to the answer here, when light hits an atom or molecule it gets absorbed if the electrons have the same vibrational frequency as the light. Which is the reason for the color of a surface. Now let's see what happens when light interacts with a diffuse surface.

When Light hits a diffuse (dielectric or non-metal) surface 2 things happen. It gets reflected specularly or it gets refracted, scattered, and re-emitted which we call "diffuse reflection". The amount of light that gets reflected/refracted depends on the Fresnel Equation which are wave-length dependent. This gives off the hint that an RGB triple also arises due to wavelength dependent IOR and thus maybe the reason for the color. So here's the main confusion.

When light hits a diffuse surface and gets reflected specularly it's possible that the atoms or molecules at the interaction surface absorb some of the light. This might be the reason for the color. On the other hand, the composition of light also changes in each of the R, G, B spectrum due to wavelength dependent index of refraction and Fresnel equations. So what's the real reason for the color? Is it the former or the latter or a mix of the two?  I've read some notes by Naty Hoffman where he also suggests using the Fresnel Reflectance values as the specular color when calculating a specular BRDF like Cook torrance. Adds a lot more to my confusion.

After the above has been clarified how does the whole thing tie with the light that got refracted, scattered and re-emitted?

Secondly since diffuse surfaces exhibit both specular and diffuse reflection why do I mostly see people using just lambertian model for diffuse surfaces? The proper way would be to use a BRDF for diffuse reflection + a BRDF for specular like Cook Torrance. Am I correct?
Thirdly shouldn't we be weighting the diffuse component with $(1-F_{in})(1-F_{out})...$ or more fresnel terms depending on, if the refracted ray undergoes total internal reflection. Are these factors built-in by default or what?

So after reading up some more research papers and the concepts of most people working in this field here and there, I've reached an answer I'm satisfied with. If someone disagrees or thinks there is a better or more correct way to think the problem do share your ideas.

1) First to answer my point 1. I've noticed that most di-electric surfaces' Index of refraction remains fairly constant over the visible spectrum. This means the Fresnel Reflectances remain constant and are quite low over the visible spectrum for normal incidence. For angles near 90 degrees, even rough di-electric surfaces start reflecting the incoming light specularly. You can see this data here

However in the case of metals the IOR or more specifically the Fresnel Reflectances take on the exact same value as the color (in case of gold and copper). From this I conclude that,

For metals where Fresnel Reflectances (FR) vary greatly over the visible spectrum, FR is linked and is just a consequence of the surface of metals absorbing photons of certain frequencies. This means for Gold, the electrons at the surface absorb the blue-end of the spectrum, the remaining golden colored light either gets reflected or refracted. Thus the Fresnel Reflectance is golden in color which we can also call the "Specular Color".
Note that the absorption depends on whether there are electrons available. It's possible for some blue photons to refract or reflect if there aren't much electrons for absorbing to begin with.

In-case of di-electrics the FR don't change much over the visible spectrum. However we can see color. The possible explanation is that the color in case of di-electrics comes from within the surface. That is, there are no such electrons present at the "interface" that absorb certain frequencies. Else we would have seen different FR for different wavelengths. The electrons absorbing wavelengths of certain frequencies come from within the surface, like pigments lying inside a liquid. Hence for di-electrics FR is not really linked to the concept of electrons absorbing certain frequencies imo.

This makes sense to me as colored metals (gold, copper) tint the reflections with their color. However certain di-electrics don't such as a polished marble floor. The reason for that again is that in case of metals the cause of color i.e. absorption by electrons occurs directly on the surface. The reflected light thus has a different composition for R,G,B giving us the tint. However for di-electrics the cause of color lies beneath the surface. Hence the reflection is non-tinted.

Thus simply stating for metals FR is the same as the albedo/color of the surface. For non-metals or di-electrics FR is different from the albedo/color and just defines the amount of specular reflection.

2) The proper way would surely be to use a BRDF with both diffuse and specular components since diffuse surfaces reflect greatly at near-grazing angles.

3) Still don't know about this. It might be baked in or not. What I do know is that the diffuse component should surely get lesser and specular component larger as angle increases to 90.

Another interesting point to note is that the basic Fresnel Equations apply for transparent and Flat surfaces. For metals we have complex IOR making the equations a little more complex. Sebastian Lagarde did a comparison here. Fresnel equations don't apply to rough surfaces but for microfacet models where we assume each facet to be perfectly specular we can maybe. Either way they are a good way to approximate the behaviour for increasing reflection near 90 degrees.


Given a composited image, is it possible to find the color and opacity of an overlaid shape? I have an image that I'm trying to recreate programatically using Pyx in Python. It seems that there's an overlaid circle covering the color wheel. I'm trying to see if there's a way to, given the starting and composited RGB values for each of the 8 colors shown in the image, as well as the assumption that the overlaid shape has uniform RGB color and opacity, to find said shape's color and opacity.

However, seeing that I'm not familiar with alpha blending formulae, I'm at a loss as to how to find this out. How could I go about this? I've done some research using the info here, but I can't seem to find a converging answer using the system of equations.

You can solve the colors by solving a system of linear equations if you make few assumptions:

The alpha of the color wheel is constant (i.e. same for all colors in the wheel)
The beige background extends half way through the color wheel, and is constant for top and bottom halves of the image
The background in the center is constant for all colors
The alpha blending equation is the standard $f=c*\alpha+b*(1-\alpha)$, where $f$ = final color, $c$ = color on the wheel, $b$ = background color, $\alpha$ = alpha of the color wheel

If you now pick two colors with the same beige background (e.g. green and yellow), and feed them into the above alpha blending equation you get 4 equations with 4 unknowns, which you can then solve. I.e.

$$f_1=c_1*\alpha+b_1*(1-\alpha)$$
$$f_2=c_1*\alpha+b_2*(1-\alpha)$$
$$f_3=c_2*\alpha+b_1*(1-\alpha)$$
$$f_4=c_2*\alpha+b_2*(1-\alpha)$$

where $f_1$ & $f_2$ = brighter & darker green colors respectively, $f_3$ & $f_4$ = brighter & darker yellow colors respectively, $c_1$ & $c_2$ = the unknown green & yellow colors respectively you try to solve, $\alpha$ = alpha you try to solve, $b_1$ = beige background color, $b_2$ = unknown background color in the center.

Then you can repeat this process for all the colors, or because you solved $\alpha$ you can use this information to solve the rest of the colors simply by:
$$c=\frac{f-(b_1*(1-\alpha))}{\alpha}$$


How to implement a realtime 2D light renderer with fog/colored light on the GPU? Since long ago I wanted to implement a 2D lightning algorithm based on an idea I saw on YouTube. The video is realtime, but it runs on the CPU and the resolution is pretty low. I'm curious if anyone has an idea how to do this on the GPU.

The algorithm works the following way:

We have light data maps, these hold the color of the material (e.g. a red glass has 0xFF0000) and how transparent that pixel is.
Work out the light values of each pixel in growing circles from a light source. In other words, first calculate values right next to the light (8 pixels), then the neighbours of these pixels and so on. The color of a pixel is its value from the lightning data map, its alpha equals: (alpha of the pixel next to it closest to the light source - own alpha). So it is some kind of ray casting algorithm that calculates value for each pixel and can handle colored glass and fog/smoke.

So the CPU implementation is pretty trivial. My problem is that I want to use this in a mobile game, but I don't know how this would work as a shader.
How can this be implemented on the GPU (that would run on mobile, so with OpenGL ES 2.0/3.0, maybe with Metal - if this is not possible then with OpenCL/CUDA)?

Note: I am not looking for full implementations, just ideas/shader pseudocode how this would be possible.

If your wall geometry is vector graphics you can simply extrude the segment away from the light position. This means 2 triangles per draw call, all the extrusion offsets can  can be handled in the vertex shader.

Image 1: For each wall generate a shadow volume extrusion.

Quick and extremely dirty sample implementation of shadow volumes here:

http://webglplayground.net/saved/AeN6yoNGih (please do not save your own version, fork instead)

Now since your shader can color the triangles as they see fit you can apply a shader on the triangles that is colored. Just like you would render transparent surfaces. To do this proper you may need a offscreen buffer for getting a proper color accumulation mode.

Image 2: Coloring the volumes based on distance to light.

Certainly the coloring algorithm may be whatever you like. for example the color could become darker the nearer you are to the extrude edge etc.

And here is very quickly done extremely dirty live example of colored shadow volumes:

http://webglplayground.net/saved/9xgxDbtY7f (please do not save your own version, fork instead), very bad code style done on the run (and on my phone).

This is just one way hopefully others will elborate. You can also use the exact same methods as you would in 3d. As for nonuniform fog, you could just use a raymarcher.


Compute Shader PSO Dx12 I am new to the DX12 world and I am currently trying to tweak the nbody_gravity DX12 sample, but appending or calling another Compute Shader which is to add 2 buffers to produce an output in a different buffer.

Right now, I have made a call to my ComputeBufferAddition shader and was wondering if I need a separate Compute PSO to do this, or can I reuse the one already present to call the NbodyGravity.hlsl

If I understand you correctly, you've added a new compute shader. In DX12, you'll need at least one separate PSO for each shader, since the shader code is part of the PSO.


Path tracer - multi layered materials and importance sampling I'm currently trying to implement a Monte Carlo path tracer. I've done some research and it seems that a common approach to materials is to use a layered model. Something like this:

When light hits the surface, Fresnel tells us how much of that light is reflected by the first layer and how much goes to the second, and so forth.

So I did something similar, but simpler: only one layer of specular and one layer of diffuse. No transmittance yet. So far so good, I use a simple cosine-weighted brdf for my diffuse and the Cook-Torrance microfaceted model for my specular.

Now comes the hard part: what should I do once a ray hits the surface?
Normally, I'd pick the brdf corresponding to the surface material, sample an incident light direction, evaluate the brdf, and divide by the right probability distribution function.

But here, a surface hit effectively corresponds to multiple materials. The naive way to handle this would be to sample once for each layer hit. But this clearly is source of a huge performance hit, causing my path to effectively become a tree.

Is there a better solution?

Wenzel Jakob et al presented a framework for layered Materials at SIGGRAPH 2014. Section 6.2 explains importance sampling. If you prefer code over equations, the method is implemented in the Mitsuba renderer.


Vulkan: Swapchain image count with VK_PRESENT_MODE_FIFO_KHR I'm working on an engine for Win32 exclusively. Can I safely assume that the flag VK_PRESENT_MODE_FIFO_KHR will always generate 2 and only 2 images for the swapchain?

There is nothing in Vulkan which guarantees or requires this. So even if it were a safe assumption today (if it were enforced by Windows in some way), all it would take would be one Windows update to break you.

It's best to work with what you're given, even if what you're given may be more than you would prefer.


Y axis inversion in 3D rasterization What is the correct way to invert the y axis during the 3D projection?

I see a lot a people doing:

pixel_x = (x_world / z_world + 1) / 2 * ScreenWidth(); // This is right
pixel_y = (1 - y_world / z_world) / 2 * ScreenHeight();

But by inverting like this, we get an incorrect position of pixel_y because what this does is saying that pixel_y is 1 when y_world is -1 and 1 when y_world is -1. This seems right but don't forget that a point at x == 1 in NDC space will map to pixel_x = ScreenWidth() and therefore won't be visible. In contrast, a point at x == -1 in NDC space will map to pixel_x = 0 and WILL be visible.
So if we invert like this, a point at y == -1 will become pixel_y == ScreenHeight() and WON'T be visible but a point at y == 1 will become pixel_y == 0 and will be visible.

I think that the correct way of inverting y is by first calculating pixel_y like pixel_x and then and only then invert it in pixel space:

pixel_y = (y_world / z_world + 1) / 2 * ScreenHeight(); // Y points up
pixel_y = ScreenHeight() - 1 - pixel_y; // now it points down

So what is the correct way to invert the y axis during the projection?

Let's look at your formula:

pixel_y = (y_world / z_world + 1) / 2 * ScreenHeight();
pixel_y = ScreenHeight() - 1 - pixel_y;

Let's call y_world / z_world for short a, H for ScreenHeight(). So you have:

Y = (a + 1) / 2 *H
Y = H - 1 - Y

Let's replace the first in the second:

   Y = H - 1 - (a + 1) / 2 * H
=> Y = H * (1 - (a + 1) / 2) - 1
=> Y = H * ((2 - a - 1) / 2) - 1
=> Y = H * (1 - a) / 2 - 1

Which is the formula you said every one uses (except with an off-by-one error):

pixel_y = (1 - y_world / z_world) / 2 * ScreenHeight();

Off-by-one error aside, looks like you have the right understanding, just didn't work out that the formula everyone uses is the optimized version of what you came up with.


What objects do get loaded into GDDR? I currently have a 4K monitor and want to buy a new graphics card. My choice would either be the RTX 2080 or the RTX 2080 Ti. Now I need to know which one I really need. The Ti variant has 12 GB of GDDR6 instead of just 8 GB (and more shader cores of course, which makes the card faster)

My question is, what elements do actually get loaded into the GDDR6 memory? Is it only the textures or is there other stuff that needs to be loaded into the GPU memory? Does the memory consumption differ when comparing 1080p(HD) and 2160p(4K)? What if you would run a game at 4320p (8K)? People say that you need more GPU memory if you have a higher resolution, is this really true? And what things do you need to take into account when calculating the rough memory usage?

Typically you will need VRAM to store your frame buffer (memory used to store pixels for use with the display and for rendering). This would usually be 4 bytes per pixel so a 1080p frame buffer is 1920x1080x4 bytes (1 byte each for R,G,B components + 1 padding byte). Your card is going to use 2 of these for double buffering so it can use one for display output and the other for constructing the next frame. Any increase in resolution will require an increase in VRAM usage. If HDR is used then you're looking at 16 bytes per pixel so you can use floating point accuracy. Certain types of post-processing special effects may also need additional rendering buffers which are some division of the screen resolution so will consequently use more VRAM if using a higher resolution.

After that the majority of VRAM is going to be allocated for textures which for a typical game is the biggest user of VRAM. Then mesh data needs storing in VRAM which usually consists of vertices storing information like geometry position/normals/colours/transformation matrices/etc. Finally compiled shaders will need to occupy VRAM but they should be low down on memory usage compared to textures and mesh data. There will be other uses for VRAM too depending on how the game was engineered so this is not an exhaustive list of what VRAM is used for.

In short: Display resolution will change the amount of VRAM required but not by a large amount. For a video game most VRAM is from textures which are usually defined by the quality settings of the game and are not affected by display resolution. The 12gb card you mentioned will allow higher texture resolution but with your choice of 1080p or 4k display resolution making little difference in VRAM usage. However for 4k it makes sense to use the highest texture quality.


How to use my Ray Tracer in 3DS Max If I want to use my own Ray Tracer in a program like 3DS Max to render geometry, how could I do this? Can someone explain to me what I need to do and where I can learn to use an SDK to make this happen? Is this worth it to render test scenes to compare and test my ray tracer?

You can do this by writing a renderer plugin for 3ds Max. This gives you the same kind of access as the built-in renderers, including a settings dialog, a preview window, and an interface where you can write the final frame of a full render (and 3ds Max will write it to the output file). The renderer plugin gets full access to the scene graph when the user hits "Render" (or when the preview window is in use). Any complex geometry (such as subdivision surfaces) will already have been converted to a triangle mesh for you.

PaulHK already linked the official Programmers' Guide online. You'll also find it in the help files that are installed with 3ds Max, along with sample source code for a trivial renderer plugin. Because your plugin needs to link against the 3ds Max SDK, you'll need to compile it with the same version of Microsoft Visual Studio that was used to compile the particular version of 3ds Max you're targeting. (This means that if you want to target multiple versions of 3ds Max, you might need multiple builds.) Again, how to do this is described in the Programmers' Guide.


How to decompose a complex mesh to simple geometry shape programmatically? I have a complex geometry mesh object, which is an irregular shape.

I want to redraw that complex geometry mesh object using multiple simple primitive shapes.

For example, I want to use cuboid, sphere and cylinder to represent a complex geometry mesh object.

I am given only the vertices points, triangular of that complex geometry mesh.

How do I decompose the geometry shape into cuboid, sphere, cylinder.

Please ask if you need details.
Thank you.

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

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

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

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


Why if we rotate an object by R and then translate it with T, from the object perspective, we're actually applying $-T$ and then $-R$ I've been introduced to local coordinates in contrast to the global ones which I was used to work on, where we have basically the camera at the origin.
For example, I've the following picture of a cube:

According to a slides that I've:

the object is rotated about the x-axis by $R$ and then translated by $T$
from the object's perspective, the world is first translated by $–T$ and then rotated about the (object's local) x-axis by $–R$

Not just the sign but also the order of the transformations changes. Why is that?
Note: I've some ideas, clearly, but I would like to hear a good answer with a mathematical explanation.

If you have object$\rightarrow$world space transformation matrix:
$$M=T*R$$
then inverse (i.e. world$\rightarrow$object) of this transformation matrix is:
$$M^{-1}=(T*R)^{-1}=R^{-1}*T^{-1}$$
So the order of multiplication of matrix inverses is reversed per matrix inversion rules.


What's a parent vector space or coordinate system? After asking this question, a few new terms that I had never heard of came up. Note, I'm quite familiar with linear algebra, but I've never heard these terms in the context of linear algebra.

Comments like

  In my example, you can use the columns to get the basis vectors of the coordinate system it describes. The columns are in the coordinate system of whatever the parent coordinate system is. If there is no parent coordinate system, they are in global space. Else, they are in the coordinate system of the parent.

What's a parent coordinate system? When is this term used? Why is it called a parent coordinate system?

Then the author of the comment tries to explain me the meaning as follows:

  Matrices can be parented off of each other, but that is probably too confusing to visualize as you are just trying to learn things. Just imagine that if there was a matrix hierarchy, that all the matrices are multiplied together into one matrix M then you can ignore hierarchies.

This hasn't really cleared things up. What is it mean that matrices can be parented off of each other? What is it meant by matrix hierarchy?

I know that if you have $m$ $A_1, A_2, \cdots, A_m \in \mathbb{R}^{n \times n}$ matrices which represent transformations, any combination of products of these matrices represents clearly a new transformation. For example, say that $A_1 * A_2 = B_{12}$. Suppose now that we have a vector $v \in \mathbb{R}^{n \times 1}$. Then the following two statements should clearly be equivalent

$$A_1 * A_2 * v$$

and

$$B_{12} * v$$

but the transformations used are different, i.e., in one case we use two single transformations (i.e., $A_1$ and $A_2$) and in the other case we use only one transformation, namely $B_{12}$.

Now I don't know if this has something to do with "parent coordinate systems", but I just wanted to show you a few things that I'm suspecting could be related to this terminology and concepts of computer graphics.

Final question would be: does it make sense to talk just about "parent coodinate systems" or does it also make sense to talk about "parent vector spaces"? Why?

You have to step outside the world of mathematics for a while and look at what we are trying to achieve. Mathematics in its purest form only tells us what kinds of properties certain constructs have, it does not tell us why and how that would be useful.

The modeler's perspective on things

So we have to look at the problem from modeling perspective. In this perspective it is mostly irrelevant how the mathematics work. As long as it provides the modeler with a system that yields with a understandable toolset to do his work everything is as it should be.

It is frequently beneficial to describe things such as physical objects (creatures, mechanisms etc.), forces or any number of other things independent of each other. Either because it's easier to think in one orientation or just simply because you want to move/rotate/scale objects out of convenience.

In practice you want at minimum that the camera is separated from the rest of the objects. While in more complex cases you want to have a more rich system. For example a bug is walking straight ahead on a straw. For practical reasons it would be neat if the bug only move forward in relation to the straw while the straw sways in the wind in relation to the world and the camera is independent of the straw. Similar modeling cases happen a lot, in human hands, robotics, car simulations, Finite object modeling etc.

Computational perspective

The rendering and other functions need to be able to transform elements from these modeling hierarchies to each other. For example you need to know the point location in camera space to render. Preferably all this space transform happens automatically. For this purpose the modeler tells your application how the modeling elements are structured in relation to each other, a hierarchy, for modeler's benefit.

Although this could be done in any number of ways it is commonly done with a tree structure, much like a filesystem with much the same effect. Each level stores in addition to tree information a affine matrix that describes the transform to its predecessor in the hierarchy. Mainly because this takes care of two core issues. The tree structure is easy to traverse and find the path to any other part. The matrices solve the problem of needing to do a lot of work transforming form a transform from one hierarchy space to another.

So the user provides a tree where each object describes the transform required to transform the object to the coordinates of the object it is described in relation to, the parent. This parent in turn in turn describes the transform to its parent all the way to the world. Since all objects share one common ancestor, world, we can easily traverse the tree to find a transform path from any one coordinate system to another coordinate system.

Since linear transforms are invertible, we do not need to store a description separately for moving in the opposite direction, away from world towards the children/leaves of the tree structure. All we need to do is to invert the matrix. This is almost always needed as it's practical to describe camera as a separate object under the world, there is no reason to describe the cameras transform from world to camera just treat it like any other object.

To compute a point from one space to another you do as follows:

Use the tree to find a relationship between spaces.
For each step on the way pre multiply your matrix/ or its inverse if you're traversing away from world. **

Example:  You have the following hierarchy because it makes sense (this way you do not need to model each petal separately)

World
  |
  +---- Flower
  |      |
  |      +--- Petal 1
  |      |
  |      +--- Petal 2
  |      |
  |      +--- Petal 3
  |
  +---- Track
         |
         +--- Boom
               |
               +--- Camera

To render Petal 1 you need to transform the vertices of petal one into the camera object space and from there to perspective space etc. Your calculation would be:

$$
T_{\text{Perspective}} \cdot T_{\text{Camera}}^{-1} \cdot T_{\text{Boom}}^{-1} \cdot T_{\text{Track}}^{-1} \cdot T_{\text{Flower}} \cdot T_{\text{Petal 1}} \cdot \vec{v}_{\text{PetalPoint}}
$$

This way you can model a flower in a flowerpot totally independently from  from the robot shaking the camera about. At the same time freeing the modeler of the need to do complex trigonometric calculations, and in fact a big load of mathematics. Pretty neat.

Now that you understand why, you should understand also that we do not have any limit to complexity of the hierarchy to
facilitate a broad range of things you could do.

This kind of hierarchy is called a scene graph and such things can be found in web pages, vector and CAD applications, many scientific modeling applications, most games.

This should answer why as well as the less exciting how.

Do we absolutely need these?

No, we do not. We can dispense all the matrices and describe all of our data directly in the camera's final coordinates. It's just that this is horribly complicated in 98% of the cases.

In practice we need this hierarchy if we try to do even something more complex than a stationary box. Most of this deign is to make scene modelers' life easier. So that simple operations make more sense.

* why do we call it a parent child relationship? Because it's a tree, and earliest tree graphs are genealogical studies, aka family trees. Where the previous level is simply the parents and the next one is their children.

** or the other way around if you want to transpose your calculations.


OpenGL VertexArray Data "Retention"? After calling glVertexAttribPointer to associate data of the currently bound vertex array with data from the currently bound GL_ARRAY_BUFFER, I mentioned that I can simply delete the used buffer without it affecting the rendering.

What actually happens with the data within the buffer when calling glVertexAttribPointer? It seems like the data from the buffer actually get's copied into another memory location that the vertex array uses.

Deleting an OpenGL object is merely a suggestion. Deleting an object will unbind the object from any binding point it is currently bound to. However, buffer objects are not "bound" to VAOs. They are attached to VAOs.

When you call glVertexAttrib*Pointer, you attach a buffer object to the VAO. The buffer object to be attached is the one bound to GL_ARRAY_BUFFER. Unbinding that buffer, or even flat-out deleting it, will not undo the attachment.

And an OpenGL object will continue to exist so long as it is attached to a container object.


BRDF that interpolates between diffuse, glossy and reflective? Is there a way to obtain a parametrized BRDF that smoothly interpolates between diffuse, glossy and mirror? For example, $\lambda = 0$ would be perfectly diffuse, $\lambda=0.5$ glossy and $\lambda = 1$ a perfect mirror. Linear interpolation seems very wrong here.

Any microfacet BRDF with a roughness parameter will do something like this—for example using the GGX or Beckmann NDFs. When the roughness goes to zero it becomes a mirror; as roughness increases the reflection will be wider, and in the high-roughness limit should be essentially Lambert I think. Roughness is not necessarily limited to [0, 1] as roughness values higher than 1 are possible, but typically roughness = 1 will be very close to Lambert already.
One thing to note about the roughness = 0 limit is that the NDF will become singular (a delta function), so will very likely break the shader code by producing infinite values or NaNs and such. So as a practical matter it might be necessary to special-case that, or clamp the roughness to some low minimum value like 0.0001.


kinematics and dynamics of a sphere in a spring mass system? I am attempting to code a simple spring mass system simulation in which a sphere pendulus hangs from a string (a spring) by the top and then another sphere (controlled by the user) can move and interact (collide) with this hanging sphere.

I have already coded the dynamics of the spring part of the simulation, but I do not know enough to add the rigid body dynamics. I would like either an explanation or a source to understand how to algorithmicaly do this simulation.

The rigid body simulation is very similar to the point mass case except for
that we have to handle rotational motion (orientation and angular momentum).

In addition to common particle attributes such as mass, position, and linear velocity, we will need to store initial moment of inertia $\mathbf{\hat{I}}$,
current angular momentum $\mathbf{L}^n$, and current orientation $\mathbf{R}^n$.
If you are using a data driven particle system, this step is as easy as declaring a few new attributes.

Contract to the mass, the moment of inertia at current time step $\mathbf{I}^n$ depends on the current orientation $\mathbf{R}^n$: $\mathbf{I}^n=\mathbf{R}^n \mathbf{\hat{I}} (\mathbf{R}^n)^T$.

The kinetic of a rigid body is analogous to the linear motion:
$$
\begin{align}
\dot{\mathbf{R}} &= \omega^* \mathbf{R} \\
\frac{\mathbf{R}^{n+1} - \mathbf{R}^n}{\Delta t} &= (\omega^{n*}) \mathbf{R}^n \\
\omega^n &= (\mathbf{I}^n)^{-1} \mathbf{L}^n
\end{align}
$$
where $\omega$ is the angular velocity and $\omega^*$ is the "cross product" matrix.

For dynamics, we also have a similar version of Newton's "f=ma":
$$
\frac{\mathbf{L}^{n+1} - \mathbf{L}^n}{\Delta t} = \tau^n
$$
where $\tau$ is the torque.

Because there will be interactions between rigid spheres, you will also need to implement the collision detection for spheres.

Now we have known the kinematics and dynamics of rigids. The only thing left is how to solve (integrate) above equations. The naive forward Euler may not give stable result. A good introduction of this topic can be found at Witkin and Baraff SIGGRAPH course, and here is an another more recent SIGGRAPH course by Bargteil and Shinar.


Algorithm for constructing doubly connected edge list in 3d This post explains how to construct double connected edge list in 2d. One of the steps in the algorithm is to sort the halfedges around a vertex in clockwise order. However this will not work in 3d. We can project the halfedge coordinates onto 2d viewplane and sort them that way (if the construction is user interactive). However this would make the construction dependent on the user view.
What sort of algorithm would we use for 3d case of double connected edge list?

The problem statement in the linked post says that only the vertices and edges are input to the algorithm, but I don't think it's possible to do this unambiguously in 3D without additional input about the faces of the mesh. In the 2D case, since the input is specified to be a planar graph, the faces are unambiguous: any region in the plane contained within an edge loop, and empty of edges in its interior, is a face. However, in 3D, you don't know which edge loops should be faces and which shouldn't.
Consider a cube, represented as just vertices and edges: you would want the "usual" 6 sides of the cube to be treated as faces, but you wouldn't want the algorithm to create additional faces that stretch across the diagonal of the cube, internally. But there is no way for the algorithm to know that. Moreover, the vertex/edge mesh might not even be possible to assign faces to in a sensible way; it might have non-planar faces, might be non-orientable (e.g. Möbius strip) or non-manifold.
Typically in 3D applications we would have the mesh faces already defined, and we can assume it to be a manifold, orientable mesh. With the face data as input to the algorithm, such as by lists of edges or vertices in counterclockwise order around each face, then it becomes straightforward (if tedious) to figure out the half-edge relationships.


What effects are used to light this scene? I am interested how that image on the right of the slider (just albedo) can produce such a realistic looking scene as the scene on the left.
What effects (at a minimum) does this scene seem to be using. ie. what rendering features would be necessary to reproduce this scene?
Thanks
Apologies for the poor quality screenshot, for reference, it is taken from Joey de Vries 2017 tech reel at about the 1:05 mark.

The rendering engine that rendered this image is using a technique called deferred rendering, which first writes scene information (as seen from the camera) to seperate buffers (such as position, normal, and albedo buffers) and then calculates lighting for the image based off this information. It is important that we have position and normal buffers on top of the albedo buffer so that lighting can be calculated at each pixel (these buffers are not visible in your example, but they are there under the hood). As an example, take a look at the image below that shows the different buffers of an engine I worked on - it may help to better understand what is going on.

Once a buffer has been made with all of the lighting calculations, you can then achieve post processing effects by processing the buffer with various algorithms to produce the final image. Some post processing effects that are visible in your image are bloom (which adds "glow" to bright spots), motion blur and an implementation of screen space ambient occlusion (SSAO).
A full list of the rendering features can actually be found at the 1:02 mark of the video, I have attached the image here to make it easy to see. It may be worth googling what each individual post-processing effect does so that you can better understand the effect they have on the overall image.

Hope this was of help :)


How can I make a graphics demo without a frame buffer? I am programming a microcontroller - a tiny 8 bit computer that has about 100Mhz - 300Mhz CPU clock speed and 64K application RAM (actually ROM), but only a tiny amount of RAM (6K) - nowhere near enough for a graphics frame buffer.
So, I want to display an animated graphics demo on this machine.  It seems to have enough computing power to calculate animated graphics of some sort.
To get animated graphics to display, I will somehow need to have a computer program that each time it is called, returns a single line of pixels of one image frame, which is then displayed.  The display controller program continues to do this, calling line after line until it has displayed a whole frame, then it starts at the top again for the next frame.
Just to be clear, I'm not asking about the program that controls the display.  I'm asking about the demo program.  I need a demo program that yields its graphics one line at a time, which my display controller will then throw onto the screen.
I'm trying to imagine what sort of graphics program could work this way?  Presumably the display of some sort of mathematical formula.
Can anyone suggest techniques for graphics programming that work in this way, in which a function can be called, which calculates and returns a line of the frame, only when requested to do so?  Are there existing programs that work like this that I could examine?
I hope the question makes sense.  Any pointers in the right direction or hints would be appreciated.

This is a case where looking at the workings of more retro hardware would be reasonable. Older hardware had strong limitations in both memory and processing power. Your 100+Mhz chip is far faster than most consumer-grade chips of the 80s and before. So while those CPUs needed dedicated graphics chips to be able to render, your much faster CPU can probably handle the task adequately.
I would suggest starting with something like the NES's tilemap-and-sprite architecture. These architectures are designed to be both memory efficient (getting a lot out of limited storage space) and computationally efficient in a line-by-line output, as they generated pixel data and sent it directly to the display device at the expected speed of a CRT.
The broad idea is this. A tilemap consists of two parts: a series of tiles and a 2D array of indices into the tile map that represents the image being created. The tiles are typically 8x8, and on the NES were 2-bits-per-pixel and the tiles used palettes. Or more specifically, the index into the tile map includes not just the index of a tile but also the index of the palette to use with that tile. So a tile is not inherently associated with a palette; the association is made at the point of use (technically, on the NES, the tile map and palette map were separate, as each 2x2 block of tiles all had to use the same palette).
To allow for scrolling, the tile map is bigger than the visible screen, and there is an offset that represents where the top-left corner of the visible screen is within the tilemap. Let this offset be at position Xoff and Yoff.
You can see how this makes row-by-row processing trivial. To generate a horizontal row for the horizontal position Ypos (in screen-space), you need to get the starting pixel within the tilemap. That requires transforming the XY position (0, Ypos) from screen-space to tilemap space. So you add to it the vector (Xoff, Yoff), hielding the vector ``Xoff, Yoff + Ypos)`.
Note that when doing any mapping from screen-space to tilemap space, that the tilemap space should wrap around in both the X and Y axes. So whenever you compute a new pixel in tilemap space, you have to wrap it around the size of the tilemap space.
Now, we need to break down this tilemap pixel into two 2D components: the tile index within the tilemap that gives us this this pixel, and the pixel within that tile that we need to fetch for this pixel. The tile index is just the tilemap-space pixel integer-divided by the tile size. The pixel coordinate is the tilemap-space pixel integer-modded by the tile size. Given an 8x8 tile size, you're doing this:
ivec2 tilemap_pixel = ...; //Compute the tilemap starting pixel as above.
ivec2 tilemap_tile = ivec2(tilemap_pixel.x & ~0x7, tilemap_pixel.y & ~0x7); //Mask off the lower 3 bits.
ivec2 pixel_in_tile = ivec2(tilemap_pixel.x & 0x7, tilemap_pixel.y & 0x7); //Mask off all but the lower 3 bits.

So given tilemap_tile, we now have the index of the tile we are currently working within. And pixel_in_tile gives us the pixel we're working in. So we can fetch that pixel, whose value can be mapped into a palette to produce the final color for that pixel. Or we can use it directly.
To get the next pixel is pretty trivial. We just increment pixel_in_tile.x by 1, modulo the tile size. If the increment exceeded the tile size, then we also increment tilemap_tile.x by 1, modulo the tilemap size. And you keep going until you've filled out the row of pixels.
There are many opportunities for performance optimization of such an algorithm.
The tiles probably represent the largest data. A 128 element tile set of 8x8 tiles, even at 2bpp, is 2K. But the thing is, those can be stored in ROM, since you're probably not changing the tiles themselves. The size of the tile map (assuming it must be in RAM) depends on the desired output resolution and the tile size. A tile map for 8x8 tiles that can cover a 320x240 screen is 1,200 bytes. Not exactly tiny. You'll need to take up more memory if you want room for smooth scrolling (and thus a larger tile map).
That being said, it's also important to note that the "output size" doesn't have to be the actual size of the display device. For example, if you intend to draw to a 1080p display device, you could still render to an internal resolution that's, for example, 8 times smaller, 240x135. It's easy to modify this algorithm to essentially generate the same pixel value 8 times in a row, as well as reusing the same line 8 times per 1080p line. Indeed, it wouldn't be too difficult to have this algorithm allow for subpixel scrolling (scrolling in 1080p space, not 135p space) and even adding some filtering between pixel values. A 240x135 "output size" tilemap would only require 510 bytes for the visible region, so you would have more room for a larger scrolling area.


When is it better to upload partial model matrices to the vertex shader? As of now, when rendering my scene and while iterating through the scene graph, for each node its model matrix is calculated from the parent's model matrix and the scene node's pose. This is quite simple and already reduces the number of matrix multiplications to one multiplication per node and frame.

But all these matrix multiplications have to be done on the CPU and in every frame to be able to perform (multiple consecutive) movements of scene nodes very fast. The GPU, however, is probably much better suited to perform lots of matrix multiplications, so I'm thinking about sending multiple partial model matrices to the vertex shader instead of computing everything on the CPU.

Sending every single part (so the pose of every node) to the GPU probably does not make much sense, as in this case all the computations are done for every vertex instead of every node, which would actually decrease performance. But maybe scene nodes with lots of children or only non-moving children (relative to its parent) could be a place to split the model matrix and shift the multiplications to the shader.

So, when is it better to send partial model matrices to the shader and move the multiplication to the GPU? Or is it simply a bad idea to to this?

Doing math with uniforms is a shader won't usually get you any performance over doing it on the CPU. A CPU isn't slower than a GPU at doing matrix math, it just isn't structured so as to do large amounts of math in parallel. But you have to actually do that large amount of math to get a win. Sending extra data to the GPU just to have the GPU multiply two matrices together will rarely net you anything.

Now, say you have a buffer of skinning matrices. It might start to matter whether you transform them all into world space on the CPU or just pass an extra model-to-world-space matrix to the GPU. But even then it depends on your ratio of vertices to bones.


OpenCL ray tracer: which is better, geometry code on device side or on host side? I am writing a ray tracer using openCL, and following this tutorial http://raytracey.blogspot.com/2016/11/opencl-path-tracing-tutorial-2-path.html
However, I find that the author has two copies of the Sphere code, one in host in c++ and one in device in cl. This causes duplication, which I would like to avoid if possible.
Is there any way to avoid this? If there is, should the code for, say a sphere struct be in host or in device?

In order to pass data to the device side, in OpenCL you must create the sphere structure on the device as well (that is in the kernel). So you first create your structures as classes or structs on the CPU. The variables in the structs should be of cl_* datatypes. OpenCL provides typedefs for all primitive data types. Then create these structures on the GPU as well.

Care should be taken about data alignment when passing structures from CPU to GPU. If you have passed data in OpenGL, you'll know what this is about.

After you create your structures on the CPU, you encode them in a OpenCL buffer, and pass this buffer to the kernel.


row and column majored rotation matrix pre- or post- multiplied For column-major rotation matrices (right up forward in columns) do you right-multiply (post-multiply?) a row vector or left-multiply (pre-multiply) a column vector to result in a correct/valid transformation? Or are both "valid" but just transform different spaces?

In case I'm getting my terminology wrong, suppose we have 3x3 column-major matrix R. Is it R * V for column-major matrix, where V is 3x1? Or is it V * R for column-major matrix, where V is 1x3? What about for row-major?

Thanks so much for the help!

Edit: I believe my question needs further clarification. I am more confused about whether a vector, regardless if it's a row or column, is multiplied to the left or right of a row specific majored matrix. And vice versa for column-majored matrix, but it would be implied by answering either which one. I do understand the concept that transposing a matrix will just mean you have to transpose the vector and flip the order of multiplication, which will result in the same thing because you're multiplying the same elements the other way around. That is not the concern of my question (though thanks for those who answered that part). When I say row specific (or column), I'm talking about the way the right up forward vectors are positioned in the matrix. Though at this point, I think I already have figured out my answer just by typing this, but will leave it open for answers.

My question is simply this:
(sorry, I don't know how to format things here)

I have the following matrix composed of Right Up and Forward vectors:

Rx Ry Rz

Ux Uy Uz

Fx Fy Fz

This is a row-majored, orthonormal rotation matrix. Now I have a vector V as {V1 V2 V3} as either a 3x1 or 1x3 (right side or left side respectively, else the multiplication doesn't even work out). Is it R * V or V * R in this case of a row-major matrix? Again, not asking about 1x3 on left or 3x1 on right, but rather for a row-specific matrix, which way would produce a valid or meaningful transformation?

{V1*Rx + V2*Ry + V3*Rz, V1*Ux + V2*Uy + V3*Uz, V1*Fx + V2*Fy + V3*Fz} ?

OR

{V1*Rx + V2*Ux + V3*Fx, V1*Ry + V2*Uy + V3*Fy, V1*Rz + V2*Uz + V3*Fz} ?

I'm guessing the second, but would like clarification/confirmation. Thank you again!

Okay let us start by pointing out that a colmun major matrix is the same as a transposed row major matrix. So:

$$
{M_{cm}}^{T} = M_{rm} \tag{1}
$$

Then notice that matrixes have following properties. Matrix multiplication is associative (2a) and that the distribution of transpose reverses computation order (2b).

$$
A(BC)  =  (AB)C \tag{2a}
$$
$$
(AB)^T  =  B^TA^T \tag{2b}
$$

From these follow that the chain of multiplication events can be as long as one likes and all transpose does is inverse the computation. So given that we can conclude

$$
{T_1}\ {T_2}\ \ldots\ {T_n}\ \vec{v} = \vec v\,^T\ {T_n}^T\ \ldots\ {T_2}^T\ {T_1}^T, \tag{3}
$$

so calculating in column major order is the same calculation as calculating in row major orientation. The difference is that the order of computation is reversed. An interpretation of this is that the difference is the same as looking at the object from the outside or looking at the situation from the object out.

Formula 3 should provide you the insight. Just one more thing a column vector is the same as a transpose of a row vector.

Note: You are allowed to mix and match the computations as much as you like. All you have do is remember is that the other approach is just transposed.


Why does my lighting look incorrect? I have a problem with lighting calculations.
I am rotating the camera around a cube which was supposed to be illuminated by the light but the resulting lighting is very weird.
Check out the image above, fragment shader and vertex shader below.

//Vertex shader

#version 330 core

layout (location = 0) in vec3 pos;
layout (location = 1) in vec3 norm;

uniform mat4 model;
uniform mat4 view;
uniform mat4 projection;
uniform vec3 lightPos;

out vec3 ourNormal;
out vec3 fragPos;
out vec3 ourLightPos;

void main()
{
    gl_Position = projection*view*model*vec4(pos,1.0);
    fragPos = vec3(view * model * vec4(pos, 1.0f));
    ourNormal = mat3(transpose(inverse(view * model))) * norm;
    ourLightPos = vec3(view * vec4(lightPos, 1.0));
}

//fragment shader

#version 330 core

//Output variables
out vec4 finalColor;

//Input variables
in vec3 ourNormal;
in vec3 fragPos;
in vec3 ourLightPos;

//Uniform variables

struct Material
{
    vec3 ambient;
    vec3 diffuse;
    vec3 specular;
    float shininess;
};

struct Light
{
    vec3 ambient;
    vec3 diffuse;
    vec3 specular;
};

uniform Light light;
uniform Material material;
uniform vec3 viewPos;

void main()
{
    //Ambient
    vec3 ambient = light.ambient*material.ambient;

    //Diffuse
    vec3 normal = normalize(ourNormal);
    vec3 lightDir = normalize(ourLightPos - fragPos);
    float diffuseStrength = max(dot(lightDir,normal),0.0);
    vec3 diffuse = light.diffuse*(diffuseStrength*material.diffuse);

    //Specular
    vec3 viewDir = normalize(viewPos - fragPos);
    vec3 reflectDir = reflect(-lightDir,normal);
    float specularStrength =         pow(max(dot(viewDir,reflectDir),0.0),material.shininess);
    vec3 specular = light.specular * (specularStrength*material.specular);

    //Last step
    vec3 result = (ambient+diffuse+specular);
    finalColor = vec4(result,1.0);
}

As you can see, I transformed all the positions, normals and light source position in view space, i.e camera space, but I don't know why it's not working.

The problem with your calculations is that you use a uniform for viewPos which is the camera position.
The rest of your calculations is in Camera-Space, so the viewPos should always be $(0.0, 0.0, 0.0)$ and thereby the $viewDir$ becomes $-1*\text{fragPos}$.

In general: Always be careful about the different reference frames your calculations can be done in and aim to keep this consistent.


How to modify Perlin (not simplex) noise to create continental like terrain generation I have been playing around for a day with Perlin noise, and I am currently stuck. Most of the modifications I have made to the algorithm produce more or less the following:

Now, this is a very good start, but the idea is to generate terrain similar to real life (as close as I can get at least). Rivers and lakes would be nice to have, but that's way ahead in the schedule, right now I would like some help understanding 2 things.

Let's say that in my image, black is water and grey is land this is quite unlike the earth's shores. On earth continents are large masses of land and if they are cut by watter, it's usually on large areas (Imagine the Mexican gulf or the Mediterranean sea). However my image has a lot of narrow elongated "peninsulas" with patches of water around it. Due to the nature of Perlin noise (the square grid with the underlying random vector field) I am not sure how to create those large clusters of land and water.

The other problem is vertical, if we see the grey scale as a height map, these islands are too odd. In real life one would have large sections of flat land with elongated mountain ranges cutting through.

Some options that I have considered are, changing the smoothing/fade function in the improved Perlin noise algorithm for one that extends over multiple squares in the grid, but this adds too much computational complexity. I have also considered changing the vector field generation from pseudo random to one that follows a pattern, but this doesn't seem like it would actually solve the problem given that Perlin noise, as is, doesn't seem able to generate large consistent clusters.

Edit:

I know about octaves, but they have their limitations, re-sampling perlin noise at different frequencies and amplitudes does change the terrain generation and ca give you some good results:

But even this has issues.
For example if I want smooth hills I loose jaggy shores, same as if I try to create more valleys. And doing this also reduces the likelihood of generating islands in the middle of the bodies of water, moreover in terms of topography, the mountains look chaotic, they don't really from mountain ranges, they rather spread semi-chaoticly, which is not exactly what I need.

Perlin noise is just a base block, not very interesting by itself. You don't need to modify it, but to combine and filter it in interesting ways. Look at how to make fractal Brownian motion (fBm) with it for example, which combines octaves based on few parameters to get a richer texture.

The question of terrain rendering is a difficult one and a topic of active research. Many generated terrains have this artificial and uninteresting look. This is exactly what the paper "Modeling Real-World Terrain with Exponentially Distributed Noise" tries to address, by proposing a formula based on statistics measured from actual terrain, which yields more convincing shapes.

Another source of valuable information is Iñigo Quilez's website, where he mentions procedural generation a lot, including tricks to fake erosion.


What graphics techniques can be used to simulate a color nebula effect? I've been playing around with more advanced graphics these days (beyond the basic 2D UI and image effects that the iOS platform offers), and I'm wanting to implement a visual effect similar to how iOS's Siri uses what appears to be a "color nebula" in the background.

Here's a video of it in action. Seeing it animated is pretty important given that it's a dynamic effect.

Over time, the colors and intensity change, and various areas bloom and fade colors in. It's very subtle and has this ambient feel to it.

Anyway, I'm working in SceneKit, Apple's 3D scene composition API, and it has access to anything from Core Image to OpenGL to Metal as far as shaders and filtering geometries. So I'm curious if there is a general purpose algorithm for this kind of a) color effect (changing hue and other properties) and b) the slow, nebulous way colors come in and out and move around.

What techniques can one employ to pull of this animated visual effect?

I'd also love to read any additional resources about various ways to use colors and blending in graphics to achieve interesting effects.

I have no knowledge of SceneKit whatsoever, but the effect appears to be a simple post-process Gaussian blur of the app icon grid, with the blur radius increasing over time (i.e. increasing the blur amount) during the transition, with a touch of colour correction tacked on (which causes the darkening). It should be easy enough to implement in any graphics API that allows rendering to textures and performing image filtering on them (for instance, in OpenGL you could use framebuffer objects to achieve this).

You can have a look at an example WebGL implementation here. It's worth noting that it is a separable filter; meaning, it's a rectangle-shaped filter, but you can avoid sampling the same pixels (overlapping neighbouring samples) multiple times by splitting it into two passes – a horizontal and a vertical one – to the same effect.


Grainy image in my simple ray tracer The wall on the left of the red ball is perfectly reflective wall.

In the first image there's a point light that lies on the plane of the reflective wall and in the second image, it's 0.01 units ahead of it. Due to the light being on the reflective wall, I think, I am getting black dots all over my image.

I would like to know why putting a light on the same plane as the wall causes black dots ?

It's likely due to shadow rays. When the light source is exactly on the plane of the wall, a shadow ray traced to it may or may not be found to intersect the wall before it reaches the light. The result will depend on arithmetic roundoff error, and may appear as random noise, or stripes or some other artifact.

To fix it, you can either keep the light offset slightly from the plane, or set up the wall object not to cast shadows (assuming it doesn't need to in the scene).


Rendering Fluid Simulations? I've read about Lagrangian and Eulerian fluid simulations and here's what I take from their methods:

Lagrangian - Simulating fluid particles by calculating displacement for each particle
Eulerian - Simulating fluid particles by calculating interactions between finite spaces containing group of fluid particles.

(?) Do each method have different rendering technique suitable for it?

My guess is that you can take the finite space or 'voxel' data for Eulerian simulation, but I would like an expert's say in my hypothesis.

(?) Also regarding MPM (Material Point Method) which is a hybrid of both worlds, if Lagrangian and Eulerian sims does have different rendering technique, does it mean that I can use either techniques?

Here's a more complete answer from the extent of my knowledge. A sort of brief overview you can google more about. I'm sure I didn't cover all the different techniques but most branch off the mentioned ones. Note: if it's a liquid we are more concerned with getting an accurate surface representation.

Surface Extraction Methods: The most common way would be to rasterize the particles into a 3d image/grid using a basis function, unless they're already in a grid. Then extract the polygonal surface from the image using marching cubes or some variant of it. Then render that polygon. There are some methods to extract polygonal surfaces directly from particles without rasterizing.
Ray Marching with an Implicit Surface: Again we rasterize the particles into an image but quickly convert into an implicit surface in our 3d image then ray march render the implicit surface, very fast.
Splat Volume Rendering (doing it in screen space): Splatting is good for visualizing extremely large datasets and used to be used a lot for volume rendering because of how fast it is. Basic idea is to rasterize all or most points as discs from the volume. You can do many effects, lighting, etc. Nvidia's screen space fluids is a form of this (SSF). Simple, fast, quality is acceptable for many cases.
Slicing/Texture Based Volume Rendering: Here we overlay 2d semi transparent images. You can just overlay some precomputed textures on various particles or compute a series of sliced 2d images a set distance apart in the 3d image/volume given the camera angle. More expensive. Gives better results than splatting.
Ray cast Volume Rendering: Similar to ray marching, we march along the ray from every pixel but instead of looking for an implicitly defined surface we sample the volume directly and map it too color and transparency then composite it back along the ray. For lighting we can do it similar to surface based rendering but use the gradient of the image as the normal. There are many other tricks.
Ray traced Volume Rendering: Basically the same as the ray casting but we bounce the rays around inside of the volume. They're distributed according to a phase function. I'm sure all the clouds in your favorite animated movies were rendered this way. Disney did this for their MPM simulated Snow in Frozen. The ray tracing approach is the most expensive of all of them, more expensive then surface based ray tracing. Not for real time as of writing this.

Note: The first two methods aren't for gasses. The last 3 are best for gasses due to their lack of surface representation.

I think it's also worth noting the value of having a stored representation for post processing effects. For manual deformations or effects by an artist. Procedural effects like spray, foam, bubbles, etc. Or just some extra geometric processing (smoothing or whatever).


Linear independence of three points What is the best way to prove if three points are linear dependent?

This is my current way to do it:

$$\mathbf{v_a} = \mathbf{b}-\mathbf{a} \\
\mathbf{v_b} = \mathbf{c}-\mathbf{a} \\
\mathbf{v_c} = \begin{pmatrix} -\mathbf{v_{a,y}} \\ \mathbf{v_{a,x}} \end{pmatrix} \\
\phi = \mathbf{\hat{v}_c} \cdot \mathbf{\hat{v}_b} \\
\phi < 10^{-3}
$$

$\phi$ is the $arccos$ of the real angle between the two vectors. This works good if the polygon or the three points of the polygon have well defined distances. But what if the polygon looks like this:

The distance between $P_0$ and $P_1$ is much bigger than between $P_1$ and $P_2$. $P_0$, $P_1$ and $P_2$ are of clearly not linear dependent.

I'm searching for a scale-independent algorithm for that.

Do you have any ideas or a reference to a paper I can read about it?

Normalize $v_a$ and $v_b$ and your algorithm should no longer depend on the length of the edges, unless you consider numerical stability.

As for the "best way", I'm not sure there's a much better algorithm but I would try a better definition of the tolerance. Instead of a fixed value, I would use differentials to compute the change in the angle for a change of the inputs of a few ulps. If the resulting range overlaps 0, then I think the points are colinear within available precision.

Whether that complexity is justified depends on what you're doing with this, which you did not specify. A constant could be fine or even the best choice for some uses.


Ray-tracing the Cornell Box results in really inconsistent image So I have a vector of glm::vec3 containing the triangles for the classic Cornell Box called triangles. The Draw method casts a ray for each pixel on the screen and calls ClosestIntersection which returns true or false and updates a struct containing things like colour and the point of that intersection. Then I simply draw the pixels based on the colours (black for no intersection).

The result is very inconsistent and I can't find the error:

void Draw()
{
    if (SDL_MUSTLOCK(screen))
        SDL_LockSurface(screen);

    // Loop through each pixel and cast ray
    for (int y = 0; y<SCREEN_HEIGHT; ++y)
    {
        for (int x = 0; x<SCREEN_WIDTH; ++x)
        {
            vec3 dir(x - SCREEN_WIDTH / 2, y - SCREEN_HEIGHT / 2, focalLength);
            Intersection isect;
            if (ClosestIntersection(cameraPos, dir, triangles, isect))
            {
                vec3 color = triangles[isect.triangleIndex].color;
                PutPixelSDL(screen, x, y, color);
            }
            else
            {
                PutPixelSDL(screen, x, y, vec3(1, 1, 1));
            }
        }
    }

    if (SDL_MUSTLOCK(screen))
        SDL_UnlockSurface(screen);

    SDL_UpdateRect(screen, 0, 0, 0, 0);
}

This is the function called from Draw:

bool ClosestIntersection(vec3 start,
    vec3 dir,
    const vector<Triangle>& triangles,
    Intersection& closestIntersection)
{
    bool foundIntersection = false;

    // Loop through all the triangles and check for intersection with ray
    for (size_t i = 0; i < triangles.size(); i++)
    {
        vec3 v0 = triangles[i].v0;
        vec3 v1 = triangles[i].v1;
        vec3 v2 = triangles[i].v2;
        vec3 e1 = v1 - v0;
        vec3 e2 = v2 - v0;
        vec3 b = start - v0;
        mat3 A(-dir, e1, e2);
        vec3 x = glm::inverse(A) * b;

        // Check that found scalars are within bounds
        if ((x.x >= 0) && (x.y > 0) && (x.z > 0) && (x.y + x.z < 1))
        {
            if (foundIntersection)  // If there's a previvous intersection for this ray check that new one is closer to camera
            {
                if (glm::distance(start, x) < closestIntersection.distance)
                {
                    closestIntersection.distance = glm::distance(start, x);
                    closestIntersection.triangleIndex = i;
                    closestIntersection.position = x;
                }
            }
            else
            {
                foundIntersection = true;
                closestIntersection.distance = glm::distance(start, x);
                closestIntersection.triangleIndex = i;
                closestIntersection.position = x;
            }
        }
    }
    return foundIntersection;
}

Two symptoms

There appear to be two problems with the image.

The background is showing through along the line between adjacent triangles.
The colour displayed is not always from the closest intersection.

Note that the background colour is white, rather than black, due to the line:

                PutPixelSDL(screen, x, y, vec3(1, 1, 1));

Why this background shows through at the triangle edges I do not know. However, the second problem is identified below, so I recommend you fix that first and then the first problem can be analysed in isolation without the additional distractions.

Cause of the problem with ClosestIntersection

The ClosestIntesection function returns true when an intersection is found, and updates an Intersection object called closestIntersection. However, the intersection stored here is not always the closest to the camera.

The reason for this is here:

                closestIntersection.distance = glm::distance(start, x);

This appears in two places so it will need to be fixed in both.

start is cameraPos, presumably in world coordinates. x appears to be in the local coordinates of the triangle being intersected (one of the triangle vertices being the origin). The distance between two points in different coordinate systems is meaningless, so that in different regions of a triangle it will appear to be behind or in front of another triangle for no immediately apparent reason.

If x is first converted to world coordinates then the distance will be correct and the intersection chosen will be the closest to the camera.


How to do texturing with OpenGL direct state access? How do you use textures with direct state access in OpenGL?

I have the following in my code, which seems to work:

GLuint textureHandle;
glGenTextures(1, &textureHandle);
glActiveTexture(GL_TEXTURE0);
glBindTexture(GL_TEXTURE_2D, textureHandle);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA8, imageW, imageH, 0, GL_RGBA, GL_UNSIGNED_BYTE, image_data);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);

However, when I replace it with the following everything just becomes black:

GLuint textureHandle;
glActiveTexture(GL_TEXTURE0);
glCreateTextures(GL_TEXTURE_2D, 1, &textureHandle);
glTextureImage2DEXT(textureHandle, GL_TEXTURE_2D, 0, GL_RGBA8, imageW, imageH, 0, GL_RGBA, GL_UNSIGNED_BYTE, image_data);
glTextureParameteri(textureHandle, GL_TEXTURE_MIN_FILTER, GL_LINEAR);

You still have to bind the desired texture to the texture unit to use it for rendering. In your current code, you're not specifying which texture to use for rendering, so the GL driver doesn't know which one you want to use and is defaulting to "no texture".

There are a few ways to bind a texture. You can keep using glActiveTexture+glBindTexture as in your non-DSA code, or you can use either glBindTextures or glBindTextureUnit.

For example, with glBindTextureUnit, do this:

glBindTextureUnit(0, textureHandle);

The first parameter is the texture unit to bind to.

By the way, instead of using glTextureImage2DEXT (which is from the old and deprecated EXT_direct_state_access extension), it's probably better to stick with core OpenGL calls. You can initialize the texture by using glTextureStorage2D to allocate the memory and set the format, then glTextureSubImage2D to upload the data.

(Here's an article with more on the differences between EXT_direct_state_access and the newer core version of the functionality, if you're interested.)


Double buffering always necessary? Question from the graphics newbie:
What I know by now is that "usually" double buffering is used: You calculate the content of frame x+1 while frame x is shown on the screen, if you want to achieve the maximum update rate, calculation must not take longer than one frame time, otherwise the "drawing process" is visible.
So, having two framebuffers absolutely makes sense, and I guess that's why we have that "glfwSwapBuffers" call in some OpenGL tutorials.

But what if I program my things in a way that every primitive leads to fragments that are horizontal lines, and let the GPU process it from top to bottom line "on the fly"?
In this case I would need only one framebuffer that could be filled with a static background, and I would only have to store the other objects in some much smaller memory.
Is this possible at all?
Is there even any GPU implementation that does it that way to save memory?

Indeed there are/were 'just in time' renderers.

For example, Dreamcast (PowerVR CLX2) had a mode where the 'frame buffer' only had to be a few rows of tiles in size. The system would be rendering into one row while the display was reading out of some subset of the others. It would then cycle through the buffers.

In order to do this, however, you do need a display-list rendering system. A standard 'immediate mode' renderer is not appropriate.

Of course, scene complexity needs to be considered carefully for this sort of scheme to work. In particular, if one tiny section of the screen contains particularly complex geometry, the renderer might not finish it in time before the display needs to read it. Allocating more memory for the partial screen buffer allows for more variability in scene complexity.

I also have a feeling/seem to recall some old (e.g 60s/70s?) flight simulators might have rendered 'on the fly' because memory (for a frame buffer) was once fiendishly expensive.

Alternatively, the PowerVR PCX1/PXC2 ports of Tomb Raider had an optional single buffered rendering mode. (This was primarily because one of the guys doing the port (cough, me, cough) only had a 2MB 2D graphics card which could only allocate a single 1024x768 framebuffer).  Again, since the system was tile-based, it didn't suffer from the nasty artefacts you'd get with single buffering on a traditional Z-buffer system.

UPDATE:
FWIW there's another related question on "Racing the Beam" here


Understanding the irradiance map generation I am trying to understand how the generation of irradiance maps works. I was reading LearnOpengGL tutorial and Codinglabs article. Reading those articles, I got a bit confused about how we use convolution to generate the irradiance map.

Do we apply the integral to the environment map to convolute it, and do we do it because our environment map is equirectangular?

Yes, the convolution is effectively evaluating the following integral:

$$
\text{irradianceMap}(\vec n) = \frac{1}{\pi} \int \text{environmentMap}(\vec \omega_i) \, \max(\vec n \cdot \vec \omega_i, 0) \, d\omega_i
$$

This convolution isn't about whether the environment map is equirectangular, cubemap, or some other projection. We still have to do the convolution regardless, because we want to get the total diffuse light (irradiance) coming to a surface with a given normal, from all directions in the hemisphere around that normal. The environment map to start with just has light from one direction (radiance).


Books to learn Ray Tracing Recently I have developed and interest in Ray Tracing and like most computer graphics tutorials online there is nothing regarding implementation for a beginner like myself.

So far I have only done real time rendering (DirectX), however I understand the basics of Ray Tracing but I want to buy a book before proceeding any further. I've taken a look at Physically Based Rendering: From Theory to Implementation (I want to learn Ray Tracing with a Physically Based Approach so I thought this would be great) but I don't think it's good for a beginner since there's not much emphasis on the code.

When I was learning DirectX 11 everyone recommended Frank Luna's Introduction to 3D Game Programming, which was great since it covered all the basics and also a few advanced topics like SSAO with an approach a beginner could understand. Is there something like this for Ray Tracing?

For an introduction, you can give a look at: Ray Tracing from the Ground Up (Amazon link here).

It starts really from the basics, and provides simple implementations for the concepts that are gradually introduced.


Volumetric raycasting with transparent rasterized geometry I have an idea of how to render opaque rasterized geometry alongside raycast volumes:

Render rasterized geometry to a depth map and also a render target
When raycasting, check position against the depth map. When the ray penetrates the opaque geometry, alpha blend its color (from the render target) with the current color "rolling sum" of the ray, and stop raycasting

This might even work for a single piece of transparent geometry (say a piece of glass in front of the raycast volume), but it will break down with multiple pieces of transparent geometry.

For example, imagine a red transparent quad in front of a raycast volume, and a green transparent quad behind the same volume. On the rasterized geometry pass, the render target will receive a yellow color (blend of the red and green of the quads). This yellow color will be alpha blended with every sample of the raycast volume, making it look as if the green quad was also in front of it. Ideally we would want to see a reddish volume with effectively no green.

How could I go about solving this?

This is called "deep shadow mapping" and deep compositing.

Sadly invented long before you had this ideas yourself);

Now you are talking about implementing this idea specifically on a given architecture (GPU). It's up to you to make it work for this given architecture, and if you have technical difficulties with that maybe you can ask a question on this forum again.


Tweaking a glow shader to make it look better I have a simple game and and subjects of it are these little lines. It is targeted for iOS and android so it has a HUGE range of processors that it could run on, right now.

I am trying to add realtime glow to them for two reasons

I am trying to hide the fact that I don't have the rendering time to process anti-aliasing on most devices.
The subject of the game is supposed to be pure light, ergo that picture should look like those things are pure light.

I have been tweaking a separable gaussian blur shader for quite awhile and I have came up to a point of frustration, I just can't get it to look right, perhaps the issue is I am trying to futilely hide the jagged edges of the light meanwhile not making the light look blurry.

My biggest problem is all the variables involved in making it look its best.

I am very new to graphics/rendering and I am in no way an artist. Perhaps the most frustrating thing about rending to me is all the variables that seem to be involved. With glow I have seen so many possible changes.

A. Add blend mode, screen blend mode, or some other concoction
B.Weighting the blur, and normal differently before combination
C. The
Sigma of the gaussian bell function (I have been using this
confusing calculator but it doesn't seem to give the same values I
see other people have in)
D. Scalars on the "x" values sent to the
sigma function
E. Sample scale (making the blur radius smaller or
larger)
F. Changing the resolution of the glow buffer

How does one find the "best looking" constants when working with so many variables like this?

I am also having issues because the time between me making a tweak and seeing it is a long that its hard to see changes, I would do it in shader toy however I can't load up this image or procedurally generate one like it.

Right now I am really stuck on the sigma of the gaussian bell curve kernel, especially because I am coding in the numbers rather then the formula because I need the processor speed. Can you suggest a good sigma to use?

Sigma and kernel size of Gaussian filter

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

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

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

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

Creating a good-looking glow filter

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

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

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

Jaggies

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

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


What is the most efficient line algorithm using a shader program I'm new to shaders and I have been experimenting with them in shadertoy. I'm trying to get a deeper understanding of the graphics pipeline and I want to implement some features using shaders. I want to start off simple and draw a line on the screen using shaders. I wrote two-line algorithms from scratch
struct Vertex {
    vec2 p;
    vec4 c;
};

vec4 overlay(vec4 c1, vec4 c2) {
    return vec4((1.0 - c2.w) * c1.xyz + c2.w * c2.xyz, 1.0);
}

vec4 drawLineA(Vertex v1, Vertex v2, vec2 pos) {
    vec2 a = v1.p;
    vec2 b = v2.p;
    vec2 r = floor(pos);

    vec2 diff = b - a;

    if (abs(diff.y) < abs(diff.x)) {
        if (diff.x < 0.0) {
            Vertex temp1 = v1;
            Vertex temp2 = v2;

            v1 = temp2;
            v2 = temp1;

            a = v1.p;
            b = v2.p;
            diff = b - a;

        }

        float m = diff.y / diff.x;
        float q = r.x - a.x;

        if (floor(m * q + a.y) == r.y && a.x <= r.x && r.x <= b.x) {
            float h = q / diff.x;
            return vec4((1.0 - h) * v1.c + h * v2.c);
        }

    } else {
        if (diff.y < 0.0) {
            Vertex temp1 = v1;
            Vertex temp2 = v2;

            v1 = temp2;
            v2 = temp1;

            a = v1.p;
            b = v2.p;
            diff = b - a;

        }

        float m =  diff.x / diff.y;
        float q = r.y - a.y;

        if (floor(m * q + a.x) == r.x && a.y <= r.y && r.y <= b.y) {
            float h = q / diff.y;
            return vec4((1.0 - h) * v1.c + h * v2.c);
        }

    }

    return vec4(0,0,0,0);
}

vec4 drawLineB(Vertex v1, Vertex v2, vec2 pos) {
    vec2 a = v1.p;
    vec2 b = v2.p;

    vec2 l = b - a;
    vec2 r = pos - a;
    float h = dot(l,r) / dot (l,l);

    vec2 eC = a + h * l;

    if (floor(pos) == floor(eC) && 0.0 <= h && h <= 1.0 ) {
       return vec4((1.0 - h) * v1.c + h * v2.c);
    }

    return vec4(0,0,0,0);
}

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
    float t = iTime;
    float r = 300.0;
    Vertex v1 = Vertex(vec2(400,225), vec4(1,0,0,1));
    Vertex v2 = Vertex(vec2(400.0 + r*cos(t) ,225.0 + r*sin(t)), vec4(0,1,0,1));

    vec4 col = vec4(0,0,0,1);
    col = overlay(col,drawLineA(v1, v2, fragCoord));
    col = overlay(col,drawLineB(v1, v2, fragCoord));
    // Output to screen
    fragColor = col;
}

However, they are both quite slow, is there a more efficient line algorithm that I can use that outputs a color based on whether the pixel is in the line or not. I've heard that Bresenham's line algorithm is the fastest however I don't know how to use shaders to speed up the algorithm because it needs the previous y value to compute the next. Can line algorithms be sped up by shaders or is it already the fastest it can be on the CPU. If there is a optimised line drawing algorithm using the GPU (where the GPU would out-perform the cpu) how can I implement it into my code?
Thanks

Here is a (mostly) minimal version of an SDF for a line segment using a signed distance field as suggested in the comments. I take no credit for this code, it is your function pieced together with IQ's SDF function done in the style you listed above.
Be sure to go to IQ's website, it is one of the best learning resource out there for this material. Though it can be hard to digest till you get all the basics down. IQ's Index Page.
float udSegment( in vec2 p, in vec2 a, in vec2 b )
{
   vec2 ba = b-a;
   vec2 pa = p-a;
   float h =clamp( dot(pa,ba)/dot(ba,ba), 0.0, 1.0 );
   //return length(pa-h*ba); // use actual length

   // or use length squared
   vec2 sqrd = pa-h*ba;
   sqrd = sqrd * sqrd;
   return sqrd.x+sqrd.y;
}

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
   vec2 p = ((2.0*fragCoord-iResolution.xy)/iResolution.y)*1.4;

    // give it some spin
    vec2 v1 = iResolution.xy * vec2(cos(iTime),sin(iTime));

    vec2 v2 = vec2(0,0); // set the start point
    float th = 0.004; // Controls line thickness

    float d = udSegment( p, v1, v2 ) - th; // compute sdf

    vec3 col = vec3(1.0) - sign(d);
    fragColor = vec4(col,1.0);
}

If all this is doing is drawing a line, then there is no need to compute the actual length, so don't...just return lenght squared. I made an edit to the code above that skips the sqrt, but line thickness is now squared.
Bresenham's algorithm was intended to be used for drawing individual pixels and is often implemented directly in the hardware of GPU's. So it drives which pixels to draw in its own loop and tells the hardware which pixel to draw.
ShaderToy is drawing the entire screen, so every pixel is covered probably by drawing a fullscreen triangle, then calling the mainImage function in the fragement shader.
To implement Bresenham's algorithm in ShaderToy the code would need to determine if a particular fragment was actually on the line and in so doing we lose any advantage gained by this clever line drawing technique.
The most efficient way to draw a line on a GPU is not to use ShaderToy at all but write our own bit of code that tells the hardware to just draw a line, this is where graphics API's like OpenGL come into play. Which ultimately would call a fragment shader but unlike ShaderToy, the fragment shader would only be called for those fragments which are actually on the line and our fragment shader would then be reduced to something ultra simple like:
void main(){ return vec4(1,1,1,1); }

Which would result in a pure white line being drawn on screen.