Double precision in shader for better accuracy, instead of GLfloat, I bound double data and tried to use the data in shader as follow: (I just tested to draw single triangle.)

cpp.

// xyzw three vertices
double points[] = { 0.0, 0.0, 0.0, 1.0 , 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0 };

glGenVertexArrays(1, VAO);
glBindVertexArray(VAO);

glGenBuffers(1, &VBO);
glBindBuffer(GL_ARRAY_BUFFER, VBO);
glBufferData(GL_ARRAY_BUFFER, 96, points, GL_STATIC_DRAW);

int data = 0;
glEnableVertexAttribArray(0);
glVertexAttribPointer(0, 4, GL_DOUBLE, GL_FALSE, 0, (void*)data);

shader.

#version 460 core
layout(location = 0) in dvec4 vPos;

void main() {
    gl_Position = vec4(vPos);
}

What's worng with me?

(If I changed the dvec4 in the above shader to vec4, the triangle was drawn, but maybe it's not double anymore. I want to use double in shader.)

The problem is, glVertexAttribPointer(0, 4, GL_DOUBLE... doesn't do what you think it does.

Using actual double-precision vertex attributes and performing double precision computations is a very modern hardware feature (GL4/DX12) and is different from specifying the type GL_DOUBLE in the good old glVertexAttribPointer call. This always worked and does nothing else than specify the input type, i.e. the type of your vertex data in memory. All it does is make the GL convert your doubles into singles and feeding them into a normal single-precision attribute (and failing when there is none), same with other input types like GL_SHORT or GL_UNSIGNED_BYTE.

When specifying data for genuine double-precision attributes, you have to use glVertexAttribLPointer (note the L) instead. The same holds for genuine integer attributes (ivecX/uvecX), which use glVertexAttribIPointer.

Of course the answer isn't complete without some general advise, that you should really make sure you actually need double precision vertex attributes, or even double precision computation. Even on modern hardware that's still significantly slower and not what those GPUs are really made for, not to speak of the doubled memory consumption for the vertex data. More precision is not always better if it isn't actually necessary and you might be surprised what a lousy little float is able to accomplish when used well.


Perspective Correct Texture Mapping So I'm trying to correctly map my textures in my software renderer using the u, v coordinates but I can't seem to get it working. I got affine texture mapping working. This is what I can produce using it:

You can see from the "tilt" in the texture that it's not quite right. If I add more triangles to the mesh it becomes more correct. From my understanding these are not perspective correct textures. But this perspective divide thing is confusing me. I read that I needed to divide the u, v coordinates by the w component (perspective divide). I'm guessing that this is the w component from the vertex after multiplying with the projection matrix. But I couldn't get that too work. So I looked a little bit more into the problem. First, here's what is happening to one vertex of my triangles.

float4 pt1 = worldViewProj * mesh->vertices[mesh->indices[i]];
float2 uv1 = mesh->texCoords[mesh->indices[i]];
triangle.p1 = float3((pt1.x / pt1.w + 0.5f) * screen->GetScreenWidth(), (pt1.y / pt1.w + 0.5f) * screen->GetScreenHeight(), pt1.w);

I multiply it with the wVP and then do my perspective divide with x and y. The + 0.5f is to center it in homogeneous space and then multiply with the screen dimensions to get it in screen space. I then stuff the w component of the vertex as the z value so it will be sent to the triangle drawing function and can be used for things like the depth buffer.

To my understanding the z value from the vertex gets put into w after multiplying with the projection matrix. This makes sense since m32 = 1 in my projection matrix. So after multiplication with the projection matrix w = z. I first tried dividing the texture coordinates per vertex by w. Like so:

 float2 uv1 = mesh->texCoords[mesh->indices[i]] / w;

Then in the triangle drawing function I used the bary centric coordinates to interpolate across these the uv coordinates. This did not work. Since w = z. When the texture is far from the camera (ie z is a large value. With my world translations applied z = ~700) then the texture coordinates shrink a lot and in every render I just get the (0, 0) value of my texture.

But I also tried this instead in my triangle drawing function:

float2 texCoord = (texCoord1 * u + texCoord2 * v + texCoord3 * w) / z;

(Here u, v, and w are the bary centric coordinates. Each texCoord is the texture Coordinate at that vertex) The difference here is that the interpolated z value is being divided at every pixel instead of it being divided at the vertices. Either way I can't seem to get it too work. Again the z value is too large and I end up getting (0, 0).

So I'm investigating what I need to divide u and v by. Obviously I'm doing something wrong. Is it really the w component of the vertex after multiplying with the projection matrix? Is my w value wrong? Could the projection matrix be causing this? I've been googling around for awhile now... x / w and y / w are [-1, 1] (homogeneous) but z isn't [-1, 1]. Is it supposed to be? My perspective divide for x and y obviously works.

Here's how I built my projection matrix just in case it's wrong?:

float tanHalfFov = tanf(fov * 0.5f * 3.14f / 180.0f);
float s = 1.0f / (tanHalfFov * aspectRatio);
float zRange = farZ - nearZ;

// Set the projection matrix
proj.m00 = s;    proj.m01 = 0.0f;            proj.m02 = 0.0f;          proj.m03 = 0.0f;

proj.m10 = 0.0f; proj.m11 = aspectRatio * s; proj.m12 = 0.0f;          proj.m13 = 0.0f;

proj.m20 = 0.0f; proj.m21 = 0.0f;            proj.m22 = farZ / zRange; proj.m23 = farZ * nearZ / zRange;

proj.m30 = 0.0f; proj.m31 = 0.0f;            proj.m32 = 1.0f;          proj.m33 = 0.0f;

You are on the right track but what you need to do is to calculate u/w and v/w, and also 1/w for each vertex, which you interpolate linearly in screen space in your rasterizer. Then for every pixel you divide the interpolated u/w and v/w coordinates with the interpolated 1/w to get perspective correct uv-coordinates for the pixel.

The same applies to all the vertex attributes, e.g. if you need to get perspective correct color or position of vertices per pixel, then you interpolate c/w and p/w and divide those values by 1/w per pixel. Even if you don't implement software rasterizer this can be quite useful for example in ray marching of screen-space reflection implementation. I have seen people doing the ray marching for SSR in world space because they don't know how to properly interpolate position in screen space.

What old software rasterizers used to do is to perform this 1/(1/w) division only every X pixels and linearly interpolate values in-between because the division was relatively expensive operation to perform every pixel.


How to clip multiple tiled textures to polygon in Webgl / opengl I have a bunch of planes each with their own texture in a grid. Currently I am rendering these as separate planes, each with their own texture, although I could use a single plane with multiple faces.

Each color is a texture.

I have a polygon mesh with arbitrary shape that is parallel to these planes:

This shape could be completely contained within one of the planes, or larger.

I would like to texture the polygon with the overlapping textures of the planes:

How do I accomplish this clipping of the textures in three js / WebGl?

I am also open to any other WebGL solutions.

A few ideas I had:

Subdivide the polygon into faces that correspond with the overlapping planes. Then texture these faces using UV coords. I know I can get this to work, but it seems like too complicated of a solution.
Apply multiple textures to the polygon and use UV coordinates to distribute them. -- Im not sure this is possible without subdividing?

Any other ideas? Can this be accomplished with blending modes?

Quick idea:

render platforms color to screen quad
render mesh and platforms to screen quad, but as a mask. For example mesh is white, rest is black.
in another pass sample these textures and if mask is white, color it with sample from first texture. Render to screen.


An Effective way to explain Ray Tracing? In my CS class in high school I'm doing a presentation on Computer Graphics and I wanted to talk about Ray Tracing. I was wondering what would be the easiest way to do this without confusing my audience?

What are some of your personal favorite analogies and explanations that have worked effectively to people who have never touched the field?

Please don't mistake this as a 'do my homework' type question. I'm just curious to see what has worked and what hasn't.

Here's my introduction: http://www.gabrielgambetta.com/computer-graphics-from-scratch/raytracing.html It uses the somewhat contrived analogy of making a painting by putting a grid in front of a real landscape, and painting a square of the colour you see through each hole in the grid. A raytracer is essentially that, but with some linear algebra :)


Unfold a 3D mesh to a 2D plane I'm trying to unfold a 3D mesh onto a 2D plane. My general idea to do this, would be to cycle through all the faces of the meshes and perform a hierarchical transformation.

So I would start at the first face and transform it's vertices to the plane, then go to the next face and transform the vertices, that were not already transformed (since the mesh consists of triangles, each face shares 2 vertices with the next triangle) with the transformation of the last face and then add another transformation to get it to the plane.

The problem is I don't really have an idea how to calculate the transformation matrices.
Can someone help me?
Thanks.

When performing the unfolding the way you want, after you have unfolded one triangle in the plane, the next one should be one of the three triangles, adjacent to the unfolded one, i.e. the next triangle to be unfolded shares a common edge with the unfolded one.
Assume you have a triangle $ABC$ in three space with vertices  $$A = [A_1, A_2, A_3], \,\, B = [B_1, B_2, B_3],\,\, C = [C_1, C_2, C_3]$$ which is one of the triangles from the 3D mesh.
If $ABC$ is the first triangle you are starting the unfolding with, then:

calculate $l_{AB} = ||A - B|| = \sqrt{(A_1 - B_1)^2 + (A_2 - B_2)^2 + (A_3 - B_3)^2}$;
set the 2D vertices $a = [0,0]$ and $b = [l_{AB}, 0]$ as well as $$l_{ab} = l_{AB};

Else if $ABC$ is a next triangle to be unfolded in the plane, i.e. you have already unfolded one of $ABC$'s adjacent (neighboring) triangles, therefore one of $ABC$'s edges is already unfolded in the plane. Say that this edge is $AB$ and it is unfolded in the plane as the edge with vertices $a = [a_1, a_2]$ and $b = [b_1, b_2]$, where $l_{ab} = ||a-b|| = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2} = ||A-B|| = l_{AB}$.
Either way, for the triangle $ABC$ you already have the edge $AB$ unfolded as $ab$ in the plane, so that $l_{ab} = l_{AB}$ (i.e. you already know $a, \, b$ and $l_{ab}$). The question is, how do you find the coordinates of the third vertex $c = [c_1, c_2]$ so that $l_{bc} = l_{BC}$ and $l_{ca} = l_{CA}$? We impose the latter two conditions because two triangles that have pairwise equal edge-lengths are congruent (isometric, i.e. identical copies of each other).
For your information, I will write vectors like $B - A = [B_1 - A_1, \, B_2 - A_2, \, B_3 - A_3]$ and $C - A = [C_1 - A_1, \, C_2 - A_2, \, C_3 - A_3]$ and $b-a = [b_1 - a_1, b_2-a_2]$ and will use dot product $\cdot$ and cross product $\times$ between vectors. You already know what $||B-A|| = l_{AB}$ and $||C-A|| = l_{CA}$ are and that $l_{AB} = l_{ab} = \|b-a\|$.

Calculate $$s = \frac{\|(B-A)\times(C-A)\|}{l_{ab}^2}$$

Calculate $$c = \frac{(B-A)\cdot(C-A)}{l_{ab}^2}$$

Calculate both pairs of coordinates
\begin{align}
&c'_1 = a_1 + c(b_1-a_1) - s(b_2 - a_2)\\
&c'_2 = a_2 + c(b_2-a_2) + s(b_1 - a_1)
\end{align}
and
\begin{align}
&c''_1 = a_1 + c(b_1-a_1) + s(b_2 - a_2)\\
&c''_2 = a_2 + c(b_2-a_2) - s(b_1 - a_1)
\end{align}

You have two candidate points $c' = [c'_1, c'_2]$ and $c'' = [c''_1, c''_2]$

Perform a check whether $c'$ is on the same side of the edge $ab$ as the  triangle unfolded right before $ABC$.

If it is not, then $c = c'$
else if it is, then $c = c''$
As a result of this procedure, you have constructed the planar unfolding $abc$ of triangle $ABC$ and the next triangle from the 3D mesh to be unfolded (if any), should be the one that shares either edge $BC$ or $CA$ with $ABC$. Either way, for that next triangle, you already know the unfolding $bc$ of the edge $BC$ and the unfolding $ca$ of $CA$ (whichever is relevant), so you can apply the same procedure for that next triangle. And so on and so forth, until you have unfolded all triangles from the mesh.
Have in mind that there are 3D meshes that do not posses unfolding that do not self overlap, no matter what you do. For such meshes there no greedy algorithms or any other algorithm that can do it.


Why do I need memory barrier when doing atomic operations? I am reading the OpenGL SuperBible 7th edition which covers atomic operations on memory specifically within shader storage blocks.

It says (about atomic operations):

  If two invocations access the same memory locations... then they will be serialized and only one will get to go at one time.

Great. However, it then goes on to cover Synchronizing Access to Memory specifically and the use of glMemoryBarrier

As I understand it, you need to use glMemoryBarrier once you start writing to buffers from shaders.

However, the distinction is not made clear to me about why I need to use a barrier if the operations I am doing within my shader are atomic operations.

It's possible I am conflating atomic operations and general memory access, but, in the book the line is not clearly drawn.

When is it that a glMemoryBarrier is required? Is it everytime a shader writes to memory (whether the operations are atomic or not)?

glMemoryBarrier is for when you want to make writes from one rendering command visible to reads from a subsequent rendering command.

That is, you can do all the atomics you like during a rendering command. But without the barrier, there's no guarantee that any of those atomic actions will be visible to later commands. Yes, they will still be atomic, but this only ensures that they will each execute in some order and each operation will fully execute before the next. What they won't ensure is that operations which OpenGL defines has happening "later" will execute before earlier operations.

Sometimes, you actually don't care about the order of the operations; being atomic may be enough. And sometimes, you do care.

Consider the case of a "linked-list" style blending buffer. Each pixel in the image is an integer that represents one of the items in the list. Each FS invocation will use an atomic increment to get a unique identifier, then swap that identifier with the current value in the image. It writes its pixel data to the entry in an SSBO, along with the identifier it swapped out of the image.

When doing that atomic increment on the unique identifier, you don't care if FS invocations from two different rendering commands execute out of order. You simply need the operation to be atomic. Similarly, the swap doesn't have to be in order; it just needs to be atomic. As long as they all execute, and the atomic operations do their jobs, then they will be fine.

Now, when it comes time to do blending based on this data, that is when you need to be able to read all of the data that was previously written. And that rendering operation requires glMemoryBarrier.

Of course, you're not necessarily using atomic operations to read these values.


Wrong color in .ppm file I'm going through the rasterizer tutorial from Scratchapixel, but I encountered a problem with the generation of the .ppm file. Since something was off, I reduced the example to the bare minimum, so I currently simply generate a 512x512 image of a plain color.

#include <fstream>

using Rgb = unsigned char[3];
int main()
{
    const uint32_t w = 512;
    const uint32_t h = 512;

    Rgb *framebuffer = new Rgb[w * h];
    for (uint32_t j = 0; j < h; ++j) {
        for (uint32_t i = 0; i < w; ++i) {
            framebuffer[j * w + i][0] = static_cast<unsigned char>(255);
            framebuffer[j * w + i][1] = static_cast<unsigned char>(0);
            framebuffer[j * w + i][2] = static_cast<unsigned char>(0);
        }
    }

    std::ofstream ofs;
    ofs.open("./example.ppm");
    ofs << "P6\n" << w << " " << h << "\n255\n";
    ofs.write((char*)framebuffer, w * h * 3);
    ofs.close();

    delete[] framebuffer;

    return 0;
}

The code above should generate a red square image, but if I open the file with Gimp, I get a green image.

Do you have any idea of what's happening?

EDIT: This is the .ppm file with a hex editor:

The issue is that on your system, writing out "\n" is writing out 0x0D0A, whereas on my system, it's only writing out 0x0A. If you explicitly write out 0x0A instead of "\n" I think it will work for you.

Here's a hex dump on macOS Mojave:

50 36 0A 35
31 32 20 35
31 32 0A 32
35 35 0A
FF 00 00 // <- pixels start here
FF 00 00
FF 00 00
FF 00 00
FF 00 00
FF 00 00


What is the cost of changing state? Programmers are supposed to have a fairly good idea of the cost of certain operations: for example the cost of an instruction on CPU, the cost of a L1, L2, or L3 cache miss, the cost of a LHS.

When it comes to graphics, I realize I have little to no idea what they are. I have in mind that if we order them by cost, state changes are something like:

Shader uniform change.
Active vertex buffer change.
Active texture unit change.
Active shader program change.
Active frame buffer change.

But that is a very rough rule of thumb, it might not even be correct, and I have no idea what are the orders of magnitude. If we try to put units, ns, clock cycles or number of instructions, how much are we talking about?

The most data I've seen is on the relative expense of various state changes is from Cass Everitt and John McDonald's talk on reducing OpenGL API overhead from January 2014.  Their talk included this slide (at 31:55):

The talk doesn't give any more info on how they measured this (or even whether they're measuring CPU or GPU cost, or both!).  But at least it dovetails with the conventional wisdom: render target and shader program changes are the most expensive, uniform updates the least, with vertex buffers and texture changes somewhere in the middle.  The rest of their talk also has a lot of interesting wisdom about reducing state-change overhead.


