Why do multiple Gaussian Blurs? Applying multiple Gaussian blurs can result in an effect that is equivalent to a stronger Gaussian blur.

For instance this question says that: Is doing multiple Gaussian blurs the same as doing one larger blur?

Wikipedia also says it, but says that it will always be just as many calculations or more to do it in multiple blurs versus doing it in a single blur.

  Applying multiple, successive gaussian blurs to an image has the same effect as applying a single, larger gaussian blur, whose radius is the square root of the sum of the squares of the blur radii that were actually applied. For example, applying successive gaussian blurs with radii of 6 and 8 gives the same results as applying a single gaussian blur of radius 10, since \sqrt{6^2 + 8^2} = 10. Because of this relationship, processing time cannot be saved by simulating a gaussian blur with successive, smaller blurs — the time required will be at least as great as performing the single large blur.

Source: https://en.wikipedia.org/wiki/Gaussian_blur#Mechanics

However, I've heard and read about people doing multiple blurs in realtime graphics to achieve a stronger blur.

What benefit is there if it isn't a reduction in computation?

There are two cases I can think of where multiple blurs would be performed in succession on a single image.

First, when performing a large-radius blur, it may reduce the total computation if you first downsample the image (which is a blur) and then perform a smaller-radius blur on the downsampled image.  For example, downsampling an image by 4x and then performing a 10px-wide Gaussian blur on the result would approximate performing a 40px-wide Gaussian blur on the original—but is likely to be significantly faster due to improved locality in sampling and fewer samples taken overall.

The initial downsampling filter is often simply a box (as shown above), but it can also itself be something more sophisticated, such as a triangle or bicubic filter, in order to improve the approximation.

This is a Mitchell-Netravali (cubic) downsample followed by a Gaussian. Interestingly, it turns out that using a Gaussian for the initial downsampling doesn't make such a great approximation if your goal is to use it to produce a larger Gaussian.

An initial downsampling step is also frequently used when implementing visual effects like depth of field and motion blur, for similar reasons.

A second reason to perform multiple Gaussian blurs is to approximate a non-separable filter by blending between various Gaussians of different radii.  This is commonly used in bloom, for example.  The standard bloom effect works by first thresholding to extract bright objects from the image, then creating several blurred copies of the bright objects (usually using the downsample-then-blur technique just discussed), and finally weighting and summing them together.  This allows artists a greater level of control over the final shape and appearance of the bloom.

Here, for example, is a weighted sum of three Gaussians (red line) which produces a shape that's more narrowly peaked and heavier-tailed than a single Gaussian (blue line).  This is a popular sort of configuration to use for bloom, as the combination of a narrow, bright center with a wide, diffuse halo is visually appealing.  But since this kind of filter shape isn't separable, it's cheaper to make it out of a mixture of Gaussians than to try to filter with it directly.

Another variation on this idea is the concept of a diffusion profile used with subsurface scattering for skin rendering. Different blur radii may be used for the red, green, and blue channels to approximate the way different wavelengths of light scatter differently, as in GPU Gems 3 skin shading chapter by Eugene d'Eon and Dave Luebke.  In fact, that paper uses a mixture of seven different Gaussians, with different R, G, and B weights for each, to approximate the complicated non-separable, wavelength-dependent scattering response of human skin.


Importance sampling microfacet GGX I have a renderer where the BxDF interface is Sample(), PDF(), and Eval(). The Lambertian BRDF is working well, and I believe I have properly implemented Eval for GGX based on another user's question, but I'm struggling to find a resource I can understand that explains how to generate samples, and then calculate the corresponding PDFs, for a GGX distribution.

I've found some of the original papers, but unlike Lambert the Sampling and PDF seem based on spherical coordinates (which I don't really understand - 3D Vectors are about the limit of my math).

I would really love to know how to translate "A Simpler and Exact Sampling Routine for the GGX Distribution of Visible Normals" into separate Sample() and PDF() functions.

Here's what I have for Lambert:

type Lambert struct {
    R, G, B float64
}

func (l Lambert) Sample(out, normal geom.Direction, rnd *rand.Rand) geom.Direction {
    return normal.RandHemiCos(rnd)
}

func (l Lambert) PDF(in, normal geom.Direction) float64 {
    return in.Dot(normal) * math.Pi
}

func (l Lambert) Eval(in, out, normal geom.Direction) rgb.Energy {
    return rgb.Energy{l.R, l.G, l.B}.Scaled(math.Pi * in.Dot(normal))
}

And here's my in-progress work for Microfacets:

func (m Microfacet) Sample(out, normal geom.Direction, rnd *rand.Rand) geom.Direction {
    // TODO: better sampling
    return normal.RandHemi(rnd)
}

func (m Microfacet) PDF(in, normal geom.Direction) float64 {
    // TODO: PDF that matches a better sampling distribution
    return 1 / (2 * math.Pi)
}

// https://computergraphics.stackexchange.com/questions/130/trying-to-implement-microfacet-brdf-but-my-result-images-are-wrong
// https://schuttejoe.github.io/post/ggximportancesamplingpart2/
func (m Microfacet) Eval(in, out, normal geom.Direction) rgb.Energy {
    F := schlick2(in, normal, m.F0.Mean())  // The Fresnel function
    D := ggx(in, out, normal, m.Roughness)  // The NDF (Normal Distribution Function)
    G := smithGGX(out, normal, m.Roughness) // The Geometric Shadowing function
    r := (F * D * G) / (4 * normal.Dot(in) * normal.Dot(out))
    return m.F0.Scaled(r)
}

The GGX BSDF relies on several physics functions I've also implemented:

// Schlick's approximation of Fresnel
func schlick2(in, normal geom.Direction, f0 float64) float64 {
    return f0 + (1-f0)*math.Pow(1-normal.Dot(in), 5)
}

// GGX Normal Distribution Function
// http://graphicrants.blogspot.com/2013/08/specular-brdf-reference.html
func ggx(in, out, normal geom.Direction, roughness float64) float64 {
    m := in.Half(out)
    a := roughness * roughness
    nm2 := math.Pow(normal.Dot(m), 2)
    return (a * a) / (math.Pi * math.Pow(nm2*(a*a-1)+1, 2))
}

// Smith geometric shadowing for a GGX distribution
// http://graphicrants.blogspot.com/2013/08/specular-brdf-reference.html
func smithGGX(out, normal geom.Direction, roughness float64) float64 {
    a := roughness * roughness
    nv := normal.Dot(out)
    return (2 * nv) / (nv + math.Sqrt(a*a+(1-a*a)*nv*nv))
}

Through help from several people, & referencing and re-referencing the commented urls, I managed to get a sampling scheme with matching PDF that handles everything from perfect mirror surfaces to roughness = 1. Here's the eventual result:

// Cook-Torrance microfacet model
type Microfacet struct {
    F0        rgb.Energy
    Roughness float64
}

// https://schuttejoe.github.io/post/ggximportancesamplingpart1/
// https://agraphicsguy.wordpress.com/2015/11/01/sampling-microfacet-brdf/
func (m Microfacet) Sample(wo geom.Direction, rnd *rand.Rand) geom.Direction {
    r0 := rnd.Float64()
    r1 := rnd.Float64()
    a := m.Roughness * m.Roughness
    a2 := a * a
    theta := math.Acos(math.Sqrt((1 - r0) / ((a2-1)*r0 + 1)))
    phi := 2 * math.Pi * r1
    x := math.Sin(theta) * math.Cos(phi)
    y := math.Cos(theta)
    z := math.Sin(theta) * math.Sin(phi)
    wm := geom.Vector3{x, y, z}.Unit()
    wi := wo.Reflect2(wm)
    return wi
}

// https://schuttejoe.github.io/post/ggximportancesamplingpart1/
// https://agraphicsguy.wordpress.com/2015/11/01/sampling-microfacet-brdf/
// https://en.wikipedia.org/wiki/List_of_common_coordinate_transformations#From_Cartesian_coordinates_2
func (m Microfacet) PDF(wi, wo geom.Direction) float64 {
    wg := geom.Up
    wm := wo.Half(wi)
    a := m.Roughness * m.Roughness
    a2 := a * a
    cosTheta := wg.Dot(wm)
    exp := (a2-1)*cosTheta*cosTheta + 1
    D := a2 / (math.Pi * exp * exp)
    return (D * wm.Dot(wg)) / (4 * wo.Dot(wm))
}

// http://graphicrants.blogspot.com/2013/08/specular-brdf-reference.html
func (m Microfacet) Eval(wi, wo geom.Direction) rgb.Energy {
    wg := geom.Up
    wm := wo.Half(wi)
    if wi.Y <= 0 || wi.Dot(wm) <= 0 {
        return rgb.Energy{0, 0, 0}
    }
    F := fresnelSchlick(wi, wg, m.F0.Mean()) // The Fresnel function
    D := ggx(wi, wo, wg, m.Roughness)        // The NDF (Normal Distribution Function)
    G := smithGGX(wo, wg, m.Roughness)       // The Geometric Shadowing function
    r := (F * D * G) / (4 * wg.Dot(wi) * wg.Dot(wo))
    return m.F0.Scaled(r)
}


In forward rendering what's the go to technique to smooth out rigid shadow due to low resolution shadowmap texture? I am building my own graphic engine.

My depth texture is significantly smaller than that of the screen.

The low resolution depth map results in rigid shadow like this...

I am sure this is a common issue.

I would like to learn "go to" technique to resolve this issue.

Percentage Closer Filtering with some amount of blur (ie. a minimum filter size in texture space) is the most basic method I know of. For example, see GPU Gems. My experience is that it is also quite robust.


Why does this gl_FragDepth calculation work? I am raytracing in GLSL. My gl_FragDepth calculation wasn't right, so I did some hunting and found this solution (P is the world-space coordinate of the pixel and pv is proj*view):

    vec4 Pclip = pv * vec4 (P, 1);

    float ndc_depth = Pclip.z / Pclip.w;

    gl_FragDepth = (
        (gl_DepthRange.diff * ndc_depth) +
        gl_DepthRange.near + gl_DepthRange.far) / 2.0;

It works. But why?

Okay, so I need to divide by w and scale it to the expected z-range. That makes sense qualitatively, but the calculation surprised me.

If you told me to "divide by w and scale to gl_DepthRange" I would have written

float ndc_depth = Pclip.z / Pclip.w;

gl_FragDepth = gl_DepthRange.diff * ndc_depth + glDepthRange.near;

At this point I'd like to point out that this depth calculation looks correct with the raytraced geometry which is intersecting with my normal triangle models, so I guess OpenGL is performing the same depth-scaling implicitly for those triangles as well.

Three questions:

Why add gl_DepthRange.far to the calculation?
Why divide by 2?
I set the pv matrix in C++ with glm::perspective(...)*glm::lookAt(...) so how the hell does gl_DepthRange know what the near and far planes are?

