CS 248 - Introduction to Computer Graphics

Autumn Quarter, 2000

Marc Levoy

- Triangles may share points in the interior (and possibly those on the edges and the vertices). In this case the intersection of those two triangles (the region of overlap) is a convex polygon (a 2-dimensional set of points).
- Triangles may share points on an edge (and possibly vertices) but no points in its interior. In this case the intersection (the edge) is a line segment (a 1-dimensional set of points).
- Triangles may share a common vertex but no points on its edge or in the interior. In this case the intersection (the vertex) is a point (a 0-dimensional set of points).

From this point on, when I refer to an 'intersection' of two triangles, I will be referring to the set intersection of the points comprising them.

Note that this doesn't have anything to do with rounding or floating point error. We would get the same result even if we had perfect, infinite-precision arithmetic. The problem occurs because of the approximations inherent in taking only a finite number of samples.

Confused? Here's an example. We are given two triangles that share a vertical edge. One triangle is to the left, and the other triangle is to the right of the edge. The two triangles also share the vertices at the two endpoints of that edge. Therefore, the intersection of the two triangles is 1-dimensional. The vertical edge is exactly on the pixel centers. If you scan converted the two triangles independently, the pixels on the vertical edge and the two shared vertices will be drawn twice.

To get rid of the intersection, you need to remove the points comprising the common edge and vertices from either the left or right triangle. Suppose we decide to remove them from the left triangle. The left triangle now contains the single unshared vertex, the points on its two unshared edges, and the points in its interior. The right triangle contains the same points as before. But now, the intersection of the two triangles is empty. They can be scan converted independently without any pixel being double-drawn.

Strictly speaking, we are changing one of the triangles. But so what? The set of the points we're eliminating is supposed to be invisible anyway. We are only removing an infinitely thin line.

Here's another example. Suppose several triangles share a common vertex. They are arranged around the vertex so that they go all the way around the vertex, like slices of a pie. There are no slices of the pie missing. In this case, we remove the common vertex from all of the triangles except one. We also need to remove common edges as well.

Note that this process doesn't have anything to do with 'perturbing' vertices. The locations of the vertices are not modified in any way. We are just redefining the points contained in the triangle set given those vertices. It would be wrong to eliminate all of the edges and vertices, even though they are infinitesimal. Suppose a set of triangles completely tile a region in the plane. If you took away all the edges and vertices from the triangles, then then there would be 'cracks' in the interior. The idea is to eliminate just enough edges and vertices so that

- the remaining edges and vertices are just enough to fill the cracks
- each edge or vertex is contained in at most one of the triangles

Here is a portion of a plausible set of rules for vertical edges. You look at the problem from the point of the view of the edge. Each edge belongs to either its left side or to its right side. If a triangle exists adjacent to the edge on the right side, then the triangle contains the points on the edge. If a triangle exists adjacent to the edge on the left side, then the triangle doesn't contain the points on the edge. If there were actually no triangles adjacent to the right, but there were some triangles adjacent to the left, then the points on the edge will never be drawn. But like I said before, so what? The edge's width is infinitesimal anyway.

You'll have to come up with a similar set of rules for non-vertical edges and vertices.

Here is a hint for the vertex case. Think about the center vertex of a pie with many pieces (with all the pieces there). You want the center vertex to belong to exactly one of those pieces. How can each piece, just by looking at where it is in the pie, determine if it contains the center vertex or not?

Now think about a pie that may or may not be complete. If the pie is complete, then the center vertex will be drawn. If the pie is not complete, then the center vertex may or may not be drawn, depending on which triangle you assigned it to.

Here is an example. Suppose there are two triangles with different
colors but the exact same vertices. The intersection in this case is
2-dimensional. The points in the intersection are comprised of (some
of) the vertices, points on the edges, and the points in the interior.
The two triangles share the *same* interior, edges, and vertices. They
should contain the exact same set of points. In this case the triangle
scan converted later should completely overwrite the triangle scan
converted earlier. No part of the triangle scan converted earlier
should be showing, nor should the later scan conversion write a pixel to
a location which wasn't written by the earlier scan conversion.

My advice is to first figure out the meshing rules in the case for which no two triangle intersect in the interior. After you have the solution for that case, you'll be better able to understand what should happen in the case two triangles overlap in the interior.

Similarly, the meshing rules may make a small triangles even smaller. Suppose that you were given a 3-pixel wide right triangle with the vertical edge exactly on the pixel centers, and you decide that the triangle doesn't contain that edge, then the resulting scan-conversion of that triangle will be just 2 pixel wide. This is an aliasing artifact, and anti-aliasing will alleviate the problem (i.e. make the triangle look wider).

hishii@cs.stanford.edu

Last update: October 27, 2000 03:00:00 AM