Best way to group 3d points into planes, if any If I have some 3d points, how can I discover parallel planes within them (not just arbitrary planes).

I want to know how many "levels" or "floors" something can travel within, after it has done so, so I want to cluster the positions into planes.

Some of them might not be in a plane, most of them are noisy (not perfectly planar), and I have no knowledge of the world orientation, so the planes aren't necessarily orthogonal to some known axis.

I know one way is a 3d-hough transform, but is there something better?

A reasonable approach is a continuous sample consensus method. The hough transform can be though of as a discrete sample consensus method, and so becomes intractable for some problems. Sample consensus is nice, because we can impose arbitrary constraints, and handle even the most horrific noise.

Getting Planes: Sample Consensus

The idea is determine the minimum number of observations needed to form a hypothesis, and then check how many observations agree with that hypothesis. We'll call those observations "inliers".

Three point determine a plane. Select three points (deterministically, at random, whatever) from your dataset, fit a plane to them.
Check how many points in your point cloud "support" the plane. Meaning that the plane existing in the world could explain what the sensor saw; the observations "support" the conclusion that the plane exists. For your case, a reasonable metric for "support" would be perpendicular distance to the plane.
In postprocessing, you might cull planes that don't have sufficient width.

Extracting Parallel Planes: Normal Binning

If you don't have a prior on the structure of your data other than "has parallel planes", then you're likely trapped trying to discover as many planes as possible and then filtering for parallel ones.

One might consider a "binning" approach

Start with the first plane, and say its normal belongs to $bin_0$
For each discovered plane, check the angle it makes with every existing bin
If the angle is less than $\epsilon$, add that plane to $bin_n$
If the angle is greater than (or equal, for completeness) to $\epsilon$, create a new bin, $bin_{n+1}$

Presumably the largest bin is the thing you want if you have culled small planes.

Other Notes

Sample consensus will generally perform better if, after fitting to data and finding points that agree, you run a quick optimization to fit a plane to all of the inlier points. Then recompute inliers, and re-run the optimization. After all, it's quite unlikely that the three points you happened to choose were exactly the true plane. Much more likely is that varying plane parameters to minimize point-to-plane error over all of the inlier observations will yield a nice plane, with the noise averaged out.


Signed distance field font looks odd I attempted to implement font rendering using signed distance fields.

My program first generates a mono bitmap at font size 64 (using FreeType), then generates an SDF from the bitmap. This is then uploaded into a texture atlas.

The results are not very nice and look nothing like the various papers show:

My guess is that the bitmap does not have a high enough resolution, but
I do not necessarily want to generate SDF's larger than 64px (they have to fit in the atlas). Besides, at 256px, the generated sdf still has artifacts, albeit less noticable unless blown up.

So how can I get better results / how am I applying the algorithm wrong?

Hmm, that SDF doesn't look right. It should be much smoother, like this image for instance:

(image from this blog).

One possible issue I noticed in your description:

  My program first generates a mono bitmap at font size 64 (using FreeType), then generates an SDF from the bitmap.

The initial text needs to be rendered at a much higher resolution than the resulting SDF, so you can get subpixel precision in the distances stored in the SDF. For example, in the original Valve paper, they render the initial mono bitmap at 4096×4096 in order to generate a 64×64 SDF from it.


total internal reflection implementation in pbrt-v3 I've been implementing a path tracer, referring pbrt-v3. However, I'm a bit confused about its implementation. Code is here.

It seems when we sample to do transmission, it tests if it meets a total internal reflection, but it doesn't assign a proper value to the pdf, instead, after the function returns Vec3f(0,0,0) as BTDF value, it then tests if pdf is 0, if 0 then directly jumps out of the tracing loop.

I don't think this make sense since there should be radiance value if this ray continues to trace and does out of the specular object and hit a surface which is illuminated. But this implementation seems to leave out all such kind of radiance, and rely on the sample_f function to sample a reflection.

So how to properly compute the pdf of total internal reflection?

        // Account for the indirect subsurface scattering component
        Spectrum f = pi.bsdf->Sample_f(pi.wo, &wi, sampler.Get2D(), &pdf,
                                       BSDF_ALL, &flags);
        if (f.IsBlack() || pdf == 0) break;

The code does seem a bit ugly since it doesn't assign pdf and instead returns 0.

By returning 0 it's basically saying the same thing as pdf = 0 because f.IsBlack() returns true.

This is acceptable, it's basically saying the BSDF doesn't allow light go through at the given $w_o$


R16_FLOAT, SampleCmp and CheckFormatSupport I want to use PCF shadow map on my d3d11 app. My shadow map is an R16_FLOAT texture. When I use SampleCmpLevelZero it didn't give a correct result. After enabling debug layer, it shows:

  The Shader Resource View in slot 1 of the Pixel Shader unit is using the Format (R16_FLOAT). This format does not support 'SampleCmp' or 'SampleCmpLevelZero', at least one of which is being used on the Resource by the shader. This mismatch is invalid if the shader actually uses the view (e.g. it is not skipped due to shader code branching).

