Scalar Data Visualization: Part 3

• Download source files - 136 KB

Introduction

I'm back fellows. Sorry I'm late. But I've been very busy with my pre-master stuff. This time I'll discuss another technique in scalar data visualization called "flooded contouring". This technique generates colored regions as illustrated in the pictures above. Each area represents the average value of the two contour lines it lies between.

Background

A previous knowledge of simple scalar data visualization techniques and DirectX9, and a quick review on the Line Contouring article.

The Algorithm

Let's start with illustrating the main idea in the algorithm before getting into the code. Our target is to fill the areas between any two contour lines with the color relative to the average of these two values. So, we start by iterating on all the triangles we have in our grid for each two consecutive contour lines. We have three possible cases for each triangle:

• The first case is when the whole triangle is between the two adjacent contour lines, i.e., no contour line intersects with the triangle as shown in the figure below. This is the easiest case, where we calculate the average contour value and get the corresponding color for this value and flood this triangle with it.



• The second case is when the triangle is intersecting with the contour lines and this intersection is forming a pentagon as shown in the figure below. We first extract this pentagon and color it with the average of the two contour lines. After that, we have two triangles left. Both of them will be the first case or the third case, so we will solve them as illustrated below.



• The third case is when the triangle is intersecting with the contour lines but the intersection doesn't form a pentagon. The result will be a polygon, or more, and a triangle as shown in the figure below. So, what we do is extract the first polygon, and the remaining triangle still needs to be solved. It might match with the first case, and so we are finished with the triangle, or it might match again with the third case.

To sum up the algorithm, we can write it as follows:

For each triangle in the grid 
   For each 2 consecutive contour lines in the set of lines
      If triangle falls complete within those 2 triangles // 1st case
          Color the whole triangle with the average of the 2 contour values.
      Else if intersection makes a pentagon
          Extract the pentagon and color it.
          Do the same steps for the left triangle.
          // i.e. check for the cases again on this triangle.

          Do the same steps for the right triangle.
      Else
          Extract the bottom polygon and color it
          Do the same steps for the remaining triangle.
      End if
   End for
End for

Using the Code

Here we solve the first case by checking whether the first contour line, which has the maximum contour value, has a value greater than the maximum value in the triangle. The triangle vertices are sorted in ascending order as will be illustrated below, so this triangle completely lies in the region of the maximum contour value, same for the last contour line less than the minimum value in the triangle, and the normal case where the triangle lies completely between the two consecutive contour lines.

In all these cases, we get the color of the triangle and add this triangle to the list of flooded faces which will be rendered finally. If there was no matching case, the function will return false.

private bool FullTriangleFallage(int[] verts)
{
    TriangulatedPolygon temp = new TriangulatedPolygon();
    temp.Vertex1Index = verts[0];
    . . . 
    for (int i = 0; i < Lines.Count; i++)
    {
        if (Lines[i].Value >= Points[verts[2]].Data[VariableIndex] && i == 0)
        {
            temp.Color = GetRegionColor(i);
            FloodedFaces.Add(temp);
            return true;
        }
        else if (Lines[i].Value <= Points[verts[0]].Data[VariableIndex] && 
                 i < Lines.Count - 1 && Lines[i + 1].Value >= 
                 oints[verts[2]].Data[VariableIndex])
        {
            temp.Color = ScoOteRColorPalet.GetColor(
               (Lines[i].Value + Lines[i + 1].Value) / 2);
            FloodedFaces.Add(temp);
            return true;
        }
        else if (Lines[i].Value <= 
             Points[verts[0]].Data[VariableIndex] && i == Lines.Count - 1)
        {
            . . . 
        }
    }
    return false;
}

This function is responsible for extracting any polygon in the flooded contouring, except for the pentagon case. If the triangle is empty or it's a full fallage, the function returns and the problem is solved. If it's the third case, we start by extracting the last polygon and recalling CutTriangle with the remaining triangle.

To get the next part clear, we should agree on the following, using the figure below. The vertices are sorted in ascending order, where vertex0 has the minimum value and vetrex2 has the maximum value. The edge between 01 is denoted as the left edge, and the edge between 12 is denoted as the right edge.

So, we first determine if the contour line cuts the left edge or the right edge. This will vary from where we will start extracting the polygons as illustrated in the two figures below. The left picture is the one with the left edge intersected, so we started extracting polygons by taking vertices 1 and 2 in the new polygon, with the two new vertices generated from the intersection. And we call CutTriangle for vertex0 and the two new vertices. In the case of the right edge, vertex2 is switched with vertex0.

I hope that by now the main idea is clear; if we took a look at the code, we'll find it clear now.

