Creating 3d model building notation using ASCII

As you’ve found, it’s hard to use a two-dimensional format, even from multiple viewpoints, to represent a 3D structure that’s not axis-aligned. I’m not sure I have a useful suggestion there—there’s a reason most 3D file formats support specifying translation/rotation/scaling of individual parts.

A different direction you might try would be using the existing work in the LDraw project; their file format is technically ASCII, and though it’s closer to a standard 3D format in that the fundamental parts (like studs) are built out of lists of vertices / triangles / etc., the higher-level pieces (bricks, plates, etc.) are built out of references to the fundamental ones, which sounds like it’s roughly along the lines of what you’re after. There’s an assortment of third-party design tools that provide GUIs on top of the LDraw parts library; of those, I’m partial to Bricksmith.


Visualize the interpolated unit quaternion on the surface of the unit sphere

Because given 3 values of a unit quaterion we can derive the fourth value.

Which means there exists a bijective mapping from unit quaternion to 3D space.

Though for visualization you want the mapping that makes what is happening the most easily discernible. However a usable visualization doesn't need to be fully bijective.


Answer over in Photography:
https://photo.stackexchange.com/questions/119761/sensor-size-of-sony-hdr-hc7e/119764#119764
It turns out to be Vertikal: 3.74 horizontal 4.98 and diagonal 6.23


Applying correct light physics to gaussian blur formulas for glow

Yes, your theory is correct. A gamma-correct blur entails converting the input pixels to linear color space, performing the blur weighting and accumulation in that space, and then converting back to gamma space at the end.

As noted in the comments, the actual transform is not literally squaring and square-rooting, that's just an approximation (and not that good of one). For the true sRGB gamma transform, see the equations in this Wikipedia article (look down the page for the equations involving $C_\text{srgb}$ and $C_\text{linear}$).

By the way, some visual comparisons of gamma-correct and gamma-incorrect blurs can be found on this page by Elle Stone, which shows why this whole thing matters.


Why do GPUs divide clip space Z by W, for position?

If you are doing a perspective image and your model has implicit intersections then, if you use "linear Z", those intersections will appear in the wrong places.

For example, consider a simple ground plane with a line of telephone poles, receding into the distance,  which pierce the ground (and continue below). The implicit intersections will be determined by the interpolated depth values. If those are not interpolated with 1/Z, then when the projected vertices have been computed with perspective, the image will look incorrect.

I apologise for the non-aesthetic quality of the following illustrations but I did them back in '97.

The first image shows the required rendering effect. (Note that the blue "pylons" go quite a long distance under the ground plane so are clipped at the bottom of the images)

This second image shows the result of using a non-reciprocal depth buffer: (Apologies for the change of scale - these were copied out of an old MS Word doc and I've no idea what has happened with the scaling.)

As you can see, the results are incorrect.

On another note, are sure you really want a linear Z representation? If you are rendering perspective, surely one wants more precision closer to the camera than at a distance?

Re your later comment:

  “if those are not interpolated with 1/Z” that I don’t understand. What interpolation is that?

The first thing to note is that, with a standard perspective projection, straight lines in world space remain straight lines in perspective space. Distances/lengths, however, are not preserved.

For simplicity, let us assume a trivial perspective transform is used to project the vertices, i.e.
$$X_{Screen} = \frac{X_{World}}{Z_{World}}$$
$$Y_{Screen} = \frac{Y_{World}}{Z_{World}}$$
We should also compute a reciprocal screen-space depth, e.g. $$Z_{Screen} = \frac{1}{Z_{World}}$$ but linear Z in the depth buffer would, to me, require something like: $$Z_{Screen} = scale*Z_{World}$$ (We can assume here that scale=1)

Let's assume we have a line with world space end points$$
  \begin{matrix} \begin{bmatrix}
    0 \\
    0 \\
    1 \\
    \end{bmatrix} and
   \begin{bmatrix}
    200 \\
    0   \\
    10  \\
    \end{bmatrix}\\
  \end{matrix}
$$
With the perspective mapping these map to screen space coordinates
 $$ \begin{matrix}   \begin{bmatrix}
    0 \\
    0 \\
    1 \\
    \end{bmatrix} and \begin{bmatrix}
    20 \\
    0  \\
    0.1 \\
    \end{bmatrix}
 \end{matrix}$$

The rendering system/hardware will linearly interpolate the screen space z, so at the 1/2 way point of the line, as it appears on-screen, i.e. at pixel (10, 0), we would get a projected (inverse) Z value of 0.55, which corresponds to to a world space Z value value of ~1.818. Given the starting and end Z values, this is about 20% along the length of the line.

If instead, we tried to interpolate using the original Z values, we'd end up with Z corresponding to a world space value of 5.5. As long as nothing intersects, you might be ok (I've not thought about it too thoroughly) but anything with implicit intersections will be incorrect.

What I haven't mentioned is that once you introduce perspective correct texturing (or even perspective correct shading), you must do per-pixel interpolation of 1/w and, additionally, also compute, per pixel, the reciprocal of that interpolated value.


Vulkan: Swapchain image count with VK_PRESENT_MODE_FIFO_KHR

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.


How do fragment shader invocations subgroups map onto triangles?

Fragment shader subgroups are not required to be restricted to a single primitive (and such a restriction would negatively impact performance). So subgroup broadcasting can cross primitive boundaries.
Note that the most recent version of the Vulkan standard states that invocations in the same quad scopes are required to be within the same primitive scope.


Your inputs and outputs still don't line up.
#version 440 core

// Comment out the line below
// in vec4 vs_pos;    <----- No corresponding output in the vertex shader
in vec3 vs_color;

out vec4 fs_color;

void main()
{
    fs_color=vec4(vs_color, 1.f);
}

The gl_Position output is consumed and does not need a specific input in the fragment shader. Only variable declared as "out" in the vertex shader need a corresponding "in".
The next issue is the vertices need to have colors in them. The way it is setup now all the components are consumed before even a single triangle is drawn.
The vertex buffer needs to be setup:
vertex,color, vertex,color, vertex,color
where each vertex and color has 3 floating point values.
GLfloat vertices[] = {

//    vertex           color
-0.5f, -0.5f, 0.0f,  1.0f,0.0f,0.0f
 0.5f, -0.5f, 0.0f,  0.0f,1.0f,0.0f
 0.0f,  0.5f, 0.0f,  0.0f,0.0f,1.0f
};

Something like the above. Is what you need for the vertices.


Found a solution.

In the vertex shader I project position from model to the clip-space, then from clip-space to screen space, adjust the width in screen pixels, and the project back to clip-space, which ultimately becomes gl_Position value.


When solving the equation $(M - tL_C)u = \delta_\gamma$, you effectively have to invert the operator:
$$
u = (M - tL_C)^{-1} \delta_\gamma
$$
Note that while the individual operators $M$ and $L_C$ are only local, containing information about the individual vertices and edges of the mesh, the inverse operator is decidedly not local. Inversion is a global operation that incorporates information across the whole matrix being inverted, which means information across the whole mesh. (Note that $M$ has a trivial inverse since it's diagonal, but $L_C$ definitely doesn't.)
In practice, you might not literally compute the inverse matrix but rather use Gaussian elimination or some such to solve the $u$ for a given $\delta_\gamma$. In that case, it's the solving process that integrates information across the whole mesh. Effectively $L_C$ is encoding a bunch of constraints between neighboring vertices, and the solver has to satisfy all the constraints across the whole mesh at once.
(Note that it's not a trivially parallelizable job. There are methods for using parallelism to accelerate solving large linear systems, but they're going to be multi-pass methods that transfer information up and down between different "scales" of the problem. Think like parallel prefix scan, or FFT—that sort of thing.)
BTW, another perspective on this equation is that it is solving for the fixed point of $u$ in
$$
u = M^{-1}(\delta_\gamma + tL_Cu)
$$
This is yet another way of algebraically rewriting that same equation. In this form it looks a lot like the rendering equation $L = L_e + \int L \, f_{\text{brdf}}$! It has a similar structure, where $\delta_\gamma$ is like the emitted radiance and $L_C$ is like the scattering at surfaces. Just as in the rendering equation, you're looking for a global equilibrium solution. (And if rendering was discretized, we could similarly solve it by turning the scattering operator into a matrix and throwing the whole thing into a linear solver.)


What other paradigms exist besides vector/fragment/transform graphics programming?

Several other rendering paradigms exist aside from conventional rasterization of triangles using vertex and fragment shaders.

Ray tracing works by intersecting light rays with surfaces (triangle meshes, or more general surfaces: anything that can be tested for intersection) and then firing additional rays to gather information about lighting, shadows, reflections, etc at the intersection point. Path tracing and photon mapping are refinements of this concept.
REYES rendering subdivides all primitives into micropolygons the size of a single pixel or smaller, calculates lighting and shading per micropolygon vertex, then uses a specialized rasterizing algorithm to render the micropolygons in screen space with motion blur and depth of field.
Distance field ray-marching (also called sphere tracing) represents all primitives in terms of distance fields: 3D functions and/or volumetric textures that give the distance from any given point to the nearest surface in any direction. The distance field is used to step adaptively along a ray until it hits a surface, and can also be used for lighting effects such as ambient occlusion.

However, all rendering algorithms use linear transformation matrices. That's not part of the "paradigm" so much as it's the basic machinery for manipulating objects, the camera, etc in 3D space. It would be hard to do anything interesting without it.


Bresenham circle drawing algorithm, compute the distance?

After a short research, I found this site, which describes the algorithm. I didn't know it before. An important thing you didn't mention in your question is the calculation of the decision parameter $d$, which is:

$$d=f\left(N\right)+f\left(S\right)$$

It abuses the fact, that the bottom pixel will always lie on the circle or inside and the right pixel will always be on the circle or outside (for this particular segment). In conclusion, this means that $f\left(S\right) \le 0$ and $f\left(N\right) \ge 0$. If $d<=0$ you pick the right one and the left one otherwise.

  Okay, we're using the circle equation to determine which is the closest point to the circle but why not simply using the euclidean distance?

Most probably for performance reasons. Using the Euclidean distance requires you to calculate 2 square roots, which is quite expensive when compared to simple multiplication ($r\cdot r$). On a Haswell CPU, you can perform 6 independent multiplications at the same time as calculating a single square root.

