Quiz 3: Testing Triangles

(NOTE: This quiz is not due until the lecture following the next one, on September 18.)

In class we discussed how modern triangle rasterization works; a key operation here is testing whether a given sample point is covered by a given triangle. Here you'll walk through some basic steps that will help you implement triangle rasterization in your next assignment.

You are welcome to use whatever language you are most comfortable with (or pseudocode), even though we provide function prototypes in a C-like language. You do not need to actually compile or run the code you write! Just write your answer on a sheet of paper, or type something and print it out.

1. Testing an edge

Signed distance to a line passing through points p and q

Recall that our strategy for evaluating a sample point was to see if it is contained in the three half-planes corresponding to the three triangle edges. Write a function that takes two points p, q as input, and returns the signed distance to the line passing through those points. The signed distance means that it is positive if we are one side of the line, negative on another side of the line, and zero when we're exactly on the line. In particular, let u be the unit vector pointing from p to q and let v be the vector obtained by rotating u 90 degrees in the counter-clockwise direction. Then the distance should increase as we travel along the direction v. (Hint: The vector v can be very helpful in the algorithm itself!)

A prototype for your function might look something like this:

double distance( double x[2], double p[2], double q[2] )
   // compute and return the signed distance of any given point x to the line
   // passing through p to q (assuming this line is oriented from p to q)

2. Sampling coverage

Triangle with vertex coordinates and sample point coordinates

From here, the rest of your task should be easy. Given a sample point x, test whether it is covered by the triangle with vertices p0, p1, p2 using the distance function you wrote in the previous part. (If you did not do the previous part, you can still complete this one by simply calling distance) You do not have to worry about edge cases; assume that x will never coincide with an edge (or vertex). You can also assume that the triangle vertices are given in counter-clockwise order, as depicted above.

A prototype for your function might look something like this:

bool covered( double x[2], double p0[2], double p1[2], double p2[2] )
   // return true if the sample is covered by the triangle, false if it isn't

If it makes your life easier, you are free to change this prototype so that the three points are given as a list, rather than three named arguments.

3. Orientation

In the previous part, you assumed the vertices were given in counter-clockwise order. What happens if they are instead given in clockwise order? Does your function covered still work? If not, how could you change it so that it always works?