How can I utilize all cores of CPU In my ray tracer with std::thread? I have been working on a ray tracer and I was trying to use multiple threads to maximize the performance. I tried couple of approaches but there's no difference in performance. Here's my shot...

void ray_tracer::render()
{
    #define USE_THREADS
    #ifdef USE_THREADS
        for (int threadIndex = 0; threadIndex < mMaxThreads; ++threadIndex) {
            mThreads[threadIndex] = std::thread(&ray_tracer::put_pixel_with_thread, this, threadIndex);
        }
        for (int threadIndex = 0; threadIndex < mMaxThreads; ++threadIndex) {
            if (mThreads[threadIndex].joinable())
                mThreads[threadIndex].join();
        }
    #else
        put_pixel(); //uses single thread
    #endif

    stbi_write_bmp("result.bmp",mImageWidth,mImageHeight,3,mFrameBuffer);
}

and here's the put_pixel_with_thread(int)...

void ray_tracer::put_pixel_with_thread(int threadIndex)
{
    for (int row = 0; row <mImageHeight; ++row)
    {
        for (int col = int((threadIndex / mMaxThreads)*mImageWidth);
            col < int(((threadIndex + 1) / mMaxThreads)*mImageWidth);
            ++col)
        {
            int index = ((row * mImageWidth) + col) * 3;

            mFrameBuffer[index] = 0;
            mFrameBuffer[index + 1] = 0;
            mFrameBuffer[index + 2] = 244;
        }
    }
}

As you can see in put_pixel_with_threads(int) that I tried to split the row for each thread. I don't know what am i doing wrong. I am working on intel i5 6th gen which has 2 hyper-threaded cores. Please help.

Thanks.

This is not really a CG issue but you appear to have an integer division problem. Assuming mMaxThreads is an integer,  (threadIndex / mMaxThreads) is always 0 and ((threadIndex + 1) / mMaxThreads) is 0 for all threads but the last one, where it is 1. So one thread is doing all the work.


Mimicking Blender's "roughness" in my path tracer Recently I asked a question regarding how to mix a glossy and diffuse shader in my path tracer: Mix shader looks wrong on my path tracer.
I thought it was incorrect, but a comparison between mine and Blender's seems correct. However, now I am lost in how I would approach making the surface of a mirror look rough as this example shows:

I have done some research, and discovered that there are different types of reflectance models such as Beckmann and GGX. I've found some explanations of how to find the BRDF such as this site: Specular BRDF, but I can't find any explanation on how to do the reflection ray with explicit lighting. As shown in the pseudo code of my path tracer (below), for every object I shoot a ray towards a light and use the surface transport rendering equation to incorporate the BRDF. I am assuming this is where the GGX/Beckmann BRDF would be plugged in. (I'm guessing it's not quite that simple though and some probability must be involved). What really gets me though is that reflection ray. For diffuse it's easy because I just send off a random ray anywhere in the hemisphere of the surface normal. However, for specular, there's a more sharp bump in the BRDF. How would I translate that into a reflected ray? If I just jittered the ideal reflection ray a little, that wouldn't relate to how the microfacets are modeled in the GGX/Beckmann reflection.

Explicit lighting equation from Peter Shirley's Realistic Ray Tracing:

$$\large L_S(\mathbf x,\mathbf k_o)\approx\frac{\rho(\mathbf k_i,\mathbf k_o)L_e(\mathbf x',\mathbf x-\mathbf x')v(\mathbf x,\mathbf x')\cos\theta_i\cos\theta'}{p(\mathbf x')\left\lVert \mathbf x-\mathbf x'\right\rVert^2}$$

Where $p(\mathbf x)$ is the density function of the light triangle $1/\text{Area}$

$\mathbf x'$ is a random point on the light triangle

$\mathbf x$  is the hit point on the object

The cosines are the angles between the light's normal and the light ray, and the object's normal and the light ray

$\rho$ is the BRDF ($1/\pi$ for ideal diffuse)

And $v$ is either $1$ or $0$ depending on if it's in shadow

Pseudo code:

rayColor(ray r, depth, int E=1)
{
    if(r doesn't hit triangle)
        return 0
    if(r hit is a light)
    {
       if(E)
         return light_emission
       else
         return 0
    }

    vector x = r.origin + r.direction*t // x is point where r hit tri
    vector n = normal where ray hit triangle
    n.normalize()
    vector nl = n.dot(r.d) < 0 ? n : n*(-1) // properly orient normal

    if(++depth > 5) return 0 // max bounces

    float triangle_area   = area of emitting triangle
    vector x_light_random = random point on emitting triangle
    vector light_normal   = normal of emitting triangle

    vector d = x_light_random = x_converted;

    if(light_normal.dot(d) > 0) light_normal *= -1; // make it emit
                                                    // both sides

    object_normal.normalize();
    light_normal.normalize();

    BRDF = 1/PI // perfect diffuse
    light_emitted = 1 // emission of 1
    vector light_out = 0
    if(ray starting at x towards d hits light (i.e. not in shadow))
    {
         light_out = BRDF*light_emitted*(object_normal.dot(d))*
                            (-1*light_normal.dot(d)*triangle_area)/
                            (d.length*d.length*d.length*d.length)
    }
    vector direct_light = color_of_object_triangle*light_out;

  //----SPECULAR-----
  vector d2 = r.dir-n*2*n.dot(r.dir); // ideal reflection
  vector light_color = 1 // white since dialectics don't change spec
  vector specular = light_color*rayColor(createRay(x, d2),depth)

  float P = 0.5; // 50/50 chance of mirror/diffuse
  if(erand(Xi) < P)
      return direct_light/P
  else
      return spec/(1-P)

For explicit light sampling: yep, you just evaluate the BRDF for that incoming direction and the output direction back toward the camera. There's probability involved in the case of an area light: you have to randomly choose a point on the light source, and include a factor to convert from probability density over light source area to a density over solid angle at the receiver point. It looks like you've got that already (that's the $\cos \theta' / (p(\mathbf{x}')\|\mathbf{x}-\mathbf{x}'\|^2)$ in the formula you mentioned).

For sampling the reflection ray, you could just pick a random ray from the hemisphere and weight it by the BRDF, the same as you'd do for diffuse. But that won't be very efficient; it'll take a huge number of samples to converge to a low-noise result.

What you really want to do is importance-sample the BRDF. This means choosing a random ray not uniformly over the hemisphere, but using a probability distribution that matches the shape of the BRDF (as much as possible). Then you'll automatically get rays that are clustered around the sharp reflection peak in the BRDF when the roughness is low, and spread out more over the hemisphere when the roughness is high.

So how do you do it? The paper Microfacet Models for Refraction through Rough Surfaces by Walter et al (which popularized the GGX distribution in graphics) handily gives importance-sampling formulas for several common BRDFs in section 5.2. Their approach is to importance-sample the normal distribution of the BRDF, then leave the Fresnel and geometry factors to be factored into the path weight.

For example, their GGX importance-sampling formula is (equations 35–36):
$$\begin{aligned}\theta_m &= \arctan \left( \frac{\alpha_g\sqrt{\xi_1}}{\sqrt{1-\xi_1}} \right) \\ \phi_m &= 2\pi\xi_2\end{aligned}$$
where $\alpha_g$ is the GGX roughness parameter, and $\xi_1, \xi_2$ are a pair of uniform random numbers in [0, 1]. The outputs $\theta_m, \phi_m$ are the polar coordinates (relative to the surface normal) of the sampled microfacet normal.

So to use this, you'd choose random inputs $\xi_1, \xi_2$, then evaluate the above equations, and use the resulting normal to compute the reflection ray, as well as the Fresnel and geometry factors from the BRDF.


Is it possible to override or disable blending per pixel I'm rendering transparent objects in separate framebuffer then compositing it with opaque one to get final image.

The transparent pass has additive blending:

glBlendFunci(0, GL_ONE,  GL_ONE);

so transpareny seems work perfect (I used weighted, blended OIT). Now I have problem if I set all surfaces' alpha to 1. Transparency works if alpha is between 0 and < 1 but not work as expected if alpha = 1. In this case (alpha=1) transparency surface seems opaque on opaque surface[s], but it also appears as semi-transparent on transparent surface[s].

I think additive blending causes this issue/artifact, how can I fix this? I want to transparent surfaces appear opaque if alpha is set to 1 in fragment shader. I can't disable blending because it will disable whole transparency process.

What I want to do is control blending in fragment shader or per-fragment blending; is this possible? Overriding old values of some fragments in framebuff e.g. to zero (0,0,0,0) could also help to fix/control blending, because I can put some values in blend equation to get what I want.

I'm asking this because maybe there is a way to simulate this which I don't know yet. Maybe I can fix this with another rendering passes/targets, I will give a try, any help would be appreciated

EDIT:

The first image is rendered with alpha = 0.5 and the second one is rendered with alpha = 1.0. As you can see transparency is still active among transparent objects. The pink plane overrides Suzanne mesh and bottom plane but not sphere :( Both sphere and pink plane are rendered in transparency pass.

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

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

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

That last part makes what you want essentially impossible.

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

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

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

glBlendFunci(0, GL_ONE,  GL_SRC1_ALPHA);

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

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


How to compute the following integral over a polygon? I am implementing an algorithm which requires me to compute the following integral,
$$\int_{Poly(P_i)}||P-P_i||^2 dP$$
where $P_i=(X_i, Y_i)$ is a point in 2D and $Poly(P_i)$ is a polygon containing $P_i$ (it is the Voronoi Cell of $P_i$ with a certain weight). Could anyone give me some indications on how to compute this quantity?

Triangulate the Voronoi cell then write the integral as a sum over the triangles:

$$\int_{\Omega}\|P - Pi\|\,dP = \sum_{k=1}^{N}\int_{\Delta_k}\|P-P_i\|\,dP.$$

Write the integration over the triangle in barycebtric coordinates. Let the Jacobian of the transformation, from barycentric coordinates to physical coordinates, for triangle $k$ be $J_k$, and $|det(J_k)| = 2|Area_{\Delta_k}|$. Then $\int_{\Delta_k}f(P)\,dP = |det(J_k)|\int_0^1\int_0^{1-\beta}f(P(\alpha, \beta))\,d\beta\,d\alpha$, where $\alpha, \beta$ are two of the barycentric coordinates.

Now we need only evaluate (let $\vec{v}_i$ be the vertices of the current triangle):
$$\int_0^1\int_0^{1-\beta}\|\vec{v}_1 + \alpha (\vec{v}_2 - \vec{v}_1) + \beta (\vec{v}_3 - \vec{v}_1) - \vec{P}_i\|^2\,d\alpha\,d\beta$$

Expand this and integrate the polynomials. The absolute value of the Jacobian determinant is: $$|det(J)| = \|(v_2-v_1) \times (v_3 - v_1)\|$$.
If you are working in 3D, $\times$ is the cross product here. If it's 2D then augment the vectors with a $0$ for $Z$ and perform the cross product.

Another option is to use a quadrature rule to compute this. For example you can still triangulate, but evaluate the integral over a triangle (let $f(P) =\|P - P_i\|^2$) through samples at the edge midpoints:
$$\int_{\Delta}f(P)\,dP = \frac{|det(J)|}{6}\sum_{k=1}^{3}f\left(\frac{\vec{v}_k + \vec{v}_{k+1}}{2}\right).$$

If memory serves me right, the above quadrature is exact for polynomials of up to degree 2 (which is what you have, and the reason I wrote $=$ instead of $\approx$). Note that $k+1$ is taken to wrap around, that is, for $k = 3$ I use $\vec{v}_4 = \vec{v}_1$.


Mapping sample to a disk So I have been reading this wonderful book on ray tracing by Kevin Suffern, Ray tracing from Ground Up. I am reading this book after finishing Peter Shirley's first two book on ray tracing & implementing multi-threaded ray tracer, adding features like Intel's denoiser, assimp integration etc.

What struck me was before I read the third book, it would be good idea to read more on sampling. Which is why am skimming through this current book. At this moment, am stuck on a topic which explains how sample point in unit square is mapped onto unit radius disk.

I am stuck at the part where book mentions how equations are mapped. Radius part is clear to me, however, am not very clear about the angle (phi) part. Is there any derivation as to how this was deduced? Or is it done to avoid atan() calculation and is a neat approximation of it? After putting in test values I have understood how values get converted, however, am very keen to understand how this formulas for Phi was deduced based on different quarters, unless it's very obvious and I have overlooked it :(

Regards.

EDIT:
After more digging, i have understood that if i assume first quadrant value, then second, third & fourth values can be deduced by rotating/adding (Pi/2) to angle phi & switching axis due to quadrant change. However, first quadrant value is still not clear :|

Check the last column in the table for the deciphered version of the existing Map Equations for easier comprehension.


Why for perfect reflections a surface must have G2 continuity? Why for perfect reflections a surface must have G2 continuity (class A surface)?

I would like a mathematical answer.

What you see on reflects is the n-continuity of normals, which are the derivative of positions. -> a G1-only surface would have G0-only normal field, i.e.,  with sudden change of gradient in the normals (and thus, the reflects), that the eyes can notice. G2 surfaces have G1 normals fields, which is smooth enough for your eyes.


Creating Sparks using Code I'm new to this area and have less knowledge. I want to create some graphics like  sparks and lightning by writing some code, using my own physics. I don't want to use some engine, However I can use external libraries.

Can anyone tell me how to set started, where should I proceed?
Like should I go with OpenGL for writing my own code or something else.

For the lightning, I recommend using a midpoint displacement algorithm. You start with a line segment between any 2 points A and B (this works in either 2D or 3D). Calculate the midpoint of the segment AB. Now move that point a random amount in the direction perpendicular to the line segment AB and call it point C. Replace the original segment AB with 2 line segments AC and CB. Repeat with the new line segments until you are satisfied with how it looks. In my experience you'll need somewhere between 5 and 10 iterations depending on the resolution you're working at. You can add a glow to the resulting geometry to make it look more realistic.

For sparks you need to make a particle system. These are pretty fun. You generally have a point (or other shape) that generates particles every few milliseconds. That is, particles are spontaneously formed on the point or boundary of the shape periodically. Each particle has various properties such as location, velocity, color, size, lifetime, etc. When animating, you can update the velocity and position based on various forces such as gravity, wind, or some sort of convection current or flow field. After a particle has reached its "lifetime" it can disappear, or fade out, and a new particle will be generated in its place at the point or on the boundary of the shape. The particles themselves can be drawn as single pixels, small shapes, or images. There's an interesting wikipedia article on particle systems.


What metrics are used for deciding if a 3D object is visible? I'm wondering what metrics I could use to decide upon the visibility of a 3D object in VR or other 3D applications and what advantages each has.

Visibility for culling (or passing to the render pipeline) is very sensitive to false negatives. False positives are not a big deal because when rendering the Z buffer will take care of that.

This means that one very simple metric is simply assuming that it's always visible. If any other metric gives too much overhead than simply processing the object requires then this is a good fallback. For example in a redering api with command buffers rebuilding the command buffer would be too expensive compared to the processing required to render a single object to warrant it.

The next option is to see if the object is in front or behind the camera, This can be done with a dot product with the view vector and the forward most point of the bounding volume of the object. If it's negative then the object is behind the camera and you can skip it.

The next is using the view pyramid. From the camera you extrude the frustum and do a collision check between it and the object. If it collides then the object is visible. Instead of 1 plane you now check against 4 and the object must pass All 4 to be considered visible.

Next you can take into account when the object is fully occluded by another object. This can be done by various methods. With static geometry you can partition the world and say for each section which other sections you can see from it. You can also ask the GPU to do occlusion queries which basically means "did any fragments of these render commands pass the depth test". But getting the information back from the GPU typically has a decently long latency, by which time the camera may have moved.


Is it better to blur the input or output of an edge detection shader for noise reduction? To reduce noise of edge detection the norm seems like it is to apply a blur. However, is it generally better to apply the blur to the input of the edge detection. The input in my case being the depth and normal GBuffers in which I compare neighbouring pixels.
Or is it better to blur the output of the edge detection, e.g. a greyscale image of edge strength, before I use that to apply some edge to a colour buffer?

Standard blur removes high frequency content from the signal, whereas edge detection usually look into high frequency to detect edges. Be careful on how much blurring to apply to ensure that you don't lose desirable edges. The goal of blurring is to perform noise reduction, so the best would be to come up with a model of the noise present in your images and what your desired edges looks like (their frequency, orientation, what caused them: shading on a smooth object, shadows, etc.) and tailor your blur filter to remove the noise but not the edges.

Seems like you want to implement an edge detector into a shader. Be sure to check what are the sources of noise in your image. For example, if you are displaying pure lambertian surfaces, chances are that there is virtually no noise in your data, so you don't need to apply a smoothing filter before detecting edges.

Also, instead of using a standard gaussian blur, you could look into edge-preserving filters like the bilateral filter. It is much slower, but is good to remove noise without altering too much the edges.

If you are performing filtering and edge detection through convolutions (the standard way of doing it), it doesn't matter if you do one before another, as convolutions are commutative, meaning $a*b = b*a$, where $*$ is the convolution operator, $a$ being the edge detector and $b$ the smoothing kernel.

On non-associative operations (like the bilateral filter), you must ask yourself the question "what is the goal of this operation?" Basically, blurring before the edge detection will diminish the image noise while blurring after will give you blurred edges (potentially caused by noise) instead of sharp edges. The same edges will be found, though, but the blurred one will be less precise. It depends on what you want to achieve: it could be interesting for art, but it just removes interesting information for signal analysis.

Not sure what "applying an edge to a color buffer" means; is the goal to perform edge enhancement?


In texture mapping, should we set texture coordinate to every vertex or can I skip vertices in between? I am working on a texture mapping problem. I use vtk C++ library for my work. I have a very dense mesh with lots of vertices. I want to apply image texture to this mesh. Should I set texture coordinates for every vertex ? Or can I skip few vertices and setup the texture coordinates and still expect the texture to be set properly? Please see the image attached.

If A,B,C,D, E, F are the vertices of 4 faces in a mesh, can I set the texture coordinates only to A,C,F,D ? Will the texture drape the faces stretching equally?

Typically, texture coordinates are interpolated from the vertices of a triangle during rendering. This can be seen in two ways. evaluating your texture at vertices and the interpolating the result or interpolating the texture coordinates and evaluating your texture at the fragment level.

If you do not supply vertices with corresponding texture coordinates then there is no guarantee that the interpolated texture coordinates or colours for the fragments of the rendered triangle will behave nicely. By skipping a few vertices, the vertices would need some default texture coordinate such as $(0,0)$, which would show up as a weird artefact in your rendering. The vertices B and E in your example are required to have texture coordinates in order to have a continuous set of interpolated texture coordinates or colour values.


Represent shape as particles Input: Triangles which make up an arbitrary shape. Each triangle is represented by 3 3D points.

Output: A set of particles which fills up the inside of the object (see image).

I have read the description made by GPU-Gems, and tried to implement the proposed solution that don't make the computations on the GPU. I have tried to take each triangle one at a time and see if they intersect with lines, and if so store the z-value which I later used to generate particles. This gave bad results, and in theory it is possible for a line to intersect with a lone point which would cause a bug.

Can anyone tell me how to easily on the CPU side create a set of particles that represent a shape? Where the shape is defined as a set of triangles.

I prefer a solution that is simple and works well rather than an efficient solution that can have bugs.

Edit: I re-checked my code, and I found that I was not sorting the z-value arrays correctly like I thought I did, after fixing this I got a good result! If anyone still wants to answer this question that is ok, but I consider my problem to be solved now.

Solution: Check for the minimum x,y,z value for all points. Add these values multiplied by (-1) to all points in order to guarantee that all points are not negative. Then take the largest point and subtract with the minimum point (max and minimum x y z) in order to get a cube-like bound for the object.

Then divide this cube by an arbitrary size constant representing the radius of each particle. Now you should have a 2D array for z-values, such that for any x, y position you can quickly store z-values that you find intersecting lines.

For each triangle in the mesh, check all possible that have a large or small enough x-y value for intersections with a line going through the whole cube. If there is an intersection, save the z-value in the x-y array for z-values.

Lastly loop through each possible z-values in the imaginary cube and check if it has an odd number of z-value hits before the current z-value. If that is the case, then we know that there is a particle here. Don't forget to add the minimum x,y,z values that we added in the beginning in order to make the particles have the correct positions again.


How to smooth out a voxel grid? So I am facing the following issue. Say I have a minecraft like mesh (i.e I have a bunch of cubes on top of one another).

I wish to smooth out this mesh in such a way that only the regions where there are edges are smoothed out and such that the smoothing concentrates around the edges (e.g if I have a staircase the overall shape of the cubes that make the staircase should still be close to the staircase but instead of having straight edges I should have something much smoother).

I should be able to smooth things out locally, so that if a block is removed from this mesh, I can run the subdivision algorithm only on the newly generated coarse region that is created after the block is removed.

Does anybody have any ideas as to which algorithm I could use?

If you have this data in a 3d array where a block is a 1 and no block is a 0 you can apply a 3d blur and then set all voxels that are left with a value higher than 0.5 to 1 and those that arent to 0. this will smooth out sharp details and leave flats mostly uneffected


How to approximate the heightmap of processed wood? In the above image, you can see that there is some slight variation of the height of each wood plank. These variations do NOT come from the wood texture itself, but from the way it was cut, i.e if a different tool had been used to cut the same plank, it would look different.= and exhibit the pattern of the tool used.

I am trying to use a perlin noise generated heightmap to approximate, to the best of my ability, this "wavy" pattern exhibited.

This image is better to see the pattern:

I have tried multiple strategies to modify perlin noise but I can't quite get heightmaps that look like the prior images.

My strategies so far are based around:

Stretching perlin noise along one direction, taking powers of linear combinations of the sampled noise to try to get a "bowl" shape, similar to the corner of the bottom image.

Does anyone have suggestions?

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

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


How to simulate elastic material with restoring shape I'd like to simulate a rubber-like material. This material if deformed would experience a restoring force to its original shape, a bit like a school rubber ereaser.

I tried with a spring-mass system but the system become quickly instable, moreover it's computational expansive.

Doing some research I found out I could simulate this behaviour through finite element method If I understood well. The problem is I haven't got the right mathematical tools to understand this method.

So how would you face up to this problem?
Resources, links, tutorials, papers are welcome.

A good introduction to finite element methods for deformable body animation is Sifakis and Barbič's course FEM Simulation of 3D Deformable Solids from SIGGRAPH 2012.

However, since you say

  I tried with a spring-mass system but the system become quickly instable, moreover it's computational expansive.

you should know that a finite element model is usually more expensive than a mass-spring system. If you're having problems with instability, you should try keeping your mass-spring system but (i) reducing the time step, or (ii) doing implicit integration; see the "Implicit Methods" chapter of the Witkin and Baraff notes.

You can also consider position-based dynamics or projective dynamics, which are fast, stable, and easier to implement than FEM. They may be good enough for your needs, unless you require high accuracy or nonlinear material models.


PBR : Understanding the right part of Split sum integration of specular IBL This is the website I am learning from.
In the specular part of IBL this is the split sum approximation

Now the left part of the equation I have asked in  This post and I have understood everything now this question is about the right part.
On simplifying the right part of the equation with the procedure shown in the website we get this

And on translating this to code we get this

I have so many questions about this code.
1)What is the V vector? How did they compute that
2)Why have they assumed N=(0,0,1)?
3)why is NDotL=max(L.z,0)? How did they simplifying a dot product to an min/max Operation same question I have for NDotH
4)G_Vis=GVDoth/(NDotHNDotL) why the division by (NDOTH*NDOTL)? that was nowhere in the equation.
5)what is vector L? it looks like they have reflected vector V about H to get this but why?
These are just some of the questions I have come up with so far but if there are any other important parts I should not know about A general explanation on how they derived this code would be appreciated

1)What is the V vector? How did they compute that