If you optimize the Bresenham algorithm you will probably get something like that:

$$\begin{matrix}
d &=& x_{k+1}^2 + y_k^2 - r^2 +  x_{k+1}^2 + y_{k-1}^2 - r^2\\
 &=& 2x_{k+1}^2- 2r^2 + y_k^2   + y_{k-1}^2 \\
 &=& 2\left(x_{k+1}^2- r^2\right) + y_k^2   + y_{k-1}^2
\end{matrix}
$$

then compare

$$d \le 0$$
So in total, you end up with 9 multiplications, 2 additions, 1 subtraction and 1 comparison.

EDIT
As mentioned in the comments to this answer, the Euclidean length and the Bresenham algorithm won't give you the same results. While the Euclidean length will always give you the Pixel with the closest distance of its center to the arc, the Bresenham algorithm will favor points inside the circle, even though they are a little bit farther away. However, this error gets smaller the closer you get to the circle and shouldn't be noticeable.

Update

After rereading some tutorials like the one above or this one, I am not totally sure if they are really stating that they take the closest point. The tutorial I linked says:

  So if $Dk < 0$ that means the negative $F(S)$ is bigger then the positive $F(N)$, that implies Point $N$ is closer to the circle than point $S$.

Language details are not my strong suit, but I think "implies" is meant more in the way of "indicating" something. In this case, it does not mean it is the exact result.

Anyways, after some elongated calculations, you are right, that $d=f\left(N\right)+f\left(S\right)$ will give wrong results in favor of the inner point if both distances to the circle are quite close. I did some error estimation.
With:

$$
\begin{matrix}
a &=& \sqrt{x_{k+1}^2 + y_k^2} \\
b &=& \sqrt{x_{k+1}^2 + y_{k-1}^2} \\
\end{matrix}
$$
being the distances to the points from the center, you can calculate the error $\epsilon$ as follows:

$$\begin{matrix}
a^2 - r^2 + b^2 - r^2 + \epsilon &=& ((a-r) - (r-b))^2\\
&=& (2r -a - b)^2
\end{matrix}$$

If you solve that for $\epsilon$ you will get:

$$\epsilon = 6r + 2ab - 4ra - 4 rb$$

You can get 2 interesting pieces of information from that. First, as you already claimed, the Bresenham algorithm does not take the exact distance to the circle when deciding which point is the next one, otherwise $\epsilon$ must have been 0. However, the second information is: If $a$ and $b$ are both on the circle, the error vanishes.

I was wondering how much closer $a$ must be than $b$ until it is selected. So I did the following:

$$\begin{matrix}
a &=& r+\delta + \tau\\
b &=& r-\delta
\end{matrix}$$

The reasoning here is as follows: If $\tau = 0$, then both points have the same distance $\delta$ to the circle. So the right-hand side of

$$\begin{matrix} a^2 - r^2 + b^2 - r^2 + \epsilon &=& (2r -a - b)^2 \end{matrix}$$

, the Euclidean distance, will be 0. Now I want to find an offset $\tau$, which causes the left-hand side to be 0, which is the condition where the Bresenham algorithm "assumes" both points to be equally distant to the circle. So if you say  $$a^2 - r^2 + b^2 - r^2 = 0$$, replace the $a$ and $b$ with the shown formulas and solve for $\tau$ you get:

$$\tau =   \sqrt{r^2 + 2\delta - \delta^2}- (r + \delta)$$

You can rewrite this a little bit so that it looks like this

$$\tau =   \sqrt{(r + \delta)^2 - 2\delta^2}- \sqrt{(r + \delta)^2}$$

From this, you can see again that both approaches give the same result in the special case that both points lie on the circle since $\tau$ gets 0. Putting in some real numbers will also show, that $\tau$ does not get too big. I am no mathematician, but I think you can show, that the "error" and $\tau$ get relatively small with a growing ratio of $r:\delta$. So if you are not drawing circles with a radius of just 2-3 pixels, the differences in the visual output should be negligible.

Apart from that, taking the Euclidean distance might also not be the best way in the first place.
In the end, a rasterized circle is just an approximation and not a true circle. So there is no "correct" rasterization method for that. With enough distance, you won't notice that it contains of pixels. But in this case, you won't also notice anymore which pixels center is closer to the "true circle".

Conclusion

The Euclidean distance and Bresenham algorithm result in slightly different rasterizations (probably not noticeable most of the times).
The Euclidean distance is much more expensive to calculate due to the square roots. Additionally, as one can read in the linked sources, the Bresenham algorithm can be optimized even further than written in this answer, which makes it really fast. If I got it right, one just needs 1-2 multiplications and 2-3 additions/subtractions per pixel.


Ray tracing - BRDF using Cornell measured spectral data

The MATLab data file has 3 arrays

Input vector - aka, the light source (In Cartesian coordinates)
Output vector - aka, the eye (Also in Cartesian coordinates)
Spectral data (spectral data is discretized into 31 bins)

So input[n], with output[n] results in spectral[n]

The ASTM file is a flattened version of the MATLab data file, with one major difference: the input and output vectors are in spherical coordinates, specifically the traditional physics notation:

The data is defined in the following range:

For input vector, $\theta$ (theta) varies from $0$ to $\frac{\pi}{2}$, and $\phi$ (phi) is always a constant $0$.

The output vectors are uniformally distributed across the hemisphere. Since $\phi$ is periodic on $2\pi$, mathematically you can define the bounds of $\phi$  in an infinite number of ways. In this data set they chose:
$$\phi = [-\pi, \pi]$$
but it would be perfectly fine to choose
$$\phi = [0, 2\pi]$$

Now, in order to use the data:

Since the input vectors only vary over a quarter circle ($\theta = [0, \frac{\pi}{2}]$ and $\phi = 0$), not the whole hemisphere, you will need to find the matrix transform that transforms your input vector to the quarter circle.
Apply the same transform to the output vector.
Using the transformed input and output vectors, look up the spectral response of the BRDF.

I'm not sure of the best way to do this. I defer to others' opinions. I'm sure there is some kind of data structure / algorithm to do the search.
The naive way would be to do a O(n) search of all the input and output directions to find the two or three that are closest, then LERP between them.

Use the spectral values as the BRDF in the rendering equation


Is there a term to refer to a cube-break-down process?


Open GL Shader Storage Buffer Objects to replace Vertex Attributes

The counter you want is built in the shader as gl_VertexID.

However you have 16 attributes of 4 components each to work with. Take 2 components for the texture coordinates and you have 62 float values to play with. If you need 6 components per blend shape (3 pos + 3 normal) you get 10 blend shapes to work with per object per frame. If you leave off the normal as static then you get up to 19 shapes.

Times when you want to blend between more than 10 shapes should be very rare. And even then you can probably get away with making another shape to get the resulting shape you want.


I would consider the curvature in that case too. If the curvature is small - then it is a flat region - so you can safely remove it - your 4th point for example. If the curvature is large (your 5th point for example), even if the distance is the same, you should most likely leave it alone.

I would actually recommend a curvature based method coming before Douglas-Peucker.


Ray tracing in One weeked: issue with metal reflection

The problem was in the way I was calculating the function bool Sphere::hit(). The author eliminates some redundant 2's that cancel each other without explicitly showing it, and if you don't pay attention to this detail the code the hit function will not work as it is supposed to. In case someone else is stuck, that might be the problem.


How can a diffused(frosted) glass be modelled in path tracing

Assuming that you are familiar with the concept of BSDFs, the usual way of modelling rough dielectric surfaces (i.e. glass, water, plastics) is to use microfacet-based models like Microfacet Models for Refraction through Rough Surfaces.

To make it work efficiently in a path tracer you will need a good sampling strategy, like Importance Sampling Microfacet-Based BSDFs using the Distribution of Visible Normals.

Also keep in mind, that the mentioned BSDF model tends to get darker as you increase roughness because it neglects the light which gets inter-reflected among micro-facets. This can be compensated, but it's not a trivial thing to do.


While this MSDN page does claim that SV_RenderTargetArrayIndex can be written in a pixel shader, I believe this is incorrect. Viewport array index and RT array index values are both intended to be output by the geometry shader stage. They can then be read by the pixel shader (and have a constant value per-primitive, based on the GS output). However, it is not possible to set these values from the pixel shader.

The stereo instancing approach detailed in those slides is interesting precisely because it avoids using slow geometry shaders. However, if you're not using GS, you can't use multiple viewports or render target arrays. That's why the stereo instancing approach uses one large viewport and bakes each eye's viewport transform into its projection matrix, and requires clip planes.

Clip planes should work, so if you're having problems with them, you could post another question detailing the specific issues (preferably with screenshots) and we can try to figure that out.

