Implementing the example of Walter et al. (2007) paper As the title suggests I'm trying to implement the last images of the "Microfacet Models for Refraction through Rough Surfaces" Paper by Walter et al. in OpenGL
I "think" (I had to put that into quotation marks) I know how the microfacet model should work and hopefully am only stuck on practical execution.
So I started by implementing the GGX formulas for the Normal Distribution, Fresnel and Geometry Function.
Initially and still I'm not so sure how to get the color of the object behind the glass into the formulas. My first thought was to create a cubemap around the slate of glass and then use the outgoing direction vectors (o_t and o_r) to sample the cubemap. But then I'm still not so sure how to incorporate that into the larger picture. Going by my first thought again I just multiplied the result of the BTFD with the sample of the o_t vector but apparently the BTDF was really big so the whole slate turned white (possible bug?). After dividing the result a few times some washed-up version of what was supposed to show up appeared.
Also I think I read somewhere that the reflection and transmission should be handled seperatly depending on the result of the Fresnel formula.
Or should it be handled at the same time (possibly somethink like : BRDF * sample_of_reflection + BTDF * sample_of_refraction)?
And another thing I found curious is the given equation for sampling:
$\theta = arctan(a * sqrt(rand1) / sqrt(1 - rand1))$
$\phi = 2 * \pi * rand2$
After some playing around with this function I noticed that is basically something akin to a gaussian distribution pointing towards the positive z-axis. But shouldn't the distribution give samples which are distributed around the surface normal?
I'm wondering if I have to add an additional pair of quotation marks to my earlier statement...
So anyway here is the pseudocode for my implementation until now:
for(#samplecount)
{
 //get a sample m
 vec3 m = drawsample();

 //calculate normal and incoming vector
 vec3 i = normalize(viewPosition - fragmentPosition);
 vec3 n = normalize(Normal);

 // calculate outgoing vector
 vec3 o_r = calculate_like_paper();
 vec3 o_t = calculate_like_paper();

 //sample cubemap
 vec3 reflection = sampleCubemap();
 vec3 refraction = sampleCubemap();

 //calculate halfvectors
 vec3 h_r = calculate_like_paper();
 vec3 h_t = calculate_like_paper();

 //calculate NDF, Fresnel and Geometry
 float D = GGX_D(h_r);
 float G = GGX_G(i, o_r, h_r);
 float F = GGX_F(i, h_r);

 //calculate BSDF, BRDF & BTDF
 float BRDF = F * G * D / (4.0 * abs(dot(i, n)) * abs(dot(o_r, n)));
 float BTDF = longFormula();

 float BSDF = BRDF + BTDF

 vec3 result += BRDF * reflection + BTDF * refraction //?
}
result /= #samplecount;

Thank you if you take your time to answer and I'm relatively new to StackExchange so I could definitely do with some feedback to improve the way I ask questions.
Edit:
So if anyone found this question and has similar questions Epic Games has some nice notes on this topic:    https://blog.selfshadow.com/publications/s2013-shading-course/karis/s2013_pbs_epic_notes_v2.pdf

Initially and still I'm not so sure how to get the color of the object behind the glass into the formulas.

Normal, this was written with path / ray tracers in mind where that part is easy. Your idea of a cube map might be ok for some use cases (eg. reasonably rough surface for the distance to the surrounding objects). It is not a general solution however. That would likely require GPU ray tracing.

  Going by my first thought again I just multiplied the result of the BTFD with the sample of the o_t vector but apparently the BTDF was really big so the whole slate turned white (possible bug?).

I'm writing this from memory but I think you need to divide by the PDF. Which means that your weights will be close to 1. But not quite 1 as the sampling distributions don't include the shadowing terms.

  Also I think I read somewhere that the reflection and transmission should be handled seperatly depending on the result of the Fresnel formula. Or should it be handled at the same time (possibly somethink like : BRDF * sample_of_reflection + BTDF * sample_of_refraction)?

A classic path tracer would randomly pick either reflection or refraction based on the fresnel coefficient. That does efficient sampling. But if you can easily get both from a cube map, you can also blend them with the fresnel coefficient.

  After some playing around with this function I noticed that is basically something akin to a gaussian distribution pointing towards the positive z-axis. But shouldn't the distribution give samples which are distributed around the surface normal?

Yes, you need to transform the generated direction. It is mentionned in section 5.2, after equation (24), that $\theta_m$ is the angle between $m$ (microfacet normal) and $n$ (surface normal). They don't go into great detail as this way of defining microfacet models goes back to much older articles.

The short version is that you build an orthonormal basis using the surface normal as z and two other perpendicular vectors as x and y. Here it does not matter which as the distribution is isotropic, as long as they are perpendicular to each other and to the normal. Then you transform using that basis.


What is the "dipole approximation" for subsurface scattering? If you read papers about subsurface scattering, you'll frequently come across references to something called the "dipole approximation".  This term seems to go back to the paper A Practical Model for Subsurface Light Transport by Henrik Wann Jensen et al, but this paper is pretty difficult to understand.

Can anyone explain in relatively simple terms what the dipole approximation is and how it's used in rendering subsurface scattering?

The assumption underlying such model is the same as lots of other models for skin rendering; the subsurface scattering can be approximated as a diffusion phenomenon. This is good because in highly scattering media, the distribution of light loses dependency from the angle and tends to isotropy.

The dipole approximation is a formulation for the resolution of such diffusion problem in an analytical fashion.

Basically they start by approximating the BSSRDF as a multiple scattering and single scattering component. The multiple scattering is then defined as:

Where $F_t$ are Fresnel terms and $R$ is the diffusion profile expressed as function of the distance between the entry and exit point.

This $R$ is referred to as diffusion profile and they formulate this profile via a dipole approximation. The contribution of the incoming light ray is considered to be the one of two virtual sources: one negative beneath the surface and one positive above it (that's why dipole)

Here in the picture r is the $\|x_i - x_o\|$ above.  The contribution of those light sources is dependent on various factors such as the distance of the light from the surface, scattering coefficient etc. (See below for a more detailed description of the formula itself).

This model only account for multiple scattering events, but that's fine enough for skin. It must be noticed though that for some translucent materials (e.g. smoke and marble) the single scattering is fundamental. That paper propose a single scattering formulation, but is expensive.

The diffusion profile is usually approximated for real-time application as a series of gaussian blurs (like in the seminal works of D'Eon et al. in GPU Gems 3 then used for the Jimenez's SSSSS) so to make it practical for real time scenarios. In this wonderful paper there are details on such approximation.
A picture from that paper show actually how good is this formulation:

As side note the dipole approximation assumes that the material is semi-infinite, however this assumption doesn’t hold with thin slabs and multi-layered material such as the skin. Building on the dipole work, Donner and Jensen [2005] proposed the multi-pole approximation that accounts for the dipole problems.
With this model instead of a single dipole, the authors use a set of them to describe the scattering phenomenon. In such formulation the reflectance and transmittance profiles can be obtained by summing up the contribution of the different dipoles involved

EDIT:
I am putting here the answers to a couple of @NathanReed 's questions in the comment section:

  Even with the diffusion profile approximation, the BSSRDF model still requires integrating over a radius of nearby points on the surface to gather incoming light, correct? How is that accomplished in, say, a path tracer? Do you have to build some data structure so you can sample points on the surface nearby a given point?

The BSSRDF approximation still need to be integrated over a certain area, yes.

In the paper linked they used a Montecarlo ray-tracer randomly sampling around a point with a density defined as:

$\sigma_{tr}e^{-\sigma_{tr}d}$

Where that sigma value is the effective extinction coefficient defined below ( it is dependent on scattering and absorbing coefficient, which are properties of the material) and d is the distance to the point we are evaluating. This density is this way defined because the diffusion term has exponential fall-off.

In [Jensen and Buhler 2002] they proposed an acceleration technique. One of the main concepts was to decouple the sampling from the evaluation of the diffusion term. This way they perform a hierarchical evaluation of the information computed during the sampling phase to cluster together distant samples when it comes to evaluating the diffusion. The implementation described in the paper uses an octree as structure.
This technique, according to the paper, is order of magnitude faster than the full Monte Carlo integration.
Unfortunately I never got myself into an off-line implementation, so I can't help more than this.

In the real-time sum-of-Gaussians approximations the correct radius is implicitly set when defining the variance of the Gaussian blurs that need to be applied.

  Why one positive and one negative light? Is the goal for them to cancel each other in some way?

Yes, the dipole source method (which dates way before Jensen's paper) is such defined to satisfy some boundary condition. Specifically the fluence must be zero at a certain extrapolated boundary that has a distance from the surface of $2AD$ where

Being $F_{dr}$ the fresnel reflectivity of the slab considered and that sigma value is the reduced extinction coefficient described below.

EDIT2: I have expanded (a tiny bit) some of the concepts in this answer in a blog post: http://bit.ly/1Q82rqT

For those who are not scared by lots of greek letters in a formula, here's an extract from my thesis where the reflectance profile is briefly described in each term:


Terminology: Volumetric Model I am reading a paper TileGAN: Synthesis of Large-Scale Non-Homogeneous Textures
available here, and in the section entitled Selected Applications of GANS (i.e. applications of Generative Adversarial networks), they make claim that recent papers in computer grahics apply GANs
to :

Volumetric modeling of shapes

A quick google search of this term does not yield great results for a definition of this word. What does the term "volumetric modeling" mean?

Volumetric Modeling usually refers to using a regular 3D grid of voxels, analogous to 2D pixels, to define properties of an object at points or small regions of space.

While more complex data might be stored at each voxel, often each contains a simple vector of values which can be interpreted directly as density or material properties for analysis and rendering. There is a whole literature on such techniques (search for Volume Rendering), often in the context of medical imaging where e.g. MRI scanners produce such data directly.

It is natural to consider extending techniques for generating images composed of 2D pixels to 3D voxels and modeling solids.


Name and influence of style used for futuristic line patterns? What is the name of the style of the line graphics used in the image below? The line patterns seem to envelope the shape of the woman maybe algorithmically somehow, becoming denser and yellow on the chest.
Are there other artists that employ this technique, or where it was borrowed from?
Besides the line patterns, the coloring of the lines gives a holographic sort of feeling. Is there also a distinct style name for the coloring scheme used for the lines?
Any ideas overall on which software and computer graphics/machine learning techniques were used to create the line patterns and colors?

That looks a lot like it’s based on the straight skeleton of some outline shapes drawn on the image. You can see similar structures in the middle one of these diagrams from a research page by Stefan Huber, one of the researchers who’s published a lot of work on straight skeletons:


correct rgb or cmyk code from some proportion of cyan, magenta and yellow I am trying to find a way to go from some proportion of cyan, magenta and yellow where:

cyan: 33 % + magenta : 33% + yellow : 33% = 100% black

so each is represented as a percentage of the sum total. mixing 50% magenta and 50 % yellow should result in red. Mixing some colour with its complement would in effect mix some proportion of all three primaries and result in some amount of black and pulling it further towards one of the primaries, so mixing red and blue would mix cmy in some proportion which would result in some amount of black and a balance of the other two primaries so it would just change chroma.

Any help is appreciated. I know that the gamuts of devices and colour models vary so it doesn't need to be perfect, it just needs to be intuitive for someone familiar with the cmy colour wheel to be able to use.

The desired output is an rgb colour code or a cmyk that could then be converted to rgb.

There is no white so you're limited to the hues and shades that can be formed from the three primaries. I'm okay with that.

Hey guys, I'm still trying to find a solution to this. If anyone could help it would be great.

This is for a game, the input is derived from some time value that represents a proportion of primary paints. Sort of.

I realize that in cmyk k stands for key and is a black dye that is purer than the black that can be obtained from mixing the primaries. In my game cmyk is unimportant, only that I can mix three primary colours cyan, magenta and yellow to mix the colour wheel.

It is unlikely that black will even be required, but the chroma effect of mixing some proportion of all three primaries together is required as I would want more than just the hues.  I appreciate that lightness of the hues is not possible without white but that is also fine.

I want it so that given some floating point value for representing some proportion of each primary, I can calculate that as percentages and then resolve that to an rgb colour code. It need not be a perfect conversion as only the rgb colour will be displayed, the cmy will just be for the calculation. A close approximation will suffice.

I don't need an especially wide gamut. I just need to be able to mix some proportion of the paints to mix a colour palette. If the player mixes equal parts of each primary then it would be black, if they keep mixing in magenta then it will become more and more magenta again as the volume of magenta dwarfs the volume of black.

If you mix red and blue you're mixing magenta and yellow with magenta and cyan.

I hope that clarifies some of the questions. The goal is to take the intuitive representation expressed to the player, three primary colours, and resolve that to a colour code that can be used to actually render to the screen.

The player will be able to clear the colour so they can then return to a pure primary colour. But to mix any particular colour they will do so by mixing the primary colours. Hue, chroma and brightness should be possible though lightness isn't possible without white as this is subtractive.

First off, the CMYK model includes black as its own channel, so you typically don't mix a combo of cyan, magenta & yellow to get black, you add black directly as its own independent element. There are a number of reasons for using black directly & without knowing your context, it's difficult to advise you on how to get by without it. What kind of black should I use when designing for CMYK print? on the graphic design SE has some in depth answers regarding use of black by itself & as a mixture (sometimes called composite black).

Second, CMYK is a subtractive model for mixing inks based on the notion of reducing brightness. RGB is an additive model based on mixing lights. Because they use different models & are both context dependent, there isn't a generalized conversion formula. The RGB to CMYK and back algorithm question on SO has a number of in depth answers regarding possible conversion algorithms. Again, it's hard to know what to suggest when you haven't clarified what you're using the colors for.


Pixel packed texture source I am grabbing video from a web cam using Microsoft Media Foundation. The image data is in YUY2 format. The pixels are packed in a 4:2:2 ratio. The color format is YCbCr. The color data gets repeated 2x. Ex the packed pixel data is:

y0 u y1 v

Gets unpacked to 2 pixels:

y0 u v and y1 u v

I want to use this data as an OpenGL texture. The question is: is there a way to pass this type of texture to glTexImage2D as-is? Or do I need to unpack it first? I would like you keep the YCbCr color and convert to RGBA in a shader.

(I know I can use OpenCV to get video - I've already done that. I am trying a more low level solution mostly as a learning experience).

The question is: is there a way to pass this type of texture to glTexImage2D as-is?

Yes; you can just pass it as-is, but (looking at the docs) it is not supported directly.  You'll need a custom shader to interpret it.

Depending on your needs, expanding the pixels first (or even doing the full conversion CPU-side) may be worthwhile.  At a guess, I'd say that expanding the pixels (as you copy from the camera's driver buffer into a staging buffer for upload to the GPU) is a pretty consistently good idea, unless you're extremely bandwidth-saturated.  I'd add the color-space conversion for easier debugging, or if the image doesn't update frequently.


Data structure and algorithm for clipping triangulation with leaf nodes of an octree I have an application in which I am using an octree to store a volume mesh of axis-aligned bounding boxes (AABBs).

Given a water-tight manifold triangle mesh, I need to:

find if an AABB is intersected by or completely inside/outside of the surface mesh,
clip the surface mesh with the intersected AABBs to generate triangles that completely lie within each AABB.

The triangulation and the octree containing the AABBs are both dynamic. The number of leaf nodes in the octree is huge. The number of triangles in the surface mesh is much smaller (O(10^9 - 10^13) octree nodes, vs O(10^6) triangles).

Which data-structures and algorithm are suitable for my problem?

Right now I:

store the triangles in the same octree as the volume mesh,
store each triangle in the smallest octree node that contains it,
clip the triangle mesh with a single AABB by traversing from that AABB to both the root node and its leafs clipping each triangle contained in the nodes with the AABB.

The triangles in the nodes until the leafs are fully contained within the AABB and don't need any "clipping" (the AABB just contains those triangles), while the ones contained in the nodes from the AABB to the root need clipping. However:

due to the way I am storing the triangles (in the smallest octree node that fully contains them) I don't have an upper bound in the maximum number of triangles that can be stored within each single octree node, so I don't have an upper bound in the number of triangles that have to be tested against a single AABB.
if I just want to test if an AABB is intersected by the triangle mesh, I have to test all triangles between that AABB and the root node which might be expensive. Ideally I would like to have a very fast way to test, and then clip the mesh if the test is true.
currently I have no fast way of determining if a node is inside/outside/intersected by the mesh. I could construct a signed distance field (which is expensive), or perform some ray casting (which is also expensive), maybe there is a better solution or maybe I just need to precompute something to speed this up every time I move the triangle mesh.
moving the triangle mesh requires manipulating the octree (I don't know if this can be avoided). Ideally I would like to generate an octree for the triangle mesh once, and then just move the mesh using a single transformation matrix. However, then I would need to have some sort of mapping between "the octree containing the triangle mesh" and "the octree of my volume mesh". Maybe this mapping is trivial but I haven't figured it out yet. This would save me from manipulating the octree when I move the mesh and maybe the coordinate transformations that would be required are negligible with the cost of clipping.

Rather than making one spatial subdivision structure do double duty in representing both the voxels and the triangles, I would suggest creating a separate BVH for the mesh. You can find many articles and papers about BVH-building algorithms on the web. It's likely to be a more efficiently queryable representation of the mesh than the octree would be.

Given the BVH, it's easy to determine whether a given voxel might intersect the mesh by starting at the BVH root and traversing to child nodes that intersect the voxel box. Depending on the quality of the BVH, i.e. how tightly it fits the mesh, many voxels (or even higher-level octree nodes) may be able to be eliminated with only a few checks. For voxels that do intersect the mesh surface, the BVH traversal will reach down to the leaves, where you can accumulate the triangles into a list for clipping.

If the BVH is built in the mesh's local space, the mesh can easily be moved or transformed without needing to update the octree. (If translation is the only transform needed, then the BVH nodes will always be axis-aligned relative to the voxels, which simplifies the intersection test to an AABB overlap test; if more general transforms are needed, you'd have to use a more general OBB vs OBB test.)

However, note that a BVH doesn't lend itself that well to determining whether a things are inside versus outside a watertight mesh. If that's important to you (it wasn't clear to me whether it is), then you might want to look into using a BSP tree instead of a BVH. A BSP tree can be used for intersection testing similarly to a BVH, but additionally can represent the exact boundary of the mesh so that it can be used to determine whether a point (or voxel) is inside or outside. This property of BSP trees is widely used for collision detection.

An alternate approach to determining inside/outsideness is to use raycasting and count the number of intersections with the mesh (even = outside, odd = inside). The raycasting can be accelerated by the BVH as well.


Measure how long a rendered frame takes to arrive on a client from the cloud Say I am running a game in the cloud and I am playing that game on my client (the game is being streamed from the cloud to the client), be it a laptop, phone or calculator.

How can I work out how long a frame (of the game being played) takes to arrive at the client?

Try putting a timestamp over some key frames as the last step on your render pipeline. Then compare it to the local systems time. If both clocks are correct you should get a delay in ms (using unix rime-stamps).

Another idea to measure the round-trip-delay (might be important for UX reasons):
input to server,
server render,
result from to server on your screen
is to have a bot give an input than measure the time till the result is back


Mat4 that is written to a storage buffer in a compute shader has an altered value when read back I am attempting to use a compute shader to calculate joint transforms for animations.
I use a loop to calculate the global joint transforms from the local transforms. Relevant code below:
layout(set = 0, binding = 2) readonly buffer LocalTransforms {
    Similarity local_transforms[];
};

layout(set = 0, binding = 3) buffer GlobalTransforms {
    mat4 global_transforms[];
};

struct NodeAndParent {
    uint node_index;
    int parent_index;
};

layout(set = 0, binding = 4) readonly buffer DepthFirstNodes {
    NodeAndParent depth_first_nodes[];
};

void main() {
    uint index = gl_GlobalInvocationID.x;

    uint nodes_offset = index * num_nodes;

    if (nodes_offset >= global_transforms.length()) {
        return;
    }

    for (uint i = 0; i < num_nodes; i++) {
        NodeAndParent indices = depth_first_nodes[i];

        uint node_index = nodes_offset + indices.node_index;
        mat4 local_transform = similarity_to_mat4(local_transforms[node_index]);

        if (indices.parent_index != -1) {
            mat4 parent_transform = global_transforms[nodes_offset + indices.parent_index];
            global_transforms[node_index] = parent_transform * local_transform;
        } else {
            global_transforms[node_index] = local_transform;
        }
    }

There is a bug somewhere and I have been attempting to use renderdoc to debug it. I have realised that on the first iteration, one matrix is written to index 3 of of the buffer (right side image), but when it is read back as the parent transform on the second iteration (left image), the values reported in renderdoc are incorrect.

Note that the section of the buffer is not being used by any other thread, and I have an early-exit for threads that would be out-of-bounds of global_transforms. I've tested other threads and they all return early.
My question is this:

A) Is it possibly that renderdoc is reporting this incorrectly?
B) Is the value stored in the buffer really like that in that point in time? Would using a barrier help? What kind of barrier?
C) Is there some other problem with the code that could be causing this?

Thank you!

It appears that this is indeed a bug within renderdoc. I have encountered the bug I was debugging for in only 1 model, while all the others work fine. In every instance of using the renderdoc debugger, I get the same problem though.


Calculating intersection of polyline and line I have a convoluted polyline composed of vertices and straight segments and a separate point that is independent of the polyline. I am trying draw a straight new line from the point at a given angle and determine if the new line intersects the polyline and get the location of that intersection. If there are multiple intersections I want the location of the closest intersection.

I'm currently doing this by drawing a line an arbitrary (long) distance from the point at the desired angle and then intersecting it with the polyline using a python gis toolkit (shapely). If there are multiple intersections I sort them by distance and select the closest one.

This method works but is somewhat clumsy. Is there a more efficient method of calculating the closest intersection? It almost seems like ray tracing (of which I have minimal knowledge) but I can't find much online that applies to my case.

The other method that I contemplated was to iterate over every line segment in the polyline and use y = mx+b to see if the segment intersects the new line from the point. The polyline is potentially quite long with many segments, but I've also seen some sorting tricks online to make this method more efficient. Is there a method that I'm missing?

Given that you want to test for intersection against rays with many different starting points and directions, it's worth investigating raytracing-style acceleration structures, such as the bounding volume hierarchy (BVH). In 2D, this would look like a tree of axis-aligned bounding boxes that divide up the space. Each leaf node of this tree would store a reference to a small list of nearby segments of the polyline, as well as a bounding box that contains them. Higher nodes would store a bounding box that contains all their children.

There's a ton of material on BVH construction and traversal out there, so I'd recommend doing a few searches and reading up. It's not too difficult to implement a top-down construction method, by starting with the bounding box of the whole polyline and recursive splitting. Then, to use it for acceleration, when you do a ray query you can find which BVH nodes the ray touches and test only the segments in those nodes for intersections.

However, all that being said, I'd like to propose a different approach to your original problem of working with contour lines. It seems to me that this is a place where Delaunay triangulation can probably be very helpful. It basically constructs a triangle mesh that connects a set of input vertices and edges. For example, here is a contour map I found on the internet:

And now here it is with a constrained Delaunay triangulation, calculating using Jonathan Shewchuk's "Triangle" program:

As you can see, the triangulation gives you a lot of information about neighboring regions in the contour map, so I suspect that you could find a way to get what you want from it somehow. For instance, you could find all the triangles that touch the two contour lines you're interested in, and look at their edges, midpoints, and so on.


Why random monte carlo sampling instead of uniform sampling? Why is it that it's so common to use monte carlo randomized sample locations, instead of uniform sampling?

I'm assuming that taking randomized samples gives some benefit but I don't know what they could be.

Is anyone able to explain the advantage of randomized sample locations over uniform sample locations?

Sample locations with a uniform pattern will create aliasing in the output, whenever there are geometric features of size comparable to or smaller than the sampling grid. That's the reason why "jaggies" exist: because images are made of a uniform square pixel grid, and when you render (for example) an angled line without antialiasing, it crosses rows/columns of pixels at regular intervals, creating a regular pattern of stairstep artifacts in the resulting image.

Supersampling at a finer uniform grid will improve things, but the image will still have similar artifacts—just less badly. You can see this with MSAA, as in this comparison image from an NVIDIA presentation on temporal antialiasing:

The 8x MSAA image (which is not quite a grid but still has a repeating pattern) still plainly has jaggies in it, although they're antialiased jaggies. Compare to the TXAA result, which both has a higher effective sample count (due to temporal reuse) and uses a Gaussian rather than box filter for accumulating the samples.

On the other hand, random sampling produces noise instead of aliasing. There is no pattern to the sample locations, so no pattern to the resulting errors. Both aliasing and noise are errors due to not having enough samples to form a clean image, but arguably noise is the less visually-objectionable artifact.

On the other other hand, perfectly random sampling (in the sense of i.i.d. random variables) tends to exhibit a certain level of clumping. Purely by chance, some areas in the domain will have denser-than-average clumps of samples, and other areas will be lacking in samples; those areas will be, respectively, over-represented and under-represented in the resulting estimate.

The convergence rate of the Monte Carlo process can often by improved by using things like stratified sampling, low-discrepancy sequences, or blue noise. These are all strategies to generate "de-clumped" samples that are spaced out a bit more evenly than i.i.d. samples, but without creating any regular patterns that might lead to aliasing.


How updating a depth buffer works in GPU? Right now I'm trying to implement some sort of depth buffer in software and I have a huge problem when I'm writing to it. Having one mutex is absolute overkill. So I created a number of mutexes equal to the number of threads. I'm locking a mutex based on current pixel (pixel_index % mutexes_number) and this works better, but still very very slow. And I wonder how it's done in a real GPU? Is there a clever algorithm or hardware handles it?

In a real GPU, instead of having multiple cores trying to read/write the same region of the depth buffer and attempting to synchronize between them, the depth buffer is divided into tiles (such as 16×16 or 32×32), and each tile is assigned to a single core. That core is then responsible for all rasterization in that tile: any triangles that touch that tile will be rasterized (within that tile) by the owning core. Then there is no interference between cores, and no need for them to synchronize when accessing their part of the framebuffer.

This implies that triangles that touch multiple tiles will need to be rasterized by multiple cores. So, there is a work redistribution step between geometry processing (operations on vertices and triangles) and pixel processing.

In the geometry stage, each core might process a chunk of input primitives; then for each primitive, it can quickly determine which tiles the primitive touches (this is called "coarse rasterization"), and add the primitive to a queue for each core that owns one of the affected tiles.

Then, in the pixel stage, each core can read out the list of primitives in its queue, calculate pixel coverage for the tiles the core owns, and proceed to depth testing, pixel shading and updating the framebuffer, with no need of any further coordination with other cores.


How to use GLSL texelFetch? I have read the OpenGl documentation of texelFetch, which is:

gvec4 texelFetch(gsampler2D sampler, ivec2 P, int lod).

I know the first argument "sampler" is just a texture. But I am very confused about the second and third arguments.

According to the documentation, the second argument "P" is a texture coordinate. But it has the type ivec2, which means that it is a vector of integers. Shouldn't a texture coordinate be in the range [0, 1]?

And for the third argument "lod", in the documentation, it said "If present, specifies the level-of-detail within the texture from which the texel will be fetched." I have no idea how to set this argument...

Could anyone explain this and give a real example of how to use texelFetch?

Thank you!

OK, I have figured out this problem.

For the texture coordinates, there are two kind of texture coordinates. One is normalized texture coordinates, which is in the range [0, 1]. The other is texel space, which is in the range [0, size), where size is the size of the texture. For texelFetch(), the texel space is used.

For lod, it means the level of detail in the mipmap. We can simply use 0 for the base level (the original size).

Thus, an example of using texelFetch() should be:

vec4 texelValue= texelFetch(texture2D, ivec2(gl_FragCoord.xy), 0);


VR and frustum culling When rendering VR ( stereo view ) environments, do you guys recommend just doing 2 frustum checks for determining what is to be drawn during the frustum culling pass or is there some other check that would be able to combine both frusta?

It's pretty easy to create a single frustum that encloses both of the individual eye frusta, as shown in this diagram created by Cass Everitt at Oculus. You just have to place the vertex of this frustum between the eyes and behind them a little bit. You can also increase the near plane distance to match the original near plane of the eye frusta.

Such a frustum includes a little space that wasn't in the union of the original two frusta. There's a small volume horizontally between the two eyes; also, the diagram doesn't show the vertical dimension, but pulling the frustum vertex back makes it include some space above and below the original frusta. However, for practical culling purposes it probably doesn't matter. Frustum culling is usually conservative anyway, and the extra space is only a few centimeters in thickness.

It's also possible to simply cull against the original frustum top and bottom planes (which are shared between eyes) together with the outer side planes. These planes don't form a frustum, technically, but if using "the usual" culling algorithm that tests against one plane at a time, the algorithm will happily work on any set of planes you care to give it.

Sharing frustum culling, LOD selection, etc. between eyes, rather than re-doing it twice every frame, is a great way to optimize the CPU cost of stereo rendering. This is also a prerequisite if you want to use a rendering method that draws both eyes in a single pass, such as instanced stereo rendering.


Legendre Polynomial equation in Spherical Harmonics I recently started to read about spherical harmonics. I have a question about this spherical harmonics basis function equation which is mentioned in this StupidSH article:

What are those lm() and Re() used for?

The article can be found here: http://www.ppsloan.org/publications/StupidSH36.pdf

The notation Re() and Im() refer to the real and imaginary parts of a complex number.  Mathematicians and physicists are accustomed to using spherical harmonics (and Fourier transforms too) that are complex-valued, due to the factor $e^{im\phi}$.  You would then also have complex coefficients, in general, in the spherical harmonic expansion of a (real or complex) function.

Using Euler's formula, $e^{im\phi} = \cos(m\phi) + i\sin(m\phi)$.  So that factor encodes cosine and sine waves  (that oscillate $m$ times as you move around the equator of the sphere) in its real and imaginary parts, respectively.

When we know we're going to be working strictly with real-valued functions, it may be more convenient to use real-valued variants of the spherical harmonics, where $e^{im\phi}$ is replaced by either $\cos(m\phi)$ or $\sin(m\phi)$, and using real coefficients instead of complex ones.  We trade a single complex coefficient for two real coefficients, so we haven't lost any information or flexibility; it's essentially a change of basis.  This formulation just explicitly ensures that everything always comes out real.


What is an OpenGL VAO in a nutshell? Before I get downvoted. I am not asking how to use them, I know how to use them. I am trying to understand what they are. For example, an array is actually a contiguous section of memory, a linked list is actually just a clever way of using memory addresses, a 3D array is actually just a 1D array being used in a clever fashion...

Under that logic, VBO's are sections of GPU RAM that contain rendering data. They are thus "arrays". But then what is a VAO? My current understanding is that they are magical "boxes" that somehow store machine state information for a set of VBO's, but what are they actually?

Because for example, as far as I know, you MUST bind the VBO's under a VAO to get rendering output, if you just bind the VAO you won't get outpt, so what is their purpouse?

VAOs are essentially 'plumbing' objects that help get data from your buffers into your vertex shader ready for drawing. On the GPU this is handled by the vertex fetch stage, so a VAO is basically just a bundle of vertex fetch state corresponding to a particular model.

You can think of it as a bundle of pointers, but with somewhat more complexity than CPU-side pointers. Since OpenGL buffers are just a blob of untyped bytes by default (that's why you get a void* when you map them), the VAO handles type-casting (to vec3 or whatever) when fetching the data. It also deals with the size of the data not necessarily matching the stride between consecutive elements, and makes sure that each data item (position, normal, uv, etc.) is transmitted to the correct 'channel' in the vertex shader input.

You can render without a VAO in legacy OpenGL, but this is generally more of a PITA, since you need to bind each vertex attribute separately each time you draw the object. Encapsulating all these bindings in a VAO lets you set them up once, then you have a 'plug and play' object that simply needs to be bound before a draw call, and all your vertex data will be ready to go.


What is the difference between a point transformation and a vector transformation? This is what my lecturer told me in the coursework:

We only consider 4*4 matrices. These are used to rotate, scale or translate objects (or any combination of these operations). Matrices are also used later in the implementation of the virtual camera model. If you do not know the difference between a vector transformation and point transformation, look it up.

I can't seem to find an answer and made an account for this website just for this question.

Here's the simple answer.

In 4D, to be able to multiply them by a 4x4 matrix, vectors are represented as (x,y,z,0) and points are represented as (x,y,z,1).

Since the 4th row of a 4x4 matrix represents the translation of the matrix, the above representations make it so points are affected by translation, but vectors are not.

Both vectors and points are affected by the rotation, scaling, etc though.

Caveat:

There is deeper discussion to be had if you expect the vectors to have certain properties.  For instance, if you transform a triangle's normal by the same matrix you transform the triangle's vertices, it likely won't actually be the normal vector of that triangle anymore. This is because normal vectors have a sort of inverse relationship to the vertices that they are calculated from.


Building view transform matrices For a 3D scene in the world coordinates, its View Reference Point $\mathrm{VRP}$ is at $(5,-2,1)$, and a viewer is looking towards point $A=(1,1,1)$. Construct a transform matrix which will map world coordinate points to a right-handed $(UVN)$ viewing space, so that $\mathrm{VRP}$ is the origin, the line joining $\mathrm{VRP}$ to $A$ is the positive $N$ axis, and the view-up Vector is $(0,0,1)$.

To my knowledge, the final answer should be a single transform matrix.
To calculate the final matrix, I first find the matrix which translates the coordinate system to the to the origin in homogeneous matrix form:

Translation matrix:

$$
T=
        \begin{bmatrix}
        1 &0 &0 &-5 \\
        0 &1 &0& 2 \\
        0 &0 &1 &-1 \\
        0 &0 &0 &1 \\
        \end{bmatrix}
$$

Using the unit vectors of the coordinate axes, the resulting rotation matrix is:

$$
R=
        \begin{bmatrix}
        -0.6 &-0.8 &0 &0 \\
        0 &0 &0 &1 \\
        -0.8 &0.6 &0 &0 \\
        0 &0 &0 &1 \\
        \end{bmatrix}
$$
Then the final matrix (the final answer for full marks) would be the rotation matrix multiplied by the translation matrix:

$$
M=
        \begin{bmatrix}
        -0.6 &-0.8 &0 &1.4 \\
        0 &0 &0 &1 \\
        -0.8 &0.6 &0 &5.2 \\
        0 &0 &0 &1 \\
        \end{bmatrix}
$$
Is my method and final answer correct?

Following the answer to this question, I have calculated the translation matrix:

$$
T=
\begin{pmatrix}
1 & 0 & 0 & -5 \\
0 & 1 & 0 & 2 \\
0 & 0 & 1 & -1 \\
0 & 0 & 0 & 1 \\
\end{pmatrix}
$$

I have calculated the rotation matrix:

$$
R=
\begin{pmatrix}
-0.6 & -0.8 & 0 & 0 \\
0 & 0 & 1 & 0 \\
-0.8 & 0.6 & 0 & 0 \\
0 & 0 & 0 & 1 \\
\end{pmatrix}
$$

But what would the final transformation matrix $M$ be? My lecture slides tell me it would be rotation matrix multiplied by translation matrix, with the last column multiplied by $-1$ except for the $1$. This would equal:

$$
M = R \times T =
\begin{pmatrix}
-0.6 & -0.8 & 0 & -1.4 \\
0 & 0 & 1 & 1 \\
-0.8 & 0.6 & 0 & -5.2 \\
0 & 0 & 0 & 1 \\
\end{pmatrix}
$$

But the answer here just adds them together somehow. Which one is correct?

To solve the problem, we will flow three steps, first, calculate translation matrix, second, calculate rotation matrix, third, get transformation matrix.

Because translation is a affine transformation, we need to use a 4x4 matrix to represent translation. I find you use column vector post-multiply matrix. the result of the translation matrix is same as yours.

Translation matrix =

Then, same as your idea, we use basis vectors(same as unit vectors of the coordinate axes) to calculate rotation matrix.

basis z vector: we can get rotated basis z vector by using a vector from VRP to point A, and normalize it.

z = b(VRP) - a = [5,-2,1] - [1,1,1] = [4,-3,0] ,then, normalize to [0.8,-0.6,0]
basis x vector: we know basis vector is a vector perpendicular to z-up plane, we get the x vector by cross product up and z

x = up x z = [1,1,1] x [0.8 ,-0.6 ,0] = [0.6, 0.8, 0]
basis y vector, y is prependicular to z-x plane.

y = z x x = [0.8 ,-0.6, 0] x [0.6, 0.8, 0] = [0, 0, 1]

finally, the rotation matrix is:

Rotation Matrix =

The 4x4 matrix is:

Transformation matrix =

The transformation matrix is a matrix from Object Space to World Space, we should invert this matrix to get World Space to Camera Space matrix.(Thanks for @JarkkoL correcting me).

Refer to 3D Math Primer for Graphics and Game Developmen.

Following your request for clarification: I just combine the translation matrix and the rotation matrix, actually, It's the result translation matrix(T) multiply rotation matrix(R).

The rotation is a 3x3 matrix, we can extend the matrix to a 4x4 matrix with adding a dimension, the 4x4 rotation matrix is:

And the translation matrix is:

So, now we can calculate the transform matrix by translation matrix multiply(T) rotation matrix(R):

Cause the matrix multiply formula is too big for the 4x4 matrix, we just look at the 1st row, In the transform matrix(M), the M11 element equals to T11*R11+T12*R21+T13*R31+T14*R41, cause T12, T13, R41 is 0, so, the M11 equals to R11 right? And in the same way, M14 equals to T11*R14+T12*R24+T13*R34+T14*R44, only R44 equals to 1, so, the M14 equals to T14. so, I just simply put them together in my last answer. For the reason why we put the translation matrix on the left, you can check on the book that I gave you in my previous answer on page 91(translating first and then rotating).


How to draw an orthogonal graph from its edges and vertices data? I am writing a software and I need to represent an graph in a orthogonal manner from topological data (vector of edges,vertices and their connectivity data)

Graphs consist of a set of vertices and a set of edges, each connecting two vertices.A vertex may have any number of connected edges so it makes the problem a lot more complicated.

I have read some articles and its looks like that the Kandinsky model is the post popular one. However I just don't know the algorithm, any other solution (algorithm) that solve the problem is also very welcome.

Added after edit

The following picture shows a real world example for an electricity network which should be considered as raw data, in order to create a graph from this network, some preliminary tasks must be done.

Input Data:

The result I am looking for is something like below,
there are some characteristics if you take a look much closer :

The Red Polygon in the middle of the above picture(input data) represents an electricity substation which is a node itself and can be connected to more than 4 edges.
There are more red polygons but only one can be fit into the above picture however as you may see, the following picture could cover much more than a red polygon that means it can map a bigger area, so the following picture is much more denser.

In Schematics diagrams, red polygons (Substations) usually maintain their position against each other relatively so if we manage to see beyond the extents of the above map by zooming out for example, we should almost see a triangle that is obviously can be seen at the below while having the left one at the left, the down one at the down ..... (this is not a rule, but I thought it could be a head start for desired algorithm)

Orthogonal Diagram:

libCola

cola.js (a.k.a. WebCola) is a JavaScript based rewrite of libcola which works well with D3.js

http://marvl.infotech.monash.edu/webcola/

Gridified Layout example:

http://marvl.infotech.monash.edu/webcola/examples/dotpowergraph.html

OGDF

Open Graph Drawing Framework

Have an orthogonal layout

  Orthogonal: Ortholayout with modules for the steps of shape and
  compaction, ClusterOrthoLayout

http://www.ogdf.net/doku.php/ogdf:features

Check projects that uses OGDF

http://www.ogdf.net/doku.php/project:external

HOLA

Human-like Orthogonal Layout Algorithm

https://vimeo.com/150509722

Kieffer, Steve, Tim Dwyer, Kim Marriott, and Michael Wybrow. "Hola: Human-like orthogonal network layout." Visualization and Computer Graphics, IEEE Transactions on 22, no. 1 (2016): 349-358.


Understanding VAO and VBO I'm reading through Learn OpenGL to refresh the basic concepts as I haven't touched in quite some time.
Specifically I still think I cannot quite understand the meaning of VAO and VBO, the book mainly proceeds through examples it doesn't really give rigorous definitions.
About the VBO:

With the vertex data defined we’d like to send it as input to the
first process of the graphics pipeline: the vertex shader. This is
done by creating memory on the GPU where we store the vertex data,
configure how OpenGL should interpret the memory and specify how to
send the data to the graphics card. The vertex shader then processes
as much vertices as we tell it to from its memory.
We manage this memory via so called vertex buffer objects (VBO) that
can store a large number of vertices in the GPU’s memory. The
advantage of using those buffer objects is that we can send large
batches of data all at once to the graphics card, and keep it there if
there’s enough memory left, without having to send data one vertex at
a time. Sending data to the graphics card from the CPU is relatively
slow, so wherever we can we try to send as much data as possible at
once. Once the data is in the graphics card’s memory the vertex shader
has almost instant access to the vertices making it extremely fast

So my understanding of VBO they're essentially Buffer objects (bunch of bytes to be sent to the GPU) with the difference that VBO are specifically dedicated to Vertex Data. Is this correct?
About the VAO:
Here instead I don't really understand.

A vertex array object (also known as VAO) can be bound just
like a vertex buffer object and any subsequent vertex attribute calls
from that point on will be stored inside the VAO.

What does it mean any subsequent vertex attribute calls from that point on will be stored inside the VAO, I don't understand the "call be stored" bit, does it mean somewhere in the opengl context created we store like some data related to the vertex attribute calls (like the pair input output of the call? the output of the call? something related to the call?).

This has the advantage that when configuring vertex attribute pointers you only
have to make those calls once and whenever we want to draw the object,
we can just bind the corresponding VAO. This makes switching between
different vertex data and attribute configurations as easy as binding
a different VAO. All the state we just set is stored inside the VAO.

I don't understand the advantage here. I understand the "call made once", because they're stored in the VAO (whatever the "stored part means"). The switching part does maybe mean I can create multiple VAO each one capturing different Vertex Attributes calls and I can just bind each one of these when I need without calling again the vertex attribute?
For reference I've also found this question which I thought had an interesting answer.

So my understanding of VBO they're essentially Buffer objects (bunch of bytes to be sent to the GPU) with the difference that VBO are specifically dedicated to Vertex Data. Is this correct?

A "VBO" is not really a thing, and I really wish tutorials would stop pretending that they are.
You are correct in that there exist buffer objects. These are linear arrays of unformatted data that the GPU stores and can access for various processes. One of those "various processes" that the GPU can use them for is providing array data for vertex rendering operations.
But the buffer itself isn't special. It doesn't become a different thing just because you use it for vertex data, and there is no rule that says that a buffer you're currently using for vertex data cannot be used for other buffer usages too.
Note that this is different from how textures work. When you create a texture object and bind it as a 2D texture, that texture object forever becomes a 2D texture. You cannot later bind it as a 1D or a cubemap or whatever. Buffer objects aren't like that; where you bind them defines only how you're currently using them.

What does it mean "any subsequent vertex attribute calls from that point on will be stored inside the VAO"

This is yet another annoying tutorial trope: that objects "store calls" or are macros or other such nonsense.
Objects in OpenGL don't store calls; they store state. They're like structs; they have data members. Binding an object to the OpenGL context allows OpenGL operations that access certain state to find that state within the bound object. So if you call a function that modifies certain state that is from a bound object, that function will modify the state within the object.
When you bind a VAO, you are binding an object that stores the state used for vertex arrays. When you call a function that modifies the state for vertex arrays, that function will modify the state stored in the VAO currently bound. When you render, the rendering system will use the vertex array state found in the currently bound VAO.


What algorithm is used in the animation of the uTorrent 's "About window"? In a recent version of uTorrent , if you open the About Window, you will see an animated background , which is kind of waves that go on forever.
How can this be achieved? Is this kind of a well-known algorithm/class of algorithms?
Thanks.

As you discovered and mentioned in your self-answer, the pattern in the background appears to be a sum of sinusoidal gradients.

However, the example linked to in your answer is more complicated than that used by µTorrent. The background of the About window appears to be a static pattern, rather than the animated sinusoidal pattern used in the plasma post.

Several sinusoidal gradients have been summed to give a single image, and the illusion of movement is given by simply cycling the colours in that one image, rather than generating a number of different images. This is most noticeable if you focus on the centre of one of the rings of colour. In the µTorrent pattern you will notice that each ring stays in one place, and has colour flowing either into it or out of it. In contrast, the rings of colour in the fully animated pattern move around, occasionally dividing or merging.

The simplified approach used by µTorrent is reminiscent of animations used in the past when recalculating the sinusoidal patterns each frame was not realistic.


Forward Rendering Distortion Effect (example of effect i am trying to render)
Rendering Transparent Object in forward rendering is far easier. However I am having an issue when it comes to transparent glass like object that applies post processing like effect when seen through it.
I do know how to render "glass" that reflects "skybox" however I do not know how to render a glass like object that applies its distortion effect around its dynamic surroundings.
I need help figuring out how to render this effect.

An effect like that is most likely done as a second pass, after storing a copy of the color buffer.

When looking carefully, you can see some of the vertices from the shape of the effect above the character. So this scene in particular probably does something like this:

First render the scene into a color buffer, without the distortion effect.
Because it's not possible to both read from and write to a same frame buffer at the same time, copy it as is (blit) into another frame buffer. From now on, new draws will go into that new frame buffer.
In the new frame buffer, draw a mesh with the shape of the effect, using a shader that will fetch the texture of the first color buffer, with an offset depending on the normal. Also note that:

The mesh is opaque (no blending): it's the texture that makes it look transparent.
Although we don't see this in the screenshot, it's also perfectly possible to use the depth buffer as usual and have the effect intersect with the scene.

Finally a simpler effect, like rain drops on the screen, could be done this way:

First render the scene into a frame buffer, without the distortion effect.
Copy the entire frame buffer into another frame buffer using a custom shader. The shader will apply some offset to the texture coordinates (either directly or maybe using a distortion texture), thus distorting the image.


Mapping of cylinder to 2D plane I have a cylinder that has rectangular box regions to mark leakage problems. The location of a rectangular box is determined by its initial position in the longitudinal axis and its initial position in the circumferential axis in degree. The length  and width (in degrees, from 0° to 360°) of the boxes are also available.

How can I convert this cylinder to a plane surface so that I can find the location of the rectangular boxes in the 2D plane?
Here I have  three rectangles on the surface.

You already have a 2D parametrisation, don't you? One of the dimensions is the longitudal axis (in mm?) and the other is the circumferential axis (in degrees). The only problem I see is when you have rectangles wrapping around the 0/360-degree boundary. One workaround for that would be to duplicate each rectangle (or just the ones on the boundary) so that you get one copy on each side of the boundary. Does that help? And if you need to have a distance, and not an angle, for the circular dimension, that is readily available as $l = r a \pi/180$, where $r$ is the radius and $a$ is the angle in degrees.


Screenspace Normals - Creation, Normal Maps, and Unpacking I'm trying to condense my Deferred Rendering G-Buffer. So I have some questions about getting 2-component Screenspace Normals. I know Frostbite and Killzone (the only two AAA company's G-Buffers I could find) use them.

How are screenspace normals created, and is this step before or after using normal maps or bump maps? If it's done before using normal maps, how are normal maps going to be affected by the screenspace-ness of the normals, and if after, how can you justify using a Model-View matrix on all fragments rather on vertices? Isn't that a lot more calculations?

Finally, how are they unpacked? I realize you can get the blue component using pythagoras, but how are they returned to world space?

How are screenspace normals created, and is this step before or after using normal maps or bump maps?

They are created after using normal maps. In deferred rendering, you write to the various buffers (diffuse, normal, depth, etc.) in fragment shaders. By this time, the normal maps would have already been read.

  If it's done before using normal maps, how are normal maps going to be affected by the screenspace-ness of the normals,...

If you are referring to normal maps on models, normal maps can stay the same. You can compress normal maps as well if you want, but this becomes irrelevant to what you do for writing to the normal buffer.

  ...and if after, how can you justify using a Model-View matrix on all fragments rather on vertices? Isn't that a lot more calculations?

Your model's normals are computed per vertex and interpolated through rasterization to be per fragment. The normal maps are processed per fragment, but these are just texture lookups, and these can be applied to the camera-space normals produced from the previous pipeline steps. Therefore, a view matrix is no longer necessary.

  Finally, how are they unpacked? I realize you can get the blue component using pythagoras, but how are they returned to world space?

The idea behind 2-component normals versus 3-component normals is that the vector magnitude isn't often taken into account for normals. Also, normals facing away from the camera generally aren't useful. With two components, you can use model a hemisphere facing the camera. You unpack them the same way you pack them.

Think about normals as positions. When converting from world space (x, y, z) to screenspace (x, y, depth), but the depth does not effect where on the screen a mesh gets displayed. Convert the 3D vector to a vector in terms of screenspace (through view matrix multiplications).

Then you can discard the z-component (aligned with the camera) as long as you normals are unit vectors (because you can derive z from the other two vectors).


Determining the function of a radial gradient fill with midpoint Recently I have been trying to create a shader that imitates a shader within Affinity Photo. It is used in the radial gradient fill and essentially you set your endpoint colors and then set the midpoint to a percent.

What is interesting here is that with a midpoint set to 0 everything is not just one color. Same with 100. So it does not appear to be a trivial function.
I exported some images of this gradient at percent of 0%, 50% and 100% and graphed the red pixel values from the center pixel going to the end. Below are the results.

Unfortunately even after seeing it graphed I am unable to determine the f(x,a) where a goes from 0-100 that would recreate this graph in order to replicate the shader. Any tips that might get me closer to this formula?

It seems to be just a scalar Bezier function to me, where the second coefficient is determined by $a$
$$(1-x)^2 + a 2 (1-x) x,$$
here $a \in [0, 1]$ is a normalized percentage. This gets you pretty close to the function that is graphed, but the function will not be as flat for $a = 0$ and $a = 1$. I suspect the function is of a higher degree:
$$(1-x)^3 + a 3(1-x)^2 x + a 3(1-x) x^2$$
or even
$$(1-x)^4 + a 4(1-x)^3 x + a 6(1-x)^2 x^2 + a 4 (1-x) x^3$$
With increasing degree comes increased flatness (dragging out the colour of the midpoint). However, these higher order function are not exactly straight at $a = 0.5$. Using the coefficients $\frac{2}{3}$ $\frac{1}{3}$ in the cubic equation will get you a straight line for the cubic version
$$(1-x)^3 + \frac{2}{3} 3(1-x)^2 x + \frac{1}{3} 3(1-x) x^2.$$
For the cubic version you can create two additional functions
$$q(a) = 0.975 \cdot 2 (1-x) x + x^2$$
$$r(a) = 0.025 \cdot 2 (1-x) x + x^2$$
and then replace the second and fourth coefficents in the quartic function with these
$$(1-x)^4 + q(a) 4(1-x)^3 x + a 6(1-x)^2 x^2 + r(a) 4 (1-x) x^3$$
this will preserve flatness at extremes and (approximate) linearity at $a=0.5$. You can view it here: https://www.desmos.com/calculator/hwj7jyozv9


Why is thread safety such a huge deal for Graphics APIs? Both Vulkan and DirectX12 are claimed to be usable in a thread-safe manner. People seem to be excited about that.

Why is this considered such a huge feature? The "real" processing gets thrown over the memory bridge on a separate processing unit anyway.

Also if it is so big, why is it not until now that a thread safe Graphics API came out?

The main gain would be that it would be easier to divide CPU tasks into multiple threads, without having to solve all the difficult issues with accessing the graphics API. Normally you either would have to make the context current (which might have bad performance implications) or provide a queue and call the graphics api in a single thread. I don't think that any performance is gained this way, because the GPU indeed processes them sequentially anyway, but it makes the developer job a lot easier.

The reason that it was not done until now probably is because directx and opengl were created in a time where multithreading was not really apparent. Also the Khronos board is very conservative in changing the API. Their view on Vulkan is also that it will coexist next to OpenGL, because both serve different purposes. It probably was not until recently that paralism became so important, as consumers get access to more and more processors.

EDIT: I don't mean that no performance is gained from doing work in multiple CPUs, it is not useful to split your calls into multiple threads to create textures/shaders faster. Rather the performance is gained due to having more processors busy and keeping the gpu busy with things to perform.


Monte Carlo Integration Let $I$ = the value of integration and $p$ = probability distribution.

The estimator is denoted as $\left\langle I \right >$ and is
$$\left\langle I \right >=\frac{1}{N}\sum_{i=1}^{N}\frac{f(x_i)}{p(x_i)}$$

The expected value of this estimator is computed as follows:

$$E[\left\langle I \right >] = E[\frac{1}{N}\sum_{i=1}^{N}\frac{f(x_i)}{p(x_i)}]$$

$$\qquad \qquad  \space \space \space \space = \frac{1}{N}E[\sum_{i=1}^{N}\frac{f(x_i)}{p(x_i)}]\cdots(1)$$

$$ \qquad \qquad\qquad\quad= \frac{1}{N}N\int\frac{f(x)}{p(x)}p(x)dx\cdots(2)$$

$$ = \int f(x)dx \space \space$$
$$ = I\qquad\qquad \space$$

I wonder why the two equation, $(1)$ and $(2)$, are equal??

In Monte Carlo integration, the samples $x_1, x_2, \ldots x_N$ are independent, identically-distributed random variables. This implies they all have the same expectation value. The derived quantities $f(x_i)/p(x_i)$ also all have the same expectation value. So the expectation of a sum of $N$ of these is the same as $N$ times the expectation of any one of them:
$$E\left[ \sum_{i=1}^N \frac{f(x_i)}{p(x_i)} \right] = N \cdot E\left[\frac{f(x_1)}{p(x_1)}\right]$$
(I picked $x_1$ arbitrarily.)

Then, the expectation value of a continuous random variable is found by integrating over its probability measure:
$$E\left[\frac{f(x_1)}{p(x_1)}\right] = \int_{\text{domain of }p(x)} \frac{f(x)}{p(x)} \, p(x) \, dx$$


Why don't I see tile-based 3D graphics? As we know, tiles can make it quicker to update large portions of the display at once, as compared with a bitmap. To put, say a letter, on the screen, the Commodore 64 typically does two writes (the screencode and the attribute), but the ZX Spectrum typically does 9 (eight bytes which make up an 8x8 bitmap, plus 1 for the attribute).
Recently, a demo for the SEGA Genesis was released called Red Eyes. My understanding is that the 3D scenes were rendered on a PC, and some kind of program converted these animations to a tileset so that each frame can quickly be written into VRAM.
But, however hard I search I cannot find any contemporaneous games for these retro systems which use a tileset to render (an approximation of) three-dimensional graphics. So is there a technical reason for that?
I am asking because of a game I'm trying to write for the Commodore 64. My choice of platform has meant that the compute budget really is quite miserly, so of course I need to cut down on the amount of time spent pushing pixels to the framebuffer, and tile-based graphics are an obvious solution to that problem on this platform. Also I need to keep in mind the amount of time spent in 3D projection, and I believe this problem can also be solved with tile graphics, since for example a raycaster could cast one ray tile instead of one ray per pixel. But I'm unsure about that.
So the camera in my game is restricted to movement in one plane in the same way that the camera in DOOM is. It pans left and right only, and moves forward and sometimes backward. Plus I know that the walls in my game always are East-West or North-South. No diagonal walls. I think that this will mean that a manageably small number of pre-computed tiles will be enough to show the walls at various angles depending on how the camera is positioned.

The nature of this question is such that it could be answered in the following ways:

It wouldn't work because ...
You obviously weren't looking hard enough because here's an example of a game that does that. Here's a disassembly or source code so you can figure out how it worked
It might be possible, but you'd have to watch out for ...

This is not really an answer to the latter parts of your question but more to address

As we know, tiles can make it quicker to update large portions of the display at once, as compared with a bitmap. To put, say a letter, on the screen, the Commodore 64 typically does two writes (the screencode and the attribute)

What you are effectively describing is a compressed framebuffer where you are directly writing/storing compressed data and letting the display pipeline decompress on the fly.
I would say that such things "still exist" in today's games/hardware, but not perhaps in form you are expecting.

Compressed frame buffers do still exist. Mobile devices certainly do (for example Imagination/PowerVR have PVRIC, and I believe ARM devices have their own scheme)
These compression schemes are generally "transparent" to the programmer, but it does mean the GPU and display pipeline does less reading and writing of external memory.

A display decompression system like PCG  (Programmable Character Generator) is effectively a precursor to (and effectively a subset of) some texture compression schemes, e.g. such as S3TC/DXT1. In that sense, therefore it still exists, but users don't typically write directly to them, but certainly take advantage of the bandwidth savings.


Luminace, RGB, and SMPT ST 2084 EOTF I need a point clarified.  According to wikipedia, SMPT ST 2084 EOTF is this:
I've seen this equation implemented in game engines where for L they feed the channels RGB, each of which is 0 to 10,000 and normalize them.  Am confused because luminance from what I understand is supposed to be one quantity instead of 3.  I understood luminance to be kind'a like speed in physics, and the RGB is the "direction" vector. Is it really correct to plug the RGB linear channels in into L (the "linear optical luminance") in this equation, or am I misunderstanding something? The way I think of it, we need to compute the luminance from the RGB triplet, and then plug that value into L, then from V we compute colors.
Where is my thinking wrong?
Thanks.

I fully understand the confusion (I was also a bit confused when I saw it). So, I decided to look at the ACES implementation of the ST 2084 EOTF. https://github.com/ampas/aces-dev/blob/v1.0.3/transforms/ctl/lib/ACESlib.Utilities_Color.ctl#L402
From there it is very clear: You perform the transfer function on the R, G and B values separately and not by first calculating the luminance. The confusion most likely comes from the fact that we are talking about two different kinds of luminance.
We have relative luminance, which is the luminance we use when talking about colours and can be calculated with $Y=0.2126R+0.7152G+0.0722B$
We also have luminance for which the SI unit is cd/m2 and basically means how bright something is.
You, and I when I first read your post, were thinking about relative luminance, but the Wikipedia article was talking about just luminance. In this case, it talks about the luminance of red light, green light and blue light separately (since a camera captures it separately and a monitor produces it separately). I'm pretty sure the ST 2048 spec is more clear about this, but that's behind a paywall.


Role of gl.vertexAttrib I'm re-learning WebGL, and I stumbled upon gl.vertexAttribPointer and gl.vertexAttrib. To my knowledge, gl.vertexAttribPointer tells the GPU how the data in the currently binded buffer relates to the vertex attributes. But, I'm confused on what gl.vertexAttrib does. It seems like it also sends data to the GPU, but without the use of a buffer. Can anybody explain it's role to me?

gl.vertexAttribPointer is used when different vertices should have different values, and gl.vertexAttrib is used when all vertices should have the same values, and you don't want to use a special shader with a uniform.


Max number of elements in a vertex attribute I want to load a vertex buffer with vertices of struct Vertex:
struct Vertex {
   Vector3 position;
   Vector3 normal;
   Vector2 uv;
   int groups[10];
   float weights[10];
};

According to khronos manual, the number of elements in vertex attributes must be 1,2,3,4. If that is the case how do I load the vertex attributes consisting of more elements, in this case 10?
Is this not valid?
  glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)0);
  glVertexAttribPointer(1, 3, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)offsetof(Vertex, normal));
  glVertexAttribPointer(2, 2, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)offsetof(Vertex, uv));
  glVertexAttribIPointer(3, 10, GL_INT, sizeof(Vertex), (void*)offsetof(Vertex, groups));
  glVertexAttribPointer(4, 10, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)offsetof(Vertex, weights));

