How can I send custom bitmap to frame buffer? I was trying to make a CPU-based ray tracer but I know after all the calculation I will end up with an array of pixels. I don't know how to paint it on the screen. What are the various ways to do that? I am using C++ and I am working on Windows 10. I know OpenGL(useless since I am not gonna use my GPU), Allegro 5 game library and I am also familiar with win32 C++ API.

This answer uses GDI and a little bit of MFC. The MFC bits aren't necessary and just there for my convenience. You can hit the Windows API directly if you need to.

In your window class have some data members for the bitmap. I currently use MFC's CBitmap for convenience:

CBitmap             bitmap_;
unsigned char*      bitmapBits_;

bitmapBits_ is a pointer to the bitmap data that you can write directly into.

Before rendering, you'll need to create the bitmap using CreateDIBSection() and get the pointer to the bits of the bitmap:

BITMAPINFO bmi;
memset(&bmi.bmiHeader,0,sizeof(bmi.bmiHeader));
bmi.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
bmi.bmiHeader.biWidth = widthOfTheImage;
bmi.bmiHeader.biHeight = heightOfTheImage;
bmi.bmiHeader.biPlanes = 1;
bmi.bmiHeader.biBitCount = 24;
bmi.bmiHeader.biCompression = BI_RGB;

void* bitmapBits;
bitmap_.Attach(CreateDIBSection(0,&bmi,DIB_RGB_COLORS,&bitmapBits,0,0));
if(bitmap_.m_hObject == NULL)
    AfxMessageBox("CreateDIBSection() FAILED!\n");
bitmapBits_ = reinterpret_cast<unsigned char*>(bitmapBits);

When writing to the bitmap bits, you first need to determine the row size (see here).

// Compute the row size of a DIB.
// (See https://en.wikipedia.org/wiki/BMP_file_format#Pixel_storage and ComputePitch() from atlimage.h)
const unsigned int rowSize = ((24 * imageWidth + 31) / 32) * 4;

Then you can write the colour information into the bitmap's data. Note this is a bottom-up DIB; memory earlier in the buffer represents scanlines lower in the image. Another way of putting it is that the the first element of the bitdata relates to the bottom-left. Colour components are in BGR order.

unsigned char* dibPtr = &bitmapBits_[pixelY * rowSize + pixelX * 3];
dibPtr[0] = ???; // blue between 0 and 255
dibPtr[1] = ???; // green between 0 and 255
dibPtr[2] = ???; // red between 0 and 255

Sorry if the previous part is already known to you, as you asked simply how to get it painted to the screen. Here's my simplified paint routine from my MFC application:

void RendererWnd::OnPaint()
{
    CPaintDC dc(this);

    CDC dcMemory;
    dcMemory.CreateCompatibleDC(&dc);
    CBitmap* oldBmp = dcMemory.SelectObject(&bitmap_);
    dc.BitBlt(0,0,imageWidth,imageHeight,&dcMemory,0,0,SRCCOPY);
    dcMemory.SelectObject(oldBmp);
}

There are going to be many other ways of doing this. If you're doing a long render and want to update the window periodically then you'll probably want to have a timer in your window. When this timer fires you want to request a repaint of your window using InvalidateRect(). You'll need to synchronise access to the bitmap data between your rendering thread(s) and the thread that's doing the painting. This will ensure the painter can access the bitmap when it's not being written to. I use a CRITICAL_SECTION for this.


What happens when GL_Depth is disabled In my simulation I draw a bunch of rectangles with GL_TRIANGLE_STRIP inside of one draw call.

What will happen if I turn off GL_DEPTH_SORT? If all of the rectangles were stacked on top of themselves in a 2D screenspace sense would they always be in the same order?

I'm assuming it's just like when you do multiple draw calls (the first one is in back, the last one is in front) how it essentially just draws over what was previously drawn.

I am using OpenglES 2.0.

Also what happens with blend modes? Let's say I am doing additive blending, and then multiply the colors by 0.5 making them transparent. Would additive blending work?

If depth testing is disabled, the triangles get drawn in the order they're submitted, i.e. the order they appear in the index buffer or vertex buffer. Later ones will overwrite earlier ones, or blend over them if blending is enabled. This ordering is guaranteed by all GPUs and APIs as far as I know.


Why do animated CG characters always feel fake? Why do animated CG characters always feel fake?

Usually if a CG character is an animal (or humanoid creature), they tend too look kinda off. Their movement tends to look oddly smooth or lightweight, even if aided with motion capture. Compare to real human or animal movement which is jagged, and has slight irregularity or weight. It doesn't matter whether the texture looks photorealistic, the movement of CG characters always feels off.

I'm guessing it's because the animation curves for the final images are smoothed out or simplified, like smoothing a bezier curve or something. Is that the case? Is absolute, true-to-life movement possible for CG characters?

Because animators haven't fully bridged the uncanny valley.

There are a ton of little details you notice subconsciously that hasn't been fully mapped out.

Things like how muscles and tendons move under the surface, how clothing and hair behaves as you move around. Even how you adjust your stance as you move your arms around, prepare to move, etc.

Even with mocap it is difficult to capture and recreate all that. It is also not trivial to capture the movement of the fingers.


What is the optimal radius of gaussian distribution for determining pixel colour? Using a gaussian distribution of points on an image plane to calculate a pixel value, what radius/standard deviation will give the most information in the final image? Too large a radius gives a blurred image, and too small a radius neglects information that is smaller than a pixel so that it does not contribute to the final image. Where is the optimal compromise? Is there a single answer to this question or are there circumstances under which it can vary?

I'm thinking of this in relation to raytracing but I imagine it will apply equally to things like downsizing an image. Where the answers would differ, I am interested in what applies when sampling a continuous image plane, so that the positions of pixels in a larger image cannot be used to determine an optimal radius.

I'm not sure that there's a truly optimal radius—it's going to be a subjective matter based on what the image looks like.  As you say, too large a radius results in blurring and too small a radius results in aliasing.

I like to set sigma = 0.5 px, so that the overall radius is about 1.5 px (since the Gaussian has the majority of its weight within ±3 sigma of its mean).  In my experience that gives a good trade-off between blurring and aliasing, but that's just my taste, not based on any objective considerations.

By the way, as part of a blog post on antialiasing I wrote last year (which was based on an answer I posted on the previous incarnation of this site!), I tested a variety of antialiasing kernels against a synthetic test image and came out with 0.5 px Gaussian as my subjective favorite.


How does voxel cone tracing work? Assume that we have voxelized a 3D scene into a regular 3D grid of cubes, storing the average (diffuse) radiance and some flag indicating whether or not a voxel is empty. Next, the finer levels of the 3D texture (voxels) are downsampled to get coarser levels ("pre-integrated") which will be stored as MIP levels for that texture. (I know that some sparser structures can be used instead, but a regular grid is conceptually the most easiest to master first.)

Now, given that we have our surface position (and thus also the voxel we are in), how does voxel cone tracing work and how is it applied?

Illumination components

If our scenes only contain point lights (e.g., omni lights, spotlights, etc.) and emissive surfaces, the illumination contributions at a surface position, $x$, are computed as follows:

The self emission associated with the emissive surface (i.e. 0 bounces/surface interactions) is computed as usual without using the scene's voxelization (as is the case for adding this illumination contribution to the scene's voxelization);
The direct illumination associated with the point lights (i.e. 1 bounce/surface interaction) is computed as usual without using the scene's voxelization (as is the case for adding this illumination contribution to the scene's voxelization);
The direct illumination associated with the emissive surfaces (i.e. 1 bounce/surface interaction) is obtained from the scene's voxelization using voxel cone tracing;
The indirect illumination associated with the point lights (i.e. 2 bounces/surface interactions) is obtained from the scene's voxelization using voxel cone tracing.

By computing the diffuse illumination for all the voxels from the scene's voxelization using voxel cone tracing, the diffuse illumination from additional bounces/surface interactions can be (optionally) accumulated inside the voxels. This requires each voxel to store (an approximation) to the normal distribution of the scene's surfaces overlapping those voxels as well.

Illumination from the scene's voxelization (3)-(4)

The outgoing radiance obtained from the scene's voxelization ($L_v$):

$$L_o\!\left(x, \hat\omega_o\right) = \int_\Omega f_{r}\!\left(x, \hat\omega_o, \hat\omega_i\right) L_v\!\left(x, \hat\omega_i\right) \left(\hat{n} \cdot \hat\omega_i\right) \mathrm{d}\hat\omega_i.$$

For a diffuse BRDF $f_{r}\!\left(x, \hat\omega_o, \hat\omega_i\right) = \frac{k_d}{\pi}$:

$$L_o\!\left(x, \hat\omega_o\right) = \frac{k_d}{\pi} \int_\Omega L_v\!\left(x, \hat\omega_i\right) \left(\hat{n} \cdot \hat\omega_i\right) \mathrm{d}\hat\omega_i.$$

For a partitioning of $\Omega$ in $N$ disjunct subdomains, $\Omega_j$, (e.g., $\approx$ cones) (i.e. $\Omega_1 \cup~...~\cup \Omega_N = \Omega$ and $\Omega_i \cap \Omega_j = \emptyset$ for each $i \ne j$):

$$L_o\!\left(x, \hat\omega_o\right) = \frac{k_d}{\pi} \sum_{j = 1}^{N} \int_{\Omega_{j}}  L_v\!\left(x, \hat\omega_{j,i}\right) \left(\hat{n} \cdot \hat\omega_{j,i}\right) \mathrm{d}\hat\omega_{j,i}.$$

Relying on a single cone with a direction, $\hat\omega_{j}$, and an aperture, $\alpha_{j}$, instead of individual rays with a direction, $\hat\omega_{j,i}$, for each subdomain, $\Omega_j$:

$$L_o\!\left(x, \hat\omega_o\right) \approx \frac{k_d}{\pi} \sum_{j = 1}^{N} L_v\!\left(x, \hat\omega_{j}, \alpha_{j}\right) \int_{\Omega_{j}} \left(\hat{n} \cdot \hat\omega_{j,i}\right) \mathrm{d}\hat\omega_{j,i}$$

$$\hat{W}_j = \frac{1}{\pi} \int_{\Omega_{j}} \left(\hat{n} \cdot \hat\omega_{j,i}\right) \mathrm{d}\hat\omega_{j,i}$$

