Tag Archives: Math

Faster Array Sort in Javascript

Introduction :

Based on Eugene(inspirit) post about Faster Array Sort function in Flash, I ported his test code into javascript.
First of all, I’m mainly using JS for scripting into Adobe After Effects, Photoshop, … but not so much for web anyway. That being said I’m not a javascript guru, so bare with me if I did mistake, I took his code and just changed it a little bit so it would work in JS.

I still can’t make the “Flash Sort” (which seems to be the fastest one on AS) to work w/ JS. I don’t know what I’m doing wrong, if anyone has an idea ?

[UPDATE] Thx to MrDoob, “Flash Sort” works now !! I also add the check function and it seems some sorting still not working quite well.


Download Source Code :



Stats


Firefox

*******************************************
*******************************************
INFO
10 000 elements
User-agent header: Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10 ( .NET CLR 3.5.30729; .NET4.0E)
——————————————————————–

JS BUILD IN SORT
Time : 18 ms
Sorting is OK
——————————————————————–

QUICK SORT + INSERTION SORT
Time : 9 ms
Sorting is wrong
——————————————————————–

3 WAY QUICK SORT
Time : 11 ms
Sorting is wrong
——————————————————————–

NON RECURSIVE QUICK SORT
Time : 15 ms
Sorting is OK
——————————————————————–

OPTIMIZED NON RECURSIVE QUICK SORT
Time : 16 ms
Sorting is OK
——————————————————————–

NON RECURSIVE QUICK SORT 2
Time : 13 ms
Sorting is OK
——————————————————————–

FLASH SORT
Time : 6 ms
Sorting is OK
——————————————————————–

IE 8

*******************************************
*******************************************
INFO
10 000 elements
User-agent header: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.0; Trident/4.0; SLCC1; .NET CLR 2.0.50727; Tablet PC 2.0; .NET CLR 3.5.30729; .NET CLR 3.0.30729; .NET4.0C; .NET4.0E)
——————————————————————–

JS BUILD IN SORT
Time : 88 ms
Sorting is OK
——————————————————————–

QUICK SORT + INSERTION SORT
Time : 34 ms
Sorting is wrong
——————————————————————–

3 WAY QUICK SORT
Time : 47 ms
Sorting is wrong
——————————————————————–

NON RECURSIVE QUICK SORT
Time : 49 ms
Sorting is OK
——————————————————————–

OPTIMIZED NON RECURSIVE QUICK SORT
Time : 42 ms
Sorting is OK
——————————————————————–

NON RECURSIVE QUICK SORT 2
Time : 49 ms
Sorting is OK
——————————————————————–

FLASH SORT
Time : 30 ms
Sorting is OK
——————————————————————–

Chrome

*******************************************
*******************************************
INFO
10 000 elements
User-agent header: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US) AppleWebKit/534.3 (KHTML, like Gecko) Chrome/6.0.472.63 Safari/534.3
——————————————————————–

JS BUILD IN SORT
Time : 13 ms
Sorting is OK
——————————————————————–

QUICK SORT + INSERTION SORT
Time : 4 ms
Sorting is wrong
——————————————————————–

3 WAY QUICK SORT
Time : 3 ms
Sorting is wrong
——————————————————————–

NON RECURSIVE QUICK SORT
Time : 3 ms
Sorting is OK
——————————————————————–

OPTIMIZED NON RECURSIVE QUICK SORT
Time : 3 ms
Sorting is OK
——————————————————————–

NON RECURSIVE QUICK SORT 2
Time : 3 ms
Sorting is OK
——————————————————————–

FLASH SORT
Time : 3 ms
Sorting is OK
——————————————————————–

Adobe After Effects

*******************************************
*******************************************
INFO
10 000 elements
OS : Windows Vista 6.0 Service Pack 2
——————————————————————–
JS BUILD IN SORT
Time : 291 ms
Sorting is OK
——————————————————————–
QUICK SORT + INSERTION SORT
Time : 237 ms
Sorting is wrong
——————————————————————–
3 WAY QUICK SORT
Time : 251 ms
Sorting is wrong
——————————————————————–
NON RECURSIVE QUICK SORT
Time : 287 ms
Sorting is wrong
——————————————————————–
OPTIMIZED NON RECURSIVE QUICK SORT
Time : 250 ms
Sorting is wrong
——————————————————————–
NON RECURSIVE QUICK SORT 2
Time : 298 ms
Sorting is OK
——————————————————————–
FLASH SORT
Time : 281 ms
Sorting is wrong
——————————————————————–