I need groups and weight vertex attributes for skeletal deformation.

The standard solution is to reduce the amount of per-vertex data by only specifying the 4 indices that have the highest weights (and rescaling the weights to add up to 1.0). That way, you can pass 4 weights as a vec4 and 4 indices as a uvec4. Also, you should pass the weights as normalized shorts (or bytes if you can accept the quality loss) and indices as bytes if at all possible, to further reduce the per-vertex data storage.
Most real-time rendering systems are happy with these limitations.
If that's not acceptable for your needs, then you're going to have to use multiple attributes to send the data. Each attribute can only have 4 components. And while attributes can be arrayed, arraying them like your C struct would waste a bunch of attribute locations, since each array element is considered a separate location.
So you need to send values in multiples of 4. Instead of sending 10 weights/indices, send 12, grouped into 4-element groupings. So the GLSL would look like this:
layout(location = X) uvec4 indices[3];    //Stores 12 indices, consumes 3 locations.
layout(location = X + 3) vec4 weights[3]; //Stores 12 weights, consumes 3 locations.

The C data structure ought to also store 12 elements for each array.
To specify them in the vertex format, you would do this (where X is the location given above):
glVertexAttribIPointer(3, 4, GL_INT, sizeof(Vertex), (void*)(offsetof(Vertex, groups) + 0));
glVertexAttribIPointer(4, 4, GL_INT, sizeof(Vertex), (void*)(offsetof(Vertex, groups) + 16));
glVertexAttribIPointer(5, 4, GL_INT, sizeof(Vertex), (void*)(offsetof(Vertex, groups) + 32));
glVertexAttribPointer(6, 4, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)(offsetof(Vertex, weights) + 0));
glVertexAttribPointer(7, 4, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)(offsetof(Vertex, weights) + 16));
glVertexAttribPointer(8, 4, GL_FLOAT, GL_FALSE, sizeof(Vertex), (void*)(offsetof(Vertex, weights) + 32));


