How to denoise video? Video noise is random and not correlated in time. I assume, the best method is using wavelet denoise in this case, right? If yes, how is wavelet denoise implemented for video? Is there something to consider in order to apply the calculation to the whole image sequence?

Elaboration on temporal solve:

I don't have much concrete info for you, but I'm drawing from the idea of "temporal anti aliasing".

Basically, if a camera was stationary, you could average pixel values over the last N frames, possibly using harmonic mean or something else like that to help filter out spikes.  The result would be a cleaner, less noisy, more correct image.

But not all cameras (or objects!) are stationary, so what then?  Well, if you have some way of identifying where a pixel this frame matches a pixel on the previous N frames, you could average them in the same way.  If a current pixel has no matching previous pixel (due to something previously occluding becoming visible) you just show the raw current value.

Games use this for antialiasing by simulating super sampling over time, but they have the benefit of per pixel motion vectors as well as the current and previous camera matrix, so it's a lot harder in your situation!


How can virtual texturing actually be efficient? For reference, what I'm referring to is the "generic name" for the technique first(I believe) introduced with idTech 5's MegaTexture technology. See the video here for a quick glance on how it works.

I've been skimming some papers and publications related to it lately, and what I don't understand is how it can possibly be efficient. Doesn't it require constant recalculation of UV coordinates from the "global texture page" space into the virtual texture coordinates? And how doesn't that curb most attempts at batching geometry altogether? How can it allow arbitrary zooming in? Wouldn't it at some point require subdividing polygons?

There just is so much I don't understand, and I have been unable to find any actually easily approachable resources on the topic.

Overview

The main reason for Virtual Texturing (VT), or Sparse Virtual Textures, as it is sometimes called, is as a memory optimization. The gist of the thing is to only move into video memory the actual texels (generalized as pages/tiles) that you might need for a rendered frame. So it will allow you to have much more texture data in offline or slow storage (HDD, Optical-Disk, Cloud) than it would otherwise fit on video memory or even main memory. If you understand the concept of Virtual Memory used by modern Operating Systems, it is the same thing in its essence (the name is not given by accident).

VT does not require recomputing UVs in the sense that you'd do that each frame before rendering a mesh, then resubmit vertex data, but it does require some substantial work in the Vertex and Fragment shaders to perform the indirect lookup from the incoming UVs. In a good implementation however, it should be completely transparent for the application if it is using a virtual texture or a traditional one. Actually, most of the time an application will mix both types of texturing, virtual and traditional.

Batching can in theory work very well, though I have never looked into the details of this. Since the usual criteria for grouping geometry are the textures, and with VT, every polygon in the scene can share the same "infinitely large" texture, theoretically, you could achieve full scene drawing with 1 draw call. But in reality, other factors come into play making this impractical.

Issues with VT

Zooming in/out and abrupt camera movement are the hardest things to handle in a VT setup. It can look very appealing for a static scene, but once things start moving, more texture pages/tiles will be requested than you can stream for external storage. Async file IO and threading can help, but if it is a real-time system, like in a game, you'll just have to render for a few frames with lower resolution tiles until the hi-res ones arrive, every now and then, resulting in a blurry texture. There's no silver bullet here and that's the biggest issue with the technique, IMO.

Virtual Texturing also doesn't handle transparency in an easy way, so transparent polygons need a separate traditional rendering path for them.

All in all, VT is interesting, but I wouldn't recommend it for everyone. It can work well, but it is hard to implement and optimize, plus there's just too many corner cases and case-specific tweaks needed for my taste. But for large open-world games or data visualization apps, it might be the only possible approach to fit all the content into the available hardware. With a lot of work, it can be made to run fairly efficiently even on limited hardware, like we can see in the PS3 and XBOX360 versions of id's Rage.

Implementation

I have managed to get VT working on iOS with OpenGL-ES, to a certain degree. My implementation is not "shippable", but I could conceivably make it so if I wanted and had the resources. You can view the source code here, it might help getting a better idea of how the pieces fit together. Here's a video of a demo running on the iOS Sim. It looks very laggy because the simulator is terrible at emulating shaders, but it runs smoothly on a device.

The following diagram outlines the main components of the system in my implementation. It differs quite a bit from Sean's SVT demo (link down bellow), but it is closer in architecture to the one presented by the paper Accelerating Virtual Texturing Using CUDA, found in the first GPU Pro book (link bellow).

Page Files are the virtual textures, already cut into tiles (AKA pages) as a preprocessing step, so they are ready to be moved from disk into video memory whenever needed. A page file also contains the whole set of mipmaps, also called virtual mipmaps.
Page Cache Manager keeps an application-side representation of the Page Table and Page Indirection textures. Since moving a page from offline storage to memory is expensive, we need a cache to avoid reloading what is already available. This cache is a very simple Least Recently Used (LRU) cache. The cache is also the component responsible for keeping the physical textures up-to-date with its own local representation of the data.
The Page Provider is an async job queue that will fetch the pages needed for a given view of the scene and send them to the cache.
The Page Indirection texture is a texture with one pixel for each page/tile in the virtual texture, that will map the incoming UVs to the Page Table cache texture that has the actual texel data. This texture can get quite large, so it must use some compact format, like RGBA 8:8:8:8 or RGB 5:6:5.

But we are still missing a key piece here, and that's how to determine which pages must be loaded from storage into the cache and consequently into the Page Table. That's where the Feedback Pass and the Page Resolver enter.

The Feedback Pass is a pre-render of the view, with a custom shader and at a much lower resolution, that will write the ids of the required pages to the color framebuffer. That colorful patchwork of the cube and sphere above are actual page indexes encoded as an RGBA color. This pre-pass rendering is then read into main memory and processed by the Page Resolver to decode the page indexes and fire the new requests with the Page Provider.

After the Feedback pre-pass, the scene can be rendered normally with the VT lookup shaders. But note that we don't wait for new page request to finish, that would be terrible, because we'd simply block on synchronous file IO. The requests are asynchronous and might or might not be ready by the time the final view is rendered. If they are ready, sweet, but if not, we always keep a locked page of a low-res mipmap in the cache as a fallback, so we have some texture data in there to use, but it is going to be blurry.

Others resources worth checking out

The first book in the GPU Pro series. It has two very good articles on VT.
Mandatory paper by MrElusive: Software Virtual Textures.
The Crytek paper by Martin Mittring: Advanced Virtual Texture Topics.
And Sean's presentation on youtube, which I see you've already found.

VT is still a somewhat hot topic on Computer Graphics, so there's tons of good material available, you should be able to find a lot more. If there's anything else I can add to this answer, please feel free to ask. I'm a bit rusty on the topic, haven't read much about it for the past year, but it is alway good for the memory to revisit stuff :)


Controling order of execution of a (compute) shader on an array of vertices (data) in Vulkan Is it possible to force Vulkan to execute a shader on vertices (data) in a semi-consecutive manner?

For example, if the data passed to the shaders as a binary tree, shader would process it one layer at the time, starting from the root, while allowing multiple nodes to be processed concurrently only if they're on the same layer. I know that synchronicity is a big thing in Vulkan, but I'm unsure if it could be used at this layer of the pipeline.

A use for it would be in a structure where the results of parents influence the results of their children, while the work on the each element is done with the same code.

An example would be to calculate the effect of the wind on a tree - if nodes are the branching points of a tree, the location of each point would depend on the force applied to the source branch, but also on the force applied to each and every of it's ancestors, since each branch would bend, but also move with the rest of the tree - the rotations would add up. Doing it the way I described above would greatly speed up the computation for a single tree, possible increasing performance enough to scale the simulation maybe even several orders of magnitude. The benefits are even greater if you do it for all the trees in the scene at once.

Is this possible with Vulkan? What topics should I look into specifically in order to accomplish this?

Vulkan is not really suited to at least some of the task you're trying to accomplish. It has no mechanism to declare from within a shader that some additional work should be invoked. Or at least, not directly.

The most effective way to execute this on the GPU would be to compute each level of all of the trees as a distinct dispatch operation. So you process all root nodes first, then the first level for each tree, then the second level, etc. Each compute shader invocation will need to do the processing for its node and store that computed data.

This also requires that you store your tree data in a fairly scrambled way. All of your trees need to live (on the GPU side) in the same general array, preferably with all nodes for a particular level stored contiguously with one another. This makes processing easier, but it makes adding new nodes harder.

The biggest performance problem will likely be the dependency issue. Each layer depends on the execution of the previous layer, which means you won't get much parallelism between layers. You're effectively inducing a stall between each set of layers. If you're executing thousands of nodes, you'll saturate your GPU's execution units just fine; it's the first few layers when you have few nodes that will have less performance than they could.

Now, you may be able to avoid this performance problem by using a different shader for the first couple of layers. Such a shader would have each invocation process, say, the first 3 levels of the tree. On the one hand, this mitigates synchronization costs. But on the other hand, each shader invocation has to read and process a lot more data. And reading/writing a bunch of data from multiple invocations can be expensive, compared to having a more pipelined operation.

So you should profile it and see what works best.

Oh, and FYI: OpenGL compute shaders are just as capable of this as Vulkans.


What is a good approach for handling uniforms in modern OpenGL? I'm creating a renderer using modern OpenGL (3.1 and up) and now I'm trying to create an efficient but flexible way of handling uniforms. I've been reading up on uniform buffer objects and on what a 'common' approach is to using these (the latter unfortunately didn't give me as many results as I had hoped).

In order to reduce OpenGL API calls and storing data in contiguous memory, I'm considering creating multiple large buffers for each data structure that should be uploaded to the GPU. Each buffer has a maximum size of 16kb (as from what I understand this much is guaranteed to be available for an UBO). When an object wants to be able to upload uniforms to the GPU it fetches the first buffer of the to-be-uploaded-type that isn't full yet and gets the next available index in that buffer. When the object is drawn it binds the UBO (if not bound yet) and uploads the element index of the UBO.

This results in something like this:

layout(std140) uniform ModelData {
    mat4 model_matrix[kNumInstancesPerModelUbo];
}
uniform int u_ModelDataIndex;

layout(std140) uniform SkeletonData {
    mat4 bone_transforms[kNumInstancesPerSkeletonUbo][kMaxBones];
}
uniform int u_SkeletonDataIndex;

However I'm also considering the following:

layout(std140) uniform MeshData {
    mat4 model_matrix[kNumInstancesPerMeshUbo];
    mat4 bone_transforms[kNumInstancesPerMeshUbo][kMaxBones];
}
uniform int u_MeshDataIndex;