What you are missing is, that in OpenGL's NDC space (i.e. clip space after division by w) all 3 coordinates are in the range $[-1,1]$. So ndc_depth is in the range $[-1,1]$, while your computation assumes a range of $[0,1]$.
So let's take your computation but add an initial step to map $[-1,1]$ to $[0,1]$:
float ndc_depth = Pclip.z / Pclip.w;
float win_depth = (ndc_depth + 1.0) / 2.0;
gl_FragDepth = gl_DepthRange.diff * win_depth + gl_DepthRange.near;

If we do some transformations (and realizing that gl_DepthRange.diff is just convenience for gl_DepthRange.far - gl_DepthRange.near), we get
gl_FragDepth = gl_DepthRange.diff * (ndc_depth + 1.0) / 2.0 + gl_DepthRange.near;

gl_FragDepth = (gl_DepthRange.diff * ndc_depth + gl_DepthRange.diff) / 2.0
               + gl_DepthRange.near;

gl_FragDepth = (gl_DepthRange.diff * ndc_depth + gl_DepthRange.diff +
                2.0 * gl_DepthRange.near) / 2.0;

gl_FragDepth = (gl_DepthRange.diff * ndc_depth +
                gl_DepthRange.far - gl_DepthRange.near + 2.0 * gl_DepthRange.near) / 2.0;

gl_FragDepth = (gl_DepthRange.diff * ndc_depth +
                gl_DepthRange.far + gl_DepthRange.near) / 2.0;

So, to answer your specfic questions:

That's just a result from simplifying the calculation based on the fact that gl_DepthRange.diff is nothing else than gl_DepthRange.far - gl_DepthRange.near.

Because the depth range in NDC space is $[-1,1]$, which has a width of $2$.

It doesn't. These values have nothing to do with the near and far values you used to construct your projection matrix, in fact you could use any arbitrary projection matrix (or none at all). They are the depth range values set with glDepthRange, which have a totally different meaning (okay, let's say slightly different but related).
Basically, and special situations notwithstanding, the projection matrix defines where you near and far clipping planes are in eye-space, i.e. which eye-space range is mapped to the $[-1,1]$ NDC depth range. Then the depth range defines what these NDC near/far values of -1 and 1 are mapped to in the actual depth buffer. So the names "near"/"far" do relate to the near and far clipping planes. But both transformations are basically independent of each other, using the general NDC (i.e. the normalized device space) as a mediator between both stages. This way glDepthRange more or less just extends what glViewport does onto the z-dimension.


What is Illustrator's vector rasterization process? I am currently trying to understand a few things about vector graphics rasterization and the different ways it is implemented in various application types.

I tested and compared a few programs and noticed that there is a major difference in the way anti-aliasing behaves in the rasterization process. I am especially interested in the rendering behavior in Illustrator. You will see why by reading further.

For my testing, I used a really simple composition of triangles organized in an irregular hexagon with different colors.

Vector graphics softwares

Here are three renders of the same vector graphic in Illustrator, Affinity and Inkscape. (The image produced in Affinity and Inkscape are exactly the same.)

As you can see there is an undesired white line on each of the edges in the image rendered with Affinity and Inkscape. The anti-aliasing does not fill this area with a solid color which results in a small gap between adjacent shapes.

Although there is no gap in the Illustrator render, the edges of the shapes look as smooth as the Affinity render.

Here is an image showing the same area of each image upscaled.

There is a very subtle difference between the two images. The Affinity render is a tiny bit smoother but it is almost impossible to see the difference when looking at the images in their original sizes.

Browsers

SVG rendering

Displaying the same graphics exported as SVG in a browser looks very similar to the raster image produced by both Affinity and Inkscape.

There are very tiny differences in edges anti-aliasing (that are not really worth showing here) but SVG rasterization in common browsers behaves pretty much the same.

Decomposed render

Testing Illustrator rendering a bit further, I tried splitting parts of my graphics and exporting them individually then composing them back together with a raster editing software.

In theory it would result in the same image as having it in a single piece, but the result is slightly different using this method.

As shown, when the two parts are composed, there is a tiny gap between them. Though it is more subtle, it is very similar to the graphic rendered in Affinity.

Polygon rendering

Blender (3D software)

Blender allows you to import SVG files and manipulate them as curve objects. Here is the imported graphic shown in the 3D viewport. (By default material will be affected by lights in the scene. Checking the shadeless property in the material property panel will allow the shapes to be rendered with their original colors.)

Here is a render made of the SVG inside Blender.

It does not have any gap between the triangles. Other 3D softwares are very likely to work the same way. So Blender behaves just like Illustrator, or does it? Maybe it is the other way around?

The real questions

Which vector drawing library does Illustrator use behind the scenes?
Could it be possible that Illustrator makes use of a sort of 3D rendering engine? Is it open source? (probably not?)
Can any of the well known vector drawing libraries such as Cairo and Skia achieve the same rendering behavior? (No gap between shapes)
Is there any less known vector drawing library out there that has the same behavior?

As as far as I can tell Illustrator has 2 or 3 different rasterizer. The onscreen preview is also prone to the same gap artifacting as your show though its tuned to minimize the effect. Your post seems to imply that your interested in the "art optimized" output.

Image 1: The different render modes of illustrator. Art optimized on left and hinted on right. Note that hinted shows slight background through. I dont have the new CC version so i can not show the third.

How does art optimized work then

Art optimized render mode is simply a un-antialiased image rendered at higher resolution, that has then been subjected to a box filtering. This is called super sampling which is costly. A box filter is simply the mean value of the samples in the box (pixel). This is indeed a similar technology as what the multi pixel filter used in your blender render uses. You can do the same thing manually and get same results.

In fact the render you get form illustrator is not really good. Its rendered in nonlinear space and not corrected for and you can get better results by swapping to higher order filters and computing in linear color space. All multi sample methods exhibit the same correct rendering (given enough samples even mathematically correct).

Image 2: Multi pixel filtering, on left illustrator native 'Art Optimized'. On right same image at 16x16 pixels with multi lobed Lanczos filter in linear space. Make sure your zoom is 1:1.

The problem

You have in fact come at terms with the real problem of current generation of onscreen renderers. They try to avoid multi sampling in favor for coverage calculation. But it simply can not work perfectly! Simply because alpha blend is:

$$c_0= c_1*\alpha + c_2*(1-\alpha)$$

When chained never reaches 0 when chained over semitransparent surfaces so background show trough. Also it does not know how the coverage is distributed so it will do it wrong. There's simply no way around this in a non-overlapping case like this. but if you allow the shapes overlap then the coverage calculation can be solved (See here).

Other questions You can get same result in any other engine by just simply multisampling a non-antialiased image. You can not get the effect in on screen renderings without doing the overlap trick because they optimize for speed. Does illustrator use 3D? New CC might depends on your interpretation of what 3D is. This issue has nothing to do with 3D just about signal reconstruction methods so its not applicable to the question really.

Related post how-do-i-accurately-compute-coverage-of-overlapping-analytical-curves


Triangulated model rasterization: light-weight Python library I have a 3D model, which consists of ~50 thousand vertices and 100 thousand triangles. Format is: there's array of vertices' coordinates and array of triangles, which has numbers of vertices (e.g., [1, 2, 5] -- triangle, which consists of first, second and fifth vertex from vertices' array).

I calculate color of each triangle and rotate the model by myself.
Also I "render" it manually, putting vertices as pixels on PIL image, but matrix with colors is enough for my purpose (I need only the matrix).

I don't know, whether I will implement robust and correct rendering function, but I cannot find light-weight library as well.
All I need is to display the set of triangles with specified colors and  background image fast (far less than for a second).

I've found VTK library and used bindings to Python  3 available from different Anaconda organizations: anaconda itself, conda-forge, clinicalgraphics and menpo.
Also it can be compiled from sources.

Works fast (I've rendered a mesh with half a million vertices without any problems) and easier in use than low-level OpenGL shaders with GLUT.

menpo has its own wrapper for VTK and mayavi called menpo3d.
I have not tried it yet, but examples look very simple.


Way to estimate the amount of overlap between a rectangular prism and a frustum? I am looking for some way to estimate the amount of overlap between a rectangular prism(not axis aligned) and a frustum. The rectangular prism is probably always going to be larger than the frustum itself. Basically if the prism overlaps the frustum completely the overlap function should output 1, and if the prism is completely outside the frustum it should output 0. And hopefully if it partially overlaps it outputs a value between 0-1 that is the amount of overlap. It doesn't need to be a perfect estimate I think, but it should get close and should be correct for cases where its completely overlapping or completely separate.
This will be used to voxelize the prism into a view frustum aligned 3D texture, where each entry in the 3D texture is a small frustum itself.
Any ideas?

The typical prism/obb/aabb is made up of 6 planes, and the frustum is also typically made up of 6 planes.
To generate a new volume that is the intersection of the two original volumes, use plane clipping to clip one against the other. This technique is generic enough that it can be used with any object like a mesh.
That is take all the planes from the frustum then clip them one by one against the prism. After each clip operation, the new volume becomes the input to the next clipping operation.
What is left will be the clipped volume representing the intersection of the two. Compute the volume of the new shape and divide it by the original volume and you will get a value that is somewhere between [0,1].
This technique is often used to generate decals in games (though the volume computation is not done). Searching the web for decal generation alogorithms/tutorials should help you with the implementation details.
And if you have specific questions I am happy to add more details to this answer.


Skeletal animation: What is the purpose of multiplying interpolated bone matrix with parent's matrix? Let's say I have the following hierarchy:

Bone A
    Bone B
        Bone C

Here's how most tutorial is telling me how to calculate the finalMatrix to be sent to shader.

bonePoseToWorldPose(Joint * joint, glm::mat4 & parentTransform, glm::mat4 & globalInverseTransform) {
    joint->finalTransform = parentTransform * joint->localTransform; // local transform is the result of interpolating 2 keyframes
    for (int i = 0; i < joint->children.size(); i++) {
        bonePoseToWorldPose(joint->children[i], joint->finalTransform, globalInverseTransform);
    }
    joint->finalTransform = joint->finalTransform * joint->inverseBindTransform;
}

Doing it this way, the final transform in bone C for example, would be localTransformA * localTransformB * localTransformC * jointInverseBindTransform.

Which does not make sense to me, and none of the tutorial satisfactorily explains that. Let's go back to the example again. the inverse bind transform would bring a vertex V from mesh space to bone space of Bone C. At bone space C, it would be multiplied with the localTransformC (or interpolated transform C), which I guess would set the model to our desired pose. But what are A and B doing there?

The bone transforms are relative to their parent in the hierarchy. That's the point of the hierarchy, i.e. when you move your arm, your hand and fingers go along with it. So when an animation (or whatever) changes the transform of A, then bones B and C are supposed to move along with it.

This is accomplished by defining bone B relative to A, and C relative to B, and so on.

Therefore, to get the final transform from bone local space to world space, you have to combine all the transforms from the current bone up the hierarchy to the root.

To put it another way:

The localTransform of C takes you to B's local space.
Then the localTransform of B takes you to A's local space.
Then the localTransform of A takes you to world space (since A is the root).


Perspective Raytracing Given the up and focal vector of the perspective camera, the position of the camera and the vertical and horizontal opening angle of the FOV. How can I calculate a ray for given screen space coordinates (x, y) where x, y are between -1 and 1 (inclusive).
I tried this:

1) Calculate the vectors sx, sy that span the image plane

sy = -norm(up)

sx = norm(cross(focal, sy))

2) Calculate the focal length f

