Distorted OpenGL graphics in certain models of Intel GPUs under Windows; possible causes? I'm not sure this is the best place to post this, but it definitely seemed more appropriate than programming. I'm one of the developers of Performous, essentially a karaoke (and instruments) game. We use mostly 2D graphics in OpenGL, I don't think anything particularly strange.

On most machines, everything works perfectly. There's a subset of Intel iGPUs (from what I've been able to ascertain, certain models ranging from around the Ivy Bridge generation to somewhere around Broadwell) that render incredibly distorted, on Windows machines. I've seen it happen on Windows 7 and 10 (presumably it also does on Win8)... never in Linux or OSX, I attempted to reproduce it on a mac mini (that should have been affected) running bootcamp, and was unable to.

P.S. If you want to see the code, it's on github at https://github.com/performous/performous

Relevant files most likely would be (under game/) video_driver.cc/hh, surface.cc/hh, glutil.cc/hh, glshader.cc/hh and the actual shaders that live in data/shaders

Edit: actual drawing call,

void VertexArray::draw(GLint mode) {
    GLErrorChecker glerror("VertexArray::draw");
    if (empty()) return;
    unsigned stride = sizeof(VertexInfo);
    GLint program;
    glGetIntegerv(GL_CURRENT_PROGRAM, &program);
    GLint vertPos = glGetAttribLocation(program, "vertPos");
    GLint vertTexCoord = glGetAttribLocation(program, "vertTexCoord");
    GLint vertNormal = glGetAttribLocation(program, "vertNormal");
    GLint vertColor = glGetAttribLocation(program, "vertColor");
    glerror.check("program and attribs");
    glBindVertexArray(m_vao);
    glBindBuffer(GL_ARRAY_BUFFER, m_vbo);
    glBufferData(GL_ARRAY_BUFFER, sizeof(VertexInfo) * size(), &m_vertices.front(), GL_STATIC_DRAW);
    glerror.check("bind");
    if (vertPos != -1) {
        glEnableVertexAttribArray(vertPos);
        const GLvoid* ptr = m_vbo ? (GLvoid*)offsetof(VertexInfo, position) : &m_vertices[0].position;
        glVertexAttribPointer(vertPos, 3, GL_FLOAT, GL_FALSE, stride, ptr);
    }
    if (vertTexCoord != -1) {
        const GLvoid* ptr = m_vbo ? (GLvoid*)offsetof(VertexInfo, texCoord) : &m_vertices[0].texCoord;
        glEnableVertexAttribArray(vertTexCoord);
        glVertexAttribPointer(vertTexCoord, 2, GL_FLOAT, GL_FALSE, stride, ptr);
    }
    if (vertNormal != -1) {
        const GLvoid* ptr = m_vbo ? (GLvoid*)offsetof(VertexInfo, normal) : &m_vertices[0].normal;
        glEnableVertexAttribArray(vertNormal);
        glVertexAttribPointer(vertNormal, 3, GL_FLOAT, GL_FALSE, stride, ptr);
    }
    if (vertColor != -1) {
        const GLvoid* ptr = m_vbo ? (GLvoid*)offsetof(VertexInfo, color) : &m_vertices[0].color;
        glEnableVertexAttribArray(vertColor);
        glVertexAttribPointer(vertColor, 4, GL_FLOAT, GL_FALSE, stride, ptr);
    }
    glerror.check("enable arrays");
    glDrawArrays(mode, 0, size());

    if (vertPos != -1) glDisableVertexAttribArray(vertPos);
    if (vertTexCoord != -1) glDisableVertexAttribArray(vertTexCoord);
    if (vertNormal != -1) glDisableVertexAttribArray(vertNormal);
    if (vertColor != -1) glDisableVertexAttribArray(vertColor);
    if (m_vbo) glBindBuffer(GL_ARRAY_BUFFER, 0);
    glBindVertexArray(0);
}

Client-side vertex struct:

struct VertexInfo {
    glmath::vec3 position{};
    glmath::vec2 texCoord{};
    glmath::vec3 normal{};
    glmath::vec4 color{ 1.0, 1.0, 1.0, 1.0 };
};

As mentioned on a comment, after talking about it on IRC, they helped me realize the bug was in the geometry shader that was being used for Stereo 3D.

Due to the way it was conceived (which was apparently a really bad idea), the shader was always compiled and linked if the hardware reported supporting OpenGL3.30 and GL_arb_viewport_array.