Final transformation matrix to transform world coordinate into vrc For a 3D scene in the world coordinates, its View Reference Point $\mathrm{VRP}$ is at $(5,2,1)$, and a viewer is looking towards point $A=(1,1,1)$. Construct a transform matrix which will map  world  coordinate  points  to  a  right-handed  $(UVN)$  viewing  space,  so  that  VRP  is
  the  origin,  the  line  joining  $\mathrm{VRP}$ to  $A$  is  the  positive  $N$  axis,  and  the  view-up  Vector  is $(0,0,1)$.

I have calculated the translation matrix:

$$
T=
\begin{pmatrix}
1 & 0 & 0 & -5 \\
0 & 1 & 0 & 2 \\
0 & 0 & 1 & -1 \\
0 & 0 & 0 & 1 \\
\end{pmatrix}
$$

I have calculated the rotation matrix:

$$
R=
\begin{pmatrix}
-0.6 & -0.8 & 0 & 0 \\
0 & 0 & 1 & 0 \\
-0.8 & 0.6 & 0 & 0 \\
0 & 0 & 0 & 1 \\
\end{pmatrix}
$$

But what would the final transformation matrix $M$ be? My lecture slides tell me it would be rotation matrix multiplied by translation matrix, with the last column multiplied by $-1$ except for the $1$. This would equal:

$$
M = R \times T =
\begin{pmatrix}
-0.6 & -0.8 & 0 & -1.4 \\
0 & 0 & 1 & 1 \\
-0.8 & 0.6 & 0 & -5.2 \\
0 & 0 & 0 & 1 \\
\end{pmatrix}
$$

But this answer here: Building view transform matrices

just adds them together somehow. Which one is correct?

Thanks for notification me, In my previous answer, I just combine the translation matrix and the rotation matrix, actually, It's the result translation matrix(T) multiply rotation matrix(R).

The rotation is a 3x3 matrix, we can extend the matrix to a 4x4 matrix with adding a dimension, the 4x4 rotation matrix is:

And the translation matrix is:

So, now we can calculate the transform matrix by translation matrix multiply(T) rotation matrix(R):

Cause the matrix multiply formula is too big for the 4x4 matrix, we just look at the 1st row, In the transform matrix(M), the M11 element equals to T11*R11+T12*R21+T13*R31+T14*R41, cause T12, T13, R41 is 0, so, the M11 equals to R11 right? And in the same way, M14 equals to T11*R14+T12*R24+T13*R34+T14*R44, only R44 equals to 1, so, the M14 equals to T14. so, I just simply put them together in my last answer. For the reason why we put the translation matrix on the left, you can check on the book that I gave you in my previous answer on page 91(translating first and then rotating).