But when I query whether the format support SampleCmp using the code below, it returns 0 which means success. Can someone explain why?

bool Renderer::InitRenderer(HWND hwnd)
{
    if (!InitD3D11App(hwnd)) return false;
    InitViewport();

    UINT formatSupport = D3D11_FORMAT_SUPPORT_SHADER_SAMPLE_COMPARISON;
    printf("Support?\n");
    HRESULT hr = d3d11Device->CheckFormatSupport(DXGI_FORMAT_R16_FLOAT, &formatSupport);
    printf("result: %d\n", hr);
    if (!SUCCEEDED(hr))
    {
        printf("Nope!\n");
        return false;
    }

    return true;
}

Because I was using the CheckFormatSupport wrong. The second parameter is supposed to be an input.

Here is what it should be like.

bool Renderer::InitRenderer(HWND hwnd)
{
    if (!InitD3D11App(hwnd)) return false;
    InitViewport();

    UINT formatSupport;
    HRESULT hr = d3d11Device->CheckFormatSupport(DXGI_FORMAT_R16_FLOAT, &formatSupport);
    if (!SUCCEEDED(hr) || !(formatSupport & D3D11_FORMAT_SUPPORT_SHADER_SAMPLE_COMPARISON))
    {
        printf("Not supported!\n");
        return false;
    }

    return true;
}

https://www.gamedev.net/forums/topic/700419-r16_float-samplecmp-and-checkformatsupport/?tab=comments#comment-5397459


What is a 0 "null" normal map? Or Unlit shader Does anyone understand normal maps and what would color a uniformly 0 normal map be?

I'd like to convert a standard shader into an unlit shader, so (I think?) the idea is that the normal map should not contribute to the lighting.

In the most common normal map encoding, an RGB value of (0.5,0.5,1) would be uniformly flat. If the shader is meant to be unlit, you should be able to remove anything in the code that’s using the surface normal, light / view direction, etc.


Detect a lossy matrix decomposition? I am writing a plugin to export data from 3DS Max. 3DS Max's geometry pipeline is... interesting.

As part of my plugin I decompose a transform matrix into a translation, (quaternion) rotation & scale using an inbuilt function.
This of course does not always work, such as when a shear is present.

Max does have an affine decomposition function, but I don't want to use that because the resulting components do not all have an analogue in the destination application.

What I'd like to do, is detect when the decomposition is lossy, so I can bake the geometry for the object which uses it, before transmitting it.

How can I determine, either before or after, whether a matrix TRS decomposition is exact?

You can detect a matrix that can't be decomposed in TRS form by taking its 3×3 upper-left submatrix, interpreting its columns as vectors, and dotting them together in all combinations (1 with 2, 2 with 3, and 1 with 3). For a TRS matrix, the three dot products should all be zero, i.e. the column vectors should be orthogonal to each other. If any of the dot products are nonzero (beyond some epsilon to account for roundoff error) then the matrix is not decomposable as TRS.

This derives from the property that a rotation matrix is an orthogonal matrix, i.e. its column vectors form an orthonormal basis. When you multiply the rotation by a scaling matrix, the column vectors may no longer be unit vectors, but they should still be orthogonal. And the translation part doesn't affect the rotation-scaling part.


Performance of particle implementation I am about to implement the renderer for a simple particle system. Every particle has to be updated every frame (position, rotation, scale) and so I was wondering which way is usually faster:

Calculate translation, rotation, scale and update the final positions in the vertexbuffer.
Calculate translation, rotation, scale into one transformation matrix and send that one to the GPU Shader for each particle.

Updating the position/rotation/scale in the vertex buffer will use less memory bandwidth—that’s 9 values, where a transform matrix would be either 12 or 16—and the GPU can parallelize the work of turning the position/rotation/scale into a transform for the vertices. I’d go with 1.


Hardware-accelerated drawing of curved shapes How to quickly draw a curved shape?

by "quickly" I presume one should use hardware facilities as much as possible
by "curved" I mean boundaries defined by either quadratic or cubic Bezier curves
by "shape" I mean either a "fat" stroke (i.e. more than 1px wide) or even-odd/non-zero filled "2D curved polygon", possibly with holes (i.e. letter "O")

I'm asking because the options I know of have several drawbacks:

triangulating the shape and sending it to OpenGL - does the most difficult work on CPU and might use too many/few triangles (i.e. wasteful/coarse)
texture atlas - has to recompute/upload the texture on every change (shape, scale, rotation, ...)
Signed distance field - on large scales the details don't look pretty or has to recompute/upload the texture
NV_path_rendering - could be it, if it was not working only on Nvidia's cards
OpenVG - could be it, if it was not working only on mobile
?

* It seems to me that OpenVG is not exactly moving forward, to put it mildly. Does anyone know anything about its future prospects? Is it worth at all to keep an eye on in the present day?

** OpenGL 4+ provides means of on-fly tessellation of polygons. Could it be somehow used to refine the the mesh from the "triangulating" option so that the shape boundary at least wont look "angled"?

You can use OpenGl 4.x tessellation shaders to convert Bezier control points into polygons.

A google search for "tessellation shader bezier" found this outline describing the tessellation of Bezier surfaces and curves:

http://web.engr.oregonstate.edu/~mjb/cs519/Handouts/tessellation.1pp.pdf

This offloads the Bezier evaluation from the CPU to the GPU and reduces the data flow across the bus.


Bresenham's algorithm next pixel? In line drawing, bresenham's algorithm was explicitly derived for lines with slopes between 0 and 1 in the first octant from point P1 to point P2, where the x value of P1 is less than that for P2.

In the incremental version of this algorithm, once a pixel is drawn, we need to choose the next pixel to draw.

What are the choices? How do we go about choosing which pixel to draw next? (assuming a line width of 1 pixel)

Well, for the first octant you can either step EAST or NORTH-EAST. Depending on the distance to the actual line you choose the appropriate. In many integer implementations, this is done with regard to the sign of D.


How are digital painting canvas rendered? Digital painting and raster graphics software like Krita and Photoshop have a canvas where you can paint with brushes. From a programming perspective, how is this canvas rendered? Can it be included on a graphics pipeline like OpenGL?

One proposed solution is to represent the canvas as a texture. If you know more possible solutions let me know. Thanks.

Digital painting and raster graphics software like Krita and Photoshop have a canvas where you can paint with brushes. From a programming perspective, how is this canvas rendered?

I don't have access to the code of the programs you mentioned, so I can't tell how exactly they did this since there are usually multiple ways to solve a programming problem. However, I guess everybody with some graphics programming experience will immediately think of the solution @lightxbulb already mentioned in his comment because it is the simplest one.

Textures are just an array of color values and a graphics API like OpenGL expects you to upload them as such. So a possible solution would be to represent your modifiable canvas in memory in this form too. Every time a modification is made, you find the affected pixels in your array, adjust their color values, and upload the updated canvas as texture (or update the already existing one). Then you just draw a fullscreen (or any other size you like) quad and attach the texture to it. Simple as that.

  Can it be included on a graphics pipeline like OpenGL?

As you might already guess: Yes, you can do that. If you use the texture approach, you can do anything you can do with an ordinary texture in the graphics pipeline. If your intention is to include a canvas in a 3d game, then keep in mind that finding the pixel that should be modified gets a little bit more complicated due to the perspective projection. However, the rendering process stays the same.


Understanding fragment shader coordinate system I'm trying to create an infinitely panable grid using fragment shaders (C++/OpenGL/GLSL), and I'm having a bit of difficulty understanding the coordinate system.
This is my fragment shader code, ported over from an example on ShaderToy:
#version 460 core

layout(location = 0) out vec4 color;

in vec2 v_Resolution;   // window size in pixels             [1000, 618]
in vec3 v_CamPos;       // camera position in pixels         [0, 0, 0]
in float v_CellSize;    // grid cell size in pixels          [50]

// TODO: make these variables in
float lineWidth      = 1.f;         // The width of each line (in pixels).
float darkenMultiple = 5.f;         // Multiple of which lines are darkened (e.g. every 5th line).

void main() {

    float width = lineWidth / v_CellSize;

    vec2 uv = vec2(gl_FragCoord.x, gl_FragCoord.y / v_Resolution.y + v_Resolution.y / 2 - v_CellSize / 2);

    uv.x *= 1.0 / v_CellSize;
    uv.y /= v_CellSize;

    // Adjust the origin of each line thicker than one pixel to its center.
    uv.xy += (lineWidth > 1) ? width * 0.5 : width;

    // Make the grid resolution independent by offsetting the Y coordinates based on the current viewport height.
    uv.y -= gl_FragCoord.y / v_CellSize;

    // Apply camera translation.
    uv.x += v_CamPos.x / v_CellSize;
    uv.y -= v_CamPos.y / v_CellSize;

    float grid = 0.0;
    grid = max(step(fract(uv.x), width), grid); // X lines (horizontal)
    grid = max(step(fract(uv.y), width), grid); // Y lines (vertical)

    vec4 col = vec4(grid);

    if (col.r != 0.0 && col.g != 0.0 && col.b != 0.0) {

        float mx = mod(uv.x, float(darkenMultiple));
        float my = mod(uv.y, float(darkenMultiple));

        // Make lines that are a multiple of `darkenMultiple` darker than the rest.
        col.a = (mx < width || my < width) ? 0.2 : 0.15;
    } else {
        // Turn all pixels that aren't apart of the grid invisible as to not cover the rest of the scene.
        col.a = 0.0;
    }

    color = col;
}

Everything in this code functions as intended, until I try to translate the entire grid (grid lines) to the center of the screen by adding v_Resolution.x / 2 to uv.x.
I believe the part that's tripping me up is when I normalize gl_FragCoord to uv by dividing it by the screen size (v_Resolution).
From this question I know why gl_FragCoord is normalized, but I don't understand why in this case uv.x = gl_FragCoord.x while uv.y = gl_FragCoord.y / v_Resolution.y. Why would I divide the y-component by the screen height, but not the x-component by the screen width? If I try to divide gl_FragCoord.x by the screen width, the entire shader breaks, and the grid columns are not rendered. This is especially strange to me, because in the ShaderToy example, the coordinates are not normalized at all, and it functions perfectly fine! I feel like I'm missing a very important concept here.
The entire code can be downloaded and compiled (Windows, OpenGL 4.5) from my GitHub repo: https://github.com/wooandrew/boomerang/tree/develop
EDIT:
Okay, I was able to get the translation working as intended, but I'm still confused on the normalized UV as well as the coordinate system of UV.
My solution (simplified):
vec2 uv = vec2(gl_FragCoord.x - (v_Resolution.x / 2.f), (gl_FragCoord.y / v_Resolution.y) + (v_Resolution.y / 2.f));