When the stereo3d option was disabled, via a very hacky solution, the shader was put into a "pass-through" mode which is supposed to do nothing but (still not sure if it's a bug in the shader itself or a hardware/driver issue) it was sending a lot of undefined values to the fragment shader, instead.

Here's the offending code:

#version 330 core
#extension GL_ARB_viewport_array : require

uniform float sepFactor;
uniform float z0;

layout(triangles) in;
layout(triangle_strip, max_vertices = 6) out;

struct vData {
    vec3 lightDir;
    vec2 texCoord;
    vec3 normal;
    vec4 color;
};

in vData vertex[];
out vData fragv;

void passthru(int i) {
    gl_Position = gl_in[i].gl_Position;
    fragv = vertex[i];
}

// Process all the vertices, applying code to them before emitting (do-while to convince Nvidia of the code getting executed)
#define PROCESS(code) i = 0; do { passthru(i); code; EmitVertex(); } while (++i < 3); EndPrimitive();

void main() {
    int i = 0;
    if (sepFactor == 0.0) {
        gl_ViewportIndex = 0; PROCESS(;); // No stereo
    } else {
        gl_ViewportIndex = 1; PROCESS(gl_Position.x -= sepFactor * (gl_Position.z - z0));  // Left eye
        gl_ViewportIndex = 2; PROCESS(gl_Position.x += sepFactor * (gl_Position.z - z0));  // Right eye
    }
}

I have sort-of solved it by actually recompiling and relinking the shaders to include the geometry shader or not when stereo3d is toggled.

I've also rewritten the shader to look like this (it still produces skewed geometry but atleast akin to the first screenshot, instead of the second),

#version 330 core
#extension GL_ARB_viewport_array : require

uniform highp float sepFactor;
uniform highp float z0;

layout(triangles) in;
layout(triangle_strip, max_vertices = 6) out;

in vData {
    highp vec3 lightDir;
    highp vec2 texCoord;
    highp vec3 normal;
    highp vec4 color;
} vertices[];

out vData {
    highp vec3 lightDir;
    highp vec2 texCoord;
    highp vec3 normal;
    highp vec4 color;
} fragv;

void passthru(int vp, int i) {
        gl_Position = gl_in[i].gl_Position;
        gl_ViewportIndex = (sepFactor == 0.0) ? 0 : vp;
        gl_Position.x -= (sepFactor * (gl_Position.z - z0));
        fragv.lightDir = vertices[i].lightDir;
        fragv.texCoord = vertices[i].texCoord;
        fragv.normal = vertices[i].normal;
        fragv.color = vertices[i].color;
}

void main() {
        // Render the left eye
    int i = 0;
    do {
        passthru(1, i);
        gl_Position.x -= (sepFactor * (gl_Position.z - z0));
        EmitVertex();
        } while (++i < 3);
        EndPrimitive();

    i = 0;
        // Render the right eye
    do {
        passthru(2, i);
        gl_Position.x += (sepFactor * (gl_Position.z - z0));
        EmitVertex();
        } while (++i < 3);
        EndPrimitive();
}

In order to provide a more complete answer, in case somebody faces the same issue: I finally realized the issue appears to be with the way the loop was written. For some reason, not defining i in the loop itself resulted in trying to access undefined members of vertices

Rewriting as follows fixed the issue:

for (int i=0; i < gl_in.length(); i++) {
    passthru(1, i);
    gl_Position = gl_in[i].gl_Position;
    gl_Position.x -= (sepFactor * (gl_in[i].gl_Position.z - z0));
    EmitVertex();
}


How is the multiplication in Gaussian Blur implemented I have a question regarding how the Gaussian blur works. A pixel consists on the combination of 3 colors: R,G and B. I have read that the Gaussian kernel is multiplied by the input image
by placing the center pixel of the kernel on the image pixel and multiplying the values in the original image with the pixels in the kernel that overlap. What I am not sure about is how the multiplication is carried out. For instance, lets suppose the pixel is composed as follows(I have chosen arbitrary numbers):
R: 10100010
G: 01000110
B: 10001110
My question is how the multiplication implemented:
1- The three colors are "concatenated" meaning that the value in the kernel is multiplied by the concatenation of R,G and B. In this case the concatenation would be 10100010 01000110 10001110
2- Multiply the value of each color independently by the kernel. This would imply multiplying first R by the kernel, then G by the kernel and then B by the kernel.

Each color is conceptually treated independently. If they were concatenated, multiplying a value with a color close to the maximum possible value for one channel could cause it to overflow into the lower bits of the next.
That said, if you’re asking for performance purposes, a lot of the hardware that does this kind of work can perform all of the per-channel multiplies in a single operation.


How can I resize a rendered ray traced image? Say I have rendered an HDR ray traced image with dimensions 1920x1080 (width x height) pixels and I want to instead represent it with dimensions 960x540. Assume as well that the image has not yet been gamma corrected (i.e. it is still in linear space). How should I go about downsampling the image such that I don't need to re-render the image in the new dimensions?

Since you want to downsample the image by a factor of 2 along each axis, a simple and easy thing to do is just average a 2×2 box of source pixels to generate each destination pixel. In pseudocode this would look like:

for dest_y = 0 to 540
    src_y = dest_y*2
    for dest_x = 0 to 960
        src_x = dest_x*2
        average = 0.25 * (src[src_y][src_x] + src[src_y][src_x+1] +
                          src[src_y+1][src_x] + src[src_y+1][src_x+1])
        dest[dest_y][dest_x] = average

This will do an okay job, but for higher-quality downsampling or resizing images to any size (not just neat integer factors), I suggest looking at the stb_image_resize library. It's quite easy to use, supports either 8-bit or floating-point images with any number of channels, and gives good results.


Intrepret path/light tracing by rewriting light transport equation Given the rendering equation:

$$
L_o(x, \theta_o) = L_e(x, \theta_o) + \int_{\Omega} \! f(x,\theta_i,\theta_o) L_i(x,\theta_i) \cos(\theta_i, \theta_o) \, \mathrm{d} \theta_i.
$$

Rewriting it using linear operator $F$, as:

$$
L_o = L_e + F \circ L_i.
$$

Consider the final state that $L = L_o = L_i$, then there are two ways to rewrite and interpret:

(1) (light tracing?)
$$
L_e = (I - F) \circ L.
$$

(2) (path tracing?)
$$
L = (I + F + F^2 + F^3 + \cdots ) \circ L_e.
$$

Questions

Are the two classifications the correct intrepretation?
Thinking about (2) as path tracing is easy, in that rays starting from $L$ go through multiple bounces and finally reaching $L_e$; while thinking of (1) as light tracing is difficult for me. Are there any intuitive explanations for both?

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

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

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

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

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

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


How is spectral rendering handled? Is all spectral rendering handled as simulation?  Are there technique more tailored to 'consumer' rendering, such as for real-time or even just 'realistic looking without solving full physical equations'?

I'd like to understand how we handle the rendering of spectral effects.  It seems like a photon needs to be described as a range of wavelengths, and incidence with a surface either

replaces the original, and resolves multiple new photons across the spectral function, each with their own new vector
maintains the original (or marginally modified) photon, given a threshold

I would prefer to be pointed in the direction of existing work, but appreciate any coloring of this topic.

The most common way I saw is to have photons of several different wavelengths. One then renders with each wavelength and blends the results into the final image.

"Existing work": Psychopath Renderer and The Secret Life of Photons.


why doesn't a ray hitting a sphere at only 1 point count as a hit in sphere/ray intersection? To give context to the question, I am reading Peter Shirley's Ray Tracing in one weekend. In his code for sphere/ray intersection, when the quadratic formula returns only 1 solution, he discards it, which strikes me as odd. Is there any graphics theory that support it or is it just his personal preference?

Here is the link to the code I am talking about on github.
https://github.com/petershirley/raytracinginoneweekend/blob/master/sphere.h

It is mainly personal preference, but it does have some logic behind it which would make it a better option. It should not have any big impact on your final image, though.

When the discriminant is 0, then that means that there is only one solution. For a sphere, when there is only one solution, that means that the ray is tangent to the sphere. When a line or ray is tangent to a sphere, that means that there is a 90° angle between the line/ray and the normal of the sphere at the intersection. When comparing that situation to ray-triangle and ray-plane intersections, they always ignore the hit when it has an angle of 90° with the normal. This is because the ray would then not really be able to hit it, and in real life you cannot see an infinitely thin plane or triangle that is perfectly parallel to your viewing direction.

Discarding hits when the angle is 90° could also help with shading. Depending on the shader, a 90° angle might always return black or start giving funky results, while when the angle is less than 90° it is just perfectly fine. Also as @Rahul has said, if you would calculate a reflected ray, it would end up in the same direction as your original ray and with most shaders that reflection ray would contribute to 100% of the ray's colour and not be coloured, so it would give the exact same colour as if you just discarded the ray.

The thing that makes this basically personal preference, is the fact that it would practically not happen that a ray would hit the sphere perfectly tangent, in an average render engine (as Rahul has also said). When looking at a sphere from a certain point, there would be a single circle with an infinitely small thickness that could create the occurrence of the discriminant being 0.

In short, it basically does not matter a single bit if you discard those hits or not.


Understanding view matrix I've been reading several sources in the web about transforming world-space points into camera-space ones.
I am building my view-matrix from the following parameters

1. Camera position
2. Point the camera is looking at
3. Up vector

I perfectly understand the meaning of each of the parameters, however, there are still some doubts.

How is the direction vector built? We have camera position and lookat position, is it camPos-lookatPos or lookatPos-camPos? In other words, does the direction vector aligns with (goes in the same direction of) the world +z-axis or is opposite to it? Direction is a bit confusing since it makes me think it goes the direction the camera lens is pointing to.
What's the reasoning behind translating the camera to the origin? How does this simplifies math?

My view matrix looks like follows

$$V = \begin{matrix}
  Rx & Ry & Rz & 0 \\
  Ux & Uy & Uz & 0 \\
  Fx & Fy & Fz & 0 \\
  -CamPosx & -CamPosy & -CamPosz & 1
 \end{matrix}$$

Will this V matrix convert from camera to world or from world to camera coordinates? How can I understand which direction it is going?

There is no relation between direction's direction and the world axis. And that's fortunate otherwise it would mean your camera is not a free view, it's some kind of a axis bound camera, which has its usages but most likely nothing in your mind right now.

The default camera matrix is looking at +z when everything is Identity, that's most surely where you got confused. Know that this is purely a convention, but sticking to a widely adopted convention allows for easy compatibility with libraries like glm.

the direction vector goes outward, so its normalize(lookat - campos).

The view matrix can be constructed directly with TBN vectors in rows 0 1 2 :)
(that's your RUF)

Point 2. There is no translating of the camera to the origin, that's just how you chose to view (pun) it. There is translation of world objects toward the origin. Because the rasterizer will work in device coordinates (NDC) which is not configurable, so having a roaming camera (that travels) makes it necessary to indicate its translation in world as part of the last row (row 3), and in reverse since it's not a world matrix representing the camera position, it's the matrix that will bring back points into the view space. (by the way, incidentally meaning the actual camera world matrix is the inverse of the view matrix).

oh, that was the last phrase of pt 2.


exact down sampling and re-triangulation of mesh data(non-convex) I have a human body 'surface' mesh data.: triangular mesh (vertices, face)

What I want to get from this is 'exact-down-sampled' version of the current mesh.

Which means.. the processed output mesh should have the vertices that all belong to the input mesh and the mesh data should be in the triangular mesh form..

I know there are some surface mesh simplification algorithms, such as poisson surface reconstruction algorithm. But as far as I know, they don't preserve the positions of the input mesh.
 What I simply want is to down-sample the points and triangulate them.

1. Method: Vertex Clustering

This is more or less a low-quality method, but depending on your mesh it could work well.
The basic idea is to partition the space into a regular grid, and then choose one representative for each cell that holds at least one vertex.
Then calculate the connectivity based on the connectivity of the original vertices.

In the image you see a basic 2D clustering. The unreduced mesh on the left, and the reduced on the right with the chosen representatives.
As you can see, just choosing an existing vertex as representative (by closest to mean, or closest to center, or any other idea you can think of) you get a subset of vertices.

But you also see the problem, thin parts will degenerate and parts that are close to forming a loop will probably get connected. But as already said, it depends on your mesh if this works.

2. Method: Incremental Mesh Decimation with with Half-edge Collapse

One vertex gets collapsed into its neighbour. Thereby you get again a subsampling.
This is a progressive method. You evaluate which collapse will decrease the quality (for example total distance to the original surface, but many more possible) and collapse it. Then you check if your quality has dropped too much for another collapse, and if so you stop. Otherwise you do it again. Until either the quality drops too much or the target size is reached.

Method 3: Progressive Mesh Decimation with Vertex Decimation.

The same progressive idea as in method 2, but this time instead of a collapse you just delete a vertex and calculate a new triangulation for the hole that this created.


To what degree, if at all, can custom code be embedded in a PNG, GIF, or JPG? Computer graphics files are in Windows rendered by components such as the Graphics Device Interface and Direct2D.

Is it possible to create a graphic file that, besides displaying a graphic also utilizes custom code inside the graphic file?

With custom code I am referring to functionality such as:

Incrementing a counter or date that is displayed on the graphic.
Accessing a web URL to retrieve data that is displayed on the graphic.

Common graphics formats such as JPEG, PNG and GIF are not designed to have any form of code inside them. They just store a compressed array of pixels—they can't generate anything on command or contact a web service, etc.

(There have occasionally been vulnerabilities discovered in image decoders, that would allow a maliciously constructed image to cause code execution when viewed, via a buffer overflow exploit or similar. But this is of course not part of the design of the format.)

Some vector graphics formats such as EPS and SVG actually do allow embedding code. However, being vector formats instead of bitmap ones, these formats often aren't supported by ordinary image viewers (although SVG is supported by browsers), and can't be edited in ordinary paint programs. One needs specialized vector graphics programs to work with them.

In order to generate an image that updates with new data, you could create a web service that regenerates the image on the server each time it's requested. However, if a client caches the resulting image rather than re-requesting it each time it's viewed, they would see old data.


Calculating normals for vertices which aren't a vertex of all neighbouring triangles In my procedurally generated mesh in Unity, not all vertices are vertexes of all neighbouring triangles - essentially, it's a grid with cells of varying sizes. This is messing up the calculation of normals however, making the lightning not smooth. How should I account for this? This is a part of the mesh to illustrate what I mean, in shaded wireframe and shaded mode:

For the shading to match, the normals (and any other vertex attributes) of the small triangles' verts would have to match the linear interpolation along the large triangle edge that they adjoin to.

For example: all the vertices in the green box below would need to be set by interpolating between the two blue vertices, based on their position along that edge.

As Nicol alluded to however, you may not get perfectly watertight rendering—or a perfect match in the shading—when constructing a mesh with T-junctions like this.

]