f = 1 * sin(90 - vertical) / sin(vertical)

3) Create the ray

dir = (center + x * sx + y * sy + f * forward) - center

r(t) = center + t * norm(dir)

But the resulting image does not turn out like the reference image. Someone know what I am doing wrong?

Let the horizontal FOV be given as theta (in radians), and the vertical FOV be given as phi (in radians). The we know that:

$$\tan\frac{\theta}{2}=\frac{w}{f}, \tan\frac{\phi}{2}=\frac{h}{f}$$

Let us pick $f = 1$, then $w = \tan\frac{\theta}{2}, h = \tan\frac{\phi}{2}$. Now your ray generation direction generation formula looks like:

$$\pmb{d} = x w\pmb{u} + yh\pmb{v} + \pmb{w}$$

Where $\pmb{u},\pmb{v}, \pmb{w}$ are your sx,sy, forward vectors. Essentially, I found the extent of the smallest/largest x and y respectively ($1w = w, -1w=-w$, etc.). You can premultiply $\pmb{u}, \pmb{v}$ with $w, h$ respectively, if you don't want to perform the multiplication per ray.


BRDF sampling and evaluation of diffuse vs specular component When I am sampling diffuse BRDF I am using cosine-weighted distribution and when I want to sample specular BRDF I use sampling by GGX distribution. I can decide how much light is reflected and how much is diffused by using Fresnel. That gives me an evaluation formula like this:

Eval = BRDF_specular * F + BRDF_diffuse * (1 - F)

the same principle I can use on PDF. But the problem comes up when I try to use this on sampling. It is obvious that I cannot use this interpolation for the sampled vector. But what I can do is to have some probability that I will sample specular direction and probability for sampling diffuse direction. As sample count goes up it will perform as if it was interpolation between these types of sampling. I can use this for dielectric materials because their Fresnel value is the same for RGB. But because I am using separate values for RGB for Fresnel on metallic material I can have different probabilities (for example, R = 0.8, G = 0.3, B = 0.0). This gives a nice look to metals as you can see in this post. What probability I should choose then? The biggest?? Average? Or is this some different approach to this problem, because I cannot find anywhere how to combine these BRDFs?

So I found a solution on a shader toy.

I choose randomly from sampling diffuse or sampling specular with distribution 50:50. But I calculate PDF of both and average then. If you want to use a different proportion between sample function you just have to make sure that PDFs are combined with the same proportion as choose.


Additive blending with weighted-blended order independent transparency I am trying to retrofit weighted blended OIT to my rendering pipeline and while it works well, producing convincing results, for normal alpha blending (based on the OVER) operator, I am struggling to make it support additive blending (for example Colour1 + Colour2 + Background Colour) correctly using the blending formula:

$$ \frac{C_1 w_1 + C_2 w_2}{\alpha_1 w_1 + \alpha_2 w_2} \cdot \bigl(1 - (1 - \alpha_1)(1 - \alpha_2)\bigr) + \text{Bg} \cdot (1 - \alpha_1)(1 - \alpha_2) $$

I could hack it outputting weight values of 1 and very low alphas (eg 0.01), which would make it to sort of converge to additive blending, trouble is, this does not weight the colours at all and does not blend nicely with normal alpha blending.

I was wondering how people have tackled this problem.

I have worked with this specific formula for the OVER operator but not with additive blending. I'll use the paper's nomenclature in the following discussion:

$$ C_f = \frac{\sum_{i=1}^{n}C_i \cdot w(z_i, \alpha_i)}{\sum_{i=1}^{n}\alpha_i \cdot w(z_i, \alpha_i)}(1 - \prod_{i=1}^{n}(1 - \alpha_i)) +  C_0\prod_{i=1}^{n}(1 - \alpha_i) $$

This is not explicitly stated in the paper, but the term $$C_i$$ is the premultiplied-alpha color (i.e. color.rgb * color.a)

As described in the paper, the term
$$ C_0\prod_{i=1}^{n}(1 - \alpha_i) $$
provides the "revealage" of the background color. If all the transparent surfaces are transparent, the product will be 1 and the background will be fully visible. The rest of the equation provides an approximation of the result of sorting the transparent surfaces by distance and using the OVER operator with pre-multiplied alpha colors.

However, the equation for additive blending (using glBlendFunc(GL_SRC_ALPHA, GL_ONE) and glBlendEquation(GL_FUNC_ADD)) without weights is:
$$ C_f = \sum_{i=1}^{n}\alpha_iRGB_i + C_0 $$

This equation is already order independent! In order to add weights to the transparent surfaces with a normalization step in the end, the equation can then be simplified to:

$$ C_f = \frac{\sum_{i=1}^{n}C_i \cdot w(z_i, \alpha_i)}{\sum_{i=1}^{n}w(z_i, \alpha_i)} +  C_0 $$

If you'd rather keep the same equation as before, you can achieve the same result by changing the shader outputs in listing 3 to:

gl_FragData[0] = vec4(Ci, 1) * w(zi, ai);
gl_FragData[1] = vec4(0);


Render Duplicate Miniature Scene Replica Context
I am working on project for implementing and user test a World-in-Miniature (WIM) interface for VR. A WIM essentially is a replica of the scene the user is currently in, but in miniature.
Features

the user can have control over the WIMs position, orientation, scale. Thus, allowing to dynamically view the scene from multiple viewpoints.
the user can choose from different methods to remove geometry from the scene, particularly to remove occluders such as wall of building floor, to view the objects in the room.
the user can interact with certain objects objects in the scene, by simply interacting with the proxy objects in the WIM replica.

Question
What I am interested in is a way to take a scene of relatively complex geometry and automatically render a miniature replica of it for example in a small rectangle in from of the user (i.e sort of like a 3D map). It would have to be real-time, and performed during run-time, as the viewpoint of the user towards the WIM will change during interaction (e.g. if he for example rotates, or scales up, or down the current rendered selection).
Examples

Original Paper: https://www.youtube.com/watch?v=Ytc3ix-He4E
An example I found running on an Oculus: https://www.youtube.com/watch?v=zOTx_CWsR7g&t=105s

The first thing that jumped into my head when I saw this was Multiview. You are probably already using it to render the scene if you are rendering to VR anyway. (if not...you should)
For those that don't know about Multiview:
This is a way to cast the same draw calls to multiple layers of a framebuffer image with a single draw call. It allows you to use a mask for which layers to broadcast to, so it is easy to turn broadcasting on and off (making it quick and easy to turn the WIM on and off). A new variable is available in shaders that allows the code to make adjustments for the view/projection matrix usually but the code can get much more sophisticated as needed. Its only downside is it requires relatively modern hardware.
Using multiview the cpu would set up 4 view matrices, two for the VR left and right eye, and two for the WIM left and right eye. The view could then add a constant scale factor so the WIM is sized to fit, and the camera can be positioned as needed.
To improve performance you will probably want to break it up into multiple passes where one pass renders everything that is common to both scenes and the second pass renders more expensive effects for the main scene. Again, as needed.
The last step would be merging the two scenes, probably just by bliting the WIM over the main scene using a unique background color of the WIM as a clear alpha color.
I won't go into the details of implementing multivew but googling multiview for the API you are using should give some good tutorials.
Scene interaction is simplified since the CPU only really ever works with a single scene and the only tricky part is figuring out whether the user is interacting with the WIM or the main scene. This would effect how the ray is being cast into the scene (if you use ray casting for selecting objects).
I just noticed that multiview is a opengl/vulkanism I'm not sure what the directx equivalent is.


Shader cannot move texture x, y location Crossposted https://forum.openframeworks.cc/t/shader-cannot-move-texture-x-y-location/29395
Hello I am trying to move the x y location of the texture using this code but it doest not work.

//Fragment shader
#version 120
#extension GL_ARB_texture_rectangle : enable
#extension GL_EXT_gpu_shader4 : enable

uniform sampler2DRect texture0;

void main(){
    //Getting coordinates of the current pixel in texture
    vec2 pos = gl_TexCoord[0].xy;

    // pos.x = (pos.x/0.5); //working
    pos.x += 0.2 //<-- not working how to fixed this?

    //Getting the pixel color from the texture texture0 in pos
    vec4 color = texture2DRect(texture0, pos);

    //Changing the color - invert red, green, blue components
    //color.r = 1.0 - color.r;
    color.g = 1.0 - color.g; //working..
    //color.b = 1.0 - color.b;

    //Output the color of shader
    gl_FragColor = color;
}

//Vertex shader
#version 120
#extension GL_ARB_texture_rectangle : enable
#extension GL_EXT_gpu_shader4 : enable

void main() {
    gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex;
    gl_TexCoord[0] = gl_MultiTexCoord0;
    gl_FrontColor = gl_Color;
}

whats wrong with this code?
pos.x += 0.2 //not working how to fixed this?

////////////////////////////////////////////////////////////////////////

I found the solution  pos.x += 0.2 already working but it is not visible.
if I tried bigger number like  pos.x += 100 it is clear that the textures moves.

What you do is shifting the texture coordinates. This will move the texture on your polygon, and depending on your settings it will handle the borders which are now probably wrong. however, this will not move your polygon - if you want to move an entire object, you should not do that within the shader. you do that via modifying your model matrix.

I assume you have a rectangle, and you want to move it by 0.2 along the x axis. Then you would edit the correct element of your model matrix for the rectangle.

//depending on your setup, you may need [0][3] rather than [3][0]
modelMatrix[3][0] += 0.2;
//now upload the matrix to your shader
//the entire object will be moved by 0.2 units

If that is what you wanted, then you need to remove the fragment shader position calculation.

On a sidenote: I had problems with using += in a shader the other day, so it might just be that this doesn't compile. Try using position = position + 0.2; instead.


Writing to a compressed texture using a compute shader, with no extra copies I'm trying to figure out what the best way is to generate an OpenGL texture using a compute shader. So far, I've read that pixel buffer objects are good for non-blocking CPU -> GPU transfers, and that compute shaders are capable of reading and writing buffers regardless of how they're bound. Ideally, I'd like to avoid as many copies as possible. In other words, I'd like to allocate a buffer on the GPU, write compressed texture data to it, and then use that buffer as a texture object in a shader.

