How to implement a trackball in OpenGL? After so much reading about transformations it is time to implement a trackball for my app.
I understand I have to create a vector from the origin to where the mouse is clicked and then another from the origin to where the mouse is released.

My question is, do I have to transfor the (x,y) pixel coords to world-coords or should I just do everything in image space (considering image space is the 2D projection of the scene measured in pixels)?

EDIT

Richie Sams' answer is a very good one. However, I think I'm following a slightly different approach, please correct me if I'm wrong or I'm misunderstanding something.

In my application I have a SimplePerspectiveCamera class that receives the position of the camera, the position of the target we are looking at, the up vector, the fovy, aspectRatio, near and far distances.

With those I build my View and Projection matrices. Now, If I want to zoom in/out I update the field of view and update my projection matrix. If I want to pan I move the position of the camera and look at by the delta the mouse produces.

Finally, for rotations I can use either angle-axis transformation or quaternions. For this, I save the pixel-coords where the mouse was pressed and then when the mouse moves I also save the pixel-coords.

For each pair of coords I can compute the Z-value given the formula for a sphere, i.e., sqrt(1-x^2-y^2), then compute to vectors that go from the target to PointMousePressed and from target to PointMouseMoved, do cross product to get the axis of rotation and use any method to compute the new camera position.

However, my biggest doubt is that the (x,y,z) values are given in pixel-coords, and when computing the vectors I'm using target which is a point in world-coords. Isn't this mixing of coordinate system affecting the result of the rotation I'm trying to do?

Assuming you mean a camera that rotates based on mouse movement:

One way to implement it is to keep track of the camera position and its rotation in space. Spherical coordinates happen to be convenient for this, since you can represent the angles directly.

float m_theta;
float m_phi;
float m_radius;

float3 m_target;

The camera is located at P which is defined by m_theta, m_phi, and m_radius. We can rotate and move freely wherever we want by changing those three values. However, we always look at, and rotate around, m_target. m_target is the local origin of the sphere. However, we are free to move this origin wherever we want in world space.

There are three main camera functions:

void Rotate(float dTheta, float dPhi);
void Zoom(float distance);
void Pan(float dx, float dy);

In their simplest forms, Rotate() and Zoom() are trivial. The just modify m_theta, m_phi, and m_radius respectively:

void Camera::Rotate(float dTheta, float dPhi) {
    m_theta += dTheta;
    m_phi += dPhi;
}

void Camera::Zoom(float distance) {
    m_radius -= distance;
}

Panning is a bit more complicated. A camera pan is defined as moving the camera to the left/right and/or up/down respective to the current camera view. The easiest way we can accomplish this is to convert our current camera view from spherical coordinates to cartesian coordinates. This will give us an up and right vectors.

void Camera::Pan(float dx, float dy) {
    float3 look = normalize(ToCartesian());
    float3 worldUp = float3(0.0f, 1.0f, 0.0f, 0.0f);

    float3 right = cross(look, worldUp);
    float3 up = cross(look, right);

    m_target = m_target + (right * dx) + (up * dy);
}

inline float3 ToCartesian() {
    float x = m_radius * sinf(m_phi) * sinf(m_theta);
    float y = m_radius * cosf(m_phi);
    float z = m_radius * sinf(m_phi) * cosf(m_theta);
    float w = 1.0f;

    return float3(x, y, z, w);
}

So, first, we convert our spherical coordinate system to cartesian to get our look vector. Next, we do the vector cross product with the world up vector, in order to get a right vector. This is a vector that points directly right of the camera view. Lastly, we do another vector cross product to get the camera up vector.

To finish the pan, we move m_target along the up and right vectors.

One question you might be asking is: Why convert between cartesian and spherical all the time (you will also have to convert in order to create the View matrix).

Good question. I too had this question and tried to exclusively use cartesian. You end up with problems with rotations. Since floating point operations are not exactly precise, multiple rotations end up accumulating errors, which corresponded to the camera slowly, and unintentionally rolling.

So, in the end, I stuck with spherical coordinates. In order to counter the extra calculations, I ended up caching the view matrix, and only calculate it when the camera moves.

The last step is to use this Camera class. Just call the appropriate member function inside your app's MouseDown/Up/Scroll functions:

void MouseDown(WPARAM buttonState, int x, int y) {
    m_mouseLastPos.x = x;
    m_mouseLastPos.y = y;

    SetCapture(m_hwnd);
}

void MouseUp(WPARAM buttonState, int x, int y) {
    ReleaseCapture();
}

void MouseMove(WPARAM buttonState, int x, int y) {
    if ((buttonState & MK_LBUTTON) != 0) {
        if (GetKeyState(VK_MENU) & 0x8000) {
            // Calculate the new phi and theta based on mouse position relative to where the user clicked
            float dPhi = ((float)(m_mouseLastPos.y - y) / 300);
            float dTheta = ((float)(m_mouseLastPos.x - x) / 300);

            m_camera.Rotate(-dTheta, dPhi);
        }
    } else if ((buttonState & MK_MBUTTON) != 0) {
        if (GetKeyState(VK_MENU) & 0x8000) {
            float dx = ((float)(m_mouseLastPos.x - x));
            float dy = ((float)(m_mouseLastPos.y - y));

            m_camera.Pan(-dx * m_cameraPanFactor, dy * m_cameraPanFactor);
        }
    }

    m_mouseLastPos.x = x;
    m_mouseLastPos.y = y;
}

void MouseWheel(int zDelta) {
    // Make each wheel dedent correspond to a size based on the scene
    m_camera.Zoom((float)zDelta * m_cameraScrollFactor);
}

The m_camera*Factor variables are just scale factors that change how quickly your camera rotates/pans/scrolls

The code I have above is a simplified pseudo-code version of the camera system I made for a side project: camera.h and camera.cpp. The camera tries to imitate the Maya camera system. The code is free and open source, so feel free to use it in your own project.


If a 3D scene is rendered onto a hemispherical display, will there still be warping near the edges? When a 3D scene is rendered to a 2D display, the image is distorted near the edges of the display.

If a 3D scene is rendered onto a hemispherical display, will there still be warping?

There will be no distortion as long as you project the scene properly onto your virtual camera.

In traditional raster graphics the scene is projected onto a plane.

This makes it so that two equal solid angles to the camera can take up vastly different amounts of space on the screen.

Thus, the distortion does not come from the screen itself but from the projection used. Now, if you render your scene using a hemisphere projection, you should have no warping whatsoever. However, rendering using such projection might prove to be non trivial or straight up imposible using common methods (an exception to this is ray-tracing/marching/casting where all you need to change is how you generate your camera rays).

An alternative is to render various views (one facing the front, one facing upwards, etc) rendered in the classic flat projection and then "stitch" those together by mapping them to the screen somehow.

Here is a github repository of such a thing: https://github.com/shaunlebron/blinky

TL;DR : The display has little to do with how distorted an image appears. It is the projection used by the software that creates warping. Therefore, Even when using a curved display, the image will still appear distorted, unless this is compensated for in software.


How to compare anti-aliasing effects on images ? I am trying out different anti-aliasing algorithms on my image to improve the image quality. I want to compare the differences between these generated images via some metric. I was checking online for good metrics and found none.

Could someone please help me by pointing me to a valid metric that one can use to measure aliasing effects in an image ?

What you want to do is compare your anti aliased results against a "ground truth" image.

The ground truth image is the same image but without aliasing.

There are many ways to make an alias-free image, but a straight forward way would be by doing super sampling.

Super Sampling

When we render, we usually take a single sample at the center of the pixel (rasterize / shader / etc it to make the color).

Super sampling works by taking $N$ samples for that pixel, in random parts of the pixel and averaging the result.

The more samples you take, the closer you get to the ideal "alias free" image.

One simple way to do super sampling is to render the image at a higher resolution and then shrink it down to a smaller image.  For instance, if you render at double the height and width and then shrink the image down, that's the same as taking 4 samples per pixel.  However, going this route, the samples are evenly spaced on a grid, not randomly placed within each pixel.  Making the samples random instead of evenly spaced is really important to this monte carlo integration working, but evenly spacing them on a grid is a cheaper method that is better than nothing (aka useful in realtime situations sometimes).

Another way to do super sampling would be to render the image at normal resolution $N$ times, but in each render, you randomly offset the camera by a sub-pixel amount.  You then average your $N$ images together.  That will give you the random sample points, but of course each pixel has the same random sample points.

This is why you will often see sub-pixel jittering of the camera when doing temporal anti aliasing: it allows for better anti aliased results (a better integration) over time when combining multiple frames.  If they were all in the same position every frame, you wouldn't get any more information about the pixel.

Doing these methods will give you your ground truth alias free image, if using enough samples.

Comparing vs Ground Truth

The next step would be to compare the other anti aliased techniques against the super sampled ground truth.

There are lots and lots of ways that you might want to analyze this data, but I'll give a few ideas.

One way could be to make a texture where each pixel is the absolute value of the difference between the images for that pixel.  This would let you see the entire image as a whole and get an idea of how different it was from the ground truth.

Another way could be to calculate the mean and standard deviation of the difference of the images. This would give you an idea of how much on average pixels differed in the images, while also giving you an idea of how much variance there was in the difference. A high variance means some places are much worse than other places, so isn't very consistent.  Ideally, the best AA method will have the lowest mean, and the lowest variance.

Lastly, since aliasing is ultimately a "frequency" thing, you might find interesting data in doing a discrete Fourier transform on your images and comparing the frequencies in the AA method images vs the frequencies in the super sampled image.

More info on taking DFT of images here: https://blog.demofox.org/2016/07/28/fourier-transform-and-inverse-of-images/