Pixel Bender : “ft-Filmic Contrast” for After Effects

Introduction

A one slider plugin that gives a very compelling filmic contrast “look” to your footage.  Partially based on Ken’s Perlin Gain function & Roy Stelzer’s presentation



Download & Sources


How to install it ?


Just copy the .pbk file into your “Support Files” folder in your AE install directory

Donate

How to convert a Lightprobe into the 9 spherical harmonics coefficients

Here is a tutorial on how to convert your own Light Probe into the 9 coefficients needed into my ft-SSIBL plug-in (Screen Space Image Base Lighting).





Links :




I’m sorry for the poor sound, I hope you will still be able to understand !

Rotating Normals from a Normal pass

RotateNormal is a  group node inspired from Roy Stelzer (2D TD at Double Negative) “2.5D Relighting inside of Nuke” presentation.

This node setup allow you to offset your normal pass on the X,Y,Z axis. It could be use for several cases (relighting is one of them for sure, so I thought I would share this node. All you have to do, is to “Append” this node in your blend file and your are done. It use a normal pass as input, and would output the new normal pass.

Feel free to use it as much as you want 🙂

Download RotateNormal Blend File

2.5D relighting in compositing with Blender (using spherical harmonics)

Introduction

About a year ago, I was watching a great presentation at the Nuke Master Class by Roy Stelzer (2D TD at Double Negative) about “2.5D Relighting inside of Nuke”. There is 3 videos which you can download from The Foundry and also files which goes with. I recommend you to watch those videos especially if you are not familiar with relighting in post-production.

What Roy did, is using a paper from Siggraph 2001 called “An Efficient Representation For Irradiance Environment Maps“.

“An Efficient Representation For Irradiance Environment Maps”

This paper cover how to do Environment Lighting based on Angular Map (or light probes, or HDRI map, whatever you want to call it) but without using those map for computation. Odd you said ? Yes sure !
They develop a technique using Spherical Harmonics to simplify an HDR Angular Map to only 9 coefficients !! That means after their process, you only have to do a few multiplication with those 9 coefficients and then you are done !  Check out the comparison  :

left is a standard rendering, right is using the 9 parameters. Grace Cathedral Light Probe was used for this rendering http://www.debevec.org/Probes/

If I’m not mistaking, there is less than 1% of error between both rendering, and of course you can image that the second one goes much much faster 🙂

Please visit there website and presentation for more information about it :

What did Roy ?

In his demo, Roy shows the use of  the irradiance only of a Angular Map. This means he will get all the HDR Luma intensity of the map (no color variation). Once you have the 9 coefficient, the operation is pretty easy and so it compute very fast. The operation looks something like this :

color = c1 * L22 * (x2-y2) + c3 * L20 * z2 + c4 * L00 – c5*L20 + 2 * c1 * (L2_2 * xy + L21 * xz + L2_1 * yz) + 2 * c2 * (L11 * x + L1_1 * y + L10 * z)

Where c1, c2, c3, c4 and c5 are 5 constant number given in the paper. X, Y, Z are float numbers from your normal pass (X2 means x*x ; xy means x*y ; so on … ). All the L22, L20, …. variables are the 9 coefficients)

So as you can see, this is not a really complicated operation and it does compute really fast. Running this on each pixels would return a kind of light map (irradiance) which you can use to ADD to your original color map.

What did I do ?

As I did for the Lift/Gamma/Gain the first time, I tried to reproduce this formula with the “Math Node” of Blender. So for that matter I did use the EXR file (render passes) provided by Roy in his demo, and only kept the Normal and AO passes.

Blend File here

This is not as fast as it could be, the render time for a 1920×1080 is around 1.5 second (well for HDR environment lighting we have seen worst ^^). There is several reasons for this to be slow, but I’ll come to that later.
Note that for this example, I did use the Grace Cathedral Light Probe value and not Roy’s light probe.