Currently, my code looks something like this:

GLuint buffer;
glGenBuffers(1, &buffer);
glBindBuffer(GL_SHADER_STORAGE_BUFFER, buffer);
glBufferStorage(GL_SHADER_STORAGE_BUFFER, tex_size_in_bytes, 0, 0);
glBindBuffer(GL_SHADER_STORAGE_BUFFER, 0);

// Bind buffer to resource in compute shader
// execute compute shader

glBindBuffer(GL_PIXEL_UNPACK_BUFFER, buffer);
glCompressedTexImage2D(GL_TEXTURE_2D, 0, fmt, w, h, 0, tex_size_in_bytes, 0);

Is this correct? I read somewhere about guaranteeing synchronization, too. What do I need to add to make sure that my compute shader completes execution prior to copying from the buffer object?

After looking into this for a while, I found out a couple of things:

You cannot avoid a memcpy: You cannot write directly into texture storage allocated for a compressed texture using only OpenGL API calls. This means that you cannot avoid the call to glCompressedTexImage2D with a bound PBO. That being said, you may be able to use a 16-bit RGBA texture and a GLSL image type in your compute shader.
You do need to synchronize memory: In order to make sure that your compute shader finishes writing to your storage buffer, you must make sure that all reads and writes to it finish. This is done by calling glMemoryBarrier with GL_SHADER_STORAGE_BARRIER_BIT.

The full code for something that writes into a buffer to be used as a compressed texture looks like this:

GLuint buffer;
glGenBuffers(1, &buffer);
glBindBuffer(GL_SHADER_STORAGE_BUFFER, buffer);
glBufferStorage(GL_SHADER_STORAGE_BUFFER, tex_size_in_bytes, 0, 0);

glUseProgram(compute_shader_prog);
glBindBufferBase(GL_SHADER_STORAGE_BUFFER, compute_shader_bind_point, buffer);
glDispatchCompute(wg_x, wg_y, wg_z);
glMemoryBarrier(GL_SHADER_STORAGE_BUFFER_BIT);

glBindBuffer(GL_PIXEL_UNPACK_BUFFER, buffer);
glCompressedTexImage2D(GL_TEXTURE_2D, 0, fmt, w, h, 0, tex_size_in_bytes, 0);


Line segments overlapping I have implemented line segments intersetion test and at the very same test I want to include the fact that if two line segments overlap each other partially or fully , it will be flagged as no intersection.

Some hint to it would be great to have!

The first step in your existing code calculates the orientations of one line segment relative to each of the two end points of the other line segment, using the cross product. This allows testing whether the other line segment has one end point anticlockwise and the other end point clockwise from the first line segment, indicating that the line on which the first segment lies cuts the other segment.

Rather than writing a new test, you can use these same orientations to test for line segments that overlap (including partial overlap). If both segments lie on the same line, then all four orientations calculated in your first step will be zero, because none of the end points are either clockwise or anticlockwise from the line, since they are on the line. Then it remains only to check whether the two segments on the same line overlap, by checking whether either of them has an end point between the end points of the other segment.


Camera position in vertex shader in the vertex shader I have the vertex position vpos which is in object space and I want to get the vector going from the camera to vpos. Can I just do vpos - cameraPos or do I need to do some matrix multiplication with the model-view inverse because vPos and cameraPos are not in the same space?

Operations between two vectors do not make sense unless both vectors are in the same space. So you must either transform the camera position into object space or transform the object position into camera space. I would suggest the latter, since you already likely have a matrix lying around for doing that for other reasons (lighting, etc).


Determining the 'outer' subpath in a compound SVG path The following four SVG paths render the same (using the default fill-rule="nonzero"):

<path id="cwOccwI" d="M0,0 10,0 10,10zM5,2 8,5 8,2z" transform="translate( 0,0)"/>
<path id="ccwOcwI" d="M0,0 10,10 10,0zM5,2 8,2 8,5z" transform="translate(15,0)"/>
<path id="ccwIcwO" d="M5,2 8,5 8,2zM0,0 10,0 10,10z" transform="translate(30,0)"/>
<path id="cwIccwO" d="M5,2 8,2 8,5zM0,0 10,10 10,0z" transform="translate(45,0)"/>

As hinted at by the IDs, these are combinations of clockwise (cw) and counter-clockwise (ccw) orientations for the outer (O) and inner (I) subpaths, varying the order the subpaths are added.

I'm converting SVG paths to GeoJSON. It requires a single 'positive' subpath that is oriented counter-clockwise, and any/all 'hole' subpaths to be oriented clockwise.

Given an SVG path with subpaths (which I can assume/guarantee will not overlap), how can I determine which subpath(s) are 'positive' paths, and which are 'holes'? As shown above, I cannot rely on the orientation of the points within the path, and I cannot rely on the ordering of sub-paths.

If you can assume the subpaths are non-intersecting (and non-self-intersecting), and that the fill rule is always the nonzero rule, the easiest way is probably to pick the first point on the first subpath, and do a standard point-in-polygon test with the polygons defined by each other subpath. If the point is not inside any other subpath, then this subpath is the outermost one. If the point is inside one other subpath, that one must be the outermost one. If the point is inside more than one other subpath, take the set of subpaths it is inside and repeat the test.

Obviously doing it this way requires that there is only one outermost subpath. It's entirely possible in SVG to have multiple disjoint subpaths in one path, and you didn't say whether this is possible in your source data. If it is possible, then you'll have to test every subpath to find out which other subpath(s) it is inside. Each time you run the point-in-polygon test, you find the subpath you're considering is either an outermost one, or you'll find out which subpath it is inside. If it's inside another path, you don't need to consider it in any further tests. At the end, you have a list of outermost subpaths, each of which has a list of all the subpaths it encloses. You can turn each outermost subpath into a separate GeoJSON polygon.


LWJGL/OpenGL get BufferedImage from texture ID I have got a texture ID and would like to retrieve its data. The data should be stored in a BufferedImage for future use. I am using the LWJGL library in Java, so if there are some library-specific shortcuts I'd like to use them.

My naive approach is to first fill a buffer with the image data and then pass it to the image.

int id = ...;
IntBuffer buff = BufferUtils.createIntBuffer(1024*512*4);
GL11.glBindTexture(GL11.GL_TEXTURE_2D, id);
System.out.println(buff.remaining());
GL11.glGetTexImage(GL11.GL_TEXTURE_2D, 0, GL12.GL_BGRA, GL12.GL_UNSIGNED_INT_8_8_8_8_REV, buff);
System.out.println(buff.remaining());
buff.flip();
buff.rewind();
System.out.println(buff.remaining());
// Somehow create a BufferedImage from buff here

I don't know why, but the first and to buff.remaining() return the same value, indicating that nothing has been written which should not be the case.

To make it a more complete example, let's also consider loading a texture from a BufferedImage as well.

First let's assume:

int texture = glGenTextures();
glBindTexture(GL_TEXTURE_2D, texture);

First we need to load an image. For this we can use ImageIO.read(). Then we put all the pixels from the BufferedImage into a ByteBuffer.

BufferedImage image = ImageIO.read(new File("image.png"));
int width = image.getWidth(), height = image.getHeight();

int[] pixels = new int[width * height];
image.getRGB(0, 0, width, height, pixels, 0, width);

ByteBuffer buffer = BufferUtils.createByteBuffer(width * height * 4); // 4 because RGBA

for(int y = 0; y < height; ++y) {
    for(int x = 0; x < width; ++x) {
        int pixel = pixels[x + y * width];
        buffer.put((byte) ((pixel >> 16) & 0xFF));
        buffer.put((byte) ((pixel >> 8) & 0xFF));
        buffer.put((byte) (pixel & 0xFF));
        buffer.put((byte) ((pixel >> 24) & 0xFF));
    }
}

buffer.flip();

glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, width, height, 0, GL_RGBA, GL_UNSIGNED_BYTE, buffer);

Before we go ahead and call glGetTexImage() lets assume that the only thing we have is the texture name (texture). Thus we consider that we don't know the size or format of the texture. We can get all this by doing:

int format = glGetTexLevelParameteri(GL_TEXTURE_2D, 0, GL_TEXTURE_INTERNAL_FORMAT);
int width = glGetTexLevelParameteri(GL_TEXTURE_2D, 0, GL_TEXTURE_WIDTH);
int height = glGetTexLevelParameteri(GL_TEXTURE_2D, 0, GL_TEXTURE_HEIGHT);

Using that information we again create a ByteBuffer as well as a BufferedImage. Reading the pixels from the ByteBuffer and placing them on the BufferedImage.

int channels = 4;
if (format == GL_RGB)
    channels = 3;

ByteBuffer buffer = BufferUtils.createByteBuffer(width * height * channels);
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);

glGetTexImage(GL_TEXTURE_2D, 0, format, GL_UNSIGNED_BYTE, buffer);

for (int x = 0; x < width; ++x) {
    for (int y = 0; y < height; ++y) {
        int i = (x + y * width) * channels;

        int r = buffer.get(i) & 0xFF;
        int g = buffer.get(i + 1) & 0xFF;
        int b = buffer.get(i + 2) & 0xFF;
        int a = 255;
        if (channels == 4)
            a = buffer.get(i + 3) & 0xFF;

        image.setRGB(x, y, (a << 24) | (r << 16) | (g << 8) | b);
    }
}

Now go ahead and save that BufferedImage to a file.

ImageIO.write(image, "PNG", new File("out.png"));

Last but not least, you can get rid of all those GL11. prefixes, by statically importing GL11. You do that by doing:

import static org.lwjgl.opengl.GL11.*;


Is doing multiple Gaussian blurs the same as doing one larger blur? To make Gaussian blurring a 2d image faster, I know that you can do one axis and then the other.

I'm wondering though, if I did two Gaussian blurs of size $N$, would that be the same mathematically as doing one Gaussian blur of size $2N$?

If I did two Gaussian blurs of size N, would that be the same mathematically as doing one Gaussian blur of size 2N?

Almost. Applying two Gaussian blurs is equivalent to doing one Gaussian blur, but with a slightly different size calculation.

Applying a Gaussian blur to an image means doing a convolution of the Gaussian with the image. Convolution is associative: Applying two Gaussian blurs to an image is equivalent to convolving the two Gaussians with each other, and convolving the resulting function with the image.

As it happens, the convolution of two Gaussians with each other is another Gaussian, whose variance is the sum of variances of the two original Gaussians. A Gaussian of N pixel width has variance $N^2$; applying it twice is equivalent to a Gaussian with variance $2\cdot N^2$, which corresponds to a width of $\sqrt{2}\cdot N$ pixels.