Now, if I remember correctly, the origin in a GLSL fragment shader is bottom left, so why do I have to subtract v_Resolution.x / 2.f instead of adding it? (also, why is the x-component not normalized, like the y-component?)

Everything in this code functions as intended, until I try to translate the entire grid (grid lines) to the center of the screen by adding v_Resolution.x / 2 to uv.x.

Not sure what your intention is here since the Shadertoy example you referenced generates an infinite grid. So maybe you can clarify that.
However, I think I can help you with this problem:

... the ShaderToy example, the coordinates are not normalized at all, and it functions perfectly fine! I feel like I'm missing a very important concept here.

I think the basic problem here is, that you do not really understand how the mesh is generated and why the Shadertoy example isn't normalizing the uv-coordinates. If I can help you understand it, you can probably fix your other problems by yourself.
So let's walk through the Shadertoy code and what it actually does:
vec2 uv = fragCoord.xy;

// Correct the coordinates by taking into account the aspect ratio (turns the grid into perfect squares).
uv.x *= 1.0 / spacing;
uv.y /= spacing;

Here you first copy the frag coordinates into uv and afterward divide it by the spacing of your lines. Not sure why the author used those 'complicated' last two lines, but you can replace them simply with uv /= spacing;.
The purpose of this step is to transform into a new space where the lines of your grid are located at every whole number. If your spacing is 20, like in the shader toy example, only the fragments with one of its frag coordinates being one of 0, 20, 40, etc. would produce a whole number and would be located on a line. Maybe you can already see where this is going.
// Adjust the origin of each line thicker than one pixel to its center.
uv.xy += (lineWidth > 1) ? width * 0.5 : width;

// Make the grid resolution independent by offsetting the Y coordinates based on the current viewport height.
uv.y -= (iResolution.y - 600.0) / spacing;

// Apply camera translation.
uv.x -= translation.x / spacing;
uv.y += translation.y / spacing;

Here he is just translating the grid to consider several things like line thickness and camera position. The camera position is probably what you are interested in. I have no clue, about the purpose of the second line, even though the comment specifies it, but it is just a y-shift of your grid. However, note that all translations must be in the "grid-space" like the uv coordinates. Hence he always divides by spacing. For width, he already applied the transformation several lines above -> float width   = float(lineWidth)   / spacing;
float grid = 0.0;
grid = max(step(fract(uv.x), width), grid); // X lines (horizontal)
grid = max(step(fract(uv.y), width), grid); // Y lines (vertical)

vec4 col = vec4(grid);

Now here comes the magic that actually produces the grid. Let's dissect the second line. fract(uv.x) just returns the fractional part of uv.x. So a value of 12.125 is reduced to 0.125. The step function returns 0 if the second value is smaller than the first and 1 otherwise. So the point of step(fract(uv.x), width) frac is to get a 1 if the uv coordinate is on a vertical line and 0 if not. The max in this line is pretty pointless since grid (which is set to 0.0) is either equal to the returned value or less. The third line does the same thing for horizontal lines, but here the max is actually needed.
So to sum it up, grid is 1 if the fragment lies on a horizontal and/or vertical line and 0 if not.
The last line just turns that into a vector. So you either get pure white ((1.0, 1.0, 1.0, 1.0)) as pixel color if the fragment is part of a line or pure black ((0.0, 0.0, 0.0, 0.0)) if not. Note that if alpha blending is enabled, black is actually translucent since the alpha channel is also 0.
if (col.r != 0.0 && col.g != 0.0 && col.b != 0.0) {
    float mx = mod(uv.x, float(darkenMultiple));
    float my = mod(uv.y, float(darkenMultiple));

    // Make lines that are a multiple of `darkenMultiple` darker than the rest.
    col.a = (mx < width || my < width) ? 0.2 : 0.15;
} else {
    // Turn all pixels that aren't apart of the grid invisible as to not cover the rest of the scene.
    col.a = 0.0;
}

col = showNyanCat(col, fragCoord);

fragColor = col;

This just adjusting the color of the grid and plotting the cat and not relevant to your question.
I optimized the shader from the Shadertoy example a little bit by removing obsolete instructions, postponing the transformation into "grid space" after applying the translations, and vectorizing some operations. Maybe it makes it easier for you to understand what is happening. I kept the original comments and added some own ones:
void mainImage( out vec4 fragColor, in vec2 fragCoord ) {
    // Define some variables we use ---------------------------------------------
    // Simulate camera translation, just for this example.
    vec2 velocity = vec2(-30.0, 10.0);
    translation += scale * iTime * velocity;

    float spacing = float(lineSpacing) * scale;
    float width   = float(lineWidth)   / spacing;

    // Add all translations to uv -----------------------------------------------
    // Apply camera translation.
    vec2 uv = fragCoord - translation;

    // Make the grid resolution independent by offsetting the Y coordinates based on the current viewport height.
    uv.y -= (iResolution.y - 600.0);

    // Adjust the origin of each line thicker than one pixel to its center.
    uv += (lineWidth > 1) ? float(lineWidth) * 0.5 : float(lineWidth);

    // Transform to "grid space" ------------------------------------------------
    // Correct the coordinates by taking into account the aspect ratio (turns the grid into perfect squares).
    uv /= spacing;

    // Identify if pixel is on a line -------------------------------------------
    float grid =     step(fract(uv.x), width)       ; // X lines (horizontal)
    grid       = max(step(fract(uv.y), width), grid); // Y lines (vertical)

    // Set the correct color ----------------------------------------------------
    vec4 col = vec4(grid);
    if (grid != 0.0) {
        float mx = mod(uv.x, float(darkenMultiple));
        float my = mod(uv.y, float(darkenMultiple));

        // Make lines that are a multiple of `darkenMultiple` darker than the rest.
        col.a = (mx < width || my < width) ? 0.2 : 0.15;
    }

    // Plot the cat -------------------------------------------------------------
    col = showNyanCat(col, fragCoord);

    fragColor = col;
}

In this version, you can simply add your translations in pixels without any need to transform them to "grid space" or to normalize them. Hope that helps. You can copy it into the Shadertoy example to see that the results are the same.

Now, if I remember correctly, the origin in a GLSL fragment shader is bottom left, so why do I have to subtract v_Resolution.x / 2.f instead of adding it?

Probably because you use different signs here:
// Apply camera translation.
uv.x += v_CamPos.x / v_CellSize;
uv.y -= v_CamPos.y / v_CellSize;

(also, why is the x-component not normalized, like the y-component?)

I guess you fiddled around until "something" produced the expected image rather than knowing what happens. I see no point in investigating the "why" here. Understand the Shadertoy code (or my version) and then apply your changes while actually knowing what you are doing. If you use my version, all you have to add are the translations in pixels that you want to apply.

Update
Regarding the comment of Andrew Woo:

I really appreciate the in-depth explanation, it helped a lot in my understanding, however it doesn't really answer my [original] question, which was why the x-component of uv isn't normalized.

I was addressing that at the end of the original answer when I said that you fiddled around until "something" worked and I didn't saw any point in investigating why "obviously wrong" code produces the correct result.
Well, let's get something clear: uv coordinates are not screen coordinates. So gl_FragCoord.y / v_Resolution.y is not the general definition of v. I would rather call them "normalized screen coordinates". uv coordinates are (usually) used to map regular 2-dimensional data like an image onto a surface. You can read more about them on Wikipedia. Don't be fooled by the fact that the author of the question you linked used the "normalized screen coordinates" as uv coordinates. They might be the same if you want to map an image to your screen, but usually, they are not.
In the shadertoy example, the uv coordinates are used to map a single cell of your grid. You start using uv coordinates of the grid after you divided the frag coordinates by the cell size. Before that, they are no uv coordinates, at least not in relation to the grid.
So let's summarize what the shader does: You start with pixel coordinates inside your shader with values between 0 and the screen resolution in either direction and you want to calculate the uv coordinates of the grid in order to draw it. That's the whole purpose of the code we discussed. Do we need to divide by the screen resolution for that? No, we don't. We could if it would make our life easier to get from A to B, but we simply do not need it here and the original shadertoy algorithm doesn't do it.
So the question shouldn't be "why the x-component of uv isn't normalized" but:
"Why do I get the correct result when I use normalized screen coordinates instead of fragment coordinates for the y-component and wrong ones if not"?
I have not tested your code, but by just looking at it, I would say by normalizing the y component here: (gl_FragCoord.y / v_Resolution.y) + (v_Resolution.y / 2.f) you are more or less "removing" them from the line. Just insert the numbers:

gl_FragCoord.y / v_Resolution.y is a number between 0 and 1
v_Resolution.y / 2.f is 309

So at this point, you have v-values between 309 and 310. It is almost a constant. Simply remove gl_FragCoord.y / v_Resolution.y and you should still get the same result. Now the question arises, why is the grid still rendered correctly? I guess because of this line:
// Make the grid resolution independent by offsetting the Y coordinates based on the current viewport height.
    uv.y -= gl_FragCoord.y / v_CellSize;

Note that you use gl_FragCoord.y while the Shadertoy code used iResolution.y, which is a constant. What you do here is correcting the effective removal of gl_FragCoord.y I explained before. You need to divide by v_CellSize because the uv coordinates were also divided by v_CellSize 2 instructions before (uv.y /= v_CellSize;).
How to correct it?
Simply remove this line:
uv.y -= gl_FragCoord.y / v_CellSize;

Then remove the division through v_Resolution.y from here:
vec2 uv = vec2(gl_FragCoord.x, gl_FragCoord.y / v_Resolution.y + v_Resolution.y / 2 - v_CellSize / 2);

It should look like this:
void main() {

    float width = lineWidth / v_CellSize;

    vec2 uv = vec2(gl_FragCoord.x, gl_FragCoord.y + v_Resolution.y / 2 - v_CellSize / 2);

    uv.x *= 1.0 / v_CellSize;
    uv.y /= v_CellSize;

    // Adjust the origin of each line thicker than one pixel to its center.
    uv.xy += (lineWidth > 1) ? width * 0.5 : width;

    // Apply camera translation.
    uv.x += v_CamPos.x / v_CellSize;
    uv.y -= v_CamPos.y / v_CellSize;

    float grid = 0.0;
    grid = max(step(fract(uv.x), width), grid); // X lines (horizontal)
    grid = max(step(fract(uv.y), width), grid); // Y lines (vertical)

    vec4 col = vec4(grid);

    // ... insert rest of your code
}

Now you should have the "correct" result and the x and y components are treated identically.


How does a GLSL Sampler2D read a Vec2 UV coordinate to determine UV range I am working with an atlas shader that steps through various sprite tiles within a single png atlas page to playback an animation with sampler2D.  Looking at the shader code, I would expect to have to define a lower left and upper right point for each image area on the atlas image that I want to use for that frame.  However, it simply uses a Vec2 which is just a single x,y value.  How is this possible?  How is a single vec2 defining both position and range of the sampled area?  In a more broad sense how are these UV vec2s from varying UVs being interpreted in GLSL in general?  To me, you can't define an image area from just a vec2 so I am really confused???