$$L_o\!\left(x, \hat\omega_o\right) \approx k_d \sum_{j = 1}^{N} \hat{W}_j L_v\!\left(x, \hat\omega_{j}, \alpha_{j}\right).$$

We can use for example the following six cones, each with an aperture of $\frac{\pi}{6}$.

The normalized weight of the blue cone about the surface normal is equal to:

$$\hat{W}_{\mathrm{blue}} = \frac{1}{\pi} \int_{0}^{2\pi} \int_{0}^{\frac{\pi}{6}} \cos\!\theta \sin\!\theta \, \mathrm{d}\theta \, \mathrm{d}\phi = \frac{1}{4}.$$

The normalized weight of the other cones is approximately equal to:

$$\hat{W}_{\mathrm{purple|red|green|orange|brown}} \approx \frac{1-\hat{W}_{\mathrm{blue}}}{5} = \frac{3}{20}.$$

For a specular BRDF, one typically uses a single cone with a direction, $2 \left(\hat{n} \cdot \hat\omega_o\right) \hat{n}-\hat\omega_o$ (i.e. reflected direction of $\hat\omega_o$ about $\hat{n}$), and an aperture based on the roughness of the surface material.

Voxel Cone Tracing

$L_v\!\left(x, \hat\omega_{j}, \alpha_{j}\right)$ is computed using voxel cone tracing, which can be implemented by marching the mip-mapped 3D voxel texture in UVW texture space.

Our accumulated radiance (red, green, blue channels) and opacity (alpha channel) are initialized to zero.

Lv ← [0, 0, 0, 0]

Our cone marching distance is initialized to an offset to avoid sampling the self emission associated with the emissive surfaces and the direct illumination associated with the point lights twice. We need to basically skip the voxel containing the surface position for which the outgoing radiance needs to be estimated.

distance ← voxel_offset

Marching continues until we reach an accumulated opacity of 1 or more:

while Lv.alpha < 1:
    compute diameter (i.e. cone voxel footprint)
    compute mip_level
    compute position at distance
    if mip_level >= max_mip_level or position ∉ [0,1]^3
        break
    sample Lv_step(position, mip_level)
    Lv ← Lv + (1-Lv.alpha) * Lv_step // blend equation
    distance ← distance + cone_step  // marching -> diameter and mip_level will increase
return Lv


Image rescaling algorithm Suppose I have to use bilinear interpolation to rescale image. I more or less understand how enlargement works in case of integer scale factor.

But what to do with non-integer scale and especially when you need to downsample an image?

Explanation
With a non-linear scale, you apply different weights for each pixel (or whatever unit you are using). You can use Euclidean distance towards the closest pixels in both directions to determine the weights.
Example
Normalization
For example, in the image below, the red image is the downsampled image (3x3) and the black image is the original image (4x4). The dots represent the sample points (center of the pixels).
You can align the two images by treating each pixel coordinate as a set of two values (x and y) between 0 and 1 (inclusive). Pixels should not be treated as square, so you should treat each pixel as a point rather than a square (when aligning the two images).

In the above image, the four corners would all carry the weight of the original image's four corners, for example. The points in the middle would carry different weights depending on the difference between the four neighboring points.
With numbers:
This is a hypothetical area to sample in larger images (not related to the image above). The distances are between original pixels are normalized from 0 to 1 to simplify the math.
The black dots represent the sample points (pixels) of the original image. The larger red dots represent the sample points of the downsampled image. The red dot in the top left is closer to the black dot in the top left than the other three surrounding dots, so that pixel will have a heavier weight for determining the color of the downsampled pixel.

Horizontal distance from:

Right 2 original (green) pixels = 0.1 pixels
Left 2 original (green) pixels = 0.9 pixels

Vertical distance from:

Top 2 original (green) pixels = 0.1 pixels
Bottom 2 original (green) pixels = 0.9 pixels

Weight for final pixel:
$$weight(0, 0) = (1.0 - 0.1)(1.0 - 0.1) = 0.81$$
$$weight(0, 1) = (1.0 - 0.1)(1.0 - 0.9) = 0.09$$
$$weight(1, 0) = (1.0 - 0.9)(1.0 - 0.1) = 0.09$$
$$weight(1, 1) = (1.0 - 0.9)(1.0 - 0.9) = 0.01$$
Subtract from 1 both the horizontal and vertical distance (because closer pixels should carry more weight). The scale factor in this example is 0.75 in each direction.
Scaling Up vs. Scaling Down
Scaling up in the same  process as scaling down. By normalizing both the original image and the new image to between (0, 0) and (1, 1), you can do either with the same process. As an exercise, in the first figure, if the red points were from the original image and the black points were from the enlarged image, you should be able to see that the process is the same.


Cloud based VR would be the future? According to the following assumptions, I think Cloud based VR would be the future:

1) Real world scene rendering needs ray tracing or other complex computing graphics technologies. It needs a lot of computing power.

2) Single GPU can't afford enough GFLOPS for that. And the powerful GPU is costly and hot. Since the moore's law is ending soon, the process of GPU will also end evolution, that means GPU can't get much faster than needed.

3) Mobility is the king. But mobile GPU speed will be limited by the power and process. It won't get much faster too.

4) Cloud gaming would be promise for that. The network bandwidth and latency would be the biggest issues. Since Google Fiber has been deployed, I don't think network is the issue in the future.

5) Rendering a real world needs unlimited computing power, but human eye resolution is limited. Limited resolution means limited network bandwidth consumption. For example, 1Gbps is enough to transmite 8K/16K H265 streaming video in stereo format.

So, I believe Cloud based VR (Rendering in Cloud and stream to the client) would be the future. Am I correct?

added more detail @20160406

I did some research on it. The motion-to-photon has to be less than 20ms. Maybe only 5ms is left for round trip network. So that the Cloud DC has to be very close to the client. In case optical fiber access, only two hops ( switch and BRAS ) to local router and then to local Cloud DC. (Transmission speed in optical is 200K KM/s, so 100KM radius would take only 0.5ms. That means Cloud DC would cover 30K square KM area.)If no network congestion with good QoS policy, the network latency would be very low. At the mean time, use distributed GPU clusters to render the VR content and then stream it to the client in parallel to reduce the time further. Let's count the time consumptions during each stages. 1.5ms for head tracking and local cpu processing. 1.5ms for network transmission to Cloud. 1.5 ms for distributed GPU cluster rendering and encoding. 5ms for network transmission to client. 1ms for decoding with special decoder since current video decoder designed for video playing not for VR. 5ms for transmission to monitor (equal 200Hz monitor, or very high bandwidth transmission as display port 1.4). The total time is 1.5+1.5+1.5+5+1+5 = 15.5ms. Of course, if using Foveated Rendering technology, addition 3ms for eye tracking delay, but the network bandwidth and latency will be reduced.