In some ways this feels a lot cleaner in that it takes a single index to access all data related to the mesh to be uploaded. On the other hand this could get out of hand (buffer size larger than 16kb, handles to irrelevant data (e.g. a mesh with no skeleton) or even synchronization issues as you're not allowed access to say the bones while uploading the model matrices) and I'm not sure how this would affect the memory layout on the GPU either.

Frankly it feels like I'm stuck here and I can't find a good concrete example of how you'd go about handling UBO's fast and flexible.

Do you have any advice or resources for me that could help me out here?

Suballocating from a larger buffer is absolutely the way to go, with caveats. I'm coming more from a DirectX/Vulkan side of things, but this should apply equally to OpenGL (I just won't have direct API calls here in this answer). The things to consider are the following:

Do you need to index into the larger buffer, or are you OK with binding the resource to the offset each time?
Have you taken care of any/all alignment restrictions for your uniforms that are packed together (256 byte alignment is common)?

Newer graphics APIs have a "dynamic offset" you can specify with the draw command which is a pretty fast way to indirectly access a subregion of a buffer. However, assuming you are triple-buffering data that's mutable, there should be little to no contention in the driver for binding the data (just some fixed overhead).

In summary, yes, allocating larger regions of memory/buffers and subleasing those regions is considered best practice. This applies even to objects with different shaders (if your allocator can handle it).


Which 3D object properties should be affected by distance? Which 3D object properties should be affected by distance in VR and other 3D applications and how important is it that they are changed?
For example the level of detail, colour (?)...

There is only one major thing that I can think of in nonstereographic view that is affected by size and that is:

Atmospheric haze and subsurface scattering, even this is similar at most or all macroscopic ranges.

That said you can easily do this by fudging one constant in a shader. Or slightly more tediously by adding aerosols in the air if you are in fact doing this in real photography, altough getting it exactly right is hard.

This changes in stereoscopy as humans have some sense of their own scale. So the disparity between cameras sets a scale. But if you change the distance between the cameras then you change scale so even they do not have to be in absolute scale just relative scale.

So in fact most things are self similar at all practical scales. And only when you start to see effects that are fixed light wavelength do you get into this problem.


How is orthographic projection used in computer graphics technically classified as a projection? I'm wondering why the orthographic projection we use in computer graphics is called a projection, if all it does is just scale and translate a mesh?

According to wiki orthographic projection is Orthographic projection (sometimes referred to as orthogonal projection, used to be called analemma[a]) is a means of representing three-dimensional objects in two dimensions, but we don't use orthographic projection to project our mesh to 2d space, we just use it to transform our mesh defined in the view box with arbitrarily defined dimensions (left, right, up, bottom, far and near) to a view box of (-1, 1, -1, 1, -1, 1) dimensions. So why do we call it an orthographic projection?

I think it is more of a terminology shared specifically in the computer graphics community. The transformation $P$ results in a vector one-step-ahead from getting the actual projection. From a 3D position transformed with $P$, we can obtain both

the 2D-projected position in normalized device coordinate (NDC) (by obtaining xy component)
the depth (by obtaining the z component) in NDC

This so-called projection matrix is designed specifically to satisfy the needs in the computer graphics pipeline. The key difference between an ordinary N-D-to-(N-1)-D projection is that the projection matrix results in 2D positions with "depth", which is required for obtaining a depth map used for many purposes in the computer graphics pipeline.


GPU not reaching 100% usage when frame rate is dropping I am making an iOS game using Unity. I am testing some shaders that I have made for the game, and in some cases the device will run at under 30 FPS but not have 100% device utilization.

Sometimes a test will start at a higher device utilization %, and then over time go lower, even though the test is simply rendering a plane with a material on it.

For example, a shader test I just ran on an iPad 4: Device utilization 85% Renderer utilization 85% Tiler utilization 1% Core Animation Frames Per Second 12

This test is using barely any CPU, and is only rendering 4 triangles (2 big planes covering the screen).

Does anyone have any ideas why this could be happening? Usually the renderer utilization goes up to 100%... pretty stumped, being a graphics rookie.

IOS has mandatory v-sync. I am curious why the "Core Animation Frames Per Second" in the Instruments profiler would say 12 FPS if v-sync is enabled, and how that would correspond to the 85% device utilization.

Perhaps the device is rendering 12 frames, and 2 are dropped to get it down to the v-synced frame rate of 10? That would result in ~83-84% effective device utilization.

Or perhaps it is that given the above stats (85% utilization and 12 FPS), the GPU could render 14 FPS if at 100% usage. However v-sync requires either 10, or 15 FPS, nothing in between. This may result in the GPU slowing down, to not waste power and CPU, but still remain safely above the next step down on v-sync.

Generally, with VSYNC, your CPU is effectively doing nothing 99% of the time, as it merely sent the simple vertex buffer batch (few triangles, as you said) to the driver. If the shader is bandwidth-heavy, it takes multiple frames to render. In your case, you said it's 12 fps, e.g. 60/12 = 5 frames. So, the CPU (or the core that runs your thread), is literally doing nothing for 5 frames (other than waiting for vsync). That's an egregious waste of performance for a 3d engine.

Why is the 'utilization' statistics important, anyway ? What matters is your framerate, that's how you know how well you're doing, not some arbitrary 'utilization' number in the OS, that god-knows-how it got assembled in the first place.


Finding vertices of the outer contour of intersecting polygons I have a bunch of intersecting convex polygons, I want to find vertices of the outer contour of all those polygons. An individual polygon is not self-intersecting.

Could you please tell What could be a generic way of achieving this? Is there an API to do this?

PS: I'm developing a CAD drawing generator using .netdxf and C#.

Below is a simple example

Sounds like you’re looking for a way to do a Boolean union operation. There’s a couple of algorithms linked from that article that should do the trick.


Explanation of the Vatti clipping algorithm I am going through the Vatti Arbitrary Polygon Clipping Algorithm, but got stuck at their very initial explanation. It says the following:

  Call an edge of a polygon a left or right edge if the interior of the polygon is to the right or left, respectively. Horizontal edges are considered to be both left and right edges. A key fact that is used by the Vatti algorithm is that polygons can be represented via a set of left and right bounds which are connected lists of left and right edges, respectively, that come in pairs. Each of these bounds starts at a local minimum of the polygon and ends at a local maximum. Consider the "polygon" with vertices $\{p_0, p_1, ..., p_8\}$ shown in Figure 1(a). The two left bounds have vertices $\{p_0, p_8, p_7, p_6\}$ and $\{p_4, p_3, p_2\}$, respectively. The two right bounds have vertices $\{p_0, p_1, p_2\}$ and $\{p_4, p_5, p_6\}$.

The image it refers to is:

I do not understand the vertices of the second left bound $\{p_4,p_3,p_2\}$. How are these vertices derived?

(Promoting "comment" to an answer)

It looks to me that it's just finding monotonic runs of edges. Given a defined winding order (in this case anticlockwise), then you can identify {P6, P7, P8, P0} as a decreasing run, as is {P2, P3, P4}. Since the left most vertex, P8, is in (**the middle of) a decreasing run, the decreasing runs define left boundaries and, therefore, increasing runs are right boundaries.

**it just occurred to me that if the left most point is at the beginning/end of a monotonic run then a slightly more involved rule will need to be applied involving the edges entering/leaving that point.


What's the meaning of the "dynamic" in "high dynamic range"? What's the meaning of the "dynamic" in "high dynamic range"?

Why use this word?

Dynamic, adjective:

  1: pertaining to or characterized by energy or effective action; vigorously active or forceful; energetic:

  ...

  4: of or relating to the range of volume of musical sound.

HDR allows you to deal with high light energies. And such high energies could be characterized as being "vigorously active or forceful; energetic".

But I think the fourth definition is more suitable. Graphics and rendering are forms of signal processing, much like sound. So they share a lot in common. For example, the term "aliasing" originated in digital conversion of sound.

"High light energies" are the visual equivalent of "volume" in sound. So the "dynamic range" that you can record, the "range of volume" is high, as opposed to low.