It's hard to say without seeing the shader in question. My guess is that every animation frame in the atlas has the same size. This fixed size allows mapping any UV coordinates to the proper animation frame's UV extents.

For example, with 16 frames in a texture:

0 0.25 0.5 0.75 1.0
\  \   |   /  _/
 +--+--+--+--+
 | 0| 1| 2| 3|
 +--+--+--+--+ 0.25
 | 4| 5| 6| 7|
 +--+--+--+--+ 0.5
 | 8| 9|10|11|
 +--+--+--+--+ 0.75
 |12|13|14|15|
 +--+--+--+--+ 1.0

This code should do the trick to convert UV coordinates (range [0, 1]) to a given frame's UV extents:

vec2 uv = ...
uint frameId = ... // [0, 15]
const uint rowFrameCount = 4; // implies frameUVWidth = 1 / 4 = 0.25
const vec2 frameUVSize = vec2(1.0 / rowFrameCount, 0.25);

// Find the column and row offset
uvec2 frameOffset = uvec2(frameId % rowFrameCount, frameId / rowFrameCount);

// Offset to the proper column
uv += frameOffset;

// Scale the coordinates in the range of a single frame (here [f_0, f_0 + 0.25])
uv *= frameUVSize;

Some results:

uv = vec2(0, 1); frameId = 0; uv_out = vec2(0, 0.25);
uv = vec2(0, 0.5); frameId = 3; uv_out = vec2(0.75, 0.125);
uv = vec2(0.5, 0.5); frameId = 14; uv_out = vec2(0.625, 0.875);

In truth however, this kind of texture trickery is less useful these days since array textures are now widely available with better results and simpler indexing.


Diffuse lighting calculations in ray-tracer I am trying to write a ray-tracer. The lighting part is proving to work but not accurately. To debug I simplified the scene to a single sphere centered at the origin with a radius of 1 and a point light shining from above (0, 2, 0). The camera is at (0, 0, 4).

ambient 0.2 0.2 0.2
specular 0 0 0
shininess 1
emission 0 0 0
diffuse 0 1 1

The image I'm rendering seems wrong - should its cutoff be lower closer to the equator of the sphere?

Any help would be appreciated.

Some elementary trigonometry tells you what to expect from this situation.

The angle to see the shadow terminator is marked on the diagram, and a use of SOHCAHTOA tells you it's $\cos^{-1}\tfrac{1}{2} = 60^\circ$. Yours looks higher than that so your intuition seems correct. Stepping through the lighting code will help you see where it's going wrong, and you should consider writing unit tests for it, so that it's easier to provoke bugs like this in isolation.

Something else you might try to help narrow down the problem space is replacing the diffuse calculation with 1 iff $L.N > 0$ (i.e. if the light is in front of the surface), 0 o/w. That will give you a sharp line instead of a gradient, and if that sharp line is in the wrong place, you know the input vectors are wrong. If it's in the right place, the problem is in the diffuse shader itself.


Why are oct trees so much more common than hash tables? When reading papers I commonly find Oct tree implementations of geometry representations to sort the data. However whenever I think about the problem hash tables seem better overall.

Hash tables have a better average and worse case scenarios for most applications:

For example for ray tracing an oct tree, near misses will cause you to iterate through a binary tree substructure, which is O(nlogn) whereas the hash table is O(n).

Hash tables are easier to generate in the GPU, as they do not require any logical position in memory other than their hash position.

Most advantages tree structures have over hash tables do not seem to hold on the GPU either.

In graphics we don't like re-allocating memory so we usually over allocate memory in VRAM just to be able to reuse a data structure. So the property binary trees have (being memory efficient) doesn't seem very relevant for GPU applications.

Data coherence for caching doesn't seem to hold either. For a GPU generated tree, asynchronicity makes it very difficult to guarantee that logically close values also get stored close to one another in the underlying memory. So you will end up jumping around pointers anyway.

It is also much easier to enforce certain GPU friendly heuristics in a hash table than in a tree. For example limiting the number of hash lookups to a fixed number, say 20 and using the same logic to prevent warps from executing different branch code. in essence you can always check the 20 potential collisions and just interpolate the result with the cell containing the key. In a tree the traversal through the data structure is a lot more dependent on the data itself and less on the data structure.

So why are oct trees used so much more than hash tables?

Lots of things here.

"When reading papers". What papers? If the topic of the paper is about something other than the spatial partitioning structure, it could be fair to use whatever knowing that the basic ideas will translate to other structures. Or not, hard to say.
"For example for ray tracing an oct tree, near misses will cause you to iterate through a binary tree substructure, which is O(nlogn) whereas the hash table is O(n)". Big O notation means nothing at all in this context. You are dealing with a particular technology at a particular scale when you talk about things that depend on implementation details. An O(nlogn) algorithm might be much slower than an O(n) one for the "n" that is realistic today, it happens all the times. And while you might say, in 10 years that might change, sure, that might be the case, but in the same 10 years your GPU might look completely different and thus the state of the art algorithms need to change regardless. That's common, if you look at GPU algorithms (and GPUs specifically are still evolving quite a bit)
What octree? What hash table? There are lots of choices there. For example "...as they do not require any logical position in memory other than their hash position". That's true only if you have no hash collisions, yes? If you have collisions then whatever strategy you use (probing or linked lists) you'll need to synchronize between threads, so the build is not so easy to implement on a GPU. Conversely, for octrees if you wanted to "overallocate" as you suggest then you could allocate a full tree, and indexing would then be equally only dependent on position. In fact, if you do some math you can see that in such cases octrees become just a way to swizzle a grid (e.g. compare the van Ende Boas layout with a grid in Morton order... nice exercise).

There are lots of other things I could say, but let me cut to the chase here.

For raytracing specifically, neither Octrees nor Hash tables are -that- popular. BVHs of AABBs are the way to go.
The main benefit of Octrees over hashed grid is that your cell resolution adapts to the geometry. Grids won't, you have to chose a cell size and that might be too small in certain parts of the scene and too big in certain others.
There are a -lot- of variants and a -lot- of implementation details. Naive octrees should probably never be used in practice as they are too deep / not wide enough. If you make an octree "larger" by having say, a 4x4x4 grid with 4x4x4 grids nested in each non-empty cells, you create what it's called a hierarchical grid. So grids and octrees exist on a spectrum, where octrees are the most "deep", grids are the most "shallow" (just one level, a single grid globally in the scene), and hierarchical grids can trade between the two
This might help! http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf ;)


Shader code for putting an atmosphere over a planet I'm working on a game set in space with procedurally generated planets, and I'm trying to write a shader that puts an atmosphere over a planet given the color of the atmosphere and the strength of the atmosphere.

It looks ok at low strengths:

But at high strengths the planet looks really bright:

And neither of them look realistic. For example in space engine the atmosphere really affects every part of the planet including the oceans without necessarily looking very bright:

Here's the relevant part of the shader code I'm using (in glsl):

//Final atmosphere color to use
vec4 atmo_pixel_color;

if(r > radius_percent)
{
    //This is in space, cut off the color quickly
    float atmo_alpha = clamp(0.5 - pow((r - radius_percent), 2) * 600, 0, 1);
    atmo_pixel_color = atmo_color * atmo_strength;
    atmo_pixel_color.w = atmo_alpha;
}
else
{
    //Atmosphere is thicker near the edges of the planet
    float thickness = pow((r / radius_percent), 2) * 0.1f;
    atmo_pixel_color = atmo_color * (atmo_strength + thickness);
}

gl_FragColor = planet_color + atmo_pixel_color;

r is the distance from the center of the planet. radius_percent is the percentage of the texture that is in the planet (above that is empty space). planet_color is the final base color of the planet itself, or empty black if the pixel is in space.

I have very little experience doing graphics programming and I didn't really know where to start to research this.

What kind of algorithm should I be using here to make the atmosphere look correct?

I believe that Space Engine as a base algorithm still uses Precomputed Atmospheric Scattering by E. Bruneton. It is released on github. So it is good starting point if you want to implement atmospheric scattering.

For beginner this algorithm is pretty advanced stuff written in C++11, and modern OpenGL, so such knowledge is required. In short, to avoid a cost of solving rendering equation for scattering in participating medium (single as well as multiple scattering) it uses precomputed lookup textures where it is possible and equations for Rayleigh and Mie scattering based on physical model.

There is also simpler demo computed in real time on shadertoy. This is probably better place to start. It involves raycasting a sphere and integrating Rayleigh and Mie scattering along a ray in real time. It is based on GPU Gems article, which provides some good information how it works.


How does mip-mapping work with non-power-of-2 textures? I have heard that recent GPUs all support non-power-of-2 textures and all features just work. However, I don't understand how mip-mapping would work in such a scenario. Can someone explain?