In the same vein, applying a Gaussian of width $2\cdot N$ is equivalent to applying a Gaussian of width $N$ four times.


Why do T-junctions in meshes result in cracks? I have heard from many sources that having T-junctions in 3D meshes is a bad idea because it could result in cracks during rendering. Can someone explain why that happens, and what one can do to avoid them?

lhf's answer is good from the perspective of tessellation, but these can occur with simpler triangle mesh use cases.

Take this trivial example of three, screen-space triangles, ABC, ADE and DBE...

Although point E was, mathematically, intended to be exactly on the line segment AB, the pipeline won't be using fully precise values, such as rational numbers (e.g. https://gmplib.org/). Instead, it will likely be using floats, and so some approximation/error will be introduced. The result is probably going to be something like:

Note that all of the vertices may have inaccuracies. Although the example above shows a crack, the T-junction may instead result in overlap along the edge causing pixels to be drawn twice. This might not seem as bad, but it can cause problems with transparency or stencil operations.

You might then think that with floating-point the error introduced will be insignificant, but in a renderer, the screen-space vertex (X,Y) values are nearly always represented by fixed-point numbers and so the displacement from the ideal location will usually be much greater. Further, as the rendering hardware "interpolates" the line segment pixel-by-pixel with its own internal precision, there is even more chance it will diverge from the rounded location of E.

If the T-junction is "removed" by, say, also dividing triangle ABC into two, i.e. AEC and EBC, the problem will go away as the shifts introduced by the errors will all be consistent.

Now, you might ask why do renderers (especially HW) use fixed-point maths for the vertex XY coordinates? Why don't they use floating-point in order to reduce the problem? Although some did (e.g. Sega's Dreamcast) it can lead to another problem where the triangle set-up maths becomes catastrophically inaccurate, particularly for long-thin triangles, and they change size in unpleasant ways.


how many watts are in the SPD of the color white? Please help. I'm trying to implement a ray tracer, going by the PBRT book and got stuck on an issue that I fail to find the answer to. My scenes are made from objects and light sources. From that, I can get the spectral power distribution(SPD) of radiance for each pixel (in watts per steradian per meter squared per meter of wavelength). The problem is, how to correctly convert them to RGB color values? It appears that I should first get the XYZ color, and then convert to RGB. But how do you go from an SPD to the XYZ color? I could just integrate the SPD with the xyz-color-mathing-functions, but they work with "relative power distributions", and I have absolute. The problem is with this scaling that needs to be done. So, if my understanding is correct so far, then the question is, how should I scale my SPDs so that the final image is correct and the XYZ values don't fly far out of the 0..1 range?

I'm not an expert in color, and it's possible that my undestanding of the situation is wrong. Does it make sense to ask, what absolute(i.e. not relative) SPD of radiance should the pixel get(watts per steradian per meter cubed), so that its RGB value is exactly white (1, 1, 1) ?

There is no unique answer or approach and it's not simple either. I'm afraid that once you know the absolute spectral distribution of light that falls onto your camera, you've only computed half the story. What happens now depends on what observer you are trying to simulate, and to what accuracy.

I can highly recommend Moving Frostbite to Physically Based Rendering 3.0 from SIGGRAPH 2014. It contains many details especially section 4.3 and 5.1.

If you are trying to simulate a camera you need to answer some other questions for yourself:

What ISO am I simulating?
What is my shutter speed?
What is my aperture?

With the answers to that you can correct how much light falls onto your sensor and how sensitive it is to that light. Perhaps you don't have to correct for aperture if you already simulate this for depth-of-field.

Then knowing that you need to know how that sensor responds to light of different wavelengths. Perhaps you can find some spectral responsitivity diagrams for the camera sensor you are interested in simulating? Then you can divide by integrate for each sensor type (R, G, B) to get RAW exposure, which still needs processing to turn into sRGB (which involves choosing a whitepoint). It's not simple.

  I'm not an expert in color, and it's possible that my undestanding of the situation is wrong. Does it make sense to ask, what absolute(i.e. not relative) SPD of radiance should the pixel get(watts per steradian per meter cubed), so that its RGB value is exactly white (1, 1, 1) ?

Absolutely not. If you are indoors and look at a piece of paper, that is white, right? Now if you move outdoors, a much greater amount of light hits your eye, yet you still view it as white.

Assuming you view your image on a monitor, there's a lot of color spaces involved: the absolute spectral distribution, the camera, the stored image, the monitor used to display the image and your eyes. They all have different ideas of what 'white' means, and they all have different settings to tweak it: brightness, whitepoint, exposure, viewing conditions, etc.


"Importance Sampling of Many Lights with Adaptive Tree Splitting" - paper: participating media I'm reading and implementing a paper about Importance Sampling of Many Lights with Adaptive Tree Splitting. In section 5.2 on cluster importance for participating media, there is a part that I don't understand: How do they compute the vectors o1, o2? I don't understand the paragraph explaining how to obtain this basis from v1, v2. Can anyone explain it?

Someone else feel free to correct me as I am not 100% certain, but from what I can gather:
They are describing all the normalized vectors v, which point at the ray between points v1 and v2.
They are doing this using one parameter angle φ.
They are essentially interpolating between two vectors o1 and o2, with the equation v = o1 cosφ + o2 sinφ
o1 is simply the normalized v1. o2 is a vector at right angles with the o1 along the plane of the ray. (I think this would be calculated by cross product of o1 and N from the paper).
Because this angle can sweep greater than the length of the ray defined by v1 and v2 they also define a limit Bmax so that φ always stays within the bounds of the ray.
I've tried to annotate the diagram below (but I think I made a mistake and o2 would have an angle create than v1).

They also discuss it briefly here: http://www.aconty.com/pdf/importance-sampling-lights-slides.pdf
Might be worth mesaging the orinal authors to see if this is correct.


How to decompose projection matrix? I want to decompose projection matrices into near, far, top, bottom, left and right values to create a bounding box for view frustum. I used the formula described in  this site Decompose the OpenGL projection matrix. This formula works for perspective which is created with frustum function (glFrustum). But it does not work for perspective which is created via perspective func (gluPerspective)

Frustum and perspective may create same perspective effect but generated matrices seems different. So it seems I can't use single formula to extract perspective parameters.

Is there any proof of that decomposition formula, or does it always work?
How do I decompose the matrix generated by perspective function into near, far, top, bottom, left and right values? Is there any formula which is already used in industry?

My implementations of ortho, frustum and perspetive is here: https://github.com/recp/cglm/blob/master/include/cglm/cam.h

Do you have any "input data" from which you constructed the matrix (like fov, near plane distance, etc.)? Or is the matrix itself the only data you have?

EDIT:
Ok, so if you want to know the size of the near plane while you have viewProj matrix available do this:

a) compute viewProj^-1

b) vertices of the near plane in clip-space have coordinates (in OpenGL):
(-1, -1, -1, 1)
(-1,  1, -1, 1)
( 1, -1, -1, 1)
( 1,  1, -1, 1)

and on the far plane:
(-1, -1, 1, 1)
(-1,  1, 1, 1)
( 1, -1, 1, 1)
( 1,  1, 1, 1)

It's a unit cube spanning (-1, -1, -1) and (1, 1, 1) coordinates with w=1

c) take each of those vertices, mutiply by viewProj^-1 and finally divide all resulting components by the w-component. That gives you the frustum's vertices in world space. From this you can easily find world space planes constraining the view frustum or the bounding box or whatever you like.

I think it's not possible to extract left/right/bottom/top/near/far from the matrix directly. But since you can compute the world space coordinates of frustum's corners (as shown above) you can easily find left/right/bottom/top/near/far.


What are the i,j,k components of a 3d mesh on plot.ly (online)? A 3d Mesh on plot.ly online graph maker (https://plot.ly/create/#/) takes 3 mandatory variables (X, Y, Z) and 3 optional variables (I, J, K).
I understand that if I want to draw a cube that I then have to use the IJK-variables, since without them nothing will be drawn.

After some googling I found that with i, j, k you can represent vectors. Though I do not understand how in the following examples they correspond to the XYZ values, so that a cube can be drawn.
There are several examples of cubes and cuboids on plot.ly, all of which share the same i, j, k, values.
f.e.
https://plot.ly/create/?fid=RPlotBot%3A3933#/

https://plot.ly/create/?fid=markope%3A143#/

Taking the first link as an example:

x   y   z       i   j   k
0   0   0       7   3   0
0   1   0       0   4   7
1   1   0       0   1   2
1   0   0       0   2   3
0   0   1       4   5   6
0   1   1       4   6   7
1   1   1       6   5   1
1   0   1       6   2   1
                4   0   5
                0   1   5
                3   6   7
                2   3   6

This will draw a normal cube.
When I try my XYZ-coordinates, however, it will draw following:

My xyz-coordinates are:

x   y   z
25  25  65
25  55  65
55  25  65
55  55  65
25  25  80
25  55  80
55  25  80
55  55  80

How can I calculate the according ijk-values so that I get a cuboid? Any tips or links to resources?

The official tutorial for a 3d mesh on plot.ly online graph maker only mentions the ijk-values, doesn't explain them though.

Most mesh drawing tools use triangles to draw meshes, for technical reasons.

You could simply specify the coordinates of the three vertices of each triangle, but that is a bit wasteful in terms of memory.

What is done in many places is to specify a list of points in space, with their coordinates, and then specify a list of triangles, using indices of the points in the first list.

The exact same thing happens here. The x,y,z parameters form a list of points. The I,j,k parameters indicate triangles, using IDs in the list of points.

Have a look at the function documentation for more details:
https://plot.ly/python/reference/#mesh3d


Path Tracer - sampling dimensions confusion Suppose my path tracer is shooting 64 rays per pixel (in an 8x8 grid). The confusion is, when accounting for Global illumination, should I shoot additional X number of random rays for each of those initial 64 rays? This would equal to shooting 64 * X *number of bounces rays (all sorts of) which is really large. And since I am making the path tracer on GPU memory is surely a concern.

OR I just shoot 1 random ray for indirect illumination. This would mean that the total secondary rays cast for GI would equal 64 per pixel.

The problem here is, all those 64 rays cast per pixel aren't guaranteed to intersect at the same point albeit close enough. If the intersection positions aren't the same then this would mean I am calculating indirect illumination using just 1 sample which is ofcourse very low.

Now this is again for just GI. What about Area light sources? Should I be explicitly sampling X number of rays for Area Light for each of those initial 64 rays?

I think this is what Cook mentioned in his paper on Distributed Ray Tracing. He says

  Rather than adding more rays for each dimension, the existing rays are
  distributed in each dimension according to the values of the
  corresponding parameter. The key is that no extra rays are needed beyond
  those used for oversampling.

I am confused because mostly I have seen algorithms and code snippets following the second approach. Casting X number of rays for GI.

2) Secondly for direct illumination is the light path explicitly calculated or it's taken from the samples created for GI? The former means if I am sampling 1 ray for GI for each of the 64 rays per pixel, then I am also shooting another ray explicitly for the light path. The random sampled ray, if points to the light source I ignore it.

