Introduction

In this blog post, we’re going to look at visualizing the unit tests that are automatically generated by Diffblue cover. For this, we’re going to look at a common task in the world of computer graphics: triangle intersections. This is used when producing photorealistic images using ray-tracing.

Ray-tracing is a technique that simulates the behavior of light in a scene. The light rays are case from the camera into the scene, one ray per pixel (there are techniques to improve the quality of the image by using more than one, but for this discussion we’ll stick with a single ray). If the ray hits an object, then the color of the resultant pixel in the image is determined by the material properties of the intersection point: if the material is a blue cloth, then the resulting pixel will be a shade of blue. The exact color will depend on not only the material properties but also the lighting, shading, occlusion, textures, etc.

How do you determine what object should be used to color the pixel? Traditionally, the objects were represented as a mesh of triangles, so the first step is to determine if the simulated light ray intersects with a triangle or not. If it hasn’t, it’ll continue on until it hits something else, or nothing.

For the rest of this post, we’re going to assume that the ray is shooting into the page perpendicular to the surface (i.e. straight into the screen). This makes it easier to visualize and discuss. In a real application, the math would need to take into account the direction of the ray.

Triangles

Suppose we have a triangle sitting on the page. It has three points at the following coordinates:

a = (x_a, y_a)
b = (x_b, y_b)
c = (x_c, y_c)

These really define three lines, AB, BC and CA. Let’s look at an image of one of these lines.

Remember that the light ray is being fired into the page, and so corresponds to a point on the plane. To determine if the point intersects the triangle, we need to determine if it’s inside or outside the triangle. We will get to a proper definition of “inside” or “outside” after we’ve discussed a little geometry.

Lines from Points

Lets start with defining the line (y = mx + c, where m is the slope of the line, and c is the intersection point) going from A to B. Suppose that the point A is at (1, 0) and B is at (3,3). We have the following two equations:

0 = m(1) + c
3 = m(3) + c

We need to find the slope and intersection points. To do this we can then subtract one equation from the other, simplify the result and obtain the following:

m = (3 - 0)/(3 - 1) = 1.5

From that, we can obtain the value for c by working backwards from one of the equations above with the new value of m:

0 = 1 * 1.5 + c
0 = 1.5 + c
c = -1.5

Now that we have the m and c values, we can define a line in two dimensions:

y = 1.5x - 1.5

Left or Right of a Line?

We now have our equation and can check to see if a point is to the left or the right of it. To check, we need to introduce an inequality. In this case, we say it’s to the right if y is less than the equation.

y < 1.5x - 1.5
0 < 1.5x - 1.5 - y

From the figure, we can see that if a point is in the shaded region, then the inequality holds. Suppose we had a test point p at (2, 1); what happens when we put that into the inequality above?

0 < 1.5 * 2 - 1.5 - 1
0 < 3 - 1.5 - 1
0 < 0.5

The inequality holds, therefore it must be on the right of the line. Let’s see what happens for point q at (2,3).

0 < 1.5 * 2 - 1.5 - 3
0 < 3 - 1.5 - 3
0 < -1.5

This inequality doesn’t hold, therefore the point is to the left of the line.

In this figure, you can see the two test points that we introduced and tested. Point p is in the shaded region and to the right of the line, while point q is not.

Inside or Outside

From here, you can see that if you perform this three times on the three different pairs of points in the triangle, you can determine if the point is inside (when it’s to the right of all the lines) or outside (when it’s to the left of any one of them).

This only works when the lines are defined by a clockwise traversal of the points. If you wanted to support a counter-clockwise traversal, the left and rights in the previous condition would be reversed. In reality, we don’t know (nor does it really matter) which direction we visit the points in, as long as the test point is on the same side for all the lines it’ll be inside.

Here’s an example of the inside/outside test implemented in java. The sign method is implemented to check the point against the line equation. The derivation of this is left as an exercise for the reader.

public class Triangle {

  private final Point2D a;
  private final Point2D b;
  private final Point2D c;

  public Triangle(final Point2D a, final Point2D b, final Point2D c) {
    this.a = a;
    this.b = b;
    this.c = c;
  }