I was kind of happy of the rendering though, but a bit disappointed to only get Luma value when environment maps have so much information about colors as well ! (you thought the previous example was a mess with nodes, wait for the following one 😉 )
UPDATE : I was totally wrong 🙂 !!! the only reason why I only get Luma (or actually greyscale) is because I used Math node. I thought it was able to do the operation on any kind of input, but actually it does it on only one composant. So the vector operation never happen :p. I just figure it was possible by trying this same formula in another shader language (pixel bender) and see color happening ^^ . So my bad, Color works too, and I’m not sure to know the difference between the vectors or the Matrices in this case, except using the formula with vectors is much faster ! (I’ll change the blend file later)

So I took a closer eye to the paper, and especially to the example they provide, and I found out that their filter wasn’t only generated coefficients, but also Matrices !!! This means you can do the operation with 9 coefficients to just get the irradiance of the environment or do a similar (but a bit more complex) operation with 3 4×4 matrices (red,green,blue) !
I guess the obvious reason Roy didn’t go for this solution was because the computation is more slower, and he didn’t really need it since he is doing a kind of 3 points lighting in his example.

As I said the math are a bit different ! Here is the formula by using the 3 matrices :

n = worldNormal;
color.red = dot(n , matriceRed);
color.green = dot(n , matriceGreen);
color.blue = dot(n , matriceBlue);

Ok so while this might look more simpler on paper, remember the matrices are 4×4 and if a dot product is quite simple, it is not the costless operation too :). Here is what it looks like in Blender with “Math node” as well :


Blend File here
Again, due to the heavily use of Math node, I believe that 3 second is not too bad, but I’ll come back to that later. Also the node I use to rotate the normal pass, is using some math that might slow the render a bit too and not absolutely necessary

This shows that the technique is working pretty well, but probably not production ready as it is in Blender since we are missing a few thing to make this work smoothly.

What would we need in Blender for this to be more efficient ?

  • More “Input” nodes : this might be one of the reasons why the rendering is slow down a bit. Because actual “Input node” only works between 0-1, and the matrix number were between -n and n, I had to find a trick. For this I used the “Math node” for each number of a matrix. Setting it to “Add”, enter the value in the first input, and setting the second input to 0.0. So the output would be equal to the first input. I only did that because I couldn’t figure another way to have negative and positive values in Blender compositing in another way. But this also mean that the compositor tell blender to do an operation for each input, can’t say it’s much optimized 🙂
    • Input Value that goes between -n and n
    • Vector4 Input (right now you can only use Vector3, but you usually need to work with alpha)
    • Matrix Input (could even be useful to do some quick and dirty convolution)
  • Expression node : ok now, I’m dreaming for this one ! And this is IMO probably the main reason why this is so slow. I believe that each time I’m using a Math node, Blender does treat them individually. Which makes sense though, but it probably make a lot of exchange with inputs, outputs, inputs again, outputs again, ….
    I would believe that sending the entire operation at once to the CPU (or whatever) and getting it back at once would make things different and much faster (but I might be wrong on this one !?)
    Anyway the other reason for this node would be … well seriously, have you seen the mess with all the nodes ?!?
    So a simple field, even just interpreted by python would be great !!!!
  • Math with Vector : Maybe I did something wrong, but I couldn’t do a “dot product” between vectors, which is one of the reason why I have all those nodes. I’m doing the entire “dot product” by hand and this is heavy.
    I wish Math could be use with any kind of input. But again, maybe I’m doing something wrong here
  • Passes : we need more passes! For this example we need an Object Normal Pass rather than a World Normal Pass. Probably not to much to do though, the only problem I have with the Passes system today is that they are all hardcoded in Blender, which makes it complicated to create a custom one like you would have in Maya.
    I’d like to be able to assign a material overall to a define passes, but yet I would probably need to write shaders, which implicate the needs of writing shaders as well for the renderer. I guess OSL will fix that in a future if it gets implemented one day
  • Better support for EXR : beside this really annoying, flip node you have to add when working with other packages (I know flip node is nothing, but when working with 2K or 4K it is not the same deal, especially when the composite gets complex, you want to save any operation you could) , but I believe anyone is aware of this now, the other lack of EXR in Blender is the passes support. it doesn’t support custom passes coming from other package. Roy provided his Nuke script, with all the EXR file so you could play with it. But when I tried to load it in Blender, the input node couldn’t find all the passes inside, beside the usual color, Z (and maybe another one can’t remember exactly) it couldn’t find any. So I had to open the EXR in Djv, select the pass I wanted, and save it to another file as the RGB value. Really painful process

