Programming assignment #2 help session

Programming assignment #2 help session - Perfect meshing

CS 248 - Introduction to Computer Graphics
Autumn Quarter, 2000
Marc Levoy

1. What's a triangle?

In the mathematical sense, a triangle is a set of points in the plane. Which points are in the set of points defined by the triangle? Generally speaking, the set contains its vertices, points on its edges, and points in its interior. The points comprising an edge are the points on the line segments between two distinct vertices. The edge does not include the vertices themselves. The points comprising the interior are the points on the line segments between two points on distinct edges. The interior does not include the vertices or the points on the edges.

**Figure 1** A triangle. The solid borders represent the points contained in the edges of the triangle. The solid circles represent the vertices of the triangle.

2. Triangle intersection

Since triangles are just sets of points, we can apply the usual operation of set intersection on them. The intersection of two triangles may be one of three types:

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).

**Figure 2** (a) 2-dimensional intersection (b) 1-dimensional intersection (c) 0-dimensional intersection

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.

3. What happens to triangles during scan conversion?

In the ideal, mathematical world, points and line segments are 'invisible' in the sense that they have zero area. If the intersection of two triangles is a point or line segment, then it is invisible. Scan conversion invalidates this property. Suppose a pixel center falls on a common vertex or on a common edge. In the absence of anti-aliasing, the entire pixel must be colored the color of one the triangles which the center hit. Since a pixel has a non-zero area, the invisible, 0- or 1-dimensional intersection has become a visible, 2-dimensional area on the screen. The triangles on screen 'overlap' on that pixel. If the two triangles were drawn both independently, then that pixel will be drawn twice.

**Figure 3** Cross hairs indicate pixel centers, at which samples are taken. The yello sample in the center falls on the common edge betwen the red and the green triangles

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.

4. Redefining the triangles

The way to solve this problem is to get rid of those pesky 0-D and 1-D intersections. How? We cheat a little bit. We redefine the triangles so that a common edge or vertex is contained in exactly one of the triangles which have them in common. In other words, we remove the points in the common edge or vertex from the set of points comprising one of the triangles. In doing so, we eliminate the 0-D and 1-D intersections.

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.

**Figure 4** Redefining the triangle so that their intersection is empty. The red and green triangles share the same vertical edge. The triangles are shown shifted apart so that you can see the shared edge on both triangles. The dashed line indicates that the points on the edge is not part of the triangle. The empty cicle indicates that the vertex is not part of the triangle.

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.

**Figure 5** Exploded view of center vertex in a pie. Right: before applying meshing rules. Left: after applying meshing rules. The picture is a little misleading in the sense that you won't be able to implement the meshing rules in such a way that the containment pattern is exactly as shown in the figure.

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

5. Making the decision without global knowledge

The problem now is deciding from which triangles we remove the points in the intersection. For each triangle, you have to decide which of the edges and vertices it contains within its set. It turns out that there is a consistent, deterministic set of rules which allows you to make the decision independently for each triangle, without knowledge of any other triangle. Also, two triangles with the same three vertices should contain the exact same set of points. That is, the decision should only depend on the vertex locations.

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.

6. Triangles which share points in the interior

If two triangles share points in the interior (intersection is 2-dimensional), then there is nothing we can do about it. We leave as it is. This is important. You only need to 'fix' things when the intersection is 0-D or 1-D, and not when it's 2-D. When the intersection is 2-D, we don't need to even bother with fixing 0-D or 1-D subsets of the intersection.

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.

7. Scan convert one triangle at a time

You should scan convert 1 triangle at a time. Don't attempt to merge all the edge tables into one and then try to scan convert all those edges at once. Unless you assume that there are no overlaps, that method will be very difficult to implement. To do so, you'll have to find the intersection between all the edges which takes O(N lg N + I lg N) time (where N is the number of edges and I is the number of intersections). On the other hand, scan converting 1 triangle at a time will take only O(N) time. In other words, scan converting all edges at once may take longer than just scan converting 1 triangle at a time.

8. Slivers and really small triangles

A sliver is a really skinny triangle. For our scan converter, any triangle that is small enough has the possibility of slipping though the cracks in the sampling grid. It may also create gaps between pixels when scan converted. Anti-aliasing will help alleviate this problem.

**Figure 6** A sliver. No pixel will be turned on in the third column from the left.

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).

**Figure 7** A small right triangle may become even smaller due to meshing rules.

hishii@cs.stanford.edu