  public boolean inside(final Point2D p){
    final int k1 = sign(p, b, a);
    final int k2 = sign(p, c, b);
    final int k3 = sign(p, a, c);
    return k1 > 0 && k2 > 0 && k3 > 0 || k1 < 0 && k2 < 0 && k3 < 0;
  }

  private int sign(Point2D p1, Point2D p2, Point2D p3) {
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
  }
}

Testing

This is all very well and good, but what tests cases are there? Well, when the point is inside or outside of a triangle, right?

  @Test
  public void testInside() {
    // Arrange
    Point2D a = new Point2D(0, 0);
    Point2D b = new Point2D(0, 3);
    Point2D c = new Point2D(3, 0);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(1, 1);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertTrue(actualInsideResult);
  }

  @Test
  public void testOutside() {
    // Arrange
    Point2D a = new Point2D(0, 0);
    Point2D b = new Point2D(0, 3);
    Point2D c = new Point2D(3, 0);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(4, 4);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }

These test cases correspond to the following diagrams.

Automatically Generated Tests

Running dcover on that snippet above, I got the following set of tests:

Or if you prefer the code:

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

import org.junit.jupiter.api.Test;

public class TriangleTest {

  // human written test
  @Test
  public void testInside() {
    // Arrange
    Point2D a = new Point2D(0, 0);
    Point2D b = new Point2D(0, 3);
    Point2D c = new Point2D(3, 0);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(1, 1);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertTrue(actualInsideResult);
  }

  // human written test
  @Test
  public void testOutside() {
    // Arrange
    Point2D a = new Point2D(0, 0);
    Point2D b = new Point2D(0, 3);
    Point2D c = new Point2D(3, 0);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(4, 4);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }

  // tests below here were generated by `dcover`

  @Test
  public void testInside1() {
    // Arrange
    Point2D a = new Point2D(1, 0);
    Point2D b = new Point2D(-10, 3);
    Point2D c = new Point2D(2, 10);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }

  @Test
  public void testInside2() {
    // Arrange
    Point2D a = new Point2D(1, 10);
    Point2D b = new Point2D(-10, 3);
    Point2D c = new Point2D(2, 3);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }

  @Test
  public void testInside3() {
    // Arrange
    Point2D a = new Point2D(10, 0);
    Point2D b = new Point2D(-10, 3);
    Point2D c = new Point2D(2, 10);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertTrue(actualInsideResult);
  }

  @Test
  public void testInside4() {
    // Arrange
    Point2D a = new Point2D(1, 10);
    Point2D b = new Point2D(-10, 3);
    Point2D c = new Point2D(2, 0);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }

  @Test
  public void testInside5() {
    // Arrange
    Point2D a = new Point2D(1, 3);
    Point2D b = new Point2D(-10, 3);
    Point2D c = new Point2D(2, 3);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }

  @Test
  public void testInside6() {
    // Arrange
    Point2D a = new Point2D(1, 0);
    Point2D b = new Point2D(10, 3);
    Point2D c = new Point2D(2, 10);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertTrue(actualInsideResult);
  }

  @Test
  public void testInside7() {
    // Arrange
    Point2D a = new Point2D(1, 0);
    Point2D b = new Point2D(-10, 3);
    Point2D c = new Point2D(2, 3);
    Triangle triangle = new Triangle(a, b, c);
    Point2D p = new Point2D(2, 3);

    // Act
    boolean actualInsideResult = triangle.inside(p);

    // Assert
    assertFalse(actualInsideResult);
  }
}

The interesting thing about these tests is that the point stays in the same position, but the triangle changes shape. The Triangle class also allows some interesting constructions—look at the 5th example, a case where the two of the triangles points are equal.

From these tests above, we can see that there are some interesting edge cases tested—what if the test point and one of the triangle points share the same location?

Conclusions

This article visualizes some automatically generated test cases for a simple triangle intersection test. As we’ve seen, there are some interesting test cases produced that wouldn’t necessarily have been considered by a human writing the same code. You can try it yourself using Diffblue Cover.