The rule is that to compute the next mipmap size, you divide by two and round down to the nearest integer (unless it rounds down to 0, in which case, it's 1 instead). For example, a 57x43 image would have mipmaps like:

level 0: 57x43
level 1: 28x21
level 2: 14x10
level 3: 7x5
level 4: 3x2
level 5: 1x1

UV mapping, LOD selection, and filtering work just the same way as for power-of-two texture sizes.

Generating good quality mips for a non-power-of-two texture is a little trickier, as you can't simply average a 2x2 box of pixels to downsample in all cases. However, a 2x2 box filter wasn't that great to begin with, so using a better downsampling filter such as Mitchell-Netravali is recommended regardless of the texture size.


Light coordinate in Phong shading and Normal interpolation I'm currently making a small 3D renderer and I got stuck in Phong shading.
My questions are:

Into which space should the light coordinate be converted?
I have my light position at world coordinates (0,0,0). I'd like to calculate "phong shading" after converting all the vertices to screen space (viewport).
So Should I convert the light position to screen space too?

Is there a faster way to calculate Phong shading with normal interpolation if the camera's position equals the light's position?

Typically, you calculate lighting in either world-space or view-space (or camera-space). The benefit to calculating it in camera-space is the increased precision, although this may involve introduce additional math operations in shaders depending on your setup. So it wouldn't be in screenspace, or you would need to reconstruct the positions (which could happen in deferred shading depending on your G-buffer layout).

I assume you are talking about a punctual light type (such as a point light). If so, if your light position equals your camera position, then the view and light angles are the same, which can be factored out in the BRDF that you use, so you save a dot product.


OpenGL - drawing icosahedrons and cylinders and combining them I have drawn a cylinder and an icosahedron using OpenGL.

Now, I need to use the icosahedron and the open cylinder to build a structure motivated by crystal lattices, where I use an icosahedron for each atom and a cylinder to connect each 2 icosahedrons.

I would have to use 12 icosahedrons for atoms and about 20 cylinders for the lines connecting the atoms, as I need to place them all to form the shape of an icosahedron itself.

Is there anybody that could give me any ideas regarding how to go about this? I can arrange 12 icosahedrons to simulate the 12 vertices of an icosahedron, but I'm not sure how to place all of the cylinders around properly.

When drawing in OpenGL and related APIs you usually have one or more models. In your case, this would be the cylinder and the icosahedron. The models are generally generated at some default size which may or may not suit your needs for a particular task. You move them, scale them, and rotate them by setting up a model matrix which describes how you want to transform them.

So how would this work in your case? I recommend having 2 functions. One which draws a unit cylinder and another which draws a unit icosahedron. Say you have a data structure for your coordinates like this (I'm assuming a C-like language):

typedef struct Position3D {
    float x;
    float y;
    float z;
} Position3D;

You can then construct a triangle by making a structure for one:

typedef struct Triangle3D {
    Position3D p0;
    Position3D p1;
    Position3D p2;
} Triangle3D;

Then you'd have functions for generating the vertices you need. Something like this:

void generateCylinder (Triangle3D* triangles) // <-assumes you allocated triangles before calling and that you have enough space for all of them!
{
    int i = 0;
    const float kRadius = 1.0;
    const float kDeltaH = 0.1; // <- change this to make the mesh more or less dense
    const float kDeltaAngle = M_PI / 10.0; // <- change this to make the mesh more or less curved
    for (float h = -1.0; h < 1.0; h += kDeltah)
    {
        for (float angle = 0; angle < 2.0 * M_PI; angle += kDeltaAngle)
        {
            float x = kRadius * cos(angle);
            float y = h;
            float z = kRadius * sin(angle);
            //... add points to triangles array here...
            // p0 = <x,y,z>
            // p1 = <x, y + kDeltaH, z>
            // p1 = <x + radius * cos(angle + kDeltaAngle), y, z  + radius * sin(angle + kDeltaAngle)>
        }
    }
}

And a similar function for the icosahedron.

Next, you'll create a matrix for every object you draw and send that to your shader before drawing it. So you'll have the translations for the vertices of the (big) icosahedron, and you want to draw a (small) icosahedron at each one. You'd do the following:

float translationMatrix [ 16 ] = {
    1, 0, 0, 0,
    0, 1, 0, 0,
    0, 0, 1, 0,
    0, 0, 0, 1
};
translationMatrix [ 12 ] = xPos;
translationMatrix [ 13 ] = yPos;
translationMatrix [ 14 ] = zPos;
GLuint modelMatrixLoc = glGetUniformLocation(program, "modelMatrix");
glUniformMatrix4fv(modelMatrixLoc, 1, GL_FALSE, translationMatrix);

Then you'd draw your icosahedron. For the cylinders you would need to scale vertically, rotate to the appropriate angle and translate it to the position between 2 icosahedrons.


GLSL Debugging Volumetric light I'm implementing basic volumetric lighting using deferred shading (gbuffer + render to screen quad) and basic shadow mapping. So,  I am sending the position texture and shadow map to a separate shader, applying ray-marching for every position and computing the scattering accumulation when is not in shadow. The question is , how do I know I am getting the right results? is it just by rendering the volumetric lighting texture to quad and look for colored patches in the scene? these are my results:

Original Scene

Volumetric Light buffer

This is the code of my volumetric fragment shader:

uniform sampler2D positionMap;
uniform sampler2D shadowMap;
float NB_STEPS = 3.0f;
int NB_STEPS_INT = 3;
float G_SCATTERING = 0.7f;
out vec4 fragColor;

void main()
{

vec2 texCoord = vec2(gl_FragCoord.x/width,gl_FragCoord.y/height);
vec3 worldPosition = texture2D(positionMap,texCoord).xyz;
vec3 startPosition = ViewPos;

vec3 rayVector = worldPosition.xyz- startPosition;
float rayLength = length(rayVector);
vec3 rayDirection = normalize(rayVector);
float stepLength = rayLength / NB_STEPS;
vec3 step = rayDirection * stepLength;

vec3 currentPosition = startPosition;

vec3 accumFog = vec3(0.0f);
for(int i = 0;  i < NB_STEPS_INT; i++)
{
  bool shadow = ShadowCalculation(currentPosition);
  if(!shadow)
  {
    accumFog += ComputeScattering(dot(rayDirection, light.position)) * light.diffuse;
    //accumFog +=  light.diffuse;
  }
  currentPosition += step;
}

accumFog /= NB_STEPS;

fragColor = vec4(accumFog, 1);

}

I am computing the scattering factor like this:

float ComputeScattering(float lightDotView)
{
  float result = 1.0f - G_SCATTERING * G_SCATTERING;
  result /=  (4.0f * PI * pow(1.0f + G_SCATTERING * G_SCATTERING - (2.0f * G_SCATTERING) *    lightDotView, 1.5f));
  return result;
}

At the end should I just blend the volumetric light buffer with the deferred shading final buffer?

I appreciate the help.

This question is a bit too broad to answer, but I'll try.

Right now you have a screenshot and you are not really sure whether it's correct or not, and if it turns out it is not, it will be difficult to know what is incorrect about it. I would recommend to split your problem into smaller, isolated, problems that can be validated separately.

For example, is the lighting information correct at each point? Are the coordinates (screen space vs world space) correct? To answer these questions you could maybe represent the distance from the light at each point, with something like the following, and check that the visual result is consistent with your scene.

color = fract(length(light.position - currentPosition));

Similarly, is the shadowing correct? This problem is unrelated to scattering so you can check that it  is correct by just having a constant light contribution (your commented code seems to indicate that you have tried so already). You will see quickly if a volumetric shadow is properly cast from occluding geometry.

if (!shadow)
{
    accumFog += light.diffuse;
}

Finally you can test the scattering without any shadow, and make sure it behaves as expected. For example, you should get the same fog color when changing the number of steps. Moreover, the scattering contribution should be less noticeable when there is geometry close to the camera (make sure you stop marching when you reach the scene depth).

Once you are confident the separate parts are working, you can combine them until you reach the final result. I have suggested a few points to check, but you might check other points as well, as you see fit.

  At the end should I just blend the volumetric light buffer with the deferred shading final buffer?

Since the lighting is additive, you just need to do an additive blend of the resulting buffer on your scene. However if you later decide to also handle distance fog (contrast fading in the distance), then a different blending will be necessary.

P.S.: I happen to have written about volumetric lighting in this article (see part "Volumetric lighting"). It doesn't go into details, but maybe it will be helpful nonetheless.


Changing image so it would look like through colorful glasses I am currently working on some simple pixel shader in HLSL. I send to shader texture and I want to make it more colorful (something like in the picture below).

In the picture 1 there is original texture. Picture 2 shows an effect that I want to achieve. Is there some mathematical formula to do that? My input is the RGBA value of each pixel.

EDIT:
I'll try to write more concrete.

Let's say I want to make that garden texture more red. I suppose that what I need to do is:

OutputR = InputR * X,

OuputG = InputG * Y,

OutputB = InpputB * Z

But how do I find X, Y and Z?

(XYZ) can be the RGB colour you want to tint your scene by. For the above scene it can be a red colour (1.0, 0.0, 0.0) or something similar with a strong red component.

Bear in mind that since you are applying the colour in a multiplicative way it will act as a filter suppressing original colour components. So if your scene is mostly green but you apply (i.e. multiply it with) a red filter (1,0,0) the resulting scene will be very dark.

A trick you could potentially do in such cases is to desaturate the original scene and then multiply it by the tint colour. That way you will keep the overall image intensity and achieve the colour tint you require.

For example, here is the image multiplied by (1, 0, 0), (1, 0.2, 0.2), and (1, 0.5, 0.5) from left to right:


Finding the angle of any side of a polygon I'm trying to find the angle it would take for me to rotate a polygon so that a specific side is completely horizontal and on the bottom.

For example, a shape like this:

Needs to be rotated so the side with the red square on it is on the bottom and completely horizontal, like this:

So far I've tried several approaches but all end up having strange edge cases where the angle is incorrect.

Deducing the angle and rotating by that angle works quite well in 2D (describe in TLousky's post). This strategy, does not extend very well into three-dimensional realm. I will provide an alternative solution that shows a general strategy that works in a larger set of cases. As a bonus this without needing to think of trigonometry as it can be encoded away.

First identify the vector that you want to be transformed to orientation in your reference space. Let us call this vector $\vec{a}$, or a along vector.
Next you will need to identify a vector that is perpendicular to this vector. Let us call this vector $\vec{b}$, it is sometimes also called a up vector. In three-dimensions you need 3 vectors but once you identify 2 you can compute the third.

Finding out the $\vec{b}$ in 2-D realm is especially easy you could just rotate the vector by $90^{\circ}$ or simply swap the coordinates and make the x coordinate negative (see 1). Alternatively you can use the same procedure as in 3D.

$$\vec{b} = rotate(90^{\circ})\cdot\vec{a} =
      \begin{bmatrix}
         \cos(\pi/2) & -\sin(\pi/2) \\
         \sin(\pi/2) & \cos(\pi/2)
      \end{bmatrix}
      \begin{bmatrix}
         x \\
         y
      \end{bmatrix}
         =
      \begin{bmatrix}
         -y \\
         x
      \end{bmatrix}
     \tag{1}$$

In 3-D this usually requires a trick. Since each triangle is flat, one can use this to ones advantage. This gives us a perpendicular direction, now we still need a third one and we can get it by cross product of the 2 known vectors. You now have 3 vector.

Image 1: Vector $\vec{a}$ and derived $\vec{b}$
Normalize the vectors
Use these vectors to produce a a rotation matrix (or a affine matrix wich allows you to specify point to be at zero, your choice). This matrix represents the local coordinate of the rotated object.
All you now need is to invert this matrix and point matrix multiply your polygon corner vectors for a aligned version of the polygon.

What is especially nifty is the sidestepping of trigonometrical operations. Now i see no point i defining basic matrix operations but i see value in code. So i will use numpy.

import numpy as np, pylab

pts = np.array([
        [0.,0.],[10.,1.],[12.,12.],[-2.,11.],[0.,0.]
      ]).transpose()

f = pylab.figure(facecolor="1.")
pylab.axis('off')
pylab.axis('equal')
pylab.plot(pts[0], pts[1])

# 1. Get the vector
vec_a = np.copy(pts[:,2]) - np.copy(pts[:,1])

# 2. up vector
vec_b = np.copy(vec_a[::-1])
vec_b[0] *= -1

# 3. normalize
vec_a /= np.linalg.norm(vec_a)
vec_b /= np.linalg.norm(vec_b)

# 4. build rotation matrix
mtx_R = np.concatenate(([vec_a], [vec_b])).transpose()
mtx_R = np.linalg.inv(mtx_R)

# 5. transform, or set hierarchy transform
pts2 = np.copy(pts)
for i in range(len(pts2[0])):
    pts2[:,i] =  np.dot(mtx_R, pts2[:,i])

pylab.plot(pts2[0],pts2[1])
pylab.show()

I admit it cold be have slightly shorter by refactoring the code and eliminate redundant manipulations but its a demo only so...

Image 2: Polygon, in blue axis fixed in green.

Same method works well for straightening, skew and other problems such as perspective correction. You can extend this to affine matrices that way you can encode the translation into the calculation with just 1 more lines. In essence you specify what point is at origin and with 2 more operations one could define around what to rotate. Now it just just rotates about the origin.


Simple Intersection Algorithm for Ray and 3D Bézier Curves of Varying Thickness I'm trying to get an algorithm for intersecting a "tube" (a 3D cubic Bézier curve extruded by a possibly-changing radius) with the following required properties:

Computes intersections of ray and a 3D cubic Bézier curve.  Must not become confused, as some numerical algorithms do, by secondary rays, which start from the surface of the curve (i.e. at a zero).
Must support a varying radius along the curve (a linear function is fine).  The radius may be zero in at-most one point.
Hit point accuracy should be a function of floating-point precision or solver iterations.  I.e., the geometry must be correct, fully volumetric.
Some reasonable way of handling endpoints.  I'd prefer spherical caps, but flat ones would be okay too.  A choice would be nice.

I don't need the fastest-possible algorithm.  The easiest reasonable algorithm is what I'm looking for.

Can someone help me find an ray + 3D-cubic-Bézier intersection algorithm satisfying the above?  A paper link, a description, help pinning down references, etc.

I've had great difficulty with a literature search on this.  Here are some of the (few) papers I found:

"Ray Tracing for Curves Primitive".  I implemented this, but the hit depth seems to be incorrect.  I suspect this is because it assumes (erroneously) that the cross section of the curve will be circular, even if at an angle.
"Exploiting Budan-Fourier and Vincent's Theorems for Ray Tracing 3D Bézier Curves".  Seems over-complex, and doesn't seem to support varying radius.  Looks like it has the same bad assumption, and code isn't available.
"High-Quality Curve Rendering using Line Sampled Visibility".  Quadratic curves only, rasterizer-based, unclear if meets other criteria.

You say that you don't need the fastest possible algorithm, so instead of solving it analytically, you might try considering the numeric alternatives, which in this case could mean ray marching.

How you could do this is take steps down the ray and test if the point is inside or outside of this bezier tube.

You would iterate down the ray until you either find an intersection or leave the bounding box of this shape (or maybe when you take a maximum number of steps, or some other fail case).

The challenge then only becomes "how can I tell if a point is inside or outside of the shape?" which is a lot simpler.  If you had constant thickness you would just find the closest point on the bezier to your point and do a distance comparison.

Some details you might be interested in:

taking smaller steps, and more of them, will give you more accurate results, but will be more expensive computationally. That makes this algorithm tuneable for quality vs speed.
if the step size is too large or the tube is too thin, you may completely miss the tube when there is really a hit.
when/if you do find a hit, you are finding the first point inside the shape. The real answer is somewhere between the last sample and the current sample.  You could refine the hit location with a binary search or some other method if you wanted to.
you can likely increase the step size as you move farther from the camera. Smaller details are harder to see at greater distances.
you might be able to calculate or approximate the gradient of your point vs bezier tube function as you ray march. If so, this gradient can be used to give you a lower bound on the distance from your point to the bezier tube, which would let you take larger steps through empty space.

Regarding the "secondary ray" issue you mention like for shadow rays or reflection rays that comes up with both analytical and numerical solutions.  Getting a (probably) less precise answer than a numerical solution does make the problem worse, but there should be ways to get around it.

For instance, after you detect a hit, you could find a point on the surface near the hit even if it isn't where the hit was (like, push the hit point to the surface, in whatever direction is easiest to compute), add an epsilon (needed for analytical solutions anyways) and spawn secondary rays from there.

Another way could be to have every object have an ID and when ray marching / tracing, don't count intersections with the same ID as what you just hit.  This only really works for opaque convex objects though.


Description of the process involved in displaying digital images Could someone please provide me with/point me to a description of the process involved in displaying a digital image? Starting from reading the data from a file to displaying the image on the screen.

I am puzzled regarding which parts of this process are handled by the OS and which are handled by the GPU.

I am especially interested in the transition from the initial, device-independent representation of the image to controlling the actual physical pixels on the screen. For example, how does a 1920x1080 image eventually get displayed on screens with higher or lower display resolutions?

Starting from reading the data from a file to displaying the image on the screen.

As was pointed out in the comments, this is an extremely broad question, and depends on what operating system you're using, and which tool sets for that OS you're using. That said, I think it is possible to talk generally about the process with much of it (if not all) being similar from machine to machine, and OS to OS.

I am puzzled regarding which parts of this process are handled by the OS and which are handled by the GPU.

I'll try to point out which parts are handled strictly by the OS, your program, and the graphics hardware, and I'll even provide C-like pseudo code. My pretend code will not be efficient, simply illustrative, and I'll be pretending to read this example image file.

For example, how does a 1920x1080 image eventually get displayed on screens with higher or lower display resolutions?

I think some of my pretend pseudo code will illustrate that, but the short answer is that you will manually resize your image to better fit the screen (or any other drawing area) inside your program.
The Long Answer
The first step is to open the image file. It doesn't matter what the format of the image is, from the view of your program it'll simply be a list of bytes. Some languages have tools and libraries that can be used to open files in a generic (OS independent) way, but often this step is OS specific. However, even though the task of opening and/or reading the file is dependent on the operating system, once your program has copied the content into memory it's just bytes for your program to deal with however you desire.
File imgFile = OS_OPEN_FILE("sample.ppm"); // Ask the OS for a file.
byte buffer[imgFile.size()];               // Set aside memory to hold the file's content.
for(int i = 0; i < imgFile.size(); ++i) {  // Start a reading loop.
    buffer[i] = OS_READ_BYTE(imgFile);     // Ask the OS for all bytes in the file, one by one.
}

Once you have access to all of the bytes in the entire image file it is up to you, the programmer, to know what each byte means, then to make your program read and interpret them correctly. For example, the portable bitmap format starts with a couple of bytes letting you know if the picture file is color, gray scale, or black and white. There are bytes that let you know what size the picture is, bytes that should be ignored because they're comments intended for humans to read, and finally bytes that are the dots of color to be sent to the screen. It is up to the program to sort through all of that.
int bufSize = imgFile.size();
for(int i = 0; i < bufSize; ++i) {  // loop through all the bytes read earlier.
    if(buffer[i] == 'P' && buffer[i+1] == '3') {  // Handle the image header.
        /* Do something */
    }
    else if(buffer[i] == '#') {  // Handle comments
        /* Do something */
    }
    else if(buffer[i] == /*...*/) {
        /* Do something */
    }
   /* ... etc. */
}

The next task is OS specific. You'll need to somehow ask the operating system to give your program access to a "drawing surface". Again, there are libraries such as SDL or SFML that provide surfaces in a generic way, but they are hiding the surface the system gave them behind an easy to use wrapper.
Often the drawing surface given by the OS is just a big block of bytes and you can simply copy data into it. Again, it is up to you to know which byte does what (like, which bytes represent red, green, or blue), but the task itself is usually just to copy from one chunk of memory into another. This is known as a Block Image Transfer, or a BLIT, and it's at this point that you may be handling memory inside the graphics card. Ultimately, it's up to the OS to decide where the drawing surface keeps the bytes that represent colors, but you can usually request that those bytes be on the GPU.
Surface sampleImage = OS_GET_GPU_DRAWING_SURFACE();
if(sampleImage.good()) {
    /* Copy in bytes from buffer[], sorting or converting data as needed. */
}

Depending on what tools you're using, and what task you're performing, a drawing surface you request from the OS can be the screen itself, and other times the screen is something that you can't touch directly but can only send surfaces to. Even when you can draw directly to the screen you will want to draw to a hidden surface, then blit the finished work over to the screen to prevent flickering and other visual problems. This is called double buffering, and mostly applies to the screen because it's always visible to the user.
Generally you will have many small drawing surfaces that represent things like, buttons, pieces of terrain in a game, letters, or whatever, and you'll use those to assemble a larger image on a bigger (usually screen sized) drawing surface that you will finally send to the screen as one big block.
Just to reiterate, these steps are all being done by your program, but the way your program has to do them is OS specific, and much of the memory being handled at this late stage is probably on the GPU.
// Ready the screen and a drawing area.
Surface * screen = OS_GET_SCREEN_SURFACE();
Surface * screenBuffer = OS_GET_GPU_DRAWING_SURFACE();

// Make the image 800% bigger!
sampleImage.resize(8.0f);
// Copy the image to the screen sized buffer, centering it.
// blitTo(surface, x, y)
// I'm assuming that in this pretend code images draw from their top left corner.
sampleImage.blitTo(screenBuffer,
                   screenBuffer.width()/2 - sampleImage.width()/2,
                   screenBuffer.height()/2 - sampleImage.height()/2);
/* ... etc. */
/* Do more image drawing work. */

// Finally, display all our complex behind the scenes work to the user.
// This is called a buffer swap.
Surface * temp = NULL;
temp = screen;
screen = screenBuffer;
screenBuffer = temp;
temp = NULL;

The Short Answer
In summary...
Task your program needs to do (what's primarily in charge):

Open a file (OS)
Read file (OS & Program)
Interpret data (Program)
Get a drawing surface (OS & GPU)
Fill the drawing surface with image data. (Program & GPU)
Assemble your final picture. (Program & GPU)
Gain access to the screen (OS)
Send your final picture to the screen. (OS and/or Program)


The meaning of early ray termination and front-to-back traversal in ray tracing I'm new to computer graphics. These days I've been trying to understand how ray tracing using an acceleration data structure works. I came across the term "early ray termination" several times, I looked it over the internet several times too, but I haven't been able to find a satisfactory explanation of it.
What does it mean to terminate a ray early, and why do we have to do it?
Besides, I noticed that the term "front-to-back traversal" is mentioned almost every time there's a mention of "early ray termination".
Concretely how does front-to-back traversal work (in the case of a kd-tree for example) ?

Front-to-back traversal is the idea that when traversing a ray through the acceleration structure, we want to examine nodes that are in front, i.e. closer to the camera, before other nodes. If you only want the first intersection with a surface (as usual in ray tracing), then if you get an intersection in the front node you don't need to traverse any nodes behind it; as any possible intersection there would be later than the one you already found. This saves time.

For example, in a kd-tree, at each node you have a splitting plane dividing space into two child nodes. You would first descend to the child closer to the camera, and only if no intersections are found there do you descend to the other child.

Early ray termination seems to be a term used in the context of volume rendering. When you're traversing a ray through a medium that attenuates light, such as fog, smoke, cloudy liquids, etc., then beyond a certain distance there is no possibility of the ray having any more effect on the image. If you have thick fog with a visibility of 10 meters, then an object 11 meters away cannot be seen.

You can precalculate the distance at which the attenuation reaches 99% or so (it never quite reaches 100%, but approaches it exponentially). There is no reason to intersect the ray against objects farther than that, so when using the acceleration structure, you can simply discard any nodes beyond that distance. In effect, the ray becomes a line segment terminated at a fixed length. If it doesn't hit anything within that length, there's no point checking further. (Another case where limited-length rays are handy is for shadow rays. You only want to trace them back to the originating light source; any intersections beyond that are irrelevant for the shadow.)


Problems rendering a plane via `drawElements` I am generating plane vertices where the y values are generated by a heightmap (noise) algorithm. This is how I produce my vertex array:

for (let row = 0; row < noise.length; row++) {
    for (let col = 0; col < noise[0].length; col++) {
        color = noise[row][col];
        positions.push(row, color, col);
    }
}

After that I generate index values like this (I know that there is a lot of optimization that can be done here):

const height = noise.length + 1;
const width = noise[0].length + 1;

for (let row = 0; row < height - 1; row++) {
    if (row % 2 === 0) {
        if (row === height - 2) break;
        for (let col = 0; col < width - 1; col++) {
            indices.push(col + row * (width));
            indices.push(col - 1 + (row + 1) * (width));
        }
    } else {
        for (let col = width - 2; col >= 0; col--) {
            indices.push(col - 2 + (row + 1) * (width));
            indices.push(col - 2 + row * (width));
        }
    }
}

indices.pop();

Finally I draw the plane using:

gl.drawElements(gl.TRIANGLE_STRIP, buffers.numIndices, gl.UNSIGNED_SHORT, 0);

So if I use POINTS as mode, the plane seem to look as it should:

Whereas if I am using TRINGLE_STRIP the result looks wrong:

First I thought wrong indices might be the reason but then I checked by scaling to a 3x3 grid/plane and the vertex and index output looked as I would have expected:

Vertices:

[-1, -43.89, -1,
-1,  -82.27,  0,
-1,  -23.06,  1,
 0,  -43.43, -1,
 0,  -54.85,  0,
 0,  -66.27,  1,
 1,  -61.89, -1,
 1,  -27.43,  0,
 1,  -59.89,  1]

Note:

  The vertices might not exactly correspond to what you would have
  expected from above loop. That is because I am centering the mesh
  around origin after the loop.

Indices:

[0, 3, 1, 4, 2, 5, 8, 4, 7, 3, 6]

So my guess is that the problem is that I am pushing my triangles counterclockwise, that is why I tried to enable culling and depth testing but that did not help either:

gl.enable(gl.DEPTH_TEST);
gl.enable(gl.CULL_FACE);
gl.cullFace(gl.FRONT);

Any guess what might be the reason for wrong TRIANGLE_STRIP rendering?

Update 1:

According to @PaulHK's recommendation I changed my index creation loop to insert the last index of a single strip twice.

for (let row = 0; row < rows - 1; row++) {
    if (row % 2 === 0) {
        for (let col = 0; col < cols; col++) {
            indices.push(col + row * cols);
            indices.push(col + (row + 1) * cols);
        }
    } else {
        for (let col = cols - 1; col >= 0; col--) {
            indices.push(col + (row) * cols);
            indices.push(col + (row + 1) * cols);
        }
    }
}

For a 3x3 grid this produces:

Vertices:

[-1, -9.6, -1,
 -1, -64.6, 0,
 -1, -11.1, 1,
 0, -38.8, -1,
 0, -32.8, 0,
 0, -26.8, 1,
 1, -37.0, -1,
 1, -1, 0,
 1, -47.5, 1]

Indices:

[0, 3, 1, 4, 2, 5, 5, 8, 4, 7, 3, 6]

Unfortunately the rendered object still looks the same.

Update 2:

I use the Diamond-square algorithm to generate the mesh. This requires a grid of size (2^n) + 1.
I.e.:

  2, 3, 5, 9, 17, 33, 65, 129, 257, 513 ...

Maybe it's just a coincidence but it seems to me that the grid can be displayed correctly for sizes 3 - 129 with the procedure from Update 1. For a size of 257 and above the mesh has errors.

3x3 looks fine:

129x129 looks fine:

257x257 seems wrong:

This looks like a case of 16bit truncation in your indice buffer. For a 257x257 grid you will be addressing more than 65536 vertices so you will need to use a 32bit indice buffer.

gl.drawElements(gl.TRIANGLE_STRIP, buffers.numIndices, gl.UNSIGNED_SHORT, 0);

change to :

gl.drawElements(gl.TRIANGLE_STRIP, buffers.numIndices, gl.UNSIGNED_INT, 0);

Also change your buffer allocation code to match this type (Uint16Array -> Uint32Array for Javascript).


When is a compute shader more efficient than a pixel shader for image filtering? Image filtering operations such as blurs, SSAO, bloom and so forth are usually done using pixel shaders and "gather" operations, where each pixel shader invocation issues a number of texture fetches to access the neighboring pixel values, and computes a single pixel's worth of the result.  This approach has a theoretical inefficiency in that many redundant fetches are done: nearby shader invocations will re-fetch many of the same texels.

Another way to do it is with compute shaders. These have the potential advantage of being able to share a small amount of memory across a group of shader invocations. For instance, you could have each invocation fetch one texel and store it in shared memory, then calculate the results from there.  This might or might not be faster.

The question is under what circumstances (if ever) is the compute-shader method actually faster than the pixel-shader method?  Does it depend on the size of the kernel, what kind of filtering operation it is, etc.?  Clearly the answer will vary from one model of GPU to another, but I'm interested in hearing if there are any general trends.

An architectural advantage of compute shaders for image processing is that they skip the ROP step. It's very likely that writes from pixel shaders go through all the regular blending hardware even if you don't use it. Generally speaking compute shaders go through a different (and often more direct) path to memory, so you may avoid a bottleneck that you would otherwise have. I've heard of fairly sizable performance wins attributed to this.

An architectural disadvantage of compute shaders is that the GPU no longer knows which work items retire to which pixels. If you are using the pixel shading pipeline, the GPU has the opportunity to pack work into a warp/wavefront that write to an area of the render target which is contiguous in memory (which may be Z-order tiled or something like that for performance reasons). If you are using a compute pipeline, the GPU may no longer kick work in optimal batches, leading to more bandwidth use.

You may be able to turn that altered warp/wavefront packing into an advantage again, though, if you know that your particular operation has a substructure that you can exploit by packing related work into the same thread group. Like you said, you could in theory give the sampling hardware a break by sampling one value per lane and putting the result in groupshared memory for other lanes to access without sampling. Whether this is a win depends on how expensive your groupshared memory is: if it's cheaper than the lowest-level texture cache, then this may be a win, but there's no guarantee of that. GPUs already deal pretty well with highly local texture fetches (by necessity).

If you have an intermediate stages in the operation where you want to share results, it may make more sense to use groupshared memory (since you can't fall back on the texture sampling hardware without having actually written out your intermediate result to memory). Unfortunately you also can't depend on having results from any other thread group, so the second stage would have to limit itself to only what is available in the same tile. I think the canonical example here is computing the average luminance of the screen for auto-exposure. I could also imagine combining texture upsampling with some other operation (since upsampling, unlike downsampling and blurs, doesn't depend on any values outside a given tile).


Merge multiple Point Clouds into a single 3D object I am testing the Intel RealSense D435 camera and have been able to create multiple Point Clouds (.ply) of a certain object. Each Point Cloud is taken in a different viewing angle of the object.

Now I wish to merge all these point clouds into a single, 3D Object. I have tried CloudCompare but this requires manual cropping of outliers and noisy data, as well as translating each Point cloud.

I wonder if there is a piece of code that can merge point clouds together and remove noisy data in order to have a rough 3D Object?

CloudCompare has statistical outlier removal (called SOR) function that can eliminate all lonely points for you. I would filter each *.ply first and then try to carry out a cloud to cloud registration. For registration, you can use MeshLab or use 30 days trails of commercially available software such as Faro Scene. Scene won't accept *.ply file though, so you need to convert your files to *.e57 first. Good luck.


OpenGL : How to translate an object with it's own axis I'm working with OpenGL to try to rotate / translate my 3d object : a cow.

The requirement is simple :

If I toggle key 'r'. The cow spinning around and random axis.
If I drag the cow with mouse, it translate along its own x axis which means +x directions is for cow's head
Rotation and translation need not execute at the same time.
Rotation and translation is done is modeling space.

To implement first requirement, I used timer function like this :

void rotateCow(int value) {
    //rotation ended
    if (!rotate_flag)
        return;

    printf("rotateCow\n");

    angle = (angle + 5) % 360;
    glutPostRedisplay();
    glutTimerFunc(30, rotateCow, 1);
}

and for rotation and translation :
(some of codes are skipped)

void dragCow() {
    glPushMatrix();
    //some codes are skipped..

    //rotation start
    if (rotate_flag == 1) {
        rotate_flag = 2;
        glutTimerFunc(30, rotateCow, 1);
    }

    glTranslatef(trans_x, trans_y, trans_z);
    glRotatef(angle, rotate_x, rotate_y, rotate_z);

    glCallList( cowID ); // Draw cow.
    glPopMatrix();
}

void onMouseDrag( int x, int y ) {
    y = height - y - 1;
    if (trans_flag == DIR_X) {
        trans_x = ((x - oldX) / DRAG) + old_trans_x;
    }

    glutPostRedisplay();
}

If I run as above(rotate and then translate) rotation is as expected.

However, the translation is done in global x-axis not towards head direction of cow.

If I change the order like this :

glRotatef(angle, rotate_x, rotate_y, rotate_z);
glTranslatef(trans_x, trans_y, trans_z);

It shows that translation is as expected(towards head direction of cow).

However, the rotations not works - the rotation-axis made on global x-axis and the cow revolve around that line.

So how can I solve this problem??

You can put the translation first, and then the rotation, but have the translation happen in the direction of the cow's head. To do that, you need a vector from the center of the cow to its head. Then you need the length of the translation. You can then do the translation in that direction. Like this:

float direction_x;
float direction_y;
float direction_z;
direction_x = cow_head_x - cow_center_x;
direction_y = cow_head_y - cow_center_y;
direction_z = cow_head_z - cow_center_z;

// find the length of the direction vector
float dir_length = sqrt(direction_x * direction_x + direction_y * direction_y + direction_z * direction_z);

// normalize the direction vector by dividing by the length
direction_x /= dir_length;
direction_y /= dir_length;
direction_z /= dir_length;

// Create a new vector pointing in the correct direction with the same
// length as the drag
float cow_translate_x = direction_x * drag_length;
float cow_translate_y = direction_y * drag_length;
float cow_translate_z = direction_z * drag_length;

// Do the transformation
glTranslatef(cow_translate_x, cow_translate_y, cow_translate_z);
glRotate(angle, rotate_x, rotate_y, rotate_z);

You could also get the direction vector by converting the angles to a direction. For example, if the rotation is only around the Y-axis, you could calculate it by doing the following:

float direction_x;
float direction_y;
float direction_z;
direction_x = cos(angle);
direction_y = 0.0; // since we're rotating around the Y axis
direction_z = sin(angle);

In this case, the direction vector is already normalized.

If you do have rotations around all 3 axes, you can calculate the direction vector using spherical coordinates:

direction_x = sin(angle) * cos(phi);
direction_y = sin(angle) * sin(phi);
direction_z = cos(angle);

where angle is the rotation around the y axis and phi is the angle above/below the x/z plane. The direction should already be normalized in this case, too.