How do I implement object picking, using OBB in OpenGL? I am trying to make 3D drawing software. I wanted to have the drag feature so I am using object picking using the OBB algorithm. I am facing problems in understanding the algorithm, and my implementation thus is having bugs.

How do I implement object picking, using OBB in OpenGL? As I am new to OpenGL (free-glut library), a step by step explanation would be helpful.

I am not able to understand what t1 and t2 mean and how the algorithm is working. If you explain the algorithm that would be enough.

Ray vs OBB intersection works by shooting a ray towards the OBB's planes. This results in 2 intersections referred to as t1 and t2 (per axis), also referred to as tNear and tFar or tMin and tMax.

Checking whether the ray intersects with the box, can then be done by comparing the largest tNear against the smallest tFar. If the largest tNear is less than the smallest tFar then there is a intersection.


Difference betwen Rendering Equation, Lighting model, Ray Tracing, Global Illumination and Shadows? What is the difference between all these techniques? I know what a lightning model does, eg Phong, Flat, Gouraud. As far as I know both Ray Tracing and Global Illumination are just lighting models different from the classic ones mentioned above that simulate physical light more accurately, taking into account light ray bouncing, indirect light etc.

As for shadows, I believe not all lighting models can support shadows. Are shadows something implemented on top of a lighting model, ie they can't be used without a proper one that supports them, or are they used independently of lighting?

I know that the rendering equation is a general technique for the approximation of lighting in a 3D world. Is the rendering equation used in conjuction with a lighting model, or is a "lighting model" an implementation of the redering equation?

Does the rendering equation account for shadows as well (from its form on wikipedia I think not) and if not should an "extended" rendering equation be developed for a particular 3d world that enables shadows?

I'm trying to clarify this foggy cloud of concepts in my mind. Thanks in advance.

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

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

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

Let us consider the commonly shown formulation:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$$L = L_e + TL_e$$

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

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

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

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

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

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

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

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

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


How does a 2D Fourier Transform of an image work? I understand how a 1D Fourier transform separates a signal into its component frequencies, but I'm having difficulty understanding how a 2D Fourier transform affects a 2D image.

From another question, John Calsbeek linked to an interesting paper about measuring the quality of noise functions. This showed various noise functions and the Fourier transform of each.

Is this a discrete transform of the pixel data, or a continuous transform of the continuous interpolating function which is used to generate the noise at arbitrary points?

Is the annular shape analagous to taking 1D Fourier transforms of the line through the centre of the image at every possible angle? Or is the transform for each possible angle also measured across the whole 2D space rather than only along a line through the centre? I'm trying to get an intuitive feel for what changes in the input image correspond to what changes in the Fourier transform.

A 2D Fourier transform is performed by first doing a 1D Fourier transform on each row of the image, then taking the result and doing a 1D Fourier transform on each column.  Or vice versa; it doesn't matter.

Just as a 1D Fourier transform allows you to decompose a function into a sum of (1D) sine waves at various frequencies, a 2D Fourier transform decomposes a function as a sum of 2D sine waves.  These waves can have different frequencies along the x and y axes.  They generically have the form:

$$ \exp \bigl(i \cdot (k_x x + k_y y) \bigr) $$

where $k_x$ and $k_y$ are the frequencies along the $x$ and $y$ axes. These two values form a vector called the wave-vector.  In the spatial domain, the wave is oriented along the $(k_x, k_y)$ vector with a frequency along its axis of $\sqrt{k_x^2 + k_y^2}$.

Just as for the 1D Fourier transform, there exist both discrete and continuous versions.  The result of a discrete 2D Fourier transform is a matrix of complex amplitudes for a set of discrete $(k_x, k_y)$ values.  This is commonly visualized (like in the paper you linked to) as an image where the pixel at coordinates $(k_x, k_y)$ represents the amplitude of that wave-vector.

So, an annular shape in a 2D Fourier transform indicates rotational invariance of the distribution of frequencies (i.e. just as much amplitude for waves in every direction), with a narrow range of magnitudes (from the inside of the annulus to the outside).  In other words, the paper is using the Fourier transform to demonstrate that their noise is reasonably isotropic and band-limited.


How will the z-buffers have the same values even if polygons are sent in different order? I know when we use Z-buffer to eliminate the hidden faces, the polygons can be in any order. But my teacher said that this does not mean that two images generated by sending polygons in different orders will have identical values in their z-buffers and in their frame buffers. How does this happen?
And if this is the case, When or how will the z-buffers and the frame buffers have the same values even if polygons are sent in different order?

What your teacher means is that at the end of the frame, once all polygons in the scene have been drawn, the z-buffer will have the same values. This is because the z-buffer keeps the minimum Z within each pixel, over all the polygons drawn to that pixel, and the minimum doesn't depend on the order.

If you look at the z-buffer in the middle of the frame, when some polygons, but not all, have been drawn, then naturally the contents of the z-buffer will depend on what's been drawn so far, which would depend on the order in general.

With regard to the color buffer, the same things are true if all the Z values within each pixel are distinct. However there's one case where the results do depend on the order: when multiple polygons have the same Z value at a given pixel. This could happen if the same polygons are rendered twice with different colors, or some such. Then, the behavior depends on the setting of the depth test (i.e. glDepthFunc in OpenGL). If it's strictly "less", then the first polygon drawn that has the minimum Z will "win" and its color will end up in the color buffer at the end. But if the depth test is set to "less-equal", then each polygon that has the minimum Z will overwrite the one before it, and the last one drawn will end up in the color buffer at the end. So in that case, the order of drawing polygons, and the state of the depth test, do make a difference.


Does cosine weighted hemisphere sampling still require NdotL when calculating contribution for indirect light? When converting from uniform hemisphere sampling to cosine weighted hemisphere sampling I am confused by a statement in an article.

My current indirect contribution is calculated as:

Vec3 RayDir = UniformGenerator.Next()
Color3 indirectDiffuse = Normal.dot(RayDir) * castRay(Origin, RayDir)

Where the dot product is cos(θ)

