Computing heat diffusion creates weird results I am trying to model heat diffusion on the surface of a mesh. I annexed the most important bits of theory about this topic as screenshots on the question see the bottom.
The crux of the issue is we are solving a linear system $(M - tL_C)u = \delta_y$. In this case $M$ is a diagonal matrix, $L_C$ is the discrete Laplace operator, $t$ is a constant time step equal to some epsilon and $\delta_y$ is a sparse vector with only one non-zero entry which is equal to 1.
My expectation is that, upon solving this system and drawing the resulting vertex distances, I get a fading from white to black starting at the source vertex and slowly fading away as the vertices go away from the source. I am however seeing this:

Which looks like random noise to me, as if I messed up the calculation.
I implemented the solver using Eigen, this is the snippet:
Eigen::DiagonalMatrix<float, Eigen::Dynamic> areas(sources.size());
    Eigen::SparseMatrix<float> laplace_operator(sources.size(), sources.size());

    for(uint i = 0; i < sources.size(); i++)
        laplace_operator.insert(i, i) = 0;

    areas.setZero();

    for(uint e = 0; e < mesh.Edges().size(); e += 2)
    {
        const auto& edge = mesh.Edges()[e];
        const uint i = edge.Vert().ID();
        const uint j = edge.Pair().Vert().ID();

        const Eigen::Vector3f e1 = -edge.Next().Dir().normalized();
        const Eigen::Vector3f e2 = edge.Prev().Dir().normalized();

        const float alpha = acos(e1.dot(e2));

        const Eigen::Vector3f p1 = -edge.Pair().Next().Dir().normalized();
        const Eigen::Vector3f p2 = edge.Pair().Prev().Dir().normalized();

        const float beta = acos(p1.dot(p2));

        const float laplace_coeff = -0.5f * ((1.f / tan(alpha)) + (1.f / tan(beta)));

        laplace_operator.insert(i, j) = laplace_coeff;
        laplace_operator.insert(j, i) = laplace_coeff;

        laplace_operator.coeffRef(i, i) -= laplace_coeff;
        laplace_operator.coeffRef(j, j) -= laplace_coeff;
    }

    uint count = 0;
    for(auto& v: mesh.Verts())
    {
        std::vector<HMesh<VertexData>::MFace*> faces = v.ContainingFaces();
        for(auto f: faces)
        {
            areas.diagonal()[count] += f->Area();
        }

        areas.diagonal()[count] /= 3.f;

        count++;
    }

    SparseLU<SparseMatrix<float>, COLAMDOrdering<int> > solver;

    const Eigen::SparseMatrix<float> a =
        Eigen::SparseMatrix<float>(areas) - 0.01 * laplace_operator;
    solver.analyzePattern(a);
    solver.factorize(a);

    return solver.solve(sources);

I have checked and sources is indeed a sparse vector with a singular source vertex set to 1 so the input is correct. The mesh operations that fetch values are very tested and they are returning what is expected, so I know the error is in the logic of this function.
I suspect my mistake might be creating the laplace operator, but I am not sure.

I messed up I am doing a double negative and that is causing the problem:
const float laplace_coeff = -0.5f * ((1.f / tan(alpha)) + (1.f / tan(beta)));
This should be positive.


VR stereo rendering with Instancing I have been reading this paper by Timothy Wilson Fast Stereo Rendering for VR
and it would suit our game engine (DirectX 11) to use this method of stereo rendering. I have managed to get the game rendering Instanced and the screen squished into left and right areas like he mentions but am unable to get the SV_ClipDistance working correctly, when I use his methods or the method the jMonkeyEngine uses I get 4 views of the world!

My question is does anyone know if you can write SV_RenderTargetArrayIndex in a pixel shader according to MSDN it says it can be read and written by the pixel shader but in all my experimentation I am unable to get the shader to compile, it complains about too many outputs. If I could get this to work the instancing would work by just setting the SV_RenderTargetArrayIndex to SV_InstanceId. Any help would be much appreciated.

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

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

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

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


Reading neighbouring pixels during object draw call I need something to be cleared up for me, and I hope this is the right place to ask my question:
I intend to attempt stochastic transparency, where I will draw glass panes and smoke particles onto the g-buffer for deferred shading.
For every 2x2 cell of pixels, I will allow up to 3 of the 4 pixels to be used for glass or smoke. The last pixel is always the opaque background. But say we have this situation:

Camera
(Near clip plane)
Smoke particle
Glass pane
Solid wall
(Far clip plane)

The smoke particle is in front of the glass pane, and would occupy all 3 pixels. This I do not want, and therefore I will need to check whether neighbouring pixels in that 2x2 cell already have 'smoke' or 'glass' written to them, rather than just the simple Z-check.
I therefore wish to sample neighbouring pixels from the same g-buffer that I'm currently writing to, but this seems not possible, am I right? And why do the depth & stencil buffers seem to be exceptions to this, or does this have something to do with only reading the exact pixel you are about to write to?
I hope the way I formulated the question(s) make sense, and is sufficiently detailed.

In general you can't safely read from neighboring pixels in the render target you're currently writing to. You can sample from them, but there's no guarantees about how other pixels are scheduled on the GPU, so it's a race condition—you might get the neighboring pixel value either before or after modification, and it might change frame to frame due to unpredictable scheduling differences.
You can read from the same pixel you're about to write to, but only if your geometry is set up to ensure that nothing is overlapping in screen space (e.g. a full-screen pass). If other triangles in the same render pass are overlapping the same area on screen, then you have a race condition again, similar to the neighboring-pixels case. (You can use fragment_shader_interlock or equivalent functionality to address this case, but it is not universally supported across all GPU vendors, and it can also be slow.)
The depth and stencil buffers, as well as fixed-function blending (additive, alpha, etc) can get around this because they have special-purpose hardware that sorts the fragments in submission order in order to apply those simple fixed operations.
I believe the way stochastic transparency usually works is to randomize the set of pixels output and use spatial/temporal filtering to clean up the noise afterward. So you wouldn't have such fine-grained control like "within each 2x2 block, there will be N pixels of this, and M pixels of that". It would be more probablistic, like "on average, X% of the pixels will be this, and Y% of the pixels will be that", with the exact outputs being randomly chosen each frame.


smallpt: when to stop diffuse ray scattering For those familiar with smallpt, the ray tracer in 99 lines: I am checking the code, and there is something that is not clear to me in the DIFFUSE ray scattering.
After the rays are shot, they keep bouncing until the if-statement with the Russian Roulette stops them.

if (++depth>5) if (erand48(Xi)<p) f=f*(1/p); else return obj.e;

This means that, when rays are scattered and hit the light source, they don't actually stop there (which is what I thought at first: rays bounce until they hit the light source, or until they reach a specific amount of bounces). Am I missing something?

p is gonna be zero for light sources. Light sources are defined by emission variable and color is zero for them. Hence the reflectance parameter calculated previous to this line p would be zero giving us obj.e


Understanding inequality to equality in the Hartmann & Gribbs frustum planes extraction method I've been reading this article on how to extract the plane equations from the view and projection matrices. And I can understand most of it. However, the only thing that is unclear to me (and that might be for lack of mathematical knowledge), is the part where they transform their inequality 0 < v * (row4 + row1) into the equality  v * (row4 + row1) = 0 (that is for calculating the plane in the x negative side).
Usually, to convert inequality to equality you use a slack variable, but in their approach, none was used. How can we be sure that  v * (row4 + row1) will always be zero on that frustum plane? All we know is that the resulting value of  v * (row4 + row1)  has to be positive to be on the right side of that frustum plane.
I also know how the plane equation is constructed. How we use the dot product of two vectors (any vector in the plane and the normal a,b,c) must be equal to zero: ax + by + cz + d = 0. I can see that the resulting expression from v * (row4 + row1) > 0 results into a identical plane equation. My only doubts are in the conversion from inequality to equality.

The volume inside of the frustum is defined by a set of inequalities, and since we are trying to find the boundaries of the frustum, we set the inequalities to equalities. That's really all it is.
To take a 1D example, if we have a "frustum" defined by 0 < x < 5, then of course the bounding points of it are defined by x = 0 and x = 5. Replacing each inequality by an equality, in turn, gives you the most extreme point you can get to in that direction.
Slack variables, BTW, don't really convert inequalities to equalities. They just transform the inequality into a standardized form "x > 0" (or "x ≥ 0") for some slack variable x.


Inconsistent shading in pathtraced image I am currently building a pathtracer, which has support for vertex normals and face normals.

There seems to be an issue when it comes to rendering objects with triangles exported from Blender. Regardless of how I calculate the normal, the result always shows inconsistent shading of triangles.

The shading seems to change per triangle, with the ones more aligned to the camera being correct. It seems to depend on where the objects are in the scene relative to the camera. Below is the intersection algorithm for the triangle.

bool Triangle::intersection(Ray &ray, HitInfo &hit)
{
    float3 edge1 = v1->pos - v0->pos;
    float3 edge2 = v2->pos - v0->pos;

    float3 h = ray.getDirection().cross(edge2);
    float a = edge1.dot(h);

    float f = 1.0 / a;
    float3 s = ray.getOrigin() - v0->pos;
    float u = f * (s.dot(h));

    if (u < 0.0 || u > 1.0)
        return false;

    float3 q = s.cross(edge1);
    float v = f * ray.getDirection().dot(q);
    if (v < 0.0 || u + v > 1.0)
        return false;

    float t = edge2.dot(q) * f;
    if (t > 1e-9 && t < ray.tmin)
    {
        hit.t = t;
        float3 temp_normal = unit(edge2.cross(edge1)); //unit(v1->normal*u + v2->normal*v + v0->normal*(1. - u - v));
        if (unit(ray.getDirection()).dot(temp_normal)< 1e-9) temp_normal = temp_normal * (-1);
        hit.normal = temp_normal;
        return true;
    }
    else
    {
        return false;
    }
}