The latter means, I sample only 1 ray, if it doesn't hits the light source that's my GI, and if it hits the light source I accumulate it's color as direct lighting.

Only one path per sample.

If you had 64 bounces per first hit and 64 per second hit and so forth you'd never get an image.

Edit: And that's why you need to sample each pixel so many times (easily more than 1024 samples) in order to get it to converge, ie get rid of the noise.

As per 2) (from comment below) The 64 primary rays will not hit the same object in the same spot so you will have to calculate everything for each sample.


Rays (~1k) intersecting triangle meshes (~100k) with ca. 100 vertices each I am looking for a way to efficiently compute ray-triangle intersections for a large number of rays (~1k) and a large set of triangle-mesh bodies (~100k) with each composed of several hundred faces. My current approach towards optimization consists of

thread parallelism for each ray
pre-select bodies by testing for ray-bounding box intersections
loop over faces of pre-selected bodies to detect ray-triangle intersections using the Möller-Trumbore algorithm.

Not impressed with performance so far. (Admittedly using python). Are there alternative solutions ?

Your procedure could be optimized in two directions:

If your rays are structured you could possibly take advantage of space coherence: if a ray intersects a given triangle, then a nearby rays has high possibility of intersecting the same triangle or an neighboring one. Therefore simple parallelism over the rays may not be optimal, you could at least process them in batches based on adjacency.
If you have adjacency information on the triangles of your meshes, you could possibly exploit it when testing a ray against the mesh: the Möller-Trumbore algorithm can inform you if the intersection point of the ray and the triangle plane lies inside or outside each of the edges, so you may have a hint at which (neighboring) triangle to check next. That said, your meshes are quite small so the extra overhead may not be worth it.


How is Raster and Random Scan Display different? Raster scan display forms an image with pixel whereas a Random scan display works with Geometric primitives, but even a geometric primitve( a line) is made up of pixels so what is the difference?

A raster display draws every pixel on the screen in every frame whether there is something to show or not.

A random scan display activates only those pixel which are occupied by an geometric primitive.

So yes, they both use pixels, but the difference is in how they draw the pixels onto the screen.


When does it make sense to use drawRangeElements I am trying to understand when it makes sense to use the glDrawRangeElements function.

The OpenGL wiki says:

  for optimization purposes, it is useful for implementations to know the range of indexed rendering data

