Materials for research on spherical projection I am currently doing a research on projection on a sphere, specifically for NOAA's project Science on a Sphere. What I'm trying to do is to find out how exactly do you create a video material for such a device, because it's not as simple as making a regular video since the projection on the sphere warps the final image a lot etc.

However, I'm struggling with finding any reasonable material source. I only found NOAA's creation guidelines, and even though they do describe all the problems with warping and having a seamless video pretty well, they do not describe specific methods, or the whole process of creating this kind of a video. They only mention several programs and plugins for Adobe's AE, but that's it.

Link: http://sos.noaa.gov/_downloads/docs/sos-content-creation-guidelines.pdf

I can't get any reasonable source from Google either, since all links are directing me to topics related to projecting a sphere (Earth) onto a plane, which is not what I'm trying to find at all.

I decided to give this site a shot and ask you whether you know any source/tutorial that could help me with this issue, or whether is here someone who understands this topic better than I do.

You need to use a cylindrical projection. So the key issue is how to prepare data for a cylindrical projection. Basically what you do is:

You project your data on a sphere, it may be that this process was already done for you.
And then you project it back to a cylinder

Both steps can be easily taken care of by your cartography software. Will the data distort... yes but since you project information onto a sphere from whatever source onto a sphere and to cylindrical coordinates it will just interpolate the distortion away. If anything your just going to have slight over resolution at poles.

Quite a lot of data is in fact in this format to begin with. But nearly all 3D applications can use projected textures and texture baking to do these steps for you. Also most 2D applications like Photoshop have tools for turning rectangular coordinates to polar coordinates which do the same thing

The real question is what your original image data is like?


GDDR5 vs. DDR3 for learning GPU programming on a limited budget? [Please (kindly) let me know if this is not the place for this question]

I'm hoping to learn about GPU programming, but as a college student, I've a quite limited budget.  I'm wondering whether I should buy a modestly more expensive GPU that uses GDDR5 memory, or if DDR3 memory is sufficient.

I can see some potential pros and cons:

GDDR5 is standard in nearly all but the lowest-end GPUs, so I'd be getting experience that would transfer to most popular cards
However, is it possible that learning with DDR3 memory will only help me learn to be more efficient, thus my skills would translate (probably with a bit more difficulty) to even better programming abilities on a higher-end GPU

Any advice or words of wisdom?

Note that I don't want the card for gaming purposes (although I would gladly use it in such a capacity, but that would be a happy by-product of having it around to learn to program on).  I also don't really care too much about being able to run programs faster on the GPU; I mainly want the ability to learn how to program on a GPU.  I'm currently considering only NVIDIA GPUs, as I've learned a smidgen about CUDA programming.

If your goal is to learn GPU programming, it doesn't matter at all whether you have DDR3 or GDDR5 memory. The way you program it isn't going to change based on how fast the memory is. It will affect performance, but if that's not a primary consideration for you, then you don't need to worry about it.

Do make sure that you get a GPU that supports the latest graphics APIs (DX12 and OpenGL 4.5). I think that's essentially all GPUs made in the past 5 years or so.


Calculate Normals of Boolean Operation for Ray Tracer I'm working on a small ray tracing project in my free time and I'm currently implementing boolean operations for spheres.

My code is setup to calculate the intersection points of each of the spheres with any given ray and spit out the correct points to be rendered to the screen based on the type of boolean operation being performed (Union, Difference or Intersection).

I haven't been at it for too long, but so far I have the code for the Intersection running nicely:

v3df and v2df are 3d and 2d float vectors respectively.
s1t and s2t are the intersection points for each of the spheres with a ray.

if(s1t.x == 0 && s1t.y == 0 || s2t.x == 0 && s2t.y == 0)
    return v2df();

if(min(s1t.x, s1t.y) > max(s2t.x, s2t.y) || min(s2t.x, s2t.y) > max(s1t.x, s1t.y))
    return v2df();

std::vector<float> values = { s1t.x, s1t.y, s2t.x, s2t.y };
std::sort(values.begin(), values.end());
v2df res(values[2], values[1]);
return res;

This produces the following output with variable spheres:

Now I would like to implement the normals for said intersection, and my basic idea would be to take the normals of each of the corresponding spheres where their geometry shows, but I'm at a loss for how to implement this.

here's the method stub I would like to use:

v3df GetNormal(v3df point) {
    return v3df();
}

My code is setup to calculate the intersection points of each of the spheres with any given ray and spit out the correct points to be rendered to the screen based on the type of boolean operation being performed (Union, Difference or Intersection).

Then you need to do the exact same thing with the normals. Indeed, you would typically do this operation with all of the appropriate parametric values for the various leaf surfaces.

However, you need to take into account how the operations affect the meaning of the intersections. With positions, an intersection is used to determine if you're inside an object or outside of it. An OR operation (union) makes any intersection of the two objects considered "inside", with "outside" only happening if you're outside of all of them. An AND operation (intersection) only makes the composite object "inside" if you're inside all of the AND'd objects.

A negation reverses the meaning of inside and outside for the object. So an AND with a negation (difference) means that the only part that is inside of the composite object is the part of the first object which is not also inside of the second.