(For completeness, note that if you're using OpenGL, the GL_AMD_vertex_shader_viewport_index extension is available on recent GPUs from all three IHVs and allows setting the viewport index from the vertex shader.)


How can I chase down VRAM & GTT memory leaks?

Probably not. Most OpenGL resources (framebuffers, vertex buffer objects, textures &c.) are controlled by host code (i.e. your C++ code), but take up GPU memory. OpenGL doesn't make it very easy to manage these resources, so it's most likely that they're being created but not deleted from your C++ code. For example, it might create a new VBO per frame but never delete the old VBOs.
I've never used it for this purpose, but if you're on Windows I'd suggest RenderDoc as your first stop. It's not specifically designed for debugging source - it intercepts GL and DX calls so you can see how the application is using the library even if you don't have the source - so it won't point you to the offending line of code, but it does show you what resources are being created and when, so it should at least tell you what is being leaked and how often. It might even be that this is enough information is enough for you to guess the rest, or that the easiest way to continue after this is to do something by hand (e.g. printing __FILE__ and __LINE__ every time such a resource is created).

Sorry this is a bit of a half-answer but it's too big for a comment. I hope it gives you a good starting point at least.


As you are taking the mean of a number of sine waves, your colour values will range from -1 to 1. From your example image, it looks like only the top half of this range of values (from 0 to 1) is resulting in colour, with everywhere else remaining black.

If whatever you are using to display the result can only handle positive values, then you will need to convert the result to the correct range of values. For example, to convert from the range [-1 to 1] into the range [0 to 1], you would add 1 and divide by 2.

In the context of your example code, this could be by following the line

color /= (float)_iterations;

with

color += 1;
color /= 2;


Why does substracting -1 in shader fail for a float data type?

Without seeing the error message I can't be sure but I think it's failing on the 1 being int instead of a float.

float inv_coord = v_coord - 1.0;

There is a simpler method, you can do 1.0 - v_coord and do away with the abs.


Strategy for connecting 2 points without intersecting previously drawn segments of curves

The general problem is called graph drawing and is not an easy problem.
The graphs that can be drawn on the plane without crossings are called planar, but not all graphs are planar: the typical graphs that are not planar are the complete graph on $5$ vertices $K_5$ and the complete bipartite graph on 6 vertices $K_{3,3}$, famous because of the three utilities problem.
You may want to try Graphviz - Graph Visualization Software to produce nice drawings.
See also

Szirmay-Kalos, László, Dynamic layout algorithm to display general graphs, in Graphics Gems IV, 1994. code
Rosati, Claudio, A simple connection algorithm for 2-d drawing, Graphics Gems III, 1992, code.


What part of the graphics chain rotates computer displays when in portrait mode?

On typical GPUs today it's option B: monitor rotation is done by the video output hardware ("display engine") during scan-out. In addition to rotating/flipping, the display engine can also scale the image within certain limits, do simple color/gamma correction, and even composite multiple image layers ("planes") together, all dynamically during scan-out.


You aren't doing perspective correct texturing. At each pixel, $(X,Y)$, you need to be computing U and V with the equivalent of:

$U=\frac{aX+bY+c}{pX+qY+r}$

$V=\frac{dX+eY+f}{pX+qY+r}$

The denominator of both is linearly interpolating 1/W, while the numerators are, respectively, interpolating U/W and V/W.

I.E. for each triangle vertex you need to compute 1/W, U/W and V/W and then interpolate these. You can do it via barycentrics if you wish but you must do the division per pixel.


"whiteness" in center of bright colored lights - what is it called?

In general this is caused by HDR tone mapping. Tonemap curves typically decrease saturation as the input light gets brighter, so that very bright lights are rendered closer to white on the display. If bloom is rendered in HDR (prior to tonemapping) then the bloom around the light can still be highly saturated since it is of a lower intensity than the light itself, and so doesn't get desaturated by tonemapping as much.
You can see some good examples of this on the UE4 Color Grading and Filmic Tonemapper docs page. Unreal uses the ACES tone mapping curve, which is a pretty good default tone curve that you can easily hook up in your own shader code as well.
That said, lightsabers in Star Wars games are probably a special case visual effect that's tuned specifically to reproduce how they look in the movies. :)


As far as I know there are no tools that allows you to steps through code in a shader (also, in that case you would have to be able to select just a pixel/vertex you want to "debug", the execution is likely to vary depending on that).
(NOTE: Renderdoc allows you to do so by selecting a specific thread/pixel)
What I personally do is a very hacky "colourful debugging". So I sprinkle a bunch of dynamic branches with #if DEBUG / #endif guards that basically say
#if DEBUG
if( condition )
    outDebugColour = aColorSignal;
#endif

.. rest of code ..

// Last line of the pixel shader
#if DEBUG
OutColor = outDebugColour;
#endif

So you can "observe" debug info this way. I usually do various tricks like lerping or blending between various "colour codes" to test various more complex events or non-binary stuff.
In this "framework" I also find useful to have a set of fixed conventions for common cases so that if I don't have to constantly go back and check what colour I associated with what.
The important thing is have a good support for hot-reloading of shader code, so you can almost interactively change your tracked data/event and switch easily on/off the debug visualization.
If need to debug something that you cannot display on screen easily, you can always do the same and use one frame analyser tool to inspect your results. I've listed a couple of them as answer of this other question.
Obv, it goes without saying that if I am not "debugging" a pixel shader or compute shader, I pass this "debugColor" info throughout the pipeline without interpolating it (in GLSL with  flat  keyword )
Again, this is very hacky and far from proper debugging, but is what I am stuck with not knowing any proper alternative.


The hint with the perspective division was already mentioned by ratchet freak, but I'd like to add some explanation of how to come up with the solution.

First of all, remember that homogenous coordinates add a fourth value $w$ to your 3D vector. For points in the 3D space, $w \neq 0$ holds and $[x, y, z, w] = [n*x, n*y, n*z, n*w]$ also holds for every $n$.

Now the goal is to find a transformation matrix $T$, which solves

$$
    \begin{bmatrix} \frac{2}{x + y} \\ \frac{5y + z}{2x + 2y} \\ 3 \\ 1 \end{bmatrix}
= T \cdot
\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}
=
\begin{bmatrix} t_{11} & t_{21} & t_{31} & t_{41}  \\ t_{12} & t_{22} & t_{32} & t_{42} \\ t_{13} & t_{23} & t_{33} & t_{43} \\ t_{14} & t_{24} & t_{34} & t_{44} \end{bmatrix}
\cdot \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}
$$

These are basically four equations, but having a look at the first row, being

$$\frac{2}{x + y} = t_{11}\cdot x + t_{21}\cdot y + t_{31} \cdot z + t_{41}$$

and trying to find values for the $t$s, you'll see that this is not possible without further restructuring. The main problems are the $x$ and $y$ in the denominator. But as we can make use of the fourth value in the vector, we can expand the $w$.

$$
\begin{bmatrix} \frac{2}{x + y} \\ \frac{5y + z}{2x + 2y} \\ 3 \\ 1 \end{bmatrix}
=
\begin{bmatrix} \frac{2}{x + y} \\ \frac{2.5y + 0.5z}{x + y} \\ 3 \\ 1 \end{bmatrix}
=
\begin{bmatrix} 2 \\ 2.5y + 0.5z \\ 3(x + y) \\ x + y \end{bmatrix}
$$

In the first step, I removed the factor of $2$ from the second values denominator, leading to every values denominator either being $1$ or $(x + y)$. In the second step, I made use of the above mentioned rule ($[x, y, z, w] = [n\cdot x, n\cdot y, n\cdot z, n\cdot w]$), setting $n = (x + y)$, thus eliminating the denominator of the first two values.

Now we've got

$$
\begin{bmatrix} 2 \\ 2.5y + 0.5z \\ 3(x + y) \\ x + y \end{bmatrix}
=
\begin{bmatrix} t_{11} & t_{21} & t_{31} & t_{41}  \\ t_{12} & t_{22} & t_{32} & t_{42} \\ t_{13} & t_{23} & t_{33} & t_{43} \\ t_{14} & t_{24} & t_{34} & t_{44} \end{bmatrix}
\cdot
\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}
$$

which is not that hard anymore.

$$
\begin{bmatrix} 2 \\ 2.5y + 0.5z \\ 3(x + y) \\ x + y \end{bmatrix}
=
\begin{bmatrix} 0  &  0 &   0  &  2   \\ 0 &  2.5 & 0.5 &  0 \\ 3 &   3  &  0 &   0 \\ 1  &  1  &  0  &  0 \end{bmatrix}
\cdot
\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}
$$

TL;DR

Remember the advantage of homogenous coordinates $w$.
$[x, y, z, w] = [n\cdot x, n\cdot y, n\cdot z, n\cdot w]$ is the key.
Push everything that's in the denominator to the $w$ coordinate.


What is this technique called and how can I reproduce it algorithmically?

I've done something similar. The way I did it was by using a height map image to change the positions of vertices in a grid in a vertex shader. I generated a 2D grid of vertices that were evenly spaced on the CPU. I uploaded the vertices and a texture and in the vertex shader, I sampled the texture and used the resulting brightness as the height. So I'd keep the x and y positions of each vertex and change the z based on the image.

Now there are other ways you could utilize this to get something more like in the video. You could either have a 2D grid of single vertices, or even a grid of small 3D models. Change the z position based on the color of a height map. But additionally, you could upload a small noise texture and vary the x and y positions by a small amount based on the noise, which might vary per frame. I would see if you could vary the x and y by a large enough amount to see, but small enough that no point ever crossed over a neighbor point. That would get you some more movement and randomness.


Rotate a model or a view with mouse input to produce intuitive results

Here's a more complete answer from my comment. The end product we want is:

Projection * ViewTranslate * Model * ViewRotate

All are 4x4 matrices. Where model is your models transformations. To implement you can just separate out the view's translate and rotate during your draw.

If you're using an abstraction that requires you to use Proj * View * Model. Or you just really don't want to ruin your own abstraction that follows that pattern. You'll need to modify model to cancel out views rotational part and put it on the right side:

Model = ModelTranslate * View^-1 * ViewTranslate * ModelRotate * ViewRotate
      = ModelTranslate * ViewRotate^-1 * ModelRotate * ViewRotate

Here's some of my code that does the above. It does not matter if model or view is translated, objects will still rotate around their local origins:

glm::vec2 diff = (prevMousePos - mousePos) * rotSpeed;
glm::mat4 rotX = MathHelp::matrixRotateY(diff.x);
glm::mat4 rotY = MathHelp::matrixRotateX(diff.y);

// Decompose the translate and rotate part of view
glm::mat4 viewT, viewR;
Decompose(cam->view, viewT, viewR);

// Decompose the translate and rotate part of model
glm::mat4 modelT, modelR;
Decompose(exampleObj->model, modelT, modelR);

exampleObj->model = modelT * glm::inverse(viewR) * rotX * rotY * viewR * modelR;

This preserves the existing rotation and translation in exampleObj->model as the function gets called continually applying small rotations. And assumes you'll be using Proj * View * Model.

Lastly decompose just separates out the 3x3 rotation/scaling from the translational part:

void Decompose(glm::mat4 m, glm::mat4& t, glm::mat4& r)
{
    glm::mat4 I4 = glm::mat4(1.0f); // Identity
    for (unsigned int i = 0; i < 4; i++)
    {
        for (unsigned int j = 0; j < 4; j++)
        {
            if (i == 3 || j == 3)
            {
                r[i][j] = I4[i][j];
                t[i][j] = m[i][j];
            }
            else
            {
                r[i][j] = m[i][j];
                t[i][j] = I4[i][j];
            }
        }
    }
}