Why do 3d modeling packages use a single normal per polygon and how is this viable for smooth shading If we have a quad that is non-planar. Why do most 3d modeling packages choose to use a single normal for the quad (Specifically for Blender3d by using cross product of two edge's vectors that do not share a vertex, here's the math). Instead of viewing it as two triangles, and using a separate normal for each triangle?
Normally we calculate a vertex normal as the normalized average of all polygons the vertex is part of. If we have a quad consisting of two triangles, then the two vertices that are part of both triangles, get the average of the two triangle normals. This results in smooth shading across the non-planar quad. Instead of the uniform shading we would get if we were to use a single normal for the whole quad.
This also extends to polygons in general. In 3d modeling sofware a single normal is calculated for the whole polygon (for Blender3d with Newell's method), instead of individual normals for each triangle it consists of.
To build on top of this, if we have a mesh with flat shading, each polygon gets a single normal as described above. Flat shading means that the shared vertices are split. And each vertex gets the normal of the polygons it's part of. However what happens if we want to apply a smooth shading on the mesh? Are the vertex normals calculated as average of all polygons it is part of? This doesn't seem right. Do we instead triangulate the mesh, and calculate the vertices as the average of all triangles it's part of?

I think the problem comes from this starting assumption:

If we have a quad that is non-planar.

A non-planar quad does not have a normal. It's not a flat surface, so you can't talk about what its normal would be. You can't talk about the normal of a sphere, a cone, or any other non-flat surface. You can talk about what the normal might be at any particular point on that surface, but there is no normal for the surface in its entirety.
You are asking a question for which there is no correct answer. But there are many incorrect answers, and they're all equally wrong. So there's no reason to pick one wrong answer over another.
If you're talking about computing vertex normals, a non-planar quad is still not a valid surface. The two triangulations for a non-planar quad represent very different surfaces, which would have very different vertex normals. Neither answer can claim legitimacy over the other, so both answers are equally wrong.
So why choose that particular method? Because it's no more wrong than any other method you might pick.
It does not make sense to talk about the vertex or face normals for non-planar polygons. So if you want an answer that makes sense, fix that problem first.


Confused on reflection coeffcient of Fresnel equations I am reading a paper about layered materials. However, I am confused on the implementation of this paper. The following picture describe the layered material.

r_ab is a complex reflection coeffcient when going from medium a to medium b.

And in the code, there is:

        float2 R12, phi12;
        fresnelDielectric(LdotH, 1.0, eta_2, R12, phi12);
        float2 R21 = R12;

I don't understand why is r_12 equal to r_21?


How to store > 256 transparency values in textures? I am making an engine with 2D volumetric transparent objects and need advice how to store transparency data. There are 3 requirements:
- The transparency textures need to be easily editable with common tools (e.g paint.NET, so .png preferred)
- Since a pixel value will determine the light transmittance 8 bits are not enough - in this case lights could travel maximum 256 pixels in non fully transparent textures.
- It should be clear what each pixel means when looking at the texture.

I've tried using the HEX values from RGB pixels. For example heres a strip with HEX values from 0 to 0xFFFFFF:

While this gives enough values (256*256*256), looking at the image its not clear what each pixel means (=if I'd pick a random pixel from this image you could not tell approximately the alpha value).

Does anyone know a good method how to represent >256 values in an RGB texture, where its clear what each pixel means?

A normal argb image has 8 bits per channel and therefor 32 bits per pixel, the size of an integer. That's why it's stored in an integer a lot of the times.

Floats are also 32 bits.

Something that you can do, is to have a separate image that has only 1 channel, for the transparency. If you make that a float type (or for 16 bit, another type that uses 16 bits instead of 32 bits), then it will take about the same room as an extra normal image.

After a quick google, I found out that most programs are limited to 8 bit per channel, but there should be programs that have 16 bit per channel.
This gives you at least more precision.

When loading in the normal 16 bit image (your texture, if you use 16 bits per channel), you could convert the normal rgb part to 8 bits, and load that in and then create a new image that has 1 channel that is 16 or 32 bits, and then store the alpha value in there.

This way it should be similar to having an extra image, and you do, but instead of 2 textures, you have the transparency in another image.

What would then also be possible to do, is to store the transparency in a normal rgba image (inside your program as a texture), as you were talking about, and then in the shader, you manipulate the rgba values to restore the transparency value. This way you wouldn't need a floating point image.

This is just a quick idea. As far as I know, this should work. (This is my first answer here! whoop! whoop!)

Hope it helps and good luck!

https://developer.mbed.org/handbook/C-Data-Types

(^for the data sizes)


How can I debug what is being rendered to a Frame Buffer Object in OpenGL? I have a point cloud that is being rendered to the screen. Each point has its position and color as well as an ID.

I was asked to render the IDs for each point to a texture so I created a FBO and attached two textures, one for color and one for depth. I created the necessary VAO and VBO for this off-screen rendering and uploaded for each point its position and ID.

Once the rendering to the FBO is done, I read the pixels of the color-texture with glReadPixels() to see what the values are, but they seem to be all cleared out, i.e., the value they have is the same as glClearColor().

Is there a way I can debug what it is being render to the color texture of my FBO? Any tips that you may provide are very welcomed.

Generally to see what is being rendered in the various steps of your pipeline I'd suggest the use of a tool for frame analysis. These usually provide you with a view on the content of each buffer for each API call and this can help you in your situation.

A very good one is Renderdoc which is both completely free and opensource. Also it is actively supported.

Another one is Intel GPA that unfortunately, according to its webpage, support up to OGL 3.3 Core.

Just for the sake of adding one more, I used to use gDEBugger, but it has passed long since the last update. This has evolved into AMD CodeXL that unfortunately I never used.


human visual: relation of Distance and DPI I was told that human's visual sharpness is 60 pixels per degree. As such, pixel per inch is approximately given by:

PPI = 1/ (Distance * tg((1/60*pi/180) )

Is this formula fully correct? (I saw similar, but slightly different versions). How is this formula derived? Maybe some step by step description?

According to a review by Legge & Bigelow the arc or degrees of visual angle ($\alpha$) is,

$$
\alpha = 57.3 \times S/D,
$$

where S is height of object and D is distance to object. [1] $S/D$ is the small angles approximation of $2 \times arctan(S/2D)$ which follows form geometry.

Image 1: the equation comes straight from trigonometric definitions.

Since humans continuously scan the page with the fovea, small angles assumption is a good approximation for entire pages. The factor $57.3$ is simply $180/\pi$ or conversion form radians to angles.

So given that we do not know the nature of $tg$, then its hard to say. Looks a bit fishy, but if tg is some sort of inversion of S then its plausible.

[1] G. Legge & C Bigelow. 2011. Jornal of vision. Does print size matter for reading? A review of findings from vision science and typography.


Why do GPUs divide clip space Z by W, for position? Background:
I found that it is very easy to use a linear depth buffer, using only a slight modification to the canonical vertex transformation. The simplest method is found at the bottom of https://www.mvps.org/directx/articles/linear_z/linearz.htm.

However, the caveat is that it only works for triangles that don't need to be clipped against the near or far planes. (And an alternate solution, of performing the perspective divide in the vertex shader, will yield a similar problem for the other four frustum planes.)

Because clipping requires linear interpolation to work across all four clip space coordinates, I think it's impossible to work with linear depth, using  only a vertex shader. But the reason for that is all down to Z being divided by W.

Why is that done? X and Y need to be divided by distance from the camera, but the Z coordinate does not, to fit perfectly into the NDC box.

If you are doing a perspective image and your model has implicit intersections then, if you use "linear Z", those intersections will appear in the wrong places.

For example, consider a simple ground plane with a line of telephone poles, receding into the distance,  which pierce the ground (and continue below). The implicit intersections will be determined by the interpolated depth values. If those are not interpolated with 1/Z, then when the projected vertices have been computed with perspective, the image will look incorrect.

I apologise for the non-aesthetic quality of the following illustrations but I did them back in '97.

The first image shows the required rendering effect. (Note that the blue "pylons" go quite a long distance under the ground plane so are clipped at the bottom of the images)

This second image shows the result of using a non-reciprocal depth buffer: (Apologies for the change of scale - these were copied out of an old MS Word doc and I've no idea what has happened with the scaling.)

As you can see, the results are incorrect.

On another note, are sure you really want a linear Z representation? If you are rendering perspective, surely one wants more precision closer to the camera than at a distance?

Re your later comment:

  “if those are not interpolated with 1/Z” that I don’t understand. What interpolation is that?

The first thing to note is that, with a standard perspective projection, straight lines in world space remain straight lines in perspective space. Distances/lengths, however, are not preserved.

For simplicity, let us assume a trivial perspective transform is used to project the vertices, i.e.
$$X_{Screen} = \frac{X_{World}}{Z_{World}}$$
$$Y_{Screen} = \frac{Y_{World}}{Z_{World}}$$
We should also compute a reciprocal screen-space depth, e.g. $$Z_{Screen} = \frac{1}{Z_{World}}$$ but linear Z in the depth buffer would, to me, require something like: $$Z_{Screen} = scale*Z_{World}$$ (We can assume here that scale=1)

Let's assume we have a line with world space end points$$
  \begin{matrix} \begin{bmatrix}
    0 \\
    0 \\
    1 \\
    \end{bmatrix} and
   \begin{bmatrix}
    200 \\
    0   \\
    10  \\
    \end{bmatrix}\\
  \end{matrix}
$$
With the perspective mapping these map to screen space coordinates
 $$ \begin{matrix}   \begin{bmatrix}
    0 \\
    0 \\
    1 \\
    \end{bmatrix} and \begin{bmatrix}
    20 \\
    0  \\
    0.1 \\
    \end{bmatrix}
 \end{matrix}$$

The rendering system/hardware will linearly interpolate the screen space z, so at the 1/2 way point of the line, as it appears on-screen, i.e. at pixel (10, 0), we would get a projected (inverse) Z value of 0.55, which corresponds to to a world space Z value value of ~1.818. Given the starting and end Z values, this is about 20% along the length of the line.

If instead, we tried to interpolate using the original Z values, we'd end up with Z corresponding to a world space value of 5.5. As long as nothing intersects, you might be ok (I've not thought about it too thoroughly) but anything with implicit intersections will be incorrect.

What I haven't mentioned is that once you introduce perspective correct texturing (or even perspective correct shading), you must do per-pixel interpolation of 1/w and, additionally, also compute, per pixel, the reciprocal of that interpolated value.


mapping 3d texture on view frustum (or part of it) I'm implementing volumetric fog in my OpenGL renderer. First I inject color into 3D texture using compute shader, atomic operations and shadow map visibility check. The information I use to compute cell index and position in world space are uniforms: camera pos, cellsize and texture dimensions.
Next, when volume filled with data is ready, I need to align it with view frustum to raymarch through texture and apply effect as postprocess (deffered stage) and I'm quite stuck with it. I think there are two options (red is texture volume):

So, while applying effect I raymarch from camera pos to frag pos (from G-Buffer texture). I dont know if it is correct, but I think I need to somewhat transform frag pos to NDC, scale it to [0,1] and then using this sample from volume.

Tried some magic like:

vec4 texcoords = vpMatrix * vec4(fragPos, 1.0); //to clip space
texcoords.xyz /= texcoords.w; //to NDC
texcoords.xyz = texcoords.xyz *0.5 +0.5; //[-1,1] to [0,1]

Eventually:

vec3 texcoords;
texcoords.x = texcoord0.x; //texcoord0 - texcoords of screen quad
texcoords.y = texcoord0.y;
texcoords.z = depth; //depth from vector: worldpos-camerapos

But its just guessing. In addition I dont know which option from picture is used in such cases (pro game engines) and how to apply only on some length of frustum because its quite big. Will be really grateful for any hint for this.

To check if this works for now its implemented like this: camera aligned in center of volume so rotating it not really matters some much. So i probably will need to modify injections stage too to get correct cell indexes which are statically computed like:

vec3 index = vec3(gl_GlobalInvocationID); //cell number of texture;
vec3 pos = camerapos+index*cellSize;

In techniques I've seen that use a frustum-aligned voxel grid (so-called "froxels"), it looks like option 2 in your diagram. The voxels are cuboids in post-projective screen space, so when transformed back to world space they look like mini-frusta, automatically expanding as they get farther from the camera.

Marching along eye rays is then very easy: you just step along the grid's Z axis. Summing optical density or in-scattered light along an eye ray is just a matter of iterating over the Z dimension of the texture. (Or you could try to apply methods like parallel prefix sum as well, but it may not be worthwhile, depending on the texture size.)

If you're rendering some geometry and you want to know which voxel it's in, you don't have to do any matrix transformations. Just use gl_FragCoord, which represents the screen-space position (including depth) of the current fragment. It comes in window units (i.e. pixels) so you'll have to remap it to [0,1] for texture sampling, or to voxel units if you're doing an image store.

Otherwise, for mapping world-space positions into the voxel grid, use the usual sequence of transformations. It looks to me like you got it right in your code snippet, assuming fragPos is in world space. For getting from the voxel grid back to world space, you'll need to invert that sequence of transformations.


Determining level connectivity Imagine you have a 3D level format consisting of an arbitrary number of convex polytope brushes (or we can simplify and consider just oriented-bounding boxes) and several point entities.

I want to find an algorithm to determine

If the level is water-tight. That is, the brushes are adjacent to each other and fit together to form a hull without gaps or holes.
If the level is disjoint, identify the set of brushes in each section.
If all entities are inside the water-tight level, and in which section (from (2)) they are in.

(1) isn't strictly necessary, but it seems necessary to ensure that (2) and (3) are well defined.

All engines I know that use this kind of level format (Doom, Quake, Source) seem to use a BSP algorithm for these tasks. However, they also use the resulting BSP tree as an acceleration structure for rendering, which I'm not interested in using.

Is anyone aware of any other possible alternative algorithms, or is BSP the only choice?

BSP is a classic for computational geometry tasks involving polygons. However, polygonal meshes are subject to a dismaying list of pathologies such as degenerate polygons, inconsistent winding order, T-junctions, coincident vertices, cracks or holes, self-intersecting geometry, loss of coplanarity or collinearity due to roundoff error, and other such things. Making computational geometry robust on arbitrary polygon meshes is Quite Difficult™.

It worked in Doom/Quake/Half-Life days because the base level geometry (made of brushes and constructed in a level editor, as opposed to a 3D modeling tool), was relatively simple, mostly axis-aligned, and all vertices were snapped to grids. More recently, the trend seems to be for level design seems to be done by creating mesh pieces in 3D modeling tools, then sticking together a bunch of instances of them to form a level. This kind of construction is a lot less friendly to BSP-type algorithms—especially as the geometric complexity rises.

An alternative approach for connectivity questions is voxelization. In short, you voxelize all your level geometry at some reasonably small resolution, like 10–30 cm per voxel or so. The voxelization wipes away any geometric errors smaller than the voxel size, and it gets rid of all those annoying pathologies mentioned earlier. You can use an octree or brickmap etc. to avoid voxelizing empty space.

Once you have the voxel representation of the level, you can then do all sorts of connectivity queries on it very easily because of the regular structure of the voxels. For instance, determining if a level is watertight or finding connected-components at the voxel level is basically a flood-fill. These kinds of algorithms can also be done hierarchically using the octree etc. to avoid the expense of a global flood-fill over a huge number of voxels.

For more reading, there was a 2011 SIGGRAPH talk Making Game Worlds From Polygon Soup, from some engineers at Bungie who used voxelization techniques on Halo Reach levels to build nav meshes, precompute visibility cells and portals, and so on.


Ray tracing the next week: understanding Instances My question is not about the code, but it's about the approach used by the author Peter Shirley (and apparently common practice in ray tracers) of handling Instances. To understand the question it's necessary to be familiar with the book, because posting the code for every class involved is not feasible.
Something I don't understand is how rays behave.

Let's consider the traslation. The idea is to offset the origin, and check if the new ray - which is now shot from the new origin with the same direction of the original ray - hits the object. If so, we shift the hitting point by an equal and opposite offset.

Two questions:

1) Why is it not sufficient to shoot rays from the "standard" origin, and offset the hitting point without actually shifting the origin first? Example: the ray is shot, if it hits the object in point (x,y) I move the hitting point by 2 (x+2, y+2) and store it.

2) The hit function of the class translate is only called when the original ray hits the object? Because in that case, the translation would not result in the whole object, since it would only store those points that are first hit by the original ray, and for which the new ray hits the object again.

There are two ways to 'translate' your object. The first is by moving each point of your object by the desired translation. The second is by translating the origin of your coordinate system. In this case it's the latter. Basically it turns out to be the same, whether you translate your object by a vector $\vec{t}$ or whether you translate your origin by $-\vec{t}$.

For 2) note that you only care about the intersected points (since that is what you use to compute the pixel color), so you compute the offset only when you need it. So yes, you do translate the origin of the ray at each intersect, it's the same as translating the object though (at each ray intersect), since $\vec{p}+\vec{t} - \vec{o} = \vec{p} - (\vec{o}-\vec{t})$.