Use glTranslatef and shaders? In newer OpenGL it's encouraged to use shaders and pass the model-view-projection as parameters. But what if I drew a complex object, and wanted to translate/rotate it and draw many copies?

For example I wanted to do something like this :

glBindFramebuffer(GL_FRAMEBUFFER, fbo[0]);
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
{
    shader.bind();

    glm::mat4 projectionMatrix = glm::perspective(20.0f, (float)SCRWIDTH/(float)SCRHEIGHT, 0.0f, 100.0f);
    glm::mat4 viewMatrix = glm::lookAt(
        glm::vec3(0, 0, 2),
        glm::vec3(0, 0, 0),
        glm::vec3(0, 1, 0)
    );
    glm::mat4 modelMatrix = glm::toMat4(quaternion);
    glm::mat4 MVP = projectionMatrix * viewMatrix * modelMatrix;
    GLint loc_MVP = glGetUniformLocation(shader.id(), "MVP");
    glUniformMatrix4fv(loc_MVP, 1, GL_FALSE, &MVP[0][0]);

    glTranslatef(1,0,0);
    gluSphere(...);
    glTranslatef(2,0,0);
    gluSphere(...);

    shader.unbind();
}
glBindFramebuffer(GL_FRAMEBUFFER, 0);

But my experiment shows that the glTranslatef doesn't work here, all the spheres are rendered at (0,0,0). I don't want to call the shader 100 times, each time calculating a different MVP matrix. Is there any easy way around this?