It's the vector toward the camera (view vector), i.e. direction of the reflected ray. The lookup table they're building is parameterized in terms of NdotV, so they are working backward from NdotV to obtain a corresponding V vector. For purposes of doing this integration it doesn't matter what N and V are exactly, just that they have the correct NdotV. So, just to make things concrete, they assume that $N = (0,0,1)$ and V is aligned with the positive x-axis (i.e. in the positive xz half-plane). Then you have $V = (\sin θ, 0, \cos θ)$ where θ is the angle from N to V (this is just the equation for a circular arc from z down to x). Now $N \cdot V = \cos θ$, so by a standard trig identity $\sin θ = \sqrt{1 - \cos^2 θ} = \sqrt{1 - (N \cdot V)^2}$.

2)Why have they assumed N=(0,0,1)?

This whole thing is a pre-integration of the BRDF alone, it doesn't depend on any scene or lighting environment. So it doesn't matter where the BRDF is or how it is oriented in space, only the relative orientation between the N, L, and V vectors is important. So just for the sake of convenience they have chosen to fix N = (0, 0, 1), let V vary only in the xz half-plane as mentioned above, and let L vary over the whole hemisphere. To put it another way, they have chosen to set the coordinate system to be aligned with N and V.

3)why is NDotL=max(L.z,0)? How did they simplifying a dot product to an min/max Operation same question I have for NDotH

Since N = (0, 0, 1), dotting N with any vector just takes the z component of that vector. $N \cdot L = 0L_x + 0L_y + 1L_z = L_z$. (This is why it's convenient to assume a coordinate system in which N = (0, 0, 1).) Taking the max with 0 clamps it to the upper hemisphere, otherwise the dot product would go negative if the vector happens to be pointing below the hemisphere. This clamp is a standard thing to do when dealing with opaque BRDFs to avoid accidentally getting unwanted negative values in your calculations— although it is not really necessary here since they check if (NdotL > 0.0) immediately afterward.

4)G_Vis=GVDoth/(NDotHNDotL) why the division by (NDOTH*NDOTL)? that was nowhere in the equation.

It is a standard part of the microfacet BRDF formulation:
$$
f_r(p, w_i, w_o) = \frac{DFG}{4(\omega_o \cdot n)(\omega_i \cdot n)}
$$
Note that $\omega_o = V$, and $\omega_i = L$, these are just different notations/names for the incoming and outgoing light vectors.
However I think there is a typo in the code, the denominator should contain NdotV rather than NdotH. I am also not sure why there is a multiplication by VdotH in the numerator, or where the factor of 4 went, but perhaps they have accounted for it elsewhere. I would probably double-check the BRDF equations here against some other sources as I don't think it's entirely correct.

5)what is vector L? it looks like they have reflected vector V about H to get this but why?

As noted, L is the vector toward the incoming light. H is the "half-angle" vector exactly halfway between L and V, so reflecting V around H will give you L, or vice versa. The significance of H is that in microfacet BRDFs, it is the normal vector of those microfacets that are "active" for a given L and V. So, to importance-sample a BRDF, we sample a random normal vector from the NDF, and use that as H. Since H and V are specified, we then calculate L from those.


Inverted Normals in Raytracer I am having the following issue. I am working on a ray tracer for school and I am trying to render a sphere where the radiance of a intersection point is the dot product of the ray direction and the normal at the point of intersection. This works fine if return the inverted normal ( i.e. a vector going from the intersection point to the center of the sphere but not the other way around as it should be ) and I can't figure out what I messed up. Anyone have a intuitive clue on what I could have messed up? Can't really post code here as it's a school task but feel free to ask for further information and I am trying to provide as best as I can. (left: inverted normals, right: right normals)

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

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


Ray tracing implicit surfaces using Sturm's theorem I am trying to render implicit surfaces given by a polynomial equation $F(x,y,z) = 0$ using Sturm's theorem.

Plugging the parametric ray equation $r(t) = o + td$, where $o\in\mathbb{R}^3$ is the ray origin and $d\in\mathbb{R}^3\backslash\{0\}$ is the ray direction,  into $F$ yields a polynomial equation $p(t) = 0$ for the intersections of the ray with the surface. I noticed that the straightforward implementation of calculating a Sturm sequence as