How do I create a Win32 window with a Vulkan context? I am aware of libraries that already do this (like GLFW), but I would actually prefer do all of the window and context creation by myself.

There's no such thing as a Vulkan context, the way there is with OpenGL.  This is because Vulkan is a lower level API and an OpenGL context ties together a number of concepts that are distinct in the Vulkan API.
For example, the OpenGL context ties together the concept of extension management, memory management, draw commands and surface presentation.  In Vulkan those are all managed through independent interfaces.
There are a number of things in Vulkan that kind of correspond to an OpenGL context in different ways, depending on what you're trying to do.
VkInstance encapsulates access to the Vulkan libraries on the system, including enumerating the global extensions.
VkPhysicalDevice lets you query the hardware capabilities and hardware specific extensions.
VkDevice lets you actually interact with the hardware to do things like allocate memory.
VkCommandBuffer is the interface for setting up and executing draw calls.
However, since you're focused on windows, what you're probably interested in is VkSurfaceKHR.  This encapsulates interaction with a windowing system, including initializing a surface from the OS specific window handles and doing presentation calls.
On Windows, to interact with a window, you need to have an existing VkInstance, and you need to call vkCreateWin32SurfaceKHR and pass it a structure containing an HWND and an HINSTANCE.  If it succeeds then you have a surface to which you can then present images.


Opengl : GLSL utility files We can create header files in C/C++ which we can include in our project using #include directive but when I use this keyword in my shader it gives the error  reserved keyword. If let's say I create an simple text file for adding two numbers and I want to include this file & code in my vertex/fragment shader is it possible?

Yes,  With a certain OpenGL extension, that is possible (thanks to NicolBolas for pointing that out). It is pretty much the same as in C++. Let's assume you have a file util.glsl, vertex.glsl and fragment.glsl, all in the same folder. $^1$
//in util.glsl
float add(float a, float b)
{
    return a + b;
}

Then you can call that function, as if it were in your shader file
//in either vertex.glsl or fragment.glsl
#include "util.glsl"

void main()
{
    float result = add(1, 2);
    ...
}

Your result would then be 3. Of course, if you have the file in a different folder, you need to adjust the path, but again, that is pretty much the same as in C++.
The only caveat is with debugging. Without having tested it right now, as far as I remember compiler errors will not display your util.glsl as the source of your error. Rather it will put the contents of util.glsl at the position, where your include call is and then say you have an error in that line in vertex.glsl / fragment.glsl, so this might be a bit confusing
$^1$Actually, this is incorrect (by default at least). In a project we used it like that, but since I did not do that setup myself, I assume it was either setup to work like that by a collegue or by OpenSceneGraph, which we used. In any case, I cannot (yet) answer this myself. I want to add this part, as soon as I understand it myself. Until then, I will simply link to a similar question with answer from NicolBolas, which hints at what you have to do: https://stackoverflow.com/questions/10754437/how-to-using-the-include-in-glsl-support-arb-shading-language-include


How to derive a perspective projection matrix from its components? This has been haunting me for several days now. I want to find the component that makes up of this 4x4 perspective projection matrix, with $l$(left), $r$(right), $b$(bottom), $t$(top), $n$(near), $f$(far) defining the frustum.

$\left(
\begin{array}{cccc}
\frac{2n}{r-l}&        0&  \frac{r+l}{r-l}&         0\\
0& \frac{2n}{t-b}&  \frac{t+b}{t-b}&         0\\
0&        0& -\frac{f+n}{f-n}&-\frac{2fn}{f-n}\\
0&       0&           -1&         0
\end{array}
\right)$

Here's my approach so far. The first matrix component would just copy $z$ over to $w$ coordinate:

$\left(
\begin{array}{cccc}
    1& 0&  0& 0\\
    0& 1&  0& 0\\
    0& 0&  1& 0\\
    0& 0& -1& 0
\end{array}
\right)$