private void CutTriangle(int[] verts, int line) {
    if (verts == null)
        return;
    if (FullTriangleFallage(verts))
        return;
    for (int i = 0; i < Lines.Count; i++)
    {
        if (i == line)
        continue; // right edge intersection
        if (Lines[i].Value >= Points[verts[1]].Data[VariableIndex] && 
            Lines[i].Value <= Points[verts[2]].Data[VariableIndex])
        {
            // getting the 2 new intersection vertices using 
            int p23 = CreatePoint(verts[1], verts[2], Lines[i].Value);
            int p13 = CreatePoint(verts[0], verts[2], Lines[i].Value);
            int color;
            if(i == 0)
                color = ScoOteRColorPalet.GetColor((Lines[i].Value + MinVal) / 2);
            else
                color = ScoOteRColorPalet.GetColor(
                         (Lines[i].Value + Lines[i - 1].Value) / 2); 
            //creating the new polygon
            TriangulatedPolygon t = new TriangulatedPolygon();
            t.Vertex1Index = verts[0];
            t.Vertex2Index = p13;
            t.Vertex3Index = p23;
            t.Color = color;
            FloodedFaces.Add(t);
            t = new TriangulatedPolygon();
            t.Vertex1Index = verts[0];
            t.Vertex2Index = p23;
            t.Vertex3Index = verts[1];
            t.Color = color;
            FloodedFaces.Add(t); 
            //recursing on the rest of the triangle
            CutTriangle(GetSortedPoints(verts[2], p23, p13),i);
            return;
        } // left edge intersection
        if (Lines[i].Value >= Points[verts[0]].Data[VariableIndex] && 
            Lines[i].Value <= Points[verts[1]].Data[VariableIndex] && 
            (i == Lines.Count - 1 || Lines[i + 1].Value >= 
             Points[verts[2]].Data[VariableIndex]))
        {
            . . . 
        }
    }
}

Now we are dealing with the second case, extracting the pentagon and iterating on the other two generated triangles for possible match with the first and third cases. We first check for the pentagon, and extract it and add it to the flooded surface as three triangles. Then we return back the two generated sub-triangles in the out params to be used as I'll illustrate below.

private void ExtractPentagon(int[] verts, out int[] subtrinagle1, 
             out int[] subtriangle2, out int line1, out int line2)
{
    for (int i = 0; i < Lines.Count-1; i++)
    { 
        if ((Lines[i].Value >= Points[verts[0]].Data[VariableIndex] && 
             Lines[i].Value < Points[verts[1]].Data[VariableIndex]) && 
             (Lines[i + 1].Value > Points[verts[1]].Data[VariableIndex] && 
             Lines[i + 1].Value <= Points[verts[2]].Data[VariableIndex]))
        {
            int p12 = CreatePoint(verts[0], verts[1], Lines[i].Value);
            int p13 = CreatePoint(verts[0], verts[2], Lines[i].Value);
            int p23 = CreatePoint(verts[1], verts[2], Lines[i+1].Value);
            int p31 = CreatePoint(verts[0], verts[2], Lines[i+1].Value);
            int color = ScoOteRColorPalet.GetColor((Lines[i].Value + Lines[i+1].Value)/2);

            TriangulatedPolygon t = new TriangulatedPolygon();
            t.Vertex1Index = p12;
            t.Vertex2Index = p23;
            t.Vertex3Index = verts[1];
            t.Color = color;
            FloodedFaces.Add(t);
            t = new TriangulatedPolygon();
            t.Vertex1Index = p13;
            t.Vertex2Index = p23;
            t.Vertex3Index = p12;
            t.Color = color;
            FloodedFaces.Add(t);
            t = new TriangulatedPolygon();
            t.Vertex1Index = p13;
            t.Vertex2Index = p31;
            t.Vertex3Index = p23;
            t.Color = color;
            FloodedFaces.Add(t); 

            subtrinagle1 = GetSortedPoints(verts[0], p13, p12);
            subtriangle2 = GetSortedPoints(verts[2], p31, p23);
            line1 = i;
            line2 = i + 1;
            return;
        }
    } 
    subtrinagle1 = verts;
    subtriangle2 = null;
    line1 = line2 = -1;
}

Finally, to sum it up, we loop on all the triangles in the grid. We call ExtractPentagon. If there's a pentagon, subverts1 and subverts2 will not be null and the program recurses in both triangles until they are finished. If there is no pentagon, subverts2 will be null and CutTriangle(subverts2, line2) will return immediately.

private void CreateFlood()
{
    FloodedFaces = new List<TriangulatedPolygon>();
    foreach (TriangulatedPolygon t in Faces)
    {
        int[] verts = GetSortedPoints(t.Vertex1Index, t.Vertex2Index, t.Vertex3Index);
        int[] subverts1;
        int[] subverts2;
        int line1;
        int line2;
        ExtractPentagon(verts, out subverts1, out subverts2,out line1,out line2);
        CutTriangle(subverts1, line1);
        CutTriangle(subverts2, line2);
    }
}

After this function returns, FloodedFaces will be holding all the flooded surface, triangles, which we set after that in the vertex buffer to be rendered.

public ContourManager(List<Point> p, List<TriangulatedPolygon> f, 
                      List<string>variables, ScoOteREngine e,
                      double max, double min, int num, int varIndex, bool flood)
{
    if (flood)
    {
        CreateFlood();
        CreateFloodedVertexBuffer();
        . . . 
    }
}

That's all.