Saturday, June 6, 2009

Photoshop like Alpha Blending

I have written about simple blending equation in previous blog. Now I want to describe more complex blending equation. That equation is used by graphics applications like Adobe Photoshop or Corel Paint Shop. Adobe “basic” blending equation in its simplified form is presented below: Let’s adapt to HLSL. We will use premultiplied alpha to simplify and optimize equation (see my previous post):

// Performs advanced "over"-type blending
// (blended is the result of advanced blending 
// (for ex, overlying.rgb * underlying.rgb))
float4 blend(float3 blended, 
             float4 overlying, 
             float4 underlying)
{
      // Convert to premultiplied format 
 overlying.rgb *= overlying.a;
 underlying.rgb *= underlying.a;

 float4 result = 
       ((1-underlying.a)*overlying) + 
       ((1-overlying.a)*underlying) + 
       (overlying.a * underlying.a) 
               * float4(blended, 1);
 
      return float4(result.rgb / result.a, result.a);
}
* I used the same equation for rgb-values and alpha

Saturday, May 30, 2009

Advanced Alpha Blending with HLSL

Alpha blending is the process of combining an overlying image with an underlying one to create the appearance of partial transparency. Most of graphics programs (like Photoshop, Corel Paint Shop Pro and so on) can blend the layers. In addition these programs provide several advanced blend modes where you can manipulate color values (for example, result of a blending is multiplication of layer’s colors). I know two ways to perform alpha blending with modern graphics hardware. You can use fixed pipeline’s functions and set proper alpha blending modes (see, http://msdn.microsoft.com/en-us/library/bb172252(VS.85).aspx) and maybe it would be enough for you. Using these render states you can customize the fixed blending equation:

Result = overlying * (SrcBlend) (BlendOp)
        underlying * (DestBlend)
Another way is to use programmable pipeline i.e. shaders. This way provides full freedom. In this article I will describe advanced alpha blending with shaders. In simple case (when underlying layer has alpha = 1, no transparency) to perform blending (in terms of HLSL):
rgb = overlying.rgb * overlying.a + 
        (1 - overlying.a) * underlying.rgb;
But what if underlying layer is partially transparent as well? Our equation must be
float3 rgb = overlying.rgb * overlying.a + 
(1 - overlying.a) * underlying.a * underlying.rgb;
Another question is how to compute result alpha. The question is:
float alpha = underlying.a + 
            (1-underlying.a)*overlying.a;
Maybe you hear about ‘premultiplied alpha’. Premultiplied alpha allows to simplify these equation to:
// Here all rgb = rgb * a;
float3 blended = overlying.rgb + 
       ((1-overlying.a)*underlying.rgb);
To get premultiplied format you can turn you graphics pipeline in appropriate mode or just multiply in begin of shader and divide before return. I have written this function:
// Performs "over"-type blending 
// (colors must be premultiplied by alpha)
float4 blend(float4 overlying, float4 underlying)
{
 float3 blended = overlying.rgb + 
        ((1-overlying.a)*underlying.rgb); 
 float alpha = underlying.a + 
         (1-underlying.a)*overlying.a;
 return float4(blended, alpha);
}
As you can see equations for RGB and A are the same and you can perform blending in just one line! But what about different blend modes like ‘multiply’, ‘darken’, ‘lighten’ and so on? Here I do not have definite answer. I use the following function:
// Performs advanced "over"-type blending
// (blended is the result of advanced blending 
// (for ex, overlying.rgb * underlying.rgb))
float4 blend(float3 blended, 
             float4 overlying, 
             float4 underlying)
{
 // Special case
 if(overlying.a == 0) blended = overlying.rgb;
 if(underlying.a == 0) blended = overlying.rgb;
 
 return blend(float4(blended, overlying.a), 
              underlying);
}
Graphics applications like Adobe Photoshop or Corel Paint Shop uses more comlex equations (see my further post).

Sunday, March 25, 2007

Delaunay triangulation

Finally I have a little time to implement my project. I have implemented Graphics Device Abstraction Layer, XNA Implementations for WinForms and WPF. Than I have implementing Mathematics Subsystem and now I have reached Topology Subsystem.
There are two kind of Delaunay triangulation. This is 3D and 2D triangulation. In my case I need to tessellate a 3D polygon which locates on the plane. Well I decided implement 2d case for a start.
Let’s see what has been done. The essence of the algorithm is adding step by step points and edges. An important thing, adding new point we have to broke some edges to push new point in optimal way. Let’s see the code.

float xmin = points[0].X;
float ymin = points[0].Y;
float xmax = xmin;
float ymax = ymin;
for (int i = 1; i < points.Length; i++)
{
     if (points[i].X < xmin) xmin = points[i].X;
     if (points[i].X > xmax) xmax = points[i].X;
     if (points[i].Y < ymin) ymin = points[i].Y;
     if (points[i].Y > ymax) ymax = points[i].Y;
}

float dx = xmax - xmin;
float dy = ymax - ymin;
float dmax = (dx > dy) ? dx : dy;

float xmid = (xmax + xmin) * 0.5f;
float ymid = (ymax + ymin) * 0.5f;

In this fragment we calculate the maximum and minimum coordinate. This will be useful for calculating the bounding triangle. Bounding triangle (or supertriangle) includes all input points. Now we can construct the supertriangle and add to the list.

Vector2[] vertices = new Vector2[points.Length + 3];
points.CopyTo(vertices, 0);

vertices[points.Length + 0] = new Vector2(
     xmid - 2.0f * dmax, ymid - dmax);
vertices[points.Length + 1] = new Vector2(
     xmid, ymid + 2.0f * dmax);
vertices[points.Length + 2] = new Vector2(
     xmid + 2 * dmax, ymid - dmax);

List<IndexedTriangle> triangles =
     new List<IndexedTriangle>();
triangles.Add(new IndexedTriangle(
     points.Length,
     points.Length + 1,
     points.Length + 2));

Now we have all points in the "vertices" and the supertriangle in the "triangles". The algorithm begins here...

for (int i = 0; i < points.Length; i++)
{
   List<IndexedEdge> edges = new List<IndexedEdge>();

   for (int j = 0; j < triangles.Count; j++)
   {
      Circle2 circumcircle = new Circle2();
      try
      {
            circumcircle = new Circle2(
            vertices[triangles[j].First],
            vertices[triangles[j].Second],
            vertices[triangles[j].Third]);
      }
      catch
      {
         // Points are collinear
         continue;
      }

      if (circumcircle.IsInside(vertices[i]))
      {
         edges.Add(new IndexedEdge(
            triangles[j].First, triangles   [j].Second));
         edges.Add(new IndexedEdge(
            triangles[j].Second, triangles[j].Third));
         edges.Add(new IndexedEdge(
            triangles[j].Third, triangles[j].First));
         triangles.RemoveAt(j);
         j--;
      }
   }
   // Clear dublicates
   for (int j = edges.Count - 2; j >= 0; j--)
   {
      for (int k = edges.Count - 1; k >= j + 1; k--)
      {
         if (edges[j] == edges[k])
         {
            edges.RemoveAt(k);
            edges.RemoveAt(j);
            k--;
            continue;
         }
      }
   }

   // Form triangles
   for (int j = 0; j < edges.Count; j++)
   {
      triangles.Add(MakeClockwise(
      new IndexedTriangle(
         edges[j].First,
         edges[j].Second, i), vertices));
   }
}

I have written a lot of modul tests and got "green bar". If you need the sources - ask me daVinci@mail.ru