As other people have mentioned, due to network latency issues, I think that full rendering on a cloud server and streaming video to a client device is unlikely to be workable. Even if the latency can be kept low enough in a best-case scenario, it would only work for a very limited number of users with very high-quality internet connections. (Don't forget that e.g. in the USA, there are still tens of millions of people on dialup or DSL, with no access to cable internet, let alone fiber. It will be decades still before fiber is widespread.) Also, note that many cloud gaming services do exist, but that according to players, input latency is noticeably worse on these services than playing locally on a PC.

However, all that being said, rendering entirely on a cloud server is not the only way to approach the problem. The most latency-sensitive aspect of VR is head tracking. Oculus's "timewarp" technology shows that you can quickly and cheaply update a previously rendered image to respond to head rotation, as a 2D image operation: if the user turns their head to the right, you shift the image to the left, and so on. With a depth buffer, you can do positional timewarp as well, although this creates various artifacts with parallax because it's based on a single-layered 2D image.

Timewarp is certainly cheap enough to run on a mobile device. So, one approach is to render frames in the cloud, stream the video to the client, then timewarp the video on the client device to obtain very low-latency head tracking. This wouldn't help the latency of other inputs such as keyboard/mouse/controller inputs, but those don't induce nausea when they're delayed, the way delayed head-tracking does.

There are also other possibilities along the lines of splitting rendering between the cloud and the client. For example, object-space lighting and shading could be done on the cloud and streamed to the client as textures; then the client only needs to render simple textured geometry. This would work better than positional timewarp for getting correct parallax when you move your head around, though you'd still have some artifacts with specular shading and reflections. There are a lot of possibilities for offloading rendering to the cloud in VR-friendly ways.


Triangle - Why is it the basic building block for complex shapes I was recently learning about OpenGL and computer graphics development. I have a question regarding the usage of triangle as the basic building block, or basic shape to develop complex shapes. Is there a particular reason? Or just something that "stuck"?

Triangles are always flat, unlike a quad which can be made in a way that is bent / not all vertices on the same plane.

If you were to interpolate say vertex normals across each scanline, on a 4-edge bent quad it will render with horizontal (scanline) artefacts. If you made that same bent quad out of triangles, it will render correctly as each triangle has a different normal slope.

That's one reason why triangles are preferable for scanline rasterising


Ghosting in volumetric lighting Does anyone know any method to remove ghosting in volumetric lighting?

When light move it leaves trail behind, i would like to remove it.
Volumetrics are Bart Wronski style (in frustum) with exponential temporal accumulation.

I have tried neighborhood clamp, Karis and variance clipping, both remove ghosting but also introduce other artifacts.

Temporal by definition will ghost. I’d limit past frame sampling, apply weight < 0.5, limit movement etc.


why is translating in 3D space the same as shearing in 4D space? I was reading "3D Math Primer for Computer Graphics and Game Development" and there was something the author had said that I thought was particularly interesting, he stated

  It is important to understand that this matrix multiplication is still a
  linear transformation. Matrix multiplication cannot represent “translation”
  in 4D, and the 4D zero vector will always be transformed back into the 4D
  zero vector. The reason this trick works to transform points in 3D is that
  we are actually shearing 4D space. (Compare Equation (6.11) with the
  shear matrices from Section 5.5.) The 4D hyperplane that corresponds to
  physical 3D space does not pass through the origin in 4D. Thus, when we
  shear 4D space, we are able to translate in 3D.

I'm familiar with the shearing transformation, and I can see how a translation matrix in 4D resembles that of a 3D shear. I did not quite understand how this translation in 3D though. So, restating the question I had asked, how does a shear in 4D equate to a translation in 3D space? A geometric visual would also be nice to help me understand this a bit more.

In a linear transformation system, your origin is always a fixed point, since 0*anything = 0. So imagine you have a cinema screen, and the origin is at the centre of the screen. Using linear transformations, you can rotate, scale or shear the image, what you can't do is move it, since you have a fixed point in the middle.

Now add a dimension, and move your origin out of the screen through this new dimension. Your origin is now at the projector, at <0, 0, 0>, and the centre of your screen is at <0, 0, 1>. So as well as the image transforms you had available before, you can now effectively move your image, by shearing through the space in between the projector and the screen.

Add another dimension and you have the 4D -> 3D case.


Trading off instancing for render order I've been doing some searching online and it seems like I could improve my renderer by ordering my draw calls based on depth. For opaque objects render the closest items first and move backward in depth to hopefully take advantage of depth test rejection.

The question I have is would this be worth the tradeoff of sacrificing instancing? It seems like the most straightforward approach would be to stop instancing completely and do each draw call one by one. I'm sure you could write some clever code to find groups within a new depth-first rendering order to instance but it seems like you'd get substantially less benefit.

It depends on your GPU. "Tiled renderers" do this for you so the benefit of doing it yourself is minimal (unless you have some more efficient way of knowing the order, e.g. sorting a fixed-viewpoint scene in advance). In this case, your best way of keeping efficiency is by ensuring they are allowed to draw the scene all in one go by avoiding glReadPixels and similar sync points between draw calls.

Even for a truly immediate-mode renderer, instancing can be hugely powerful and reducing overdraw is unlikely to be worth it, but the trade-off comes down to whether you're bottlenecked on the fragment shader or by the memory bandwidth used feeding vertices to the vertex shader. In turn that will depend on how big your instanced geometry is (and how many instances), and how long your fragment shader takes to execute. These are all specific to your application and to the GPU you're running on, so you can only really know by profiling.

As an outright guess I'd say it's unlikely that the change you're suggesting will improve performance, unless you have few instances and a big fragment shader on a non-tiled GPU architecture.


SSAO - artifacts appearing I am trying to implement SSAO using DirectX11 but instead I got white screen with few black dots on model. My suspect is that kernel generation or usage might be wrong. I've tried changing order of TBN matrix and sample multiplication order in pixel shader and it doesn't change results in any way:

In fact those "dots" are small models of model itself that appear on it instead of dark creases (Example with sphere model):

My G-Buffers looks like this (Position, normal, tangent, bitangent):

myKernelGeneration.cpp

//Create kernel for SSAO
std::uniform_real_distribution<float> randomFloats(0.0f, 1.0f);
std::default_random_engine generator;
XMFLOAT3 tmpSample;
for (int i = 0; i < SSAO_KERNEL_SIZE; i++)
{
    //Generate random vector3 ([-1, 1], [-1, 1], [0, 1])
    tmpSample.x = randomFloats(generator) * 2.0f - 1.0f;
    tmpSample.y = randomFloats(generator) * 2.0f - 1.0f;
    tmpSample.z = randomFloats(generator);

    //Normalize vector3
    XMVECTOR tmpVector;
    tmpVector.m128_f32[0] = tmpSample.x;
    tmpVector.m128_f32[1] = tmpSample.y;
    tmpVector.m128_f32[2] = tmpSample.z;

    tmpVector = XMVector3Normalize(tmpVector);

    tmpSample.x = tmpVector.m128_f32[0];
    tmpSample.y = tmpVector.m128_f32[1];
    tmpSample.z = tmpVector.m128_f32[2];

    //Multiply by random value all coordinates of vector3
    //float randomMultiply = randomFloats(generator);
    //tmpSample.x *= randomMultiply;
    //tmpSample.y *= randomMultiply;
    //tmpSample.z *= randomMultiply;

    //Scale samples so they are more aligned to middle of hemisphere
    float scale = float(i) / 64.0f;
    scale = lerp(0.1f, 1.0f, scale * scale);
    tmpSample.x *= scale;
    tmpSample.y *= scale;
    tmpSample.z *= scale;

    //Pass value to array
    m_ssaoKernel[i] = tmpSample;
}

myPixelShader.ps

Texture2D textures[3]; //position, normal, noise
SamplerState SampleType;

//////////////
// TYPEDEFS //
//////////////

cbuffer KernelBuffer
{
    float3 g_kernelValue[64];
};

struct PixelInputType
{
    float4 positionSV : SV_POSITION;
    float2 tex : TEXCOORD0;
    float4x4 projection : TEXCOORD1;
};

const float2 noiseScale = float2(1280.0f / 4.0f, 720.0f / 4.0f);
const float radius = 0.5f;
const float bias = 0.025f;
////////////////////////////////////////////////////////////////////////////////
// Pixel Shader
////////////////////////////////////////////////////////////////////////////////
float4 ColorPixelShader(PixelInputType input) : SV_TARGET
{
    float3 position = textures[0].Sample(SampleType, input.tex).xyz;
float3 normal = normalize(textures[1].Sample(SampleType, input.tex).rgb);
float3 randomVector = normalize(textures[2].Sample(SampleType, input.tex * noiseScale).xyz);

float3 tangent = normalize(randomVector - normal * dot(randomVector, normal));
float3 bitangent = cross(normal, tangent);
float3x3 TBN = { tangent, bitangent, normal };

float3 sample = float3(0.0f, 0.0f, 0.0f);
float4 offset = float4(0.0f, 0.0f, 0.0f, 0.0f);
float occlusion = 0.0f;

for (int i = 0; i < 64; i++)
{
    sample = mul(TBN, g_kernelValue[i]);
    sample = position + sample * radius;

    offset = float4(sample, 1.0f);
    offset = mul(input.projection, offset);
    offset.xyz /= offset.w;
    offset.xyz = offset.xyz * 0.5f + 0.5f;

    float sampleDepth = textures[0].Sample(SampleType, offset.xy).z;
    occlusion += (sampleDepth >= sample.z + bias ? 1.0 : 0.0);
}
occlusion = 1.0f - (occlusion / 64.0f);

return float4(occlusion, occlusion, occlusion, 1.0f);
}

Offset.xy is definatelly off because it just return XY coordinates from screenspace:

Clamping solved 'small copies of model' on the model itself, thanks!

sampleDepth actually looks like this and indeed is not in viewspace and it may really explain those little models now:

Using viewspace (offset = mul(projection, offset) ---> offset = mul(view, offset)) solves depth problem but final buffer is clear white. No effects are actually visible. What next step do you suggest? If depth comparing is correct now, what might be off?

UPDATE:
Comparision is working but in a wrong way. Below line results in just fully white buffer screen:

occlusion += (sampleDepth >= sample.z + bias ? 1.0 : 0.0);

Changing it to:

occlusion += (sampleDepth >= sample.z - bias ? 1.0 : 0.0);

Actually gives us comparision but it is really bold and doesn't include only holes and creases but whole model. Changing bias to small values like 0.001f doesn't help:

Update #2:
Directly comparing gives result presented below. However it doesn't seem satisfying enough to use as it seems to present rather edges than creases and holes:

occlusion += (sampleDepth == sample.z ? 1.0 : 0.0);


Structural artifacts in ray jitter I recently set up temporal super-sampling in my path-tracer, and now I'm trying to improve early samples by adding random offsets between -[PIXEL_WIDTH] and +[PIXEL_WIDTH] to each initial ray position. The jitter works well enough and hides obvious aliasing artifacts, but it creates tattered edges (e.g: https://imgur.com/a/VIWPK is my test shape after one sample/pixel) instead of regular grain. Is there any way to change that?

Jitter is supposed to make edges more irregular; that's how it masks aliasing in the first place. I didn't realise this when I made the question, but the noise in path tracers comes from undersampled global illumination; because each sample travels in a random direction, it's possible for a visually-significant number of samples to reach unrepresentative areas (e.g. for rays at the bottom of a curve to mostly hit the walls of the curve rather than travel upward towards), and the dissonance between these and the actual image function creates the fuzzy variance you get in path-tracing renderers.

That sort of noise is completely different to the pseudo-one-dimensional edge variance you expect to get from ray jitter at one sample/pixel. Single-sample ray jitter essentially means pulling edges randomly closer to or further away from their actual tendency in order to hide the high-frequency patterns introduced by aliasing; it looks nothing like "fuzzy" GI noise because (at least at the single-sample scale I was thinking about when I made this question) it's one-dimensional (variance about an edge) rather than two-dimensional (variance over a surface).

So, this question is invalid. It assumes that jittered edges are supposed to be fuzzy (as in GI noise), but forgets that edges are one-dimensional and that the jitter can't magically expand them to two dimensions and spread them over some domain (at least, not without spreading the aliasing as well (multi-pixel jitter)). Jitter doesn't produce fuzzy noise because it isn't supposed to; it's only supposed to vary the relative distance of points "on" an edge from the actual edge positions given by the image signal.


OpenGL Polygon Offset Fill implementation example code I am working on a pure java implementation of OpenGL 1 called jGL.
I am missing glPolygonOffsetFill and am looking for an example implementation in java, c/c++ example of this GL function in order to integrate it in jGL.
Would anyone suggest a direction?

I found a workaround suggested at the bottom of this page : to deal with coplanar lines and polygons, one can apply a different glDepthRange to polygon face and polygon wireframe.


What's a proper way to clamp dither noise? When reducing color depth and dithering with a 2 bit noise (with n=]0.5,1.5[ and output=floor(input*(2^bits-1) + n)), the ends of the value range (inputs 0.0 and 1.0) are noisy. It would be desirable to have them to be solid color.

Example: https://www.shadertoy.com/view/llsfz4

(above is screenshot of the shadertoy, picturing a gradient and both ends which should be solid white and black respectively, but are noisy instead)

The problem can be of course solved by just compressing the value range so that the ends get always rounded to single values. This feels bit of a hack though, and I'm wondering if there's a way to implement this "properly"?

TL;DR: 2*1LSB triangular-pdf dithering breaks in edgecases at 0 and 1 due to clamping. A solution is to lerp to a 1bit uniform dither in those edgecases.

I am adding a second answer, seeing as this turned out a bit more complicated than I originally thought. It appears this issue has been a "TODO: needs clamping?" in my code since I switched from normalized to triangular dithering... in 2012. Feels good to finally look at it :) Full code for solution / images used throughout the post: https://www.shadertoy.com/view/llXfzS