$$p_0 = p, \\ p_1 = p', \\ p_{i} = -\text{rem}(p_{i-2},p_{i-1}) \quad\forall i\ge2$$

is numerically unstable. When rendering a torus for example, the equation for one particular ray in my program was

$$p(t) := t^4 + 0.00329589844t^2 - 660.766052t + 9627.17676 = 0.$$

In single precision, the associated Sturm sequence is computed as

$$p_0(t) = t^4 + 0.00329589844t^2 - 660.766052t + 9627.17676,\\
  p_1(t) = 4t^3+0.00659179688t-660.766052,\\
  p_2(t) = -0.001647949220t^2+495.5745390t-9627.17676,\\
  p_3(t) = -3.617114498\cdot 10^{11}t+7.027166964\cdot 10^{12},\\
  p_4(t) = 0,$$

which indicates that (up to multiplicity) $p$ has exactly one real root. But in fact $p$ has no real roots, which can easily be verified with a computer algebra system. If the same computation is done with higher precision, it turns out that $p_4(t)\approx 0.000039>0$. In this case the correct number of roots is calculated.

Is there anything that can be done to avoid this problem when calculating a Sturm sequence?

This is a rather late reply but it might interest others who come up to this question.
Your question assumes that your ray tracing platform does not support double precision. This is unlikely.
If you are using CUDA or OpenCL they both support double precision vectors.
If you are using Vulkan things are a little more complicated due to specification saying: "The precision of double-precision instructions is at least that of single precision."
Though not a ray tracing platform OpenGL also supports double precision vectors from OpenGL 4.0 and on.
If you are tracing on CPU, chances are you can define a double precision vector data type, if it is not already defined.

If, in the unlikely case that your ray tracing platform does not support double precision, or you are obliged to use single precision in any way, the only thing that I can think of is using pseudo-remainder sequences for rem- i.e. euclidean division.
Particularly you might want to check out Subresultant pseudo-remainder sequence from the wikipedia section in the link. I am adding the pseudocode of the algorithm in here:
r_0 = a
r_1 = b
for (i:= 1;r_i not equal to 0; i := i+1)
    d_i := degree_of(r_{i-1}) - degree_of(r_i)
    g_i := leading_coefficient_of(r_i)
    if i = 1 then
        b_1 := (-1)^{d_1 + 1}
        p_1 := -1
    else
        b_i := -g_{i-1} (p_i)^d_i
        p_i := ((-g_{i-1})^d_{i-1}) / (p_{i-1}^{d_{i-1}-1}
    end if
    r_i := rem((g_i)^{d_i+1} r_{i-1}, r_i) / b_i
end for


Speeding up convergence: am I reinventing the wheel? I'm trying to learn about raytracing by implementing things in Python 3. I know this is always going to be slower than something like C++, and I know the speed could also be improved by using GPU raytracing, but for this question I'm not looking for general ways of speeding up, but specifically ways of reducing the number of samples required, which will then be useful for any language I may work with in future.

I have a partly formed idea which I'd like to work on, but first I wanted to run this past the experts to see if this is a pre-existing technique so I don't repeat work that has already been done.

I've searched for "sampling solid angle" and "voronoi sphere sampling" but I can't see any sign of prior work. I'll describe my idea in case it goes by a name I can't think of.

Example image

This is an image of three spheres on a plane (which is actually a very large sphere). One is emissive, one is reflective, and one is matt (as is the floor). Sampling is adaptive so that pixels that quickly reach a stable colour do not take up much time. I limit the total number of samples per pixel to avoid the rendering continuing for too long. Even allowed to run overnight, the resulting image is very grainy, and experimenting with smaller images suggests this size image (1366 by 768) would take weeks to converge with my current approach.

My idea: concentrating samples along colour boundaries

I'd like to be able to concentrate samples where they are needed, and to do this adaptively based on previous samples for the same intersection point or pixel. This will give an unknown bias in the distribution of samples, which means taking the average of the samples will give an inaccurate result. Instead I would like to consider the size of the voronoi cell on the surface of the unit hemisphere centred on the point of intersection (for sampling light incident at a point on a matt surface) or on the surface of a small circle (for sampling around a pixel).

Assume that all points within that voronoi cell are receiving rays of the same colour as the centre of the voronoi cell. Now an estimate of the average colour can be obtained by weighting according to the area of each voronoi cell. Choosing new samples on the boundary between the two voronoi cells with the greatest difference in colour leads to an improvement in the estimate without needing to sample the entire hemisphere. Samples should end up more densely concentrated in areas of higher colour gradient. Areas of flat colour should end up being ignored once they have a few points near their boundary.

The extra complication is that in both cases (sampling from a point on a matt surface, or sampling over a circle around a pixel centre) the simplified approach I have described is roughly equivalent to a large number of samples distributed uniformly. To make this work I would need to be able to bias the average by both the voronoi cell areas and the required distribution (cosine around the surface normal for a matt surface or gaussian around a pixel centre).

So I have some more thinking to do before I could test this idea, but I wanted to check first if this has either already been done, or already ruled out as unworkable.

It sounds like you're trying to do adaptive subdivision on the surface of a hemisphere.

This has indeed been tried before, although perhaps not in the exact way you're thinking.  Usually for hemispheric integration, people use some well-distributed, pre-defined sampling density over the hemisphere and forget about adaptive subdivision.

But you may be missing the point.

The whole idea of doing such things is to get a better estimate of the integral.  But it's not the integral over the hemisphere you care about.  You're integrating over the pixel to get AA, over the aperture to get depth-of-field, over the lights to get soft-shadowing, over the hemisphere to get GI, over time to get motion blur, over wavelength to get dispersion, and so on.  You're integrating over all that.  This is an absurdly high-dimensional space, and decades of development have shown that you need to be exploring it not more carefully, but faster.  That is, you get better results from breadth, not depth.

All very abstract.

The point is this: you don't want to sample over the hemisphere with lots of samples.  You want to sample over your hemisphere with one sample and then move on.  This is called path tracing.  It differs from ray tracing in that the maximum width of the ray tree is 1 (or maybe 2).

The key insight is that if your random samples are well-distributed with respect to all dimensions, other rays will "fill-in" the rest of your missing tree.

For an intuitive example: say you're doing 4x AA.  So you shoot four rays through a pixel.  Probably, they hit in very similar points (creating similar reflectance hemispheres).  Then, they each shoot exactly one recursive ray.  But, since the four hemispheres are in almost the same place, the recursive rays (kindof) count for all the hemispheres.  So each of the four paths gets some of the benefit of the other three.

That's sortof handwavy math, but since each path is actually independent of the others, and the color you get is an unbiased estimate of the entire scene's illumination, averaging them together is unbiased.  It just converges much faster in practice.

Obviously, if a cheap estimate of the hemisphere's integral is available, you can just use that--this is preintegration (cone tracing, etc.), importance sampling (next event estimation, light sampling), or better paths (BDPT, photon mapping)--but for a simple approach, it's basically always better to use path tracing instead of stochastic ray tracing.

Also matt -> matte (or mat, in a pinch).  It's a French loanword, not a person's name, and I don't care what the American dictionaries say.


How does the Waves class in the book Introduction to 3D Game Programming with DirecX11 work? I'm confused by the Waves class implementation in the source code of the book Introduction to 3D Game Programming with DirecX11:

float d = damping*dt+2.0f;
float e = (speed*speed)*(dt*dt)/(dx*dx);
mK1     = (damping*dt-2.0f)/ d;
mK2     = (4.0f-8.0f*e) / d;
mK3     = (2.0f*e) / d;

What do the parameters mean? How are the waves generated? I've tried searching waves implementation and found https://stackoverflow.com/questions/6716887/how-to-render-ocean-wave-using-opengl-in-3d , I looked up the links mentioned by the answer but I couldn't understand the complicated equations and it seems that the equations have no relation with the code above. I also tried searching "spatially damped wave", and then I found https://physics.stackexchange.com/questions/223366/wave-equation-with-spatial-damping, that didn't help me, neither...

This implementation represents the water as a regular height field grid. The function parameters m and n are the dimensions of the grid, dx is the regular distance between the water vertices, dt is the time step, speed is the speed of the movement and damping is a constant to ease disturbance as the water flows from the disturbance center.


how to draw mesh equal distance from irregular shape geometry bounding box I am given an irregular geometry shape with its vertices, bounding box information.

How to draw a smooth mesh equal distance from that irregular geometry shape's bounding box?

Please refer to the image here:

My attempt:
1) I have tried to create 8 spheres at 8 corners of a bounding box and a box for X, Y, Z direction. The result looks very ugly and not smooth like this:

Is there any algorithm or formula I can utilise to draw mesh around a bounding box?

Thank you

One way to visualize an object's bounding box would be like this:

$\hskip2.5in$

As Rahul mentioned in a comment, you can achieve this by adding a total of 12 cylinders at the edges of the bounding box, connecting the spheres at the corners.

If you want to render the bounding box transparently, I don't see an easy way to hide the intersections of the spheres and cylinders without knowing what program you are using. You could try to use partial spheres for the corners and see if that helps, i.e.

$\hskip2.5in$

Maybe this is already sufficient for your purpose. (This is exactly 1/8th of a full sphere.)


Screen coordinates, barycentric coordinates and global coordinateas To continue with this my other question, here's the problem. So, I've a slide, which I'm trying to understand.

Here are my questions.