Hopefully someone hear me out there ^^

Color Grading with Blender 2.5


Introduction

Yeahh Matt Ebb just commit my patch (SVN r27733) for the “Color Balance” node in Blender 2.5 Compositing node !!! Now it should be much easier to work with.

You can get a version of blender at Graphicall.org (any version above revision 27733)

There is still some precision issue on the color wheels, I guess some day it will be possible to move the color picker slower.



How to use it ?

First I would recommend you to un-check the “color management” setting in Blender 2.5 or it will make the blacks really hard to control.

If you are not so familiar with color grading, and push-pull techniques, I would really recommend you to watch Stu Maschwitz’s (Prolost) video tutorial using Magic Bullet Colorista. The settings won’t be exactly the same, but the approach quite the same though !

Red Giant TV Episode 22: Creating a Summer Blockbuster Film Look from Stu Maschwitz on Vimeo.


How does it works ?

I described the Lift/Gamma/Gain in a previous post, and mostly this node is based on the formulas specified there. We just slightly modified it so the 3 defaults values parameters are equal to 1.0 just like in Colorista. Which makes it much easier to control the blacks.
Actually the “Color Balance” node before this revision was the same formula but with lift default value equal to 0.0


Some presets !

While making some comparison test between Colorista in After Fx and the “color balance” node in blender, I tried to mimic some of Colorista’s presets.
You can download the “Blender Color Grading Presets” here : http://code.google.com/p/ft-projects/downloads/list

There is the following presets :

Bleach preset w/ Color Balance node
Cold preset w/ Color Balance node
Cool to Warm preset w/ Color Balance node
Day to Night preset w/ Color Balance node
Punchy preset w/ Color Balance node

vignetting using Mike Pan's approach


Understanding Gamma and Linear workflow

Even If I’m aware of what gamma and Linear workflow is, I’m not quite sure I’m using it always in the correct way. So I decide to dive into documentations and forums again to refresh my memory about it and at the same time closing a few gap.
Since so many people, even in the industry, still don’t know what it is and how it works, I thought I would make kind of a dairy of what I found on with my research those couple days.



Introduction


To get started, there is this great example from AEtuts+.com talking about Linear workflow in AE. It is not a the deepest explanation out there, but it will give you a nice overview with simple words and explicit example of what Linear workflow is and why it is so important !

So after that, 5 points you should keep in mind about Gamma (from Gamma 101 on mymentalray.com)

  1. Most displays have a non-linear response to pixel values.
  2. Most graphics software are written for a linear color model, i.e. they make the simple assumption that 255 is twice as bright as 128. But since the monitor is non-linear, this is not true. In fact, for most monitors (with a gamma=2.2), you need to send the pixel value (0.5^(1/2.2))*255=186 if you want 50% of the brightness of 255. The commonly used value of 128 will only produce about (128/255)^2.2 = 22% brightness.
  3. Digital cameras have a (roughly) linear response to light intensity, but since they are intended for display on computer monitors, they embed the non-linearity (gamma) in the image. (True for .jpg, whereas RAW files are just that – RAW, i.e. linear data, that gets non-linear when converted to JPG, for example)
  4. Therefore, if you input .jpg images taken with a camera into a graphics software, you need to compensate for the images gamma. (by inverse gamma. 1/2.2 = 0.455)
  5. And if you display the (linear) data generated from a graphics algorithm, you need to compensate for the display gamma. (add 2.2 gamma to the picture)



A few facts :

When creating a texture in Photoshop, you’ll see its color with 2.2 gamma applied (Because screens are big liar :p). Meaning when you think you got the good “brightness”, you actually made it twice (or more) brighter than what it’s supposed to be in real world.
When for painting, or montage it might not be import, for texture it is really important !!! Because as said above, your renderer/shader/… will assume the picture is linear and will apply math according to that.
So the only solution to bring this picture back to a “linear color space” is to set the gamma to the inverse of what the monitor shows you. As we know on PC, gamma are shown as 2.2 (I think it’s 1.8 on mac OSX). So the gamma value of your texture before saving it should be 0.455 (1/2.2).

Tips : In Photoshop, on top of your layer, add a “Level Adjustment Layer” and set the gamma value (mid-tone) to 0.455