The second matrix translates the eye ($at = \left(0, 0, 0\right)$) to ($\frac{l+r}{2}$, $\frac{t+b}{2}$, $\frac{n+f}{2}$, the center of the frustum because canonical coordinate is just a cube of size $2$ with its centroid at the origin $\left(0, 0, 0\right)$

$\left(
\begin{array}{cccc}
    1& 0& 0& \frac{l+r}{2}\\
    0& 1& 0& \frac{b+t}{2}\\
    0& 0& 1& \frac{n+f}{2}\\
    0& 0& 0&       1
\end{array}
\right)$

The last matrix just scales the thing so that the frustum fits into the cube of size $2$.

$\left(
\begin{array}{cccc}
    \frac{2}{r-l}&       0&       0& 0\\
          0& \frac{2}{t-b}&       0& 0\\
          0&       0& \frac{2}{f-n}& 0\\
          0&       0&       0& 1
\end{array}
\right)$

As you can see the multiplication of these 3 matrices isn't equal to the perspective projection matrix. What am I missing?

The second matrix translates the eye [...]

You don't do that in a projection matrix. You do that with your view matrix:

Model (/Object) Matrix transforms an object into World Space
View Matrix transforms all objects from world space to Eye (/Camera) Space (no projection so far!)
Projection Matrix transforms from Eye Space to Clip Space

Therefore you don't do any matrix multiplications to get to a projection matrix. Those multiplications happen in the shader, where you do $Projection\cdot View \cdot Model$$^1$ Matrix (for example in the vertex shader to specify your position output).

Also, remember that a perspective projection changes angles (i.e. parallel lines won't be parallel anymore). As far as I can see that is missing in your derivation.

Edit

As to how you actually derive it, I'll largely use the explanation byEtay Meiri. It has some additional information and illustration, so you may want to check it, if something seems unclear.

First, your camera is (as mentioned earlier) positioned in the origin.
Now assume, you will only project onto a plane of distance $d$ and the plane you project onto is bounded by the aspect ration $ar$ (that is $ar = \frac{window\text{ }width}{window\text{ }height}$ in positive and negative $x$ direction and by $1$ in positive and negative $y$ direction.

You can now determine $d$ by your vertical field of view $\alpha$ (since looking from the side, your camera, the center at the top of your projection plane and the center of the bottom of your projection plane build a triangle and your vertical field of view is the angle at your camera):

$\frac{1}{d} = \tan(\frac{\alpha}{2})\\
\implies d = \frac{1}{\tan(\frac{\alpha}{2})}$

Now you go about calculating projected points. Assume you have an arbitrary point $v = (v_x, v_y, v_z)$, and you want to calculate the point on your plane $p = (p_x, p_y, d)$. Looking at it from the side again, the triangle with your camera, your projection plane top center point and your projected point is similar to the triangle with your camera, your projection plane top center prolonged to have the same z coordinate, as your point $v$ and the point $v$, i.e. they have the same angles$^2$. Therefore, you can now calculate the projected $p_x$ and $p_y$ coordinate:

$
\frac{p_y}{d} = \frac{v_y}{v_z} \implies p_y = \frac{v_y\cdot d}{v_z} = \frac{v_y}{v_z \cdot \tan(\frac{\alpha}{2})}\\
\frac{p_x}{d} = \frac{v_x}{v_z} \implies p_x = \frac{v_x\cdot d}{v_z} = \frac{v_x}{v_x \cdot \tan(\frac{\alpha}{2})}
$

To additionally take into account, that the projection plane ranges from $-ar$ to $ar$ in $x$ direction, you would add $ar$ to the denominator in order to make the projected $x$ range be $\left[-1, 1\right]$:

$
p_x = \frac{v_x}{ar \cdot v_x \cdot \tan(\frac{\alpha}{2})}
$

If you think about applying this to a matrix now, you need to take into account the division by $z$, which is different for any point with differing $z$ value. Therefore, the division by z is deferred until after the projection matrix is applied (and is done without any code of you, i.e. for OpenGL you'd specify the gl_Position in Clip Space ($\implies$ after projection) and the division is done for you).

The depth test (Z-Test) still needs the $z$ value though, so it needs to be "safed" from the $z$ divide. Therefore you copy your $z$ value to the $w$ component (which is what you got right in your assumption) and end up with the following matrix:

$\left(
\begin{array}{cccc}
\frac{1}{ar\cdot\tan(\frac{\alpha}{2})}&0&0\\
0&\frac{1}{\tan(\frac{\alpha}{2})}&0&0\\
0&0&0&0\\
0&0&1&0
\end{array}
\right)$

The next step is to not project onto a plane, but into a $z$ range of $\left[-1, 1\right]$ (this range is for correct clipping, as is the same range when handling the $x$ and the $y$ coordinate). To be more specific, you don't want all points to end up in that range, but all points between your near and your far plane, so you map $[n, f]$ to $[-1, 1]$.
The resulting range is $2$, so you first scale your near-to-far range to $2$. Then you move it to be $[-1, 1]$:

$
f(z) = A\cdot z + B
$

And now taking into account that we want to safe the $z$ value from $z$ divide, we get to

$f(z) = A + \frac{B}{z}$

Mapping this scaling to $[-1, 1]$ is a little bit of leg work: you know that any point with $z = n$ (on your near plane) will be projected to $p_z = -1$ and any point with $z = f$ (on your far plane) will be projected to $p_z = 1$. This leads to the following equation system:

$
A + \frac{B}{n} = -1\\
A + \frac{B}{f} = 1
$

Solving this for $A$ and $B$ leads to$^3$:

$
A = \frac{-n-f}{n-f}\\
B = \frac{2fn}{n-f}
$

Your third row of the projection matrix must produced the (undivided) $p_z$ (projected) z value. Therefore, you can now choose the individual elements of said row $(\begin{array}{cccc}a&b&c&d\end{array})$ such that the correct $z$ value is produced when multiplying with your point. The correct $p_z$ value is (as established earlier):
$p_z = A\cdot z + B$

Therefore this must be the right hand side of your multiplication. Assume your point to project is $(x, y, z, w)$, then
you must achieve the following:

$
a \cdot x + b \cdot y + c \cdot z + d \cdot w = A \cdot z + B
$

Obviously, your point's $x$ and $y$ coordinate should not influence the projected $z$ coordiante, so you can set $a$ and $b$ to $0$.

$
c \cdot z + d \cdot w = A \cdot z + B
$

Since you know that $w$ for any point is $1$, you're left with

$
c \cdot z + d = A \cdot z + B
$

And thus, you have $c = A$ and $d = B$.

Now your matrix is complete for projection

$\left(
\begin{array}{cccc}
\frac{1}{ar\cdot\tan(\frac{\alpha}{2})}&0&0\\
0&\frac{1}{\tan(\frac{\alpha}{2})}&0&0\\
0&0&\frac{-n-f}{n-f}&\frac{2fn}{n-f}\\
0&0&1&0
\end{array}
\right)$

Obviously, the tutorial works a little differently in projecting with the vertical field of view, so we can take a look at how you can additionally get to that (with the help of Eric Lengyel:

Instead of projecting onto a plane at $z = d$, we will project onto the near plane, and thus get for a point $v = (v_x, v_y, v_z)$ the projected point $p = (p_x, p_y, n)$:

$
p_x = \frac{v_x \cdot n}{v_z}
$

Additionally, you want to map any point with $l\leq x \leq r$ to $\left[-1, 1\right]$, as before.
Thus you get

$f(x) = (x-l) \frac{2}{r-l}-1$

Combine those two and you achieve

$p_x = \frac{2n}{r-l}\left(-\frac{v_x}{v_y}\right)- \frac{r+l}{r-l}$

Now put this (and the term for $y$) into the matrix and you get to the first row, first column being  $\frac{2n}{r-l}$, and the first row, third column being $\frac{r+l}{r-l}$. Since you may assume $r$ and $l$ to be different, here you can see why those two matrices differ. $r$ and $l$ are guaranteed to be the same in the tutorial's matrix and therefore you get $r+l = ar-ar = 0$ in the denominator, making the third row first column (and second column accordingly) $0$.

$^1$Assuming you have Column-Major matrices like in OpenGL$

$^2$For the $x$ calculation, you will need to take a different point of your projection plane of course, but the idea is the same

$^3$The differences of the sign come from how you orient your camera: in your assumption it is along the negative $z$ axis, whereas in the tutorial it is along the positive $z$ axis


Can I use QueryPerformanceCounter to measure single draw or compute call performance? I know I can use QueryPerformanceCounter for measure time for whole single frame. But can I when it comes to OpenGL draw or compute call?

I always assumed that, as on the diagram, CPU waits for GPU to finish so timer would measure approximate time or am I wrong?

As seen in code:

glBindVertexArray(vertexArrayObject);
timer->startCounter();
glDrawElements(GL_TRIANGLE_STRIP, indices.size(), GL_UNSIGNED_INT, 0);
glBindVertexArray(0);
estimatedRenderTime = timer->getCounter();

or

timer->startCounter();
glDispatchCompute(width, height, 1);
estimatedRenderTime = timer->getCounter();

That diagram includes a CPU block titled "wait for GPU". I do not see the part of your code that includes an equivalent command.

Furthermore, even if it did include glFinish/glClientWaitSync/etc, there is no guarantee that the CPU time in any way relates to how much time the GPU spent processing it. glFinish might block on a mutex, thus ending the thread's timeslice. Which means that the thread will start up sometime after that mutex is released. How long after? Who knows, but your QueryPerformanceCounter call will include that time.

If you want to measure GPU time, you should use tools that actually measure GPU time. For example, timer queries. You bracket some commands with glBeginQuery(GL_TIME_ELAPSED, queryObject) and glEndQuery(GL_TIME_ELAPSED). Then you can read the result after some time has elapsed. Like maybe next frame.

And unlike glFinish, this will not absolutely murder your performance ;)


Tracing shadow rays in a scene with mirrors In my real time ray tracer, I shoot primary rays from the eye, and at hit points, I trace to a single light source to determine if the object is shadowed or lit.

Pretty straightforward stuff so far.
However I have recently added perfect mirrors to my scene.
The reflections work just fine.

However, the shadow calculation breaks down!

A shadowed point could still be lit by the light source via a mirror.

Is there an easy way to handle shadow rays towards bounced light?

NOTE: I am not talking about the projection visible in the mirror surface: this shows shadowed and lit objects. But the directly visible scene itself, there are more shadowed objects than there should be, as some of the scene is lit via a mirror.

It depends how you define easy and what kind of constraints you have. The general case of this is rendering caustics but that's probably not what you're looking for if real time is your target.

If your mirrors are always flat as in your demo and you only want to support a single bounce, the easiest I can see would be to reflect your light sources on the other side of the mirror's plane, before you start a frame. Let's call each reflection a virtual light source. Then for each of these, test if the ray between whatever you're shading and the virtual light source hits inside the mirror (simple plane/ray test). If it does hit then you trace the actual shadow ray to the mirror and the rest of the shadow ray from the mirror to the actual light source.

This obviously won't scale well to many mirrors. I think it could be adapted to 2-3 bounces if the mirror and light count is low. The number of virtual lights could quickly grow out of hand though.


Find the longest straight line between two points on surface of polygon My shape is a slightly concave polygon, and I'd like to know the maximal diameter. I imagine a straight line between two points on the surface of the polygon, such that the line does not pass outside the polygon.

Is there a general algorithm for this?

In my case I am interested in 2D. My shapes are tumors in medical images. So we can also assume:
1 the centroid is always inside the polygon.
2 a high vertex density, i.e. the next vertex is always close to the previous one.

I don't have an exact answer for this, as the answer is far from trivial. I would suggest that you have a look into computational geometry as this clearly is a visibility problem - my guess is that a solution already exist. My own idea would be: for each line segment in polygon find the visible parts of the other line segments and then pick the pair of points that are furthest apart. Inspirational link: Wikipedia on 'visibility polygon'.


Can microfacet BRDF (including ggx) represent perfect mirror? Perfect mirror's brdf is simple,

$F\frac{\delta(\omega_i-\omega_r)}{|\cos(\theta_r)|}$

as in http://www.pbr-book.org/3ed-2018/Reflection_Models/Specular_Reflection_and_Transmission.html

As shown in several articles, microfacet brdf can have zero roughness by definition then they should be able to represent a perfect mirror. But I cannot derive them to above correct perfect brdf.

For instance, when I put zero roughness into GGX model,
(https://www.graphics.cornell.edu/~bjw/microfacetbsdf.pdf )

D(m) = D(H) goes to infinity by divided by 0 and G is just one. However, the brdf I got is,

$F\frac{DG}{4|N\cdot V||N\cdot L|}$

Then rendering equation is,

$\int F\frac{D(H)G(L,V, H)}{4|N\cdot V||N\cdot L|} \cos\theta_id\omega_i = \int F\frac{D(H)G(L,V, H)}{4|N\cdot V|} d\omega_i$

If this was correct, $\frac{D(H)G(L,V,H)}{4|N\cdot V|}$ should be a dirac delta function. But I don't think so.

Where am I wrong? How can I derive a perfect mirror from microfacet brdf?

UPDATE

I concluded that Cook-Torrance's brdf can not represent a perfect mirror. The equation has some small value greater than zero when H $\neq$ N even if roughness is zero. So, normalization factor $4|N\cdot V|$ should be not be removed.

Correct me if I was wrong.

If this was correct, $\frac{D(H)G(L,V,H)}{4|N⋅V|}$ should be a dirac delta function. But I don't think so.

Actually, you're close to your answer - you just are trying to find out, what the assumption was in the very beginning - if you're talking about a specular BRDF. The term  $F\frac{DG}{4|N⋅V||N⋅L|}$ only works, if you start with the precondition, that you're dealing with a perfect mirror, otherwise this would be an integral itself. Have a look at PBR Diffuse Lighting for GGX+SmithMicrosurfaces by Earl Hammon Jr., where explains how to get to the specular BRDF. Especially have a look at slide 29:

Microfacet BRDF is a perfect mirror

I.e., light reflects if and only if $m = H$

Mathematically, BRDF is a scaled dirac delta $\delta_m(H, m)$

So the perfect mirror is your model in the beginning$^1$ - but only for the specular BRDF!

If you are trying to see, if including the diffuse BRDF into your BRDF is a perfect mirror, then this assumption does not hold any more and thus you don't have the dirac delta function.

$^1$ Note that he speaks about a microfacet being a perfect mirror. However, if all your microfacets are perfectly aligned, then your microgeometry "equals" your macrogeometry


Why is the back of a perspective frustrum larger than the front? I'm following this tutorial on the perspective projection.

Question: If the point of a perspective projection is to create the perspective effect (where objects faraway appear to be smaller):

then why does it generate a frustrum in which the back is larger than the front? Should it be the other way around?

It might help to think of it this way:

Both the near plane and the far plane are the size that will fit onto the screen you are viewing on. The further away something is, the bigger it can be and still fit on the screen. Close up, a playing card can fill the whole screen, but in the distance, an entire building can fit on the screen.

Consider the example image:

If a playing card exactly fills the near plane, then you will be able to fit 4 playing cards on the far plane. This reflects the fact that when a playing card is twice as far from the camera, it appears to have half the height and width.

Think of the near plane and the far plane as simply the area that will fit on your screen. The further away you point your camera, the more will fit on the screen. This matches up with the fact that things look smaller in the distance - this means you can fit bigger things on the screen if they are further away.


Is there way for polygon decomposition by thickness? Here is an example

dots representing coordinates of pixels

added more representative example

added real example

added main problem

It is a bad idea to try to abuse clustering algorithms for this. In particular k-means will not cut vertically, nor consider rectangles.

What you need to do is a trivial axis-aligned corner detection.it does not get much simpler than that!

You begin on the left, and whenever the location of the topmost pixel changes, a rectangle is complete.


How to get unique nearest neighbour? There's already something called K-nearest neighbour algorithm with gives nearest neighbour to points. But what I want is unique neighbour which is not shared by any other neighbour.
I've implemented this logic but it's very slow. You can review my code here.

EDIT: Let's assume there're 2 galaxies with 5 stars in each. GalaxyA neighbour list(let's call it closestNeighbourList) in GalaxyB starting from closest to fartherest...

star 0: [4, 1, 0, 3, 2]

star 1: [2, 0, 4, 3, 1]

star 2: [2, 1, 3, 0, 4]

star 3: [0, 3, 2, 4, 1]

star 4: [0, 3, 1, 4, 2]

from these lists default first neighbour list:

star 0: [4]

star 1: [2]

star 2: [2]

star 3: [0]

star 4: [0]

Since I want unique neighbour in GalaxyB, but here you see a problem, star 2 in GalaxyB is closest to two GalaxyA stars 1 & 2 and same for star 0. So these are not unique neighbour as shared by two or more stars. So to overcome this problem what I'm doing first storing all neighbours in a list(closestNeighbourList) then looping over those to check if it's closer to(shared by) some other star then go to next neighbour and when it's find unique neighbour break out of the loop.

after applying unique neighbour algorithm first neighbour list will be:

star 0: [4]

star 1: [2]

star 2: [1]

star 3: [3]

star 4: [0]

After asking around a bit on Twitter, I found that what you're trying to solve seems to be an instance of the assignment problem. In general, the assignment problem is to take two sets and assign elements of one to the other, in such a way that a cost function is minimized.

In your case the two sets would be the stars in each galaxy, and the cost function would be the distances between stars. An optimal solution to the assignment problem would then minimize the total distance between corresponding stars, summed over all the stars in the galaxies.

A classic algorithm for solving the assignment problem is called the Hungarian algorithm. If you google around, you'll some explanations of how it works. There's even a Python module implementing this algorithm, called Munkres.

A warning: this algorithm runs in $O(n^3)$ time, so it will be rather slow for large point sets. You might want to do some further research on fast algorithms for the assignment problem. It may be that you can find a faster, approximate algorithm if you don't require a perfectly optimal solution. Or maybe there are specialized algorithms for the case of point clouds that can do better.


Compression-friendly PNG files How to create PNG files optimized for being compression-friendly? I.e. would it help if image is created (mostly) from 8x8 unicolor blocks?

PNG format is lossless format where for compression the image is first "filtered" and this filtered image is then passed to DEFLATE lossless compression algorithm. The purpose of filtering stage is to make the image more compressible by DEFLATE and current method uses delta-compression from previously decoded pixels.

So if your plan is to pre-process the image in some lossy way, then if you can reduce the deltas so that the following entropy encoding can benefit from it, then you get better compression ratio. For example "blockifying" the image as you suggested would only require more storage for the top-left pixel in the block while the deltas for the remaining pixels would be zero, which DEFLATE can compress very efficiently. This same would apply to any continuous constant color regions.


"whiteness" in center of bright colored lights - what is it called? When a source of colored light is very bright, it's center appears white. What is the term I need to look for so I can implement this in my shader? I have added an image which is an example of what I mean. Obviously there is also some bloom going on but that alone doesn't cut it. The search results for "opengl glow" don't seem vey promising either, that just gives me more bloom, not white centers.
I have thought about blending a white emission with the desired color like in this question/answer. However, as you can see that turns the emission pink, not red.
So what I'm really after is a tinted light, glowed, with high (color) contrast.

In general this is caused by HDR tone mapping. Tonemap curves typically decrease saturation as the input light gets brighter, so that very bright lights are rendered closer to white on the display. If bloom is rendered in HDR (prior to tonemapping) then the bloom around the light can still be highly saturated since it is of a lower intensity than the light itself, and so doesn't get desaturated by tonemapping as much.
You can see some good examples of this on the UE4 Color Grading and Filmic Tonemapper docs page. Unreal uses the ACES tone mapping curve, which is a pretty good default tone curve that you can easily hook up in your own shader code as well.
That said, lightsabers in Star Wars games are probably a special case visual effect that's tuned specifically to reproduce how they look in the movies. :)


Estimating the area of a triangle-circle intersection I am trying to implement Ray Tracing with Cones (Amanatides 1984). Instead of rays, cones are shot into the scene and intersected with geometry. Since multiple triangles can occupy the cone's aperture, we need to calculate (or rather quickly estimate, since cone tracing makes a lot of approximations anyway) the relative area of the circle that is covered by the triangle. Afterwards, the individual contributions are weighted and summed up.

The author, unfortunately, does not give a lot of detail about his solution. Here is what he writes on cone-plane intersections:

  The spread angle and the angle between the ray and plane computed
  above together indicate how the distance between the center of the
  circle and the edge of the half plane [sic]. Given this distance, the area
  of intersection is computed using a polynomial approximation. This
  completes the intersection calculation for planes.

And then, after projecting a polygon to the plane perpendicular to the
direction vector of the cone:

  We then must calculate the intersection between the projected polygon
  and a circle. This can be accomplished by calculating the distance
  from the center of the circle to each of the edges and then using the
  circle - half plane intersection estimation mentioned earlier.

I found a solution to the problem over at StackExchange. I have ported the code from NowIGetToLearnWhatAHeadIs' answer, and it works fine, but seems pretty complicated to me. I am working with Compute Shaders, so branching is a bad thing, and the solutions rely heavily on it.

What is this polynomial approximation that Amanatides talks about, and how is it to be applied to polygons (espc. triangles)?
Is there any approximation to the problem that will give resonably accurate results (say ±10%) at considerable performance / code simplicity gains?
Working with GPUs, I am interested in an optimized solution that uses min/max over branching, for example. Maybe something like this already exists. Any luck?

Working Towards an Exact solution

Just some quick thought before I must run!

Ok, let us turn the problem on its head. What if one does not calculate the area of the triangle cut by the circle. Instead let's calculate the inverse of this. The area of three segments cut out of the circle. The beauty of this approach is that we can make a single piece of code that we can repeat three times. Of course some of the time the answer will be 0 but that is OK.

Image 1: Let's calculate this problem instead.

Now it turns out we know how to calculate the inverse, it is the segment of a circle.  So we can just say that $A_{int}=A_{circle}-A_1-A_2-A_3$.

Image 2: We know this solution.

The formula for the area of a segment is simply $A_{sector}-A_{triangle}$ and that has a well known solution in literature.

So now all you need to do is find the intersections between the edges and the circle in a space centered on the circle, calculate the angle between those and then calculate each segment. And the only special case is if no intersection exists. I dont know if this is fast but at least code should be somewhat easy to implement.


Simple Two Point Perspective of a Cube I know this question may be a little basic, but still I haven't found an answer for it anywhere.

Let's say I have a normalized cube; vertices at (+-0.5, +-0.5, +-0.5)
If I render it on screen (omitting the Z axis), I'll see a square.

If I rotate it along the Z axis with 45 degrees, I'll see two rectangles:

However, I would like to see it with perspective, so it should look something like this:

What is the matrix multiplication that transfers the original points to the rotated+perspective points?

Your first image employs an orthographics projection, while the second uses a perspective projection. You can look up the perspective matrix derivation in: http://www.songho.ca/opengl/gl_projectionmatrix.html Note that there's a division at the end to account for perspective projection being a non-linear transformation.


Implement own Bend function I'm trying to write a mesh deformer that bends a Cube around an axis like this:

The bend degree in figure A is 90 and something like 35 in B. So if I know my desired bend degree how can I get alpha?

I know that the distance between the vertices v1 and v2 stays the same and that i basically just have to rotate the edge alpha degrees. I can't figure out where the center of the Circle has to be, so that the bend looks organic.

It's easy to work out if you consider not that case but the angle at v3 (if the "cube" were continued past v3). By the time you get to v3, the angle is simply the desired bend angle. (That's not quite right, though: because you've got alpha on the decreasing side, it's 90 degrees minus the desired angle.) You have to split that angle equally among all the segments going along the bend direction, so the angle alpha is simply 90 degrees minus (the desired angle divided by the number of vertices). So for A, where the requested angle is 90 degrees, each vertex gets a third of that angle: alpha is (90 - 30) degrees.

For cube B, if the total bend is 35 degrees, each vertex gets just over 11 degrees, so alpha is just under 79 degrees.

This doesn't generalise to an arbitrary axis, though. It only works for bends like those in your diagram. For a more general (and more useful!) tool, it makes more sense to simply apply a 2D rotation (about the axis) to each vertex independently. Exactly what rotation to apply depends on some design decisions about how the bend should behave when the axis goes through the mesh, and how strong a bend you want to allow. The crucial point is that it's not the same rotation for every vertex: the rotation is proportional to the perpendicular distance from the vertex to the neutral line of the transformation. In your example, the neutral line is the bottom edge of each cube.


What is the accepted method of converting shininess to roughness, and vice versa? Most modern renderers use physically-based materials and their models are often parameterized over roughness. Since this wasn't always the case with renderers, conventional assets often don't have a notion of roughness. Instead, we see "shininess" or "specular power" as a common material parameter.

I understand that there is no exact conversion between the two, but is there a rule-of-thumb / approximate way to get roughness for a material whose specular power or shininess is known?

As you already note, there is no clear cut interpretation/conversion for these values. I think it is even much worse: Depending on your BRDF and internal limitations (like having defined exponents ranging from 2-2048) the interpretation is completely different. Like suggested in the comments, it might be the best to render a series with different values and fit a conversion curve until the value looks intuitive.

A few examples I was able to find some blog posts that mention something about that topic:

At Dontnod entertainment they use a "perceptual linear distribution".
Sébastien Lagarde acknowledges the problem in this blog post and writes a few notes on that.
Brian Karis uses a squared roughness values in this Microfacet BRDF overview. This illustrates also nicely how differently  roughness is used in different Normal Distribution Functions. Blinn-Phong power is here defined as 2/roughness^4 - 2.
Frostbite uses a squared remapping. ie. Roughness =  (1 − Smoothness)^2
Details about it and their entire material system is explained in section 3.2 of Sebastien Lagarde's writeup.
This blog post suggests to define the roughness for a Beckmann distribution from the roughness alpha as:


API or Tools to query state of graphics during gameplay? I’m looking to somehow programmatically query the state of graphics during a PC gameplay session. What I mean by “state of graphics” is, how polygons, textures, lighting and any other scene elements are stored and computed for any particular frame. I’m mainly interested in what the graphics card is doing on a low level.

Is there any need to be game engine specific in this matter, or will all games be drawn to the screen in the same way?

I’m specifically interested in NVIDIA cards if at all possible. I’m not sure if different manufacturers do things differently, but I only have an NVIDIA card.

Are there any tools or APIs that will give me access to this data?

What I mean by “state of graphics” is, how polygons, textures, lighting and any other scene elements are stored and computed for any particular frame.

The closest to what you are asking and that I know of is RenderDoc. I have not tested it myself so far, but some features they list in their documentation that are related to your question are:

Full graphics pipeline state display
Shader source display
Flexible resource inspector
Mesh buffer inspection and visualisation
‘Raw’ buffer inspection for buffers
Texture/render target viewer

  I’m looking to somehow programmatically query the state of graphics during a PC gameplay session.

  ...

  Is there any need to be game engine specific in this matter, or will all games be drawn to the screen in the same way?

I am not sure here if you are asking to dissect the graphics state of a commercial game or software that is not written by yourself. If so, there is no guarantee that RenderDoc can capture data but it is possible. See for example this issue on their GitHub page, where the author says:

  However I want to be clear that I cannot and do not support capturing 3rd party programs that you do not control. It generally works but for obvious reasons I don't provide any help with problems...

As stated in this section of their documentation, RenderDoc uses a "man-in-the-middle" approach to get the data. So it intercepts any calls to the graphics API (OpenGL, DirectX, Vulkan) of the executed program, gathers the data it needs, and passes it along to the API afterward.


Resolution issue of generating a PNG icon for macOS menu bar Wonder if anyone has experienced this. When generating png image icons for macos. its recommended at 19x19 pixels. However, based on that, the icon (shield) that is generated is pixellated compared with the next in line. I have tried using 38x38, which effectively doubles the pixels. It looks much finer in preview but when attached, it because a large icon cropped off the bottom. Are there are specifics to generating a retina compatible icon for mac status bar?

The issue is the difference between pixel and point sizes. On macOS and other Apple platforms, the user interface is measured in points, which don’t necessarily map one-to-one to pixels; on a Retina screen like the one you’re using, 1 point is 2 pixels. Since there’s no way for the system to know whether your image’s scale is the same as the screen’s, it’s assuming that each pixel in your larger image is meant to be one point.

One way to resolve this would be to explicitly set the size property on your NSImage to the point size your image is supposed to be drawn at, i.e. 19×19; you’d have to handle loading different images for 1x and 2x screens on your own, though, which is inconvenient. A better way would be to use an asset catalog in your project, which will let you specify assets for 1x and 2x screens and allow you to load the appropriate image by name.

As Simon F pointed out, future questions in this vein probably belong on Stack Overflow—it’s more about API usage than graphics concepts.


What does texture resolve mean? In the context of render targets or textures, what does "resolve" mean?
For example: To resolve a color texture.

From my understanding, it seems to mean, "copy but process/convert at the same time", but I can't seem to find a good definition for it anywhere.

I don't know about other contexts, but for DirectX resolving a texture means blending multi-sampled texture into a non-multisampled one. For simple scenarios this is usually done automatically by the output merger, but is often needed to be done explicitly (e.g. ResolveSubresource) when using multi-sampled render target as an input for a next render pass (e.g. post-processing). Reasons being both performance and lower complexity of the following pass shaders.


How much precision do I need in my G-Buffer? I'm in the process of working out how to pack all the information I need for a Physically Based Deferred Renderer into a G-Buffer without using an obscene amount of render targets.

What I have so far is 4 3-part vectors:

Albedo/Diffuse
Normal
Tangent
Position

And 4 single components

Metallic
Roughness
Height
Ambient Occlusion

A naive approach is to bundle one of the single components into the alpha (fourth) channel with one of the 3-part vectors, which is my current line of investigation. However, given that four 4-channel full precision floating point render targets isn't small I understand it's common to use half precision and even smaller representations to be more memory conscious.

What I'm asking is: which components can I safely cut precision down on without losing quality, and by how much?

First of all, you don't need position in the G-buffer at all. The position of a pixel can be reconstructed from the depth buffer, knowing the camera setup and the pixel's screen-space xy position. So you can get rid of that whole buffer.

Also, you don't ordinarily need tangent vectors in the G-buffer either. They're only needed for converting normal maps from tangent space, and for parallax mapping; these would be done during the G-buffer fill pass (when you have tangents from the mesh you're rendering), and the G-buffer would only store normals in world or view space.

Material properties like colors, roughness, and metallic are usually just 8-bit values in the G-buffer, since they're sourced from 8-bit textures. Same for AO.

Height is also not needed in the G-buffer unless you're going to be doing some kind of multi-pass blending that depends on it, but if you do need it, 8 bits is probably enough for that too.

Normals can be benefit from being stored as 16-bit values rather than 8-bit. Half-float is okay, but 16-bit fixed-point is even better, as it gives you more uniform precision across all orientations (half-float is more precise near the axes and loses some precision away from them). Moreover, you can cut them from 3 components down to 2 using octahedral mapping.

So, at the end of the day, a minimal G-buffer might look like:

Material color + metallic: RGBA8
Octahedral world-space normal + roughness + AO: RGBA16

and that's all! Only 12 bytes per pixel.

Alternatively, you could use an RG16 buffer for the normals, and move roughness + AO into a separate 8-bit buffer. That would give you some room to grow should you eventually need more G-buffer components of either 8-bit or 16-bit sizes.


Honouring Depth Test with Stencil Test I'm using OpenGL's stencil test to carve out a semicircular hole in a transition frustum with a cylinder oriented perpendicularly. However as one can see below, while this objective is achieved, the cylinder is still visible through the frustum which shouldn't be the case.

I'm using the following code fragment that I found at
https://en.wikibooks.org/wiki/OpenGL_Programming/Mini-Portal

glClear(GL_DEPTH_BUFFER_BIT);
glEnable(GL_STENCIL_TEST);
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
glDepthMask(GL_FALSE);
glStencilFunc(GL_NEVER, 1, 0xFF);
glStencilOp(GL_REPLACE, GL_KEEP, GL_KEEP);  // draw 1s on test fail (always)

// draw stencil pattern
glStencilMask(0xFF);
glClear(GL_STENCIL_BUFFER_BIT);  // needs mask=0xFF
DRAW_CYLINDER ();

glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
glDepthMask(GL_TRUE);
glStencilMask(0x00);
// draw where stencil's value is 0
glStencilFunc(GL_EQUAL, 0, 0xFF);
/* (nothing to draw) */
// draw only where stencil's value is 1
glStencilFunc(GL_EQUAL, 1, 0xFF);

DRAW_FRUSTUM();

glDisable(GL_STENCIL_TEST);

Moreover I've found that the results are insensitive to the parameters of the glStencilOp  and DepthMask commands.

I seem to vaguely remember from several years ag that a multi-pass rendering may be required. If so, could someone point me to how to accomplish this with the proper set of command parameters?

thanks in advance.

This is an example of what I'm expecting - The cylinder should cut a hole through the frustum. I've rendered it here by trimming the black cylinder within the frustum so that it just just out past the frustum surface.

When cylinder and frustum intersect the hole will be a view into the internals of the cylinder. The hole is where external of the cylinder occlude frustum and internal of the cylinder does not occlude the frustum.

Knowing this you should simply do the following to find the surface (or rather volume) made from the hole.

Render frustum without color and set depth accordingly. Set a stencil bit where the cylinder (external) occludes the frustum, without setting new depth. Clear the previously set bit where the internal of the cylinder occludes the frustum, without setting new depth.

Alternate between internal and external using CullFace.

The stencil mask you now have is the surface where the frustum hole is. Render the frustum (in color) masking it with the stencil. Make sure to use LEQUALS depth test to allow the frustum to render on top of itself. Voila. Note that the depth buffer holds the value of the unmasked frustum so If you need to render something within the hole you would have to render the whole scene again and mask it to only render in the hole unless depth test passes against the frustum. Left as student exercise.


Light field rendering for 3d software? Is there any 3d software that supports rendering an artificial scene to a light field image?

With that I mean an image capturing light from more than one point in a scene, more lika a spherical volume of evenly distributed points.

There is research being done by for instance P Debevec for Google VR that does this for physical scenes with an expensive camera rig. I would like to be able to render the same output but from an artificial scene, in for instance 3dsmax. And then preferably use this in for instance Unity 3D.

Would be awesome for a Myst-like game with high fidelity ray traced graphics instead of low-poly rasterized real time graphics. But I guess animations would be almost out of the question. It should at least in theory be easier to incorporate animations in cgi-light fields than in real photos.

Is there any 3D software that supports rendering an artificial scene to a light field image?

I took a look at Myst and realMyst, and found this YouTube video: "LightField synthesis & realtime render in Unity - sneak preview (raw footage)" with accompanying background introductory information from Frooxius on Reddit. You can see the pipeline he used to convert lightfields, though copying it may be a challenge. He has obtained pretty good results.

So the answer is yes.

  I guess animations would be out almost of the question. It should at least in theory be easier to incorporate animations in cgi-light fields than in real photos.

It's an interesting experiment but the scene is baked, adding characters or new objects will kind of look like cutting out one photograph and pasting onto another - thus what you hoped to gain in speed is lost trying to smooth the two scenes together.

To walk into a scene and see a moving object you essentially need to create a dynamic 'lightfield movie' so the moving object can move normally and then you simply walk/look around the dynamic lightfield. That will be somewhat computationally intensive but most of all it will take a lot of memory.

Check out Frooxius' video and let me know if that's the look you were hoping for.

This webpage: "Light fields – the future of VR-AR-MR" by Mike Seymour (May 26, 2015) says:

  "The Octane renderer has plugins for a range of products from 3DsMax to Maya and even Nuke.".

There's mention of OTOY and on their website the latest announced is: "OTOY and Epic announce OctaneRender® 2019 for UnrealEngine 4", their DEMO version is free, the least expensive paid version is U$400.


What is this graphical effect called? I was watching this trailer:
https://www.youtube.com/watch?v=pWh5388AEHw
and at 1:22, the player used a magic trick that created a sphere that warped the projection of the scene.

Does anyone know what is this effect?

I don’t think there’s a formally established name for it, but it’s generally known as distortion, warping, or refraction. It works by taking an already rendered version of the current frame, sampling it with warped/stretched texture coordinates, and, usually, compositing the result back in with the rest of the scene. One of the first games I know of that used it was Half-Life 2, for an effect when the Strider enemies fired their cannon:

For an example of what this looks like in a modern game engine, check out Unreal’s documentation.


Calculating the angle between two polygons For my application, I want to render models as polygonal surfaces in 3D space and have edges that are bent "outwards" to have a solid line and those who are bent "inwards" to have a dotted line. So if I look from the top of the edge if they "bend towards me" they are bending inwards, if they bend away from me, they bend outwards.

For this, I need to calculate the angle between two connected triangles.
How can I calculate this angle? How can I define if it is bent outwards or inwards (looking from the top it would always bend downwards if the angle is >180 and inwards (so up) if the angle is <180, but how can I calculate this?

I suggest computing the normal vector for each polygon and compute the angle between the normal vector of one triangle and the normal vector of a plane perpendicular to the other surface that passes through the common edge.

See the following illustration, where the red arrows are the normal vectors of the red polygons. The blue vector is the plane perpendicular to the left polygon that passes through the edge common to both polygons.

If your polygons are planar, then you can compute the normal for any polygon ABC by computing the cross product AB x AC.

To obtain the blue vector, take the cross product of the normal of the left polygon and the vector that is the common edge.

The angle you're looking for is formed between this blue vector and the normal to the other polygon (the red vector on the right in the diagram).

You then compute the cosine of the angle between two vectors u and v by taking their dot product, then dividing by their magnitudes.

Image taken from here.


How to convert from Object space into World space (exercise from 3D Math Primer book) This is not homework. I'm self studying Computer Graphics, using the book "3D Math Primer for Graphics and Game Development" (2nd edition). So there is the exercise 6 in chapter 3 which I can't figure out how to solve exactly. It goes like this:

"Assume that the robot is at the position (1, 10, 3), and her right, up, and forward vectors expressed in upright space are [0.866, 0, −0.500], [0, 1, 0], and [0.500, 0, 0.866], respectively. (Note that these vectors form an orthonormal basis.) The following points are expressed in object space. Calculate the coordinates for these points in upright and world space.
(a) (−1, 2, 0) (b) (1, 2, 0)
..."

Now I know that in order to convert from Object space to world space I have to first convert into inertial/upright space by performing a rotation and then into world space by performing a translation. So I assume that that the point (1,10,3) is expressed in world space coordinates. What I don't understand is which one is the matrix I have to use to do the rotation on point (-1,2,0)? I understand conceptually what is going on but I don't know which operations to do here. Help is greatly needed and will be appreciated. Thanks in advance.

For others who might have this question, here a perhaps more straight forward numeric answer (I'm now working myself on this book as well). Consider that:

We are given object space coordinates that need to be transformed into upright and subsequently world space coordinates.
We know that a vector $\vec{v}$ can be represented as a linear transformation of its axises in relation to the set of basis vectors $\vec{p}$, $\vec{q}$, $\vec{r}$, when these are orthonormal (perpendicular to each other and with length $l = 1$)
The equation to represent this is thus: $\vec{v} = v_{x}p + v_{y}q + v_{z}r$
Given the basis vectors we can computed this for each object reference using the above equation. So, the first example would be:

$\vec{u} = -1 \begin{bmatrix}0.866\\ 0\\ -0.500 \end{bmatrix} + 2 \begin{bmatrix}0\\ 1\\ 0\end{bmatrix} + 0 \begin{bmatrix}0.500\\ 0\\ 0.866\end{bmatrix} = \begin{bmatrix}-0.866\\ 2\\ 0.500\end{bmatrix}$

Then, to compute this in world space, you simply need to add your world space reference to the upright vector. Meaning:

$\vec{w} = o + u$

For the first example in the book that would be:

$\vec{w} = \begin{bmatrix}1\\ 10\\ 3\end{bmatrix} + \begin{bmatrix}-0.866\\ 2\\ 0.500\end{bmatrix} = \begin{bmatrix}0.134\\ 12\\ 3.500\end{bmatrix}$


Skybox in a Ray Tracer I have implemented a sky rendering model in my ray tracer which saves the color of the sky to an image. I was wondering how I can render the sky dome and texture map the image on to it.

Do I render the sphere at the center of the environment and add the image to the inside of the sphere? How would I add a texture to the inside of a sphere as opposed to the outside in code? Do I just reverse the normals?

I'm not entirely sure if I understood the question, but it seems like you want to implement environment map illumination in your ray tracer (you seem to be thinking in real-time, though). I will approach the general solution for offline renderers without assuming anything about the scene except the environment sphere.

This is generally done by considering your environment as a light source. Let's say that you use a sphere with a radius big enough to contain your scene. Then, you sample it as you would sample an area light source. You can think of this sphere as a textured light source.

The contribution of the direct lighting on the radiance leaving a point $x$ on the direction $\Theta$ would be:
$$
L_{\text{direct}}(x \rightarrow \Theta) = L_{\text{lights}}(x \rightarrow \Theta) + L_{\text{env}}(x \rightarrow \Theta)
$$

Where the environment map contribution is:

$$
L_{\text{env}}(x \rightarrow \Theta) = {\int_{\Omega_x} L_{\text{tex}}}(x \leftarrow \Psi)f_r(x, \Theta \leftrightarrow \Psi)V(x, \Psi) \cos(\Psi, N_x)\, d\omega_{\Psi} \qquad (1)
$$

Note that, here, $\Psi$ are directions to the sphere, $V(x, \Psi) = 1$ if and only if the sphere is visible from that direction and $V(x, \Psi) = 0$ otherwise, $f_r$ is the BRDF and $L_{\text{tex}}$ is the color on the texture.

Directions $\Psi$ can be generated with a parameterization of the sphere. If you want something simple, then this is enough, just treat it as a textured area light and emit whatever color is on the texture on the sampled point. If you want something more elaborate, consider the rest of the text.

With this said, environment mapping can be inefficient if not implemented with care.

Also, I am assuming you only implemented area lights that emit uniformly, so it was okay to sample its area uniformly. However, it is clear that the sphere is a light source where some parts contribute more than others since the colors vary on the texture. This, combined with the fact that the sphere occupies the entire solid angle around a point (instead of the hemisphere that you usually sample), skyrockets the variance of the estimator of $(1)$. The visibility term $V(x, \Psi)$ further complicates things regarding variance, depending on your scene (if it very exposed or not).

In order to sample and estimate $(1)$, you have to consider:

Parameterization of the sphere: You need to decide how to parameterize your sphere. You need to have a space where you can generate random points and map to a point on the sphere to get a direction $\Psi$ and the color from the texture. You can just use typical the latitude-longitude parameterization.

For more elaborate, better distributed parameterizations: paraboloid parameterization [page 4]; concentric-map parameterization.

PDF $p(\Psi)$ used for sampling the sphere: It is possible to reduce the variance that I mentioned earlier. You can importance sample only using the term $\cos(\Psi, N_x)$ (i.e. cosine lobe sampling), but even so it is possible to do better than that. If the BRDF $f_r$ is simple, you can sample the product of the BRDF with $\cos(\Psi, N_x)$.

There are other methods. In [Kollig, Keller; 03] a PDF is built from the 2D array of the texture itself. This way, it is possible to get more samples from directions from where the map contributes more. A PDF from the product of this with the BRDF would yield the best results considering a compromise between the sampling cost and actual variance reduction.

For a more elaborate and adaptive solution, check [Agarwal et. al, 03].