But in this article on better sampling (http://www.rorydriscoll.com/2009/01/07/better-sampling/) the author suggests the PDF is (cos(θ) / pi), and there is no evidence of the N dot L calculation.

My question is - does that mean that I no longer need to perform the normal dot rayDirection because it is included in the PDF, or is it in addition to the pdf?

You always need to multiply by the cosine term indeed (that's part of the rendering equation). Though when you do indirect diffuse using ray-tracing and thus monte-carol integration (which is the most common technique in this case), you have to divide the contribution of each sample by your PDF. This is well exampled here.

Note also that in the mentioned reference, if the PDF has terms that you also find in the rendering equations then you can optimise the code if you wish by cancelling out these terms.

  Don't forget that the BRDF of a diffuse surface is ρ/π where ρ stands for the surface albedo. So we need to divide the result by π. Though in the case of the indirect diffuse component, don't forget that we should have divided the result of castRay by the PDF of the random variable, which as we showed earlier in this chapter is 1/(2π). Dividing indirectDiffuseby 1/(2π) mis the same as multiplying this value by 2π. And since the albedo is also divided by π we can simplify the code...

You have a similar situation. If you look at the PDF for the cosine sampling, then you will realise that terms can be cancelled out. Which doesn't mean they are 'not' strictly necessary. They are, they just cancel each other out which allows to optimize the code slightly (and avoid a few division, multiplication, etc.). You are more in the micro-optimisation here... which can be confusing if you try to learn the theory by just looking at optimised code (which is often not properly commented).

$ \dfrac{(cos(\theta) ... )}{PDF} = \dfrac{(cos(\theta) ... )}{\dfrac{cos(\theta)}{\pi}} = ... $


Ray tracing with thin lens camera I'm reading Cook's paper "Stochastic Sampling and Distributed Ray Tracing", I don't understand how the rays are generated. He says:

  Determine the focal point by constructing a ray from the eye point
  (center of the lens) through the screen location of the ray. The focal
  point is located on this ray so its distance from the eye point is
  equal to the focal distance.

I can't parse this image. Where is my screen plane located according to this image? What is the focal point? If you see some optics picture of a thin lens, the focal point is always in the same place, where all the rays converge. If it is always the same point, why do have I to calculate it for each ray?

In a traditional camera, the photons from the scene travel through the lens of the camera, then hit the sensor at the focal length. A consequence of the lens is that the image is upside down and backwards.

In ray tracing, we can optimize this by imagining the focal plane is in front of the camera. You can think that the photons from the scene travel towards the camera hole, and resolve on the image plane.

Another optimization in ray tracing to to trace rays from the camera into the scene, rather than tracing them from light sources and hoping they hit the camera. Therefore, the first rays we shoot out are the ones that go from the eye through each pixel on the virtual screen.

In order to create the ray, we need to know the distances a and b in world units. Therefore, we need to convert pixel units into world units. To do this we need a define a camera. Let's define an example camera as follows:
$$origin = \begin{bmatrix} 0 & 0 & 0 \end{bmatrix}$$
$$coordinateSystem = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$
$$fov_{x} = 90^{\circ}$$
$$fov_{y} = \frac{fov_{x}}{aspectRatio}$$
$$focalDist = 1$$

The field of view, or fov is an indirect way of specifying the ratio of pixel units to view units. Specifically, it is the viewing angle that is seen by the camera.

The higher the angle, the more of the scene is seen. But remember, changing the fov does not change the size of the screen, it merely squishes more or less of the scene into the same number of pixels.

Let's look at the triangle formed by fovx and the x-axis:

We can use the definition of tangent to calculate the screenWidth in view units
$$\tan \left (\theta  \right) = \frac{opposite}{adjacent}$$
$$screenWidth_{view}= 2 \: \cdot \: focalDist \: \cdot \: \tan \left (\frac{fov_{x}}{2}  \right)$$

Using that, we can calculate the view units of the pixel.
$$x_{homogenous}= 2 \: \cdot \: \frac{x}{width} \: - \: 1$$
$$x_{view} = focalDist \: \cdot \: x_{homogenous} \: \cdot \: \tan \left (\frac{fov_{x}}{2}  \right)$$

The last thing to do to get the ray is to transform from view space to world space. This boils down to a simple matrix transform. We negate yview because pixel coordinates go from the top left of the screen to the bottom right, but homogeneous coordinates go from (-1, -1) at the bottom left to (1, 1) at the top right.
$$ray_{world}= \begin{bmatrix} x_{view} & -y_{view} & d\end{bmatrix}\begin{bmatrix} &  & \\ & cameraCoordinateSystem & \\ &  & \end{bmatrix}$$

You can see an implementation of this here (In the code, I assume the focalDist is 1, so it cancels out)


Microfacet BRDF artifacts I've been trying to implement a microfacet specular BRDF based on the equations in Real Shading in UE4, but I'm getting weird ring-shaped artifacts in the highlights of rough surfaces:

Here's the relevant pieces of the fragment shader:

float D(float NoH, float roughness) {
    float a = sqr(roughness);
    float a2 = sqr(a);
    float denom = PI * sqr(sqr(NoH) * (a2 - 1.0) + 1.0);
    return a2 / denom;
}
float G1(float NoV, float k) {
    float denom = NoV * (1.0 - k) + k;
    return NoV / denom;
}
float G(float NoL, float NoV, float roughness) {
    float k = sqr(roughness + 1) / 8.0;
    return G1(NoL, k) * G1(NoV, k);
}
float F(float VoH, float ior) {
    float f0 = sqr((1.0-ior)/(1.0+ior));
    return f0 + (1.0 - f0) * exp2((-5.55473*VoH - 6.98316) * VoH);
}
vec3 brdf(in vec3 V, in vec3 L, in vec3 N, in Material mat) {
    vec3 H = normalize(V+L);
    float NoL = dot(N, L);
    float NoV = dot(N, V);

    float nom = D(dot(N, H), mat.roughness)
        * F(dot(V, H), mat.ior)
        * G(NoL, NoV, mat.roughness);
    float denom = 4.0 * NoL * NoV;

    return vec3(1) * nom / denom;
}

// ----------------------

void main() {
    // ...

    vec3 rd = normalize(frag_pos - camera_pos);
    Material mat = materials[mat_index];
    col = brdf(-rd, sun_dir, normal, mat);

    // ...
}

Any idea what I'm doing wrong?

It turns out that the ring was happening from a negative divided by a negative, so adding nom = max(nom, 0.0); fixed the problem. The new highlight, amplified:


Does the blending matrix change between calculating various curve segments in a uniform cubic B-splines approximation? I would like to ask about uniform (periodic) cubic B-splines (approximation, no interpolation).

$$B=1/6\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&0&3&0\\1&4&1&0\end{bmatrix}$$

$B$ is the matrix of coefficients that allows calculating a single curve segment with the formula:

$$ Q_i(u)=[u^3 u^2 u^1 1]B \begin{bmatrix}P_{i-3}\\P_{i-2}\\P_{i-1}\\P_{i}\end{bmatrix} $$

When $i=3$ I calculate the first segment of the curve. My question is when $i=4$ and I want to calculate the second segment of the curve I must change the $4$ control points but does $B$ change or not?

No, the $B$ matrix (basis coefficient matrix) does not change from one segment to the next. It is a property of the type of spline you're using, in this case cubic B-splines. If you used Bézier splines or Hermite splines instead, you'd have a different $B$ matrix.


Is there a way to achieve the look of a distant flock or shoal without full simulation? Although simulation models like Boids give good results for bird flocks or fish shoals on a small scale, simulating every single member in real time becomes unrealistic for huge numbers. Is there a way I can model a flock in the distance where only the density of birds is visible? I'd like to have that flowing, changing density gradient with a much smaller number of variables to process.

I've tried using a much smaller population and displaying each boid as a blurred area with Gaussian density so that as they overlap the density rises and falls through their interaction. This is reasonably cheap but it never leads to sharp changes in density, either spatially or temporally, which makes it look too uniform.

Is there any other way of getting away with a much smaller number of individuals? Or is the only way to get realistic results to prerender?

One way that might work is to have boids but render each boid as a group of birds.  This way the simulation is still simple but the rendering makes it seem complex.  You might even allow a little drift per bird in the boid to make it look so obviously rigid.


How can I bind my texture in the correct orientation? I have successfully completed a working program that draw a rotating sphere with a map of the world as the texture, simulating the earth in space.  However, the texture is bound on it's side, i.e. all the continents are on their sides and the poles are shown as the sphere spins on the y-axis.  I used the following reference to build the rotating sphere:
http://www.songho.ca/opengl/gl_sphere.html#:~:text=In%20order%20to%20draw%20the,triangle%20strip%20cannot%20be%20used.
and the stb_image library (https://github.com/nothings/stb) to load a JPEG image for the texture.
I've tried a couple of things like:
actual rotation of the JPEG image,
rotating the array that holds the texture coordinates,
rotating the array that holds the indices
Everything is good apart from the orientation of the image bound for texturing.  Any advice/pointers would be appreciated.

Binding the image is unrelated to its orientation. A shot in the dark is that your texture coordinates are either reversed or computed with the orientation in the wrong direction. You could just rotate the image as a work around. The main issue here is whether the upper left corner is your origin, or the lower left corner is the origin. But neither of these explain the image being sideways. At any rate, look at your texture coordinates, how the image is being copied into memory, how is is being passed to opengl, and the texture coordinates.


How does Processing language relate to the industry standard? Here are its docs: https://processing.org/reference.
Processing is described as a 'language built with the purpose of teaching non-programmers the fundamentals of computer programming in a visual context'.

However, how does this language relate to the real-world computer graphics tools?

For example:

Is it similar to some low-level library maybe?
Is the concept of a repeating draw() { background(255) } (in order to draw each new frame of an animation) used in real-world libraries?
Are the same
methods/concepts used (pushMatrix, popMatrix, rotate,
translate)?

It does not relate to low level libraries. Yes, usually each frame is drawn separately, nothing can change if i dont change anything. However the draw loop is often handled by somebody else in for example game engines, etc. So in fact processing is often lower level stuff than what many people would do day to day.

Pushing matrix state is pretty common, it exists even in graphics languages from 1970's.


How to voxelize geometry using textures and shaders? I am trying to fetch a given geometry and, through (potentially multiple) render passes, create a 3D texture that stores the color value of said geometry into an associated texel.

In other words there is a 3D box that i am trying to color based on the geometry inside of that box.

Currently I am attempting to do so with the following vertex shader:

#version 450

#define PI 3.1415926535897932384626433832795

layout(location = 0) in vec3 position; //(x,y,z) coordinates of a vertex
layout(location = 1) in vec3 norm; //a 3D vertex representing the normal to the vertex
layout(location = 2) in vec2 texture_coordinate; // texture coordinates

layout(std430, binding = 3) buffer instance_buffer
{
    vec4 cubes_info[];//first 3 values are position of object
};

out vec3 normalized_pos;
out vec3 normal;
out vec2 texture_coord;

uniform float width = 128;
uniform float depth = 128;
uniform float height = 128;

uniform float voxel_size = 1;
uniform vec3 origin = vec3(0,0,0);

uniform float level=0;

void main()
{
    texture_coord = texture_coordinate;
    vec4 pos = (vec4(position, 1.0) + vec4(vec3(cubes_info[gl_InstanceID]),0));

    pos-=vec4(origin, 0);

    pos.x = (2.f*pos.x-width)/(width);
    pos.y = (2.f*pos.y-depth)/(depth);
    pos.z = (2.f*pos.z-depth)/(height);

    gl_Position = pos;

    normalized_pos = vec3(pos);

    normal = normalize(norm);
}

And the following fragment shader:

#version 450

in vec3 normalized_pos;
in vec3 normal;//Normal to the vertex
in vec2 texture_coord;

out vec4 outColor;//Final color of the pixel

uniform sampler2D text;

void main()
{
    outColor = vec4(0,1,0,1);
}

Currently the color is ahrd set to green, just to test whether I am doing things in the correct fashion.

But I seem to have failed.

How exactly would you design a shading program that voxelizes a 3D grid of a space?

A fragment shader executes for a 2D rasterized position. When you output the normalized position it's still being projected onto the 2D xy image plane onto a render target. The render target is 2D, so you can't use the fragment shader output to achieve this.

You need to bind a 3D texture as a read/write texture in order to store values.

The other thing is how you're expecting to voxelize the geometry, are you trying to voxelize the surfaces? If so you can use a pixel shader but you need to render all faces (disable back face culling).


Fuse detailed road mesh with regular grid terrain mesh I am experienced with C++ and know more embedded device related stuff but have absolutely no knowledge of computer graphics and its algorithms.

I would like to get a road mesh (based off of a spline) blended seamlessly into a terrain mesh, which is based on a regular grid, like in the picture below. How is this achieved?

Just looked at the CGAL documentation and I cannot even see which problem I am facing and which package to study. Delauney refinement maybe? But I only see a CGAL package for 2D. I'd like to generate a 3D mesh.

The road mesh should be unmodified, the terrain mesh can be altered to form a seamloss mesh.

Can you guide me to the kind of algorithms needed for this?

Kind regards
Max

I think the best way to tackle this problem would be to make an algorithm that works on a single triangle at a time.

You'd look at each terrain triangle individually that the road intersected and process it.

Looking at one triangle individually, you would have to chop that triangle into one or more meshes to make it contour to the road.

Here are some of the cases to consider in the image below.  I'm betting there is some triangle slicing algorithm that would be suited to this, and I'm not sure of a name off hand, but the main contribution I'm proposing here is that you deal with triangles individually.

When cutting the triangle on the x/y plane to make a hole for for the road, you would also want the terrain to take on the z value (height) of the road, for those vertices that touch the road.  This will make the terrain rise up to meet the road.

At this point, you'd have a terrain mesh which did conform to the road but it would be ugly.

Instead of having a nice even looking hill that went up to the road at reasonable slopes, you'd have some triangles that went very sharply up to the road, and others that had a very flat slope.

What you would need to do now is do some kind of "relaxation" algorithm to address this.

Basically, if something is too steep, because there wasn't enough triangle to make the height adjustment, you need to make your whole triangle closer in height to the road and bleed off some of the height adjustment to neighboring triangles.

If something was not steep enough for your liking, because there was a lot of triangle to make a small height adjustment, you may want to break the triangle up into more polygons where it gets closer to the road and have that smaller area handle the change in elevation.

During this second step, when you added a vertex to an edge between two triangles you would also need to adjust the triangle that shares the edge to prevent cracks from showing up in the terrain.

The details are a bit vague, but hopefully the two step approach will help you tackle the problem.

Make the terrain mesh adapt to the road, without caring about how it looks.
Refine the terrain mesh to make it appear to meet the road in a more organic man made way.


Douglas-Peuker and equal distances I have a polyline and I want to simplify it with Douglas-Peucker. It's an easy algorithm, but what if there are points with the same distance. What point should I select? Is there a reasonable solution?

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

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


How can DSA functions be used without extension names on lower versions of OpenGL? My GPU supports OpenGL 4.4 but looking at the OpenGL extensions viewer the only part of 4.5 that it does not support is the GLSL version.

I am able to use all DSA functions without specifying any sort of Extension Prefix.

Similarly, I have been able to run code that uses DSA on GPUs that only support OpenGL 4.2

How is this possible?

I thought that, if my GPU does not support a version of OpenGL I have to use extension prefixes to use those features.

How is this possible?

Because ARB_direct_state_access is an extension. Note that the function/enumerator names in that extension lack the ARB suffix. There are dozens of ARB extensions that work like that. Suffix-less extensions were introduced in OpenGL 3.0 for compatibility purposes. You could write code that could work on OpenGL 3.0 or extensions that expose 3.0 functionality, without having to write different function calls.

The same goes here. You're not using OpenGL 4.5; you're using OpenGL 4.4+some extensions.


What is the typical use case for rendering to an image through imageStore? The typical scenario for using a texture would simply be:

//Create texture
glGenTextures(1, &textureID);
glBindTexture(target, textureID);
glTexImage2D(target, 0, color_format, width, height, 0,
    color_format, GL_UNSIGNED_BYTE, data);

glTexParameteri(target, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
glTexParameteri(target, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
glTexParameteri(target, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexParameteri(target, GL_TEXTURE_MAG_FILTER, GL_NEAREST);

//load to program
glActiveTexture(texture_unit);
glBindTexture(target, textureID);
//Get the uniform location in the program and attach the texture unit
GLuint location = /*get_uniform_location*/;
glUniform1i(location,texture_unit - GL_TEXTURE0);

//Draw
render();

However image load store are somewhat different. First, they don't use texture units but image units. Second you need to manually set memory barriers yourself to ensure completion of writing stage before reading. Amgon other things.

I have read the documentation and attempted to implement things myself but It seems I am doing things wrong. I'd rather just forget about what I have tried and understand properly how this needs to be done step by step.

I want to know what a typical, minimum example use of image load stores qould be.

So creation of the image, writing to the image, reading from the image.

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

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

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

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

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

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

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

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

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


How to compute volume of intersection of non-axis-aligned cuboids in 3D? Given two cuboids in 3D space (8 vertex coordinates each) that are arbitrarily oriented, how can we find the volume of overlap between them in the fastest manner?

You can use CGAL's half_space_intersection_3 or half_space_intersection_with_construction_3 functions, where the half-spaces are defined by the faces of the cuboids.


Is it possible to emulate Vulkan on a non Vulkan compatible gpu? I don't think there is much to explain here, since the question is pretty much in the title, but i'll try to explain myself better:

My current laptop's gpu does not support Vulkan, so i was wondering if it was possible to do something like d3d12 does, where if a specific function is not able to be performed by the gpu, it can be emulated by the cpu, while maintaing the program running and functioning, at the obvious cost of performance.

Can I achive something like that using Vulkan?

It's possible to emulate Vulkan on a sufficiently capable non-Vulkan API.  This is the point of the Vulkan Portability Initiative.  Indeed, there is already a Vulkan implementation on top of the Apple proprietary API Metal, and there is work being done to implement Vulkan on top of D3D12.

It probably would be possible to implement a version of Vulkan that ran partially on a GPU (to which you had some other API access) and partially in software on the CPU, but unless you're working with some kind of mobile device with integrated memory, the performance of such a system would probably be utter garbage.

If your goal is to better understand and develop for Vulkan, I'd suggest you investigate some of the existing efforts at creating a fully software Vulkan implementation.

If you're just trying to get some game to run better, I suggest you get a better laptop.


Non Real Time Raytracing I've played with real time raytracing (and raymarching etc) quite a bit, but haven't spent that much time on non real time raytracing - for higher quality images or for pre-rendering videos and the like.

I know one common technique to improve image quality in the non real time case is to just cast A LOT more rays per pixel and average the results.

Are there any other techniques which stand out as good ways to improve image quality in the non real time case, over what you would normally do in the real time case?

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

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

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

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

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

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


DX9 Shadow map PCF issue I am trying to do simple PCF with Unity but I am facing some issues and I don't know where they come from. If anybody has an idea...

Here are two examples

// C#
GetTemporaryRT(_shadowMapProperty, _shadowSettings.shadowAtlasWidth, _shadowSettings.shadowAtlasHeight, _depthBufferBits, FilterMode.Bilinear, RenderTextureFormat.Depth, RenderTextureReadWrite.Linear);

// CG
sampler2D_float _ShadowMap;
float4 _ShadowMap_TexelSize;

half ShadowAttenuation(float3 shadowCoord)
{
    float depth = tex2D(_ShadowMap, shadowCoord).r;
#if defined(UNITY_REVERSED_Z)
    return step(depth - _ShadowData.y, shadowCoord.z);
#else
    return step(shadowCoord.z, depth + _ShadowData.y);
#endif
}

/////// EXAMPLE 1 ///////

float shadow = ShadowAttenuation(half3(shadowCoord.xy, shadowCoord.z));
return shadow;

/////// EXAMPLE 2 ///////

float3 UnityCombineShadowcoordComponents(float2 baseUV, float2 deltaUV, float depth)
{
    float3 uv = float3(baseUV + deltaUV, depth);
    uv.z += dot(deltaUV, receiverPlaneDepthBias.xy);
    return uv;
}

half shadow = 1;
const float2 offset = float2(0.5, 0.5);
float2 uv = (shadowCoord.xy * _ShadowMap_TexelSize.zw) + offset;
float2 base_uv = (floor(uv) - offset) * _ShadowMap_TexelSize.xy;
float2 st = frac(uv);

float2 uw = float2(3 - 2 * st.x, 1 + 2 * st.x);
float2 u = float2((2 - st.x) / uw.x - 1, (st.x) / uw.y + 1);
u *= _ShadowMap_TexelSize.x;

float2 vw = float2(3 - 2 * st.y, 1 + 2 * st.y);
float2 v = float2((2 - st.y) / vw.x - 1, (st.y) / vw.y + 1);
v *= _ShadowMap_TexelSize.y;

half sum = 0;

sum += uw[0] * vw[0] * ShadowAttenuation(UnityCombineShadowcoordComponents(base_uv, float2(u[0], v[0]), shadowCoord.z));
sum += uw[1] * vw[0] * ShadowAttenuation(UnityCombineShadowcoordComponents(base_uv, float2(u[1], v[0]), shadowCoord.z));
sum += uw[0] * vw[1] * ShadowAttenuation(UnityCombineShadowcoordComponents(base_uv, float2(u[0], v[1]), shadowCoord.z));
sum += uw[1] * vw[1] * ShadowAttenuation(UnityCombineShadowcoordComponents(base_uv, float2(u[1], v[1]), shadowCoord.z));

shadow = sum / 16.0f;
return shadow;

Here are the results.

It seems that sampler2D_float doesn't allow to interpolate shadow lookup  linearly. So I had to do it by hand. Here's an example of interpolated shadowing.

float texture2DCompare(sampler2D depths, vec2 uv, float compare){
    float depth = texture2D(depths, uv).r;
    return step(compare, depth);
}

float texture2DShadowLerp(sampler2D depths, vec2 size, vec2 uv, float compare){
    vec2 texelSize = vec2(1.0)/size;
    vec2 f = fract(uv*size+0.5);
    vec2 centroidUV = floor(uv*size+0.5)/size;

    float lb = texture2DCompare(depths, centroidUV+texelSize*vec2(0.0, 0.0), compare);
    float lt = texture2DCompare(depths, centroidUV+texelSize*vec2(0.0, 1.0), compare);
    float rb = texture2DCompare(depths, centroidUV+texelSize*vec2(1.0, 0.0), compare);
    float rt = texture2DCompare(depths, centroidUV+texelSize*vec2(1.0, 1.0), compare);
    float a = mix(lb, lt, f.y);
    float b = mix(rb, rt, f.y);
    float c = mix(a, b, f.x);
    return c;
}


Why does _ray_ tracing work? Perspective projection (or at least non-orthogonal) is by far the most common in photo-realistic graphics. When we use perspective projection, the (equally thick) slices of volume visualized by each pixel get larger with the distance. But with ray tracing we normally cast cylinder-like rays instead of cones. It seems to me that this must make quite a difference to the results: consider the two fields of view of pixels: cone-like one at the LHS, and cylinder-like one at the RHS, the pixels are at the bottom:

The colored lines here represent walls of randomly-distributed light sources with the same density in each wall. If we assume that the intensities of the light sources are the same, so that one of the pixels would "see" white average color, the other must necessarily have a color tint, because the left one samples more red compared to blue than the right one.

Am I right in this? If so, why does then ray tracing work? Why don't we do "frustum tracing" or "cone tracing" to get the colors/illuminances right? And if I'm wrong, then what is my mistake?

But with ray tracing we normally cast cylinder-like rays instead of cones.

Rays aren't really cylinders: they're infinitely thin. This infinitely thin ray can be an approximation to the cone just as much as it can be an approximation to the cylinder.

  If we assume that the intensities of the light sources are the same, so that one of the pixels would "see" white average color, the other must necessarily have a color tint ... Am I right in this?

Sort of. Your left-hand diagram doesn't have a colour tint. Although it covers more of the red wall than the blue wall, both of them subtend the same solid angle from the camera's point of view. The same $\tfrac{1}{r^2}$ ratio between the amount of light included in the cone is exactly countered by the $\tfrac{1}{r^2}$ falloff of the light. If the world worked the way you describe, you could make anything brighter by moving it further away from your eye. The right-hand diagram would have a blue colour tint, because the blue light is closer, but this diagram is not how ray-tracing works.

There has been research in a few variants of beam tracing, where instead of tracing an infinitely thin ray, you trace a cylinder, or cone tracing, where you trace a cone or frustum as a simple approximation to the irregular solid that contributes to the pixel. The maths (and therefore the algorithm) are somewhat more complex (and therefore slower) than simple ray tracing, and then you have to deal with what happens when the cone partially intersects an object, and you have to use the same shape to approximate the continued path of the cone. These approaches never caught on.

Instead, supersampling with rays offers the same advantages as cone tracing but with the performance advantage of doing the same simple algorithm many times. You don't supersample by moving the origin of the rays, which would make a cylinder shape, but by varying the directions, which makes a cone shape. Instead of approximating that cone by a single ray along its axis, you're approximating it by (say) 32 rays spread throughout its volume.


Rotating object around its own center I am trying to implement Blades of Waving Grass and I am still stuck at the point where I need to achieve texture arrangements like in the figure below (the first one).

So my plan is to draw the first texture, then draw the second and rotate it by 30°, then another and rotate it by 60° etc. Drawing the first texture is not a problem but I have some issues rotating the second one. I would expect it to look something like this (view from above):

Instead the actual result looks something like this:

I suspect that this deviation occurs due to the object being rotated around the world-space axes and not around its own.

Vertex and position data:

GLfloat vertices[] = {
    -0.5f, -0.5f, -0.5f,  0.0f,  0.0f,
     0.5f, -0.5f, -0.5f,  1.0f,  0.0f,
     0.5f,  0.5f, -0.5f,  1.0f,  1.0f,
     0.5f,  0.5f, -0.5f,  1.0f,  1.0f,
    -0.5f,  0.5f, -0.5f,  0.0f,  1.0f,
    -0.5f, -0.5f, -0.5f,  0.0f,  0.0f,
};

glm::vec3 texturePositions[] = {
    glm::vec3(0.0f, 0.0f, 0.0f),
    glm::vec3(0.0f, 0.0f, 0.0f)
};

Camera/View transformations:

// Camera/View transformation
glm::mat4 view;
view = camera.GetViewMatrix();
// Projection
glm::mat4 projection;
projection = glm::perspective(glm::radians(camera.Zoom), (GLfloat)WIDTH / (GLfloat)HEIGHT, 0.1f, 1000.0f);
// Get the uniform locations
GLint modelLoc = glGetUniformLocation(ourShader.Program, "model");
GLint viewLoc = glGetUniformLocation(ourShader.Program, "view");
GLint projectionLoc = glGetUniformLocation(ourShader.Program, "projection");
// Pass the matrices to the shader
glUniformMatrix4fv(viewLoc, 1, GL_FALSE, glm::value_ptr(view));
glUniformMatrix4fv(projectionLoc, 1, GL_FALSE, glm::value_ptr(projection));

Drawing the first two textures:

//Texture 1
glm::mat4 model;
model = glm::translate(model, texturePositions[0]);
glUniformMatrix4fv(modelLoc, 1, GL_FALSE, glm::value_ptr(model));
glDrawArrays(GL_TRIANGLES, 0, 6);

//Texture 2
GLfloat angle = glm::radians(30.0f);
model = glm::translate(model, texturePositions[1]);
model = glm::rotate(model, angle, glm::vec3(0.0f, 1.0f, 0.0f));
glUniformMatrix4fv(modelLoc, 1, GL_FALSE, glm::value_ptr(model));
glDrawArrays(GL_TRIANGLES, 0, 6);

Online search showed that this might have several reasons:

Order of the applied transformations are crucial
One solution might be to first move the "object" until its center
matches the world-space origin, apply the rotation and then move it
to the desired position.

As I am still in the very early learning process so I am kind of clueless here.

I think that the order of transformations for the second texture is fine in my code, isn't it?
Also how would I determine the right position for the object where
the rotation would be applied correctly? (see above point 2)
Might it be more efficient to apply the rotation in the objects
local space? Is that possible in my case?

I do not expect anybody to write code for me (though some snippet would be nice) but I would appreciate some hints or somebody pointing me in the right direction. I think that I have a basic fallacy here.

Thanks in advance.

Edit:

If I change the rotation axis from y to z the object rotates
around its own center just like expected.
I also tried to apply the following solutions (taken from here
and here) where I moved the object to glm::vec3(-x,-y,-z)
rotate it and then moving it back to glm::vec3(x,y,z),
unfortunately with no success. Which makes sence as the position
vector is set to (0,0,0) anyway. I also tried to change thisposition
to something else than the origin also with no success.

Am I right if I understand

GLfloat vertices[] = {
    -0.5f, -0.5f, -0.5f, 0.0f, 0.0f,
    0.5f, -0.5f, -0.5f, 1.0f, 0.0f,
    0.5f, 0.5f, -0.5f, 1.0f, 1.0f,
    0.5f, 0.5f, -0.5f, 1.0f, 1.0f,
    -0.5f, 0.5f, -0.5f, 0.0f, 1.0f,
    -0.5f, -0.5f, -0.5f, 0.0f, 0.0f,
};

as being:

  x, y, z, texX, texY

for 6 vertices in total?

If so, then it seems like you do not use indexing yet (vertices 3 and 4 are the same), but nevermind.

Not being sure what order your coordinate system is in, the plane you are constructing here is perpendicular to an axis, but does not go through your origin.

An object that gets rotated by a rotation matrix rotates around its origin. The origin of your model matrix is (0, 0, 0), but this is not the center of your object.

In a right handed coordinate system, the following vertices give you a plane that is standing on the x-z-plane (perpendicular to it) and goes through your origin. Rotating that around y should rotate it like you wish to do:

 GLfloat vertices[] = {
     -0.5f, 0.0f, 0.0f, 0.0f, 0.0f,
     0.5f, 0.0f, 0.0f, 1.0f, 0.0f,
     0.5f, 1.0f, 0.0f, 1.0f, 1.0f,
     0.5f, 1.0f, 0.0f, 1.0f, 1.0f,
     -0.5f, 1.0f, 0.0f, 0.0f, 1.0f,
     -0.5f, 0.0f, 0.0f, 0.0f, 0.0f,
 };

Notice the third value for each vertex.


What are the differences between GPU instancing and standard instancing? I have been reading a lot of debate on a new feature that will be available in the new version of the game engine Unity 5.4 - called GPU instancing. I understand the importance of instancing in general, both in terms of saving memory and draw calls.

However, even after doing some reading, I still couldn't understand what exactly are the differences between GPU instancing and non-GPU instancing - and, more importantly, where the alleged GPU advantages in terms of performance come from in comparison to standard instancing.

Thanks for your knowledge and for any references.

Unity provides a pretty clear description of GPU instancing. It is exactly the same as instancing. Employees of Unity even spell this out by initially arguing against it years ago before finally implementing it.

Before this, Unity solely relied on batching, which was a technique that combined meshes together into one to reduce draw calls.


How are textures projected onto 3d models in texture painting applications In most modeling software you can texture paint onto 3d models using so called stencil textures. They basically project a texture from the viewport view onto the model as seen for instance in the image below from Blender.
What is the general technique used to project textures like this onto 3d models?

I don't know if there is a smarter/more efficient way to do it, but a possible approach is the following:
Step 1 - Projection volume
First, you calculate the "projection volume" where its near plane corners are identical to the texture corners on your screen. You can do this by transforming the screen coordinates of the textures' corners into the range [-1, 1]. Then you use those coordinates to create a quad in NDC by combining the transformed x-y coordinates with z=-1 (near plane) and z=1 (far plane).
Step 2 - Collision test
Now you need to have both, your model and your "projection volume", in the same space. You can either transform the "projection volume" into your model space or your model into NDC. I think the second choice makes the next step a little bit easier.
Now you have to find all triangles that are fully or partially inside the "projection volume". This is basically a collision detection check (triangle vs. quad or frustum) and I won't go into the details here. For all triangles that are fully inside the volume, you now have a connection between each vertex and its position inside the texture you want to project. Simply transform the vertex position into screen space and from there to the textures pixel coordinates. The second transformation depends on where you positioned your texture on the screen and how you have scaled it.
For all partially covered triangles, the basic procedure is the same, but you have to introduce extra "helper vertices" and to transform them too to separate the covered from the uncovered areas. Doesn't mean that you have to really split your triangles into multiple smaller ones, but at least you need the extra vertices as intermediate data for the final step.
Step 3 - Adjust model data
In the last step, you have to bake this information somehow into your model. This totally depends on your model's data structure and layout. You can for example just split partially covered triangles into new ones and then set the texCoord of every vertex that is inside the "projection volume" accordingly.
If you have some kind of model-specific  UV-mapped textures, you would now use the information of the previous step to interpolate and copy the data of your projected texture to your model texture. For each vertex, you know where it is located inside the projected texture and inside its models UV texture. Now you basically cut out each triangle from your projected texture, and transform it into the corresponding triangle in your UV texture. Notice that this is not trivial since the triangle usually gets distorted and scaled. However, you can use the graphics pipeline for that by rendering directly to your UV-texture.
There are probably a lot of other data representations that might require a different approach for this final step. However, the key here is the second step which establishes the connection between your vertices and the texture. Once you have this, it shouldn't be too hard to come up with a method to add the projected texture to your model.
Further information
During the second step, you might also need to perform some kind of depth testing, so that only the closest area gets affected and not all sides that are inside the projection volume.


How to remove internal geometry programmatically in all meshes in .OBJ file? I have an .OBJ 3D model with many complex meshes shape.

The meshes are complex because each of them have multiple internal mesh located in it.

Meshes with internal geometry is defined as a mesh, which consists of many nested geometry.
For example: a tank in .OBJ file is represented by 1 outer geometry with several nested small geometry in it. Total number of geometry to represent that tank would be 5-7.

I want to simplify the tank mesh object above to be represented by 1 geometry instead of multiple geometries.

What tool and what programming language can I use to iterate all the meshes object, remove all internal geometry in .OBJ file?

Please ask if you need clarification.

Thank you.

This would not be perfect but should probably work well enough for your use case - you could render the objects from lots of different angles with a different solid color for each mesh component (without lighting) then remove any meshes that didn't appear in the final image by counting the pixel colours.
If the objects aren't split up into separate meshes then do this by repeatedly merging groups of triangles which share a vertex into the same group, starting with one group per triangle or polygon.


If you can use subdivision surfaces for 2D curves I've seen how subdivision surfaces are good for 3D curves/modeling, but haven't seen anything on if it's good, or even usable, in 2D.

My question is just that, if (a) you can even use subdivision surfaces in 2D, and (b) if you can use it for 2D, if it's a good solution for modeling curves in 2D, or if not, what a good solution for modeling curves in 2D might be (if it's just bezier curves, or ideally something better / more powerful).

Here it suggests subdivision surfaces could be used in 2D, but not sure if they would be considered good for it.

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

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

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

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


smallpt: ray scattering and Importance Sampling Introduction

For those familiar with smallpt by Kevin Beason:
In path tracing, when rays hit a surface, they are scattered and the theta angle (the angle between the normal to the surface and the scattered ray) depends on a probability density function. For cosine importance sampling, this probability depends on cos(theta). This is the case implemented in the basic smallpt. Multiple rays should be scattered for each hitting point, and their contribution needs to be calculated to return the color value of the specific pixel.

Problem

Looking at how rays are scattered, this doesn't actually happen in the smallpt code. Multiple rays per pixel are shot at slightly different positions. That means, they don't always land in the same spot on the surface. For this reason, the image posted above does not represent what is happening. Indeed, it is not true that multiple rays are scattered FROM EVERY HITTING POINT, but multiple rays are shot for each pixel. Is my interpretation correct?

Let me first address some misconceptions you have:

  the theory states that we need to shoot x number of rays for each
  intersection

No, the "theory" doesn't state such a thing. Note also that the paper @gallickgunner is referring to is inapplicable in this case since smallpt is based on the rendering equation and not the limited variant present in Cook's paper. Thus you actually need to refer to Kajiya's paper or Veach's path formulation. What @gallickgunner is right about is the canceling of the cosine term (but there's a missing $\pi$ factor).

Now onto the bigger misconception you have:

  Multiple rays should be scattered for each hitting point, and their contribution needs to be calculated to return the color value of the specific pixel.

There's no such requirement, in fact Kajiya proved that scattering multiple rays at each bounce is bad since you get an exponential explosion of the ray count later down the bounce tree where the actual contribution is actually very small. In MC terms you perform splitting where the contribution is small thus wasting computational power which would be a lot more useful in reducing variance in other places. To understand why this is the case, one has to dig deeper into the theory of how raytracing works and how you estimate the rendering equation.

You start with a Fredholm integral equation of the second kind:

$$L_o(x,\omega_o) = L_e(x, \omega_o) + \int_{\Omega}{f(\omega_o,x,\omega_i)L_i(x,\omega_i)\cos\theta\,d\omega_i}$$

As long as the integral converges (which happens when the operator is a contraction, or when it is not but enough energy can escape the scene for there to be a steady state), you can find the solution as the Liouville-Neumann expansion. To do this however I'll first rewrite the equation in operator form:
$$L = L_e + TL$$
$$(I-T)L = L_e$$
$$L = (I-T)^{-1}L_e = \sum_{i=0}^{\infty}T^iL_e$$
Where the last equality holds as long as $T$ is a contraction ($||T||<1$). Note that $T^0$ represents $0$ bounces, $T^1$ represents $1$ bounce, and $T^n$ represents $n$ bounces. Thus you can look at the solution as accumulating contributions from all light paths of length $0$, $1$, $2$ etc. till infinity. Now to actually write this out explicitly it's more convenient to rewrite the rendering equation in terms of integration over all scene surface points $S$ rather than the upper hemisphere (this was actually how Kajiya derived it initially, not precisely the form below but in an equivalent form):
$$L_o(x_1\rightarrow x_0) = L_e(x_1 \rightarrow x_0) + \int_{S}{f(x_2 \rightarrow x_1 \rightarrow x_0)L_o(x_2 \rightarrow x_1) G(x_1 \leftrightarrow x_2)\,dA(x_2)}$$
Where $G$ is defined as:
$$G(x \leftrightarrow y) = \frac{|\cos\theta_x\cos\theta_y|}{||x-y||}V(x,y)$$
Where $\theta_x$ is the angle between the vector $y-x$ and the normal at $x$, and $\theta_y$ is the angle betwen the vector $x-y$ and the normal at $y$ (the cosines can be written as dot products provided you have the normals). $V(x,y)$ is the visibility function and it is 1 only if there's no surface point between $x$ and $y$ (if you shoot a ray from $x$ to $y$ the first thing you hit will be $y$), and $0$ otherwise. The visibility function is implicit in the solid angle formulation inside $L_i$ (through the ray-casting function). Now let us rewrite the operator expansion in terms of what we have above, we get:
$$L_o(x_1\rightarrow x_0) = L_e(x_1 \rightarrow x_0) + \int_{S}{f(x_2 \rightarrow x_1 \rightarrow x_0)L_e(x_2 \rightarrow x_1) G(x_1 \leftrightarrow x_2)\,dA(x_2)} + $$
$$\int_{S}\int_{S}{{L_e(x_3 \rightarrow x_2)f(x_3 \rightarrow x_2 \rightarrow x_1) G(x_3 \leftrightarrow x_2)f(x_2 \rightarrow x_1 \rightarrow x_0) G(x_2 \leftrightarrow x_1)\,dA(x_3)\,dA(x_2)}}$$
$$+ ...$$
This sum continues till infinity with iterated integrals corresponding to $T^i$, the part expanded above is $T^0L_e + T^1L_e + T^2L_e$. Note that usually you have an extra integration over the area of the pixel (then there's a factor $W$ to account for the sensor sensitivity). When you do pathtracing (what smallpt does) you're actually estimating this infinite sum of integrals through Monte Carlo (this is also the reason why Monte Carlo is employed, since the convergence doesn't depend on the dimension, which in this case is infinite). You can estimate each term in the sum by Monte Carlo integration, that is for a $n$-iterated integral your samples are really paths starting from the camera with length $n$: $x_0x_1x_2...x_{n+1}$ for a path of length $n$. Note that you do not require that you split the path for each subsequent integral.
What path tracing implementations do, is create this path $x_0x_1...x_{n+1}$ incrementally, and reuse the path for earlier terms in the sum. That means that you start by picking some point $x_0$ inside a pixel, pick some point $x_1$ in the scene compute the value of the integrand of the term $T^0L_e$ for the path $x_0x_1$, pick a point $x_2$ in the scene and compute the value of the integrand of the term $T^1L_e$ for the path $x_0x_1x_2$, and so on. In an implementation you usually use the solid angle formulation (at least for bsdf sampling), but there's not major difference, you still end up with paths of the form $x_0x_1...x_{n+1}$.

The takeaway from this is that pathtracing works with paths where, a path starts at the camera and ends at a lightsource. Using different paths that do not split (in general) to estimate the sum of integrals is usually more efficient than splitting each path into more paths at each bounce. I am not saying there's no place for splitting (actually smallpt uses it for the first few bounces for materials that refract), you just have to know when to apply it (when the contribution is large and is inadequately sampled by only 1 or a few samples). Note that the opposite of splitting is early path termination in the form of the Russian roullete - basically kill off paths with small contributions since it's not worth it wasting computational resources on those (it also lets you make your estimator unbiased, but in practice there's usually a ceiling to the number of bounces allowed, since for most scenes your estimator being "fully unbiased" is not worth it in terms of performance).


How to use trackball for rotating an camera matrix in eye frame I have a QOpenGLWidget where I use camera transformation matrix(4,4), FOV and vectors Position(4), Up(4), Forward(4). I also have an ArcBall which I can use. I managed to implement zoom and pan by modifying the Position vector. Now I want to implement rotation with arcball.
On mouseMove I compute the rotation matrix with arcball. Then I need to use this matrix for rotating the camera. Now how do I do that?
I tried multiplying or summing the camera matrix and arcball matrix but it is not working for me.

I'm assuming the rotation matrix generated from the arcball is 2D, so I think there are a few clear top level steps. But I'm not sure about the details of some of them.
First you'll need to extend the 2D rotation to 3D which should be easy.
Next you'll need to rotate the rotation matrix itself so its axis aligns with your Forward vector. I'm not certain how to do this step.
Then, use the resulting matrix to transform the Up vector and reconstruct the camera matrix using the new vector and the other values and vectors.


How can I raycast with chunks? I am attempting to implement chunks/octrees to speed up my render times. However, sometimes the walls show horizontal or vertical lines (rays hitting the inside of voxels?) or some blocks disappear altogether, although sometimes everything renders fine.

Edit: Yes, the chunks are stored fine. OctrA stands for OctreeA,  which is the chunk.
Edit: I reversed the ray for two steps after hitting a chunk. Although the glitches have gotten better, there is still the same problem.

      float cameraX = x/(float)HALFRESX -1;// -1 to 1
      struct Point3D rayd;
      rayd.x = dir.x + plane.x * cameraX;
      rayd.y = dir.y + plane.y * cameraX;

      struct Point3D delta;
      delta.x = fabsf(1/rayd.x);
      delta.y = fabsf(1/rayd.y);

      int zy = -HALFRESY;

      struct pos map;
      map.x = (char)pos.x;
      map.y = (char)pos.y;

      float sdistX;
      float sdistY;
      struct pos s;
      struct pos step;
      struct Point3D sdist;
      if(rayd.x < 0) {
        step.x = -1;
        s.x = 1;
        sdistX = (pos.x - map.x) * delta.x;
      }
      else {
        step.x = 1;
        s.x = 0;
        sdistX = (map.x + 1 - pos.x) * delta.x;
      }
      if(rayd.y < 0) {
        step.y = -1;
        s.y = 1;
        sdistY = (pos.y - map.y) * delta.y;
      }
      else {
        step.y = 1;
        s.y = 0;
        sdistY = (map.y + 1 - pos.y) * delta.y;
      }

      for(int y = 0; y < RESY; y += 1) {

        zy++;
        float cameraY = y/(float)HALFRESY - 1;
        rayd.z = dir.z + plane.z * cameraY;
        delta.z = fabsf(1/rayd.z);

        map.x = (char)pos.x;
        map.y = (char)pos.y;
        map.z = (char)pos.z;
        sdist.x = sdistX;
        sdist.y = sdistY;

        if(rayd.z < 0) {
          step.z = -1;
          s.z = 1;
          sdist.z = (pos.z - map.z) * delta.z;
        }
        else {
          step.z = 1;
          s.z = 0;
          sdist.z = (map.z + 1 - pos.z) * delta.z;
        }
#ifdef USE_OCTREE

        while( !octrA[map.x/2][map.y/2][map.z/2]) {
          if(sdist.y < sdist.x ) {
            if(sdist.y < sdist.z) {
              sdist.y += delta.y*2;
              map.y += step.y*2;
            }
            else {
              sdist.z += delta.z*2;
              map.z += step.z*2;
            }
          }
          else {
            if(sdist.x < sdist.z) {
              sdist.x += delta.x*2;
              map.x += step.x*2;
            }
            else {
              sdist.z += delta.z*2;
              map.z += step.z*2;
            }
          }
        }
        if(octr) {
          if(sdist.y > sdist.x ) {
            if(sdist.y > sdist.z) {
              sdist.y -= delta.y*2;
              map.y -= step.y*2;
            }
            else {
              sdist.z -= delta.z*2;
              map.z -= step.z*2;
            }
          }
          else {
            if(sdist.x > sdist.z) {
              sdist.x -= delta.x*2;
              map.x -= step.x*2;
            }
            else {
              sdist.z -= delta.z*2;
              map.z -= step.z*2;
            }
          }
        }

#endif
        char side; //either 0 (NS), or 1 (EW), or 2(UD)
        while( !MAP[map.x][map.y][map.z]) {
          if(sdist.y < sdist.x ) {
            if(sdist.y < sdist.z) {
              sdist.y += delta.y;
              map.y += step.y;
              side = 1; // y
            }
            else {
              sdist.z += delta.z;
              map.z += step.z;
              side = 2;
            }
          }
          else {
            if(sdist.x < sdist.z) {
              sdist.x += delta.x;
              map.x += step.x;
              side = 0;
            }
            else {
              sdist.z += delta.z;
              map.z += step.z;
              side = 2;
            }
          }
        }

Have you confirmed that objects that clip a chunk border are stored in both chunks?

Have you confirmed that octrA[map.x/2][map.y/2][map.z/2] can't point to anything weird?

In fact, what even is octrA? I assume that it's the array storing the chunks but I can't know for sure because I couldn't find it anywhere else in your code.

Other than that I'm having a bit of a hard time interpreting the problem and your code. Could you add some pictures and comments to your code?


Light Falloff through a grid I'm playing with a grid-based lighting system, where light is transported and accumulated through a grid. I initially tried attenuation based on 1/(distance*distance), but that doesn't work when the distance between each node is 1.

I tried hacks like adding an epsilon or clamping the distance, but nothing looks right. I'm sure there's something obvious I'm missing. Any guidance?

It looks to me like you're resetting the distance calculation at each grid intersection? So every time you march another grid cell you're dividing the light intensity by $gridsize^2$ ? That would explain your observed results, since dividing by $1^2$ equals no change. It won't give you the correct result though, since to get the right attenuation you need to track the total distance back to the light source and square that.

Also note that the attenuation term used in rendering is usually a bit more complicated than just $1/D^2$ - generally it's a quadratic, $1/(aD^2 + bD + c)$. While not physically correct, it's more tunable and easier to get visually pleasing results. In your case, for example, using $1/(D^2 + 1)$ would prevent the edges immediately surrounding the light from being brighter than the light itself.