So, as I interpret it, if I had one large buffer (containing say, multiple meshes' data) and I was planning to call glDrawRangeElements if I instead specify the minimum and maximum index values that this call will use, I could achieve a speedup.

Is this a correct use case for glDrawRangeElements?

It seems like I would almost always know the minimum and maximum index values (because I would know ahead of time what I am going to draw) so it seems like glDrawRangeElements should be just a drop in replacement for glDrawElements.

However, this answer implies that glDrawRangeElements might actually be slower.

So, what are the pros and cons of using glDrawRangeElements?

The problem glDrawRangeElements was invented to fix was effectively removed by the advent of vertex buffers.

What glDrawRangeElements allows the implementation to do is to know exactly what range of values will be used as indices for the vertex arrays. Given that knowledge, they can read that range of values into a separate buffer, and then render from that buffer. Without knowing the range of indices, that wouldn't be possible, since an index list could pick from any index.

But that's only useful if you're reading from client memory. Copying that range out of client memory allows you to render asynchronously. You copy out the values you know you need, issue a rendering command with that, and then return to the caller.

If you're reading from buffer objects, this isn't a useful thing to do. And since core OpenGL doesn't even allow you the option of using client memory, the Range commands are no longer useful.


Tetrahedron orientation I am developing a software that needs to interact with a mesh processing program, using tetrahedral meshes, however I am finding difficulties in this.
The program requires all tetrahedrons to have right handed orientation, and this is not the hard part, as given a list of vertices $\{ v_0, v_1, v_2, v_3 \}$, I need to check that
$h := ( \; (v_0 - v_1) \times (v_0 - v_2) \;) \cdot (v_0  - v_3) > 0$
In case $h < 0$, any odd permutation will be correct, as $\{ v_0, v_1, v_3, v_2 \}$.
The problem is that, as they told me, the program requires that all faces are oriented with the right hand rule.
This requirement puzzles me, and I do not understand it completely.
Can anyone point me in the right direction?
Code
class tetrahedron:
    def __init__(self, vertices):
        # compute handedness
        c = numpy.cross(vertices[0].coords-vertices[1].coords, vertices[0].coords-vertices[2].coords)
        h = numpy.inner( c, vertices[0].coords-vertices[3].coords )

        # vertex indices with correct right-handed orientation
        if h > 0:
            self.vertices = vertices
        else:
            s = "old h = %f" % (h)
            # swap last two vertices
            self.vertices = [vertices[0], vertices[1], vertices[3], vertices[2]]
            vertices = self.vertices
            c = numpy.cross(vertices[0].coords-vertices[1].coords, vertices[0].coords-vertices[2].coords)
            h = numpy.inner( c, vertices[0].coords-vertices[3].coords )
            s = s + " new h = %f" % (h)
            print(s)

Updated Code
I have updated my code according to the suggestions, but apparently faces are still a problem, the error it gives is
Two elements connect to the same side of the shared element face. Coordinates: 12.3669, -61.573, 81.0725

My code is now as follows:
import numpy

def handedness(vertices):
    c = numpy.cross(vertices[1].coords-vertices[0].coords, \
                    vertices[2].coords-vertices[0].coords)
    h = numpy.inner( c, vertices[3].coords-vertices[0].coords )
    return h

class tetrahedron:
    def __init__(self, vertices):
        h = handedness(vertices)

        if h > 0:
            self.vertices = vertices
        else:
            s = "old h = %f" % (h)
            # swap last two vertices
            self.vertices = [vertices[0], vertices[1], vertices[3], vertices[2]]
            vertices = self.vertices
            h = handedness(self.vertices)
            s = s + " new h = %f" % (h)
            print(s)

This refers to the order of vertices within a face. Typically in 3D graphics, faces are wound counterclockwise, so that if you're looking from outside of the tetrahedron/mesh, all the front faces will have their vertices in counterclockwise order. (See here and here for more explanation.) This is a "right-hand rule" in that if the fingers of your right hand curl in the winding direction of the vertices, then your thumb points toward the outside of the mesh.


how to render colored glass object? I want to know how to deal with the color of object,Should i use diffuse reflection on the surface?

A common interpretation of surfaces for rendering is that of a BSDF (Bidirectional Scattering Distribution Function) made up of a BRDF (R stands for Reflectance) and a BTDF (T stands for Transmittance).

In such a model, the reflectance part is the light that 'bounces' off the surface, and the transmittance part is the light that penetrates the surface.

When modeling the latter there are two common looks that we try to replicate. One is that of pure refraction (light goes through and bends at the surface), and the other is that of diffusion (light bounces around within the surface and is re-emitted (this is commonly called diffuse reflection). What determines which one of these happens is the turbidity of the material, which is analogous to the probability of a light ray changing its path while inside the material.

These two phenomena are opposite ends of a spectrum and therefore there cannot, on real materials, be a blend (e.g. alpha blend) between the two. though one could concieve a model where turbidity of the material is not at either end but somewhere in-between, however that would require taking into account the volume of a 3d model and not only the surfaces (this often called Volume Scatter or Sub Surface Scatter).

Thus, what you are looking for is probably refraction. There are many ways to aproximate it. One such way that will get you the expected color but not the distortion you might want is multiplicative blending.


What kind of anti-aliasing is used in font rasterization? I'm writing my own TrueType font rasterizer as an exercise to improve my knowledge in computer graphics (along with a basic vector graphics engine). At this stage, I have implemented most of the TTF file parsing, decoding glyph outlines, scaling, and scan converting the outlines into a bitmap.
(I'm not doing any font hinting/grid fitting for the time being).

When it comes to anti-aliasing the glyph bitmaps, what process or method is typically used (or best)? So far I have tried two methods. Bilinear filtering and setting the alpha value at the edges according to the pixel coverage of the outline.

Bilinear sampling is too blurry to be effective in font rendering, and using pixel coverage is not continuous enough. Here are some images as reference of a lowercase Arial 'c' being rendered at 24 points:

Raw bitmap with no anti-aliasing:

Bilinear filtering:

Here is the same character rendered at the same size with a library (stb):

And finally, here it is rendered as it would appear on OS X (using CoreText I presume):

I'd be happy with whatever method is used by the stb library for my purposes.

Sean Barrett, the author of the stb libraries, wrote an article on how stb_truetype's rasterization works. It's quite readable.

The article describes two methods of antialiasing, both based on scanline rasterization. In scanline rasterization, you iterate through the lines (rows) of pixels and keep track of which edges from the glyph outline are intersecting the scanline (considered as a mathematical zero-thickness line); then you can identify which pixel-centers are inside the outline by tracking enter/exit intersection points along that line.

You can do horizontal antialiasing by calculating partial pixel coverage, using the position of the intersection points relative to the pixel grid. For example, if you have an entering point at $x = 4.6$ on the current scanline, then pixel index 4 would be set to 60% empty and 40% covered. This sounds somewhat like what you tried to do. However, this doesn't help with vertical antialiasing since the scanline is still considered as a mathematical line with zero thickness. So, the article recommends to just supersample along the vertical axis: that is, process multiple "scanlines" spaced out vertically within each pixel row, and average the results together.

The second method performs both horizontal and vertical antialiasing at once, by evaluating the area of intersection of the glyph outline with each pixel square. It's still based on scanline rasterization, but now treats the scanline as a 1-pixel-tall rectangle and tracks all edges that touch the rectangle. To evaluate pixel coverage, the trapezoidal rule is used to calculate a signed area for each glyph edge—positive or negative depending on the edge's orientation—and these are summed up to give the total coverage area within the pixel square. (There are a lot more implementation details covered in the article, plus you can read the source.) This is somewhat faster and more accurate than the supersampling method, though more difficult to implement.

Finally, it's important to consider whether you want gamma correction when rendering text (as with rendering anything else). Theoretically, the antialiased coverage values shouldn't be used directly as pixel values; they should be treated as an alpha, and used for linear-color-space blending between the background color and text color, followed by conversion to output gamma. However, in practice almost no one seems to do this; we're accustomed to seeing non-gamma-correct text, and screen fonts are designed to look good rendered this way. (Print fonts are another story.) On the other hand, if the text is animated, or rotated or not aligned with the pixel grid for any reason, gamma correction will help it look more consistent regardless of its placement relative to the pixel grid.

So, the choice of whether to apply gamma correction comes down to personal preference and the needs of the application. Either way, you may see artifacts such as the font appearing to get heavier or lighter depending on color and font size.


Does prerendering actually help performance? In PC game development, after loading models, textures, shaders, etc in a loading screen, some games will render the models once to an off screen target to make sure the driver and gpu have done all the work required to keep there from being a hitch the first time the models render.

Does anyone know how much that actually helps? Does it only affect certain cards and drivers?

As far as I know, this sort of thing is mainly about shader compilation. One of the main reasons why a game may experience hitches the first time something renders is that the shaders necessary to render it haven't finished compiling yet, and the driver has to finish that work before the frame can proceed.

A little bit of background. When you write shaders in HLSL, you compile them with Microsoft's HLSL compiler (fxc.exe), which outputs a hardware-independent bytecode. When you call CreateVertexShader etc. in D3D, that bytecode gets passed to the underlying driver, which ultimately compiles it into the machine code for the specific GPU you're running on.

This internal compilation step isn't trivial—it's a full-blown optimizing compiler. So it can take a little while on a complicated shader. Because of this, when you call D3D's CreateVertexShader, the driver doesn't necessarily finish compiling the shader right then and there; it may add it to a queue, then return control to the application. Meanwhile, a background thread (perhaps more than one) consumes the queue and compiles the shaders. (The driver may also have a disk cache of previously-compiled shaders, so that it doesn't have to redo all this work every time the game is launched.)

This background-thread compilation means the main game thread can get on with other work, e.g. loading other data or building a scene graph or what-have-you, so it's generally a win for overall loading times. But the consequence of it is that the shaders may not all be finished compiling when the game starts rendering. Unfortunately, there is no way with DX11 and earlier APIs for the app to tell when the shaders are done. The best you can do is to render something with the shader—this effectively makes the app wait for the compiler to finish. That's why games sometimes do this offscreen pre-rendering business.

I don't have any hard numbers handy, but qualitatively, one can reduce the impact of shader compilation by front-loading it during loading. Create all your shaders first, then the compiler will run through those while you load everything else. However, with real-time streaming  (e.g. open-world games) it can still be quite difficult to ensure no hitches.

It's also worth noting that there are some cases where state changes can cause a shader recompile. Things like vertex buffer formats, render target formats, and shader linking details (e.g. re-using the same pixel shader with different vertex shaders, or with tessellation shaders) can potentially cause the driver to have to generate different versions of the shader under the hood. The details vary by vendor and hardware. This isn't necessarily a full from-scratch recompile—often it's just sticking on some prologue or epilogue code—but it's something to be aware of.

This is one place where the new APIs (DX12, Metal, and Vulkan) are in a good position to solve the problem. These APIs have "pipeline state" objects where all shader stages and all possibly relevant states are rolled up into a single object, and when you create one of these, the driver has all the information it needs to actually and completely finalize all the shaders. DX12 also makes shader caching explicit. Also, at least for NVIDIA DX12 drivers (I don't know about others), shader compilation is done fully inside the pipeline state creation method, and the app can use multiple threads itself in order to parallelize shader compilation and other work. So, the practice of offscreen pre-rendering to ensure shaders are finalized should no longer be necessary in DX12.


Want to study computer graphics I want to study computer graphics but I don't have a strong foundation in mathematics. I am doing a computer science degree that doesn't cover computer vision, image processing or computer graphics, linear algebra, geometry, trigonometry, calculus etc. It does cover discrete math and other math relating to computer science. I don't meet the requirements for a mathematics degree so I can't pursue a minor in that. I want to know if I can teach myself the math necessary for CG or Would discrete math be adequate enough? Any advice would be nice.

First, graphics is full of linear algebra, so you'll need that whatever you do. If you want to do any research into shaders, or to write a ray-tracer, you'll also need to understand integration and probably some statistics (to understand Monte Carlo integration).

  I want to know if I can teach myself the math necessary for CG

We can't answer that question for you: only you know how good you are at teaching yourself. If you "don't have a strong foundation in mathematics" because you struggled with it at school, you'll probably struggle to learn harder maths with less help than you had before. If it's not like that, and you're generally good at self-study, then now's the time. You'll never have more access to the means of learning than when you're at university. Hang out with your local maths students and pay attention when they talk about work. Find out when they have lectures relevant to you that don't clash with your own lectures, and go to as many as you can. Find out what books they use for their course, and read the same books.

It'll also help to approach any graphics projects you start with the mindset that when you encounter some maths you don't understand, you might need to put the project to one side while you learn what you need to know. You'll probably do this a lot as soon as you get past the "draw the first triangle on the screen" stage.

A counterpoint to this is that there are a lot of tools today that allow designers and artists to make really impressive graphics content without much maths knowledge, such as Unity and Processing. Maybe you can achieve what you want without studying computer graphics as an academic field at all! Try making a Unity game, play around with shaders a bit, and see if it tickles you.


Intuitively understanding conservation of energy for the Lambertian BRDF The Lambertian BRDF is defined as $R / \pi$, where the division by $\pi$ is there to maintain conservation of energy. The derivation is provided here.

The maths makes sense, and I can understand where the BRDF comes from in a mechanical sense. But I'm struggling to understand what it represents; how does division by $\pi$ relate to reflectance within the unit hemisphere?

A perfect Lambert reflector actually reflects light in a cosine distribution - that is, the amount of light per unit area reflected in any given direction $R$ is proportional to $N.R$. The reason the radiance appears constant for all angles is that as the view direction moves away from the normal, the reflected light per unit area decreases, but the surface area per projected beam area (and hence per pixel) increases by the same amount - the cosine factors cancel out.

Given this distribution, to be energy conserving, the probability density for the reflected light in all possible directions cannot sum to more than 1. If you integrate the cosine function over the whole hemisphere around the normal, you get $\pi$, so this is the normalization factor you need.


Why do we multiply vertex from left side in vertex shader with matrices? I have been learning OpenGL 3.3 and I saw this expression:

gl_Position = projection * view * model * vertex

I am confused because I read in some book that if the vector (vertex) is placed on the right side of the matrix then it would be a column vector and to transform this vector you should have a column major matrix.

But glm library follows GLSL right. So I printed the glm::mat4 and it was a row-major matrix.

There is no 100% consensus on what order matrix multiplication should model things, worse the industry is split along this. Some sources use row major and some sources use column major matrices. Great care should be taken to verify which is being used in your source and what is being used by your API!

Some API's go as far as allowing one to multiply vectors on both sides of the matrix. The wisdom is thus in reading your API reference and verifying how it works. Old, fixed pipeline OpenGL and glm, does in fact use column major matrices. While (warning) DirectX had chosen to use row major matrices [source]. Obviously with programmable shaders any application can have any order, even mixed one

Due to fundamental properties of matrices this duality is the same as transposing the matrix. If you transpose the matrix you reverse the order of calculation, as you are now thinking outside in instead of inside out or vice versa.

The moral of the story is that you should always check your assumptions. And just printing out values does not always help as the printing function can screw things up, and memory not aligned the same way. Also simple testing may make you blind to having mixed conventions inside your program. Read what convention is in use! Because, as confusing as having two sources with different  conventions is, it pales in comparasion to a piece of software that mixes the two in the codebase.


Fast and exact Geodesics on meshes, Backtracking confusion The following is an excerpt from a 2005 paper on geodesics on triangular meshes, taken from section 3.5

In this case $p$ is a point on some arbitrary face in a mesh, $p'$ is a point on one of the 3 edges in the triangle and $D(p')$ is the geodesic distance to that point.
I am very confused as to how this minimization is achieved. The paper doesn't go into detail, so I assume it's trivial, but I am not seeing the solution of the top of my head.
Given an arbitrary interval (segment) the shortest point to it is either the orthogonal projection of the point $p$ onto the segment or one of the end points of the segment (depending on where $p$ is located with respect to the segment).
However, this is not necessarily the point that minimizes the expression $||p - p'|| + D(p')$ or in other words, $p'$ is not, in general, the orthogonal projection of $p$ onto the segment.
The only algorithm I have is to naively check epsilon offsets along the segment and picking the shortest one. There has to be a better way than that.
I have drawn a diagram on Geogebra to show the problem:

$\overline{BA}$ is the segment, $C$ is the point we are looking to minimize the distance from. $D$ is the frontier point, which is the orthogonal projection of the Geodesic source (the source point of all geodesics in the mesh), $E$ is the orthogonal projection of $C$ onto $\overline{BA}$. Clearly the optimal point is somewhere between $E$ and $D$ but I don't know how to find it.

The solution I found to this problem is to ALWAYS intersect the edge. In other words the distance to the geodesic source $v$ from a point $p$ is $||v-p'|| + ||p - p'||$ where $p'$ is the intersection of the line $\overline{vp}$ with the current edge. In cases where $p'$ is "behind" $p$ with respect to $v$ we set the distance to the edge to be infinity.
The above seems to work in the simple tests I have generated at minimum.


Finding all possible reflection matrices for a given Wythoff construction As a pet project, I'm trying to build a small app that visualizes 4D polytopes. I want to use the Wythoff Construction method, where the shape is generated kaleidoscopically by the interaction of 4 mirrors using a single movable generator vertex.

I know how to create a reflection matrix from a hypersurface normal, what I am looking for is an simple way to generate all possible matrices generated by the interreflections of the set of mirrors.

The brute force method would be something like:

1: Create the initial set of mirrors and their matrices
2: Reflect each matrix in each of the other mirrors, add to temp list
3: Remove duplicates from temp list
4: Add temp list to master list and remove duplicates
5: Reflect each matrix in temp list through each mirror except its generating mirror
   and add to new temp list
6: Repeat from step 3 with new temp list, continue until no non-duplicates found

This method will work but will involve a huge amount of redundant computation generating, checking, and discarding duplicates, especially in symmetry groups like the 120-cell / 600-cell which contain thousands of permutations. Does anybody know of a more elegant method of creating the full set?

I found an answer in the form of the Todd-Coxeter Algorithm from group theory. This still involves iterating over permutations of the group, and removing duplicates. However, the group can be defined using symbols to represent different sequences of operations, and duplicate-matching performed on these symbols rather than elements of the group itself.

For example, if a pair of mirrors A and B have an angle of (PI/3) then they form a cycle of order 3 (since a reflection through a pair of mirrors equals a rotation through twice the angle between them). So the sequence ABABAB maps any element back onto itself. By constructing a path like this for each pair of mirrors, it's possible to define new elements for each step along a path, then eliminate duplicates either through string-matching operations or by constructing a graph and eliminating equivalent nodes. For large sets, this should be much more efficient than multiplying and comparing matrices directly at each step.


Linear interpolation on Plane (Marching Cubes) Let's assume I have the following cube.

Let's assume the isovalue = 0. I would like to draw the resulting triangles of the isosurface.

I know that first I define which values are inside or outside comparing them to the given isovalue and after that we correspond to a particular list of edges.

After that, we have somehow to linearly interpolate the points.
I have read on an article that using this formula $P = P_1 + \frac{(iso -V_1)(P_2-P_1)}{V_2-V_1}$ we can get the interpolated values.

Can someone demonstrate to me how I can interpolate the points in this case ?

P1 and P2 in this case represent the actual coordinates of the vertices of the cube in your output mesh. These might be the same as the input coordinates of the function you're using, or they might not be, it's entirely up to you how you output them. A simple way to map them would be to just use integer coords, biased by half the resolution of your sample volume - so a mesh spanning 100^3 cubes would have coordinates from -50 to 50 on each axis.

So in the formula you describe, (iso - V1) / (V2 - V1) gives you the amount to interpolate by, and (P2 - P1) is a vector representing a single cube lattice edge along the axis you want.

Let's assume we're using unit sized cubes, +Y is up, and +Z is 'into' the screen.

In your cube above, you will have crossings on the three edges coming from the left-bottom-front corner. On the X and Z edges you will interpolate by 0.25 : (0 - (-1)) / (3 - (-1)) , and on the Y edge you will interpolate by 0.5.

So if the left-bottom-front corner is at the origin, your three mesh vertices will be at
<0.25, 0, 0> ,
<0, 0.5, 0> and
<0, 0, 0.25>.

Apply the same formula to the right-top-back corner and you get <0.5, 1, 1>, <1, 0.5, 1> and <1, 1, 0.5>

The only difference is the left-bottom-front corner values will be P1 and V1 in your formula as it is at the 'negative' end of the edges to be interpolated, and the right-top-back values will be P2 and V2 as it is at the 'positive' end.

Hope that all makes sense.


Fastest way to put a point on the circumference of a circle My goal is to take a point that is inside of a circle with a given radius and put it on the circumference.

Recently I have been normalizing the vector between the point and the center of the circle then multiplying that by the radius.  However I need (if possible) a less computationally expensive method because the distance formula is expensive.

Another thought I had was to use "atan2" to get the angle between the two points and then use sine and cosine multiplied by the radius to get the point on the circumference.

Which method do you think would be faster for the computer to process? Can you think of a faster method.

Details about the simulation
This is an ios application written in swift.

Basically there are a bunch of particles moving around randomly. And the user is putting down fingers. Each finger is a circle with a radius that grows as time goes on. The part that is inneficent is that if the dot is ever inside of any of the circles (attached to touchscreen touches) that it goes on the circumference of the circle.

Before focusing on optimising the individual process of moving a point, consider how many points are being processed this way. This is likely to give a much more significant speed up if it hasn't yet been addressed.

For example, if every point on the screen is being tested against every circle, then most of the points are being checked needlessly.

If instead you divide the screen into a grid, with each grid cell keeping a list of all points currently within it, then each circle only needs to be checked against the points that appear in the grid cells which that circle overlaps. This allows checking a few tens of points, instead of hundreds or thousands.

This is a much bigger speed up than you can hope to achieve by optimising the circumference calculation, and after this you may find that further optimisation is not needed.


How do you implement perspective correct Gouraud shading across a triangle? What's the algorithm for doing so?

I have flat shading working and I have perspective correct texture mapping working.  Is the way your raster Gouraud shading much different from the perspective correct texture mapping?  (Is gouraud shading even supposed to be perspective correct?)

It is my understanding that you interpolate the lighting color/value down the edges, then interpolate across each scanline.  However,  I think I'm stuck on how to properly divide by Z for each pixel to get the correct light/color value for each pixel.

Any algorithm/article/tutorial would be of great help as I've searched everywhere but can only find high level, abstract descriptions of it.

Thanks in advance!

(Is gouraud shading even supposed to be perspective correct?)

Originally, it wouldn't have been perspective correct, but on (hardware) systems these days it will be. FWIW Dreamcast had perspective correct Gouraud shading because, once you are doing perspective correct texturing, it is relatively little additional cost to do Gouraud "correctly".

  I have flat shading working and I have perspective correct texture mapping working. Is the way your raster Gouraud shading much different from the perspective correct texture mapping?

I'm assuming that you've started with homogeneous 'world space' vertices, i.e. something like,

$[x,y,z, 1, u,v, R,G,B]$,

applied a projection matrix to get

$[X_p, Y_p, Z_p, 1, u, v, R, G, B, w]$,

and then, after clipping, divided through by w to obtain screen coordinates

$[X_p/w, Y_p/w, Z_p/w, 1/w, u/w, v/w, R/w,... ]$.

For convenience, let's rename $u/w$ and $v/w$ as $u'$ & $v'$, $1/w$ as $w'$, $R/w$ as $R'$ etc.

To do perspective correct texturing I assume you are linearly interpolating, per pixel, the $u'$, $v'$, and $w'$ values, computing the reciprocal of the interpolated  $w'$ and multiplying that by $u'$ and $v'$ to obtain the per-pixel U & V coordinates.

To do perspective correct Gouraud, simply use the same approach with the interpolated $R'$ , $G'$ and $B'$ values. The most expensive part is typically the division (i.e. reciprocal) but that can be shared with the texturing.


Question about function for color I would like a help to understand the following line of code:
return float3(pow(color.r, 2.2), pow(color.g, 2.2), pow(color.b, 2.2));

I've seen some places calling it gamma correction, but I don't know if it's correct.
If it really is a gamma correction how does it work?

With Correction
I liked the artistic result of this, I will keep it. I asked the question to understand better.

The actual color of a pixel, outputted on a monitor, does not linearly depend on the applied voltage signal for that pixel. For CRT monitors, the actual color is approximately proportional to the applied voltage raised to the power of a so-called gamma value, which depends on the monitor. This gamma value typically lies between 2.2 and 2.5 for CRT monitors. (Hence, the ubiquitous appearances of the magical constant 2.2 in rendering applications.)
$$L_\mathrm{actual} \sim V^\gamma$$
To bypass this gamma value in your computations, you need to gamma correct the computed colors of each pixel before presenting. By raising the computed color to a power of the reciprocal of that same gamma value, the computed color becomes proportional to the actual color.
$$V \sim L_\mathrm{computed}^{1/\gamma} \\
L_\mathrm{actual} \sim L_\mathrm{computed}$$
So in general gamma correction is a technique that adapts the computed colors to the transfer function of the monitor used for outputting. Both CRT and non-CRT monitors each have their own transfer function. This means that the final rendering pass should adapt the computed colors, based on the used monitor, to obtain correct actual colors.
These linear-to-gamma color space conversions seem like unnecessary overhead from a monitor construction point of view. It is physically perfectly possible to construct a CRT monitor with a gamma value of exactly one, ensuring that the computed color is already proportional to the actual color, and eliminating the need for gamma correction.
From a perceptual point of view, removing the need for gamma correction and using a monitor where computed colors are proportional to the corresponding actual colors is actually a bad idea. Typically, actual colors are represented with 8 (or 10) bits for each of the red, green and blue channel. This quantization only supports 256 (or 1024) different colors. Here, a 0 value represents completely black and a 255 (or a 1023) value represents completely white. But what about the intermediate values? If a linear encoding is used (i.e. a gamma value of 1), the majority of values would be perceptually very close to white and a very small minority would be perceptually close to black. By using a gamma encoding (e.g., a gamma value of 2.2), the distribution is perceptually more linear (i.e. equidistant intervals between black and white).


Is there a method to do ray marching style modulus repeat with raytracing? One of the features of ray marching is that you can use modulus to repeat shapes infinitely, like in the image below, which is from https://www.shadertoy.com/view/MsBGW1

I was curious if there exists any technique which allows you to do the same thing with ray tracing instead of ray marching?

One method I do know of is to ray trace a plane from above, and then where you hit the plane, calculate your location on a grid on that plane, and use the relative position in that grid cell as an absolute position to raytrace a scene.  That will repeat the scene across the grid.

However, a problem with that is if your ray doesn't hit anything in the grid cell, and it would then enter another grid cell, this technique won't catch those other shapes without walking the grid cells down the path of the ray until it exits the back side of the grid, which is very ray-marching-esque and iterative.

Does anyone know of a technique that allows you to have ray marching type repetition in ray tracing?

I've tried to figure this out as well, but I don't think there is a solution that is just as performant as tracing one sphere.  Basically you would want to cast one ray to hit a infinite set of repeating spheres with no marching iteration.  That would be awesome but is not possible:  Let me explain.

Ray-tracing is basically finding the analytical solution to this equation:
$$
f(\vec{r(t)}) = 0 \ for \ t
$$

Where $f(\vec{p})$ is the implicit surface function (which gives the distance the given point $\vec{p}$ is from the surface) and $\vec{r(t)}$ is the parametric ray equation ($\vec{r(t)} = \vec{origin} + \vec{direction}*t$).  $t$ would represent the distance along the ray the intersection happens.

In order to ray-trace domain manipulations (like repeating space), these domain manipulations need to be present in the implicit surface function $f(\vec{p})$ while finding an analytical solution.  Let's take a 3D repeating sphere for instance.
$$
f'(\vec{p}) = \|\vec{p}\bmod \vec{d}\| - r
$$
(where $\vec{d}$ is a constant representing the grid size and $r$ is the radius)

In order to solve $f'(\vec{r(t)}) = 0$ for $t$ we would need the inverse of the modulo operator which doesn't really exist : http://mathforum.org/library/drmath/view/51619.html.  That means there is no analytical solution to this equation, but there is a numerical one. Hence Ray-marching.

This is true for a lot of cool distance functions you see on shadertoy.com, the analytical solution does not exist for these surfaces so you cannot ray-trace.


Algorithm for thinning a thick line I'm trying to reduce a thick line, in raster space, down to a thin line, preferably one pixel wide (or thick).
Does anybody know of an algorithm that can do this?
Imagine you draw with a marker on a piece of paper, scribbling here and there.  Then you scan this paper into a grey-scale or black-and-white raster image.  How can I produce another black-and-white image the same size but the lines you drew are very thin instead of thick?
Surely this must be a solved problem, right?

the canny algorithm is a great start.
it takes a sobel input like so.

Computes its gradient. Then depending on the gradient orientation it compares all neighbouring pixels aligned with it. If its a local maximum the pixel remains black otherwise it is set to white.
this article will probably explain it a lot better.
https://towardsdatascience.com/canny-edge-detection-step-by-step-in-python-computer-vision-b49c3a2d8123
Ive tried to implement my own version using the algorithm provided however I'm struggling to port it to glsl as I think the interpolation might be causing an issue.
here is a working one in shatertoy though, just a beginner though so a bit complex for me.
https://www.shadertoy.com/view/wl2cW3