The vertex shader looks like this :

#version 330 core

uniform mat4 MVP;
in vec3 in_Position;

void main(void) {
    gl_Position = MVP * vec4(in_Position, 1.0);
}

Update the uniform and draw again.

auto tMVP = glm::translate(MVP, glm::vec3(1,0,0));
glUniformMatrix4fv(loc_MVP, 1, GL_FALSE, &tMVP[0][0]);
gluSphere(...);

tMVP = glm::translate(MVP, glm::vec3(2,0,0));
glUniformMatrix4fv(loc_MVP, 1, GL_FALSE, &MVP[0][0]);
gluSphere(...);

Using glTranslate would have done the exact same thing behind the scenes.

You can instead use instancing instead where you upload all the transforms into a buffer and then tell the gpu to use that.

However the more portable way involves allocating a vertex attribute for the data. This involves using glVertexAttribDivisor.

So a full mat4 would need 4 vertex attributes. You can decrease that to 2 by separating out the translation as a vec3 and the rotation as a quaternion and pass the view-perspective as a uniform and combining it all in the vertex shader.


Calculate an equally bright grey to a linear RGB colour I'm trying to get a grey linear-RGB-triple that is equally bright as another (colorful) RGB-triple.
I have to admit, that there is great confusion for me with all the color stuff, even though I read a lot of wikipedia articles, but I don't really get the big picture. I'm kind of lost and need help.
Wikipedia seems to mention a formula to receive the perceived brightness of a linear RGB color.
So I can measure the brightness of my color and do something like this I suppose:
public Vector3d get_equally_bright_grey(Vector3d color) {
    for (double c = 0.0; c <= 1.0; c += 0.001) {
        Vector3d grey = new Vector3d(c, c, c);
        if (brightness(color) == brightness(grey)){
            return grey;
        }
    }
}