What are the barycentric coordinates of? From my previous question, $(x_1, y_1)$ and $(x_2, y_2)$ are also screen coordinates. So, we're interpolating between screen coordinates. Why would we do that?
Why is $\lambda = \frac{x - x_1}{x_2 - x_1}$?
Are $p_1$ and $p_2$ points given in global coordinates? That is, are they $3D$ points or screen points?
Why is $\mu$ defined as it is?
Why do we want to know $p^z$? By the way, what is it? A vector, right?

It sounds like you're rasterizing a line segment between two endpoints. The points on the line are obtained by linearly interpolating between the endpoints (whether in world space, screen space, or any other coordinate system). The barycentric coordinates identify points on the line segment.
It's defined this way to make range of $\lambda$ be [0, 1]. (When $\lambda = 0$ you obtain $(x_1, y_1)$ and when $\lambda = 1$ you get $(x_2, y_2)$.) This is typical for barycentric coordinates for either lines or for triangles—they always range from 0 to 1, and sum to 1. These coordinates therefore also act as weights for interpolating other quantities, such as color or z-value, across the line or triangle.
Probably the $p_i$ are the original 3D points before projection.
This is about perspective-correct interpolation. It's stating the transformation between $\lambda$ (interpolation in screen space) and $\mu$ (interpolation in world space). The two parameters are not the same, due to perspective foreshortening—in screen space, perspective will compress parts of the line that are farther away from the camera. So, for example, the midpoint of the line in world space ($\mu = \tfrac{1}{2}$) will generally project to some place that is not at the midpoint in screen space ($\lambda \neq \tfrac{1}{2}$). The equation given shows how to convert between $\lambda$ and $\mu$ for a given point on the line. Note that if $p_1^z = p_2^z$, the equation reduces to $\mu = \lambda$, showing that both kinds of interpolation match if and only if the line is parallel to the screen, so the perspective effect is uniform along the whole line.
$p_z$ is going to be the depth of the interpolated point. It's the $z$-component of the vector $p$, so $p_z$ itself is a single value, not a vector. Presumably the reason you want to know this is so you can store it in the z-buffer during rasterization. In other words, while rasterizing a line, you can easily calculate $\lambda$ for each pixel based on how far you are between the endpoints in screen space; then this equation tells you the $z$ for each pixel to put into the z-buffer.


Can D3D12 resource barriers be used to synchronize between the compute and 3D engine? What is the best way to synchronize resource access between the (async) compute engine and the 3d engine (aka. direct engine) in D3D 12?

I found this paragraph about multi-engine synchronization on MSDN but it's not very detailed.

You can certainly use a fence for synchronization but then you'd have split the command lists for both engines since fences only operate on queues.

According to the documentation, the 3d engine and the compute engine share the same resource state (only the copy engine has it's own resource state). So if you write to a resource using the async compute engine and then read from it using the 3d engine, is there a way to synchronize this via resource barriers?

I doubt that it works if you use the compute engine to submit a resource barrier since the 3d engine probably won't wait automatically if the resource state is wrong. Same issue if you use the 3d engine for the resource transition (it could happen that the resource state is being changed while the compute engine is still writing to the resource).

Do you have to use split barriers? You could use the compute engine with the D3D12_RESOURCE_BARRIER_FLAG_BEGIN_ONLY flag and the 3d engine with the D3D12_RESOURCE_BARRIER_FLAG_END_ONLY flag. Unfortunately, the documentation doesn't say whether split barriers can be used across engines. What happens if the direct engine executes the end barrier before the compute engine has executed the start barrier?

My understanding would be that resource barriers are not at all about synchronization. They are about memory ordering, which is a related but separate concern. Basically, synchronization is about making sure that A happens before B. Memory ordering is about making sure that if A did X, someone how saw A happen will always also see X and no one will ever see X without first also having seen A happen.

In Direct3D terms, resource barriers are about making sure that if shader A writes to texture X, shader B running after shader A actually gets to see the result of shader A having written to texture X. Fences, on the other hand, are about making sure that shader A actually runs before shader B.

Direct3D resource barriers are just you stating in which way you are going to be using a resource. You cannot rely on just a resource barrier to automagically perform the necessary synchronization for you. The section you linked would seem to agree (emphasis mine):

  Although resource state is shared across all Compute and 3D queues, it is not permitted to write to the resource simultaneously on different queues. "Simultaneously" here means unsynchronized, noting unsynchronized execution is not possible on some hardware. The following rules apply.

  Only one queue can write to a resource at a time.
  Multiple queues can read from the resource as long as they don’t read the bytes being modified by the writer (reading bytes being simultaneously written produces undefined results).
  A fence must be used to synchronize after writing before another queue can read the written bytes or make any write access.


Is there an efficient way to achieve color blending in compute shaders? What I want is a function like imageStore, but instead of replacing a value - applying a blend operation to it, e.g. addition. It is not possible to do something like this with atomics due to them only operating on 32bit integers.
If there is no such function, why have noone made an extension for this yet? It seems rather useful for compute shader lighting, and some post-processing effects.

If there is no such function, why have noone made an extension for this yet?

Just because something might be "useful" doesn't mean it would be possible or cheap.
GPU hardware achieves blending by using an entirely separate piece of hardware, one that preserves the order of the fragment values generated by unordered fragment shader executions. These execution units, commonly called "ROPs", are distinct hardware from fragment shaders.
CS's can't just do that. They have a fundamentally unordered execution model, and what you're talking about requires at least some ordering between them. That's not simple or cheap to implement, even if it's possible at all.
The closest you can get to that is fragment_shader_interlock, which can force parts of FS execution to be ordered by primitive order and to execute critical sections that prevent overlapping executions. But as the name suggests, that's a feature of fragment shaders (and not one universally supported), not a feature of compute shaders.
Also, it doesn't really make sense to use a compute shader for post-processing effects, since FS's are perfectly capable of dealing with that sort of thing, and actually have access to ROPs.


Is it possible to render red / blue 3d from one image and a depth buffer? To render an image for use with red & blue 3d glasses, the usual way to do it is to render from one point of view, convert it to a single intensity (greyscale) value per pixel, and then put that into the red color channel.  Render from a slightly different point of view, convert that to greyscale again and put that into the blue channel.

This can be prohibitive when rendering a single time is already very costly.

Are there any methods by which you could take a single render, and corresponding depth buffer, and come up with something suitable for both red and blue channels?

Yes, this is essentially the same problem that occours in paralax mapping. What you basically have is a colored height field. That needs to be rendered from a second view.

There are several ways in which you can approach this. You could cheat and just shift pixels by their depth and ignore occlusion. Or you could just render a textured height map as if every pixel would be opaque. Or you could use any of the available paralax mapping methods to eliminate occlusion.

How well this works depends on the. A scene multiple transparent surfaces wouldnt work very well without some deep map.


How to work with half and snorm I have just come across this article about half, snorm and unorm, but I don't get some of the points (or why they work).

According to the article, a half is basically a 16 bit float and an snorm is a signed float integer$^1$ dividied by 65535. Therefore, they are basically the same, just that the snorm is represented in $[-1, 1]$ whereas the half is in $[-65520; 65520)$ (where did those 32 values go?) but doesn't need another multiplication to get to the "real" value.  Now the article says:

  Other people prefer 16-bit xNORM variants because they tend to give really good precision and it is evenly distributed.

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

For snorm a division is suggested, by either $64$ or the maximum AABB value. I get the latter, that can be used for more or less any model then, but why use the magic number $64$ if I don't want to calculate it? Is it common to have models that don't exceed this specific value?
If I get good precision with half (or xnorm respectively) to save bandwidth, but in my application actually need really large position values, can I leverage the better precision of xnorm with a multiplication for "full" float and save myself from using  double variables?

$^1$ Edit for future readers. I wrongly assumed it was a float.

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

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

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

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

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

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

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

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

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

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

Not particularly.

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

No.

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

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


Store 3d coordinates in a 2d image? How can i store the X,Y,Z vertex points of a mesh into a 2d image, such that reading the image pixel values will correspond to the 3d coordinates? is it possible to just store x, y, values on a grid and use the Z value as an intensity value?

The most straightforward way would be to put x into the red channel, y into the green channel, and z into the blue channel of each pixel.

You could also make a 1 channel image where intensity is used to describe height. This is called a height map. Usually the x and y of the mesh are the same as the x and y of the image, so no need to store them in any way.


Paper for the approximation formula provided by Brian Karis In these slides, specifically page 11, the following formula is reported:

$$
\frac{1}{N} \sum_{k=1}^N \frac{L_i(l_k)f(l_k,v)\cos(\theta_{l_k})}{p(l_k,v)} \approx \left( \frac{1}{N} \sum_{k=1}^N L_i(l_k) \right) \left( \frac{1}{N} \sum_{k=1}^N  \frac{f(l_k,v)\cos(\theta_{l_k})}{p(l_k,v)} \right)
$$

The formula above should be an approximation of the rendering equations. I'm looking for a paper that explains how that formula is derived, I cannot manage to find neither the title of a paper (other than the name "Dimitar" mentioned in the same page I pointed out).

I've done some research about some possible method that would justify. This is the closest thing I managed to find, however there's some hypothesis that doesn't seem to me fits.

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

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

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

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

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


Reference for Inverse Rendering I'm not sure this is the right place to ask for this reference but it's worth the shot since it is graphics related.
I'm looking for the very first paper describing what "Inverse Rendering" - By that I mean a machine learning system that given some renderer and a deep learning model and an image as input will provide you one or more maps describing how to render the same image.
I cannot manage to find anywhere a/the white paper the would describe how such system would work.
Can anyone provide a reference? Maybe not the very first paper but a white paper that might describe the fundamentals (I'd rather prefer papers to web articles).
Thank you

I did only quick google search and found this PhD thesis - "Inverse rendering for computer graphics" by [Marschner1998] - http://graphics.stanford.edu/~srm/thesis/thesis.pdf
Also two published papers - Ramamoorthi et al "A Signal-Processing Framework for Inverse Rendering" http://cseweb.ucsd.edu/~ravir/papers/invrend/invrend.pdf
And Yu, Smith - "InverseRenderNet: Learning Single image inverse -
https://openaccess.thecvf.com/content_CVPR_2019/papers/Yu_InverseRenderNet_Learning_Single_Image_Inverse_Rendering_CVPR_2019_paper.pdf

Based on my experience, just follow prior works in this area and you'll get to the first or first worth mentioning paper in this area. With every paper in the area of raytracing, you'll get reference to [Whitted1980]. Every BRDF will get you back to
[CT1967] and every Spherical Harmonics work to [Green2003].
Based on what you wrote, you must be familiar with reading papers. Therefore, I would suggest to read "Introduction" and "Prior work" to find references to past works in this area of computer graphics.


Image rotation algorithm I would like to rotate a raster image by an arbitrary angle. I don't really care for speed: the rotation should be of highest quality possible. Could someone please suggest a suitable algorithm?

I'm familiar with the rotation by three shears but I'm not sure if the shears would not cause too much aliasing/blurring.

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.


How do CAD programs render non-polygonal 3D objects? How CAD programs handle displaying B-Reps and NURBS/T-Splines in their viewports? Assuming viewport uses OpenGL API - are those programs transform every object into triangles and creating/deleting vertex/index buffers when needed?

Depends on the CAD program. But yes basically they do just what you describe they triangulate the model into a mesh/lines on demand and then display that. How they chose to do this depends on the CAD, most modernized codebases probably use buffers. But older cads may in fact use the old immediate mode draw calls.

This said it is possible that the triangulation happens on the GPU. Though i doubt it is implemented that way in many CAD software. There are also other reasons for the CAD to triangulate the meshes, such as intersection testing, CAM path planning and export, that has nothing to do with display as such and would result in the need of implementing both a software and a gpu triangulator doubling workload or and making maintenance difficult.

Most CAD systems allow you to access the triangulated representation, through their API as well as export. But if all else fails you could just attach a debug dll to see what data the CAD dumps to the display card. So for a definitive answer ask your CAD software to tell it to you.


Clipping circle and polygon and generate a CAD drawing I'm developing a CAD drawing generator using C# and netdxf library (https://github.com/haplokuon/netDxf)

The app first performs boolean operations (specifically - union & subtraction) on polygons and draws the resultant path on .dxf file.

I'm using Angus johnson's Clipper library (Clipper - an open source freeware polygon clipping library | angusj.com) for clipping

Everything works fine for polygons, The problem is when I need to clip circles and polygons, the result is a large list of points (representing the path of the figure to be drawn on dxf)

So the curved portion of the path is composed of tiny segments, which is a big problem for the CAM software that'd be used later.

Below is such an image (the result of clipping circle and polygon). The grey portion is full of tiny line segments

Questions -

1) How can I convert those tiny line segments to circles/arcs using the list of points?

2) Can I take a completely different approach to avoid this problem?