Which techniques do I need to animate a 3D model in my homemade engine

First decide how you are going to animate the model.

The simplest way is to just have a separate mesh per frame of animation. This requires more memory to be dedicated to mesh data more artist time to create them and it locks you into only those poses.

The next step upwards is interpolating between full meshes (keyword morph targets). This works great for facial expressions especially if you can give different weights for each vertex. It's not that great for full body animation because it's difficult to get proper circular motion into it.

The most common technique for full body animation is skeletal animation. Instead of full meshes for each frame of animation you instead have a set of model transform per "bone" and each vertex has a set of weights to decide which bones it follows. In the vertex shader you then interpolate the transforms as appropriate and then apply the interpolated transform to the vertex. This has the upside that different meshes can use the same animation data assuming the bones are set up the same.


Intrepret path/light tracing by rewriting light transport equation

Having the rendering equation one can rewrite it in operator form:

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

The last equality holds if $T$ is a contraction ($\|T\| < 1$), and under very specific conditions if $T$ is not a contraction. An example of when the 4th equality does not hold would be picking an enclosed volume bounded by some surface, that is made of a non-energy conserving material, and putting a light source inside. Then the radiance will keep increasing with every bounce so at some point $L$ will be infinity everywhere on the inside of the volume. Meaning that the the series does not converge.

The 4th equality is really the Liouville-Neumann expansion. So you get an infinite sum of increasingly-dimensional integrals, each subsequent term being a bounce away from the previous. Each term gives you the contribution due to a light path of length equal to the index of the term.

More precisely, this solution gives you the steady state $L$ if it exists (we assume that light travels instantaneously, that it is incoherent, linear etc). Note that $L$ is simply the radiance function, so this formalism really gives you the solution at every point in the scene.