With most today software I don’t think it is necessary to do that any more, but to be honest, this really depends on how the software you are using integrate Linear Workflow. For instance in 3Ds Max you can enable the Gamma correction in the “Gamma and LUT” tab of the preferences panel.

Because renders works in Linear space, your rendering would seems to look darker on your screen. So in case you are saving it to a 8bits type file (as JPG), you should set the output gamma parameter to 2.2. But in case you are saving  it to a floating point file (HDR, RAW, EXR, …), this parameter should remain 1.0. Because all the dynamics of your picture is saved in those raw file, you would apply the Gamma only in post process (compositing).

In the above case with After Effects, by making sure to activate the linear space workflow, it should take care of that for you, so you don’t have to change gamma to anything, just leave it.



Links :



Mental Ray Linear Workflow from chad smashley on Vimeo.





Here some nice read :

Cubic Lens Distortion Shader

Introduction

Cubic Lens Distortion (or undistortion as well) is well known in compositing or any VFX package. Basic Lens Distortion would usually solve the distord plate a the center, but closer you would get to the border of the picture, more the distortion will still there. The Cubic parameter let you control that.
It could also be used to give a “Chromatic Aberration” effect

This shader is based on the Algorithm shared by ssonTech website. This algorithm is used in SynthEyes (matchmove software) and is pretty simple.


Examples

k = -1.0 ; kcube = 0.0
k = -1.0 ; kcube = 0.0
k = -1.0 ; kcube = 0.5
k = -1.0 ; kcube = 0.5
Chromatic Aberration example : k = -0.15 ; kcube = 0.15  ||  using red distord channel with green and blue undistord channel
Chromatic Aberration example : k = -0.15 ; kcube = 0.15 || using red distord channel with green and blue undistord channel



Shader (Media Player ClassicHLSL)


code on Pasteall.org

Reblog this post [with Zemanta]

Saturation Shader

saturation-panel

This one should be pretty simple, but still all the shaders I have found on the Internet was based on conversion to HSL color space. Which could be actually useful if  you need some color balance control, but if you just want to control the saturation as fast as you can, it’s probably not the right approach.

Anyway here is a small shader which does the trick (Media Player Classic) :

http://www.pasteall.org/8891/c

Exposure/Offset/Gamma photoshop tool to Shaders

The goal here was to understand how works the Exposure feature of Photoshop for my research on lift/gamma/gain

exposure-photoshop-panel

NB : I wouldn’t say I’m an 100% sure about how it works, but that’s how I understood it worked so far


Exposure :

I though exposure was more complicated than that (maybe it is) but the way I’m reproducing it, is only by adding a percentage of the pixel by himself. nothing more complicated than that.


Offset :

As seen in my previous post, the Offset is just an Add of a value. My first approach on it was saying Offset is controlling the luminance of it, so I guess the correct way would be to convert the pixel in the YCbCr color space, add a value to the Y channel, and reconverting back to RBG color space. But this is doing a lot of calculation for nothing, while adding just a value to the entire picture would probably do the same, and actually would correspond to the Lift (or Offset of the CDL).
Plus switching between color space makes you loose some tiny precision in the color.

Anyway, I’ll give the two solutions, please let me know if you think one is better than the other


Gamma :


As usual, power(1/gamma)

The right order :

If all this was actually all pretty simple, at least I learned one thing (obvious as well I must say). Don’t forget to do the operation in the right order. In my first try I had a small bug, and couldn’t have the same result in Photoshop & in my shader, because I was doing the offset before the exposure. Which is pretty silly, since if you do that, you are loosing all the dynamic range of your picture when you actually want to have as much information as you can for your exposure.

The order is Exposure -> Offset -> Gamma.


Formula :

output = ((input*exposure) + offset)^(1/gamma)

hum… looks a lot like the CDL formula doesn’t it ? 🙂 Except exposure is a single float value between 0 and 20 ? (maybe more, maybe less depends of your picture)and the default value should be 1.The offset should be between -10 ? and 1 I think.


Shaders (HLSL in Media Player Classic) :

http://www.pasteall.org/8868/c

Here I’m giving the version with YCbCr conversion, but I’m pretty sure it is not doing anything more than the above one, except loosing information in conversion. But at least it shows the YCbCr conversion 🙂

http://www.pasteall.org/8869/c