Thanks!

I don't know how the clipping library you are using returns the clipped objects, but if I understand your question, you want a way to represent your circles that does not use much memory? If you are only using perfect circles (and not ellipses) you could represent each arc segment as simply an origin point, a radius, and a start/stop angle.

This is the part where it would be helpful to know what the clipping library returns. If it returns a chain of points as a separate object for each clipped arc segment, and you already know the radius and center of the circle (from before clipping), you could take the first and last point in the returned chain and compute the angle for each.

atan2(x - origin.x, y - origin.y)

Then when you would like to draw the thing, you can write and algorithm to trace the arc going from the start to stop angle. If you want to do further clipping, you could recreate the arc as a chain of points.

Be careful about whether the returned segment was clockwise or counterclockwise.


How to convert Non-Axis Aligned Bounding Boxes to AABB I am trying to write a ray tracer to render boxes that are arbitrarily rotated, i.e. not necessarily axis aligned. While I am reasonably comfortable ray tracing axis-aligned bounding boxes (AABB), I don't know how to handle non-axis aligned objects. The geometry becomes quite difficult. I've looked through a textbook (Ray Tracing from the Ground Up) but couldn't find an answer.

How should I do it? Detailed suggestions would be greatly appreciated.

You can assign a coordinate system to each nAABB in such a way that the nAABB becomes an AABB in its own coordinate system. We call this a local coordinate system.

I assume rays are expressed in a world or global coordinate system. In order to test an nAABB for intersection, one first needs to apply the world-to-local transformation on the ray (origin and direction). This way we obtain a transformed ray which we can intersect with an AABB. Once an intersection point is found, we need to transform this back to world space via the inverse transformation (i.e. local-to-world transformation).

In practice an nAABB is thus expressed as an AABB with a pair of world-to-local and local-to-world transformation matrices.

If one applies a scaling ($S$) or translation ($T$) on an AABB, one obtains another AABB. If one applies a rotation ($R$) on an AABB, one obtains a nAABB.
Typically the corresponding transformation matrices are multiplied as follows $T * R * S$. Thus translation is applied after rotation. Since the $R$ component must be included in the world-to-local transformation, you need to include the $T$ component as well. The $S$ component can be included or directly applied to a unit AABB centered at the origin of the world-coordinate system. Including a $T$ component requires your world-to-local and local-to-world transformation matrices to be of size $4$x$4$ (expressed in homogeneous coordinates).

Here you can find C++ code to construct all the $4$x$4$ world-to-local matrices and their inverses you probably need.

Note that this approach works for other geometrical objects as well (if the transformations involve scaling, rotation and translation).


PBR - How to handle multiple BSDFs and material type So I am in the midst of writing my own path traced renderer and right now I have only implemented the old Blinn-Phong models where we separately calculated the diffuse and specular components of the material and each object had a specular and a diffuse color.

Now going towards the more general side I want to be able to render different types of objects wood, polished wood, perfect mirror like reflections etc. However all this information confuses me on how should I implement these BSDFs or in other words how should I choose when to apply a certain BSDF or maybe a combination of two?

This is usually done using a material approach. The material being diffuse, glossy or perfect specular would define which BSDFs should I use.

I read PBRT for clues and they break surface reflection into 4 types. Diffuse, Glossy Specular, Specular and retro reflective. Then they implement an enum that stores the type corresponding to these reflection.

The enum has the types

BSDF_REFLECTION
BSDF_TRANSMISSION
BSDF_DIFFUSE
BSDF_GLOSSY
BSDF_SPECULAR
BSDF_ALL

The users are supposed to select a bitwise combination of the first two and
the next 3 ones. Where BSDF_ALL is a combination of
all the flags. This interface seems nice but there is one little
confusion. If BSDF_ALL combines all flags, then this means the
surface can be diffuse and specular. However this seems odd, a
perfectly specular surface can't be diffuse. While Glossy + Diffuse make
sense (polished wood, paint on a rough wall), diffuse + specular and
glossy + specular don't make sense to me.
Assuming we have solved the above problem consider an object that is
glossy+diffuse like an orange or lemon skin. How do we
calculate the color for this surface? Suppose I am using
Oran-Nayar model (ON) for diffuse surfaces and
Cook-Torrance (CT) for specular ones.

Should I compute the diffuse component through ON and specular
through (CT) then add them together? However both of these models
have their own parameters which define the slope distribution for
microfacet. For ON that's $\sigma^2$, the variance of the Gaussian
distribution and for CT that's $m$, which wiki describes as "RMS
slope of microfacets" (check respective links). Which one of these
will govern the roughness of the surface?
Moving on further there is a more general question. In the older models such
as Blinn-Phong we used to have a separate diffuse and specular color. The
specular color, from what I understand is nothing more than the Fresnel
Reflectance. This is because Fresnel
reflectance is dependent on wavelength. In case of Dielectrics this
isn't discernable but for metals it usually is (gold gives of a
yellowish tint). Hence for dielectrics the specular color would just
be the plain old Fresnel reflectance replicated across RGB channels
while for metals this would be the color of the tint.

The thing that confuses me is the lingering concept of diffuse and
specular reflectivity. Consider Cook-Torrance's original paper where
they describe their model as.

$R = dR_d + sR_s$

Where $d$ and $s$ are the coeffecients for diffuse and specular
reflectivity respectively and they must hold the condition.

$d+s \leq 1$

$R_d$ is any diffuse BRDF (they assume lambertian) while $R_s$ is
their new proposed BRDF for specular surfaces.

That's where my biggest confusion is. I was thinking the diffuse and
specular colors as the object's respective reflectivities in each
channel. The above equation however separates the color from
reflectivity. Which concept is used in PBR?

Although the specular term of the Cook-Torrance BRDF is widely used in Path Tracing, the original BRDF was meant initially for rasterization (it was proposed before the advent of Path Tracing). The idea of summing weighted diffuse and specular components (i.e. $R=dR_d+sR_s, d + s \leq 1$) is not capable of representing the complex results that may emerge from the interaction between diffuse and specular material elements (e.g. refraction, Fresnel for plastics, etc).