Regular voxel grids and RTX accelerated ray tracing I've been looking to play with ray tracing, starting with a simplest of minecraft clones (making something more akin to cave game, for starter).

I figured I'd define a voxel as a primitive and then use the regular voxel grid to trace the rays. I don't need to test (look) for intersections here, I can precisely calculate them, tracing the ray voxel by voxel.

However, I do have an RTX card which does accelerate ray tracing with dedicated hardware, and I may be able to get faster results if I were to leverage it.

From what I gathered, one of the components of the RTX system (or any ray tracer, really) is an acceleration structure that speeds up the process of testing for intersections.

You give the card an octree or a BVH (or something similar) and it uses it to quickly find the closest hit (or any other hits, for that matter).

If I'm not mistaken, the hardware accelerated part here is the hit test. It's power is in the ability to test many primitives against one or more rays in a very short amount of time.

Given the method I'm using for ray tracing, that is the one part that I don't really need, since I don't need to search for which primitives the ray intersects (I calculate them explicitly), I just need to check where the intersection on them is.

Am I wrong? Can the architecture be used to accelerate what I'm doing?
If so, is it due to the fact that I misunderstood how it works, or can I adapt my plan in order to make it more friendly to the architecture, making the resulting plan faster than the original?

As you said, the RTX Turing architecture comes with wired primitive-ray intersection, (to be more specific, triangle-ray intersection). The BVH is built by specifying the Bounding Box program to OptiX, the signature of which is:

RT_PROGRAM void my_boundingbox_build_program( int, float result[6] )

As you can guess, the result must contain the minimun (3 first components) and maximum (3 last components) bounds of the bounding box. You can use this to build virtual bounding boxes even if you have no geometry (for instance, a chunk of 16x16x16 voxels).

When you perform rtTrace , the OptiX API will detect the collision through the BVH which it has build with the help of your bounding box program. In that momment, it will call the Intersection program, which you can specify and which signature is:

RT_PROGRAM void my_intersection_program( int prim_index )

Where you will report any possible intersection within your 16x16x16 chunk of voxels (obviously you can ignore the prim_index, which is only useful when using geometry primitives).

Now, if you would use their special structure RTgeometrytriangles , the Turing RTX architecture would be able to make use of the wired primitive intersection, which is where performance boost would be gained, and you would not need to implement your own intersection program.

To sumarize:
Since you are not using the specific RTgeometrytriangles , you will not access the intersection performance boost from the Turing architecture.


Bresenham circle drawing algorithm, compute the distance? In the Bresenham circle drawing algorithm, we have to choose between the top and bottom pixel, but what we always do is using the circle's equation ($f(x, y) = x^2 + y^2 = r^2$) to determine which of the two pixels is closer to the circle (r is the radius).

For the top pixel (N), we thus have $f(N) = x_{k+1}^2 + y_k^2 - r^2$

And for the bottom pixel (S), we have $f(S) = x_{k+1}^2 + y_{k-1}^2 - r^2$

Okay, we're using the circle equation to determine which is the closest point to the circle but why not simply using the euclidean distance? What is the point to use f instead of the actual distance? It would be easier to understand (this f function seems to come out of nowhere).

The actual distance between the top pixel and the circle is $\sqrt{x_{k+1}^2 + y_k^2} - r$ and with the bottom pixel it's $r - \sqrt{x_{k+1}^2 + y_{k-1}^2}$.

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

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

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

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

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

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

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

then compare

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

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

Update

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Conclusion

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


Rotate a cylinder from XY plane to given points I am given geometry of a cylinder which lies on the XY plane with 1 unit radius. And given coordinates of 2 points in 3D I need to move the cylinder so that it connects the two points.

What I tried so far after searching online:

Calculated the vector between the two points p = p1 - p2;
Took the normal vector to the plane(0,0,1) v
Axis of rotation = v x p (cross)
angle of rotation = acos(|v|.|p|) (unit vectors)
I applied this rotation.
Translated one of the end point of cylinder to one of the points.

but it moves the object to a wrong location. Any help what I'm doing wrong?

EDIT: My apologies for not being able to respond.
The main issue was with this line.

angle of rotation = acos(|v|.|p|) (unit vectors)
I normalized the vectors then used this wrong formula. Which will always return 90 degrees.

I am still not getting exactly the correct output. Here is the screenshot.