The intersection algorithm calculate the normal using the cross product of the edges, however using the normals provided by blender does not change much either.
I use the Moller Trumbore intersection algorithm, exporting obj's from Blender (enabling "keep vertex order" doesn't change anything). I have also tried different materials but the problem still persists.

The above image is the normals being rendered with an emissive shader. This is the result I would expect, so I don't think this is the issue.

float3 cosineSampleHemi(float u1, float u2)
{
    float z = std::pow(1.0 - u1, 3.0 / 5.0);
    float phi = 2.0 * M_PI * u2;
    float theta = sqrt(std::max(0.0, 1.0 - z * z));
    float x = theta * cos(phi);
    float y = theta * sin(phi);

    return float3(x, y, z);
}

float3 random_in_unit_sphere() {
    float3 p;
    do {
        p = float3(drand48(),drand48(),drand48())*2.0 - float3(1.0);
    } while (p.dot(p) >= 1.0);
    return p;
}

The above code is for the sampling, I have tried both functions and it produces similar results. Below is the lambertian scatter function, which uses the hemisphere sampling methods.

bool Lambertian::scatter(Ray &ray, HitInfo &hit, float3 &attenuation, Ray &new_ray) const
{
    new_ray = Ray(ray.getHit(hit.t), cosineSampleHemi(drand48(), drand48()));
    attenuation = m_colour;
    return true;
}

If any more info is needed I will be happy to supply it, as I am completely stumped at this point.

I have managed to fix the error. It turns out the error was never situated in the normal calulation it was the shading algorith. The floating point precision error caused the new ray to be slightly below the surface, which meant it would intersect itself and become darker. This is a problem common in biased raytracers, the phenomenon known as "Shadow acne".

To fix it I added the following code:

bool Lambertian::scatter(Ray &ray, HitInfo &hit, float3 &attenuation, Ray &new_ray) const
{
    float3 offset = hit.normal*(1e-5);
    new_ray = Ray(ray.getHit(hit.t) + offset, cosineSampleHemi(drand48(), drand48()));
    attenuation = m_colour;
    return true;
}

the offset variable moves the ray origin to slightly above the surface by a small amount and that seems to fix the issue.


Am I calculating perspective projection correctly? If I have a point in world space: (wx, wy, wz)

and I have a centre of projection: (cx, cy, cz)

and I wanted to project that point using perspective projection

would my point on the screen be calculated by:

x = (cz * wx) / wz
y = (cz * wy) / wz

I got this from this lecturer https://www.youtube.com/watch?v=VpNJbvZhNCQ
I don't understand what he means by the variable 'd'. What would the variable 'd' be?

In the video you linked to, $d$ is just the distance from the eye to the image plane.  To simplify things though, you can just set $d$ to 1, which is the usual case and causes it to disappear from the formulas.

Your formula for projection is a bit wrong but don't worry, projection is actually pretty simple.

$x_{Screen} = x_{World} / z_{World}\\
y_{Screen} = y_{World} / z_{World}$

If you want to move the center of projection, you can do so with a screen space coordinate, by modifying the formula to be this:

$x_{Screen} = x_{World} / z_{World} - x_{ScreenCenter}\\
y_{Screen} = y_{World} / z_{World} - y_{ScreenCenter}$

If you want to re-introduce the $d$ value to control the distance from the eye to the projection plane, you can use the formula below.  Adjusting $d$ will make the camera look like it is zooming in or out.  Again, you can just set $d$ to 1 though and not deal with it.

$x_{Screen} = d*x_{World} / z_{World} - x_{ScreenCenter}\\
y_{Screen} = d*y_{World} / z_{World} - y_{ScreenCenter}$


Detect in-focus regions of an image Is there any strategy to detect the region of an image that is sharp and in-focus, in order to separate the out-of-focus background? I've tried using edge detection methods but without any success.

In other words, is it possible to determine if an area of an image is blurred (out of focus) or not?

it is quite easy to measure the local max frequency in an image (at least as a low resolution mask, with some regularization).
Several papers of the MIT graphics group have been around detecting and processing from this kind of clue, with regular or coded aperture cameras.
e.g. Defocus Magnification and Image and Depth from a Conventional Camera with a Coded Aperture.


B spline curve generation in Python I am using the de boors algorithm to generate B splines in python. However I am getting spikes in the final figure. I do not understand why this happens. I am posting my code here for reference

def knot_values(n,k):
      t = np.zeros((1,n+k+1))
      for i in range(0,n+k+1):
            if i<k:
               t[0][i] = 0
            if i>=k and i<=n:
               t[0][i] = i-k+1
            if i>n:
               t[0][i] = n-k+2

      return t

def basis_spline(u,t,i,k):
    if k==1:
        if u>=t[0][i] and u<=t[0][i+1]:
             sol = 1
        else:
             sol = 0
    else:
        a = (u - t[0][i])*basis_spline(u,t,i,k-1)
        b = t[0][i+k-1] - t[0][i]
        c = (t[0][i+k] - u)*basis_spline(u,t,i+1,k-1)
        d = t[0][i+k] - t[0][i+1]
        if b == 0:
            temp1 = 0
        else:
            temp1 = a/b

        if d == 0:
            temp2 = 0
        else:
            temp2 = c/d

        sol = (temp1) + (temp2)

    return sol

def curve_generator(n,k,ctrl_x,ctrl_y):

    t = knot_values(n,k)
    print(t)
    u = np.arange(t[0][k-1],t[0][n+1],0.001);
    length = u.shape;

    x = np.zeros((1,length[0]));
    y = np.zeros((1,length[0]));

    for i in range(0,n+1):
        for j in range(0,length[0]):
            x[0][j] = x[0][j] + basis_spline(u[j],t,i,k)*ctrl_x[i];
            y[0][j] = y[0][j] + basis_spline(u[j],t,i,k)*ctrl_y[i];

    return x,y

    n = 6
    k = 3
    ctrl_x = np.array([0,3,6,9,10,12,15])
    ctrl_y = np.array([0,4,2,3,7,8,5])

    [x,y] = curve_generator(n,k,ctrl_x,ctrl_y)

    n = x.shape
    a = [0]*n[1]
    b = [0]*n[1]
    for i in range(0,n[1]):
        a[i] = x[0][i]
        b[i] = y[0][i]

    plt.plot(a,b)
    plt.show()

In line 15 use the half-open interval, i.e.,

if u>=t[0][i] and u<t[0][i+1]:

Otherwise, at knot values, you evaluate two basis functions at the k=1 basis when you only want one. This causes the wrong evaluation of the basis function at the knot values and therefore the spikes.


What's the difference between geometric surface normal and shading surface normal? In my opinion, geometric surface normal is the cross product of triangle edge vectors, and shading surface normal is the interpolation of the predefined normals at the three vertexes.

I used Mitsuba to render the geometric normal channel and the shading normal channel:

geometric normal:

shading normal:

Your existing opinion is correct, though there's one extra detail. The geometric normal is the normal of the actual triangle, based on the vertices' positions (the cross-product of edge vectors, as you said). The shading normal is altered from this, and is used when shading a fragment or ray hit. In the simple case, it's the interpolation of the three normals set at the vertices. This is used for curved objects to hide the polygon boundaries. It might also be modified by a bump map or normal map, to add finer detail to the appearance than the polygon mesh has.


GPU short circuit when multiply by 0? So I am trying to make my shader efficient by lowing the amount of texture lookups. If I had a line of code with something like.

step(1.0, x) * texture2D(pic1, uv);

Where x is a value that ranges from 0 to 2 based on the fragment position.  Would the GPU see when step evaluates to 0 and thus not ever calculate texture2D? Or would it still lookup the texture because the 0 is not constant?

BTW I use the term "short circuit" because I have been told that is what happens when you have false && (bla) the computer sees the false and ignores the right.

There is a difference between being able to determine value at compilation time and at runtime.

false && bla
Gets eliminated because of C/C++ lazy operand evaluation rule which is standardized with left to right order.
The compiler generates no code so the machine has no overhead.

step(1.0, x) * texture2D(pic1, uv);

That will depend if x is coming from a uniform value, in which case the drivers will compile an adjustment of the shader (and put it in a combinator cache). At some point before starting to render.
(this can cause hiccups in framerate when new uniform values are encountered that cause massive shader rebuild)