Actually, a better physically based model for material representation would be that of layers. For instance, smooth and rough conductors could be modeled through a unique layer represented by the specular term of the Cook-Torrance BRDF. Smooth and rough dielectrics could be modeled through a unique BSDF. Plastics, on the other hand, could be modeled through the use two layers: the topmost layer representing a dielectric (a BSDF) and the second layer, underneath the dieletric, representing a diffuse material (e.g. a lambertian or Oren-Nayar BRDF). That two-layer setup for plastics is capable of simulating the Fresnel reflectance of plastics (through the dielectric layer), the plastic color (through the light reflected by the colored diffuse layer underneath the dielectric), the light absorbed by the dielectric (through the implementation of Beer's Law), etc.

The layer-based material model approximates quite well what actually happens in real life. I have already written a related answer, with more details, and that may help you (I've included some references in that answer): https://computergraphics.stackexchange.com/a/5761/5681

The original Cook-Torrance does not properly conserve energy (I've already posted a question about that here). In 2007, Walter et al. have published the paper Microfacet Models for Refraction through Rough Surfaces, where they propose a Cook-Torrance based model amenable for Path Tracing.

Regarding layered material, I've implemented the system presented in the paper by Weidlich and Wilkie,
Arbitrarily layered micro-facet surfaces, where a quite general layered material model is presented. After that, more sophisticated layered material models have been proposed. One of them is
A comprehensive framework for rendering layered materials
, by Wenzel Jakob. There is a new paper (published in 2017, I think), that supports subsurface scattering for top layers (I will add it here when I find it).

I think that PBRT uses layer-based materials too, but I do not know how they have actually implemented it.


A solution to sprite visibility in a raycasting engine with variable wall heights? I am writing a raycasting engine. At this point, I have added sprites, and I am using a z-buffer, with one stored length to a wall for the x coordinate of each ray. Below is an image of a sprite which is fully visible.

Z-buffering works fine when my vertical height is zero, as seen below.

However, when I change my vertical height and stand on top of a wall, as seen below, my sprite becomes only half-visible. I understand why this is true; the Z-buffer is only accounting for the first level of vertical height, and so it seems like the sprite should be partially obscured, even when it is not.  However, there also cases when most of a sprite is obscured except for the top. In that case, I could not simply have a z-buffer for each level of vertical height. Does anyone know of an algorithm that can determine the visible area of a billboard sprite in a raycasting environment?

Congratulations for having progressed so far.
Context, first analysis
Your explanation:

I am using a z-buffer, with one stored length to a wall for the x coordinate of each ray.

Means the z-buffer is currently one-dimension.
One dimension is enough in the first case (your first two images) but not in the second case. To see why, imagine that the red tomato sprite was closer to the player, such that the left half of it would be partially obscured by the first wall (bottom left). Since the top of that wall is projected to a diagonal line, it means that the property "is pixel P of the sprite obscured?" does not only depend on X but also on Y.
So, in the exact setup you have, a 1D Z-buffer is definitely not capable of performing the clipping you want.
Options
From that on, here are a few options:

switch to a 2D z-buffer (slower)
switch to painter's algorithm (slower)
switch to a 2D-based occlusion algorithm
study how Doom did it

Your geometry seems similar to Doom. It is probably a very good investment for you to study how the Doom rendering engine works. It clips sprites (called "things") using a 1D criterion, then refines. One area has only one floor height and one ceiling height. This is very important and it looks like your geometry is similar.
Solution
The solution, to summarize, is to keep not only a 1D z-buffer, but actually a structure keeping for each sector (in doom parlance) the lines that make the limit and their parameters (like the a and b in y=ax+b).
Then, when you want to draw the sprite, clip X with 1D criterion but depending on the sector the sprite is in, and then limit the Y range of pixels drawn based on the y=ax+b of the sector just in front of it.
I don't know what data structure you currently have in your program. If this seems totally unreachable, then you need to rethink the data structure you keep while drawing.
If you haven't yet, you should read (sorry if you did already) https://doomwiki.org/wiki/Doom_rendering_engine#Rendering and the pages behind the links there, perhaps run their code in slow motion or see a video where someone shows/explains how it works.  This one lacks explanations but might help your intuition: https://www.youtube.com/watch?v=gfM6NpxmVGg .
Hope this helps.  Keep up the good work!


What is the reason that a boolean operation between two almost identical 3D triangular meshes fails? I have been trying to detect defects on "before-and-after" meshes, by finding the boolean difference between them, to no avail.

I tried these two Python libraries(algorithms run in C++) but their boolean operations would produce error or never finish:

PyVista(VTK wrapper) : https://docs.pyvista.org
Pymesh : https://pymesh.readthedocs.io

More specifically, some testing and findings that I had:

The libraries would operate normally in any other case of boolean operations between two different meshes.
The 2 almost-identical meshes I wanted to use were clean and water-tight. I even used an example shape which I subtracted from itself. It crashed too.
These 2 similar meshes are originating from the same mesh, but with a small difference, like a dent or some noise. I tried to introduce stronger noise or bigger changes, but it still would not work if the 2 meshes had their biggest part identical.
by enlarging 1 of the 2 meshes by more than 0.1%, or by transforming/moving(see attached picture) it by a similar amount, the algorithm starts working. But by that point, the shapes are too different to be useful.

To reproduce the error with Pyvista with an example shape from their website:

import pyvista as pv
mesh_knot = pv.read("knot.ply")
mesh_knot2 = pv.read("knot.ply")
mesh =  mesh_knot.boolean_difference(mesh_knot2)
mesh.plot(eye_dome_lighting=True)

To conclude, has anyone any idea why this would happen? Do you think that there is a way to bypass the problem if no solution is found? Any other ideas of how I should approach my initial problem?

Without debugging the routines with the offending data, it's impossible to say conclusively. However given the examples you have given it sounds like the libraries are falling foul of the coplanar triangle cases when evaluating the meshes. This is certainly an Achilles heel of many CSG implementations out there (far to many in my experience). In many cases, both theory and implementations seem to fail to address these coplanar cases in many CSG libs.

Certainly the fact that it crashes or fails to produce the desired result implies that the libraries you use are buggy or incomplete in this regard.

  The libraries would operate normally in any other case of Boolean operations between two different meshes.

When there are no coplanar triangles between manifolds, the result is well defined and since CSG operations use triangle/triangle intersections fundamentally, if the case of coplanar triangle intersections is not accounted for, everything should be fine and dandy when there are no coplanar triangle tests between meshes. Of course this is not what you require, but makes sense that this operates normally in these scenarios.

  The 2 almost-identical meshes I wanted to use were clean and water-tight. I even used an example shape which I subtracted from itself. It crashed too.

This is certainly not correct and I would say a bug. A crash implies something is very wrong and either the coplanar triangle support is buggy, limited, or simply not implemented at all.

I suspect the latter unless you can get a result out with something simple such as diff'ing one cube from another... if you can get a result in some sandboxed cases, then it could be any of the former possibilities.

To see if your CSG routines can handle the coplanar cases, subtracting one cube from another should produce nothing (which as you said it fails). You could also attempt to subtract one cube from another which has a single face coplanar. e.g. Two cubes, both of length length. One positioned at x - length should produce a cube which is a closed manifold. i.e. Cube A (1x1x1) positioned at 0,0,0... and cube B (1x1x1) positioned at 1,0,0.

  These 2 similar meshes are originating from the same mesh, but with a small difference, like a dent or some noise. I tried to introduce stronger noise or bigger changes, but it still would not work if the 2 meshes had their biggest part identical.

Probably just one triangle in a mesh is coplanar to another triangle in the other mesh which you are operating on, and thus failing. This may be a way to test by creating two meshes with only one triangle from each mesh being coplanar to another in the other mesh. If this fails then It might indicate that this corner case of coplanar intersection is not catered for at all. As said above, if it does work, then this may point to buggy behaviour at much higher level when dealing with coplanar triangles.

  By enlarging 1 of the 2 meshes by more than 0.1%, or by transforming/moving(see attached picture) it by a similar amount, the algorithm starts working. But by that point, the shapes are too different to be useful.

I presume these libs work on floating point numbers, in which case this sounds like the FP equality tolerances are kicking in and evaluating 'almost' coplanar triangles as coplanar, and then subsequently failing to result in the CSG operation. Of course this is problematic for you if the tolerances are high since the input geometry is expected to be 'different enough' to not fall within these tolerances.

Unfortunately, there is nothing you can really do which I think you would find satisfactory since you are effectively at the mercy of the accuracy of the implementation.

If you suspect the libs can handle coplanar triangles between meshes, and its just failing in many cases, you might need to find out how you can kludge the input geometry to not fall foul of the shortcomings that may or may not be present for these corner cases in the implementations:

Remeshing the input geometry may help, although this may result is varying quality of input data in comparison to your measured data, which kind of defeats the purpose and will result in loss of accuracy wrt the original input meshes, but may at least give a result.
Re-tessellating triangles while retaining the mesh features may help. This involves inserting Steiner points into a given triangle and re-tessellating into more triangles. This will result in larger meshes (mem footprint, not geometrically speaking) but may help the routines to resolve coplanar intersections. Unlike the previous suggestion, It will retain the accuracy of the topology of the original meshes though.
Change the FP tolerance (if applicable) that the routines use which may allow you to keep meshes a similar size. However the problem is still there, but this may be satisfactory for your needs allowing you to not have to scale as much. Certainly from a visual standpoint this would be satisfactory I would have thought, however from a numerical point of view this may not be. However this does not fix the issue, rather attempt to circumvent it.

Given that the majority of the meshes will perhaps be similar, if the vertices are what are similar (i.e coplanar triangles have the SAME vertex values, although that screen shot you posted suggests otherwise) you could perhaps simply diff the meshes yourself, finding all the vertices that are not equal when comparing and then tessellating these. This is far more complex though as you would need to keep track of the edges around the different vertices (these edges will use vertices which are equal to others in the other mesh, so not a quick and dirty fix, rather a slightly different approach avoiding the libs you use) so that you can tessellate the different vertices into a meaningful manifold. I wouldn't recommend this as it is quite a specialised case, and may not be generalised enough for your needs.

Ultimately, if you can't circumvent the issue present with the current libs. You may have to find another. I certainly wasn't able to find many that matched my needs with a correct lic that was applicable to work, however I think there are certainly libs out there that would cater for this. Look for CAD libs as this is an important operation in many CAD programs.

A few years ago I spent some time testing and evaluating various different C++ CSG libs for our needs at work as we required a fairly robust implementation for production. While there were various success, they all failed at some point, and coplanar triangles were usually the culprit. It's quite frustrating as the answer is actually quite straight forward and simply requires the Boolean operation to be performed in 2D between the coplanar triangles and then testing if the resulting split triangles are within the 'other' triangle. Why this rather crucial point is missed in a lot of implementations and theory is beyond me.
/rant


Why does my image has a square pattern in cuda path tracer? I am writting a path tracer in cuda following the Shirley's book. I am having a square pattern as an output.
The size of the block change if I change the block dimensions. For this image, the block dimensions follow the aspect ratio, basically 16 * 9 is block size. I know that without actually showing the entire code, it is difficult to debug it. I am just asking if you have any idea where I should start debugging it. My hunch is that there is a problem with my random number generator.
Here is its code in case I am doing something wrong. Here is the host code:
int total_pixel_size = WIDTH * HEIGHT;
size_t frameSize = 3 * total_pixel_size;

// declare random state
int SEED = time(NULL);
thrust::device_ptr<curandState> randState1 = thrust::device_malloc<curandState>(frameSize);
CUDA_CONTROL(cudaGetLastError());

// declare random state 2
thrust::device_ptr<curandState> randState2 = thrust::device_malloc<curandState>(1);
CUDA_CONTROL(cudaGetLastError());
rand_init<<<1, 1>>>(thrust::raw_pointer_cast(randState2),
                      SEED);
CUDA_CONTROL(cudaGetLastError());
CUDA_CONTROL(cudaDeviceSynchronize());

dim3 blocks(WIDTH / BLOCK_WIDTH + 1,
              HEIGHT / BLOCK_HEIGHT + 1);
  dim3 threads(BLOCK_WIDTH, BLOCK_HEIGHT);
  render_init<<<blocks, threads>>>(
      WIDTH, HEIGHT, thrust::raw_pointer_cast(randState1),
      SEED);

Here is the device code:

__global__ void rand_init(curandState *randState,
                          int seed) {
  if (threadIdx.x == 0 && blockIdx.x == 0) {
    curand_init(seed, 0, 0, randState);
  }
}

__global__ void render_init(int mx, int my,
                            curandState *randState,
                            int seed) {
  if (threadIdx.x == 0 && threadIdx.y == 0) {
    curand_init(seed, 0, 0, randState);
  }
  int i = threadIdx.x + blockIdx.x * blockDim.x;
  int j = threadIdx.y + blockIdx.y * blockDim.y;

  if ((i >= mx) || (j >= my)) {
    return;
  }
  int pixel_index = j * mx + i;
  // same seed, different index
  curand_init(seed + pixel_index, pixel_index, 0,
              &randState[pixel_index]);
}

I would really appreciate any pointers to the problem.
.
Here is another image with different block size and dimensions but with the same problem:

I managed to fix it. It was indeed related to repeating random sequences.
The problem was the following. curandState* randState is an array of curandStates, and most calls to curand_* require a pointer of a curandState.
I was sending the randState, the array, to curand_* functions and not for example, a pointer of one of its members.
Now most of my images are like this:


GLSL Compute Shader Setting "shared" memory buffer size Is it possible to set the size of the shared memory of a compute shader workgroup from the host code? There is a way to do this in CUDA and I am suspecting that, since there is an GLSL extension to set the size of a workgroup during launch, there might be a way to do this, as the shared memory size is typically related to workgroup size.

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


Always rotate in the direction of mouse movement In my SharpGL application I do a very simple, mouse controlled rotation of the scene.

gl.Rotate(cameraRotation.X, cameraRotation.Y, 0.0f);

where

cameraRotation.Y += MousePosition.X - previousMousePositionX;
cameraRotation.X += MousePosition.Y - previousMousePositionY;

The problem with this is that the x rotation always comes first, so if I rotate the object around the x axis by 180° and then move my mouse left, the object will rotate to the right instead of left (since the y axis is now inverted). Is there a way to change this so that the object always rotates into the mouse movement direction, regardless of its current position? (like netfabb does it for example)

Transformations, and especially rotations, may have different visual effects, depending on the order they are applied to the target object. For example, using a rotation $M_R$ and a translation $M_T$ to the object's vertices $v_i$, $M_R \cdot M_T \cdot v_i$ will usually1 result in a different pose than $M_T \cdot M_R \cdot v_i$ does.

90 degree rotation and translation along the x axis applied to the box. Left: translation first ($M_R \cdot M_T \cdot v_i$). Right: rotation first ($M_T \cdot M_R \cdot v_i$).

The key here is to keep in mind to which coordinate system the transformation is applied. Assuming that your to be rotated object initially is in the origin without transformations applied, the first rotation will always yield the desired effect. This is because you're applying the first transformation to the object.

But once your object is already transformed (rotated, translated, whatever) by $M_1$, technically you can already apply the next transformation $M_2$ in two places. Namely,

$M_1 \cdot M_2 \cdot v_i$ or
$M_2 \cdot M_1 \cdot v_i$

You describe that

  so if I rotate the object around the x axis by 180° and then move my mouse left, the object will rotate to the right instead of left (since the y axis is now inverted).

This is, because the second rotation is applied to the object itself, which is case 1 of the above. But you want to have the second case, so you need to apply the rotations the other way around. That way, the new rotation will be applied to the already rotated object, i.e. the outer coordinate system.

Ideally, as long as the user holds the mouse button down you adjust that transformation $M_2$. Calculate the distance the mouse moved from the point the user pressed the button, recalculate the whole rotation ($M_2$) and drop whatever you calculated in the time between the mouse-down event and the previous frame. So for the ongoing rotation, pretend that the user moved the mouse instantly from the start to the current position.

Once the mouse button is released, you can finalize the transformation and multiply it into $M_1$, which is the identity matrix in the beginning. (Assuming you always want to rotate around the world's center.)

1 There are some special cases where the result is the same, e.g. if the translation direction matches the rotation axis.


What other paradigms exist besides vector/fragment/transform graphics programming? I am familiar with the basic concepts of writing vector and fragment shaders while using linear transformation matrices to describe orientations in 3D space.

But, what other paradigms exist (theoretical or not)?

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.


Calculate the position and rotation of a quad in 3d space given a 2d projection of that quad from a camera I am trying to build a VR tracking system with a laptop webcam, and I have succeeded in identifying, and tracking paper markers I put in front of my webcam. For context I am using OpenCV with the latest OpenCVSharp wrapper in .Net 5.
Currently I can track all 4 corners of an object (ordered, so orientation is accounted for) as a 2d quad on the webcam's image, so long as I am provided with a reference image before hand. I know the exact measurements of the reference object, and now I want to use both the 4 corners I calculate, and the measurements of the object in order to determine the position and rotation of that object relative to my webcam.
In the future I would also like to add additional cameras to the setup to allow for more precision and reducing dead zones. They would know the positions relative to the other sensors for the sake of simplicity.
How would I go about calculating both the position and rotation of an object given its' measurements, and 4 ordered corners on an image?

Hello Djgaven588 and welcome to the forums!
This is not a computer graphics question, but a computer vision one. The answer to it is a little bit involved and I cannot make it justice on a forum post. However, I can point you in the right direction so that you are able to find the answer by yourself.
Here's a helpful link: https://docs.opencv.org/master/d9/db7/tutorial_py_table_of_contents_calib3d.html
The process is somewhat straightforward, but it depends on how much you know about projections and solving systems of equations.
First you need to find key points on a known object in your image through some kind of image-processing algorithm. It seems you already did that. By known object, I mean that you know its exact measurements in the real world with regards to the selected key points.
Secondly, you need to "unproject" your 2D image points onto 3D space, by reversing the projection math from 3D to 2D. This requires building a projection matrix containing intrinsic and extrinsic camera parameters, as well as finding coefficients modelling the camera lens distortion. This process is known as camera calibration.
Thirdly, when using a single camera, you can unproject the points only up to a scale factor, because the depth coordinate has been lost during the original projection. In order to figure out the scale, rotation, and position of the object, you can set up a system of equations relating the image key points to the known key points in the real world at a specific position and rotation of the known object. Solving this system will let you figure out the transform. Note that it is important to have a reasonable amount of key points (even redundant ones) so that the error can be minimised.
OpenCV has methods and functions for doing all of these procedures, and there are many tutorials on the web, like the one I linked above.
I hope you can figure it out! :)