When you say $acos(\|v\|\|p\|)$ are you saying $acos(\|\hat{v} \cdot \hat{p}\|)$? If not the second, your angle will be some bizarre thing (In fact, you'll always get 90deg).
How are you applying the rotation? glRotate? Have you tried glRotate with the negative of your estimated angle?
Are you doing rotation/scaling/translation in the right order? Could you post the actual code that is executing if it is short? (If not, then a small runnable excerpt?)

Also: I'd be quite careful, as the cross-product-as-axis approach will produce goofy results when $v \parallel u$.


For shader math, why should linear RGB keep the gamut of sRGB? sRGB is often contrasted with "linear RGB."

Images are stored on disk and passed to displays in sRGB, which is approximately perceptually uniform in intensity.
Shader math is done in linear RGB, which is physically uniform in intensity.
Gamma correction can be applied to convert between the two.

Now, sRGB has a standard that colorimetrically specifies its gamut, saying exactly where pure red, green, blue and white lie.  But there is no corresponding standard for just "linear RGB."  Any triangle on a chromaticity diagram could be said to be linear, and, indeed, there are several well known gamuts to choose from:

In practice, when we say "linear RGB," we mean "sRGB without the gamma correction."  (This is implicitly what we're doing when we apply sRGB gamma correction as a final post-processing step but ignore color spaces for the rest of the rendering pipeline.)

But why is that RGB gamut the correct one to use for interpolation and lighting calculations?  It seems arbitrary.  If anything, wouldn't we want to use the largest possible gamut for internal calculations, and then clip or scale colors to the output device's gamut at the very end?

Is it that RGB lighting is going to be approximate no matter what, so it doesn't matter which gamut we pick, and we may as well pick the one closest to what the display natively supports?  Is it just negligence?  Or do calculations in these different gamuts actually yield the exact same results, somehow?

Talking about Linear RGB must be avoided because it does not tell you anything about the RGB colourspace intrinsics, i.e., Primaries, Whitepoint and Colour Component Transfer Functions. A few years ago, assuming it was sRGB was middling but nowadays with DCI-P3 and BT.2020 being very common, it must be ruled out.

The ideal gamut for rendering is the one that will minimize errors in respect to a real-world reference or more conveniently a ground truth spectral render. The first takeaway from this sentence is that the various RGB colourspaces are not equivalent and will not produce similar results.

One might think that performing two renders with the same base colours but one where they are encoded with sRGB/BT.709 and the other one where they are encoded with DCI-P3 and then converting the two resulting images to for example ACES2065-1 will yield the same images but it is not the case. Some mathematical operations because of the nature of linear algebra and matrices are dependent on the given RGB colourspace primaries, i.e., on the colourspaces basis. The same operations performed in different RGB colourspace will yield different tristimulus values once converted back to CIE XYZ color space. For example multiplication, division and power operations are RGB colourspace primaries dependent while addition and subtraction are not.

This image illustrates the effect of multiplying various colours by themselves into different RGB colourspaces: the resulting colours are different. The various samples are generated as follows: 3 random sRGB colourspace values are picked and converted to the three studied RGB colourspaces, they are exponentiated, converted back to sRGB colourspace, plotted in the CIE 1931 Chromaticity Diagram on the left and displayed as swatches on the right.

Tests and research conducted by Ward and Eydelberg-Vileshin (2002), Langlands and Mansencal (2014) and Mansencal (2014) showed that gamuts with primaries closest to the spectral locus, i.e. spectrally sharp primaries, tend to minimize the errors compared to spectral ground truth renders.

Here is an image I recently rendered with Mitsuba to re-validate our findings with Anders:

Those are renders of the same scene using BT.709 primaries (first row), 47 spectral bins (second row), BT.2020 primaries (third row), spectral minus BT.709 primaries renders residuals (fourth row), spectral minus BT.2020 primaries renders residuals (fifth row). The last row showcases composite images assembled with three vertical stripes of respectively the BT.709 primaries, spectral and, BT.2020 primaries renders. Direct illumination tends to match between the renders. Areas that show the effect of multiple light bounces, i.e., the ceiling, in the BT.709 and BT.2020 primaries renders tend to exhibit increased saturation, especially in the BT.709 primaries render or slight loss of energy, especially in the BT.2020 render. Excluding outliers, e.g., the visible light source, the RMSE with the spectral render are 0.0083 and 0.0116 for respectively the BT.2020 primaries and BT.709 primaries renders.

Now it does not mean they will always perform better, and one might be able to produce examples that will exhibit a bias toward BT.709/sRGB. The main takeaway is that RGB renders cannot match spectral renders and sharp wide gamuts tend to perform better. As for choosing a rendering colourspace, I would pick one with a wide gamut that encompasses Pointer's Gamut and DCI-P3, BT.2020 or ACEScg are excellent candidates for that.


Efficiently generating mesh for self-generated voxel grid I'm working on an app that lets users construct a 3D house, with the ultimate goal of it being 3D printable. I use various materials in the form of a height map constructed from an image, like this brick texture:

I map the brightness of each pixel to a height, like so:

But when you start combining wall panels side by side and at different angles, it can quickly get messy and you can end up with a self-intersecting mesh, not to mention many more polygons than are really necessary, all of which contribute to something which the 3D Printer slicer can't cope with. It looks like this but the geometry isn't clean enough to print it:

Now, currently everything in the app itself works directly with polygons. Since all of this ultimately is generated from grid-like data (the source images) it seems to me that some kind of voxel-based approach would be very suitable, and could potentially yield much better quality results. I have tested the approach of populating a grid directly from the source images, and that bit can be done very efficiently. But I'm having a hard time finding the right algorithm to then turn that grid data back into polygons ready for 3D printing.
Most algorithms for turning voxel data into a polygon isosurface assume two things, as far as I can tell:

That you have no prior knowledge of the underlying geometry
That the geometry is a scalar field, rather than a "boolean" grid where the grid lines genuinely do correspond to the final geometry. There could be fine scaled details that fall between the grid lines.

Whereas in my case:

I have huge empty patches inside the building, but I can easily ignore those because I have a list of bounding boxes of where each wall panel exists
I would like to take advantage of the fact that my data actually is gridlike in nature. Note that I can have 'diagonals' - this simple brick texture shown here is probably a little too simplistic, e.g. some roof tile textures use a lot more in-between heights:

Obviously something as simple as marching cubes could be adapted to take advantage of point 1 easily enough (just skip over sections of the grid which aren't contained within any of my bounding boxes) but I feel like marching cubes will yield WAY more polygons than necessary.
Can anybody recommend any specific algorithms that might suit this scenario (where we have prior knowledge about the underlying geometry) or give me some search terms that I can use to research? I've been searching algorithms for generating isosurfaces, but my instinct tells me that what I'm working with here is actually subtly different because of the grid-like nature of the problem - e.g. are these even really "voxels" at all?

So I've been all around the houses on this looking for an answer. In the end I found a combination of techniques worked quite well:

To take advantage of all of the 'empty space', the concept of 'surface tracking' from the Octree Decimation paper useful - you can follow the surface from cell to cell and ignore all of the cells in the middle.

The main advantage of generating the voxels ourselves is what we know two vital pieces of information: firstly, the exact position of each vertex within the cells on the 'front' surface; secondly, the 'orientation' of the mesh in each region and which way that 'front' is to be found.

Putting all the pieces together I came up with this Dual Marching Cuboids algorithm, that has pretty good results in very reasonable time.


How to correctly implement Lambertian BRDF with point light I'm implementing a simple Lamberitan BRDF in GLSL, using a point light source. My fragment shader simply returns light_colour * 1.0/PI * cosine, which should model a fully diffuse white material.

However, it looks rather dark... If I have a point light with colour (1,1,1), and no attenuation with distance, the maximum brightness of the material (at normal incidence) will be 1/3 (dark grey).

Is this just because I am using a physically incorrect point light with zero size? Is there any "correct" value for the light colour in this case, if I want the surface to be white at its brightest parts?

It doesn’t matter that it’s a point light; the 1/π normalization factor is what’s causing your surface to be 1/π as bright as you’d like it to be. You can either up your light intensity so the maximum brightness is π or just get rid of the normalization factor. There’s a good article with some notes about this and how it interacts with more complex lighting techniques here.


What is this vertical line contour effect in glitch art called? Some underlying portrait above is glazed over with a series of vertical lines that neatly follow the contours of the face. What is this effect called and how can it be replicated, step-by-step, in Adobe Photoshop or other software? plus, how can the gap between the lines be controlled?
Also is the color scheme due to chromatic aberration, or just simple RGB channel separation?

The technique is called halftone.  Achieving continuity must be done through subsampling / super-sampling, but the essence of the algorithm goes like this.
Imagine walking across a horizontal line of the image accumulating energy from each input pixel as you go.  Once you have accumulated some threshold amount of energy in the accumulator, emit a single pixel, and then reduce the energy stored in the accumulator by a constant amount.
In code, that would be something like:
for (int y = 0; y < height; ++y) {
    double accumulator = 0.0;
    for (int x = 0; x < width; ++x) {
        accumulator += input[x, y];
        if (accumulator >= 0.0) {
            output[x, y] = 1.0;
            accumulator -= K; // try values like 5.0 or more for K.
        }
    }
}

The larger K is, the more energy must be accumulated before outputting a pixel, and hence, the more horizontal distance there will be between the lines.  If K is 1, that's actually a naïve approach to the dither algorithm.
Supersample to achieve continuity.  You can also emit discrete (x,y) points instead of rendering an output pixel directly and then render a new image by rendering a vertical curve passing through the nth point generated of each scanline.
Perform the operation discretely on separate colour channels to get what you described as the "chromatic aberration" effect.
The effect degenerates the more complexity you encounter in the image on a single line.  For example, after just two eyes on the same line, the lines are extremely wavy at the right of your example image.  Here is the effect exaggerated even more.


Relationship between spatial frequency of an image and Aliasing I was looking into measuring the amount of aliasing in an image. After reading through many papers and sites, I came to the conclusion that the best method to measure the amount of aliasing in an image is by utilizing the frequency domain.

Is there a relationship between spatial frequency of an image and aliasing?
Also, is there any other metric that one can use to measure the amount of aliasing that is present in an image?

Like in any other kind of signal processing, the relationship is Nyquist's theorem. An image is a discrete sequence of samples of a continuous signal. If the original signal has frequency components higher than half the sampling rate, then there will be aliasing. To put that another way, if you look at the real-world size of a pixel, any details smaller than two pixels wide will be aliased. This applies to synthetic images as well as to photographs. If you define a procedural texture via a mathematical function, the function is continuous but you only evaluate it at certain points.

The problem is, of course, if you only have the sampled image and not the original signal, the high-frequency components have already been aliased, so you can't measure them directly. You have to use statistical techniques to guess which details in your aliased image were originally higher-frequency signals.


implementing right handed coord system APIs on top of a left-handed rendering engine I am trying to plug in a 3D game engine as the rendering engine for an existing graphic API system that uses a right-handed coordinate system.

Game engines often uses a left handed coordinate system internally.

So how can I convert the API parameters, 3d vectors, transformation matrices, and quaternions?

The right handed versions at the API boundary have to be converted to left handed equivalents before passing to the engine's APIs at a lower layer, and then the output parameters from the engine have to be converted back to the right hand representations for the higher level APIs.

Both coordinate systems I am referring to here are, x pointing to the right, y pointing to the top, and z point away from the eye (left hand) and towards or behinds the eye (right hand), with the eye at the origin or some distance behind the xy plane to allow the origin to be in the camera view.

Example: For simple 3d-points, the conversion step would be just to flip the sign of the z value.

What you probably need is this 4 x 4 matrix:

$$\mathtt{T} = \begin{bmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \\  \end{bmatrix}$$
which is flipping the z-axis. The inverse of this particular matrix is the matrix itself:
$\mathtt{T}^{-1} = \mathtt{T}$

For 3D points $\mathbf{x}$ multiply it from the left:
$$\mathbf{x}' = \mathtt{T}\,\, \mathbf{x}$$
and for 3D transformations multiply it from the right:
$$\mathtt{P}' = \mathtt{P} \,\,\mathtt{T}$$

Thus, you have not changed anything in the projection because:
$$\mathtt{P}'\,\,\mathbf{x}' = \mathtt{P} \,\,\mathtt{T} \, \,\mathtt{T}\,\,  \mathbf{x} =  \mathtt{P} \,\,(\mathtt{T}^{-1} \, \,\mathtt{T})\,\,  \mathbf{x} = \mathtt{P}\,\,\mathbf{x}$$

Quaternions $q=(s,x,y,z)^\top$ could be convert into
a 3D transformation matrix with:

$$\mathtt{P} = \begin{bmatrix} 1-2y^2-2z^2 & 2xy-2sz& 2xz+2ys & 0\\
              2xy+2sz & 1-2x^2-2z^2& 2yz-2sx & 0\\
              2xz-2sy & 2yz+2sx& 1-2x^2-2y^2 & 0\\  0 & 0 & 0 & 1\end{bmatrix}$$
and could then be treated like other 3D transformations.

However, 3D engines typically apply transformation in a transformation hierarchy. If this is the case, make sure you are only modifying the 3D transformation "closest" to the 3D point in the hierarchy.

Sources:
Graphics Programming I - 3D Transformations | Thorsten Thormählen


Directional Light ViewSpace Calculation I am a bit confused in terms of directional light calculation in OpenGL. Generally we care about the direction of the directional light and we use it with the normal and view (toCamera) vector to calculate lighting. Let's say I do my calculation in view-space ... would I need to multiply the direction of the directional light with ViewMatrix (and then normalize) ? I tried both and they don't seem to make a difference ... I'm leaning towards "yes I need to do that". Is this correct? Here's part of my fragment shader that does lighting for directional light:

vec4 calculateDirectionalLightIntensities(in vec3 N, in vec3 V)
{
    vec4 result = vec4(0.0, 0.0, 0.0, 1.0);
    for(int i=0; i<DirectionalLightCount; ++i)
    {
        //vec3 L = normalize( (ViewMatrix * -vec4(DirectionalLightDirections[i], 0.0)).xyz );
        vec3 L = normalize(-DirectionalLightDirections[i].xyz);
        vec4 currentResult = calculateDiffuse(N, L);
        currentResult += calculateSpecular(N, L, V);
        currentResult *= DirectionalLightIntensities[i];
        result += currentResult;
    }
    return result;
}

Basically N would be the normal vector and V is vector pointing towards camera in view-space and it is calculated as:

void main()
{
    normal = normalize(NormalMatrix * vec4(NORMAL, 0.0)).xyz;       //We use 0 because normals are directional vectors
    uv0 = TEXCOORD0;

    vec4 viewSpacePosition = ModelViewMatrix * vec4(POSITION, 1.0);

#if defined(BLINN_PHONG_LIGHTING)

    toCamera = -viewSpacePosition.xyz; //CALCULATED HERE

#endif

    gl_Position = ProjectionMatrix * viewSpacePosition;
}

Should I be multiplying my dir of directional light in the vertex shader? If so, is there a performance hit to having multiple lights that results in having array of varying variables being set to the fragment shader?

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

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

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

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


imageLoad() behavior for non-existent texel Is there a way to influence the behavior of imageLoad() for accessing an image2D or uimage2D with an out-of-bounds texel coordinate; for example repeat the last good texel instead of returning 0s?

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


Async readback storage buffer Every frame I dispatch a compute shader which write data in a storage buffer. The cpu needs to readback this data and use it. I would expect this to work :

// Dispatch compute shader
glDispatchCompute(x, y, z);
glMemoryBarrier(GL_SHADER_STORAGE_BARRIER_BIT);
void* data = glMapNamedBuffer(buffer, GL_READ_ONLY);

But it would introduce a sync point which I'd like to avoid. I'd like to hide the latency by reading the data written by the previous frame dispatch. If I was using textures I would have used PBOs, but I have not found a way to do this for storage buffers.

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

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

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

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

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

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

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

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

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


How do you calculate cos(theta) for diffuse in flat shading? Consider a triangular face of three vertices $A=(0,2,1)$, $B=(3,0,1)$ and the origin $O$, with normal vectors $(0,0,1)$, $(1,1,0)$, and $(-1,-1,1)$, respectively. The incident light is white and directional in the direction of $L = (0,3,4)$ and the intensity is $1$, the background ambient light intensity is $0.1$, and the diffuse reflection coefficients for $(red, green, blue)$ are $(0.6,0.7,0.8)$. No specular light contribution need be considered.

To find the $(red, green, blue)$ intensity values at the centre of the face using flat shading, I follow this procedure:

First, I try to calculate ambient light intensity

$$ambient\ light\ intensity = (ambient\ reflection\ coefficient) \cdot (incident\ ambient\ light\ intensity)$$

so,

$$red = 0.6 \cdot 0.1 = 0.06$$

$$green = 0.7 \cdot 0.1 = 0.07$$

$$blue = 0.8 \cdot 0.1 = 0.08$$

Then, I try to calculate diffuse light:

$$diffuse\ light = (incident\ light\ intensity) \cdot (diffusive\ reflection\ light) \cdot \cos{\theta}$$

so,

$$incident\ light\ intensity = 1$$

$diffusive\ reflection\ light$ is given as $(0.6, 0.7, 0.8)$

I am not sure how to calculate $\cos{\theta}$. I believe it to be the angle between the normal vector of a vertex and the incident light. But I am having difficulties because there are three different normal vectors.

After that, I think I should sum the ambient light intensity with the diffuse light to get the final RGB values.

I would really appreciate it if you could help me fill the gaps to my calculations. Thanks.

With flat shading, the normal is the same across the whole triangle (or quad or whatever). There are some assumptions that were made here and two approaches. The latter approach will probably be best for most basic problems (although more work). We don't have the winding order, so we need to calculate the normal based on the vertices.

Average normal approach

The assumption is that each vertex contributes the same amount of weight towards the triangle normal.

We first calculate the average of each:
$$normal = normalize(0,0,1) + normalize(1,1,0) + normalize(-1,-1,1) \approx \frac{(0,0,1)+(0.7,0.7,0)+(-0.58,-0.58,0.58)}{3} \approx (0.04,0.04,0.53)$$
$$normalize(0.04,0.04,0.53) \approx (0.076,0.076,0.994)$$

For Lambert shading:
$$cos(\theta) = normalize(0,3,4) \cdot (0.76,0.76, 0.994) \approx 0.84 $$

Geometric approach (recommended for this problem)

Another assumption Nathan Reed suggested was that each vertex normal holds equal weight, which would make sense in more common use cases. For this, we will want to find the face normals in both winding directions to compare this value to:

Winding order 1

$$normal1 = normalize((B-A) \times (O-A)) \approx (0.29,0.43,-0.85)$$

Winding order 2

$$normal2 = normalize((O-A) \times (B-A)) \approx (-0.29,-0.43,0.85)$$

Now, we can take the dot product between these two vectors and the one we computed above. Whichever one is greater or equal to 0:
$$geometric\ normal1 = normal \cdot normal1 \approx -0.79$$
$$geometric\ normal2 = normal \cdot normal2 \approx 0.79$$

So then,
$$normal = geometric\ normal2$$

For Lambert shading:
$$cos(\theta) = normalize(0,3,4) \cdot (-0.29,-0.43,0.85) \approx 0.42 $$


Could a hexagonal pixel array store an image more efficiently? Most computer monitors and televisions have a rectangular array of pixels arranged on a square (or nearly square) lattice. Would a hexagonal lattice give better image quality for the same number of pixels? In other words, would the same amount of memory allow storage of more detail?

I have an intuitive feeling that (at least slightly) more detail should be possible from the same number of pixels with a hexagonal lattice because (for a fixed area image) the average distance to the nearest pixel centre will be lower than with a square lattice. I'd like to see the difference defined more concretely.

Even if the answer is "yes", I don't expect monitor manufacturers to suddenly start making hexagonally arranged pixels. However, I ask the question because I wonder whether there would be anything to be gained from storing images as hexagonal lattices of pixels, even if they are translated to square lattices of pixels for display purposes.

Here's my take on it.  A pixel is not a square, and it isn't even a rectangle.  A pixel is a point (infinitely small) that has a color associated with it.

The only way I personally have ever seen pixels viewed (interpreted) by a display is to use "nearest neighbor" sampling where the pixels were on a rectangular grid, which means that the color of any given space on a display is the color of the pixel that it is nearest to.

This is a fancy way of saying "pixels are rectangular and laid out on a grid", but stay with me on this :P

As a result, image formats have their pixels stored in a grid as well, with the assumption that nearest neighbor in a grid will also be used to display it.  For instance, many images will have anti aliasing built into them so that they will look good when displayed on a "nearest neighbor grid".

Interactive applications (games), may use textures that are not meant to be displayed as is on nearest neighbor grids so are kind of an exception to that rule.  They do this because as part of their execution, they do anti aliasing, bilinear texture sampling, etc, so that whatever picture they push out to the display will look good, when the display shows it as a nearest neighbor grid!

Now, getting closer to your question: would a hexagonal grid have any advantages?

I think that yes, it would!

First off, I think nearest neighbor would look better.  I don't have any real proof of that sorry, but the hexagon more closely approximates a circle, and since it isn't a regular grid of data, i think your eye is getting a better distribution of data.  Sorry, that is a little hand wavey.

I think the big part of why it would look better though is that linear filtering would be taking information from 6 neighbors instead of 4, and would be interpolating on 3 axis instead of 2.  More information from less regularly spaced samples than a grid gives you = better resulting image.

Doing cubic interpolation would also be better than cubic interpolation on a grid, so the quality scales up as you scale up the quality of your algorithm too.

As far as whether it stores data more efficiently, the fact that it can do better filtering with less data means to me that yes, it could store data more efficiently.

And i guess lastly... maybe you could use these properties to your advantage.  Maybe you could have an image format stored in a lower res hexagonal format, and then before you needed to display the image at runtime, you could use sampling algorithms to convert it back to a grid.

Maybe there'd even be a good way to do this efficiently in a pixel shader, so it would use less memory at runtime too?

It's an interesting idea (:

PS - how cool would it be to have an analog display (no individual pixels, but a continuous colored surface) that looked at the pixel data you sent not as rectangles, but instead as sample points on a continuous surface.  Maybe a bit out there though....


Enter/Exit of unit cube representable as 4 numbers? In the paper Real-time Reflection using Ray Tracing with Geometry Field
, it mentions this:

  A ray is represented
  by its two intersection points (in,out) with the bounding box
  of the surface. Hence, the geometry field is a 4 dimensional
  function.

Having two $3D$ points gives 6 values: $A=(A_x,A_y,A_z), B = (B_x, B_y, B_z)$.

How is it that those 6 values, which are on the surface of a unit cube, can be represented with only 4 numbers?

Edit: the best I can think of is to convert each point to spherical coordinates and throw away the length, effectively converting these points to points on a unit sphere.  That way involves some trig operations though. Is there a better way that uses less computation?

3D object surface is 2D domain and can thus be parametrized with a 2D function. In case of a unit cube you could parametrize the surface for example by mapping each 6 faces to a 2D image strip. So if you know two points of the ray that intersects the cube, you can define it with 4D function using the parametrization


Is There an algorithm to remove intersections between two tetrahedrons? I have a mesh made up of several tetrahedrons, I know for sure that there are intersections between some of them: how can I remove these intersections, without generating others?
In other terms: if between a couple of tetrahedrons there is an intersection, how can I remove it?
I found these articles: the Method of Separating Axes, the Tetrahedron Overlap Algorithm.
But they are only useful for checking if there are intersections or not.
Is there an algorithm to solve this problem?

Since you already have convex shapes and started looking at the "Method of separating axis", then the GJK algorithm is probably what you're looking for. This is commonly used in physics simulations to find collisions (for games, I don't know about computational science).
When you say "remove intersections without generating others", then you're asking for collision response. Multiple collision response is actually a tough beast. Here (Reflections on Simultaneous Impact) is a paper that goes into more detail, but a very good introduction to this are course notes from Baraff:
An Introduction to Physically Based Modeling: Rigid Body Simulation I—Unconstrained Rigid Body Dynamics and part 2. Rigid Body Simulation II-Nonpenetration Constraints
Lastly, you can always use a physics engine for this, such as Bullet3d.


Challenges of Offline Rendering What are some of the challenges of Offline Rendering? I know one problem that is faced is performance and rendering times, are there any more issues?

Path Traced photos seem to have reached the point where it is hard to distinguish a CGI image in comparison to a real photo so being able to render a photo-realistic image doesn't really seem like a challenge anymore.

Is offline rendering just about refining current techniques to find an improvement in render times now and not so much about photo realism?

(Grand Moff Tarkin in Star Wars: Rogue One was entirely created through CGI since the actual actor had died)

Since you've used the "path tracing" tag, I'm assuming you're thinking mainly about light transport. At SIGGRAPH 2015, there was a course on the topic of path tracing in movie production that may be interesting:
https://sites.google.com/site/pathtracingrevolution/
Some of the presenters point out unsolved challenges towards the end of their presentation, for example see the second to last slides in the presentations from Alexander Keller and Johannes Hanika.

Then there are challenges in rendering that are not necessarily tied to path tracing but also present in game engines. Triangle meshes as an approximation of smooth solid surfaces are one, the use of shading normals or even worse, bumped normals have been pointed out as a source of artifacts a long time ago: "It's not really a rendering bug, you see..."


Generate mesh from pointcloud data Given point-cloud data :
For example.
position + color and normal.

What will you use to generate mesh of this data
and keep reasonable quality for real time cases ?

Additional info to consider:

In some cases given also
3D cameras world transforms which generated the PCL.
Number of input vertices : ~50k and up to millions .
Target latency from input to output : < 40ms
Output triangle mesh (preferably not a must)
More info about mesh reconstruction
A Benchmark for Surface Reconstruction

Any inputs are welcome.
FAQ:

How the data look like ?

Float* Position  [x1,y1,z1,x2,y2,z2...]
Float* Normal    [nx1,ny1,nz1,nx2,ny2,nz2...]
float or int8 for the color.

one popular Real time surface reconstruction method is TSDF (Truncated Signed Distance Function) used by Microsoft for the Kinect. It is based on the VRIP method but it is faster. It is based on depth maps from different (known) camera positions.
you can read more:
https://cs.nyu.edu/courses/fall12/CSCI-GA.2945-001/dl/jiakai-slides.pdf
file:///C:/Users/chaim.dryzun/Downloads/kinectfusion.pdf
From the methods in the reference you gave the fastest is Wavelet based surface reconstruction. If the overall point cloud is good and regular (uniform point density) and without holes and the normals are correct than it gives a very good mesh in a short time.
A more robust and popular method is the Poisson based surface reconstruction. You will need the normals. It gives very good mesh although it takes more time.
Another good method is the PowerCrust surface reconstruction method. It gives very good and accurate mesh, and it does not need the normals. This method produces a polygonal mesh and not triangular mesh, but it is very easy to transform it to triangular. The original code is very slow, but as it is based on calculating Voronoi cells - you can easily re-write it so it will run much faster.
You can read more:
http://web.cs.ucdavis.edu/~amenta/powercrust.html
Regarding the time, working with million of points will take much more than 40 ms, no matter which method you choose (except maybe TSDF). You will have to downsample the point cloud before meshing.


What is my GPU waiting on? I am writing an OpenCL program for use with my AMD Radeon HD 7800 series GPU. According to AMD's OpenCL programming guide, this generation of GPU has two hardware queues that can operate asynchronously.

  5.5.6 Command Queue

  For Southern Islands and later, devices support at least two hardware compute
  queues. That allows an application to increase the throughput of small dispatches
  with two command queues for asynchronous submission and possibly execution.
  The hardware compute queues are selected in the following order: first queue =
  even OCL command queues, second queue = odd OCL queues.

To do this, I've created two separate OpenCL command queues to feed data to the GPU. Roughly, the program running on the host thread looks something like this:

static const int kNumQueues = 2;
cl_command_queue default_queue;
cl_command_queue work_queue[kNumQueues];

static const int N = 256;
cl_mem gl_buffers[N];
cl_event finish_events[N];

clEnqueueAcquireGLObjects(default_queue, gl_buffers, N);

int queue_idx = 0;
for (int i = 0; i < N; ++i) {
  cl_command_queue queue = work_queue[queue_idx];

  cl_mem src = clCreateBuffer(CL_MEM_READ_ONLY | CL_MEM_COPY_HOST_PTR, ...);

  // Enqueue a few kernels
  cl_mem tmp1 = clCreateBuffer(CL_READ_WRITE);
  clEnqueueNDRangeKernel(kernel1, queue, src, tmp1);

  clEnqueueNDRangeKernel(kernel2, queue, tmp1, tmp1);

  cl_mem tmp2 = clCreateBuffer(CL_READ_WRITE);
  clEnqueueNDRangeKernel(kernel2, queue, tmp1, tmp2);

  clEnqueueNDRangeKernel(kernel3, queue, tmp2, gl_buffer[i], finish_events + i);

  queue_idx = (queue_idx + 1) % kNumQueues;
}

clEnqueueReleaseGLObjects(default_queue, gl_buffers, N);
clWaitForEvents(N, finish_events);

With kNumQueues = 1, this application pretty much works as intended: it collects all of the work into a single command queue that then runs to completion with the GPU being fairly busy the whole time. I'm able to see this by looking at the output of the CodeXL profiler:

However, when I set kNumQueues = 2, I expect the same thing to happen but with the work evenly split across two queues. If anything, I expect each queue to have the same characteristics individually as the one queue: that it starts work sequentially until everything is done. However, when using two queues, I can see that not all of the work is split across the two hardware queues:

At the beginning of the GPU's work, the queues do manage to run some kernels asynchronously, although it seems like neither ever fully occupies the hardware queues (unless my understanding is mistaken). Near the end of the GPU work, it seems like the queues are adding work sequentially to only one of the hardware queues, but there are even times that no kernels are running. What gives? Do I have some fundamental misunderstanding of how the runtime is supposed to behave?

I have a few theories as to why this is happening:

The interspersed clCreateBuffer calls are forcing the GPU to allocate device resources from a shared memory pool synchronously which stalls the execution of individual kernels.
The underlying OpenCL implementation does not map logical queues to physical queues, and only decides where to place objects at runtime.
Because I'm using GL objects, the GPU needs to synchronize access to specially allocated memory during writes.

Are any of these assumptions true? Does anyone know what could be causing the GPU to wait in the two-queue scenario? Any and all insight would be appreciated!

Compute queues in general don't necessarily mean you can now do 2x dispatches in parallel. A single queue that fully saturates the compute units will have better throughput. Multiple queues are useful if one queue consumes less resources (shared memory or registers), then secondary queues can then overlap on the same compute unit.

For real-time rendering this is especially the case with things like shadow rendering that are very light on compute/shaders but heavy on fixed function hardware, thus freeing the GPU scheduler to run the secondary queue async.

Also found this in the release notes. Don't know if it's the same issue, but could just be that CodeXL is not great. I would expect that it might have not have the best instrumentation for which dispatches are in flight.

https://developer.amd.com/wordpress/media/2013/02/AMD_CodeXL_Release_Notes.pdf

  For an application that performs simultaneous asynchronous data transfer and kernel execution,
  the timeline shown in the Application Trace session view will not show these operations being
  overlapped. This is because the driver and hardware force these operations to be synchronous
  while profiling. (333981)


Where should I project a polygon corner when it is behind me? I am creating a simple 3D engine as a learning project to get the hang on spherical trigonometry. I am using the following approach.
1. A model consists of a lot of triangular faces.
2. Each triangle is rendered through finding where the vectors pointing to the corners of it intersect a plane. This creates a flat projection I draw to the screen.

I have already implemented this, and it works great, except when some of the corners of a triangle are located behind me.

It is quite obvious what the problem is: The vector pointing to the corner is never intersecting the plane. But I need a point to render the projection, as a part of the triangle is visible.
That causes trouble. I can not place the third corner anywhere on my projection plane, as the edges of the projected triangle are diverging when they escape the field of view.

Logically, the edges of the projected triangle are thus pointing towards two different points on the plane outside the frame (or on the frame border, depending on taste and size of data types).

Suddenly having to deal with rendering a four-sided polygon instead of a triangle is no problem, my rasterization algorithms are flexible. I can however not figure out how to calculate the locations of the new "off-screen" points. How can I find them?

Trying to explain a problem seems to help the thought process. This is what eventually worked for me:

I realized that I can easily find the point (in 3D space) where a line between two of the corners brakes through one of the walls in my pyramid field of view, given the coordinates of the out-of-view corner and one of the visible ones. It is only a matter of finding the intersection between two lines. The position of the intersection point gives away the height on the frame wall.

Self answer, yes, but nothing came to mind before posting at SE.


Why isn't PNG preferred over JPG for being lossless art quality yet? This is something that pops up on my mind once a while when I browse around the web for art and desktop wallpaper, since I tend to see JPG and PNG as the common formats. I just had to ask to get it off my mind, hopefully I've posted in the correct stackexchange domain.

I'm sure many computer users who are aware that PNG is a lossless computer image format (doesn't lose quality) while JPG is a lossy format (losses quality).

After researching. I've found that PNG has been out since 1995 and the size of computer storage has drastically increased since then. Even if image resolution and file size increases, I'm sure anyone can store over 100,000+ PNG images on a single hard drive today.

Personally when I look for art. I make sure I get the highest resolution available as a PNG. I'm aware converting from JPG to PNG will still have the lossy image detail from being a JPG.

I don't know if this is the real reason, but here's one possibility: because it's unnecessary.

It's easy to say "JPEG = lossy = bad", but JPEG doesn't just destroy image quality willy-nilly. What the format gives you is a slider with "small, low-quality" at one end and "big, high-quality" at the other. You can easily reduce the byte size of a PNG image by encoding it as JPEG, and if you use the high-quality end of the slider, you needn't lose any visual appeal. Although normal JPEG is lossy in the information-theoretic sense, a high-quality JPEG appears identical by the naked eye.

Many image hosting sites will replace images by lower-quality JPEG files not because of the storage cost but because of the bandwidth cost. If you're serving millions of views of these files every day, the cost of sending those extra bytes is pretty big, even though the cost of storing them is tiny. And those bytes don't just cost money: they also cost load time for your users on mobile networks. These sites will have targets for how long their pages take to load on slow connections, and reducing the quality slider ever so slightly makes a big total difference.

In summary, JPEG encoding can be lossless or lossy, and it can be as high- or low-quality as you want. Using PNG everywhere instead of JPEG would be costly for image sites and would make you wait longer for your art files to download. Choosing a high-quality JPEG file can give you something that looks just the same as the PNG without being as "heavy".


How to load a model in .json in three.js I need to load a model "somemodel.json" into my "movie.js".Can someone tell me where i am going wrong.I followed the steps given here.

index.html

<!DOCTYPE html>
<html>
    <head>
         <meta charset=utf-8>
         <title>Test</title>
         <style>
            body { margin: 0; }
            canvas { width: 100%; height: 100% }
         </style>
    </head>
    <body>
        <script src="three.min.js"></script>
        <script src="ObjectLoader.js"></script>
        <script src="movie.js"></script>
    </body>
</html>

movie.js

var camera;
var scene;
var renderer;
var loader;

frame();
animate();

function frame() {

scene = new THREE.Scene();
camera = new THREE.PerspectiveCamera( 45, window.innerWidth /     window.innerHeight, 0.1, 1000);
camera.position.y = 0;
camera.position.z = 10;
camera.rotation.x = 0;

var loader = new THREE.ObjectLoader();
loader.load(
'somemodel.json',
function () {
    var geometry = new THREE.SphereGeometry(3,32,32);
    var material = new THREE.MeshBasicMaterial();
    var object = new THREE.Mesh( geometry, material );
    scene.add( object );
}
);

renderer = new THREE.WebGLRenderer();
renderer.setSize( window.innerWidth, window.innerHeight );
document.body.appendChild( renderer.domElement );
render();
}

function animate() {
render();
requestAnimationFrame( animate );
}

function render() {
renderer.render( scene, camera );
}

Or can your give an example with a sample model ?

When i run my file it raises an error in the console saying not well-formed        male.json

The error not well-formed        male.json doesn't appear to have anything to do with the code you've posted. I don't see any references to a JSON file called male.json.

If this file is in your code somewhere, the error is telling you the problem. It is malformed. Paste the contents of the file into an online validation tool such as JSONLint. It will tell you what is making it malformed.

Also, you're passing JSON into ObjectLoader.load but you don't do anything with the results. Instead try this:

var loader = new THREE.ObjectLoader();
loader.load('somemodel.json', function (object) {
    scene.add(object);
});

Check out the documentation for more information.


Why BMP file format last line of image is first line on file? I'm studying Microsoft Windows Bitmap File Format, extension BMP.
I'm curious to know why scanlines are stored on file from bottom to up: the last scanline on image is the first line on file and the first scanline on image is the last line on file.
The documents that I have read do not explain it.

Here's a quote from Petzold:

    So, in DIBs, the bottom row of the image is the first row of the file,
    and the top row of the image is the last row in the file. This is
    called a bottom-up organization. Because this organization is
    counterintuitive, you may ask why it's done this way.

    Well, it all goes back to the OS/2 Presentation Manager. Someone at
    IBM decided that all coordinate systems in PM—including those for
    windows, graphics, and bitmaps—should be consistent. This provoked a
    debate: Most people, including programmers who have worked with
    full-screen text programming or windowing environments, think in terms
    of vertical coordinates that increase going down the screen. However,
    hardcore computer graphics programmers approach the video display from
    a perspective that originates in the mathematics of analytic geometry.
    This involves a rectangular (or Cartesian) coordinate system where
    increasing vertical coordinates go up in space.

    In short, the mathematicians won. Everything in PM was saddled with a
    bottom-left origin, including window coordinates. And that's how DIBs
    came to be this way.

  Source: Charles Petzold, Programming for Windows 5th Edition, Chapter
  15.

from
https://stackoverflow.com/questions/8346115/why-are-bmps-stored-upside-down


Why does DirectX use COM pointers and interfaces? I have a rudimentary understanding of COM and I know that its main purpose is to enable interoperability between programs written in different languages. However I dont understand why that is useful to the DirectX api. Is it because DirectX has to make calls to the windows api which are written in C whereas DirectX is written in C++?

C++ has no defined ABI, so C++ programs can't link to libraries that were compiled with a different compiler. In addition, MS's Visual Studio C++ compiler is not ABI-stable, so you don't just have to use the same compiler: you have to use the same version that the library was compiled with.

This would be a huge problem for a widely-used library like DirectX.

COM doesn't just enable interoperability between different languages, but also between different C++ compilers. In fact, I'd say this is its main use, and language compatibility is less used. By being a COM library, DirectX can avoid application developers needing to care what compiler it was compiled with. Application developers are free to use a Visual Studio version of their choice, or a completely different C++ compiler.


Define position and orientation in a local coordinate system Suppose we have a world coordinate system W and a 3D model m1 defined in W. m1 has its own local coordinate system L.

How would we define L? Only by the transform from W to the object?

If we add a 3D model m2 to W : How do we define its position and orientation in L without worrying about the world coordinate system. Like just saying for instance that it's in (0,0,0) in L?

PS : If it's possible using algebraic or 3D geometry matrices transformation equations ?

Assuming that your 'models' can be represented by collections of points, then these points' coordinates are defined with respect to some coordinate system. You said that $m_1$ is defined wrt the coordinate system $W$. And you have some other coordinate system $L$ and want to find the positions of the points of $m_1$ in it. To do this you need to multiply each of your points with the matrix used to go from $W$ to $L$. To build this matrix you need to know the coordinates of the basis vectors of $W$ wrt $L$. Then you can make a 3x3 matrix where each column is a basis vector with which you can go from $W$ to $L$. Note that a translation will also be necessary if the origins do not agree.
The solution for $m_2$ is similar.


How do I calculate average hue, since the numbers loop around? If I calculate the average (mean) hue of a set of colours naively, I will get silly answers sometimes.

For example, in HSB/HSL, the average of hue=10 (slightly orange red) and hue=350 (slightly blue red) would arithmetically be hue=(10+350)/2=180 (cyan).

Considering the hue channel only, how should I calculate averages in order to get results which match intuition in these cases?

How do I calculate average hue, since the numbers loop around?
I will get silly answers sometimes. For example, in HSB/HSL, the average of hue=10 (slightly orange red) and hue=350 (slightly blue red) would arithmetically be hue=(10+350)/2=180 (cyan).

How to calculate mean and standard deviation for hue values from 0 to 360?
 and Averaging circular values (particularly Hues in HSL color scheme) which provides C++ source code.

What if the values were 0° and 180°, then there are two answers: 90° and 270°; the same thing applies whenever the two inputs are opposite, there's two answers and no clear choice.

The program "Image Color Summarizer" (Linux version) has a file called "peravg.pm" which says: "compute the average and median of a periodic data set, like a set of angles or hues". The main page offers a Windows version and a webpage image upload along with an API.

The author explains:

The colour summarizer will produce descriptive colour statistics for an image. Reported will be the average, median, minimum and maximum of each component of RGB, HSV, LCH and Lab. Average hues are calculated using mean of circular quantities.
Some of the questions the summarizer will answer are:

what is the average color hue, saturation and value in my image?
what are the colours that are most representative of the image?
what is the image's human readable colour description (e.g. dark pure blue)?
what do the RGB, HSV, LCH and Lab histograms look like?
what are the RGB, HSV, LCH and Lab pixel values?

The paper: "Perceiving the average hue of color arrays" (May 1 2014), by Jacquelyn Webster, Paul Kay, and Michael A. Webster examines the subject from the viewpoint of an observer's perception of color.


Finding the nearest neighbor of polygons I have a set of non-convex polygons and I want to merge them. I am able to find the connection between two polygons. If there are more than two polygons, one connection can intersect another polygon within the set. I do not want to check for a possible intersection. So I have to find the nearest neighbor of a single polygon. Is there an existing algorithm? I can't find anything in my literature.

You're looking for a nearest neighbor search: https://en.wikipedia.org/wiki/Nearest_neighbor_search
We've solved similar problems in 3D space using spatial subdivision (kd tree). Depending on polygon count and uniformity, a linear search or hash grid would be options too. A linear search, while O(N^2) can still be faster than setting up extra data structures for small a small number of polygons/vertices. A hash grid should be faster to update than a kd tree if your scene is dynamic, and I would expect it to be more efficient when the scene is uniform in vertex density.


Fluid sim: CPU vs. GPU I have very recently started looking into real-time fluid simulation. Idea is to make a game that would use 3D fluid simulation as a core gameplay mechanic.

Looking around the web, I found this article that compares the performance of fluid simulations on CPU and GPU. While the article itself is a bit dated, I assume that while CPUs and GPUs today are faster, the performance ration between the two has stayed similar enough to keep the article relevant. Actually, comparing their hardware (Core 2 Quad Q6600 and GeForce 8800 GT) to today's hardware (eg. i5 6600K and GTX 1070), CPU has 230% performance gain, while GPU has staggering 1670% performance gain. This would make the article more relevant today than it was before (more than six times).

Now, using the biggest grid they tested with (GS, 128^3, page 7, table 2), GPU simulation was over 3000 times faster than the CPU simulation. Even if utilizing 4 cores (they were using only a single thread), it's still over 700-fold performance gain (back in the day, today that would go up to 5000-fold). Given the results for smaller grids, that difference would only increase with bigger grids than 128^3.

The question is, along with all the normal rendering the GPU is tasked with doing, is it viable to burden it with the task of computing the simulation too, in any case at all?

What's the use of rendering the graphics at 60FPS if fluid simulation runs at 10 steps per second, effectively making the game look like it's running at 10FPS? Wouldn't it be better if I rendered graphics at 30FPS, but could do the simulation at 30 steps per second as well?

Basically, the question is, what would take longer:

For the GPU to render a frame AND compute the simulation step

OR

For the CPU to compute rest of the game logic AND compute the simulation step.

I know that this heavily depends on the GPU involved and the remainder of the GPU and CPU load, but look at the whole thing this way:

Even if I used just 1% of the power of GPU, the speed would still be 7(50!) times greater than using the CPU.

I'm a big novice in when it comes to computer graphics, so I may have gotten it all wrong. Does anything I wrote make any sense, or is it just gibberish?

Let's go through the paper you mentioned and try to list the factors which will affect your decision on whether to use GPU or CPU for simulation.
I will also add some comments about my opinion for each factor.

Computation bound

A GPU program runs in a SIMT(Single instruction, multiple threads) model.
In this model, if some threads stall due to memory access or divergence,
thread scheduler will schedule another set of threads to run
to hide the memory latency.

As we can see it requires adequate computation load to make this mechanism work.
If one implementation is memory bound, we hardly benefit from the SIMT programming model.

Fortunately, fluid simulation is a computation bound task for most of the cases.

Locality

In the paper you mentioned we can observe perfect locality:
for each grid point we only have to examine its neighbors.

The actual memory access pattern depends on the finite difference scheme you use.
But for all grid based simulation methods(Eulerian or Lattice-Boltzmann method), I think the locality always presents.

Divergence

A warp (a group of 32 threads) in a GPU program can be executed in parallel if they follow the same code path. Otherwise the program diverges and the execution of each branch will be serialized. Divergence will hurt the performance.

In particle based simulations (such as SPH method) we usually have to query the nearest N particles. A tree-like data structure will be used.

In GPU a tree data structure may introduce divergence because particles may fall into different branches.

The paper you mentioned uses grid based methods, where all threads execute along the same code path (Jacobi or Gauss-Seidel iteration), so divergence is not a problem here.

Interactivity

In the paper it uses static boundary conditions.
For this case you just need to upload the boundary conditions to GPU memory only once.

If you have dynamic boundary conditions, for example, which are specified by the user at each frame, the overhead of memory transfer between GPU and CPU should be taken into consideration.

Spatial complexity

Uniform grid based simulations cannot handle very large computation volume, because the spatial complexity is cubic.

There are adaptive grid methods, which use relatively higher resolution for the computation region we are most interested in. But that would also bring in divergence.

Numerical issues

For fluid simulation you cannot decide the number of steps solely based on the performance/frame rate.

In grid based methods, the Courant–Friedrichs–Lewy (CFL) condition puts a constraint on how large simulation step you can have.
Given a fixed time step, too large or too small steps would cause instability and blow up the simulation.

In particle based methods and some stable grid based methods (such as the semi-Lagrangian method used in the paper), we can use relatively larger simulation steps.

But we still cannot increase the step size with no bound because of the accuracy.
For example in grid based methods a large step size would introduce too much numerical viscosity.

Summary

As a summary, if your simulation has strong convergence and locality, prefer a GPU implementation; otherwise, prefer a CPU one.

In practice, I will always implement a CPU version because it is easier to debug and it will be useful as a baseline.
Then I will profile it to locate the bottleneck and decide whether to have a GPU version.


Mesh Simplification Algorithms I'm currently looking into Mesh Simplification to batch-simplify a large amount of .obj files. It is necessary for these algorithms to preserve the visual representation of a mesh as well as possible.

During research I've stumbled over Garland & Heckberts Surface Simplification Using Quadric Error Metrics. Most of the frameworks I've inspected are making use of this algorithm for Mesh Simplification.

My question is, why are most frameworks not making use of seemingly more advanced algorithms e.g. Simplifying Surfaces with Color and Texture using Quadric Error Metrics or comparable? Is the Quadric Error Metric currently state of the art concerning simplification algorithms?

According to Polygon-Mesh-Processing, section 7.2.2. paragraph "Error quadrics"

  Error quadrics have major advantages regarding memory consumption and computational efficiency: each vertex $x$ stores a symmetric 4x4 matrix $Q$ only, and the error can efficiently be computed in constant time as $x^T Q x$ - no matter how many planes are associated to vertex $x$ during decimation. Because of this, error quadrics are one of the most frequently employed techniques in mesh decimation.

The author of the reference I mentioned specifically refers to the paper you mention in your question. My interpretation is that more recent methods might be more sophisticated but resource-wise quadric errors are still better.

Also I'd add is relatively easy to implement anyway.


Interpolation in Graphics Pipeline I am trying to program my own version of WEBGL graphics pipeline in python, however, I am confused as to where the color interpolation takes place in the pipeline. According to my research, it happens after the rasterizer has calculated the points covered by the primitive. Does that mean rasterizer has access to color attribute, if so, how is the color attribute passed to the rasterizer, as the inputs for rasterizer are vertices? Or is it happening in the fragment shader?

The rasterizer determines, which pixel is rendered depending on vertex positions that come out of the vertex shader. For each rasterized pixel, the rasterizer knows where it lies inside the triangle formed by its three positions. With the known position inside the triangle, the rasterizer can also interpolate the vertex values for each pixel. So it also calculates the interpolated color, in case your vertex shader passes a color down the pipeline. The interpolated value is then provided to the fragment shader. However, the fragment shader can still modify the color before it is finally rendered to the screen.

  Does that mean rasterizer has access to color attribute

It has full access to everything that comes out of the vertex shader. A vertex shader must always have a position as output (gl_Position). In some special cases also other outputs are required. However, if your initial vertices had a color, but the color is not passed down the pipeline by the vertex shader, the rasterizer won't produce an interpolated color. It only interpolates each variable/attribute, that comes out of the vertex shader.

  how is the color attribute passed to the rasterizer, as the inputs for rasterizer are vertices?

You can define arbitrary outputs in your vertex shader. Even if the initially submitted vertex, did not have a color attribute, you can add a color output in the vertex shader. The data the rasterizer gets per vertex is just the vertex shader outputs. A vertex is a data point containing a position and optional additional values/attributes. So if a vertex has a color attribute, the rasterizer can see it, since it is part of the vertex.

Note that the vertices you pass into the vertex shader and the vertices that come out of it are not the same and might differ.

  Or is it happening in the fragment shader?

No, the fragment shader receives already interpolated values as input. But it can decide to pass it directly, ignore it or modify it as you wish. If you just pass it through, you will see the interpolated vertex colors.

Further information can be found on this site


Calculating the gradient of a triangular mesh This question is regarding a homework assignment (want to be upfront because many people on stack exchange don't like helping with homework questions).

I have a triangular mesh, which is defined by a set of vertices and a set of faces.
I want to calculate the discrete gradient of the mesh, and I even got instructions on how to implement it. The problem is that even after reading them multiple times, I don't understand them...

The implementation instructions:

My Problem:

I don't understand how to implement the marked sum, which in turn prevents me from constructing the following E matrix.

I would appreciate any help. I'm not looking for specific code examples, rather an explanation/example of the calculation for a single triangle.

A function $f$ on your triangulated surface is an assignment of real numbers on the vertices of the triangulation and therefore $f \in \mathbb{R}^{|\mathcal{V}|}$. According to the continuous theory, the gradient should be a linear (differential) operator that takes a function and spits out a vector field. Hence, in the discrete theory, the gradient should be a linear operator that takes a function $f \in \mathbb{R}^{|\mathcal{V}|}$ and spit out some kind of a discrete version of a vector field. In your case, the vector field is given as an assignment of a vector to each triangle of the triangulation. That is why the discrete gradient operator should be a linear operator, i.e. a linear transformation
$$\text{grad} : \mathbb{R}^{\mathcal{|V|}} \to \mathbb{R}^{3|\mathcal{F}|}$$
which is represented by a matrix $\text{grad} \in \mathbb{R}^{3|\mathcal{F}| \times |\mathcal{V}|}$. In the continuous theory, the gradient is determined only by local data, i.e. the behaviou of the function near the point at which the gradient is being calculated and by the geometry near that point. Therefore, in the discrete theory, the gradient is determined only by the geometry of one triangle and the values of the function at the triangle's vertices. Let the triangle $j \in  \mathcal{F}$ have vertices denoted (according to the instructions' convention) by $1, 2, 3$. The labels are set up so that the vertices $1,2,3$ define the labels of the opposing edges $\vec{e}_{j_1}, \vec{e}_{j_2}, \vec{e}_{j_3}$, i.e. for the vertex  $i$ the edge opposite to the vertex $i$ is denoted by $\vec{e}_{j_i}$, where the latter vector is oriented so that the vectors form a closed chain of vectors summing to zero in a counterclockwise direction.
Hence, the gradient can be defined as
$$(\text{grad}\,f)(j) = \frac{1}{2\text{Area}(j)}\, \sum_{i=1}^{3} f_i\, J\vec{e}_{j_i}$$ Or to write it in coordinates,
$$\begin{bmatrix} (\text{grad}\,f)(j)_1\\ (\text{grad}\,f)(j)_2\\(\text{grad}\,f)(j)_3\end{bmatrix} = \frac{1}{2\text{Area}(j)}\left( f_1\, \begin{bmatrix} (Je_{j_1})_1\\ (Je_{j_1})_2\\(Je_{j_1})_3\end{bmatrix} +
f_2\, \begin{bmatrix} (Je_{j_2})_1\\ (Je_{j_2})_2\\(Je_{j_2})_3\end{bmatrix} + f_3\, \begin{bmatrix} (Je_{j_3})_1\\ (Je_{j_3})_2\\(Je_{j_3})_3\end{bmatrix}\right)$$ and in matrix form
$$\begin{bmatrix} (\text{grad}\,f)(j)_1\\ (\text{grad}\,f)(j)_2\\(\text{grad}\,f)(j)_3\end{bmatrix} = \frac{1}{2\text{Area}(j)}\, \begin{bmatrix} (Je_{j_1})_1 &  (Je_{j_2})_1 & (Je_{j_3})_1 \\ (Je_{j_1})_2 & (Je_{j_2})_2 & (Je_{j_3})_2\\(Je_{j_1})_3 & (Je_{j_2})_3 & (Je_{j_3})_3 \end{bmatrix} \begin{bmatrix} f_1\\ f_2\\f_3\end{bmatrix} $$
So, for the matrix $E \in \mathbb{R}^{3|\mathcal{F}|\times|\mathcal{V}|}$ is defined as follows. Let $j$ be a triangle and $i$ one of its vertices. Take the edge $e_{j_i}$ of triangle $j$ opposite to the vertex $i$, and consider the vector $\vec{e}_{j_i}$ along the edge, starting from one vertex, different from $i$, to the other vertex, different from $i$, oriented so that the the vector follows counterclockwise orientation of the boundary of the triangle $j$. Then rotate the vector $\vec{e}_{j_i}$ by $90^{\circ}$ so that it points inside the triangle $j$. Denote this rotated vector by  $$J\vec{e}_{j_i} = \begin{bmatrix} (Je_{j_i})_1\\ (Je_{j_i})_2\\(Je_{j_i})_3\end{bmatrix}$$ Then fill up the following entries of the matrix $E \in \mathbb{R}^{3|\mathcal{F}|\times|\mathcal{V}|}$:
\begin{align}
&E(j,i) = (Je_{j_i})_1\\
&E(j + |\mathcal{F}|, i) = (Je_{j_i})_2\\
&E(j + 2|\mathcal{F}|, i) = (Je_{j_i})_3
\end{align}
You can rotate the vector $\vec{e}_{j_i}$ by using the cross-product operation twice. Take two of the edge-vectors of the triangle $j$, say $\vec{e}_{j_1}$ and $\vec{e}_{j_2}$, and calculate the unit normal vector to the triangle $j$:
$$\vec{n}_j = \frac{1}{\|\vec{e}_{j_1} \times \vec{e}_{j_2}\|}\,\Big(\vec{e}_{j_1} \times \vec{e}_{j_2}\Big)$$ It doesn't matter whcih two out of the three edge-vector you would choose, the result is always the same unit normal $\vec{n}_j$. Then
$$J\vec{e}_{j_i} = \vec{n}_j \times \vec{e}_{j_i}$$


How to know when rendering is complete in WebGL? gl.drawArrays()/gl.drawElements() initiates a drawing and returns immediately.
There is also (non-recommended) gl.finish() that (theoretically) blocks execution until rendering is complete.

Is there a way to receive event when rendering is complete, or other ways to track status of rendering, without blocking execution of the main thread? If there are, how well they work with Offscreen rendering (to a buffer)?

You can utilize ARB_sync or in other words sync objects which have been core since 3.2.

From the point-of-view of OpenGL then right after issuing a specific command (you want to know whether has finished), you'd insert a fence.

Say you want to check if a glDrawArrays() call has been executed.

glDrawArrays(...);
GLsync sync = glFenceSync(GL_SYNC_GPU_COMMANDS_COMPLETE, 0);

Note that if glFenceSync() fails it will return 0.

You can now check whether it has finished by doing:

GLint signaled = 0;
glGetSynciv(sync, GL_SYNC_STATUS, 1, NULL, &signaled);

if (signaled == GL_SIGNALED)
    // Done
else
    // Not done

You can then of course repeatably call glGetSynciv() and check when you receive GL_SIGNALED.

If you want to completely block until it's done then you can do:

GLenum status = glClientWaitSync(sync, 0, 0);

if (status == GL_CONDITION_SATISFIED)
    // Done

It blocks and waits for up to timeout nanoseconds (the last parameter).

Remember to delete the sync object again:

glDeleteSync(sync);

When it comes to WebGL. Then note that sync objects are not supported in WebGL 1.0. They are however in WebGL 2.0 in the form of WebGLSync.

The equivalent to the above code in WebGL 2.0 would be the following:

var sync = gl.fenceSync(gl.SYNC_GPU_COMMANDS_COMPLETE, 0);

var signaled = gl.getSyncParameter(sync, gl.SYNC_STATUS);

if (signaled == gl.SIGNALED)
    // Done
else
    // Not done

var status = gl.clientWaitSync(sync, 0, 0);

if (status == gl.CONDITION_SATISFIED)
    // Done

gl.deleteSync(sync);


Where do computer graphic engineers look for job ads? This is kind of a meta-question: We are a neuroscience lab looking for an engineer to develop virtual environments for experiments. Since it's not our usual field of job advertisement we do not know where computer graphics people usually look for job ads. A top-3 list of of places you would frequent to look for jobs would be very much appreciated.

There are several major Computer Graphics publications that have a jobs section. Try Siggraph for example. I'm pretty sure I saw a similar thing for Eurographics, but I can't find it right now.
Furthermore, you can look for applicants at the conferences themselves, if you have the resources to do so.

If you accept students that just finish university, you should put up an ad there (or tell the computer graphics professor to spread the word - my professor was kind enough to distribute offers to us every now and then).
Apart from that, you'll probably find most graphics programmers in computer games related fields. Gamasutra has a jobs section, although I'm not sure they let non-games related companies advertise there.

Moreover, Stackoverflow has a job offers section. I never really used it myself, but it's probably worth looking into. I got quite a few computer graphics related offers, so my guess is that you can advertise specifically to people with tags like OpenGL and Rendering as their favourite tags.


What is the difference between glossy and specular reflection? What is the difference between glossy and specular reflection?

What is their relations with BRDF?

The charts you show aren't showing two different phenomena - "glossy reflection" and "specular reflection" - they're showing two parameters of specular reflection. One is the specularity or specular colour and gives the amount or brightness of the specular reflection. The other is the glossiness or roughness and shows how sharp the specular reflection is.

Put another way, if you picture the curve of the specular reflection over changing angle, the specularity (the vertical axis on your charts) gives the height of the peak - the maximum brightness - and the glossiness gives the width of the peak - the size of the highlight. The highlight gets narrower with increasing glossiness, whereas roughness is the inverse of this.

BRDF is more general: it's a function that tells you how much light is reflected in a given direction (view direction) from a given direction (light direction). Usually (for most materials) we approximate a BRDF using a diffuse term and a specular term.


glTF animation keyframe question I have an animated cube with 5 keyframes and when I export it to glTF with blender, in the file I can only see 3 keyframes:

But when I viewed the gltf model with viewer all 5 keyframes worked well in the animation. Whats the explanation of this ?
My blend file if you are interested: https://files.fm/u/ujs4w23g

You're seeing channels and samplers there, not individual keyframes.  In this case, one animation is simultaneously targeting the translation, rotation, and scale channels of the same node, with three separate "samplers" (sets of keyframes per channel).

Not shown above, your glTF file has a section called accessors that tells viewers how to slice out portions of binary data from an associated .bin file.  The .bin file contains mostly mesh position/normal/UV data, but also contains the keyframe times and values.

So in the above snippet, that first channel targets the translation of node 3 with sampler 0 (the first sampler).  The sampler there asks for LINEAR interpolation of keyframes from animation times (input: 8) for translation keyframe values (output: 9).  In the accessors section, accessors 8 and 9 (using zero-based indexing) are references to the keyframe times (in 8) and values (in 9).  They are separate because the data type of the output depends on what's being targeted (rotations are vec4 quaternions for example, while translations and scales are vec3, and the input times are just floats).

The accessors in question (8 and 9 for example) will contain a value "count" that effectively tells you the number of keyframes.  If you have 5 keyframes for example, accessor 8 should have "count": 5 keyframe times, and accessor 9 will also have "count": 5 keyframe values.  The glTF Validator will flag an error if these counts don't match.


How to check which API's are available on a given machine? I'm building an engine, which has Vulkan for its primary rendering engine. But to have at least some backwards compatibility with devices that don't have drivers for it (mainly mobile) I want to implement an OpenGL fallback. Now, how do I check what API's are available in the current system?

I want to check if Vulkan support exists, if not then if OpenGL support exists and if not that then crash.

Basic Vulkan availability can be checked by the presence of the loader dynamic library. This will reside in a standard place where you can load it with dlopen or LoadLibrary.

If it fails to load then vulkan is not installed. If it does load then you can get the vkGetInstanceProcAddr function pointer from it with dlsymor GetProcAddress. After that you can query the devices as normal and decide whether or not it's sufficient to support your app.