Programming assignment #2 help session - Perfect meshing
CS 248 - Introduction to Computer Graphics
Autumn Quarter, 2000
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.
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).
(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
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
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
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.
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.
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
It would be wrong to eliminate all of the edges and vertices, even though they
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
- 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.
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).
A small right triangle may become even smaller due to meshing rules.
Copyright © 2000 Hiroshi Ishii
October 27, 2000 03:00:00 AM