But there has to be something other :)

Some context:
My input colors were spectral distributions that I converted to XYZ values (after Bruce Lindbloom).
Then I have converted those XYZ values to linear RGB (again with Bruce). And here comes my question.
I know that the Y component of my XYZ triples is also something like the luminance, but I don't know how I generate a grey color XYZ color from this either..

The easiest way to get the perceived brightness of a color is to calculate the Luma. Finding the grey color with the same luma is easy - just set all of the RGB components to the desired luma value. That works because the coefficients for calculating the luma sum up to 1.

public Vector3d get_equally_bright_grey(Vector3d color) {
    double luma = color.x * 0.299 + color.y * 0.587 + color.z * 0.114;
    return new Vector3d(luma, luma, luma);
}


Need help reasoning about video oscillation >60hz I want to make a basic video oscillator for the web. What I want to do is basically illustrated in a tutorial for Lumen: essentially, I want to define an oscillator to turn on and off a color signal at a given frequency. This is simple to do for a frequency below 60hz, but anything higher does not seem to get the effect that the program is showing.

It seems likely to me that the tutorial is far more simplified than what is going on behind the scenes, and since I don't have background in graphics programming I don't really have the tools to even know what I need to know. I'd like to understand what is going on and if it is possible to produce such things for the web

Yeah, that makes sense. Most flat panel monitors on the market have a 60Hz refresh rate! So you are not going to be able to flicker faster than 60Hz due to technical limitation.

Were you to do this with a electron sweeping oscilloscope, or a LED lamp connected to a PWM source fast enough then no problem (you can find this in arduino samples). It would work.

You can also emulate the effect by rendering multiple frames and then blending them. But you should take careto do correct kind of blending as the monitor output is not nesseserily linear!


Closest sphere on segment I am trying to get a segment closest point on a surface and display a circle (or sphere in this case) at that position.

I actually get the correct position but I can't get a uniform sphere based on the computed data.

Here's the associated code I use to find the intersection point and draw the sphere.

float3 a = from;
float3 b = to;
float3 c = worldPosition;

float3  ab = b - a;
float t = dot(c - a, ab) / dot(ab, ab);
float3 point = a + saturate(t) * ab;

return length(point - worldPosition) - radius;

Your actual result is correct in terms of what you can achieve in a single-pass with a fragment shader. It calculates the distance of the fragment's world position to the line segment. That distance is different for each fragment so the stretched black ellipsoid is the correct output.

A fragment shader has only local information about the current fragment being processed. You can't do more with that. Your expected result requires some global knowledge about the scene, since you are searching for the minimum distance across the whole surface.

Without any thoughts on optimization, the naive solution path should involve contextual computation of local minima of the fragment-to-linesegment distance. In order to get such context, you need to compute the distance field first and then access it to find the local minima in a separate pass.