First of all, here is the problem we are looking at, when quantizing a signal to 3bits with 2*1LSB triangular-pdf dithering:

 - essentially what hotmultimedia showed.

Increasing contrast, the effect described in the question becomes apparent: The output does not average to black/white in the edgecases (and actually extends well beyond 0/1 before doing so).

Looking at a graph provides a bit more insight:

(grey lines mark 0/1, also in grey is the signal we are trying to output, yellow-line is average of dithered/quantized output, red is the error (signal-average)).

Interestingly, not only is the average output not 0/1 at the limits, it is also not linear (likely due to the triangular pdf of the noise). Looking at the lower end, it makes intuitive sense why the output diverges: As the dithered signal starts to include negative values, the clamping-on-output changes the value of the lower dithered parts of the output (ie the negative values), thereby increasing the value of the average. An illustration appears to be in order (uniform, symmetric 2LSB dither, average still in yellow):

Now, if we just use a 1LSB normalized dither, there are no issues at the edges-cases at all, but then of course we lose the nice properties of triangular dithering (see e.g. this presentation).

A (pragmatic, empirical) solution (hack) then, is to revert to [-0.5;0.5[ uniform dithering for the edgecase:

float dithertri = (rnd.x + rnd.y - 1.0); //note: symmetric, triangular dither, [-1;1[
float dithernorm = rnd.x - 0.5; //note: symmetric, uniform dither [-0.5;0.5[

float sizt_lo = clamp( v/(0.5/7.0), 0.0, 1.0 );
float sizt_hi = 1.0 - clamp( (v-6.5/7.0)/(1.0-6.5/7.0), 0.0, 1.0 );

dither = lerp( dithernorm, dithertri, min(sizt_lo, sizt_hi) );

Which fixes the edgecases while keeping the triangular dithering intact for the remaining range:

So to not answer your question: I do not know if there is a more mathematically solid solution, and am equally keen to know what Masters of Past have done :) Until then, at least we have this horrific hack to keep our code functioning.

EDIT
I should probably cover the workaround-suggestion given in The Question, on simply compressing the signal. Because the average is not linear in the edgecases, simply compressing the input-signal does not produce a perfect result - though it does fix the endpoints:

References

https://www.shadertoy.com/view/llXfzS
http://loopit.dk/rendering_inside.pdf
http://loopit.dk/banding_in_games.pdf
http://32ipi028l5q82yhj72224m8j-wpengine.netdna-ssl.com/wp-content/uploads/2016/03/GdcVdrLottes.pdf


Can the framebuffer in OpenGL jargon or its color buffer end up being the one and the same memory location as the one scanned by a display controller? My understanding is:

the 'framebuffer' in OpenGL is a collection of buffers: many (due to swapping or stereo rendering) color buffers, (only one?) z-buffer and (only one?) stencil buffer;
each OpenGL application has a 'default framebuffer', but can have more 'framebuffer objects';
a 'compositing window manager' aka 'compositor' only cares about an application's current front color buffer of its 'default framebuffer'. The compositor calls this buffer 'off screen buffer'.
the compositor reads all applications' 'off screen buffers' and composites them onto a single image called screen buffer' aka 'video buffer' aka 'regen(eration) buffer';
a display controller will read (scan?) the 'screen buffer' and convert it to a signal to be sent to the physical screen.

Main question:
Can it be (eg. if I run a video game full-screen) that the compositor could simply declare the application's off-screen buffer the same as its 'screen buffer' so that the same location in memory that fragments had their colors originally blended onto will actually be the location the display controller will read from?
I.e. OpenGL will render to some area in either VRAM or RAM and without coincidence this same location will be read by the display controller even after any sort of compositor stage.
Additionally:

Does the compositor designate the 'off screen buffer' for the application (or multiple locations for double/triple buffering or stereo) and it's up to the application to fill that area in memory and "ring the compositor" when its ready or
does the application create the buffer and the compositor is only told where to read from (eg. the app's OpenGL draws to a back buffer, designates it as the front and tells the compositor to read it)?
or is it a mix of the two?

Can it be (eg. if I run a video game full-screen) that the compositor could simply declare the application's off-screen buffer the same as its 'screen buffer'

Yes. This is one of the things that "fullscreen exclusive" mode would do for you: it enables the application's swap buffers (front/back default framebuffers) to be directly scanned out by the GPU's display engine, without needing to go through a compositor first, saving a little bit of performance.
Nowadays there is also support for "borderless windowed fullscreen" (see Fullscreen Optimizations for Windows 10 for instance, though I expect other OSes have similar functionality). This is a mode where you still go through the compositor, but the compositor has a shortcut method when it detects that your app is covering the full screen with no other windows rendering on top of it. In that case it can skip the compositing steps and scan out directly from your swap buffers, while retaining the ability to seamlessly switch back to compositing mode if another window should pop up (such as an overlay, or if you Alt+Tab away from the game, etc.)

Does the compositor designate the 'off screen buffer' for the application

Also yes. When you set up an OpenGL context (or any other graphics API context) your app will request the number and format of swap buffers it wants (subject to the choices offered by the OS/driver); then the OS/driver will give you the buffers, and you render into them. You can create your own framebuffers as well, such as depth/stencil buffers or other offscreen buffers for whatever purpose, but ultimately your app will need to put the image you want to show up on the screen into the provided swap buffers. The buffers will be set up so the compositor can also access them. When you do a glSwapBuffers call, you're informing the OS/compositor that you finished a new frame and asking it to please show that on the screen (either by scanning it out directly or by including it in the next compositor frame).


Early depth test in WebGL I understand that in OpenGL early depth test can be performed in the rasterizer (before running the fragment shader), but is it the same case for WebGL? If so, how is early depth test enabled in WebGL?

In my answer I relate to WebGL 2 / Opengl ES 3.0.

As far as I know ARB_shader_image_load_store is not supported. But there is discard available for fragment shaders in WebGL 2! So what you can do is to

make a depth pass with a straight-forward fragment shader and
then in a second pass test gl_FragCoord.z against the value of the depth texture.

It's up to you, if it's worth the additional texture lookup and rendering the scene twice.


Mitchell's Best Candidate Algorithm I'm trying to generate an image where black dots are arranged in a blue noise distribution on a white background.

I know that there are other ways to do this, one of the best being "Fast Capacity Constrained Voronoi Tessellation." [Hongwei 09], but I'm using Mitchell's best candidate algorithm.

This algorithm works by generating $N$ random pixel locations as candidates for where the next black pixel should go and chooses the candidate which has the farthest distance to the nearest black pixel.

I've implemented this and have used it to put 455 black pixels on a 64x64 image, using various candidate counts.  Looking at the DFT (frequency magnitude, not phase) of the results, I'm seeing some unexpected frequency data.

Strangely, I never get that "nice concentric rings" DFT frequency amplitude that i'd expect and see in papers regarding blue noise sample patterns.

Are these results expected?

Manually hunting between 100 and 1000 samples, it seems like 400 is pretty near optimal.

Is there some "sweet spot" for the number of candidates to use based on image size and desired sample (black pixel) count to get the best result?

Another very simple, easy to implement, algorithm to generate a Poisson-disk/blue noise point distribution is the following one [ 1 ]:

Decide a radius r, and therefore the expected number N of samples per area (use the formula for maximum packing density of k disks distributed on a toroidal domain see [ 2 ])
Generate 10~20 x N samples in your area using a plain unbiased montecarlo sampling
Until all samples respect poisson disk condition:

randomly choose a sample p
remove all the samples at distance lower than r from p

Eventually step 3 can be furtherly iterated a small number of times choosing the sample with minimal number of surviving samples within distance r.

You can find an implementation of this algorithm in MeshLab.

References

[ 1 ] Efficient and Flexible Sampling with Blue Noise Properties of Triangular Meshes
Massimiliano Corsini, Paolo Cignoni, Roberto Scopigno
IEEE Transaction on Visualization and Computer Graphics, Volume 18, Number 6, page 914--924 - 2012

[ 2 ] A comparison of methods for generating Poisson disk distributions
 Ares Lagae, Philip Dutré,
Computer Graphics Forum vol:27 issue:1 , 2008


How to scale signed distance field fonts properly? I have a setup where I'm rendering a bunch of characters on a canvas with an SDF font. The users can zoom in to see the details of the smaller texts, but currently the smaller characters are quite pixelated. (See the image below.) I'm looking for an approach to improve their quality.
Based on these comments I believe SDF fonts are not really good for small text rendering:

https://computergraphics.stackexchange.com/a/9337/11769

https://gamedev.stackexchange.com/questions/71841/how-do-some-mobile-games-scale-graphics-so-beautifully/71850#comment129983_71850

I'm wondering if there's any viable workaround. For example, would it make sense to somehow reuse the larger characters by rendering them in a separate texture and scaling them down? Because when I zoom out, the larger characters look a lot better as they get smaller, I believe the problem might be that the SDF font cannot be interpolated on a too small scale.
My setup is based on these resources:

https://github.com/libgdx/libgdx/wiki/Distance-field-fonts
https://github.com/SaschaWillems/Vulkan/blob/master/examples/distancefieldfonts/distancefieldfonts.cpp

I've already tried generating mipmaps which didn't really make any difference.

After some trials I've realized my problem was a programming error and not an actual issue with SDF fonts.
Originally I was rendering the numbers on the texture of the canvas, which had a fixed scale. I thought that it will redraw the quads during the zoom but it wasn't the case. After I've separated the character drawing from the canvas and scaled them separately they finally look sharp.
The linked comments about the small text rendering was slightly misleading. They do have some issues with smaller scale, but that's only the case when the view is zoomed out.


Acceleration techniques for CPU soft-shadow calculation in light mapper My light mapper can generate soft shadows just fine - for each texel I cast a ray to the light, offset by some distribution of the 'area' of the light on disc. The problem is that I am casting many rays and that slows down production. I note that even for texels completely in shadow, I still cast 128 rays towards the light, but none of them hit it. This seems like a waste of effort. I imagine I could try to intersect a cone with the scene to reject cases when the texel is so deeply in shadow that multiple rays would be ineffective, but I currently only have a ray-tracer at my disposal, so before I go on I wanted to know if anyone has any good ideas. How can I accelerate the calculation of soft-shadows on the CPU?

You could try to optimize the calculation by first casting a smaller number of "feeler rays" (say 32) to check for penumbra, and cast the remaining rays if the result is in penumbra according to the rays. Of course this can give you false negatives, but you could then try to improve the heuristics by checking the results of nearby feeler rays.


Why is spherical harmonics used in low frequency graphics data instead of a spherical Fourier transform? I'm curious why spherical harmonics are commonly used in real time graphics instead of a spherical Fourier transform.

I get that spherical harmonics are in a sort of frequency space (like FT is) so you can do convolution very efficiently.

I also get that SH is an approximation of a function on a sphere, using up to an infinite series to perfectly reconstruct the original data, but often using only the first few items in the series.

This sounds a lot like a spherical Fourier transform, but the math uses different functions entirely.

What is the benefit of the SH representation over spherical FT?

Spherical harmonics really are the "spherical Fourier transform" you're looking for. The kind of hack you mention in comments, of doing a 2D Fourier transform on a lat-long projection, suffers from all the problems you usually have when you try to project a sphere onto a plane: not all spatial relations in the sphere are well-represented in the plane. If you take stretching at the poles as an example, that clearly results in a frequency shift. High-frequency components in the sphere get shifted down to low frequencies in the plane, and when you do the inverse transform, any inaccuracy shows up as high-frequency components at the pole.

Such a transform is useless for analysing the spectrum of the original signal, because it distorts the frequencies (and distorts them differently in different parts of the sphere). It's also poor for representation, because of the introduction of these high-frequency artefacts.

Spherical harmonics use different basis functions so they can work directly on the lat-long without treating it like a plane. If you plot the response of the spherical harmonics on a plane projection of the sphere, they look kooky (like a map of the earth does), but they look much more natural on a sphere. They don't suffer from artefacts at the poles, and they don't frequency-shift signals. They're also rotation-invariant, so it doesn't even matter where you put the poles. They don't even have poles, in the sense of discontinuities, which is a property you can't achieve from a plane projection however many ad hoc co-ordinate transforms you do. Rotation-invariance is useful for applications like environment maps, where you'd like to rotate the spherical-harmonic transform of the environment (light probe, or whatever) into the local co-ordinate system before feeding it to the shader. There isn't a projection onto the plane that has this property.


What is the relation between colour spaces and what is actually displayed on our screens? I am not entirely sure that this is the right stack exchange, but I couldn't find any other suitable one - please redirect me if necessary.
There exists mathematically defined colour spaces which help us represent colors with accuracy/efficiency in computers, and different color spaces will capture different ranges of the human visible colour gamut, and because our screens cannot represent colors as raw wavelengths we must use these spaces instead.(correct me if anything said there is wrong)
How do these relate to how our computer screens actually show colour? From what I understand, our screens only take in N-bit RGB signals for their LCDs, so why do we worry about having all these complex, computationally expensive colourimetric spaces, when we want to do colour processing or storage etc. For example, the sRGB space has a gamma encoding, to represent a different data range with the same amount of bits... but that gamma encoding (for a greater range of dark tones?) cannot actually be displayed on screen. And CIE xyY might be excellent for spectrum based rendering and accurately producing and grading colours - but I understand that we cannot actually see their results, only RGB approximations. Again correct me if any of the above is wrong! I say none of this with much authority, which is mainly why I have to ask this question :)
We are storing different, nuanced, "perception correct", data in this 8-bit channel format - but is that extra nuance is  lost as soon as we send it off to our raw RGB 8-bit channel screens, and if so, doesn't that loss invalidate (to some extent) all our extra measures to produce ever more accurate and wider gamuts?
This question focusses on R8G8B8A8 displays, as I imagine HDR would have a different story.

Several reasons. Im listing them in random order

There are entire industries that do other things than display things on computer screens. If you were to print a booklet, make a package, movie projection or paint a car you would probably be wise to be able to mathematically model it for design, quality control and documentation purposes.

Not all screen suck and not all are good. Quite many screens out there can show wider color ranges than sRGB, or wider but still not entire sRGB. See sRGB is well suited for the designs it was designed for namely crt screens. LCD screens have had  hard time coming to sRGB gamut, but we are getting there. So many screens can not even do sRGB and many now exceed it.
The RGB color on each screen is different! Unless you have a screen that has been calibrated to sRGB odds are low that it shows sRGB (even if it does bet goes off in few weeks). Now for most people this is ok they arent aware how much off their screen is (i remember calibrating for first time o was quite shocked).
Anyway point is that you might be interested is describing the color so that you can do same color, not just same numeric value, on a different screen or display technology.

You might be doing color science and communicating measurements to others, or calculate how fast humans can separate the colors.

You might be developing a light simulator, i dunno like for movie special effects and or technical design and your interested in the light spectrums.

You might need to do distributions of colors visually

And so on...
As for gamna encoding your screen is not linear. If your screen were tuned linear it would be crappy indeed. And in anycase good screens have 10 to 12 bits of color to work with so gamma correcting is no problem.
As for spectral colors CIE is not dealing with spectrums... Not at all. All 3 component color is dealing with human perception. Spectrums are way different things, the thing you call orange on screen and what your physics book called wavelength are different things.


How to do a color separation with more than 3 primary colors How would one do a color separation if there are more than 3 color primaries, or the primaries are nonstandard. In Standard  CMYK conversion K is relatively easy conceptually to figure out. Its just a constant value off all the channels.

How would one construct a CMY + orange for instance. Or in the case of a led array with say Red, Yellow, Blue and Violet for example. How would one approach this problem.

I'm fine with a conceptual answer no need to do LAB to end result conversion for example. Though that would be nice.

The mathematical approach to this is to represent the other colors/light sources in terms of your standard primaries in the color space. Represent your target color and available light sources as vectors with, say, the RGB color space as the basis. Figuring out how to display your target color using your available sources then becomes a change of basis, a standard linear algebra operation, where the target basis consists of your LEDs/nonstandard primaries.

If the dimensions of the source and destination bases are different, the change of basis matrix won't be square and thus won't be invertible. In that case, you need to solve a system of linear equations, expressed in matrix form:

$$c_{RGB} = [r, y, b, v] \cdot c_{RYBV}$$

Where $c_{RGB}$ and $c_{RYBV}$ are the coordinate vectors of your desired color expressed in terms of RGB and custom primaries, respectively, and $r$, $y$, $b$ and $v$ are your custom primaries (basis vectors) in RGB coordinates.

Solving this system is another common linear algebra operation, and there are a variety of numerical and symbolical algorithms to do so. The system is over-constrained, so solutions will likely have a free variable, however since we can't physically produce negative light, nor do the primaries have infinite dynamic range, for most practical purposes each coefficient will have to be limited to be within the $[0, 1]$ range. This will render many colors unrepresentable under certain sets of primaries.


How does UV unwrapping work? I would like to project the triangles of my mesh to a 2D surface. I would like to minimalize the distorion, avoid breaking connected polygons if possible, and also maximalize the used space on the 2D surface.

I tried to look for algorithms/papers about the topic, but I can only find articles about how to use UV unwrapping in 3D modelling softwares like Blender.

UV unwrapping is a difficult topic. They can be both combinatorial algorithms or variational methods but in general they're optimization based, i.e. you setup an optimization problem and you solve it using some numerical optimization solver. I'm just going to give you some names and some libraries you can use eventually. I'll give you few names (both classic and more recent) and you can have a look yourself. ABF (Angle Based Flattening), LSCM (Least Square Conformal Mapping), ARAP (As rigid as possible), BFF (Boundary first flattening), Variational Surface Cutting, OptCuts.

For ARAP and LSCM you can use libigl. Boundary first flattening was developed by Keenan Crane few years ago. Variational surface cutting is an improvement over BFF. And I recently discovered OptCuts. The code is available and you can run them yourself.

You need to read through the papers to understand how they works if you wanted to implement them from scratch (not going to be easy, parametrization is a difficult subject). But if you want to just to run them just clone the repos and try them yourself.
(libigl comes with tutorials, and two of these are about ARAP and LSCM). BFF, Variational Surface Cutting and OptCuts have a GUI based app so you can see the unwrapping and you can easily isolate the code if you need them in your own code.


Vectorizing to polylines instead of paths I am trying to implement a shape matching algorithm for vector images discussed in a paper.

The input to the algorithm is a model of 2D shapes deﬁned by contour segments. According to the paper, such segments can be deﬁned as polylines, obtained for example by vectorizing the output of an edge detector like Canny.

I am trying to vectorize a tiff image using Inkscape's bitmap tracing feature. The svg image I got from it has a path node with many attribute values, but that is not what the algorithm wants:

How can I vectorize to polylines instead of paths?

If you look at chapter 8 of the SVG Specification, it describes how to parse a path element. The short version is that you'll want to find the d attribute of the element. That element should be a string describing the curve. It will contain the following commands:

m - Moveto command
l - Lineto command
c, s, q, & a - Curve commands
z - close path

Simple lines will just be combinations of m and l sequences. The curves will be either circular arcs, quadratic bezier or cubic beziers.

To convert a Bezier curve into line segments, you can do the following:

const float kNumPolyLines = 10; // <- change this to make more lines per bezier segment
const float kDeltaT = 1.0 / kNumPolyLines;
Point c0;
Point c1;
Point c2;
Point c3;
GetBezierControlPoints(&c0, &c1, &c2, &c3); // <- get the 3 or 4 control points for the next bezier segment
Point prevPoint = c0;
Point currentPoint;
for (float t = kDeltaT; t <= 1.0; t += kDeltaT)
{
    currentPoint = CalculateBezier(c0, c1, c2, c3, t);

    // Now you have the next line segment in your poly line.
    // It goes from prevPoint to currentPoint. Store it or draw it,
    //or whatever you need

    // Get ready for the next iteration
    prevPoint = currentPoint;
}

You can find the formula for both quadratic and cubic bezier curves on Wikipedia.


searching for acceptable quality shadow mapping techniques Recently while searching of solving the shadow acne problem of traditional shadow mapping I implemented exponential shadow maps. It did the trick (no acne at all) but at the same time introduced other unacceptable errors.
For depth map blur I use gaussian blur with smallest sigma=1.
Test for shadow map:
float occluder = texture(shadowMap lightCoords.xy).r;
float c = 5000.0;
float receiver = lightCoords.z;
float shadow = exp(c*(occluder-receiver));
shadow = clamp(shadow, 0.0, 1.0);

with small c factor c=100.0:

Unacceptable light bleeding
with high c factor c=5000.0:

No light bleeding but high frequency detail appear "swollen".
Cant find optimal c - light bleeding appear even at c=3000.0 and high frequency shadow error is already there. Not blurring the depth map helps but then aliasing occurs.
And my question is - how can I improve this technique (ESM) or should I look for another? I think good quality shadows with nice performance are definitely possible - as seen in modern games like Witcher 3 or Fallout 4.

Well nevermind. I made some research and actually gonna:

sample ESM using Poisson sampling in PCF fashion (thanks Bart Wronski for great Poisson Sample generator app) and extend this to PCSS technique (variable penumbra). Render to texture.
optionally depth aware blur to soften - EDIT not so fast this option doesnt work as expected, too bad. Instead rotating PCF kernel seem to work fine.

And too bad not much of discussion here.


Differential or intersection of islands of 2D polygons in different layers I have a 2D layer/section containing the 2D polygons colored in shades of green.
I have another layer containing the 2D polygons colored in shades of blue.

I intend to figure out how different are the two layers. Maybe extracting the layers differential. Can anybody provide an algorithm, library or a hint? I took a look at CGAL, but not quite sure which package to try out.

In CGAL, there is the Arrangement package that allows to build a topologically valid planar partition given a set of segments, and the Regularized Boolean Set-Operations that provides boolean operations between polygons.


How to handle quads? I currently can not solve a ray-quad intersection with a quad that bends, because it is impossible to solve (because really a quad can't/shouldn't bend).

Sadly, often times, models with quadrilaterals have impossible surfaces: some quads "bend" rather than be a perfect plane/polygon. You could break the quads up into triangles, but there are two ways to do that. And even then, what do you do with the normals? Keep the quad normal onto the two resulting triangles or just recalculate the normals? What is the industry standard for this process?

It sounds like you want to know how to ray trace a bilinear surface patch.

A quick search turned up this page by Ramsey, Potter & Hansen, which includes a paper and, probably better still, source code!

However, if you just want a "cheap and cheerful" hack approach, you could try replacing the quad with 4 triangles. That is, by a new vertex at the 'centre' (i.e. computing the average of the corners) and joining each edge to that new vertex. This is generally produces a better looking, and order-independent result than just using a pair of triangles.


Using a LUT to speed up a trig heavy shader for mobile devices I am trying to get this shader to run on a really old iDevice, as well as eventually Androids.

Even when I reduce the code down to 2 sine functions per fragment the shader runs at about 20fps.

I have considered taking a leaf out of the book of old shading techniques and creating an array that holds a bunch of predefined trig values and somehow using those to approximate the shader.

In the shader I linked above I am already simulating that by rounding the values sent to the trig function the further left the mouse (while down) goes the less quality of the shader. It's actually pretty cool because really close to the left side it looks like a completely different and pretty cool shader.

Anyway I have two dilemmas:

I don't know what the most efficient way to have an array of like 360 values in it in a GLSL shader, constant or uniform?
I can't figure out how to put a number in a range like usually if I wanted an angle between 0 and 360 (yes I know GPUs use radians) I would do it like so.

func range(float angle)
{
   float temp = angle
   while (temp > 360) {temp -= 360;}
   while (temp < 0)   {temp += 360;}
   return temp;
}

However GLSL does not allow while loops or recursive functions.

It has been suggested in comments repeatedly, but noone felt the need to give a proper answer, so for the sake of completeness, a straight-forward and common solution to this problem might be to use a texture as lookup table, specifically a 1D texture that contains all the values of your function for the possible input range (i.e. $[0,360)$ / $[0,2\pi)$). This has various advantages:

It uses normalized coordinates, i.e. you access the texture by mapping your angles from $[0,360]$ to $[0,1]$. This means your shader doesn't actually have to care about the specific amount of values. You can adjust its size according to whatever memory/speed vs. quality tradeoff you want (and especially on older/embedded hardware you might want a power of two as texture size anyway).
You get the additional benefit of not having to do your loop-like interval adjustment (although, you wouldn't need loops anyway and could just use a modulus operation). Just use GL_REPEAT as wrapping mode for the texture and it will automatically start at the beginning again when accessing with arguments > 1 (and similarly for negative arguments).
And you also get the benefit of linearly interpolating between two values in the array basically for free (or let's say almost free) by using GL_LINEAR as texture filter, this way getting values you didn't even store. Of course linear interpolation isn't 100% accurate for trigonometric functions, but it's certainly better than no interpolation.
You can store more than one value in the texture by using an RGBA texture (or however many components you need). This way you can get e.g. sin and cos with a single texture lookup.
For sin and cos you only need to store values in $[-1,1]$ anyway, which you can naturally upscale from the normalized $[0,1]$ range of a common 8-bit fixed-point format. However, that might not be enough precision for your needs. Some people suggested using 16-bit floating point values, as they're more precise than the usual 8-bit normalized fixed point values but less memory intensive than real 32-bit floats. But then again, I also don't know if your implementation supports floating point textures to begin with. If not, then maybe you can use 2 8-bit fixed point components and combine them into a single value with something like float sin = 2.0 * (texValue.r + texValue.g / 256.0) - 1.0; (or even more components for finer grain). This lets you profit from multi-component textures yet again.

Of course it still has to be evaluated if this is a better solution, since texture access isn't entirely free either, as well as what the best combination of texture size and format would be.

As to filling the texture with data and adressing one of your comments, you have to consider that texture filtering returns the exact value at the texel center, i.e. a texture coordinate off by half the texel size. So yes, you should generate values at .5 texels, i.e. something like this in application code:

float texels[256];
for(unsigned int i = 0; i < 256; ++i)
    texels[i] = sin((i + .5f) / 256.f) * TWO_PI);
glTexImage1D(GL_TEXTURE_1D, 0, ..., 256, 0, GL_RED, GL_FLOAT, texels);

You might, however, still want to compare this approach's performance against an approach using a small uniform array (i.e. uniform float sinTable[361], or maybe less in practice, keep an eye on your implementation's limit on uniform array size) which you just load with the respective values using glUniform1fv and access by adjustig your angle to $[0,360)$ using the mod function and rounding it to the nearest value:

angle = mod(angle, 360.0);
float value = sinTable[int(((angle < 0.0) ? (angle + 360.0) : angle) + 0.5)];


Slide a rectangle along a sphere I'm using NASA WorldWind to place a rectangle on the Earth ('sphere'). When I drag the rectangle on the sphere, the rectangle changes shape and size but the dimensions should be preserved.

What is needed to preserve the rectangle's original dimensions when it is dragged along the Earth/sphere?

EDIT

It looks like most of the code in use was copied from this example: http://worldwind31.arc.nasa.gov/svn/trunk/WorldWind/src/gov/nasa/worldwind/util/BasicDragger.java

The line of code in the example that confuses me the most is

double y = event.getMouseEvent().getComponent().getSize().height -
                                       this.dragRefObjectPoint.y + dy - 1;

The resulting behavior is the 'rectangle' that is mapped to the globe changes shape and size.

I also want to point out my experience with computer graphics and NASA worldwind are limited. I'm especially rusty on linear algebra and very weak with geomtery. I'd appreciate suggestions on resources (outside of the obvious NASA WorldWind reference).

If I understand you correctly, the problem could be defined as the (edge) intersection of a cube with a sphere. In that case, you could shade the edges by calculating the distance to the edges of the cube.

//note: from http://iquilezles.org/www/articles/distfunctions/distfunctions.htm
float udBox( vec3 p, vec3 b )
{
  return length(max(abs(p)-b,0.0));
}

Aligning the cube poses another "interesting" issue - you probably want to use the sphere-normal and screen-up to generate a basis.


Jagged texture's edge on perfectly straight UV of sphere mesh I unwrap UV from sphere mesh to grid and put texture to align with UV grid too. When white and black border of texture fall between UV columns, I get jagged edge like in the picture. This only happens with double-curve mesh. I want to know what cause this to happens?

It looks like distortion because the trapezoids are rendered as two triangles by the GPU. This leads to incorrect UV interpolation.

Try this: draw a horizontally symmetrical trapezoid with the top being much shorter than the bottom. Then draw one of its diagonals to split it into two triangles. Place a mark at the midpoint of that diagonal. It should be obvious the mark is not at the horizontal center of the trapezoid. Yet that mark is where the middle of the interpolated texture coordinates will be. Your border will go through the mark but also through the center of the top and bottom edges.

You should not have that problem when producing a final image with any decent renderer.


How to draw depth-based volume in real-time Normally when we talk about realistic transparent volumes, we care about refraction (and total internal reflection), and we care about scattering. But there's a much simpler case of volume transparency, where the opacity of the object depends on the distance that light travels through it.

I'm writing a real-time visualization with a forward-rendering pipeline (on WebGL) and I'd like to show transparent solids this way, without having to resort to path tracing. My solids are homogeneous and isotropic, and I'm not interested in scattering or refraction. I just want thin parts of the solid to be very transparent and thicker parts of the solid to be more opaque.

It seems like most real-time transparency algorithms (e.g. OIT) are mainly for getting surfaces/sheets right, instead of volumes, and are more concerned about correct stacking, refraction, and scattering.

It seems like making the colour of the object depend on the thickness of material behind each fragment should be easily achievable with something like an extra depth pass where I draw opaque objects that intersect transparent objects, and back faces of transparent objects, possibly with some extra correction where the notional ray for one pixel goes through a torus-like object more than once. Intuition tells me that this ought to be a standard algorithm, but I don't know of one. Does this algorithm already exist, or do I just need to get my pencil and paper out and write one?

The issue is that an extra depth pass won't cut it. You may need an arbitrary number of extra depth passes. Just imagine the volume between two sinusoidal surfaces, you would have infinitely many alternating z-intervals of volume/empty space as long as you're looking from a specific direction.

Edit:
Taking into consideration the updated formulation, here's my suggestion for a rather general algorithm with different attenuation coefficients $\kappa_i$ for each volume. Note that there are non-trivial parts that are missing, also if you do not require different attenuation coefficients it can be optimized even further.
The algorithm relies on you drawing the volumes pixels in reverse z-order (this is the non-trivial missing part). You draw your volumes in a separate pass. You keep an attenuation density accumulation variable $\kappa$ for each pixel (initialize to $0$), as well as a distance time stamp $\delta$ (initialize to the the $z$ of the far plane, which I will denote $\max$), and a "color" variable $c$ (initialize to $0$). Whenever you draw a pixel:

if $\delta==\max$ and you drew a front face of volume $i$ then:
$$d = \delta-pixelDepth$$
$$c = attenuate(c,\kappa_i,d)$$

Where $\kappa_i$ is the attenuation of the currently drawn pixel (you can simply draw the volumes in the "color" of their attenuation and use that).

if $\delta<\max$ and you drew a back face of volume $i$ then:

$$d = \delta - pixelDepth$$
$$\delta = pixelDepth$$
$$c = attenuate(c,\kappa, d)$$
$$\kappa = \kappa + \kappa_i$$

if $\delta<\max$ and you drew a front face of volume $i$ then:
$$d = \delta -pixelDepth$$
$$\delta = pixelDepth$$
$$c = attenuate(c,\kappa, d)$$
$$\kappa = \kappa - \kappa_i$$
after you've drawn all pixels if $\kappa > 0$:
$$c = attenuate(c,\kappa,\delta)$$

Note that the 4th check handles the case where the camera is inside a volume (and it ends behind the camera), but the frustum is not entirely inside it. Similarly the first check handles the case where a volume is cutoff by the frustum. However, the case where the camera frustum is totally inside a volume is not handled (you can try to check this by verifying that the camera is inside a volume and then simply adding a constant to $\kappa$, then you have to modify the end case too, to check $>const$, or just not have such large volumes).
Note that the $\delta$ part can be handled by the depth buffer. Obviously you can use a compute shader, or use additional buffers to perform all of this. The function $attenuate$ can be standard Beer-Lambert uniform attenuation or whatever else you want. Combining the volumes with the original scene happens by setting the "far plane" for each pixel to the closest drawn solid geometry depth (that is initialize $\delta$ based on what you have in the depth buffer for your solid geometry).


How can I verify if a selection area is over a shape in SVG? I'm creating an SVG editor.

I have a simple selection tool that appears when I click and move my mouse from a blank area in my SVG.

My SVG is populated with rectangles that can have a rotation applied to.

I have the X and Y position applied to a translate function.
Width and height are easy to calculate based on a scale factor and original dimensions of my rectangle(s).
My rotation angle is applied in a rotate function

I know about the point in polygon algorithm but I don't know how to calculate the points of my (rotated) rectangles.

My question is how can I verify if my selection area is over one or more of these rectangles and if the PIP algorithm is the best, how can I calculate the points of my rectangle(s)?

Here is the kind of render I'm trying to have:

In pseudocode

For each rectangle:
    If the rectangle overlaps the selection area, highlight the rectangle

This is all that is required for a correctly working approach, but there are a number of other things you might need to take into account if this approach performs too slowly. I recommend implementing the simple approach, and once it works correctly you can make gradual improvements if it is not sufficiently smooth and responsive (this may not be necessary unless you have a large number of rectangles or restrictive hardware/software).

Determining whether a rectangle overlaps the selection rectangle

As you point out, using the point in polygon algorithm is impractical for this purpose - each rectangle is made up of an infinite number of points. So we need a completely different approach.

One way to check if a candidate rectangle overlaps the selection rectangle is to check for the following two cases:

Check if any edge of the candidate rectangle intersects an edge of the selection rectangle.
Check if either the candidate rectangle or the selection rectangle is completely contained within the other.

If either of these are true, there is some overlap. If neither of these are true, there is no overlap.

The complete containment check is simplified by the fact that the selection rectangle is never rotated - always remaining aligned to the x and y axes:

To check if a candidate rectangle is completely contained within the selection rectangle, check that all 4 of its corners are between the x boundaries of the selection rectangle, and between the y boundaries of the selection rectangle.
To check if a candidate rectangle completely contains the selection rectangle, check that it has one corner outside the bounds of the selection rectangle in each of the 4 orthogonal directions (left, right, up, and down). If so, it either contains the selection rectangle completely, or one or more of the edges intersect (but edge intersection was checked for in the previous stage, so we're only checking for complete containment if we already know there is no edge intersection).

Line segment intersection

To check whether any of the edges of a candidate rectangle intersects with any of the edges of the selection rectangle, you can either use a general line segment intersection algorithm and apply it to each pair of candidate edge and selection edge, or you can take advantage of the fact that the selection rectangle is never rotated,as follows:

Parallel case

If the candidate rectangle has edges parallel to the x and y axes (that is, it is rotated by 0, 90, 180 or 270 degrees), check each of its edges:

If the edge is vertical, check if its x position is between the x coordinates of the selection rectangle, and if one of the following holds then there is an intersection:

The y coordinate of one of its end points is between the y coordinates of the selection rectangle AND the y coordinate of the other end point is not.
The end points are both outside the y coordinates of the selection rectangle but in opposite directions.

Similarly, if the edge is horizontal, check if its y position is between the y coordinates of the selection rectangle, and if one of the following holds then there is an intersection:

The x coordinate of one of its end points is between the x coordinates of the selection rectangle AND the x coordinate of the other end point is not.
The end points are both outside the x coordinates of the selection rectangle but in opposite directions.

Non-parallel case

Check each of the edges of the candidate rectangle as follows:

First find the points of intersection of the infinite line on which the candidate edge lies, with the infinite lines forming the boundaries of the selection rectangle.

If either of the intersections with the y boundaries of the selection rectangle has an x coordinate between the x boundaries of the selection rectangle, then there is an intersection of one of the horizontal line segment edges of the selection rectangle with the candidate infinite line (so potentially with the candidate line segment too).

Similarly, if either of the intersections with the x boundaries of the selection rectangle has a y coordinate between the y boundaries of the selection rectangle, then there is an intersection of one of the vertical line segment edges of the selection rectangle with the candidate infinite line (so potentially with the candidate line segment too).

To then check if there is an intersection with the candidate line segment, check if one of the following is true:

An intersection with the y boundary of the selection rectangle is between the x boundaries of the selection rectangle AND between the y coordinates of the candidate line segment.
An intersection with the x boundary of the selection rectangle is between the y boundaries of the selection rectangle AND between the x coordinates of the candidate line segment.

Examples of refinements if speed is unsatisfactory

Acceleration data structures such as a grid or space partitioning hierarchy so that not every rectangle needs to be checked.
Only checking the changed parts of the selection (usually one corner of the selection stays fixed while the opposite corner moves).
Tracking which rectangles are already selected to reduce the checking required each time the selection changes:

No need to check unselected rectangles if the selection has purely shrunk.
No need to check already selected rectangles if the selection has purely grown.
It will only be necessary to check both selected and unselected rectangles if the selection has grown in one direction and shrunk in the other.


Image resize with pixel accumulation? I have a grayscale image and want to "resize" it in terms of "pixel concentration".
That means I divide the source image x_old * y_old into x_new * y_new sections, and all (sub)pixel grayscale values in each section shall be accumulated to make the new grayscale value.

Writing two loops also considering the sub pixel parts in each section is easy, but doesn't seem very sophisticated.
Are there some smart and yet efficient algorithms doing the task?

Long story short: downscale using a standard downscaling algorithm. Then multiply the value in each element by originalArea/scaledArea. This is what Rahul meant in the comments.

Why that works:
You can think of every output pixel as a (weighted or not) average of a neighbourhood of the source pixel. And as we know:

average = sum / count

Now, for the caveats.

Broadly, there are 3 types of downscaling algorithms:

Ones that simply do resampling with some kernel
1.1. Ones that lowpass first
1.2. Ones that don't
Pyramid downscaling
Algorithms like the one in "Genuine Fractals" which are intended for detail-preserving upscaling, but could conceivably be abused for downscaling

Since "3." is not intended for downscaling, it's not useful for your case.

The problem with "1.2." is that, normally a small (e.g. 5x5) resampling kernel is used, which means that only a few of the source pixels are taken into account. In image resizing applications, this can manifest as aliasing. In your application, it can manifest as inaccuracy.

This problem with "1.2." can be fixed by using a big resampling kernel. I believe that's what the ImageMagick library used to do. E.g. taking a good-quality kernel like Lanczos and stretching it by x and y. Or you could go ahead and use a big box kernel like you describe in the question. Which one is appropriate depends on your exact application, but if you're dead set on using a box kernel, use that. The algorithm you described in the question would work fine, and I believe that on a CPU there is no better one (except splitting this one into threads), for the reason that any algorithm would need at least N (number of pixels) operations to take into account all the pixels, and your algorithm does a tiny amount of work for each of these N pixels.

But on the GPU there is a better algorithm that takes full advantage of the GPU's strong parallelism. It's called "parallel reduction", you can find info on it based on that. Since it's widely documented, I'll just sketch the algorithm:

Iteratively downscale the image by a factor of 2 by x and y until you get to your desired size.

"1.1." would probably also suit your needs, but I won't comment on it for now, as it's not much better than the other options.


Storing 3D animations for ray tracing I've just finished writing a path tracer that takes OBJ files and renders it. This is convenient for still images, but my end goal was to export a sequence from a 3D application (Blender was what I had in mind), and then render an image sequence from that. Originally I figured an OBJ sequence would do, but that would take a massive amount of space for complex scenes.

I began looking into parsing .fbx, .3ds and other popular file formats, but there's so little out there that I could find. I still don't really understand how those files store animations. I can imagine the mesh is stored and then keyframes indicate which vertices translate...? Maybe? Or whole objects? What happens when you have complex deformation like an ocean wave, fluid, or character where many, many vertices are translating? At that point would it be easier to do some sort of OBJ like sequence? I want to stay away from that if I can since it takes lots of memory/time to export.

Hopefully someone can point me in the right direction or explain how other standalone renderers keep their animation data. Thank you!

I think that it is important to classify between different types of animations here. One rough classification could be

Rigid body animations
Vertex skinning animations
Others...

Rigid body animations

This refers to animations where the actual geometry data does not change. For example, you could have a geometric object, like a unit cube, and apply (usually affine) transformations to it: You can rotate, translate or scale this object. This is usually accomplished by some sort of scene graph: Each node of this scene graph can have information about the rotation, translation and scaling that should be applied to the objects. In general, this is something that can be expressed with a 4x4 transformation matrix.

The key point is that you don't have to store "animated geometry data". You only have to store the geometry data once, in its original state. In addition to that, you store the key frames of the transformation.

In your case, if you wanted to do a rigid body animation, you could store the geometry in an OBJ file, and additionally store the key frame information in an arbitrary form, for example

TIME  TRANSLATION
0.0   ( 0, 0, 0)
0.1   (10, 0, 0)
0.2   (10,10, 0)
0.3   ( 0,10, 0)
0.4   ( 0, 0, 0)

This could describe a movement of the object along a rectangular path, taking 0.4 seconds. Fortunately, you don't have to create your own file format for that. There already are solutions for storing this sort of animation data. For example, the COLLADA format already supports animations like this. A more compact representation of such an animation can be stored in a glTF asset. For example, it can represent animations like this one, from the glTF sample models repository:

Vertex skinning animations

This technique refers, roughly speaking, to cases where you have an "initial" geometry, and you can define "rules" of how this geometry should be deformed based on the pose of a skeleton. As the name suggests, this is mainly intended for character animations, where you define a skeleton consisting of the "bones" of the character, and the geometry defines the "skin" of the character. Vertex skinning is also supported by different file formats like COLLADA or glTF. The effect is shown in this image, again, from the glTF sample models:

As already mentioned by joojaa in his answer, implementing vertex skinning according to the specifications of these file formats may be a bit tricky. Additionally, a considerable amount of the skinning computations is usually done by the vertex shader. So for a ray-tracer, you would have to move these computations into your application code.

Others...

This refers to what you already alluded to in the question: There may be cases where the animation is not a simple transformation of rigid objects, and where you cannot define any "rules" of how the vertices should be transformed. For example, when the vertex positions are computed by a simulator, like a fluid simulator or a soft body simulator.

In doubt, it may simply be necessary to actually store the positions of all vertices, frame for frame. You could achieve this as a sequence of OBJ files. But note that OBJ files contain ASCII data, and thus, are usually large and the geometry data has to be parsed before it can be used. Storing the data in a binary form that can be used by the application directly may be beneficial here.

There are some possible approaches for reducing the amount of data that has to be stored. For example, one could extend the concept of "key frames" here. For example, one could store the initial configuration of al vertices, and then only store the movement of vertices that acutally have changed between two frames. But of course, if (nearly) all vertices changed, the savings may be diminishing.

I'm not aware of any universally applicable, "standardized" solutions for this. Maybe some of the solutions that joojaa referred to in his answer could be helpful here.


Multiple Lights Shading - One Pass vs Multiple Passes I was looking into ways to implement multiple lights shading and I've noticed Unity uses multiple passes to achieve it. It performs a base pass to apply the brightest directional pixel light + 4 vertex lights + SHs and an additional pass for each pixel light, up to a limit defined by the user on the editor.

I'm wondering, since I previously know how many pixels lights I need to shade, why not doing it in a single pass like vertex lights are done? What are the problems of doing so?

It's completely possible to do all pixel lights in the fragment shader (or, say, do 4 at a time) by looping over an array. However, this comes at a great performance cost: You're going to be calculating lighting for every light on every fragment of the scene, even if that geometry isn't actually affected by the light's influence.

I suspect that is reason why Unity doesn't do so: it probably culls the objects and submits only geometry that might be influenced by the respective light on each pass, meaning that shading for a light is only evaluated in the fragments where it may have an effect. This is a trade off between processing less fragments but duplicating the geometry cost.


Keep constant number of visible circles in 3D animation I have created a 3D animation with a perspective projection of white circles moving randomly in a fake 3D space projected on a 2D computer screen (GIF 1).

Since I need to keep the same number of visible circles, every time a circle disappears from the frame, I have to create a new visible one within the frame. To do so, I have written this piece of code:

First I created initial coordinates and the two angles of movements (spherical coordinates):

for circle in circles:

    circle.position.xy = np.random.uniform(-25, 25, size=2)
    z = np.random.uniform(near_z, far_z)

    circle.position.z = z
    circle.position.x *= z/-50
    circle.position.y *= z/-50

    circle.theta_deg = np.random.rand(1) * 360
    circle.phi_deg = np.random.rand(1) * 360

    theta_rad = circle.theta_deg * np.pi / 180
    phi_rad = circle.phi_deg* np.pi / 180

    circle.dx = speed * np.sin(-phi_rad - theta_rad) / frameRate
    circle.dy = -speed * np.cos(phi_rad + theta_rad) / frameRate
    circle.dz = -speed * np.cos(theta_rad) / frameRate

Then, in the loop that plays the animation, and updates the position of each circle, I have put this condition following the same answer that was provided to the same kind of issue here:

max_dist = max(abs(circle.position.x),abs(circle.position.y))
limit_dist = 25 * abs((circle.position.z-near_z) / far_z)

z_rel = np.random.uniform(near_z,far_z)

if max_dist > limit_dist:
    circle.position.x = np.random.uniform(-25, 25) * z_rel/far_z
    circle.position.y = np.random.uniform(-25, 25) * z_rel/far_z

I got a weird result as shown in GIF 2

What is wrong with my condition and how can I detect a circle that disappears from the frame and recreate one inside the frame?

You don't seem to be setting circle.position.z


Ringlike artifacts produced by rays bouncing off a light source I recently set up a (very basic) ray-marched path-tracer, and I'm getting strange surface patterns on my area light [link]. I'm using known-valid analytical normals for the light's surface, and the same patterns appear when I use a well-tested gradient estimator anyway.

Ray bounce directions are calculated with amietia's diffuse BRDF, and regenerated after each bounce. The random numbers in each bounce are uncorrelated (hashed integer versions of the intersecting ray positions) and I'm offsetting ray distances at the start of each bounce by [0.01f] to avoid shadow acne.

The last time I saw this bug was several months ago, and that time it was (probably) caused by shadow acne. What could it be now?

Fixed this today.
The artifacts were produced by shadow acne and worsened by dodgy averages (assuming every ray would complete the maximum number of bounces before returning or exiting the scene) + an undersized PRNG state buffer; maybe I was just really tired, but I still don't know why bouncing rays off my light sources by default seemed like a good idea. The point of backward path tracing is to trace paths from the camera back to the light source(s) in a scene, and there's no reason to continue following a path (=> evaluate bounces) if rays immediately intersect with a source after leaving the camera.


Optimizing performance on hardware I'm working on a webgl audio visualizer that uses particles, and I want to optimize rendering based on the user's hardware. I'd like to offer a "low quality" and "high quality" setting so that it works well on a wide-range of devices.

Is there a way to automatically detect in the browser if the user has hardware acceleration available and generically whether their graphics card is good or not?

What techniques are there for rendering low vs high quality?
My initial ideas for low quality were:

render less geometry (less particles, and nearer "far" clipping distance)
use a smaller framebuffer and scale it up to the size of the canvas
smaller texture sizes

Edit:
Additionally, any resources on performance optimization would be appreciated. It seems that searches mostly result in helping users configure their graphic card settings

Although you may be able to detect what hardware is available as a first approximation of a computer's capability, depending on this might not be useful since the same hardware may behave differently depending on the machine it is hosted in, and any other tasks that may be competing for it.

Use the frame rate

It looks like you are already measuring the frame rate, so you could simply use this value to decide which features to include. If you settle on a target frame rate, then you can order your features from most essential to most optional, and gradually add in less essential features for as long as the target frame rate is exceeded.

You could also remove features in reverse order if the frame rate drops (in order to avoid poor frame rate if the available resources change). If you decide to do this, I recommend setting the target frame rate to a slightly different value for adding and removing features. Otherwise some machines near the border between two feature levels may end up skipping back and for between the two levels, adding and removing that feature endlessly. So set the trigger for removing a feature at a  slightly lower frame rate than the trigger for adding it.

You'll need to find a compromise between adding new features too quickly so that the frame rate suddenly drops further than you intended, and adding features too slowly so that there are several seconds of low quality animation before it settles on the appropriate level of features. You may be able to estimate that some features can be added 2 or 3 at a time if the frame rate is already very far above target. This will depend on the specific features involved and may take some trial and error on a variety of machines with different resources.

If you prefer, you can show a blank background until the frame rate has settled, so the user does not see the feature level being adjusted. Alternatively you may be able to adjust the features sufficiently gradually that there will be no perceptible change in any given moment.

Consider the window size

On my laptop I get 4 frames per second consistently regardless of the window size - whether full screen or a thumbnail sized browser window. Since it appears that the particles move only away from the centre, and do not contribute later to the area they have left, it might be worth considering abandoning particles sooner when the window size is reduced. If this allows a higher frame rate when the window size is reduced, then the extra features will be automatically activated even if they were not possible at full screen.


Smooth shading on sphere approximation In what way is a "cheat" when using smooth shading on a sphere approximation?

I'm not understanding how it's a cheat to use smooth shading on this?

Other questions that are lead after this may be:
Why does it look better than the Gouraud Shaded Model and why is this not necessary generally applicable to any surface?

Sphere's don't have edges like the ones in that picture. The "silhouette" should be a circle. This is because the sphere was rendered as triangles and rasterized. Triangles can only approximate a sphere.

Compare this to ray casting for instance. Where we can directly test the intersection between a sphere and ray thus no need to approximate a sphere with other primitives.

What smooth shading lets us do is interpolate values across the face of a triangle to cheat and make something appear smoother. In reality a sphere (a uv sphere) would look like this:

There are two common ways to make the above sphere look smooth without adding anymore geometry. Both of which involve linearly interpolating values across the face of a triangle. Like barycentric interpolation. With barycentric interpolation, given values at 3 points (on a triangle) and a point we want to know the value for we can calculate a mix between the 3 values at the corners such that it smoothly varies across the face of the triangle.

In rasterization there are two popular ways to smooth shade. The later being used more often.

Gouraud: We calculate the post-lighting (shaded) color at each vertex and interpolate the color across the face of the triangle.

Phong: We calculate the shaded color at every pixel across the triangle, interpolating things like normals across the triangle.

EDIT: The difference between gouraud and phong is that gouraud assumes the color and light intensity change linearly with the normal. Whereas phong does not. For a simple light intensity = dot(normal, lightDir) = cos(angle between normal and lightDir) we can see the relationship between intensity and the normal is nonlinear. This can be well illustrated with the below image (see the seams on the specular highlight. This is the consequence of our linear interpolation):