In practice you usually need only the radiance measured at the surface of a virtual camera film. So a straightforward optimization is to trace rays starting from the surface of the camera film. This does not guarantee that you get the solution for $L$ at every point of the scene, but is a lot more efficient. You can also trace rays starting at the light source, but you are usually also interested in their contribution to the film, so the measurement function (see Veach's thesis) has to also make it in there, and only a subset of lights may be of interest. Finally you can do photon mapping, or light tracing where you are interested of the radiance over the whole scene, and that would be the closest thing to the original formulation.


Which 3D algorithms does Windows 10's "3D Builder" application use?

Well obviously nobody except the makers of this program can answer the exact algorithms used. I have done a quick explanation on each. Each separate task really deserves its own question and answer.

Just iterate each polygon, for each vertex check if all of them are above the cut line eliminate the face. To make this check easy you can transom each vertex to the plane orientation. If not all vertices are above the cut line then the triangle is split along one of the edge that has a eliminated vertex. Then use the internal face closing algorithm. Heres some math.

Face closing algorithm works by finding open edges and then tessellating the new polygon closed. Please note: That this produces somewhat erratic results if the open holes are not planar. See polygon triangulation

Simplifying planar regions is basically the same face closing algorithm except they you first build up polygons out of regions. Also decimation might come to play. There is a lot of lore, and different algorithms for simplification and going trough all of it its way too bread for a post like this.

Self intersection is a sorting problem. Quite a bit of lore on this exists too. The one that i mostly do is putting the polygons one by one into a BSP self organizing tree and checking against polygons against items in that tree to reduce the check complexity to n log n.

Internal cavities can be detected by splitting each mesh into shells and then for each shell check if the other shell is contained within each other. See this post


Matching a virtual camera to a physical camera

This is the Camera re-sectioning problem.

We need to have a few points, like the end points of the walls, to take the roles of xw, yw and zw in the following equation:

Here A is defined as:

These are the values of the camera itself.

R and T are defined as the Rotation and Translation matrices for the camera, and are the values we need to solve for. The position, C, of the camera expressed in world coordinates is C = -R-1T = -RT T .

The linked Wikipedia article mentions a few algorithms to solve these equations.

An example of a practical application of these is also found on Math Stack Exchange.

Another example, with some code samples that you may want to use, is found Stack Overflow.


Path tracing is the standard technique in non-realtime photorealistic rendering, and you should look specifically into bidirectional path tracing to get effects like caustics, which you can't really get with basic path tracing. Bidirectional path tracing also converges faster to the ground truth as shown in the below image:

Also Metropolis light transport (MLT) is a more advanced path tracing technique that converges even faster to the ground truth by mutating existing "good" paths:

You can also use importance sampling for faster convergence by focusing more rays to the directions that matter more. I.e. by focusing rays based on BRDF (more towards the BRDF spike using probability density function) or to the light source, or get best of the two worlds and using multiple importance sampling.

This is all about reducing noise in unbiased manner. There are also denoising techniques to further reduce noise in the rendered images.

I think it's best to first implement basic brute force Monte Carlo path tracer to serve as unbiased reference before looking into the more advanced techniques. It's quite easy to do mistakes and introduce biasing that goes unnoticed, so having simple implementation is good to have around for reference.

You can also get some really nice results by applying path tracing to participating media but that gets slow really fast :D


You are doing completely different things in Matlab than in your Fragment Shaders.

In Matlab you are generating bunch of points that can be drawn anywhere on the screen and then you are transforming them. This would be loose equivalent of your Matlab code in Fragment Shader:

#define ARRAY_SIZE 256

void main() {
    vec2 st = gl_FragCoord.xy / u_resolution.xy;
    st = st * 2.0 - 1.0;
    st.x *= u_resolution.x / u_resolution.y;

    //the angle to rotate:
    float ang = u_time * 0.5;

    //Transform coordinates:
    float c = cos(ang);
    float s = sin(ang);
    mat2 trans = mat2(c, s, -s, c);

    // our domain is from -1 to 1 so total length is 2.0
    float xStep = 2.0 / float(ARRAY_SIZE);

    // How far we are from current pixel location to the curve
    float minDist = 1e3;

    // initialize points
    for (int i = 0; i < ARRAY_SIZE; ++i) {
        float x = -1.0 + float(i) * xStep;

        // initialize points
        vec2 cp = vec2(x, 0.08 * sin(x * 40.0));

        // transform
        cp = trans * cp;
        minDist = min(minDist, distance(st, cp));
    }

    // Add some contrast:
    float d = pow(minDist, 0.1);

    vec3 col = vec3(fract(d));
    gl_FragColor = vec4(col, 1.0);
}

(Here is the live version: http://thebookofshaders.com/edit.php?log=180516153813 ).

For drawing I'm using distance to points because of simplicity, but better way would be to use distance to line segments that the points should be connected by.

In the other hands, in your fragment shaders you are first calculating something relative to a fixed pixel location (gl_FragCoord.xy), then transforming it in a way that it is not valid from the pixel's point of view any more, and then you are hoping that you can calculate proper distance to it.
Unfortunately this won't work.

(Example of fixed location of a Fragment Shader invocation)

But what you can do is first rotate the domain (and not result of your calculations), and then perform all calculations in it:

// Plot a line on Y using a value between 0.0-1.0
float plot(vec2 st, float pct){
  return  smoothstep( pct-0.02, pct, st.y) -
          smoothstep( pct, pct+0.02, st.y);
}

void main() {
    vec2 st = gl_FragCoord.xy / u_resolution.xy;
    st = st * 2.0 - 1.0;
    st.x *= u_resolution.x / u_resolution.y;

    //the angle to rotate:
    float ang = u_time * 0.5;

    //Transform coordinates:
    float c = cos(ang);
    float s = sin(ang);
    mat2 trans = mat2(c, s, -s, c);

#if 1
   // You need to transform domain first:
   st *= trans;

   // then perform the calculations:
   vec2 cp = vec2(st.x, 0.08 * sin(st.x * 40.0));
#else
    // This won't work (your old way):
    vec2 cp = vec2(st.x, 0.08 * sin(st.x * 40.0));
    cp = trans * cp;
#endif

    vec3 col = vec3(fract(distance(st, cp)));
    col.r += plot(st, cp.y);

    gl_FragColor = vec4(col, 1.0);
}

(Live version: http://thebookofshaders.com/edit.php?log=180516154712 )


Does the original Perlin noise ever have any advantage over Simplex noise?

To directly answer the question: Simplex noise is patented, whereas Perlin noise is not. Other than that, Simplex noise has many advantages that are already mentioned in your question, and apart from the slightly increased implementation difficulty, it is the better algorithm of the two.

I believe the reason why many people still pick Perlin noise is simply because it's more widely known. It's also worth noting that Perlin noise is very frequently confused with a combination of value noise and Fractal Brownian Motion (FBM).

Perlin noise, Simplex noise and value noise are all methods for synthesizing coherent noise. On the other hand, FBM (sometimes called "FBM noise"), is what is used when adding multiple layers of noise on top of each other at different scales to obtain more complex functions. The combination of FBM and value noise is simple to implement and can be very useful for terrain synthesis, procedural clouds and friends, and it is quite popular. However, it tends to be mistakenly labelled Perlin noise, misleadingly adding to its popularity.


It just depends on which space your light directions are actually specified in. You compute both your normal and view vector correctly in view space in order to perform your lighting computations in view space. So you need your normalized light direction in view space, too.

So it depends on how you actually transfer your light direction into the shader. Usually it's best to transform the light direction into view space before uploading it to the shader (from whatever space it's originally in in the scene, likely some kind of object space local to a certain light source, but in case of a directional light maybe already in world/view space). This has a few advantages:

As you realized yourself already, you won't have to perform a tedious matrix transformation for each and every vertex when the light is actiually constant for all vertices of a draw call (it's probably a uniform variable). While a matrix multiplication per-vertex doesn't really kill anyone, there's really no need to do that extra work, in contrast to simply transforming the light direction on the CPU once a frame.
But there's another problem to transforming it in every shader call. Usually your light direction isn't easily specified in object space at all (or not the local object space of whatever object your currently drawing). If anything, it comes from a local light source that has its own model transformation, but that is not the one encapsulated in the current modelview matrix, which usually depends on the model you're drawing. So using the modelview matrix you transform your vertices with is most likely the wrong way. You could use the view matrix (as you do) if it is specified in world space already, but as said above, that's usually not necessary.

So what you do depends on the space in which your light direction is stored in the scene. If it is stored in world space (e.g. the sun as the directional light example par-excellence), you just have to transform it into view space (e.g. by multiplying it with the camera/view matrix) right before uploading it into the shader (i.e. likely each frame, since it's view dependent). If it is actually view independent (e.g. a kind of "flashlight" always shining straight into the camera direction), you don't really have to transform it at all. And if it's local to some specific scene object (more appropriate for point light sources, though), you transform it by that object's modelview matrix.


As I said in the comments, this is indeed called torus or toroidal space when it comes to the topology. Even if the images suggest something 3 dimensional, this is just a visualization of the embedding of such a space in $\mathbb R^3$.

Regarding the distance between two points, I think you mean following:
Just consider the coordinates $p=(x_1,y_1)$ and $q=(x_2,y_2)$ in the $[0,X)\times [0,Y) \simeq (\mathbb R / X\mathbb Z)\times (\mathbb R / Y\mathbb Z)$ square. Then define all the translations $q_i$ of $q$ :

$$
\begin{align*}
q_0 &= (x_2\hphantom{+X\,\,\,},y_2\hphantom{+X\,\,\,})\\
q_1 &= (x_2+X,y_2+Y)\\
q_2 &= (x_2\hphantom{+X\,\,\,},y_2+Y)\\
q_3 &= (x_2-X,y_2+Y)\\
q_4 &= (x_2-X,y_2\hphantom{+X\,\,\,})\\
q_5 &= (x_2-X,y_2-Y)\\
q_6 &= (x_2\hphantom{+X\,\,\,},y_2-Y)\\
q_7 &= (x_2+X,y_2-Y)\\
q_8 &= (x_2+X,y_2\hphantom{+X\,\,\,})
\end{align*}$$

Then I think the distance you're looking for is

$$d(p,q) = \min_{i=0}^8 \Vert p-q_i \Vert$$


Lambertian shading illuminates all the front of a sphere

I think there is a problem with your ray-sphere intersection.
It should go like this
sphere_normal = ray.origin - sphere_center;
b = dot(sphere_normal , ray.normalized_dir);
c = dot(sphere_normal , sphere_normal ) - sphere_radius*spheres_radius;
float disc = b * b - c;

float t = -1.0f;
if(disc >= 0.0f)
t = -b +- sqrt(disc);

if(t >= 0) // means ray intersects...

Check out scratchapixel to understand how I got this.
https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-sphere-intersection


Compute shader not updating buffer, or vertex buffer unable to read the updates

Got help from someone over in the OpenGL subreddit.  Apparently, as I trimmed the code for posting here and there, I changed the operation of the code.

What I trimmed to this:

void main()
{
    uint index = gl_GlobalInvocationID.x;
    Particle p = AllParticles[index];

    vec2 deltaPosition = p._velocity * uDeltaTimeSec;
    p._position = p._position + deltaPosition;

    AllParticles[index] = p;
}

Was more or less this:

void main()
{
    uint index = gl_GlobalInvocationID.x;
    Particle p = AllParticles[index];

    // update position
    vec2 deltaPosition = p._velocity * uDeltaTimeSec;
    deltaPosition = vec2(0.0f, 0.0f);
    //p._position = p._position + deltaPosition;
    p._position = deltaPosition;

    AllParticles[index] = p;
}

Which should have been this:

void main()
{
    uint index = gl_GlobalInvocationID.x;
    Particle p = AllParticles[index];

    // update position
    vec2 deltaPosition = p._velocity * uDeltaTimeSec;
    //deltaPosition = vec2(0.0f, 0.0f);
    p._position = p._position + deltaPosition;
    //p._position = deltaPosition;

    AllParticles[index] = p;
}

So I really just did that.  The redditor who helped me downloaded my source code via github and found the error.  Standard case of one pair of eyes glossing over an error.

All is well now.


Vulkan: efficient way to update VBO mesh vertices?

With OpenGL I would have to reload whole vertex VBO's.

No you wouldn't.  You can use glBufferSubData

  I suppose with Vulkan there could be a way to directly access VBO's to only change/add/remove the changed vertex data

If you know the memory layout of the vertex buffer, you can find the offset of the contents you want to change, populate a transfer buffer with the new data and then uss vkCmdCopyBuffer to copy the data.  The VkBufferCopy parameter lets you specify the size as well as the source and destination offsets.  In other words, every call to vkCmdCopyBuffer is basically the equivalent of N calls to glBufferSubData

To clarify, updating a vertex buffer on Vulkan is almost the same as populating it.  If you're on a desktop architecture where device local memory is typically not mappable, then you have to create a transfer buffer that is host visible.  You can populate that buffer with a memcpy (or whatever), and then use vkCmdCopyBuffer to transfer it to the device local memory backed buffer.  If you're on a mobile architecture with unified memory, then device local memory is typically also host visible and so you can just map it directly and update it with your memcpy (or whatever)


Let the horizontal FOV be given as theta (in radians), and the vertical FOV be given as phi (in radians). The we know that:

$$\tan\frac{\theta}{2}=\frac{w}{f}, \tan\frac{\phi}{2}=\frac{h}{f}$$

Let us pick $f = 1$, then $w = \tan\frac{\theta}{2}, h = \tan\frac{\phi}{2}$. Now your ray generation direction generation formula looks like:

$$\pmb{d} = x w\pmb{u} + yh\pmb{v} + \pmb{w}$$

Where $\pmb{u},\pmb{v}, \pmb{w}$ are your sx,sy, forward vectors. Essentially, I found the extent of the smallest/largest x and y respectively ($1w = w, -1w=-w$, etc.). You can premultiply $\pmb{u}, \pmb{v}$ with $w, h$ respectively, if you don't want to perform the multiplication per ray.


Calculating the gradient of a tetrahedral mesh

Assuming a value is assigned to each vertex of the mesh and we use purely linear interpolation, then there will be a constant gradient vector within each tetrahedron.
Linear interpolation can be expressed using barycentric coordinates, like
$$
f(x,y,z) = f_1 w_1(x,y,z) + f_2 w_2(x,y,z) + f_3 w_3(x,y,z) + f_4 w_4(x,y,z)
$$
where $f_1 \ldots f_4$ are the values of the function at the four vertices, and $w_1 \ldots w_4$ are the barycentric weights for each vertex. Then, finding the gradient of $f$ reduces to finding the gradients of all of the weights.
This can be worked out geometrically by noting that each $w_i$ is 1 at the $i$th vertex, falling off to 0 at the plane formed by the other three vertices. The gradient vector will therefore be normal to that plane, pointing back towards the $i$th vertex, with a magnitude equal to 1 / the distance from the plane to the vertex.
Once you've calculated those barycentric gradients, you can multiply them by $f_1 \ldots f_4$ and sum them up to arrive at the gradient of $f$ overall.
This reasoning works for triangles too, by the way, only replace "plane" with "line".


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.


Why does rotation about an arbitrary axis have degree of freedom 6

The length of the axis is irrelevant and so you can remove one degree of freedom.


If depth testing is disabled, the triangles get drawn in the order they're submitted, i.e. the order they appear in the index buffer or vertex buffer. Later ones will overwrite earlier ones, or blend over them if blending is enabled. This ordering is guaranteed by all GPUs and APIs as far as I know.


I dont know what you are using to calculate the Cotan, the accuracy should different on the implementation.
But you could do more accurate calculations yourself by approximating the values using taylor expansions.
Or find some other librar that can do it more accurate.
Also, make sure you are using high prec datatypes.


It speed does not matter, I suggest to use a truncated sinc or a Lanczos isotropic kernel: to compute a target pixel, you back-rotate the filter and  convolve it with the image. Since it is isotropic, it is separable and you can even use a square filter parallel to the axis of the source image.


Using RGB texture format for image load/store

RGB8 format and similar are often not supported by GPUs (or only supported for a subset of GPU operations) because they don't have a power-of-two number of bytes per pixel. RGB8 would be 24 bits or 3 bytes per pixel. All the formats in that list have 1, 2, 4, 8, or 16 bytes per pixel.

Using a power of two simplifies addressing calculations in the hardware, because it can be implemented using a shift instead of a full multiply. (A shift by a fixed value such as 2 bits can even be implemented in hardware without any actual "calculations" at all, just by routing wires.) It also means that pixels are always nicely aligned with respect to boundaries of memory pages, cache lines, etc., which no doubt simplifies many things in the hardware.


Does it matter whether I learn OpenGL or Direct3D?

I don't think it matters much, which API you want to use when leaning to "program graphics". The more important things to learn are the typical concepts you use when working with 3D scenes. For example you want to learn how to write a simple (and later more sophisticated) Scene Graph. These concepts are much more important than the specific API method names you have to call.

Compare it when learning how to write programs. If you are quite good at writing programs in e.g. Java, you won't have that much trouble learning C++, Objective-C, Swift, or some other object-oriented language. Because it's the concepts and the thinking which you learn.

The choice between OpenGL, Direct3D and Metal is primarily the choice, which operating system you target. Direct3D is primarily available on Windows, Metal on OS X and iOS, and OpenGL is supported on most systems including OS X, iOS, Windows and Linux.

The graphics card probably has little to no influence on this decision as I don't know a card that supports only one or two. If you have no dedicated graphics card, then rendering in real time will be a problem soon. Although a Intel HD Graphics and the AMD companion can already do quite much.

So, choose your platform.

Disclaimer: As of now, I did neither use Direct3D nor Metal.


How to get started writing a low-level GPU profiler?

For basic GPU timing data, you can use D3D timestamp queries or the equivalent OpenGL timer queries.

Any low-level hardware data like cache misses is going to be extremely vendor-specific. Each GPU vendor has its own custom API or extension for giving access to low-level performance data on its hardware. The APIs vary in how they work, and they don't necessarily all expose the same details. The available data may also vary between different chip models within the same vendor, so you probably need to know a bit about how the hardware works to make sense of it.

Here are links to the relevant APIs for most of the main GPU vendors.

AMD: GPUPerfAPI; see also AMD_performance_monitor
Intel: Performance Counter Monitor (note: it's not clear to me whether this includes access to GPU counters, or only CPU ones); see also  INTEL_performance_query
NVIDIA: PerfKit
PowerVR: PVRScope
Qualcomm: QCOM_performance_monitor_global_mode


Is there a way for me to record every shading sample for a deep texture

If you really want to obtain every fragment (shading sample) within the camera frustum, regardless of occlusion, one way to do it would be to disable depth testing, and then use a large SSBO together with an atomic counter to append data into the buffer from the fragment shader.  Each fragment could then store a record of its screen position, depth, color, and any other desired information into the buffer to be read out later.  The buffer has to be large enough to store every fragment rendered, as it will throw away any extra data once it's full.

Using one huge SSBO for the whole screen likely isn't ideal, as there will be huge contention on its counter with every fragment trying to increment it.  A better way might be to slice up the screen in tiles with an SSBO+counter per tile.  There is a limit of 16 bound SSBOs on all current GPUs, and on AMD GPUs, there is a further limit of 8 atomic counters (source: Sascha Willem's OpenGL Hardware Database).  Those limits will determine how many tiles you can create. This will reduce contention and also ensure that even if you run out of memory in one tile, you'll still have valid data in the others.


Compute sphere tangent for normal mapping

You can do this a little bit more efficiently and accurately by calculating derivatives of $P$ with respect to $u, v$—or the derivatives with respect to $\phi, \theta$, equivalently (up to a scalar multiple).

Start by expressing $P$ in terms of the spherical coordinates:
$$\begin{aligned}
P_x &= r \cos \theta \cos \phi \\
P_y &= r \sin \theta \\
P_z &= r \cos \theta \sin \phi
\end{aligned}$$

Now you can get the tangent as $T = \partial P / \partial \phi$, which works out as:
$$\begin{aligned}
T_x &= -r \cos \theta \sin \phi \\
T_y &= 0 \\
T_z &= r \cos \theta \cos \phi
\end{aligned}$$

Once you normalize it, the $r \cos \theta$ factors drop out and you're left with just $T = (-\sin \phi, 0, \cos \phi)$. Pretty simple!

You can similarly get the bitangent as $B = \partial P / \partial \theta$, or you can just calculate it as the cross product $N \times T$, which is probably faster. (Note it should be $N \times T$, not $T \times N$, assuming you want $T, B, N$ to form a right-handed basis in that order.)

The above approach will work for pretty much any kind of surface that can be parameterized, not just spheres. However, in the case of spheres with the usual $\phi, \theta$ coordinates, there's an even quicker shortcut that you can do with just vector math, no trig at all. Let $C$ be the center of the sphere, and $A$ be a vector representing the axis of the spherical coordinates—i.e. pointing from the center toward the north pole. Then you can just calculate $T = \text{normalize}\bigl(A \times (P - C) \bigr)$, then $B = N \times T$ as before.


Finite difference wave equation shown in paper is wrong?

Yes, it looks like a sign error in the paper. It looks like it was introduced in equation (4) and then carried through the following ones.

Probably the authors wrote the source code first and the paper after, so did not notice that their equations did not match what their code was doing. Ideally it should have been caught in the paper review, but, mistakes happen.


Manually fetching 8 neighboring texels from 3D texture greatly decreases performance

What's probably happening is that you're doing indirect texture fetches. Are you doing something like this:

vec4 a = texture3D(sampler, coord);
vec4 b = texture3D(sampler, coord + vec4(0, 0, 1));
vec4 c = texture3D(sampler, coord + vec4(0, 1, 0));
vec4 d = texture4D(sampler, coord + vec4(1, 0, 0));
//...etc.

If so, that can slow you down. What you can do instead is to pass the texture coordinates for each sampler call into your vertex shader from your CPU code. You'd set it up as if you were doing multi-texturing, but all the texture units would point to the same texture, just sampled at different coordinates.

Taking the 2D case, instead of passing in a single texture coordinate like this:

float2 texCoords[] = {
    { 0, 0 },
    { width, 0 },
    { width, height },
    { 0, height }
};

You'd pass in 4 of them:

float2 texCoords[] = {
    // texture 0 coords
    { 0, 0 },
    { width, 0 },
    { width, height },
    { 0, height },

    // texture 1 coords
    { 1, 0 },
    { width + 1, 0 },
    { width + 1, height },
    { 1, height },

    // Texture 2 coords
    { 0, 1 },
    { width, 1 },
    { width, height + 1 },
    { 0, height + 1 },

    // Texture 3 coords
    { 1, 1 },
    { width + 1, 1 },
    { width + 1, height + 1 },
    { 1, height + 1 }
};

In your fragment shader, you'd do something like this:

vec4 pixel0 = texture2D(sampler0, coord0);
vec4 pixel1 = texture2D(sampler1, coord1);
vec4 pixel2 = texture2D(sampler2, coord2);
vec4 pixel3 = texture2D(sampler3, coord3);

Now you have the 4 pixels needed for interpolation, but there was no fragment shader math done to get the texture coords, so there are no indirect look-ups which are slower than direct look-ups.


How many polygons in a scene can modern hardware reach while maintaining realtime, and how to get there?

I think it is commonly accepted that real time is everything that is above interactive. And interactive is defined as "responds to input but is not smooth in the fact that the animation seems jaggy".
So real time will depend on the speed of the movements one needs to represent. Cinema projects at 24 FPS and is sufficiently real time for many cases.

Then how many polygons a machine can deal with is easily verifiable by checking for yourself. Just create a little VBO patch as a simple test and a FPS counter, many DirectX or OpenGL samples will give you the perfect test bed for this benchmark.

You'll find if you have a high end graphics card that you can display about 1 million polygons in real time. However, as you said, engines will not claim support so easily because real world scene data will cause a number of performance hogs that are unrelated to polygon count.

You have:

fill rate

texture sampling
ROP output

draw calls
render target switches
buffer updates (uniform or other)
overdraw
shader complexity
pipeline complexity (any feedback used? iterative geometry shading? occlusion?)
synch points with CPU (pixel readback?)
polygon richness

Depending on the weak and strong points of a particular graphic card, one or another of these points is going to be the bottleneck. It's not like you can say for sure "there, that's the one".

EDIT:

I wanted to add that, one cannot use the GFlops spec figure of one specific card and map it linearly to polygon pushing capacity. Because of the fact that polygon treatment has to go through a sequential bottleneck in the graphics pipeline as explained in great detail here:  https://fgiesen.wordpress.com/2011/07/03/a-trip-through-the-graphics-pipeline-2011-part-3/
TLDR: the vertices have to fit into a small cache before primitive assembly which is natively a sequential thing (the vertex buffer order matters).

If you compare the GeForce 7800 (9yr old?) to this year's 980, it seems the number of operations per second it is capable of has increased one thousand fold. But you can bet that it's not going to push polygons a thousand times faster (which would be around 200 billion a second by this simple metric).

EDIT2:

To answer the question "what can one do to optimize an engine", as in "not to lose too much efficiency in state switches and other overheads".
That is a question as old as engines themselves. And is becoming more complex as history progress.

Indeed in real world situation, typical scene data will contain many materials, many textures, many different shaders, many render targets and passes, and many vertex buffers and so on. One engine I worked with worked with the notion of packets:

One packet is what can be rendered with one draw call.
It contains identifiers to:

vertex buffer
index buffer
camera (gives the pass and render target)
material id (gives shader, textures and UBO)
distance to eye
is visible

So the first step of each frame is to run a quick sort on the packet list using a sort function with an operator that gives priority to visibility, then pass, then material, then geometry and finally distance.

Drawing close objects gets prirority to maximize early Z culling.
Passes are fixed steps, so we have no choice but to respect them.
Material is the most expensive thing to state-switch after render targets.

Even in-between different materials IDs, a sub-ordering can been made using a heuristical criterion to diminish the number of shader changes (most expensive within material state-switch operations), and secondly texture binding changes.

After all this ordering, one can apply mega texturing, virtual texturing, and attribute-less rendering (link) if deemed necessary.

About engine API also one common thing is to defer the issuing of the state-setting commands required by the client. If a client requests "set camera 0", it is best to just store this request and if later the client calls "set camera 1" but with no other commands in between, the engine can detect the uselessness of the first command and drop it. This is redundancy elimination, which is possible by using a "fully retained" paradigm. By opposition to "immediate" paradigm, which would be just a wrapper above the native API and issue the commands right as ordered by client code. (example: virtrev)

And finally, with modern hardware, a very expensive (to develop), but potentially highly rewarding step to take is to switch API to metal/mantle/vulkan/DX12-style and preparing the rendering commands by hand.

An engine that prepares rendering commands creates a buffer that holds a "command list" that is overwritten at each frame.

Usually there is a notion of frame "budget", a game can afford. You need to do everything in 16 milliseconds, so you clearly partition GPU time "2 ms for lightpre pass", "4 ms for materials pass", "6 ms for indirect lighting", "4 ms for postprocesses"...


First, that's the wrong memory barrier. The barrier is for how you intend to use the memory, not how it was written to.

  I'd like to hide the latency by reading the data written by the previous frame dispatch.

This is a general flaw in OpenGL: targeted synchronization of such memory operations is not possible.

In Vulkan, you can be extremely specific about both execution and visibility operations. When you start the dispatch, you can stick an event after it, which you can wait on using a specific execution and memory barrier.

In OpenGL, you only really have two tools: fence sync objects and a broad memory barrier that covers all prior commands which have executed. And sync objects don't actually ensure visibility. Yes, you can set a fence right after your dispatch, and spin on the CPU (doing actual work between checks of the fence). But even after the fence has completed, you can't guarantee visibility without firing off the barrier. And that barrier will affect all memory operations that were submitted before the barrier was called.

So if you had two dispatch operations, and call glMemoryBarrier after both of them, the barrier will wait on all of them, even if you only care about waiting for the first one.

The best you can really do is just delay the memory barrier call for as long as possible. But it's going to synchronize against all submitted commands when you call it.

You might also try... cheating. Use a persistent/coherent mapped buffer, and use a fence sync object on the CPU instead of calling the memory barrier. This is undefined behavior by the OpenGL specification, but on real systems, the fence sync should ensure execution of the operation, and the coherently-mapped buffer ought to ensure visibility.

But that doesn't mean it will. So don't expect miracles.


Correct post-displacement normal calculation (Y-component and epsilon)

The Epsilon is chosen to hit the appropriated Nyquist-Frequency avoiding aliasing. It refers to the highest frequency in your heightfield function. You'll need well knowledge of the definition of your function to find it. For example, the figure shows an iterated Brownian motion (IBM) which approximate Perlin noise. The frequency of each added noise function is given by . So the Epsilon would be the last added frequency: . That means the Epsilon is predefined for each Noise.

IBM by Hugo Elias approximating Perlin Noise.

  Might this be related to unprojecting mouse clicks? It always bothered me that you could throw a '0.5' in the Z-component, as mrdoob mentioned here:

Your first question has nothing to do with mouse picking in my opinion. Your mouse is defined in normalized-device-coordinates (NDC) meaning a click in a window is ranging from -1 to 1 in each direction. The Z component is not given since our screen is just 2-dimensional, meaning we have to select a value from -1 to 1. -1 refers to the near plane and 1 to the far plane.

For further information on that topic:
https://www.youtube.com/watch?v=DLKN0jExRIM&t=371s


why does black text have orange and blue pixels

This is called subpixel rendering.

The different primary colors in your monitor are not stacked on top of each other. Instead they are arranged near each other. Different monitors have different patterns but most commonly they are aligned so that the colors are side by side.

If you know the physical arrangement, then you can prepare the image so that you have calculated a different sample position for each color channel. In essence your boosting the resolution of your image so that you are treating each individual color as a separate pixel.

This, of course, means that you need to know the display orientation and have some data that can be shifted. The image wouldn't be all that useful on other monitors with different pixel alignments. So this is reserved for things that are dynamically generated, most often fonts.

It also means that when zoomed or presented on a medium with different or no subpixels, the effect will register as a blur. So zooming in on the pixels of a subpixel rendered image is not very good idea. For this reason it migth be a good idea to disable the effect if you make images for others to use and the subpixel alignment is unknown.


How can I implement a complex sinusoidal function?

One way to represent a complex-valued function in a bitmap is to use one color channel for the real component and one for the imaginary component. For example, rendering a complex plane wave (your equation) with R = real, G = imaginary looks like this (click for shadertoy):


Why do we have graphics frameworks like OpenGL and DirectX, when games could just draw pixels directly?

Speed is the most common reason why this is not done. In fact you can do what you propose, if you make your own operating system, its just going to be very slow for architectural reasons. So the assumption that its faster is a bit flawed. Even if it would be faster, it would be less efficient in terms of development (like 1% speed increase for 10 times the work).

Copying the data over from the CPU to the graphics card is a relatively slow operation. The less you copy the faster your update speed can be. So ideally you would have most of the data on your GPU and only update small chunks of data. There is a world of difference between copying over 320x200 pixels compared to 1920x1200 or more. See the number of pixels you need to update grows quadratically when the sides grow.

Example: It's cheaper to tell the GPU to move the image 10 pixels right than copy the pixels manually to the video memory in different locations.

Why do you have to go trough an API? Simply because it's not your system. The operating system can not allow you to do whatever you want for safety reasons. Secondly because the operating system needs to abstract hardware away, even the OS is talking to the driver trough some abstracted system, an API if you will.

In fact I would rate the likelihood that your system would be faster, if you just did all the work yourself, close to near zero. It's a bit like comparing C and assembly. Sure you can write assembly, but compilers are pretty smart these days and optimize better and better all the time. It's hard to be better manually, even if you can your productivity will be down the drains.

PS: An API does not make it impossible to do this update just like old games did it. It's just inefficient that's all. Not because of the API mind but because it is inefficient period.

PPS: This is why they are rolling out Vulkan.


Offline path tracer produces a darker image than expected

I have found the issue. The gamma correction was the correct value, the same as in the book (1/2), but the light source had the brightness of 1.0f. The book had set the light's brightness to 18.0f for all color channels.

This would introduce color overflow if left at that, and the very light areas (above 1.0f, and subsequently when converted, outside the range [0, 255]) would have wrong colors.

To fix this clamp the the pixel's color values.

Go through all samples and calculate pixel color.
Divide the color by number of samples
Apply gamma correction
Clamp colors in range [0, 1]
Finally, convert values to range [0, 255]

(I will accept this answer as a solution in 2 days because StackExchange doesn't let me to do it now.)


Does a sphere projected into 2D space always result in an ellipse?

Assuming a perspective projection and a view point external to the sphere, then the 'boundary' formed by the view point and the circle on the sphere which forms the horizon WRT the view point, will be a cone.

Doing a perspective projection (onto a plane) is then equivalent to intersecting this cone with the plane which thus produces a conic section. FYI the four, non-degenerate, cases are shown in this image from Wikipedia

An ellipse/circle is thus a possibility, but not the only one - unbounded parabolas or hyperbolas (and I guess if the plane passes through the eye, even degenerate cases ) are possible.


The depth of field is a characteristic of a camera lens setting, although the name "Depth of Field" is commonly used to describe the effect caused by such characteristic.

Camera lenses can only perfectly focus on one single point, but there is a distance for which the image will still look reasonably sharp. Such distance is what actually the Depth Of Field is. This distance is variable depending on various factors, but let's say for the sake of brevity that the easiest way to adjust it is by changing your camera aperture.

As for the circle of confusion it is helpful to look a pic from wikipedia:

In all of the three cases a single point is "projected" onto our image plane, but as you can see that is at different distances from the lens.

Basically because, as I said, not everything is perfectly in focus (that is the focal point is on the image plane), a point can be projected to our image plane not to a single point but to an area. This, as it is clear from the pic, is because the focal point is either before or after the image plane. This "circle" that is created on the image plane is what is called the circle of confusion.

Now from this should be clear that varying the depth of field you vary the CoC size, hence it can be used as a measure of the DoF itself and an intuitive one when thinking in terms of blurring.

As per how it is implemented in rendering there are really lots of methods out there. Usually in games is done as a post process using the depth information to split your scene in different "planes"; for example a focus plane that does not need to be blurred, a near plane and a far/background plane that need to be blurred. Once you blurred your planes you can composite them back together to get your final image.
How much you blur the various planes it is dependent on the effect you want to achieve. Advanced system usually implement this and other "lenses" effect using appropriate parameters coming from the photography world like the aperture.

Note that there are many ways to implement the effect, the one I described is just one way that also has variations (for example performing the whole thing at lower res). The limit is dependent on what your target is and how much you budgeted for this effect. You can go from adopting the "3 planes" method at extremely low res to computing the circle of confusion for each pixel and applying the consequent ad-hoc blur to that pixel.

EDIT: The comment from @NathanReed needs to be more in evidence as part of the answer:

  Matt Pettineo's blog posts How To Fake Bokeh and Bokeh II: The Sequel are great introductions to how to practically implement post-process DoF and address the typical artifacts you get from it.


Is it possible to store the plain buffer data in gltf files?

Embedding human readable data is not supported. However you can put the data into a data uri to store the data inline in base64 format.

"buffers": {
    "a-buffer-id": {
        "byteLength": 1024,
        "type": "arraybuffer",
        "uri"="data:application/octet-stream;base64,..."
    }
},


If you can use subdivision surfaces for 2D curves

Subdivision can be used for curves in 2D just as easily as for surfaces in 3D. Usually the subdivision algorithms applied to 2D are called subdivision curves. Subdivision curves do not suffer from the problem that subdivision surfaces have around extraordinary points and therefore all subdivision surfaces can easily be converted to (uniform) B-splines. This means that it equals to working with Bézier curves in most cases. This latter representation might be more advantageous as it possesses a closed form representation, such that curves can be evaluated easily at arbitrary parameter values.

A simple subdivision algorithm for curves is the following. Consider a polyline consisting out of $n$ points $P_0 \ldots P_{n-1}$. Than for every iteration do the following steps:

Every exisiting position $P_i => (P_{i-1} + 6 P_{i} + P_{i+1})/8$ then add new positions on every edge between existing points using $(4 P_i + 4 P_{i+1})/8$ and repeat. In the limit this procedure will converge to uniform cubic B-splines.

Some useful extensions for subdivison curves exists such as (semi-sharp) creases and boundary conditions


That is, to my knowledge, a problem without a proper solution. You're seeing the discrepancy between shading normal and geometry normal and it becomes obvious, that the shading normal is just a trick. PBRT has a paragraph on this, their solution is to look at the geometric normal to determine whether to call the BRDF (reflection) or the BTDF (transmission), then to pass the shading normal to the BxDF. Still, this doesn't work robustly in all situations.

This problem is also known and described for production proven render engines:
http://blog.irayrender.com/post/29042276644/shadow-acne-and-the-shadow-terminator
The solution suggested for iRay is to use displacement mapping instead of normal maps. This way, shading and geometry normal are in agreement again.


imageLoad() behavior for non-existent texel

No. When you use image load/store, you don't get to play "texture" games like playing with the border color, doing filtering on values, etc. You are fetching a texel from a particular location.
If you want this, you will have to detect the out-of-bounds access and choose to substitute an alternate value. You can query the image's size, so it should be easy enough to detect.


What can be reduce in peripheral circle and increase in foveated cirle?

Actually it's not that new of an idea -- it goes back to at least 1996.  I strongly suggest reading Microsoft Research's Foveated 3D Graphics.  (click 'View publication' and read the full pdf)
In a nutshell, human visual acuity is different near the center of vision compared to the peripheral.  The middle of the eye is packed more tightly with cone receptors making it more sensitive to detail and color.  In contrast, humans are quite sensitive to motion in their peripheral vision.  Evolutionarily speaking, it's a good idea to maybe take a look at that tiger sneaking up on you from the side.  Your motion perception will trigger a shift in your gaze so you can make sense of exactly what's trying to eat you.
The most obvious thing that's different is your ability to perceive detail (angular size).  Numerous things can be adjusted with the rendering to economize on detail.

Resolution can be reduced.
Texture sizes can be reduced.
Geometric (polygonal) detail can be reduced

Color perception is reduced in the periphery as well, therefore:

Texture maps with lower bit-depth can be used.
Precision of color calculations can be reduced.

CAUTION: There are nuances to making effective use of all of these techniques.  You have to be especially careful not to change the silhouette of the objects because the outer visual region is actually more sensitive to the motion differences that may be perceived by an edge jumping around.  It may also be tempting to turn off antialiasing, but artifacts introduced by crawling pixels are tantamount to motion and draw the eye to these artifacts.  Anti-aliasing sometimes needs to be increased negating the effects of foveated rendering.  A blended blurring technique is used that allows seamless transition between regions rendered at high-resolution and low-resolution. It's a complex subject -- read the paper.


realtime dynamic reflections, which way to go?

If there is only a single flat mirrored surface the solution is to render the scene twices, once normally. Afterwards you use stencil to mark the area where the mirror is visible.

Then only drawing into that area you render the scene again but mirror it around the mirror's plane and cull any geometry on the other side of the mirror.


It would seem that, in the second example, the morphNormals are targets while in in the first they are deltas.

This explains the difference in math used between the two pieces of code.


Algorithm to find the center of a Bezier curve

Bézier curves are mathematical entities and have no clearly defined center. One can in fact define many different things as the center of the Bézier curve. I have tried to depict some of the possible centers in image 1. More than this do exist.

Image 1: Some of the possible centers of a single span Bézier curve

In practice nearly all graphics applications geared for drawing use the center of the local bounding box (BB) as their center. Animation software usually have an additional concept of pivot so they use the ask user approach, if no input is made they often revert to BB center or simply local coordinate center. This is probably because the BB needs to be calculated anyway and getting its center is pretty easy to do (see A Primer on Bézier Curves).

The center of gravity metrics are also somewhat natural especially in an animation context, though nastier to compute. Easiest being to discretize the data and do the computation on the discrete input. This said some closed form solutions are possible for the curve center of gravity, but it's not a very nice equation to formulate and simplify.

Then we have the on the curve points: the midpoint by arc length and the point where the $t$ parameter is 0.5. In my mind the $t$ param is often problematic though easy to compute, and it loses meaning when you chain multiple Béziers after each other for a polybézier. The center of length of course is only natural as long as the curve is not closed.

We also define other possible centers, the center could be at the curve center of gravity of the hull, the average of the control points or the control cage BB center. Although in practice these do not seem to work out very well.

Please note: Although the curve in picture 1 shows the BB center quite near to some natural centers this this is not always the case for more complex curves and especially polybéziers.


Creating high quality background images for a game which have small areas of moving detail

The "modern equivalent" of animated GIFs is... MPEG. Or really, any decent movie compression format. These techniques are designed to spend fewer bits on static areas and more bits on moving ones. And better still, they're designed to be dynamic, allowing motion in any are at any time, rather than only in fixed areas.
So just make a short, looping movie of the "background image" you're trying to build. You may want to get into the details of the compression system you're working with, so that you can give lots of bits to the initial frame and fewer bits to moving areas.


Is it expected that a naive path tracer takes many, many samples to converge?

Without explicit light sampling, I'd expect very slow convergence.

Any path that doesn't happen to hit the light source before being terminated will be useless (contributes zero). Since you have a small light source, the vast majority of paths will not hit it. It would be interesting to add some statistics to your tracer to see how many paths return zero vs nonzero. I'd guess you'll find something like 99–99.9% of them are zero, so you're only getting one useful sample out of every 100–1000 or so paths traced.

Naive path tracing is more reasonable with e.g. a sky light, which almost every path can be expected to hit.


Technology for specific project 3d in c#?

I have done 3D graphics in c# with Managed DirectX. Nowadays people uses SharpDX and SlimDX instead. I have heard about XNA is easier for doing simple 3D games.

You can also use OpenGl since there are several bindings for C#. Some people find OpenGl simpler to understand than DirectX, and is cross platform.

Unity uses C# as scripting language, the Unity Engine is running the actual simulations. You are mostly configuring and scripting Unity for running your simulation. This is not just a technology to use in your C# project, this is the oposite, a platform for games that uses C# as one technology.

You can do 2D graphics with all the above technologies. For the simulation, in case you do not use Unity or other game engine capable of doing physics simulations, you would need to find or write a rigid body simulation for animating all your moving objects. For animating the tree you would probably need a spring system which is also simple to simulate along rigid bodies.


It's a interference pattern, called Moire pattern. You get them in signal analysis and various other fields. I guess it could be considered an optical illusion.

EDIT:

To elaborate, this occurs when a periodic waveform goes out of phase with the observer. In your case the periodic waveform are the lines when observed as a scanline (from left to right of the image or vice versa), and the observer is the image with a set number of horizontal pixels. In some parts, the pixel rasterization falls on pixel boundaries and then there is a watershed moment... should it be rasterized in pixel x, or x + 1. This then manifests as the wave pattern (due to the 'watershed' moment being slightly out of phase with the previous or next scanline i.e one scanline, pixel falls on x, the next scanline it falls on x+1). Also the display device can also have an effect. The moire in your image is much more pronounced on my computer monitor, than it is with my phone. (however this could be due to my phone’s browser scaling or applying some other filtering by default, which could help to reduce it).

Anti aliasing certainly helps, however moire can never be completely eradicated, only mitigated. Also note this can occur with rotated grids in orthographic, however perspective projection will certainly amplify this effect.


Moving each point of a surface in direction of corresponding normal

No this cannot be modelled by (non-uniform) scaling. It's fairly easy to construct a counterexample:

The issue is that the amount a section of the curve/surface grows depends on its curvature, not its orientation in space. Notice here that the circular arc grows uniformly in all directions (by a factor of $3/2$) whereas the length of the horizontal segments remains unchanged at a length of $2$.

Of course, if your surface is not only convex but also has constant curvature, then it's just a circular arc, and for circles your transformation is equivalent to uniform scaling. You can probably also construct curves of varying curvature where your transformation happens to correspond to non-uniform scaling, but for general convex surfaces, that's not the case.


How am I able to perform perspective projection without a near plane?

The near and far planes of a viewing frustum aren't needed for simple 3D→2D projection. What the near and far planes actually do, in a typical rasterizer setup, is define the range of values for the depth buffer.

Depths in the [near, far] range will be mapped into [0, 1] to be stored in the depth buffer. However, the depths aren't simply linearly rescaled. Instead, we use a hyperbolic mapping for depth: the value stored in the depth buffer is the reciprocal of the actual depth distance, with a scale and offset applied.

If you look at this curve and imagine moving the near plane value toward $z = 0$, the corresponding point on the $1/z$ curve would shoot up toward infinity. The math blows up and the depth buffer becomes useless (it suffers a catastrophic loss of precision).

The reason why we use the reciprocal instead of some other function of depth is basically convenience: the reciprocal depth interpolates nicely in screen space, and it fits naturally into the mathematical framework of perspective projections: there's already a divide by $z$ being applied to the $x, y$ coordinates.

If you'd like to know more, I have a short article on the topic: Depth Precision Visualized.


First of all we need to understand why do we need 4x4 matrices in the first place. With 3x3, we couldn't represent translation as it wasn't a linear transformation (it displaces the origin). So in order to avoid extra work, homogeneous coordinates and affine transformation was introduced.

Now instead of doing

$v' = Lv + t$

where L is a linear transform and t is the translation, we can do

$v' = Av$

Where A is the affine matrix. This makes it cleaner. So 4x4 matrices are a real necessity, we just can't work without them. In order to distinguish between vectors and points we use w = 1 for points and w = 0 for vectors. So you are suggesting to make this 4th dimension implicit and don't store it as it'll actually use space/memory.

  We can pretend that the 3 dimensional vector is 4 dimensional (imaginary w = 1). This is after all Computer Science, not math.

This works but up-to a certain extent. Using this approach we would have 4x4 matrices and 3 dimensional row/column vectors. But now when doing multiplication we will have to make a check whether it's point or vector and based on that we multiply the elements of the 4th column of the transformation matrix by 0 or 1.

This alone starts creating mess, check every time whether it's a point or a vector so why not just use the space for a single float more and get rid of this stupid check.

That aside most modern CPUs have SIMD registers 128 bits wide perfect to fit 4D vectors. If you are doing your calculations on the GPU, all the more reason to store 4D vectors as branching instructions are much more costly on the GPU.

If you start feeling the need to use 4D, great. If not then we still have the problem of composing matrix transformations. Instead of multiplying individual transformations with our vector we would like to pre-multiply all of the transformations then do a single vector-matrix multiplication. This can't work with projective transformations where we need to divide by "something"

Let's come to reason number 3.

  You will have to do division by w after projection matrix anyway. Why not divide by z then and get something like [x/z, y/z, z]. Both of them cost 1 computation.

This is the simple case for just a projective transformation. Consider the vector going through 5 or 6 transformations  and in the last comes the projective transformation. If we pre-multiply all these transformation to create a single matrix, you will notice that now when we multiply the vector with this combined transformation matrix the division factor isn't just a simple -z value. The 4th row of the matrix won't be 0 0 -1 0 as in the standard projection matrix. It might have changed due to multiplying all the transformations together. Now when you multiply that 4th row with the 4D vector, you will get your w value by which you need to divide now.


The Open Shading Language has a complete implementation which is based on this source code from Color Rendering of Spectra by John Walker, according to the comments. I can't vouch for its theoretical correctness but I have used it and it appears to work reasonably well.


intersection between line segments - narrowed precondition

The arbitrary line can be expressed as y = a*x+b (assuming it's not parallel to the y axis).

If the other line is parallel to the y axis then you can simply fill in the x coordinate of any point on the line into the formula of the first line. Then you can check whether they intersect by ensuring the result lies between the endpoints of the second line.

For the second line parallel to the x axis you just flip the x and y coordinates.


GL_STATIC_DRAW vs GL_DYNAMIC_DRAW vs GL_STREAM_DRAW: does it matter?

This will vary between implementations, but the driver I worked on did use these, mainly to decide memory layout. The optimizations enabled by these hints are much smaller than you would like, mainly because of the restriction that you can do any use whatever hints you give. e.g. it would make cache invalidation a lot cheaper if buffers hinted for read access only could not be written at all, but this optimization is impossible.

Some notable games which are widely used for benchmark comparisons between GPUs do not use these hints correctly, so GPU vendors have an incentive to make all uses fast even if they doesn't match the hints.