Now, if x is dependant, which means it comes from a previous calculation that comes from varying values or system values, the compiler will cut your expression in 2 parts, the lerp calculus and the sample call.
It will move the sampling of the texture in the first instructions of the shader. (provided it's unconditional in the shader flow).
So you're basically screwed when it's 0, you'll pay the sampling anyway.

In your case (0-2 wrt frag pos), I would recommend using if (inrect(0,0,1,1)) because this is a low frequency "step" function, which means very good branch elimination in 3 quarters of the screen.


How to interpolate vertices when clipping? When we clip in homogeneous clip space, we have to generate a new vertex located at the intersection between the edge and the clip plane. We thus have to interpolate the $(x , y, z , w)$ position of both vertices to generate the new vertex position. It seems all well and good, but what should I do when the generated vertex after interpolation has a w of 0?
It doesn’t work because the w-divide makes the point go to infinity (division by zero).
So should I ensure that I never generate vertices with a w of 0 (how?)? Or should I just deal with the null w (how?)?
You might say that this situation never happen, but it actually does happen, especially when the z of the vertices are set to their w, for skyboxes for example. In this case, when we clip against the near plane (z = 0 in clip space) and interpolate the position, we will end up with a z of 0 but also a w of 0...

Points in front of the camera have $w > 0$ strictly, by definition. I would say that if clipping is giving you points with $w = 0$ then something is going wrong.
Consider the left/right/top/bottom clip planes. There is no way that a triangle can span from part of the visible frustum, to the $w = 0$ camera plane or behind it, without also crossing outside one of the frustum side planes—or else the near plane, which lies at some positive distance $w_\text{near} > 0$.
You mentioned skyboxes and setting $z = w$ in the vertex shader output. Such geometry must cross the frustum side planes before it can get to the near plane. (How could part of a skybox get close enough to the camera to be clipped by the near plane only?) If you are correctly clipping it against all of the frustum planes, you must end up with $w > 0$ in the final vertex.


How is texture baking implemented? Suppose we already have UV coordinates assigned for mesh vertices,
how is texture baking implemented?

I guess it will be something like this:

for each coordinate (u, v) in parameter space:
    (x, y, z) = inverse(u, v) # Get the geometric space coordinate.
    f = faces(x, y, z) # Get the corresponding face. We may need face's normal for rendering.
    pixels[u, v] = render(x, y, z, f)

What is the inverse function? Is it a projective transformation, or a bilinear transformation?

And how to get the corresponding face of one coordinate (u, v) efficiently?

Texture baking can be accomplished by simply rendering the mesh in texture space.  In other words, you set up a render target matching the size of your texture, and draw the mesh with a vertex shader that sets the output position to the vertex's UV coordinate (appropriately remapped from [0, 1] UV space to [−1, 1] post-projective space).

The vertex shader can still calculate the world-space position, normals, and whatever else it needs and send those down to the pixel shader.  Then the pixel shader can do its thing without even being aware that it's rendering into texture space instead of the usual screen space.  Lighting and shading calculations will work as usual as long as the pixel shader inputs are hooked up correctly.

You don't have to do any complicated inversion operation; you just take advantage of the GPU rasterization hardware, which is happy to draw your triangles at any coordinates you choose.

Naturally, this requires that your mesh already has a non-overlapping UV mapping that fits within the unit square, but texture baking doesn't really make sense without that.


How does a GPU process a task by using multiple ALUs? I know the philosophy of how a GPU works {many weak men doing a task (GPU) compared to one strong man doing the same task (CPU)}.

How does the GPU manage all the ALUs and schedule the necessary calculation to an ALU?

Architecture Background

GPU don't schedule to individual ALUs, but rather groups of them. Terminology will vary based on GPU company (NVidia, ATI, and Intel), but I will stick with NVidia terminology since they all work somewhat similarly at the high level.

NVidia has a concept of CUDA cores, each of which contains an ALU and/or FPU, which make up collections called Streaming Multiprocessors (SM). The Fermi architecture has 32 CUDA cores per SM, for example.

GPUs operate in a SIMD-like manner. This means that unlike a CPU, which traditionally has had one execution unit per instruction, GPUs have many execution units per instruction (CUDA core). These groups of execution are called warps.

Answer

GPUs contain scheduling units that attempt to reach maximal utilization. Warps are scheduled in a way to utilize as much of the GPU as possible. One way to do this is to use a round-robin approach. Latency is something that a GPU struggles with compared to a CPU, so scheduling a process as soon as possible is often desirable. Like an OS (which controls CPU scheduling), however, simplicity and hiding latency are still desirable traits to an extent, although other tradeoffs may be deemed more important.

Your workload will determine how scheduling is done. If you run a CUDA kernel or shader on 320 pieces of data (threads), you will need at least 10 warps to be scheduled (this depends on the type of data as well). If you have 1 thread that needs to be calculated, oh well, you still need to schedule one warp to do the calculation.

Of course, what ratchet freak said is true about GPU architectures and algorithms being proprietary, especially when compared to CPUs.


getting the outline of an arbitrary set of shape unions I hope this is the right forum to ask this question.
I want to experiment with procedurally generating some buildings, and as a first step I want to generate a 2D shape to use as a foundation for the building.
My plan would be to create a union of an arbitrary (but probably quite small) amount of shapes.
It seems simple enough, but I wonder what algorithms there are available for breaking up such a union into simple line shapes? (that can be used to place walls)

Draw it twice, first time at full size and the color you want for the outline, draw it filled. The second time you draw it scaled down in both the x and y directions. The second time you draw it the color is the same as the background color, and draw it filled again. What will be left is the outline. Is this what you had in mind?
Per your comment, I add more info:
Generating an array of exterior edges can be done in a few ways. The easiest one to implement (but also the slowest) is to count the number polygons that share a given edge. The exterior is all the edges which only have a single polygon using that edge. And the two vertices that make up that edge become part of the array of "lines"( an actual line can be computed from two vertices). Also, this will count "holes" as part of the exterior. For example if a building surrounds a courtyard, then the courtyard would be counted as exterior.
This can be implemented by creating an array of unique vertices, then each polygon is formed by indexing into the list. (just like indexed triangle draw lists). Finally pick a single polygon off the list, takes its first edge, and search all the other polygons for that edge.
Another method using a doubly connected edge list is given here.


Asset creation for signed distance field rendering? In traditional computer graphics, most 3D models are rendered by rasterizing or ray tracing against a subdivided mesh of primitives, usually triangles or quads. More recently, some real-time techniques have been predicated on ray-tracing against signed distance fields (SDFs). Intuitively, these distance fields cannot be the same triangles and quads of traditional rendering and must be something like 3D geometric primitives (cubes, spheres, etc.) in order to get proper shading. Is this true? If not, can complex scenes of "traditional" 3D models be represented using SDFs? If it is true, then how do artists create high-detail models used in SDF renderers?

Signed distance fields are popular in minimal graphics applications, such as the demo scene, where interesting objects can be synthesized from few simple analytic primitives such as spheres or cubes. However, signed distance fields are not restricted to these simple objects, and they do not necessarily need to be designed by a human. For example, you can synthesize the analytic signed distance field of a triangle mesh without any artist interaction - the SDF is just the signed distance to the closest triangle after all, which can be easily computed. This allows you to keep using your traditional mesh pipeline while also using SDFs in the background.

In the case of the Unreal Engine, the SDF is precomputed automatically once for all static meshes and is then sampled into a low-resolution 3D texture. It can then be cheaply evaluated everywhere using a simple texture lookup, allowing them to do soft shadows and similar at runtime. This Unreal presentation at GDC 2011 mentions the 3D textures briefly (slide 27).


THREEjs: updating an object's matrix doesnt change it's position and rotation params I want to set a transformation matrix to an object upon creation and then control it by position, rotation and scale, but while changing the matrix does change the object in world space, it's position parameter still remains 0, 0, 0.
let mesh =  new THREE.Mesh(
    new THREE.BoxGeometry(),
    new THREE.MeshPhongMaterial({color:0xf15728})
)
this.scene.add(mesh)

let pos = new THREE.Vector3().setFromMatrixPosition(m)

mesh.matrixAutoUpdate = false
mesh.matrix.copy(m)

// ***************//
mesh.updateMatrix()
// ***************//

console.log("mesh.position", mesh.position)
console.log("pos", pos)

Here's the output for the values of both pos and mesh.position

I think you need to call setFromMatrixPosition(m) again after updating the matrix. After all, you need to update both the position and matrix, not just the matrix.
mesh.position.setFromMatrixPosition(mesh.matrix) or mesh.position = new THREE.Vector3().setFromMatrixPosition(mesh.matrix) right after mesh.updateMatrix()


How are Physically Based Rendering Methods Researched? Recently a question that came to my mind was that How are Physically Based Rendering Techniques researched and developed? Do people just use current equations by physicists or do they create their own? Hopefully I've explained my question correctly.

I guess physicists, and before that term was used philosophers, have always been thinking about the nature of light, color and shadow. Knowledge about those matters is not purely rooted in people trying to create the ultimate rendering technique for CGI. In Wikipedia there are whole categories that show formulas and models that were invented to describe attributes of lighting. What programmers do is to try to combine and fit those models into a probably more simple model that can be implemented in some way.
With the increase in computing power, those models align more and more with the models that were created by physicists to describe lighting in the real world.
If you look into recent (by that i mean 5 years back) papers that describe physically based rendering techniques, you will see that almost all of them base their algorithms on formulas and units of measure that are somehow used to describe real lighting.


How do I use ColorSync Utility to convert between Display P3 and sRGB? I have a Display P3 color (1, 0, 0), on a scale of 0.0 to 1.0. I want to find out what the closest color to this is in the sRGB gamut. I chose (1, 0, 0) on the right side ...

... but the left side still shows (1, 0, 0).

This makes no sense since (1, 0, 0) in sRGB is not the same color as (1, 0, 0) in P3 — the former is less saturated. As you can see in the screenshot above if you're reading this on a P3 monitor.

So, how do I convert this?

Conversely, given an sRGB color (1, 0, 0), how do I find out what the most saturated version of this color is in P3?

Assuming that "Display P3" refers to the DCI-P3 colour space, this covers a wider gamut of colours than sRGB, so that an exact match is not possible for P3 colours that fall outside the gamut of sRGB. The example colour in the question is the reddest red that DCI-P3 can produce. This is considerably redder than the reddest red that sRGB can produce, so the nearest available red is shown instead.

You are right that (1, 0, 0) in sRGB is not the same as (1, 0, 0) in P3, but it is the closest it is possible to get. If you enter (1, 0, 0) in sRGB, you should see that converting it to P3 gives a red that is not the extreme (1, 0, 0). Any colour in sRGB can be converted to P3, which covers all of sRGB and more. However, only some of the colours in P3 can be converted to sRGB, since sRGB doesn't cover all of those colours. For colours that sRGB doesn't cover, the conversion utility used appears to be giving the nearest approximation available within sRGB.

It is analogous to converting RGB to greyscale. Any shade of grey in RGB can be converted to greyscale and still look the same, but outside of the set of greys, any other colour will be changed when you convert to greyscale. So red will be converted to a grey that best approximates it.

In answer to your final sentence, if you want to take an sRGB colour and find the most saturated form of that colour that P3 can represent, then it is going to be less straightforward when you are dealing with a colour other than one of the primaries red, green, and blue. You need to consider whether you want the nearest hue amongst the maximum saturation colours in P3, or the most saturated of the exact hue match colours in P3. These are subtly different, because for a given hue its maximum saturation available within P3 is less than the maximum saturation available for the primaries, since the colour space is a triangle. You can compromise by deviating only slightly from the desired hue to achieve slightly more saturation, but the degree of compromise will depend on your purpose.

Even for the primaries, you need to ask whether you want to convert the greenest green sRGB can represent to the greenest green P3 can represent, or whether you want to take into account that those two colours are not quite the same hue. since sRGB and P3 don't use quite the same primaries (only the blue primary is identical). If you want the hue to remain constant, it might help to convert to an intermediary colour space that includes hue as a parameter.


How to watch image being ray traced? In my ray tracer, I render my images out to a .PPM file and then view it in photoshop. To make things easier and faster I want my ray tracer to open up another window and show the image being rendered each ray at a time like how modern renderers like Mental Ray or V-Ray do it.

How is this done? What is the most common method? I tried writing a viewer in C# that uses a picturebox to load the image which is then constantly refreshed but that doesn't work since the image cannot be shared. After asking on reddit most people suggested writing the image to an OpenGL quad as a texture but I don't want to do this as it complicates things. I've taken a look at at the setpixel function which will set the pixel's color at a specified coordinate and color, is this the way to do it?

It is really great to watch your image be rendered, it is also helpful because if your image is rendering wrong you can stop rather than waiting for the entire image to rendered and then noticing there is a problem.

(the image below is 3DS Max with Mental Ray which shows image being rendered each Ray at a time, I want to achieve this)

This is a very common question that most people in your situation (interested or fascinated shall I say in Computer Graphics) have and a problem they want to figure out. The solution is pretty simple, though not necessarily that straightforward to implement.

I can't make a specific answer because it depends on the OS you are using, and as I said this is not something you can do in 2 lines of code.

The answer is to use some sort of library that:

allows you to create a window on your system
allows you to display some content (an image) in the window you created and displayed to the screen

The first task is generally quite complex regardless of the OS you use (MacOS, Windows, Linux). For the second step, you need to generally go through some sort of graphics API (like OpenGL).

So there is hope for you. One thing you can do is use some other library that works as a wrapper around 1) and 2) In other words they help you especially with the creation of the window, and then if you know OpenGL you can do the rest of the work. You will need to create some texture that you will fill with the content of your image as it gets rendered and display this texture to the screen (that's pretty basic in OpenGL though you need to know this API in order to do so).

GLFW is a great library that will allow you to do that. It's simple to use and compile and install, etc. You can alternatively use Qt but I don't recommend it unless you want to become a professional programmer.

I had some documentation about the whole process but it's offline right now. I might put it back in a few weeks but you will need to wait I am afraid.

EDIT

I am editing the answer to respond to your comment. The algorithm would look like this:

Color *buffer = Color  char [w * h];
// create a texture that you can map onto the quad stretched over the area
// of the window. You will need to create a quad rendered in the space of the
// window, aka you in 2D not 3D.
...
// now render your image using you ray-tracer
for (j = 0; j < h; ++h) {
    for (i =0; i < w; ++i) {
        buffer[j * w + i] =  trace(orig, dir, ...);
    }
    // it is not very efficient to update your window each time you have
    // a new pixel so do this every row or every 10 rows ... you get the idea
    // copy content of your buffer into the GL texture
    // I am not using the right calls here, too lazy to find the right ones
    glCopyTexture(myGLTextureId, buffer, (sizeof(char) * 3 * w * h);
    // do the texture binding, etc... all GL or DX stuff
    ...
    // this will update your window with the content of the buffer
    glSwapBuffer();
}
// now save content of buffer to image file
saveToDisk(buffer);

Windows? Arg(. You will have to use DirectX calls indeed but they 2 APIs are very close.


Calculate normals from vertices Assume you have a list of vertices and their connectivity information. (I.e you can find all the adjacent edges and faces to each vertex).

What is a good approach to calculate a normal from this information?

Currently I first tried naive averaging, i.e:

$\frac{\sum n_i}{N}$

Where $n_i$ are the face normals and $N$ is the total number of faces

And I also tried:

$\frac{\sum n_i * a_i}{A}$

Where $a_i$ are the respective areas of each face and $A$ is the sum of the areas of all adjacent faces.

The first gave me this:

The second gave me this:

What I want is:

That last image I obtained by setting the normal to be the vector from the origin to the vertex position, but this is only true for highly regular meshes like cubes and spheres, it doesn't hold generally. The data I am using to make this is just the default blender cube.

Increasing precision to doubles doesn't seem to affect the result. This is the wiremesh:

Obviously the issue occurs because the number of faces adjacent to a vertex isn't balanced, which skews the normals into certain directions, but I don;t know how to compensate for that

You are not too far off with your second averaging approach. The problem is, that the area is the wrong weighting factor for what you want to achieve. You want each of the 3 sides of the cube to contribute equally to the vertex normal, but you need to extract the information from the adjacent triangles. The area and the number of triangles are bad weighting factors since they vary with the number of triangles per side. But one thing stays always the same at each vertex: The angle between two edges at the side. So you just need to take the angle of each triangle connected to the vertex and use it as a weighting factor for its normalized face normal. The weighting factors will always sum up to 90°/$\frac{\pi}{2}$ per side of the cube. Look for example at the bottom left vertex at the front in the image you posted.

Your first approach fails because it yields:

$$N_v = \frac{2*N_l + 2 \cdot N_f + 1 \cdot N_b}{5}$$

where $N_l$ is the left, $N_f$ the front and $N_b$ the bottom side normal. Assume them to be normalized. The factors result from the triangle count at the vertex and their sum.

Your second approach fails because it yields:

$$N_v = \frac{N_l + 0.5 \cdot N_f + 0.5 \cdot N_b}{2}$$

Here the factors result from the fact, that only the left face has all its triangles connected to the vertex. The bottom face connects only 1 of 2 and front face only 2 of 4 equally sized triangles to the vertex.

If you take the angles, you get:

$$N_v = \frac{2\cdot 45 \cdot N_l + 2 \cdot 45 \cdot N_f+ 90 \cdot N_b}{270}$$

Now each side contributes equally and independent of the number and size of triangles connected to the vertex.

EDIT:

I just realized, that the front face also contains only 2 triangles. The diagonal of the back face triangles irritated me. However, this will not affect the conclusion but the weigting factors change. For the fist approach you get:

$$N_v = \frac{2*N_l + 1 \cdot N_f + 1 \cdot N_b}{4}$$

The second remains unchanged and for the angles you get:

$$N_v = \frac{2\cdot 45 \cdot N_l + 90 \cdot N_f+ 90 \cdot N_b}{270}$$

which is still correct. What is interesting is that both your approaches give the same results for the shown cube, since a connection of the vertex to 2 triangles also means that the area weight is doubled. You can also see this if you compare both pictures.


Multiple viewports with modern OpenGL? I use SDL2.

Currently my only shader has a MVP matrix, and transforms the points with it.

I calculate my View and Projection matrix for a camera with GLM:

glm::lookAt(pos, pos + forward, up);
glm::perspective(fov, aspectRatio, zNear, zFar);

I searched it, but I can only find legacy implementation of multiple viewports.

If I create for example 4 cameras and let's say that they all the same, except every camera has a different quarter of the screen to render. (So I want 4 viewports with the same content)

How can I do this? Sorry if I didn't give enough informations, feel free to ask.

If you are writing your own Vertex/Fragment Shader there is another additional possibility to do this. It is much more complicated but might be useful for you and/or others. Additionally it speeds up the whole drawing process since it uses only one call to a draw command. The maximum number of Viewports is defined by GL_MAX_VIEWPORTS and is usually 16.

Since OpenGL 4.1 the method glViewportArrayv exists. It can define an array of Viewports. The Viewports which are created by this method have an index assigned.

This index can be used in the Vertex Shader to set the Viewport to which the scene is rendered. (You have to include the "ARB_shader_viewport_layer_array" extension in the shader code)

In your case I would suggest to do the following:

Store the 4 camera matrices in a Shader Storage Buffer (Array of mat4) to have them in the Vertex Shader
Use indexed drawing, for example :glDrawElementsInstanced
use the build in gl_InstanceID of the Vertex Shader to access the camera matrix array
set the build in variable output variable gl_ViewportIndex in the Fragment Shader to the gl_InstanceID. (for details see ARB_fragment_layer_viewport)


Importance Sampling of Environment Maps What is the best currently known and ideally also production-verified approach for sampling environment maps (EM) in a MIS-based uni-directional path tracer and similar types of renderers? I would prefer solutions which are reasonably complicated while reasonably functional to those which provide perfect sampling at cost of super complicated and hard-to-understand implementation.

What I know so far

There are some easy ways of sampling EMs. One can sample the needed hemisphere in a cosine-weighted manner,
   which ignores both the BSDF and the EM function shapes. As a result,
   it doesn't work for dynamic EMs:

To improve
   the sampling to a usable level, one can sample the luminance of the EM
   over the whole sphere. It is relatively easily implemented and the
   results are quite good. However, the sampling strategy is still
   ignoring the hemispherical visibility information and the cosine
   factor (and also the BSDF), resulting in high noise on the surfaces
   which are not directly lit by high-intensity areas of the EM:

Papers

I have found a few papers on the topic, but have not read them yet. Is any of these worth reading and implementing in a forward uni-directional path tracer, or is there something even better?

Structured Importance Sampling of Environment Maps (2003) by
Agarwal et al.
Steerable Importance Sampling (2007) by
Kartic Subr and Jim Arvo. They claim to present “...an algorithm for
efficient stratified importance sampling of environment maps that
generates samples in the positive hemi-sphere defined by local
orientation of arbitrary surfaces while accounting for cosine
weighting. “ The paper “Importance Sampling Spherical Harmonics”
comments on it: ”They create a triangulated representation of the
environment map and store the illumination premultiplied by each of
the first nine spherical harmonic basis functions at every vertex.
This forms a steerable basis where the clamped-cosine can be
efficiently rotated to any orientation.”
Practical Product Importance Sampling for Direct Illumination (2008) by
Petrik Clarberg and Tomas Akenine-Möller. An algorithm for sampling
the product of environment map lighting and surface reflectance. Uses
wavelet-based importance sampling.
Importance Sampling Spherical Harmonics (2009)
by Jarosz, Carr, and Jensenn. The abstract says: “...we present the
first practical method for importance sampling functions represented
as spherical harmonics (SH)...”
Tone-Mapped Mean-shift Based Environment Map Sampling (2015) by Feng
et al. This is pretty new and I have found neither a reference to it
nor the paper itself.

This is not a full answer, I would just like to share the knowledge I obtained by studying two of the papers mentioned in the question: Steerable Importance Sampling and Practical Product Importance Sampling for Direct Illumination.

Steerable Importance Sampling

In this paper they propose a method for sampling the product of the clamped cosine component and environment map lighting:

$$
L_{EM}\left(\omega_{i}\right)\left(\omega_{i}\cdot n\right)^+
$$

They make use of the fact that a piece-wise linear approximation of the product function can be relatively well expressed and partially pre-computed using the first nine spherical harmonic bases. They build this approximation on top of an adaptively triangulated EM and use it as an importance function for sampling.

They pre-compute and store approximation coefficients for each triangle vertex and also coefficients for computation of approximation integral over the triangle for each triangle. These coefficients are called vertex and triangle weights. Then they make use of the fact that is it possible to easily compute coefficients for an integral over a set of triangles just by summing the individual triangle weights without incorporating additional spherical harmonic bases. This allows them to build a balanced binary tree over the triangles where each node contains coefficients for computing approximation integral over the node's sub-tree triangles.

The sampling procedure consists of selecting a triangle and sampling its area:

A triangle is chosen by descending down the pre-built binary tree    with probability proportional to the sub-integral approximations. This costs $O\left(\log N_{\triangle}\right)$ on-the-fly computations of sub-integrals, each consisting of one inner product of clamped-cosine spherical harmonic coordinates with the pre-computed coefficients.
The chosen triangle surface is then sampled in $O\left(1\right)$ time in a    bi-linear fashion by a novel stratified sampling strategy proposed in    the paper.

To me, this looks like a promising technique, but the classical question with papers is how it will behave in the real life. On the one hand, there may be pathological cases when the EM is hard to approximate with triangulated piece-wise linear function, which can lead to an enormous amount of triangles and/or to poor sample quality. On the other hand, it can instantly provide a relatively good approximation of the whole EM contribution, which can be useful when sampling multiple light sources.

Practical Product Importance Sampling for Direct Illumination

In this paper they propose a method for sampling the product of environment map lighting and cosine-weighted surface reflectance:

$$
L_{EM}\left(\omega_{i}\right)f_{r}\left(\omega_{i},\omega_{o},n\right)\left(\omega_{i}\cdot n\right)^+
$$

The only pre-processing in this method is computation of a hierarchical representation of the EM (either mipmap or wavelet based). The rest is done on the fly during the sampling.

The sampling procedure:

Building an on-the-fly BRDF approximation: They first draw several BRDF importance samples and evaluate $f_{r}\left(\omega_{i},\omega_{o},n\right)\left(\omega_{i}\cdot n\right)^+$. From these values they build a quadtree-based piece-wise constant approximation of the BRDF, where each leaf of the tree contains exactly one sample.
Computing a product of the BRDF approximation and the EM: Multiplication is done at the BRDF quadtree leaves and averaged values are propagated to parents.
Product sampling: uniform samples are fed through the product tree using simple sample warping.

The procedure should generate relatively good samples at the cost of heavy pre-computation – they show that roughly 100–200 BRDF samples are needed for BRDF approximation to achieve the best sampling performance. This may make it suitable for purely direct illumination computations, where one generates many samples per shading point, but is most probably too expensive for global illumination algorithms (e.g. uni- or bi-directional path tracers), where you usually generate only a few samples per shading point.


How do I accurately compute coverage of overlapping analytical curves? Antialiasing of 2D shapes boils down to computing the fraction of a pixel that is covered by the shape. For simple non-overlapping shapes, this is not too difficult: clip the shape against the pixel rectangle and calculate the resulting shape's area. But it becomes more difficult if multiple shapes overlap the same pixel. Simply summing areas can cause the computed coverage to be too high, if it neglects the amount that one shape covers another shape. For example, see the Limitations section of this article on font rendering. You might also be in a situation where the two curves come from different objects with different colors (so it's not about the total coverage for the union of the two shapes, but the coverage of each one separately).

How would this be computed if you cared about complete accuracy? Even trickier, how do you compute coverage accurately for overlapping non-polygonal shapes like curves? Is there some point when you have no choice but to fall back to multisampling or stochastic techniques?

There is really no good way of doing this efficiently analytically for all corner cases. Most or all commercial 2D renderers that attempt to do analytic coverage calculation make predictable errors that multisampling methods do not.

A typical problem is two overlapping shapes that share the same edge. The common situation is that alpha channels sum up to a too thick alpha edge that aliases slightly. Or if shapes are differently colored the system confuses what color the background is. This is extremely annoying.

Image 1: The rendering engine confuses the coverage and makes a thin white outline where no outline should be.

Second perfect coverage amounts to box filtering. We can certainly do better. Considering that there are so many special corner cases that would require boolean operations on the shapes to do right, super sampling is still superior. In fact the coverage estimates may be used to concentrate sampling where it's most likely needed.

The situation could be simplified to polygons at sub pixel levels then the discrete analytical solution could be solved. But this at the expense of flexibility. For example its not out of the question that future vector systems might want to allow for variable width blurred lines which pose a problem for analytic solutions, as do other variably colored objects.

How to do it analytically

Image 2: Suppose you have this scene, exploded view on right

Now you can not just do this analytically, each piece separately and then merge the data. Because it results in wrong data. See alpha blending would let the blue shine trough the gaps if you did so.

What you have to so is split the scene up so that each shape eliminates what is under the other:

Image 3: You need to cut the underlying surfaces.

Now if everything is opaque then this is all straight forward. just calculate the area of each piece and multiply that by color and sum them together. Now you can use something like this.

This all breaks down if your individual shapes aren't opaque off course but even that can be done at some level.

Remember:

AA calculation need to be done in linear color space, and converted back to use space.


Can you generate your own HDRI maps without using photos? For example, preparing a scene in Maya using standard lights and rendering out a panorama?
Could they also be made from scratch in photoshop using 32bit color?
Is there a reason why people don’t seem to do this more often?
Cheers

Yes, it is possible to do this. If you use a tool like Photoshop in 32-bit per channel mode, any values less than 0 or greater than 1 should be usable as a high dynamic range values. I don't know that I agree with your contention that "people don't seem to do this". Given that the tools exist, they must be supporting some workflow.


How to rotate a camera? So I am doing a simple FPS camera with openGL. I store the camera as 4 vector, a position vector, a lookAt vector, an up vector and a right vector. When the user presses a key, I create a rotation matrix that rotates around the up vector 10 degree then multiply the three vectors that specify the orientation of the camera with it. With these new values I create a new view matrix from glm::lookAt. However, the result I get is very weird. When I press the button to rotate, the object the camera is initially pointing at dissapears, no matter how small I set the rotation. After pressing the rotate button several more time, it appears again, then if i press more it dissappears once more.
I feel like the code is not wrong, but my understanding of the math behind it and therefore the implementation is wrong. Can anyone explain to me this weird behavior?
Below is my code.

look = glm::vec3(glm::rotate(theta, axis) * glm::vec4(look, 1.0f)); // theta set at 2 degree
right = glm::vec3(glm::rotate(theta, axis) * glm::vec4(right, 1.0f));
up = glm::vec3(glm::rotate(theta, axis) * glm::vec4(up, 1.0f));
glm::mat4 cameraMat = glm::lookAt(eyePos, eyePos+camera.look, camera.up);

Promoting my comment into an answer since it identified the problem...

The issue is confusion between degrees and radians for the angle parameter. GLM, up to version 0.9.5, was very inconsistent in how it dealt with angles, accepting degrees for some functions and radians for others. This behaviour could be overridden with #define GLM_FORCE_RADIANS before including the header.

In version 0.9.6, radians everywhere became the default. Unfortunately, if you Google 'glm rotate' at the time of writing, the top result is the 0.9.4 doc page, which still describes the parameters as taking degrees, so you need to be aware of which version you are using and its default behaviour in this regard. If you still want to use degrees for your angle variables, you can convert them with glm::radians(angle) before passing them as arguments.


What is "Scanline Racing" I've heard a lot of people working on VR talk about scanline racing and that it's supposed  to help improve latency for motion-to-photon. However, it isn't clear to me how this can be done with OpenGL. Could someone explain how scanline racing works, and how it can be implemented on modern GPUs.

When your GPU displays a new frame on the screen, it transfers the image over the HDMI cable (or whatever kind) in a process called "scanout".  The pixels are sent out in linear order, usually left-to-right and top-to-bottom.  The process is timed so that it takes most of the duration of a refresh interval to do this.  For instance, at 60Hz, one frame is ~17 ms.  Each scanout will take probably around 15-16 ms, with 1-2 ms of vblank in between (the exact values vary according to the display and video mode).

Traditionally, rendering is double-buffered, which means there are two buffers stored in GPU memory: one that is currently being scanned out ("front buffer"), and one that is being rendered to ("back buffer").  Each frame, the two are swapped.  The GPU never renders to the same buffer that's being scanned out, which prevents artifacts due to potentially seeing parts of an incomplete frame.  However, a side effect of this is increased latency, since each frame may sit around in the buffer for several ms before it starts being scanned out.

VR is very latency-sensitive, so this isn't desirable. An alternative approach is to render directly to the front buffer, but time things out very carefully so that you have rendered each line of the image shortly before the scanout gets there. That's called "scanline racing" or "racing the beam" (the "beam" harkening back to the CRT days of yore). This more or less requires that you render the image in scanline order, i.e. the same order that the pixels get scanned out.  It doesn't literally have to be rendered one line at a time—it could be rendered in thin strips a few pixels high, but it does have to be done in order, as you can't go back and edit pixels that have already been scanned out.

There are a lot of disadvantages to this approach; it has very stringent performance requirements, has to be timed very carefully against vsync, and it greatly complicates the rendering process. But in principle it can shave milliseconds off your latency, which why VR folks are interested in it.


Techniques for making tesselated shapes appear smoother? What are some common techniques for making the edges on a tesselated shape less apparent without increasing the amount of tesselation which is actually carried out?

As an example, I followed along with this tutorial on tesselation shaders, and one can control the inner and outer tesselation levels. With relatively low levels of both, one can achieve a pretty good sphere. However, in order for the surface to actually appear smooth, a fairly bright light seems to be required.

This particular implementation uses triangular tesselation beginning from an icosahedron to approach a sphere.

My understanding is that performing the tesselation with quads would result in a smoother surface.

Here is a picture which illustrates how direct lighting makes it much harder to see the level of tesselation. On the top right of the sphere, where the light is hitting it strongly, no edges are visible, wheres on the bottom left, the edges can easily be seen. Perhaps in practice, simply applying a texture would mask many of the edges?

GL_SMOOTH interpolates the vertex attributes of the primitive (triangle), it looks like your normals are setup per face, rather than per vertex.

If using normal per face (i.e. a single normal for the triangle), increasing the number of triangles will produce a less faceted look as there is more granularity when interpolating the normals over the surface of a given surface area given the increase in the number of triangles within that area. It is recommended to use normals per vertex for smooth surfaces when feature edges are not important (i.e. Not for cubes!).

If using normal per vertex (i.e. a normal for each vertex, resulting in each triangle having 3 vertices), each 3 vertices of a face will be slightly different if the neighbouring triangles are not coplanar to the triangle in question (i.e. not a flat surface). This will aid in the smoothness of the shading.

Normals per vertex can be easily calculated by averaging the three normals of the three vertices defining a triangle, however your surface needs to be defined with shared vertices for this. The exception to this is if you have a sphere or ellipsoid, in which case you can calculate a more precise normal easily by unitising vertex - sphereOrigin rather than averaging the three normals of the face.

On a side note: Are you using two lights in the scene of the screen shot you posted or one? If two it looks like the normals are currently not correct as the shading does not appear correct since there is a well-lit area of the surface on the bottom left region. With a single light, either the front (top right) of the sphere would be lit, or the bottom left, but not both.

Also note that simply increasing the power of the light simply over exposes the surface colour rather than improving the smoothing. You lose the surface definition.


What would be an example of decoding-intensive video? my question might come in a bit weird but I'm looking for something that would be considered very CPU-intensive video to decode (for playback I mean). I would like to have some sample of 1080p and 4k videos that would classify to see if my CPU can handle it.

Sorry if this is a bit of off-topic but I'm not sure where else on the internet to ask.

Backstory to prevent XY-problem: HW-accelerated video decoding on my GPU is not working and I'm trying to find if it actually is a problem or if my CPU can handle it fine.

You could try to play 1080p and 2160p videos, possibly 60fps in YouTube. If you right-click on the playback window and click on "Stats for nerds" you will get more information about used video and audio codecs and dropped frames, which can indicate that your hardware may be too slow. Currently the videos are mostly encoded as VP9 codec, but you can change settings to prefer AV1 codec, at https://www.youtube.com/account_playback. However please note that not all videos are available as AV1, but you can find some videos at AV1 Beta Launch Playlist.


Splitting of NURBS curves Splitting Bezier curve into two parts at some parameter t is easy thanks to De Casteljau's algorithm.

Is there a similar algorithm for NURBS curves? How to split a NURBS curve?

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

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

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

The number of knots in the knot vector is:

numKnots = degreeOfCurve + numControlPoints + 1

or if you prefer:

numKnots = orderOfCurve + numControlPoints

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

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

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

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

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

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

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

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


Can I use several GPUs for a grid multi screen image? Is it realistic to render a super-high resolution image over an array of 3 by 3 or 5 by 5 (for example) stacked screens? Could I do this by combining several different GPUs, or would the only way be to use a GPU per screen and simply divide the image to be rendered?

Ideally I'd like to be able to use fewer GPUs than screens. Even though one GPU is insufficient I'm hoping I won't need n GPUs for n screens.

If this is possible I'd also need to know whether this requires using the same make and model of GPU or whether unrelated ones could still share processing.

Yes, it's certainly possible to do this kind of thing.  First of all, you can typically connect 3 or 4 displays to each GPU, and (with an appropriate motherboard) you can have up to 4 GPUs per machine.  That would give you 16 screens.  With multiple machines, you could have even more.

Rendering to multiple displays from a single GPU is no big deal.  You can create a single window that stretches across all the displays, render to it, and it should "just work".

Rendering the same scene on multiple GPUs is a bit trickier.  One way is to create a separate rendering context on each GPU, and essentially repeat all the rendering—re-upload all buffers and textures to each GPU, and re-submit the draw calls to each one every frame.  Another possibility is to use the built-in multi-GPU support in DX12, which allows you to manage several GPUs in one rendering context.


Is it possible to send Texture Buffer to shader dynamically? I want to send a series of integer to the geometry shader,
while the data will be modified every frame.
But when I try to retrive the sampleBuffer in geometry shader, it seems to keep output zero.
Am I using Texture Buffer wrong, or the TBO itself just can't be used as GL_DYNAMIC_DRAW?
Init Texture Buffer
void InitialTBO() {
    int index_tbo_reserved_size = 5000;
    glGenBuffers(1, &index_tbo);
    glBindBuffer(GL_TEXTURE_BUFFER, index_tbo);
    glBufferData(GL_TEXTURE_BUFFER, index_tbo_reserved_size * sizeof(GLint), NULL, GL_DYNAMIC_DRAW);
    glGenTextures(1, &index_tbo_tex);
}

Render
void RenderChunkDataCone(Primitive* primitive) {
    Program* shaders = primitive->shaders;

    shaders->use();

    glActiveTexture(GL_TEXTURE0);
    glBindBuffer(GL_TEXTURE_BUFFER, this->index_tbo);
    glBufferSubData(GL_TEXTURE_BUFFER, 0, sizeof(GLint)*index_tbo_data.size(), index_tbo_data.data());
    glBindTexture(GL_TEXTURE_BUFFER, this->index_tbo_tex);
    glTexBuffer(GL_TEXTURE_BUFFER, GL_R32I, this->index_tbo);
    shaders->setUniform("index_tex", 0);

    glBindVertexArray(primitive->vao);
    glDrawElements(primitive->drawType, primitive->drawCount * primitive->drawCount_Inner, GL_UNSIGNED_INT, 0);

    glBindVertexArray(0);
    shaders->stopUsing();
}

Geometry Shader
#version 460 core
uniform samplerBuffer index_tex;
vec3 render_primitive(vec3 position){
    int status = int(texelFetch(index_tex, 0).r);
    if(status==0)
        return vec3(0,10,10);
    else if(status==1)
        return vec3(10,0,0);
    else if(status==2)
        return vec3(0,0,10);
}

void main() {
    vec4 position =gl_in[0].gl_Position;
    vec3 returnedValue = render_primitive(position.xyz);
}

I've confirmed the index_tbo[0] is 1,
But the returnedValue outputed by shader will always be (0,10,10) as the value index_tex[0] received seems to be 0.

These:

glTexBuffer(GL_TEXTURE_BUFFER, GL_R32I, this->index_tbo);

uniform samplerBuffer index_tex;

Do not match. If the texture is a signed integer texture, then the sampler type needs to match. It should be isamplerBuffer, and you won't need to do the cast.


How do shaped lights work? I know how to program directional lights, point lights and spot lights.  Sometimes though, people have lights that are shaped - like bars, or even a torus.

How does that work from either a ray based or rasterization perspective?

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

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


Volume Rendering in simple words I am looking for a explanation about volume rendering in simple words, a step by step kind of, like ray tracing:

  for every pixel in the screen plane, trace a ray starting from the eye
  point to the screen pixel location, a compute the nearest objet
  intersection in the scene, calculate the pixel color, and so on.

something like that

Volume rendering is not like ray-tracing, it is like "scene rendering". i.e. there exists several algorithms to render volumes.

One close to ray-tracing is ray-marching, and has may variants. The simplest:
for every pixel in the screen plane, trace a ray starting from the eye point to the screen pixel location, and advance along the ray by constant steps. At each voxel calculate the pixel color and transparency, blend it to the pixel value, and so on.

Blend =

$C_{pix} += T_{pix}*C_{vox}*(1-T_{vox})$
$T_{pix} *= T_{vox}$

with $C_{vox},T_{vox}$ the color and transparency of the current voxel, and $C_{pix},T_{pix}$ the cumulated color and transparency of the pixel.


Is there something wrong with a column camera matrix? I am writing a simple ray tracer. I was working on my camera matrix when I encountered a problem. When I changed the look vector, so that it headed down, the image, which was supposed to go up, actually went down as well. Likewise, if I changed the look vector so that it headed up, the image went with it.
I understand that the camera matrix's job is to change world coordinate into eye coordinate. Since I am using column matrices, here's my camera matrix, with $r$ being right vector, $l$ being lookAt vector and $u$ being up vector

$$
\begin{bmatrix}
r_x & u_x & -l_x & 0 \\
r_y & u_y & -l_y & 0 \\
r_z & u_z & -l_z & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
$$

This is the transpose of the gluLookAt matrix of openGL. I dont understand why openGL use their matrix though, since they are also using column matrices.

What you have there is the matrix that goes from eye space (camera space) to world space. You can see this by observing that, for instance, if you apply this matrix to the column vector $[1, 0, 0, 0]^T$, which is the right-vector in eye space, then it will return $[r_x, r_y, r_z, 0]^T$, the right-vector in world space.

You want the matrix that transforms the other direction, which would be the inverse of this one. And assuming $r, u, l$ form an orthonormal basis, the inverse will simply be the transpose.


Convex non simple polygon? Existence question: Can there exist a convex polygon witch is not a simple polygon?

For a polygon to be convex the outside angle of the polygon has to be more than or equal to 180 degrees. Now at intersection of 2 lines the outermost angle has to be less than 180 degrees for the lines to intersect between the endpoints.

Now the answer to this question depends on how you define what is inside of the polygon. If you consider some a even odd filling rule then the answer is No such shape exists. But if you consider only the outermost curve to do filling then yes, its possible if you intersect at the endpoint of a line. But to me this sounds more like splitting hairs as that shape reduces to a simple polygon.


Projective texturing from many images Problem: I'm trying to dynamically texture a mesh of the real world generated by the Hololens over time using photos also captured from the Hololens, perhaps one photo per second. Each of the photos includes positional information of the Hololens from the time when the photo was taken, which allows me to project the images onto the existing mesh and figure out the UV mapping for each image.

In case of a single image, this seems fairly simple, as it is just standard projective texturing of the mesh. But I will be capturing a potentially endless stream of images over a span of time which will be taken from different positions and orientations. For acceptable performance, I cannot simply store and iterate through all photos and do projective texturing for each.

How can I perhaps generate a texture atlas & accompanying UV mapping for the real world mesh and update it after each image?

Apologies in advance for the poor quality of this answer, but this sounds a little like what an ex-colleague was doing as part of his PhD. The "Free-Viewpoint video" papers listed at the bottom of https://www.researchgate.net/profile/James_Imber might be useful, or at least a starting point to find related work.


How to build a decent lens/camera objective model for path tracing? I have written a small path-tracer after learning and experimenting on smallpt.

The only thing that I did not write (and understood) myself is how the initial rays are computed and fired from the camera. I got the principle right, but I'm looking for some resources describing how to:

Compute the initial direction of rays
Modelize a real lens (as opposed to pinhole camera), supposedly allowing effects like depth of field ?

State of the art maths and physics are not required, but OK if explained thoroughly.

The next step up from a pinhole camera model is a thin lens model, where we model the lens as being an infinitely thin disc. This is still an idealization that pretty far from modeling a real camera, but it will give you basic depth of field effects.

The image above, from panohelp.com, shows the basic idea. For each point on the image, there are multiple rays arriving at that image point, via every point on the 2D lens surface. Therefore, generating an image like this using Monte Carlo will require picking, for each ray, both a 2D sample point on the image plane and an independent 2D sample point on the lens surface.

The user-facing parameters to set will be the lens radius (as a physical radius in scene units), which controls how shallow the focus range is (larger lens = shallower focus range), and the distance at which you want objects to be in focus.

To generate eye rays into the scene, you can calculate the position and direction of rays leaving the lens surface; in this model there's no need to explicitly simulate the image plane and the refraction through the lens.  Basically, think of the lens as centered at the camera position and oriented to face the camera direction.

Based on the image location, construct a ray from the camera position (lens center) into the scene, just as you would in the pinhole model; then find its intersection with the focal plane. That's where all the rays from that image location should converge.  Now you can offset the starting point of the ray to a randomly chosen point on the lens, and set its direction to be toward the convergence point.

You can generalize this a bit by allowing the focal plane to be something other than a plane, or the lens to be something other than a circular disc, and following the same process. That can produce some interesting if not-quite-physical effects.  It's also possible to go beyond this simple model with a more physically realistic simulation of a camera's lens elements—but that's beyond my expertise.


Can pixels on the image plane be mapped to world space coordinates? I'm trying to learn the fundamentals of 3d computer graphics by writing a toy framework in WebGL.

I'm currently working on mouse based camera controls. There are plenty of good resources in the ACM SIGGRAPH library to be found, but there are some aspects of this area that I can't find answers to.

A lot of orbit controls simply use the origin as the pivot point, but other implementations can orbit around any arbitrary point in a scene and the camera stays 'still'. I'm trying to implement the latter.

It seems that a good way to do this would be to simply get the cross product of the two vectors made by the pivot point and 3d coords of the corresponding pixels on the image plane, but I can't anything like this approach anywhere which leads me to believe I've misunderstood some fundamental aspect of image projection/image planes.

Is the image plane an abstract construct that doesn't really have 3d coords or can pixels in the image plane actually be mapped to world coords?

What you are asking about is 'mouse picking'. If a user clicks a pixel on the screen how can you get corresponding world space coordinates of an object being clicked on.
Imagine a ray from that pixel, through the view volume all the way to the far plane. That ray is a set of all possible points the user is clicking on. So we want to perform ray/poly ntersections with every object in the scene, and return the first intersect.

To transform the pixel into world space, you first have to turn your x,y point in screen space into NDC coordinates (-1 to 1) use -1 for your Z component and 1 for W to create a 4 float component vector and then multiply that vector by the inverse projection and then inverse view matrices.
There are many examples of this process if you want to see code, but this is the basic process.
Now we have a ray from the camera/eye position into the scene, we want to do intersection tests with our objects. There are many ways of achieving this, take your pick.

Hope this helps, good luck!


How are normals assigned to vertices in different types of shading? I'm new to this forum and topic but wanted to figure out specifically how are normals assigned to vertices in flat shading, gouraud shading, and phong shading?

Is there a difference between any?

Flat shading uses the same normal for each vertex of the triangle. In this case the normal is constant, and one color is evaluated for the triangle.

For Gouraud and Phong shading normals are different per vertex and can represent a curved surface (even though the face is flat).

However, for Gouraud shading is evaluated per vertex, and the resulting color is interpolated. For Phong, the normals are interpolated first and the shading is evaluated per pixel.

Also note there's a bit of an overloaded term between the Phong Lighting/Reflection model and Phong Interpolation, Per-pixel shading which is what you're referring to here.

Given these 3 shading types, the next logical step is actually normal maps shading. This is basically where the normal is provided per pixel, and shading is evaluated per pixel.

And so you have the trend of doing more calculation at finer details / higher resolution.

Here's a table!

                 Normal         |   Lighting
Flat:            Per Triangle   |   Per Triangle
Gouraud:         Per Vertex     |   Per Vertex
Phong:           Per Vertex     |   Per Pixel
Normal Mapping:  Per Pixel      |   Per Pixel


Dark stripes on surfaces in V-Ray when rendering to texture (baking) I am working in 3DS Max with V-Ray 3.4. I have recently been encountering strange artifacts on baked textures.  Surfaces that should be flat smooth objects render with dark stripes or other unusual patterns, usually geometric.  The objects affected appear to be random.  One will bake just fine and another that is an instance of the first has these stripes.  And once an object starts baking like this there is no going back.  The only solution appears to be to remodel it from scratch (and that is not guaranteed to work either).  And this behavior only occurs when baking.  Normal rendering works just fine.

Things I have tested for and ruled out:

Co-Planar surfaces
bad UVW mapping (Tried automatic and manually unwrapping - no effect)
bad material
lighting problems
bad normals
and I've tested on multiple machines with the same results

Below is an image of what I'm talking about.  The large square surface should be more or less smooth and evenly lit, but instead, there is a strange dark rectangle.

Solved.  The issue was with V-Ray's global ambient occlusion on the GI tab.  Once that was shut off everything renders fine.  Interestingly, V-RayDirt maps in materials seem to be behaving just fine.

UPDATE: It appears the real root problem is deeper.  This turned out to be caused by units being set to fractions instead of decimals.  This can cause some values that are very small to round off to zero as the system tries to make it a fraction.  In v-ray lights, the shadow bias was getting rounded to zero automatically in some cases.  A zero shadow bias can produce strange results in some cases.  SOLUTION: stop using fractional units and go through and fix lights with zero bias.


How is a light probe different than an environmental cube map? Looking at a light probe texture, it looks like a blurry environment map.

What's the difference between the two, how is a light probe made, and what is the benefit of it being blurry?

There are two different common meanings of "light probe" that I'm aware of. Both of them represent the light around a single point in a scene, i.e. what you would see around you in all directions if you were shrunk down to a tiny size and stood at that point.

One meaning is a spherical harmonic representation of the light around a point.  Spherical harmonics are a collection of functions defined over a spherical domain, which are analogous to sine waves that oscillate a certain number of times around the equator and from pole to pole on the sphere.

Spherical harmonics can be used to create a smooth, low-res approximation of any spherical function, by scaling and adding together some number of spherical harmonics—usually 4 (known as linear, first-degree, or one-band SH) or 9 (called quadratic, second-degree, or two-band SH). This is very compact because you only have to store the scaling factors. For instance, for quadratic SH with RGB data, you only need 9*3 = 27 values per probe. So SH makes a very compact, but also necessarily very soft and blurry, representation of the light around a point. This is suitable for diffuse lighting, and perhaps specular with a high roughness.

This screenshot from Simon's Tech Blog shows an array of SH light probes spaced throughout a scene, each one showing the indirect lighting received at that point:

The other currently common meaning of "light probe" is an environment cube-map whose mip levels have been pre-blurred to different extends so it can be used for specular lighting with varying levels of roughness. This image from Seb Lagarde's blog shows the basic idea:

The higher-resolution mips (toward the left) are used for highly polished surfaces where you need a detailed reflected image. Toward the right, the lower-res mip levels are increasingly blurred, and are used for reflections from rougher surfaces. In a shader, when sampling this cubemap, you can calculate your requested mip level based on the material roughness, and take advantage of the trilinear filtering hardware.

Both of these types of light probes are used in real-time graphics to approximate indirect lighting. While direct lighting can be calculated in real-time (or at least approximated well for area lights), indirect lighting is usually still baked in an offline preprocess due to its complexity and computational overhead.

Traditionally, the result of the baking process would be lightmaps, but lightmaps only work for diffuse lighting on static geometry, and they take up a lot of memory besides. Baking a bunch of SH light probes (you can afford a lot of them because they're very compact), plus a sparser sprinkling of cubemap light probes, allows you to get decent diffuse and specular indirect lighting on both static and dynamic objects. They're a popular option in games today.


If I have more than enough memory, can it still be beneficial to use compressed textures? I'm wondering whether some of you would have tested and seen quite a difference in using a compressed texture even when the OpenGL environment does not need saving any memory (i.e. the card has more memory than necessary to support the textures uncompressed.)

I'm thinking that a compressed texture would use less RAM and thus reading it and decompressing in the GPU would be faster because the number of memory accesses is lower. Whereas, a non-compressed texture would rely more on memory access (GPU I/O) than processing and that is likely slower.

The main things I've read about texture compression has been about how the compression saves space. Not so much about how it can save execution time with the GPU. (Note that I specifically will be using an nVidia, Pascal for now. But I would hope that it works similarly whatever the GPU.)

Because memory bandwidth is not free.

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

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

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

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


Writing OpenCL Shaders I want to write (fragment) shaders in OpenCL rather than GLSL. Is there a standard mechanism for this (from OpenGL, and ideally also from DirectX)? Are there any drawbacks to doing this?

I also want to write screenspace effects in OpenCL. Is the mechanism the same? Are there any drawbacks?

Thanks

OpenCL isn't really a drawing API, it's designed for doing compute workloads across different devices, not necessarily GPUs. You can certainly write a kernel that renders to a texture in OpenCL, and have this texture be available to Open GL or D3D. AFAIK, though, you wouldn't have access to the fixed-function hardware like rasterization, attribute interpolation, and fragment blending, so you'd have to implement it yourself (unless you're writing a ray tracer). You'd also likely have to use one of the drawing APIs to present your texture to the screen, by rasterizing a full screen quad and sampling your texture at each pixel. This carries a synchronization penalty - although OpenGL and D3D can interoperate with OpenCL, they can't access the same memory at the same time, so you need to wait for control to transfer from one API to the other.

Using compute on an already rendered buffer for screenspace effects is a good idea, since you save the fillrate of rasterizing a full screen quad every time you apply a new effect compared to the fragment shader approach. These days though, OpenGL and D3D have compute shaders built-in to handle this kind of use case. Why do you want to use OpenCL exactly? Seems to me you'd be better off using one of the rendering APIs.


Dealing with interpolated normals within a raytracer I am trying to render a teapot within a simple raytracing that can handle reflection, refraction, and shadowing from point and directional lights.

I am very confused about one detail of the raytracer and that is the interpolated normals. This question was brought on when my raytracer rendered this image:

Now there are more than a couple issues with this render however it did bring up an important point. Not using interpolated normals causes blocking reflections like this.

I had previously figured that I should not use interpolated normals when calculating reflection or refraction rays. I had previously figured that I should not do it because that might introduce edge cases as reflecting off an interpolated normal would have the ray bouncing off the wrong position since I am shading it like its smooth.

I also feel like this might introduce edge cases when it comes time to implement accelerating spatial data structures.

So I guess my question is where should/shouldn't I be using interpolated normals in my ray-tracer.

I am betting there is a different protocol if you are rendering a feature animated film vs just creating a toy/lightweight/quick raytracer. I would love to know the answer for both.

Disclaimer: It's been a long time since I looked at this sort of thing but here goes...
Disclaimer2: On re-reading your question(s) I realised I might have misunderstood what you were asking. I'll leave this here just in case you were looking for this sort of reply.

Are you rendering from the original Bezier patch definition (e.g. https://www.cs.utah.edu/gdc/projects/alpha1/help/man/html/model_repo/model_teapot/teapot.pts)  or from a (post tessellation) triangle representation?

If the former, then you should, in the vast majority of cases, be able to 'trivially' generate the normals directly from the Bezier representation, by computing surface partial derivatives at each ray intersection point, to give tangent vectors, and computing the cross product. The cases you do have to watch out for are at very centres of the bottom and top of the teapot where the patches, though geometrically well-defined, have a zero partial derivative because the rectangular patch has been squeezed into a triangle, e.g. control points for U,V = (0,0), (0,1/3), (0,2/3), (0,1) are all identical, so dPos/dv is 0.  All you need do is compute dPos/du at (0,0) and (0,1) to get valid tangents.

If you are rendering from triangles, I assume you already have normals at the triangle vertices. If you use an appropriate ray-triangle intersection test you can get the barycentric coordinates of the intersection point. Use these to blend the vertex normals (and after renormalising) you'll have a 'reasonable' surface normal (though it will only be C0 continuous).


The mathematics of two dimensional interpolation on a quad I am trying to wrap my head around how exactly the GPU interpolates texture coords on a quad. I realize to the GPU a quad is two triangles but I find thinking in terms of the whole quad to be easiest.

If we define texture space as the texture coordinates from X:Y{0-1} and world space as the actual coordinates of the quad how can I given a point p1 that is on the quad figure out what its texture coordinate would be? Given a texture coordinate point p2 how would I figure out its real world coordinates?

Keep in mind that the quad can be any quadrilateral not necessarily always a parallelogram.

As an extra note lets define the texture coordinates on the quad so that they are as such

(It actually is easier to think (and compute) about this with triangles, but for the sake of the answer, let's first stick to your quad example.)

For this you just have to define the point you're interested in in terms of the quad's (or whatever primitive's) vertices. This is called a barycentric coordinate system. More practically-speaking, you basically give the point $n$ weights, each describing the influence the $i$th vertex of the quad has on the point. Those are the point's barycentric coordinates with respect to that quad.

So for example the center point of the quad (or "center of mass") would have the weights $\frac{1}{4}$, $\frac{1}{4}$, $\frac{1}{4}$, and $\frac{1}{4}$. A point in the middle of the left edge would have a weight of $\frac{1}{2}$ for the left two vertices each and a weight of $0$ for the right two vertices. (Notice how they always sum to $1$?)

These barycentric coordinates can then be used to interpolate whatever kind of per-vertex values you want, be that positions or texture coordinates. It all reduces to a simple weighted sum. And even more than that, they can also be quite easily computed by simple vector algebra from any existing per-vertex values if you have the point's values given (comes down to just a few little 2x2 determinants for a triangle, or similarly easy computation). This means if you know a pixel's screen space position and those of the vertices, you can compute its barycentric coordinates. These you can then use to interpolate the pixel's texture coordinates (or normal, or whatever) from the per-vertex values, or vice versa.

So much to the theory, there's a few practical considerations to keep in mind, especially when using them for interpolation in a rasterizer, like GPUs do.

For anything but triangles the barycentric coordinates don't necessarily have to be uniquely defined for any arbitrary point. That's why thinking about triangles is much easier, especially for the computer.
Due to the fact that they are negative if and only if the point doesn't actually lie inside the triangle they can also be used for checking if the point belongs to the triangle at all and thus are more or less a by-product of the pixel-in-triangle test that the rasterizer already performs to, well, rasterize the triangle.
When it comes to interpolation in projected space, i.e. when projecting a 3D world onto the plane using perspective distortion, it becomes a little more involved since you have to account for the fact that a line's length in screen space is not the same as its length in world space, or more precisely its screen space length doesn't increase linearly when going along a triangle edge in world space. The keyword here is perspective correct interpolation. But this still uses the point's barycentric coordinates.
Of course in an actual rasterizer you also have to take account for shared triangle edges and only rasterize a shared edge once, which requires special rules as to which triangle a shared edge belongs and might make the computation of barycentric coordinates a little more complicated, together with using fixed-point coordinates or whatever optimized computations.

(This is a more general overview of the matter and how it generally works. For specific mathematical as well as technical details, I'd advise for further reading, maybe starting with the above Wikipedia articles.)