Normals use the same rules as positions, with one exception. When used with a difference operation, if the ray enters the negated object (and thus is still outside of the composite), then enters the primary object (but is still outside of the composite because it's still inside of the negated one), and then leaves the negated object, that intersection represents a visible point.

Except that the normal is backwards, since you're using the inside of the negative surface to define the surface of the composite object.

When you negate a surface, you invert the meaning of its normals. So when you do a difference operation, you have to negate the normals of any intersections with the negative surface.


Is a Lambertian reflector illuminated by a smaller fraction of the incident radiation when it's tilted? In reading about Lambertian reflectance on Wikipedia I found the following phrase (in bold) which doesn't sound right to me:

  In computer graphics, Lambertian reflection is often used as a model for diffuse reflection. This technique causes all closed polygons (such as a triangle within a 3D mesh) to reflect light equally in all directions when rendered. In effect, a point rotated around its normal vector will not change the way it reflects light. However, the point will change the way it reflects light if it is tilted away from its initial normal vector since the area is illuminated by a smaller fraction of the incident radiation.

The way I picture the situation described in the paragraph, only tilting away from the light source would cause  less light to be incident in a given area. In general, tilting away from the initial normal vector could lead to either an increase or a decrease in incident light per area, as this says nothing about the location of the light source.

Have I misunderstood the context, or is this something that should be rewritten on Wikipedia?

I see some problems in the quote you posted.

  In effect, a point rotated around its normal vector will not change
  the way it reflects light.

This is true, because a Lambertian reflector will never change the way it reflects light. The underlying principle stays the same. Also, Lambertian surfaces are isotropic, so the amount of reflected light won't change either (which is probably what this sentence is aiming for).

  However, the point will change the way it reflects light if it is tilted away from its initial normal vector since the area is illuminated by a smaller fraction of the incident radiation.

Again not true, because the principle doesn't change. The amount may change, except for the special case that the cosine is <= 0 before and after the tilting. The amount does not necessarily grow, except if we define that the cosine equals 1 before, i.e. that the normal points directly towards the light source.

This whole paragraph should probably be rewritten to be less ambiguous. Including isotropy could make it more complete.


How many polygons in a scene can modern hardware reach while maintaining realtime, and how to get there? A fairly basic, in some ways, question, but one that many people, myself included, don't really know the answer to. GPU manufacturers often cite extremely high numbers, and the spread between polygon counts that various game engines claim to support often spans multiple orders of magnitude, and then still depends heavily on a lot of variables.

I'm aware that this is a broad, pretty much open-ended question, and I apologize for that, I just thought that it would be a valuable question to have on here nonetheless.

I think it is commonly accepted that real time is everything that is above interactive. And interactive is defined as "responds to input but is not smooth in the fact that the animation seems jaggy".
So real time will depend on the speed of the movements one needs to represent. Cinema projects at 24 FPS and is sufficiently real time for many cases.

Then how many polygons a machine can deal with is easily verifiable by checking for yourself. Just create a little VBO patch as a simple test and a FPS counter, many DirectX or OpenGL samples will give you the perfect test bed for this benchmark.

You'll find if you have a high end graphics card that you can display about 1 million polygons in real time. However, as you said, engines will not claim support so easily because real world scene data will cause a number of performance hogs that are unrelated to polygon count.

You have:

fill rate

texture sampling
ROP output

draw calls
render target switches
buffer updates (uniform or other)
overdraw
shader complexity
pipeline complexity (any feedback used? iterative geometry shading? occlusion?)
synch points with CPU (pixel readback?)
polygon richness

Depending on the weak and strong points of a particular graphic card, one or another of these points is going to be the bottleneck. It's not like you can say for sure "there, that's the one".

EDIT:

I wanted to add that, one cannot use the GFlops spec figure of one specific card and map it linearly to polygon pushing capacity. Because of the fact that polygon treatment has to go through a sequential bottleneck in the graphics pipeline as explained in great detail here:  https://fgiesen.wordpress.com/2011/07/03/a-trip-through-the-graphics-pipeline-2011-part-3/
TLDR: the vertices have to fit into a small cache before primitive assembly which is natively a sequential thing (the vertex buffer order matters).

If you compare the GeForce 7800 (9yr old?) to this year's 980, it seems the number of operations per second it is capable of has increased one thousand fold. But you can bet that it's not going to push polygons a thousand times faster (which would be around 200 billion a second by this simple metric).

EDIT2:

To answer the question "what can one do to optimize an engine", as in "not to lose too much efficiency in state switches and other overheads".
That is a question as old as engines themselves. And is becoming more complex as history progress.

Indeed in real world situation, typical scene data will contain many materials, many textures, many different shaders, many render targets and passes, and many vertex buffers and so on. One engine I worked with worked with the notion of packets:

One packet is what can be rendered with one draw call.
It contains identifiers to:

vertex buffer
index buffer
camera (gives the pass and render target)
material id (gives shader, textures and UBO)
distance to eye
is visible

So the first step of each frame is to run a quick sort on the packet list using a sort function with an operator that gives priority to visibility, then pass, then material, then geometry and finally distance.

Drawing close objects gets prirority to maximize early Z culling.
Passes are fixed steps, so we have no choice but to respect them.
Material is the most expensive thing to state-switch after render targets.

Even in-between different materials IDs, a sub-ordering can been made using a heuristical criterion to diminish the number of shader changes (most expensive within material state-switch operations), and secondly texture binding changes.

After all this ordering, one can apply mega texturing, virtual texturing, and attribute-less rendering (link) if deemed necessary.

About engine API also one common thing is to defer the issuing of the state-setting commands required by the client. If a client requests "set camera 0", it is best to just store this request and if later the client calls "set camera 1" but with no other commands in between, the engine can detect the uselessness of the first command and drop it. This is redundancy elimination, which is possible by using a "fully retained" paradigm. By opposition to "immediate" paradigm, which would be just a wrapper above the native API and issue the commands right as ordered by client code. (example: virtrev)

And finally, with modern hardware, a very expensive (to develop), but potentially highly rewarding step to take is to switch API to metal/mantle/vulkan/DX12-style and preparing the rendering commands by hand.

An engine that prepares rendering commands creates a buffer that holds a "command list" that is overwritten at each frame.

Usually there is a notion of frame "budget", a game can afford. You need to do everything in 16 milliseconds, so you clearly partition GPU time "2 ms for lightpre pass", "4 ms for materials pass", "6 ms for indirect lighting", "4 ms for postprocesses"...


Origin of blurring and colour distortion in monochrome diagrams I am analysing a large number of PDF files from scientific articles, all of which contain images which (I think) were originally monochrome ( black/white).
The images have been extracted with Apache PDFBox and I am doing image processing on *.png.
The images have severe colour distortion, and blurring which I do not think is due to the extraction process or to subpixel antialising (see https://stackoverflow.com/questions/16242731/reconstructing-line-diagrams-from-subpixel-rendering). Note that the effect is present on both lines and text.

The effect is present in all PNG files though in different amounts. I suspect it comes from the tool/s used to create the PDFs from the original images which
apply some softening process (antialising). I have analysed this visually and it consists of a narrow plane in HSV with only two colours mixed with a lot of white/grey/black.

I'd like to know what the algorithm is that creates this blurring and colour so that I can reverse it. Traditional sharpening is only partially successful.
I'd be delighted if anyone has code that does this (any language will do).

NOTE: I do not have originals.

UPDATE.
Here are some analyses of the colors with ImageJ ColorInspector3D plugin in YCbCr space

= YCbCr frequencies =
Note the very sharp plane in which the colors lie

and a histogram to show the distribution more clearly.

(The red/pink is there on the RH sides - not very clear in this screen shot)

I intend to ask another question on how to sharpen this. (This Q is *where" does the effect arise; the next will be how to correct it even if we don't know the origin)

This looks like JPEG artefacts so I guess the image went through a JPEG compression step at one stage and that permanently introduced noise into the image. The red channel is blurred stronger because JPEG additionally applies chroma subsampling.

I suspect the original image was subpixel rendered as you shouldn't really have anything in the chroma channels for a monochrome input image.


understanding glm::perspective vs glm::ortho I'm new to computer graphics.  I played around with OpenGL and now am trying out Vulkan.

Basically what I want to do, in 2D is have an 800x800 window, and I want that to represent 800 meters by 800 meters.  Then I want a circle with a radius of 1 meter.

I am going off of the Vulkan tutorial.

My data structure is this:

struct Vertex {
    glm::vec2 pos;
};

I create my circle:

const int NUM_POINTS = 20;
uint32_t angle = 360/NUM_POINTS;
Vertex vertex;
std::vector<Vertex> vertices;

for(uint32_t i=0; i <= 360; i+=angle){
  vertex.pos.x = cos(glm::radians(float(i)));
  vertex.pos.y = sin(glm::radians(float(i)));
  vertices.push_back(vertex);
}

Something to do with the viewport:

VkViewport viewport = {};
viewport.x = 0.0f;
viewport.y = 0.0f;
viewport.width = (float) swapChainExtent.width;
viewport.height = (float) swapChainExtent.height;
viewport.minDepth = 0.0f;
viewport.maxDepth = 1.0f;

viewport.width and viewport.height both equal 800.0f.

Projection matrices:

struct UniformBufferObject{
  glm::mat4 model;
  glm::mat4 view;
  glm::mat4 proj;
};

projections:

ubo.view = glm::lookAt(glm::vec3(2.0f, 2.0f, 2.0f), glm::vec3(0.0f, 0.0f, 0.0f), glm::vec3(0.0f, 0.0f, 1.0f));
ubo.proj = glm::perspective(glm::radians(45.0f), swapChainExtent.width / (float) swapChainExtent.height, 0.1f, 10.0f);
ubo.proj[1][1] *= -1;

This shows the circle, but it's almost as big as the window and it's tilted 45° away from me.

First of all, I don't understand why, if I make the first argument to glm::lookAt be glm::vec3(0.0f, 0.0f, 2.0f), I see nothing.  I mean the circle is in the x-y plane.  If I move in the z-direction, shouldn't I see it?

Then I tried glu::ortho

ubo.proj = glm::ortho(0.0f, 800.0f, 800.0f, 0.0f);

But I still see nothing.

I don't understand why, if I make the first argument to glm::lookAt be glm::vec3(0.0f, 0.0f, 2.0f), I see nothing.

It's because of the up vector. If you think about the look-at operation, you specify where the camera is and what point it's looking towards. These two things alone leave one degree of freedom: the rotation around that axis. Which way is up on your screen? The third argument is for specifying that: it's a direction in world space which will correspond to up on the screen. If your first argument is that and the rest of the code is as your example, you're calling lookAt((0,0,2), (0,0,0), (0,0,1)). Your up vector points along the $z$-axis, which is the same direction the camera is looking (well, the opposite direction. This can't define which way is up on the screen.

You probably want to pass a vector (0,1,0) as the third argument, which will make $y$ point up on your screen.

If you're making a plan view of a 3D scene, then perspective projection is probably the right answer, but if all your content is going to be in the $z=0$ plane, then you probably want to use an orthographic rather than a perspective projection. Look at What's the difference between orthographic and perspective projection? to learn more about that.

Last of all, remember that if you're projecting an $800m \times 800m$ scene onto $800 \times 800$ pixels, then a $1m$ radius circle will only be one pixel large. You probably need to scale up the size of your circle.


How to convert decomposed transformations between different coordinate systems? I am converting some Unity3D scenes to a proprietary json format to be used by my OpenGL renderer that uses a different coordinate system from Unity's.

I have multiple sets of {translation, rotation(quat), scale} pairs that describe some node transformations. The engine that uses them (Unity) uses the positive x-axis looking to the right, the positive y-axis looking up and the positive z-axis looking front.

I want to convert each pair into a {new_translation, new_rotation(quat), new_scale} in order to use them in my engine using the same coordinate convention with the z-axis inverted (positive z-axis looking back, the most common OpenGL convention).

How should the new pairs be constructed?

Maybe not the best solution but one that should work would be to multiply them by matrix like
\begin{bmatrix}-1&0&0\\0&1&0\\0&0&-1\end{bmatrix}
And multiply by this your mvp matrix to convert meshes vertices (this could be done offline).
Quaternion can be change to matrix form, multiply and save as quaternion.
You also need to change culling in OpenGL because triangle order will be inverted.
I did this in one project and it works fine. If I will find this project I will write something more about it.
//EDIT
This matrix will invert your Z-axis and X-axis
//EDIT2
To apply this solution to each to component you need to:

Change translation x and z component to -x and -z.

Rotation in matrix form multiply by matrix above and change it to quaternion.

Scale leave how it is.
4. Iterate through all meshes and multiply each of their vertices by this matrix.

//EDIT3
Instead of matrix you can just multiply rotation by quaternion (0, 0, 1, 0) (in order (w, x, y, z)) and new quaternion will look like this: (-y,z,w,-x). This operation (and matrix too) just rotate object by 180 degree in y-axis.


How do you deal with clipping when rendering to a limited colorspace? In my naïve raytracer experiment I work internally with RGB values, and after all the tracing has been done, I end up with raw RGB triplets that I need to write down to some image format with a limited gamut, typically sRGB.

Since bright spots in my image can have values far beyond (1,1,1), I need to clip them. Right now I just limit each channel individually, but that will obviously introduce a shift in hue when one channel clips before another. Here is a typical (enlarged) example from my code where the yellow-green object turns into yellow around the highlight:

I'm now looking for a way to solve this problem, but all the solutions I come up with seems to have the same drawback: eventually you have to discard information. For example, I've thought about working with another colorspace like Lab internally, but even then I would first have to transform it to sRGB for rendering the final image file.

Before I dig myself into this any further, I would like to see if there is either:

An objectively "best" way to solve this problem, or..
An industry standard way that is used in practice

Effectively, before you start to think about clipping/clamping, you'll need a general approach to map the much wider color range you are working in onto the [0,1] triplets you want to output. There are various way to do this, look up HDR tone mapping to get a good first impression of what is possible. Simply clipping things to [0,1] will leave you with a very cramped color space to work in, throwing away much of the advantages of raytracying in "high dynamic range" (floats).

On to the actual problem at hand, to prevent clamped colours from shifting hue, a naive but functional approach is:

Take the max component m from (R, G, B)
If m > 1, scale all three components by 1 / m.

This does not take the relative luminance of the color components into account, but if you eventually end up doing something like tone-mapping anyway that would be a better time to tackle that problem.


What is the difference between radiance and irradiance in BRDF Currently I am reading the BRDF section from Real Time Rendering and I am having a hard time to visually understand the definition of this function. BRDF is the ratio between the radiance in outgoing direction and irradiance of incoming direction. I can't visually understand what does irradiance of a certain direction means? And what is the difference with radiance of certain direction? They both represents the power of light. What does irradiance of a certain direction means? Doesn't we associate a direction with radiance? Isn't radiance defined as irradiance in a single direction? I feel like i misunderstand something here. Is E(v) <= L(v) where v is direction?

First of all, irradiance at a certain point of a surface is the density of radiant flux (power) per unit of surface area, while radiance at a certain point of a surface in a certain direction is the density of radiant flux per unit of surface area and unit of solid angle. Vaguely speaking, irradiance is the amount of light incoming to a certain point from possibly all directions, while radiance is the amount of light incoming to a point from a single direction. Why on Earth do we talk about irradiance from a direction then?
The thing is that the BRDF definition assumes that there is radiance $L_i\left(\omega_i\right)$ incoming to point $x$ through an infinitesimal cone $\mathrm{d}\omega_{i}$ around the direction $\omega_i$ with solid angle size denoted $\mathrm{d}\sigma\left(\omega_{i}\right)$, which then generates some irradiance on the surface. This "partial" irradiance is then denoted $\mathrm{d}E\left(\omega_{i}\right)$. This incident light can be partially absorbed by the surface and partially scattered in all directions. The out-scattered contribution of $\mathrm{d}E\left(\omega_{i}\right)$ to radiance outgoing in direction $\omega_o$ is denoted as $\mathrm{d}L_{o}\left(\omega_{o}\right)$.
It can be shown experimentally that the amount of outgoing radiance $\mathrm{d}L_{o}\left(\omega_{o}\right)$ is proportional to the incoming irradiance $\mathrm{d}E\left(\omega_{i}\right)$ and the BRDF is then defined simply as the ratio between the two:
$$
f_{r}\left(\omega_{i}\rightarrow\omega_{o}\right) = \frac{\mathrm{d}L_{o}\left(\omega_{o}\right)}{\mathrm{d}E\left(\omega_{i}\right)}
$$


Minimum requirements to uniquely represent a 3D object in space Let's assume we have a 3D object (in 3D space). We get a single representation vertex from this whole 3D object. Given the fact that the object can be moved and rotated in the space in any direction, what are the minimum set of other information to add to uniquely identify the object's direction and translation in space?

For instance lets consider this 3D object. If we have one single point as a reference, we can construct the whole object (the spatial dependency of other points/vertices are known). The single point can infer the movement. But the object can also rotate in any axis. I was initially thinking with a single normal vector added we can infer the object in space. But looks like we need at least two vectors (am I right?) because the object can also rotate around the normal vector. If we have another vector (maybe orthogonal to the first one), we can infer the whole 3D location. With that we can infer the degree of rotation around the normal axis. Is this right?

Another alternative can be to store 3 reference points. Right?

A rigid body has 6 degrees of freedom, in 3D- space. So that means you need 6 values to represent the object. The common way to do this is to store a position vector for position and 3 rotations. But for obvious reasons any 6 variables that are independent of each other would do this.

The problem with vectors is that they aren't the most efficient way to store the data. If you have a vector for origin and a normal you still need one value for the rotation around the normal resulting in seven variables (this is called an axis angle rotation). Two reference points on object has same problem since you dont know the rotation around the axis of point 1 and point 2 leading to 7 variables.

Image 1: Storing vectors of 2 points has a freedom to rotate along the axis of those the vectors

Now storing extra values can be beneficial for other purposes than position and orientation. So it is quite common to store 7 values for solid bodies. This way it is easier to interpolate so that you dont need to convert between representations all the time.


Identify different contour cycle after model slicing The slicing algorithm is done on the STL model and it is ensured that the result is a series of simple polygons that do not intersect each other. In other words all of those polygons generate closed loops. I need to identify which of those loops are outer and inner loops. There have been some references suggesting tree depth can be used to identify external and internal loops, without any outline of the algorithm.

It would be great if anyone can point to more detailed references where the tree depth can be utilized to filter out inner and outer contour lines.

The following images will provide more information:

According to the article that I am following - a, b, e, f, and j are outer loops, while the rest are inner loops.

In the current situation, I am identifying the inner and outer loops while doing the scanline over each layer after the slicing operation. But I want to identify the inner and outer loops ahead of the scanline operation, so that I can create inner/outer offset for the identified loops and then run the scanline to generate the fill pattern.

The article that I am following is titled - "Equidistant path generation for improving scanning efficiency in layered manufacturing". I googled up and I am afraid that it is not public. I downloaded the article through the university database.

Take a random vertex on your loop, shoot a ray trough all the other loops. For loops you crossed a odd number of times your inside for loops you crossed a even number of times your outside.

The loops that are outside of all others is in the root of your tree. Then find loops that are inside that, but not inside some other. Then find next level and next level and so on.

Image 1: Animation of arranging in tree by shooting rays

You can optimize this by using bounding boxes/ bsp trees for the test areas. But for a small number of areas that might be overkill. just sorting them left to right top to bottom should suffice. You can use the same algorithms as your scan line operators.

Image 2: And now you can offset the shape. But you need to recheck that there is no intersection left after this.

Now the topology is somewhat stable across levels of slices so you can use that to your benefit. Just follow the 3D surface.

Or you could do the offset in 3D on the polygons so you do not need this info. Also if you just need the winding for knowing which way to offset rule you can derive it from the 3d model itself, each vertex has a normal so project the normal for one triangle in each loop with your slicing algorithm per loop. That then gives you the direction of loops outside which is inside for nearly free. You wouldn't get the tree but then again you might not need it.


Are texture binds expensive? I am trying to get a feel for how much effort I should put into this. I am building a basic 2D engine and for my use case there are only 8 textures. Each draw call in this engine currently requires that its 1 corresponding texture be bound to '0'. My question is essentially: Is there something faster than this?

For example, what if I bound the texture for the first sprite to '0' the second to '1' etc etc. This would avoid the gpu having to "switch out" these textures. I am guessing that this wouldn't matter much however.

Is this something that is valid to be concerned about? Is it expensive for the GPU to swap out textures?

It's hardware dependent, but as it stands, you shouldn't expect a performance drop on modern dedicated GPUs. Typically they have a pipeline state cache which fits such a small number of states easily.

The only case when that cache even becomes relevant is if the workload performed in that state is insufficient to saturate the shaders, so execution of subsequent drawcalls overlaps. At that point you can eventually exceed the size of the cache if you have too many different pipeline states and effective utilization drops.

Except that when you do, you will also have trouble combining all the states into one, due to a limit on texture bindings per state and stage, so you would still end up with multiple states. Depending on the API you will have different limits, lower bound being set e.g. by OpenGL 3.x spec requiring 16 texture binding slots per shader, but realistically it doesn't even go much higher than 40-64 binding slots per shader even in high end hardware.

At that point you are better off using a texture array instead - the level of indirection associated with that doesn't cause any significant performance penalty any more, on modern architectures. You "only" have to group your textures by size and tiling at that point.

The alternative is to bake the individual textures into a a single, large texture, which does still allow a certain level of mipmapping, but only down to a level at which pixels from different source textures don't blend. Also you loose the ability to use native tiling, but have to do it manually in shader code.


How to get clean plate from moving footage? I'm not sure if this question is on-topic or not, based on the tour. Feel free to point me elsewhere.

The short version of the question is: what's the typical technique for generating the clean-plate for footage in which the camera moves?

More detail:

It's easy to understand how computer graphics are superimposed over live footage to cover existing elements (like an actor in green pajamas). For example, it seems easy for the CG version of the Hulk to completely cover Mark Ruffalo without having to replace anything real that wasn't already visible in the shot.

It's also easy to understand where this comes from for footage where the camera doesn't move. With a locked-off shot it's not hard to get a shot without any of the actors/props or whatever is being replaced (a clean-plate, as it were), and match that to the real take.

But I'm baffled about non-locked-off shots. A good example might be a scene from Star Trek: First Contact when the Borg Queen is introduced. The upper half of her body is lowered onto a lower-half kind of rig. Whether the actress is actually lowered or not, there is background behind either her invisible real body, as she's lowered, or behind her invisible upper body as it's being rotoscoped down into position.

Either way, they had to have something to show behind the parts of the actress that weren't supposed to be there in the final footage.

One theory I've imagined is that they run the camera through the shot first without the actors, and then repeat the shot with the actors, but this seems prohibitively prone to imprecision.

Another theory is that they get the clean plate from another frame in the same footage, but this seems like it'd only work in very specific cases.

I've also seen tutorials in which the trick is that the shot IS locked-off, and the camera shake is added in after the composite. But again, this only works for certain kinds of shots, and I have a hard time believing that this is the way it's done for everything.

What is/are the typical technique(s) for generating a clean plate for footage in which the camera moves?

There are a couple of techniques:

A motion controlled camera - The camera is on some sort of rig connected to a computer. The computer is programmed to move the camera in a particular way. The camera runs through the moves without the actors, generating a clean set of plates. Then it is run again with the actors, usually wearing green or blue costumes or parts of costumes. For example, in "Forest Gump," one character loses his legs in a war. The actor had working legs, as shown early in the movie, and in some later scenes wore blue stockings that were composited out. (They also used other techniques, such as simply hiding his legs under various things in some scenes. Whatever works!)
As you surmise, sometimes a larger scene is filmed with a locked-off camera to get a clean plate, then during editing, they zoom into the scene and pan around in software to create the motion you see on screen. This doesn't work well for anything that involves the camera rotating, but can work for scenes where the camera trucks.
Parts of the scenery that the actors are in front of are blocked off with green screens and recreated in post. I've seen outtakes of a few pieces where they did this. If you have the DVD of "The Others" with Nicole Kidman, the "DVD Extras" show how fog was added to scenes that were filmed without it. It basically involved someone walking around behind her holding a large green board. Then, they recreated the scenery in the computer, added fog to it, and replaced the green screen with the foggy scene. I have a vague recollection of them doing something similar in the HBO mini-series John Adams. This would likely involve cameras that record their motion. The motion is then imported into the computer and used to move the virtual camera around the scene they've recreated.


Given two arbitrary surfaces, what is the accurate and quite fast algo to find collision within X distance? I have two high-resolution 3D objects(femur and patella) with arbitrary smooth surface and I want to find the contact point/area between those two objects. Accuracy is more important than computation time in this case, though it would be great if the algorithm has relatively low computation time. Also, it would be great if the contact between two objects can be represented with surface/point penetration distance, e.g. if distance between two points/triangles/areas <= x distance, then there is collision, while x can be non-zero. Is there any collision algorithm that satisfy above requirement?

A key search phrase is "collision detection." You may find some references at this MO posting, "Intersection of Polyhedra."
And here is a more recent reference:

  Jiménez, Juan J., and Rafael J. Segura. "Collision detection between complex polyhedra." Computers & Graphics 32.4 (2008): 402-411. (Journal link.)

Google Scholar shows this has been cited by 33 papers since.


Why different result when change input order in GL_LINES? Code:

#include <math.h>
#include <GL/glut.h>
#pragma comment(lib, "opengl32")
#include <gl/gl.h>
#include <gl/glu.h>

//Initialize OpenGL
void init(void) {
    glClearColor(0, 0, 0, 0);

    glViewport(0, 0, 500, 500);

    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();

    glOrtho(0, 500, 0, 500, 1, -1);

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
}

void drawLines(void) {
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(1.0,1.0,1.0);

    glBegin(GL_LINES);

    glVertex3d(0.5,         0.999,  0.0f);
    glVertex3d(499.501,     0.999,  0.0f);

    glEnd();

    glFlush();
}

int _tmain(int argc, _TCHAR* argv[])
{
    glutInit(&argc, argv);
    glutInitWindowPosition(10,10);
    glutInitWindowSize(500,500);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);

    glutCreateWindow("Example");
    init();
    glutDisplayFunc(drawLines);
    glutMainLoop();

    return 0;
}

Problem description:

Above code will put the entire bottom row pixels of the window client area to white.
If I swap the command order, from glVertex3d(0.5, 0.999, 0.0f);glVertex3d(499.501, 0.999, 0.0f); to glVertex3d(499.501, 0.999, 0.0f);glVertex3d(0.5, 0.999, 0.0f);, then only the left bottom pixel will not draw.

My understandings:

The two vertices will be finally transformed to 2D pixel center coordinate which are (0.0, 0.499) and (499.001, 0.499).
The line drawing algorithm only accept pixel center integer points as input.
So the two vertices will using int(x + 0.5) and will be (0, 0) and (499 , 0). This conforms to first result but contradict to the result when input order changed. Why?

The difference in which pixels are covered depending on the vertex order is related to rasterization rules. They're the rules that the GPU hardware uses to determine exactly which pixels are covered by a primitive.

Rasterization rules are a bit subtle. One of their goals is to ensure that whenever you draw multiple primitives that are connected water-tightly, the rasterization never produces any cracks between them, nor are any pixels covered twice (that's important for blending). To achieve that, the rules have some very specific edge and corner cases. Literally...they're cases having to do with primitive edges and corners. :)

In the case of lines, it works as follows. There's a diamond-shaped region around each pixel center, as shown in this snippet of the diagram from the MSDN article linked above.

The rule is that a pixel is covered if the line exits the diamond, when tracing from the start to the end of the line. Note that a pixel doesn't get covered if the line enters, but doesn't exit, the diamond. This ensures that if you have two line segments connected end to end, that the pixel at their shared endpoint only belongs to one of the segments and thus doesn't get rasterized twice.

You can also see in the above diagram how changing the order of the vertices can affect which pixels are covered (which doesn't happen with triangles, BTW). The diagram shows two line segments that are identical except for swapping the endpoint order, and you can see it makes a difference which pixel gets covered.

Your line segment is somewhat analogous to this. The left end, at (0.5, 0.999) is inside the diamond of the (0, 0) pixel, so it gets covered when it's the first vertex (the line starts inside the diamond, then exits it) and not when it's the second vertex (the line enters the diamond, and ends inside it, so it never exits). Actually, the vertices are snapped to fixed-point with 8 subpixel bits before rasterization, so this one ends up rounded to (0.5, 1.0), which is exactly on the top corner of the diamond. Depending on the rasterization rules, this might or might not be considered inside the diamond; it seems as if on your GPU it's considered inside, but this can vary between implementations, as the GL spec doesn't nail down the rules entirely.


Which effects do I need to take into account for the iris of the eye? The iris (the colourful ring surrounding the pupil of the eye) is covered in a layer of water, and appears to have opaque elements embedded in transparent and translucent elements. What effects do I need to model in order for the iris to appear realistic close up (the iris taking up over 20% of the image area)?

Is sub surface scattering necessary or is transparency sufficient? Is it necessary to take into account light from within the eye that entered via the pupil, or can the back of the iris be regarded as completely opaque? Are there other effects that I haven't considered?

I'm looking to produce still images offline - the approach does not need to work in real time.

So far I've tried covering the eye in a thin transparent film to simulate a water layer, and treating the iris as a section of a transparent ball with coloured transparent radially arranged strands, offset as they are layered front to back. To prevent unwanted effects from light that gets all the way through, I have backed the iris with a matt black sphere section. This still seems to give an eye that looks somewhat artificial (inorganic) and disconnected though.

I'm trying to make this work with geometric primitives such as spheres, cones and cylinders, but I'm open to an approach using triangle meshes if that opens up new possibilities.

For a realistic Iris, you need:

Geometry: Irides are very different for different people and their appearance changes drastically depending on whether the pupil is dilated (sphicter muscle relaxed) or not. You will not get anywhere with primitives only. The whole structure is like a thick stretchy wrinkly cloth suspended in water. Wrinkles appear and disappear as it moves. Use a sculpting software and an anatomy textbook.
Material: There is almost no specular on the iris since it is suspended in (basically) water which has a similar refractive index as tissue. I do not know the roughness values since I have never seen a dry Iris. With the GGX specular model, roughness 0.4 looks okay. Brown irides seem to be more rough, almost like very fine sand. A shading model that uses roughness in the diffuse component would be nice.
Textures: While some are colorful, the vast majority of irides in the world are brown. You don't need too much variation inside the texture, it can be quite uniform. Make it relatively saturated and don't try to hint at geometry inside the texture by drawing dark areas for shadows or occlusion. Have a normal map. If the eye is animated, you need to blend between at least two normal maps for the dilated and undilated pupil. I don't think you need a roughness map, but especially for blue irides it might help.
Refraction and reflection at the cornea: The cornea (the fluid layer coating it) acts as a lens. This distorts the image of the iris as seen by the camera. Without this, it will not look real, especially when looking at the eye from the side. The unusual thing about the eye is that, from a graphics point of view, the object is inside the lens. So there's no thin lens equation going to come to your rescue. You have to refract light once, at the interface between the tear layer and air.
The other interfaces (tear layer to outside of cornea, layers and membranes inside the cornea, inside of cornea to chamber fluid) are not relevant since the indices of refraction are all very similar or the structures are extremely thin. The only other optically important structure is the lens, which is behind the iris and can be ignored.
The shape of the cornea is critical, as it will distort everything. People with cornea deformations such as a keratoconus have weird-looking eyes. Also the whole scene must reflect on the cornea/liquid. We expect to see reflections of light sources over the iris/pupil.
The limbus: Looking frontally at the eye, there is a greyish ring around the Iris. This is the part where the cornea merges into the sclera (the "white" of the eye), transitioning from transparent to nontransparent. Behind the limbus, anatomically, is the iridocorneal angle, where the iris meets the rest of the eye. This area is impossible to see due to the refraction mentioned above, it is literally a place that has never seen any light. Light emitted from there experiences total internal refraction at the interface of the cornea, you can't look at it from the outside. Thus, it looks very very weird when the transition from iris to the rest of the eye is visible. You need both the refraction and the gradual transition from cornea to sclera to get this transition right.
Subsurface scattering: You might possibly get away without it on the iris itself since there will never be light coming from the back, especially with a brown iris (more heavily pigmented -> more attenuation during scattering). For some light directions, it will make a difference though. And you need it on the surrounding skin and sclera anyway. But it is not the most important effect.
Ambient occlusion: You need good SSAO (or GI) to make the fine structure stand out. There's almost no specular, so you need other visual cues for the geometry. Choose a method that uses your normals from the normal map. HBAO will work well. For offline rendering, the GI will be done by your renderer of choice.
Lighting: Using some physically based method goes without saying. Image based lighting, especially for the cornea reflection. Under certain angles, refraction of the light at the cornea may become relevant as well (only for analytic lights). Postprocessing (bloom), especially for the cornea reflex.

Backscattered light from the retina, although it can be seen through the iris in very extreme viewing conditions during some medical examinations, is completely irrelevant for normal purposes. Basically, paint the retina black. If you want to go that far, you can add a little orange-red to the retina color whenever a strong light comes from a direction very very similar to the camera and the pupil is dilated (like a flash from a camera). But it will still not be strong enough to shine through the iris, by far. Black is an okay approximation.

That list looks big, but you asked for photorealism ;) It will still look good if you only do the easy half and fake the rest.

(Source: I do graphics programming for medical simulations with a focus on the human eye)

Material:

Anatomically accurate modeling and rendering of the human eye (2007)
High-Quality Capture of Eyes (Disney Research, Siggraph Asia 2014)


Ray tracing - BRDF using Cornell measured spectral data I wrote a ray tracer that implements various BRDF models (Oren Nayar, Lamber, Torrance Sparrow and so on).
Now I'm trying to implement a BRDF from measured data.
I choose the Cornell database data available here:

http://www.graphics.cornell.edu/online/measurements/reflectance/spraypaints/index.html

I want to use them because there's a representation of the data as spectrum with 31 sample (my ray tracer use spectral data for light calculation and then convert them to CIE XYZ and then RGB values for the final image rendering).

Which is the correct way to use this data?
Which sample technique must be used?
Why phi_out has all negative value?
Can I calculate phi_out using the same approximation as the one I used in Oren Nayar, so ||View - Normal * (View.dot(normal)||

The MATLab data file has 3 arrays

Input vector - aka, the light source (In Cartesian coordinates)
Output vector - aka, the eye (Also in Cartesian coordinates)
Spectral data (spectral data is discretized into 31 bins)

So input[n], with output[n] results in spectral[n]

The ASTM file is a flattened version of the MATLab data file, with one major difference: the input and output vectors are in spherical coordinates, specifically the traditional physics notation:

The data is defined in the following range:

For input vector, $\theta$ (theta) varies from $0$ to $\frac{\pi}{2}$, and $\phi$ (phi) is always a constant $0$.

The output vectors are uniformally distributed across the hemisphere. Since $\phi$ is periodic on $2\pi$, mathematically you can define the bounds of $\phi$  in an infinite number of ways. In this data set they chose:
$$\phi = [-\pi, \pi]$$
but it would be perfectly fine to choose
$$\phi = [0, 2\pi]$$

Now, in order to use the data:

Since the input vectors only vary over a quarter circle ($\theta = [0, \frac{\pi}{2}]$ and $\phi = 0$), not the whole hemisphere, you will need to find the matrix transform that transforms your input vector to the quarter circle.
Apply the same transform to the output vector.
Using the transformed input and output vectors, look up the spectral response of the BRDF.

I'm not sure of the best way to do this. I defer to others' opinions. I'm sure there is some kind of data structure / algorithm to do the search.
The naive way would be to do a O(n) search of all the input and output directions to find the two or three that are closest, then LERP between them.

Use the spectral values as the BRDF in the rendering equation


What noises can be sliced? A well-known property of Perlin noise (with FBM) is that if you take a slice of it, the result is still Perlin noise.  So, by taking successive slices of 4D  noise, you get smoothly shifting 3D noise, like a cloud or a lava lamp.

What other noises have this property?

Worley noise, also known as cellular noise, has the same property. It just as easily implemented as Perlin noise and easily extends to higher dimensions. Thus the slicing of 4D Worley noise will produce a 3D Worley noise. However, it is not necessarily a noise function but rather a texture function, producing cellular-like characteristics. With FBM applied to Worley noise some interesting patterns can be created.

You can find additional types of procedural noise functions in this survey paper.


Raytracing Problem - Casting Shadows So I was tasked to create a model of the Cornell Box. I've managed to do everything up until casting shadows, in which case some shadows are cast when there should not be any. Here are pictures of what it looks like now and a larger picture of what it should look like:

I've found that for some reason, the box walls are also casting shadows.

A quick run-down of how it works: we have a pinhole camera which casts rays out and finds the nearest collision point, which is everything you're seeing. It saves these points as well as the distance from some start pt (camera in this case) to the collision point in a pre-defined data structure called an Intersection. It then uses this data to calculate the distance away from the light to create the intensities in lighting. The same method that is used to find the nearest collision point is used to find the nearest object for shadows as well using the original collision point as the start and the light source as the direction of the ray vector.

I've narrowed down the problem to raytracing; when checking to see if there are any objects to cast shadows from from say the upper-right region of the back gray wall, the cyan ceiling is picked up at a point from the same side of the light. E.g. say the light source is in the middle and the original point is on our right side of the light. The method somehow picks up a point that is on the same side of the light when the vector should be going straight through the light source and end somewhere on our left side.

Here is my source code for the functions in question:

bool ClosestIntersection( vec3 start, vec3 dir, const vector<Triangle>& triangles, Intersection& it ) {

    vec3 least;
    vec3 e1, e2, b, v0;
    mat3 A;

    least[0] = m;

    int index = triangles.size()-1;

    for(int i = 0; i < int(triangles.size()); i++) {

        v0 = triangles[i].v0;
        e1 = triangles[i].v1 - v0;
        e2 = triangles[i].v2 - v0;
        b = start - v0;

        A = mat3( -dir, e1, e2);

        if(!getInverse(A,b)) {continue;}

        vec3 x = A * b;

        if(x[0] <= least[0] && x[1] + x[2] <= 1.f && x[1] >= 0.f && x[2] >= 0.f && x[0] >= 0.00001f) {
            least = x;
            index = i;
        }
    }

    if (least[0] == m) {
        return false;
    }
    else {
        it.position = least[0] * dir + start;
        const vec3 t = it.position-start;
        it.distance = sqrt(t[0]*t[0] + t[1]*t[1] + t[2]*t[2]);
        it.triangleIndex = index;
        return true;
    }
}

vec3 DirectLight( const Intersection& i ){
    const Triangle T = triangles[i.triangleIndex];
    const vec3 r = lightPos - i.position;
    const float dist = sqrt(r[0]*r[0] + r[1]*r[1] + r[2]*r[2]);

    Intersection t;
    t.distance = dist;
    t.position = i.position;
    t.triangleIndex = i.triangleIndex;

    //ClosestIntersection( i.position, lightPos, triangles, t);

    /*
    if(!ClosestIntersection( lightPos, i.position, triangles, t)) {return vec3(1,0,0);}
    else { return vec3(0,0,0); } */

    if(ClosestIntersection( i.position, lightPos, triangles, t) && (dist-t.distance > 1.f)) {

        return vec3(0,0,0);
    } else {
        const vec3 B = 14.f * T.color * (float(max(dot(r,T.normal),float(0)) / float(4*3.14 * dist* dist)));

        return B;
    }

}

I have spent over twelve hours trying to find this problem. Even my lecturer can't figure out the problem. Any help would be much appreciated!

are you sure you are not re-intersecting the same surface when checking for light occluder ? this is a classical precision issue. There are many way to tackle it:

First, have a good conditioning of the intersection point, by reintersecting a second time: consider your first hit distance d as approximate, create the point E' = Eye + (d-eps)*ray, recompute the intersection from here. (variant: for the first intersection, just use the bounding box).
Second, for grazing angle, depending on your shape representation, storage and computation precision and scales, tessellation, you might have dangerous imprecision here too, and must still ensure you won't reintersect the same surface. If flat or convex or tesselated, you can tag it an non-intersectable for the shadow-ray test.
A simpler trick (more approximate) is to displace the start of the shadow ray by epsilon in the normal direction.


How to scale primitive shapes [in Blender] so that they are within a [unit] sphere? I wonder how is it possible to scale all shapes so that they are within boundaries of a [unit] sphere? I know how to do this for a cube: if radius of the sphere is S I set the length of X, Y and Z of the cube to S * math.sqrt(3)/3. This way, the corners of the cube are barely touching the surface of the sphere. But I don't know how to do this for other objects such as torus, cylinder and cone in Blender. I wonder, is there a general rule/equation to calculate the scaling factor of a shape so that it fits into a sphere with radius S?

Yes, there is a fairly general algorithm to calculate this scaling factor, which works for all shapes with a known parametric representation. First, substitute the parametric equation of the shape (e.g. a torus, cylinder or cone) into the implicit equation of the sphere, $x^2 + y^2 + z^2 = S^2$. Then, solve this equation for the radius of the sphere. The result will be one or more intervals for values of $S$ for which the shape intersects the sphere with radius $S$. The largest value of $S$ is the radius of the shape's bounding sphere.

Example (torus): Substituting the parametric equation of the torus centered at the origin with major radius $R$ and minor radius $r$ into the implicit equation of the sphere yields $2Rr \cos(\phi) + R^2 + r^2 - S^2 = 0$, which is equivalent to $S\in[R-r,R+r]$. So if you want a torus to fit into a unit sphere, you need to choose the major radius and minor radius such that $R+r\le 1$.


Extracting the green-screen region borders Given a png image with an unknown number of green colored (rgba=0, 65535, 0, 65535) regions

1- How can I find and put the border points of only the separate green boxes to an array like:

[0] = []point{...} // the first box's points
[1] = []point{...} // the second box's points
[...] = []point{...} //
[7] = []point{...} // the last box's points

2- Which algorithm(s) should I use?

I tried canny edge detector and my own custom ones (like flood-fill) but the canny algorithm finds all the regions not only the green ones.

Here is a brute force algorithm. This requires some temporary storage (another image, an array, etc.) to record the visited pixels.

Start at the first pixel and continue iterating over the image until you find a green pixel. Mark each read pixel as "visited".
Extract the set of green neighbor pixels and record them. Also tag them as "visited". The idea is to find all the green pixels connected to the one found in [1].
If any pixels in the source image are left, go back to [1].

This will give you a set of contiguous green pixel regions where each pixel appears 1 or 0 times.


Generate this kind of 2d burst or pulse algorithm? I'm currently trying to develop a game using Cocos2d-x using C++.
I really need to generate this burst or (donut-shaped) pulse.
I'm having a difficult time how to generate such shape.

At first, I was thinking of scaling the image but that didn't work out because the line or "diameter" of the donut shape gets bigger accordingly.
Any experienced coders who can provide an equation of this thing? or maybe "mathematics" is more exact.

https://www.youtube.com/watch?v=ewnEE5mt1ZM

Rather than using an image, I would suggest doing this kind of effect using a shader. I'm not familiar with Cocos2d-x, but some quick googling suggests that it can work with shaders. You'd use a pixel shader that calculates the distance of each pixel to the center of the pulse effect, then applies a function based on that distance to define the shape and appearance of the pulse.

I made a quick shadertoy as a proof of concept and example.


How to implement Z-buffering? I understand the theory behind z buffering - that I have to check for each pixel if its depth value is less than the one on z buffer or not, if yes then draw else not - but I don't understand how would I actually get the z value of each pixel ?

At first I thought I will use the equation of the plane of the polygon I am drawing, but then I have to call the inverse of viewport transform for every pixel. Isn't this every inefficient ?

The values for each pixel in the Z-buffer are interpolated from the values at the corners of the triangle during rasterization. To make this work, the projection matrix produces depth values that are a function of the reciprocal of the original depth value in camera-space.

That is, the $Z'$ value in each transformed vertex is of the form $aZ + b$, where $a$ and  $b$ together determine the near and far planes, and the transformed $W'$ value is just the original $Z$. After doing the homogeneous divide by $W'$, the transformed $Z'$ becomes $a + b/Z$. By using the reciprocal of $Z$ in the depth value like this, you can then just interpolate linearly in screen space from the three corners to each pixel to get correct results. Since the last step produces floating point results, and most Z-buffers use unsigned integer values, you'll need to bias, scale and quantize before writing to the  actual buffer.

I seriously recommend Eric Lengyel's book Mathematics for 3D Game Programming for the nitty-gritty details of all this kind of stuff, he also explains perspective-correct interpolation of vertex attributes and all the other math you'll need to know to write a rasterizer.


What parts of unbiased path tracing pipeline can benefit from OpenCL? After looking at a lot of existing implementations, I am currently implementing a path tracer in OpenCL. However there seems to be divergence to what parts of the pipeline can actually benefit from OpenCL acceleration.

So is it possible to construct a complete path tracer in OpenCL? What parts of the pipeline will benefit the most? Which will benefit the least? Are there any parts that is recommended to keep out of OpenCL?

In short: All of it can benefit from OpenCL.

Path tracing is done by taking many individual ray samples from a scene and combining them into a final image.  As the number of samples increase, so does the quality of the resulting image.

If you are doing regular path tracing (not photon mapping or bidirectional path tracing or anything like that), each sample needs just READ ONLY access to the scene so can work completely independently of the other samples.

That fact makes path tracing astonishing parallelizable.  If you had an output image resolution of 1000x1000, for a total of 1,000,000 pixels, and took 10,000 samples that would mean you needed to take 10,000,000,000 (10 billion) samples.

Each one of those samples is parallelizable, so if you had 10 billion cores, you could make use of all of them.

There are pragmatic concerns when doing this including cache coherency, but the costs of getting that wrong with the naive implementation are much smaller than the benefits of going massively threaded in the first place.

Here is some more information about the details of naive path tracing if you are interested:
http://blog.demofox.org/2016/09/21/path-tracing-getting-started-with-diffuse-and-emissive/


What are the outcodes that would be assigned to these points? In Cohen-Sutherland clipping, it assigns outcodes to the points on lines that are drawn to specify their orientation relative to the clipping window.

In the diagram below, I'm confused on what outcodes that would be assigned to p1, p2, p3, p4? Can someone explain?

The diagram on the Wikipedia entry for Cohen-Sutherland Clipping explains it pretty well:

        left    central right
top     1001    1000    1010
central 0001    0000    0010
bottom  0101    0100    0110

So in your example, p1 would be left, central, so its code  would be 0001.

p2 would be central, bottom, so 0100

p3 would  be  central, central, so 0000

p4 would be central, top, so 1000


Can we use PhysX in WebGL? I'm new to GL stuff (coming in via WebGL, with no direct OpenGL experience). Can we use PhysX with WebGL?

PhysX is a C++ API and can thus not directly be integrated with the JavaScript-based WebGL.

Depending on your needs, you have the following options:

Use a JavaScript-based physics engine, mostly suitable for 2D use cases.
Use a Game Engine that can export for the web (e.g. Unity 3D) and build your application in there, using full 3D physics capability. Keep in mind that this will probably require your users to install some additional Web Player and is not native WebGL.

Keep in mind that Game Engines may be a viable way for 2D applications too and can make your life a whole lot easier.


Caustics: methods to render? What are the recommended ways to render caustics? I am aware bidirectional path tracing and photon mapping can do this. Could someone give a brief overview of photon mapping and a good resource of where to learn about implementation?

First of all, you can get caustics just by Path Tracing. Caustics isn't a difficult phenomenon in computer graphics. Almost any global illumination algorithm can render it. It's just a matter of the converging speed.

While (naive) Path Tracing can render caustics, it takes a long time to clean the rendered image due to how the algorithm works. Photon Mapping makes the converging speed faster by doing some tricks on how light paths are interpolated. Bi-Directional Path Tracing on the other hand tries to make some difficult-to-sample light paths easier.

Besides the two algorithms, Metropolis Light Transport can render caustics efficiently by finding the most significant light path in the scene and exploring other possibilities around it.

Here are some good lectures on:

Ray based rendering algorithms
Path Tracing
Photon Mapping

There is the original paper of BDPT. It's not too difficult if you can implement explicit light sampling and multiple importance sampling by your self.

Also, I recommend the book Physically Based Rendering: From Theory to Implementation. It talks about all the algorithms above and more. It is basically a must have if you want to dive deep into computer graphics.


How do I use barycentric coordinates to interpolate vertex normal? Given a triangle and a point inside the triangle in Cartesian coordinate system, I compute the Barycentric coordinate of the point like this:

double v2_1[3], v2_3[3], v2_t[3];

double bary[3];
vtkMath::Subtract(p1, p2, v2_1);
vtkMath::Subtract(p3, p2, v2_3);
vtkMath::Subtract(t, p2, v2_t);

float d00 = vtkMath::Dot(v2_1, v2_1);
float d01 = vtkMath::Dot(v2_1, v2_3);
float d11 = vtkMath::Dot(v2_3, v2_3);
float denom = d00 * d11 - d01 * d01;

float d20 = vtkMath::Dot(v2_t, v2_1);
float d21 = vtkMath::Dot(v2_t, v2_3);
bary[0] = (d11 * d20 - d01 * d21) / denom;
bary[1] = (d00 * d21 - d01 * d20) / denom;
bary[2] = 1.0f - bary[0] - bary[1];

return bary;

Now, how can I use the values in bary to interpolate the vertex normal at p1, p2 and p3? Specifically, I'm confused which coefficient belongs to which vertex.

Thats the way your defining the vectors. See your defining vectors $V_1$ and $V_2$ as pointing outwards from the point $P_2$.

Now then $denom$ is the square of the area of the parallelogram of formed by completing the triangle with a duplicate of itself. Another way to look at this is that its the 2 tines the square of the are of the triangle.

Now then the calculation:

(d11 * d20 - d01 * d21)

Is the square area of the parallelogram of $P_2$-$T$-$P_3$

Now if you divide this with denom, then you have calculated the total area relative area of triangle $P_2$-$T$-$P_3$. So the formula (d11 * d20 - d01 * d21) / denom is the triangle size in relation to whole triangle size of:

This is the weight that the opposing corner exerts on the point. which in other words it is the barycenter weight related to point $P_1$.

The next line is simply the relative area of triangle $P_2$-$T$-$P_1$ or:

Which is opposite to $P_3$ being the barycentric coordinate of $P_3$.

Lastly you calculate the rest which is the remaining triangle which is opposite of $P_2$ using 1 - bary[0] - bary[1].

Note: You could have chosen the first vectors differently for a different order.


Perspective correct interpolation z-buffer While I was deriving expressions for perspective-correct linear interpolation on triangles, I reached the conclusion that the interpolation may be kept linear only if view-space $Z$ is available. However, computing view-space $Z$ requires nonlinear interpolation (it is a rational function based on my results). Is nonlinear interpolation performed in hardware to get perspective correct $Z$, or equivalently linear interpolation is performed on $\frac{1}{Z}$ but a division is required to get view-space $Z$ anyways? As far as I get it there is no way around that - a division is required per-pixel to get perspective-correct Z values - is that correct?

Yes, that's correct. Perspective-correct interpolation works by (for some quantity $u$ to be interpolated) calculating $u/z$ and $1/z$ at each vertex, linearly interpolating those values in screen space, then calculating $u = (u/z) / (1/z)$ at each sample point. This is done by the GPU hardware behind the scenes.


3D coordinates of intersection point in clipping for a rasterizer When doing clipping in homogeneous coordinates, we need to find the coordinates of the intersection of the viewing frustum with the line to be clipped. This can be done easily if we want those coordinates to be in screen space(simply divide by the fourth coordinate). But how can we find those coordinates in 3D space? And do we need to do so in the first place?

Thanks in advance.

I think it depends on what your goal is and what kind of initial data you are provided with. I don't think that dividing by the forth coordinate solves a clipping task. What it does is switching of the coordinates of your objects from 3D projective (four components) to 3D Euclidean (three components).

I would say, the basic component you need is a procedure of calculating the intersection point in projective coordinates of a line and a plane.

An arbitrary point in projective three space is written as a four-vector column:
$$X = \begin{bmatrix}X_1\\X_2\\X_3\\x_4\end{bmatrix}$$ and a plane in projective three space can be expressed as
$$N^T X = 0$$ where
$$N^T X = \begin{bmatrix}N_1 \,\, N_2 \,\, N_3\,\, N_4\end{bmatrix} \begin{bmatrix}X_1\\X_2\\X_3\\x_4\end{bmatrix} = N_1X_1 + N_2X_2 + N_3X_3 + N_4X_4$$
A line in projective three space is traditionally given by a pair of points
$$A = \begin{bmatrix}A_1\\A_2\\A_3\\A_4\end{bmatrix} \,\, \text{ and }\,\,
B = \begin{bmatrix}B_1\\B_2\\B_3\\B_4\end{bmatrix}$$ and any point $X$ on the line is expressed as
$$X = t_1 A + t_2 B$$ for two real numbers $t_1, \, t_2$ not equal to zero simultaneously. Tho find the intersection point of the line $X = t_1 A + t_2 B$ with the plane $N^TX = 0$ we simply plug
$$0 = N^TX = N^T \big(t_1 A + t_2 B \big) = t_1(N^TA) + t_2 (N^TB)$$ and since $t_1, \, t_2$ are determined uniquely up to a common factor, a solution to the equation
$$t_1(N^TA) + t_2 (N^TB) = 0$$ is $t_1 = -\, (N^TB)$ and $t_2 = (N^TA)$.

Therefore, given a plane $N^TX = 0$ and a line determined by a pair of points $A$ and $B$, the unique intersection point of the line with the plane is calculated as
$$P = - (N^TB)\, A + (N^TA)\, B$$ We us projective coordinates, because it may happen that one of the points on the line, say $B$ is "at infinity" with respect to our perferred choice of Cartesian coordinates. That means that
$B = \begin{bmatrix}B_1\\B_2\\B_3\\0\end{bmatrix}$. In this case, the line is interpreted in Cartesian coordinates as the line passing through the 3D Cartesian point $A = \begin{bmatrix}\frac{A_1}{A_4}\\\frac{A_2}{A_4}\\\frac{A_3}{A_4}\end{bmatrix}$ and aligned with the 3D vector $\vec{V}_B = \begin{bmatrix}B_1\\B_2\\B_3\end{bmatrix}$.

In order to clip a line, you can go about it in two different ways, both of which can use the formula for the intersection between a line and a plane. You can find the (projective) equations of the planes of the frustum, intersect the 3d line with them and then project the points onto the screen, which is again intersection of a plane with lines passing through the origin. Alternatively, you can project the two points that determine the line onto the screen (again you can use the formula for the intersection of the line connecing the origin with any of the two points with the plane of the screen), which allows you to know the projection of the 3D line on the screen, and then find the intersection points of the projected line with the borders of the screen. Maybe the second scenario is simpler?

The screen is parallel to the $x,\,y$ plane of the 3D Cartesian frame, while the $z$ axis is perpendicular to the screen and the screen is at a distance $l$ from the origin of the coordinate system. Therefore, the Cartesian equation of the plane of the screen is $z = l$. In projective coordinates, $z = \frac{X_3}{X_4}$, which means that $\frac{X_3}{X_4} = l$  so the projective equation is $X_3 = l\, X_4$ and can be also expressed as
$$0 = X_3 - l\, X_4 = S^TX = \begin{bmatrix} 0 \,\,\, 0 \,\,\, 1 \,\, - l\end{bmatrix} \begin{bmatrix}X_1\\X_2\\X_3\\x_4\end{bmatrix} $$ where
$S = \begin{bmatrix}0 \\ 0 \\ 1 \\ -l\end{bmatrix}$
so if the 3D line is determined by the pair of points $A = \begin{bmatrix}A_1\\A_2\\A_3\\A_4\end{bmatrix} $ and $B = \begin{bmatrix}B_1\\B_2\\B_3\\B_4\end{bmatrix}$ Hence, with $O = \begin{bmatrix}0\\0\\0\\1\end{bmatrix}$, the projection of $A$ on the screen is
$$\hat{A} =  - (S^TO)\, A + (S^TA)\, O = l\, A + (A_3-l\, A_4)\, O = \begin{bmatrix}l\,A_1\\l\,A_2\\l\,A_3\\l\,A_4\end{bmatrix} + \begin{bmatrix}0\\0\\0\\A_3-l\, A_4\end{bmatrix} = \begin{bmatrix}l\,A_1\\l\,A_2\\l\,A_3\\A_3\end{bmatrix}$$  and the projection of $B$ on the screen is $$\hat{B}= \begin{bmatrix}l\,B_1\\l\,B_2\\l\,B_3\\B_3\end{bmatrix}$$ So one can write this projection in  matrix form as follows:

$$P_{scr} = - (S^TO)\, \text{Id} + O\,S^T$$
because $P_{scr}A = \Big(- (S^TO)\, \text{Id} + O\,S^T\Big)\,A = - (S^TO)\,A + O\,(S^TA) = - (S^TO)\,A + (S^TA)\,O = \hat{A}$

\begin{align}
P_{scr} &= - (S^TO)\, \text{Id} + O\,S^T\\
&\\
&= - (-l)\begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix} + \begin{bmatrix}0\\0\\0\\1\end{bmatrix}
\begin{bmatrix}0\,\,\, 0\,\,\, 1 \,\,\, - l\end{bmatrix}\\
&\\
&= \begin{bmatrix}l & 0 & 0 & 0 \\0 & l & 0 & 0\\0 & 0 & l & 0\\0 & 0 & 0 & l\end{bmatrix} + \begin{bmatrix}0 & 0 & 0 & 0 \\0 & 0 & 0 & 0\\0 & 0 & 0 & 0\\0 & 0 & 1 & -l \end{bmatrix}\\
&\\
& = \begin{bmatrix}l & 0 & 0 & 0\\0 & l & 0 & 0\\0 & 0 & l & 0\\0 & 0 & 1 & 0\end{bmatrix}
\end{align}
And thus
$$\hat{A} = P_{scr}\, A \,\, \text{ and } \,\,
\hat{B} = P_{scr}\, B$$
When you have your points projected on the screen plane, you would like to get rid of the $z-$coordiante, so you need to remove the third (out of our) component of your projected points, i.e.:
$\hat{A} = \begin{bmatrix}l\,A_1\\l\,A_2\\l\,A_3\\A_3\end{bmatrix} \mapsto \begin{bmatrix}l\,A_1\\l\,A_2\\A_3\end{bmatrix}$ so if you take the projection from four vectors to three vectors
$$P_0 = \begin{bmatrix} 1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ and muptiply it by  $P_{scr}$ from the right as $P_0P_{scr}$, we can take the projective map from the projective three space to the projective plane of the screen
$$P = P_0P_{scr} = \begin{bmatrix} l & 0 & 0 & 0\\0 & l & 0 & 0\\0 & 0 & 1 & 0\end{bmatrix}$$
So, to recap, given  a line in projective three space, passing through the pair of points $A$ and $B$, their screen images, in projective coordinates of the screen, are
$\hat{A} = P\, A$ and $\hat{B} =P \, B$. The formula for the intersection of a line with a plane in projective three space translates verbatim to the intersection of a line given by a pair of points $\hat{A}$ and $\hat{B}$ with another line given as an equation $N^T\hat{X} = 0$ in the projective plane, where $N = \begin{bmatrix} n_1\\n_2\\n_3\end{bmatrix}$,
$$\hat{X}_N = (- N^T\hat{B})\hat{A} + (N^T\hat{A})\hat{B}$$ so
alltogether
$$\hat{X}_N = (- N^TP{B})\,P{A} + (N^TP{A})\,P{B}$$ So this is the formula for the projected points of intersection of the three dimensional line with the frustum's boundary. For example,  the right vertical boundary of the screen is given by an $N_{right\, vert} = \begin{bmatrix} w\\0\\0\end{bmatrix}$ and the bottom horizontal boundary of the screen is given by an $N_{bottom\, hor} = \begin{bmatrix} 0\\- h\\0\end{bmatrix}$


Optimal memory access when using lookup tables on GPU? I'm exploring isosurface algorithms on GPU for a bachelor's project (specifically concentrating on just binary in/out voxel data rather than real-valued fields). So I have a CPU implementation of good old marching cubes up and running in OpenFrameworks, and now at the stage of trying to port it to GLSL compute shaders, and considering the pitfalls before I dive in. I've only written vert and frag shaders before so it's all new to me.

My first issue is how to efficiently use a lookup table across dozens or hundreds of threads in a workgroup? I understand a GPU has different kinds of memory for different tasks but not fully sure on how each operates or which type to use.

Paul Bourke's classic copypasta table is a 256*16 array so if using a scalar byte type this can presumably be packed into a 4kb texture or SSBO.

The question is, how to stop the different threads from tripping each other up? Many cubes in each work group can potentially have the same configuration therefore trying to access the same location in the buffer at the same time. Is there a workaround or optimization to deal with this?

The best place to put a look up table for a GPU compute shader depends on the size of the lookup table, and the frequency/coherency of access. In your case (you mentioned 4kb), shared local memory would likely be best (assuming you do not need this memory for other purposes in the same kernel). This memory has different names in different APIs, but is the same architectural thing and follows the same performance guidelines:

CUDA: threadgroup shared memory
DirectCompute: groupshared memory
OpenCL: local memory
Metal: threadgroup memory
OpenGL: shared memory

Storing the lookup table in global memory as a read-only buffer may perform just as well, depending on the cache size(s) of the particular GPU you're running on.

Note that I'm presuming this is a read-only lookup table. A read-write lookup table is a completely different beast, and you don't have any good options there.


Identify plane of symmetry in 3D mesh Is there an efficient way to identify the plane of symmetry in a 3D mesh? Preferably with existing code / software but if anyone knows how to implement it that would also be helpful.

Example of the problem: you have a 3D mesh of a duck that is centered at the origin. The correct answer in this case would be the plane where x = 0.

You can look into this: https://cescg.org/wp-content/uploads/2017/03/Dvo%C5%99%C3%A1k-Estimating-Approximate-Plane-of-Symmetry-of-3D-Triangle-Meshes.pdf
There are definitely other papers on the subject though


With vsync enabled where does the wait happen in OpenGL? When having vsync enabled I'm imagining that OpenGL has an explicit wait function to try and keep the frame rate constant. If so where is this function implemented exactly? After running some tests glClear() function seems to take almost 16 ms with minimal OpenGL script on my machine. When removing this function, the wait seems to happen where the first (?) glDrawArrays() or glDrawElements() function is implemented. If none of these functions are implemented then on my machine the wait happens during glxSwapBuffers().

I'm hoping to get some better understanding behind his, partly to know when to best poll the input events. Previously I polled at the start of the main loop and then rendered the scene. But since there's a wait during glClear() function, I'm experiencing a bit of an input delay. So maybe it would make more sense to poll in-between clearing the buffers and rendering the scene?

It's a bit complicated because the actual wait for vsync does not happen on the CPU, it happens on the GPU. The GPU wait then creates back-pressure that propagates back to the queue of submitted command lists on the CPU, through the GL driver, and eventually to your app. The exact behavior will depend on the details of how the GPU vendor chose to implement their GL driver, and also probably depends on the behavior of the windowing system as it controls frame presentation. Unfortunately there are no real guarantees about this in GL as far as I'm aware, it's really up to the vendors.

In this case, it seems likely that you're seeing the wait become visible to your app at the first GL command that causes the driver to try to begin recording into a new command list (which may entail waiting for a previous command list to finish executing on the GPU, so that the driver can reuse it for the new frame). Clears, draw calls, dispatches, buffer mapping or copying, etc would probably qualify, while (for example) state-setting calls or memory allocation calls might not issue any actual commands to the GPU.


Bokeh from depth map How do I generate bokeh that simulates shallow depth of field given a perfect depth map?

Here's what I tried:

Generated a sample scene using blender and corresponding depth map

Using Python, generated what sigma (standard deviation) to use at each pixel for gaussian blurring: This one makes it look like the far end of the pink cube is perfectly focused.

sigma_map = np.array(np.round(abs(np.array(depth, dtype='float32') - preferred_focus_depth)).clip(0,255), dtype='uint8')

black = 0, no blur; white = 255, large blur

Applied gaussian blurring (using the sigma_map) at every pixel and this is what I got

Flaws observed: Averaging kernels just near the edges are taking in the pink color nearby hence the pink bleed. How do I avoid this?

Note: It's not completely blurred look closely at the zoomed in image on the right. The pixels that I wanted to remain untouched are still untouched (even though it appears they were blurred as well because of the blurring near the edges)

This blog on Portrait mode on Pixel 2 says, "Actually applying the blur is conceptually the simplest part", is there any simpler way of doing it then?

The blog post that you talked about, is not about generating bokeh for a computer generated image. It is instead about generating a believable depth of field effect from an image captured by a smartphone camera, as the effect is desired for portraits to make the subject stand out. It generally works by splitting the image in to two parts. One part is the subject, which should not be blurred. The other part is the background, which should be blurred but the pixels of the subject should have no influence and would thus have a weight of zero. Slightly more sophisticated algorithms may make the blur kernel size variable across an image to create a smoother transition, but the subject's pixels would still be ignored.

In games and CGI, post process depth of field is done differently. There are multiple ways for it. A simple google search shows multiple. You could do depth of field like you have, and simply ignore the pixels which should not be blurred to remove the ghosting. However, this is not true to how depth of field occurs inside of a camera. So, in order to get a good algorithm to simulate depth of field, I will first try to explain how you get the depth of field effect in an actual camera.

Let us say, that we have an object, a single lens and an image sensor. We look at them from the side.

Light scatters in many different directions when hitting the object. To simplify we only take one point. From this point, I will show the light that would hit the lens as a gray solid.

The lens bends the light towards a single point. That is the focal point.

You can see that the focal point is in front of the sensor. This causes the light from that single point on the object, to fall on a large portion of the sensor. If the focal point is behind the sensor, the same would happen. But, if the focal point lies on the sensor, there would only be one point on the sensor where the light falls on. This area where the light falls on the sensor, is called the circle of confusion (CoC). This is also the cause of the depth of field effect.

One important thing to know, is that when the point on the object moves around, the focal point also moves around. If the point moves closer to the lens, the focal point moves closer to the lens, which would alter the size of the circle of confusion. This gives you the gradual change in blurriness that you have with depth of field, since the circle of confusion gradually becomes larger when an object moves away from the area in focus.

If we add in an aperture we simply block out a part of the light, which causes the circle of confusion to be smaller. This allows us to determine how much light to let in (to make the image brighter or darker), and how strong the depth of field effect is.

From this, we can conclude a few things on how we should implement depth of field.

Every point whose light enters the camera lens, has a circle of confusion.
The circle of confusion is the area where the light, from that point, falls on.
The circle of confusion changes size when the point moves closer to or further away from the lens, or when the aperture changes size.
The area of the circle of confusion has no falloff. Every point inside the circle of confusion has the same weight. This results in a box blur.
If a point is in focus, its circle of confusion would be either zero or something so small, that it is not noticed.

The algorithm is quite simple. For each pixel in the image, we use the depth to calculate the circle of confusion. Then, we add the colour of that pixel to all the other pixels that lie in the circle of confusion. However, if that other pixel is closer to the camera (a lower depth value), it would block the light from our pixel, and we should not add the colour of our pixel to the blocking pixel.

In pseudo code it would look something like this;

// for each pixel in the all-focus image
for(x = 0; x < width; x++){
    for(y = 0; y < height; y++){
        // How much blur? Zero or close to it if it should be in focus.
        float CoCRadius = calcCoCRadius(depth(x, y));

        // For every pixel in the square with the size of CoCRadius.
        for(i = x - CoCRadius; i <= x + CoCRadius; i++){
            for(j = y - CoCRadius; j <= y + CoCRadius; j++){
                // Discard pixels outside of the shape. Square -> Circle
                if(isInBokehShape(i - x, j - y)){
                    // Discard pixels that would block it.
                    if(depth(i, j) >= depth(x, y){
                        // Add the colour.
                        newColour[i, j] += colour(x, y);
                        // Add the weight, for normalizing.
                        weight[i, j] += 1.0f;
                    }
                }
            }
        }

    }
}
//Normalize the values with the weight.
for(x = 0; x < width; x++){
    for(y = 0; y < height; y++){
        newColour[x, y] /= weight[x, y];
    }
}

This would give you a depth of field effect that is quite true, and does not give you the ghosting effect. $calcCoCRadius$ is a method that calculates the radius in pixels of the circle of confusion. It could be anything, but if you want it as true to an actual camera, then you can use the formula from this Wikipedia page. $isInBokehShape$ is a method which returns a boolean on whether the point is inside the bokeh shape. With the two for loops we just get a square, but if we want to get a circle shaped bokeh, we need to discard the pixels that would lie outside of the circle. This discarding is also the reason why we keep track of the weights and normalize afterwards with the weight, since we do not know how many pixels we need to discard. The weight is also useful if you do want a falloff in the circle of confusion, for example if you want a gaussian blur.

Another important thing to know, is that the implementation listed here, is not very optimal. The problem is basically that you write to multiple different pixels. This causes race conditions. Instead, it is better to rework the algorithm so that you only need one write. Basically, you loop through every pixel and you then you check all other pixels (or pixels inside of a maximum CoC radius) whether their CoC radius is large enough that they contribute to the pixel's colour. This way, you can also put the normalizing of the values inside the first loop over all the pixels instead of having to do that later.

This should be a fairy good way of implementing depth of field as a post processing effect. There are also other ways, but this is one.


Why is rotating this prism in iOS Metal not rendering correctly? I've set up a test project for learning Metal on iOS to do some rendering, but I'm a bit stumped on how to get a prism rotating correctly about its y axis.

Here is the prism rendered without depth testing so all sides can be seen, so it looks like this part is at least correct:

These are the vertices:

static const float vertexData[] = {
     0.f,  1.f,  0.5f,
     1.f, -1.f,  0.f,
    -1.f, -1.f,  0.f,

     0.f,  1.f,  0.5f,
     1.f, -1.f,  1.f,
     1.f, -1.f,  0.f,

     0.f,  1.f,  0.5f,
    -1.f, -1.f,  1.f,
     1.f, -1.f,  1.f,

     0.f,  1.f,  0.5f,
    -1.f, -1.f,  0.f,
    -1.f, -1.f,  1.f
};

However, when I turn on rotation, this is what happens:
https://www.dropbox.com/s/esg41j3ibncofox/prism_rotate.mov?dl=0

(The video has depth testing turned on). Why is the prism clipping like that (and/or what is it clipping through)? And it's not rotating about it's centre.

Here are how the MVP matrices are being calculated:

static simd::float3 viewEye = {0.f, 0.f, -2.f};
static simd::float3 viewCenter = {0.f, 0.f, 1.f};
static simd::float3 viewUp = {0.f, 1.f, 0.f};
static float fov = 45.f;

CGSize size = self.view.bounds.size;
Uniforms *uniforms = (Uniforms *)[uniformBuffer contents];
uniforms->view = AAPL::lookAt(viewEye, viewCenter, viewUp);
uniforms->projection = AAPL::perspective_fov(fov, size.width, size.height, 0.1f, 100.f);

uniforms->model = AAPL::translate(0.f, 0.f, 12.f) * AAPL::rotate(tAngle, 0.f, 1.f, 0.f);
tAngle += 0.5f;

The transform, lookAt, rotate, and perspective_fov functions are lifted straight from Apple sample code I used as reference.

Here is the shader:

typedef struct {
    float4 pos [[ position ]];
    half4 color;
    float mod;
} VertexOut;

vertex VertexOut basic_vertex(const device packed_float3* vertex_array [[ buffer(0) ]],
                              const device packed_float3* colors [[ buffer(1) ]],
                              constant Uniforms& uniform [[ buffer(2) ]],
                              uint vid [[ vertex_id ]],
                              uint iid [[ instance_id ]])
{
    float4 v = float4(vertex_array[vid], 1.f);
    float4x4 mvp_matrix = uniform.projection * uniform.view * uniform.model;

    VertexOut out;
    out.pos = v * mvp_matrix;
    uint colorIndex = vid / 3;
    out.color = half4(half3(colors[colorIndex]), 1.f);
    return out;
}

fragment half4 basic_fragment(VertexOut f [[ stage_in ]]) {
    return f.color;
}

Any help/tips would be appreciated!

The problem was in the shader, and I had the order of multiplication wrong with the MVP matrix.

So this:

out.pos = v * mvp_matrix;

should be:

out.pos = mvp_matrix * v;

For whatever reason, I'm used to dealing with row vectors and had myself convinced the problem was due to the matrices themselves and the clip region..


Matching an HSV color with a blended color This is hard to explain but I am going to try, then I will explain it as pure mathematics.

Look at this image.

So basically this is a moving line, each frame a new segment is added and the previous frame is faded by an amount decided by fps. (There are dots to make things neat but I'm not showing them for simplicity).

So based on the FPS a number is calculated (0.05 if perfect FPS ) and as a result the previous frame gets a black plane drawn over it with an opacity of 0.05.

As you can see this causes an issue because of the segments. My solution is to give each vertex a color, however I don't know how to calculate that color.  The line color is defined by HSV, and the fading is decided by RGB.  Furthermore I am pretty sure fading with the transparent plane creates an exponential effect, however HSV.V works linearly.

My question is if I know on a given frame that the fading plane will have an opacity of 0.05 how can I calculate an equivalent HSV color to what the previous frame will be after fading? That way the bottom two vertices can be a darker color and interpolation can fix it.

The formula that decides the opacity of the black is as follows.

(dt / (1 / 60)) * 0.5

The opacity acts linearly through the colors, i.e. it affects R G B similarily, so it should affects the value V the same way.
You just want to have an intensity factor decay as $0.95^n$.


How to avoid slowdown with 25-30 students running simple GPU kernels on 4 GeForce GTX 650 Ti s? So I'm teaching crash-course in CUDA that teaches students how to write good GPU code (CUDA 7.5 in this case). They kernels they will be running will do matrix multiply on 2048x2048 floating point matrices, some kernels involving multiple blocks and shared memory.

The students will be ssh-ing into servers that have the GPUs where they will compile and run their programmes.

I haven't a clue on how feasible this is and the only step I can imagine taking to prevent slowdown is to assign groups of students to different GPUs by telling them what value to pass cudaSetDevice().

Edit for posterities' sake:
I ended up not taking any precautions and the lab ran smoothly. Wasn't much of test though, since only half (15 or so) students did the lab simultaneously, and we only got to cover really simple hello-world kernels.
Second edit:
There were two servers, with two GeForce GTX 650 Tis per server

You need nvidia-docker. If your ssh server is in a Docker instance, you can assign each one to a different GPU. Then just set things up so only one team is sshing into each Docker instance. You don't need to do anything fancy with cudaSetDevice(), or risk students using the wrong device and messing things up for others, because each instance looks like it only has one GPU.


Which 3D algorithms does Windows 10's "3D Builder" application use? Windows 10 ships with "3D Builder", a Universal App that contains utility functions to prepare STL, OBJ, 3DS, and other files that represent geometries for 3D printing.

The utility looks like this:

In particular, they have triangle mesh functions there that:

"Detect" when a mesh is not suitable for 3D printing;
"Repair" so that the mesh isn't right it prepares it, by removing internal faces, closing "holes" in the outer surface, etc.;
"Simplify" by removing redundant triangles, such as those found to be adjacent and co-planar; and
"Plane Cut", slicing a mesh through an arbitrarily positioned plane and filling in a surface on that plane to re-enclose the geometry, sometimes followed by a "Detect" and "Repair".

Every copy of Windows 8.1 and 10 has this utility at no additional cost. That says to me that the functions are well-known and as far as I've been able to test, reliable for virtually all inputs to the 3D printing use case. I used some of the messiest STL files I could find to prove this thing.

Which algorithms did they use for those functions? Where are they found for a .NET/WPF/UWP environment?

More to the point, did they expose the functions in an API I can use for a slightly dissimilar use case?

In the builder the functions look like this:

Simplify (the tractor top and sides have fewer facets):

Slice, UI before processing:

Slice, after processing and then one "Simplify" pass:

Well obviously nobody except the makers of this program can answer the exact algorithms used. I have done a quick explanation on each. Each separate task really deserves its own question and answer.

Just iterate each polygon, for each vertex check if all of them are above the cut line eliminate the face. To make this check easy you can transom each vertex to the plane orientation. If not all vertices are above the cut line then the triangle is split along one of the edge that has a eliminated vertex. Then use the internal face closing algorithm. Heres some math.

Face closing algorithm works by finding open edges and then tessellating the new polygon closed. Please note: That this produces somewhat erratic results if the open holes are not planar. See polygon triangulation

Simplifying planar regions is basically the same face closing algorithm except they you first build up polygons out of regions. Also decimation might come to play. There is a lot of lore, and different algorithms for simplification and going trough all of it its way too bread for a post like this.

Self intersection is a sorting problem. Quite a bit of lore on this exists too. The one that i mostly do is putting the polygons one by one into a BSP self organizing tree and checking against polygons against items in that tree to reduce the check complexity to n log n.

Internal cavities can be detected by splitting each mesh into shells and then for each shell check if the other shell is contained within each other. See this post


Ray tracing in One weeked: issue with metal reflection Problem

I am following the book Ray tracing in one weekend , and I got stuck after the implementation of the material Metal. I checked my code many times, and it looks exactly like the code implemented by Peter Shirley.
The problem is that, at this point, my code would need to generate this image:

Instead, my implementation results in this:

There is no reflection on the left and right sphere, even if the code looks fine. I am not posting the code here since many classes are involved, and I implemented it following strictly the book. Did someone have a similar problem? I can post relevant parts of code that can help.

 Possible solution

The function of the reflection is not the problem, since it is very simple and it is exactly like the one proposed in the book. Also, when I set the sphere below (the floor) as Metal instead of Lambertian, it shows the reflections correctly:

This suggests that the problem is not the reflection function, nor the material.

The problem was in the way I was calculating the function bool Sphere::hit(). The author eliminates some redundant 2's that cancel each other without explicitly showing it, and if you don't pay attention to this detail the code the hit function will not work as it is supposed to. In case someone else is stuck, that might be the problem.