Compute the raw distance field in the first pass (same as your example but no radius subtraction at the end.
Mark the pixels with local minima in the second pass (e.g. by setting the alpha channel to 1). This will be screen-space pass. The best is to have a rgba float texture at output with rgb being fragment's world position and a being 1 for local minima and 0 else.
Paint the black circles/spheres in a third pass (also screen-space).

Having the information about the local minimum of your distance function enables you to output the right shape for around the minima in the last pass. In pseudocode:

vec4 worldPos = tex2D(distance_texture, frag.x, frag.y);
if (worldPos.a > 0.5) //is minimum
    return vec3(0,0,0);
else
{
    //Sample the screen-space neighborhood in larger and larger circles
    // until a fragment with distance.a == 1 is found
    // or until all fragments are more than radius away (in world coords).

    //Minimum world space distance of any sampled fragment.
    float minDist = 0.0;
    int iter = 1;
    //Search for a local minimum until all fragments are more than radius away,
    // since then even if a local minimum gets found it will no longer produce
    // the black shading.
    while (minDist < radius && minDist >= 0.0 && iter < Math.Max(screenWidth, screenHeight))
        minDist = sampleNeighborhood(iter++, worldPos);

    if (minDist < 0.0) //found a local minimum
        return vec3(0,0,0);
    else
        return vec3(1,1,1); //or any other computed shading

    //I am aware that the function call above checks central fragments several times.
    //That should be of course optimized in production code.
}

float sampleNeighborhood(int neigh, vec4 worldPos)
{
    float minDist = float.MaxValue;
    for(int x = Math.max(0, frag.x - neigh); x <= Math.Min(screenWidth, frag.x + neigh; ++x)
        for(int y = Math.max(0, frag.y - neigh); x <= Math.Min(screenHeight, frag.y + neigh; ++y)
        {
            float p = tex2D(distance_texture, x, y);
            float d = distance(p.xyz, worldPos.xyz);
            if (p.a > 0.5 && d <= radius)
                //Return negative distance to indicate a local minimum was found.
                return -1.0;
            else
                minDist = Math.min(minDist, d);
        }
    return minDist;
}

Finding the local minima in the second pass is much easier, since you only need to sample the local 3x3 neighborhood.

I hope that helps you in reaching the desired rendering!


What's the point of "work groups" for OpenGL compute shaders? glDispatchCompute has the number of work groups as arguments.

What is the point of having work groups? How are they useful, compared to just having NxM independent pixel calculations with a known (x,y) input parameter in the shader?

Work groups share resources. The most notable resources they share are barriers and LDS (Local Data Storage aka shared memory in GL lingo, aka Thread Group Shared Memory).

See Efficient Compute Shader Programming for an example where LDS/TGSM is used to accelerate a simple gaussian blur.

It is an interesting thought exercise of how a simple algorithm (weight average N values and output the result) can be rewritten to better leverage the hardware. Basically with a kernel radius of 5, Pixel A will load pixels [A; E] to average them, pixel B loads pixels [A; F] to average, pixel C loads pixels [A; G], and so on until we hit pixel F which will load pixels [B; J] to average them. So the paper asks the question: why do we load pixels A through F from main RAM so many times? (note: GPUs DO have caches, but if multiple threads are requesting all the same regions is likely many of these loads will miss the cache or have bank conflicts) and instead tries to load A through F ONCE (each thread loads only one pixel) and store it into TGSM memory which is much faster (and can also be accessed directly by the HW). It's basically very similar to manual cache management.

Also if the workgroup happens to be <= than the GPU's native workgroup size, barriers are much cheaper.

Note not all GPUs are created equal. For example current Mali's GPU do not have LDS, and shared memory is "emulated" via RAM fetches, thus trying to use LDS like a cache is only going to hurt performance.


Reduce kd-tree's nodes' bounding box sizes to their shapes' extents? I've implemented a ray tracer that uses kd-trees for acceleration. To help debug kd-tree construction, I also created a crude OpenGL view of the same scene that shows the axis-aligned bounding boxes (AABBs) for each node in the tree (along with the shapes in the scene), and allows the user to highlight a specific node in the tree.

Here is an example of a scene with a bunch of spheres, the tree's nodes' AABBs, and one node selected:

You can clearly see that the AABB for the highlighted node contains a lot of empty space. In general, this is because, during creation, at node split time, the parent's AABB is split into two by an axis-aligned plane at whatever location is found to be optimal, and each child gets one of the two resulting AABBs.

I added a step to the splitting procedure that, after the steps above, reduces the size of each child's AABB such that its min/max extents in all axes are reduced to the min/max AABB extents of its shapes. Note that the node's AABB is never expanded, so it's still possible to have shapes partially outside the node's AABB.

Here is the same node selected with reduction turned on:

I see a slight improvement in performance, since the probability of an arbitrary ray hitting a given node's AABB is now less, since the AABB is smaller.

My question is, is there any disadvantage to doing this?

No disadvantage that I can see but what you have is not a kd-tree if you have axis-aligned bounding boxes in every node.

A kd-tree only has a splitting plane in every node, so there is no AABB to shrink. The way to deal with empty space in them is to split the node further into an empty node and a smaller node with the same objects as its parent, when justified by whatever heuristic is used. It is just one more possible split to consider when picking how to split a node.


Techniques for rendering high polycount models I would like to know what common techniques are used for rendering large models, when using rasterisation within a graphics API, for example OpenGL or Vulkan.

For example if I had a model with >10 million triangles, and it would be too slow to render the whole model, what optimisation steps or techniques could I use?

I am currently aware of:

Frustum culling
Occlusion culling

I would not know how to apply frustum culling to a single model. I know it can be used for multiple models:

for( int i=0; i < numObjects; i++ )
{
    if( insideFrustrum( objects[i] )
    {
        addModelToBeRendered( objects[i] );
    }
}

Can frustum culling be applied to a single model/mesh?
What other techniques besides the two stated can be used when rendering large data-sets?

The straightforward solution is to simple not render the high poly model at all. Have a lower detail model that you can switch to once the model is too far away for it to make a difference. There is no point in rendering 20 triangles that all end up in the same pixel.

Next option is to partition the model and then cull the individual parts. You can also make each (set of) patch have different Levels of detail.

This partition can take the form of patches that are mostly flat. That way you can use backface culling on the whole group by taking the dot product of the average normal and comparing it to the look vector, if it is too large only the backsides will be showing and there is no point in rendering that patch.


Should ideal specular multiply light colour with material colour? Ideal specular reflection is like a perfect mirror. I'm looking at the code to SmallPt and see that one of the spheres has an ideal specular material:

Sphere spheres[] = {//Scene: radius, position, emission, color, material
   / ...
   Sphere(16.5,Vec(27,16.5,47),       Vec(),Vec(1,1,1)*.999, SPEC),//Mirr
   / ...
 };

In the radiance calculation, this happens:

  } else if (obj.refl == SPEC)            // Ideal SPECULAR reflection
     return obj.e + f.mult(radiance(Ray(x,r.d-n*2*n.dot(r.d)),depth,Xi));

where f is the object colour of Vec(.999,.999,.999).

I was surprised to see colour multiplication here. Doesn't an ideal mirror have no colour? I guess as f is Vec(.999,.999,.999), effectively it's passing through the colour almost unchanged? Any thoughts on why .999 was used and not 1? I'm guessing this is something to do modelling a miniscule energy loss?

What "ideal" means in this context is that there is no divergence in the direction of light reflection vectors (i.e. no roughness) but that they are all considered to be perfect reflections from an optical flat surface. However, even for optical flat surfaces Fresnel equation is still applied in BRDF evaluation that changes specular reflection and is potentially wavelength dependent, which is a common characteristic with metals.

However, in smallPt there's no Fresnel approximation (e.g. Schlick's approximation) but the surface reflectance is simply multiplied with constant term which is wrong. Also 0.999 specular albedo is very high for any real material. Below is a table of specular reflectange of various metals & dielectrics at normal incidence for reference:


How double-buffers works in opengl? As I understand, the back-buffer is used for rendering the image while the front-buffer is drawn on the screen. So if you have only one image to be drawn on the screen, then you only need to swap the buffers one time because in the second swap the image is already drawn and there is no point to draw the same image again. However, when I tried to swap buffers no more than 2 times the graphics slow down a lot and move the window from one position to another takes 10-20 seconds. My question is... Why?
How double-buffers works then?

Yes, the back buffer is for the GPU to write the frame that's in-progress, while the display controller sends the front buffer to the attached display. Swapping buffers doesn't really copy anything these days. The display controller has a register which tells it the address of the frame buffer to display. Swapping buffers simply puts the address of the old back buffer in this register, making it the front buffer. You should only swap buffers when the frame is complete (i.e. you've finished drawing all the objects) and you want it to be displayed. This frame will continue to be displayed until you swap buffers again.

In some configurations (e.g. in EGL it depends on what swap interval you set) swapping buffers will make the CPU wait (block) until the GPU has finished rendering that frame. In others, the CPU can continue to queue up draw calls for further frames.


Why is the valence of regular vertices 6? So I recently learnt that supposedly for any mesh, and pretty much any scheme, the valence of regular vertices must be 6. It seems to be related to the Euler-Poincare formula but I have not been able to find the justification.

If require that all faces have the same number of sides $s$ and require that all vertices also have a certain valency $t$. We see that the following relation between edges, and faces hold for a regular mesh:
$$s\cdot f = 2e,$$
$$t\cdot v = 2e.$$ Substitution in the Euler-Poincare formula yields:
$$\left(\frac{1}{s} + \frac{1}{t} - \frac{1}{2}\right)e = 1 - g$$
If we then take for instance a regular plane which can be said to have the topology of a torus with genus $g = 1$. We then set the valency of faces $s = 3$ then
$$\left(\frac{1}{3} + \frac{1}{t} - \frac{1}{2}\right)e = 0,$$
$$\left(-\frac{1}{6} + \frac{1}{t}\right)e = 0.$$
The solution for $t$ is $6$, which says the valency of a vertex in a regular triangulation is 6.


Fastest Simulation Of Mass Spring Systems I'd like to simulate a 4-dimensional cloth in the web browser, since browsers don't offer great ressources for numerical computation, I'd like to know which algorithm uses the least amount of operations per frame / vertex.
Here is some naive first draft using explicit Euler.  I found this paper discussing a fast method for finding approximate solutions of the implicit Euler method.  What I gathered from the discussion is that implicit Euler is numerically more stable in certain scenarios, but it looks like it uses more operations than explicit Euler since it is built around iterations.  Is that correct?
Also, are there any libraries using WebGL to accelerate numerical computations which might be useful for this project?  I thought about looking into TensorFlow.js.

Time integration with implicit Euler is unconditionally stable. This means you can choose arbitrary large time steps without worrying that your solution "explodes". In contrast to explicit Euler, it requires you to solve a linear equation system at least once, which is generally much slower than simple matrix-vector multiplication. If the problem is non-linear, you also need to iterate until your error is minimized. This obviously takes even longer.
However, stability issues can be a pain to deal with and all explicit methods have limitations regarding their stability. Solving stability problems might force you to reduce your time step size drastically and to calculate so many intermediate steps that the implicit version gets more effective. An additional factor is the size of the system you want to simulate. If I remember correctly, the finer your mesh (smaller cells), the smaller are the timesteps you need to maintain stability.

I'd like to know which algorithm uses the least amount of operations per frame / vertex.

I think there is no general answer to the question because it depends on many factors like the mesh size, target FPS and the maximum local velocity that might occur. You need to evaluate all relevant factors and pick a method based on your exact problem.
In case you want raw speed and do not encounter any stability problems, the explicit Euler method should be one of the fastest methods but it usually blows up rather quickly.
Additional info
A time-integration method that is quite popular in real-time engines is Runge-Kutta 4. It is also an explicit method and doesn't require you to solve a linear system. It has a good balance of stability and speed, so you might have a look at it. I have never simulated cloth myself, nor have I programmed an RK4, so I can't tell if it is a good choice here.