From Explicit to Implicit and Back Again

In lecture we emphasized that there is no single "best" representation of geometry---rather, you should always try to pick the right representation for the task at hand. Of course, if you're going to switch between representations that means you have to be able to convert geometry from one representation to another! In particular we talked about two major classes of representation: explicit and implicit. Let's see how we can convert from an implicit signed distance function and back again.

Marching-X

The process of converting from implicit to explicit is called contouring: given a function f(x) defined at all points in space, we want to find an explicit mesh approximating the set of points x where f(x) = 0. In particular, let's assume that f(x) < 0 for points inside the shape, and f(x) > 0 for points outside the shape. A standard algorithm for contouring such functions is the method of marching X, where in 2D X might be squares or triangles, and in 3D X might be cubes or tetrahedra. Let's stick to 2D, and consider marching triangles. The basic idea is to find the points where the zero set f(x) = 0 intersects the edges of a regular triangular grid, then connect these points up into line segments.

1. Suppose you know the values fi, fj of f(x) at two endpoints of an edge ij. How can you check whether f(x) = 0 at any point along the edge? Does this check tell you there's a crossing with 100% certainty? Why or why not?
2. If the edge does cross the boundary of the shape, where might you put the crossing point? Assume as before that you only know the value of f(x) at the locations xi and xj of the edge. Is the value you computed the same as the exact point where the edge intersects the shape boundary? Why or why not?
3. Imagine you've already extracted crossing points for every edge of the triangle grid, done exactly as in the previous question. How would you decide which points to connect to make line segments?
4. Suppose we run the marching squares algorithm instead of marching triangles. In other words, we use a regular grid of squares instead of triangles, and again only know the values of ? at the vertices of the grid. Inside a square, is there always a unique way to connect up the segments?
5. Imagine a scenario where the shape boundary passes many times through the same triangle. Assuming we use the same marching triangles algorithm as before, will the extracted segments capture the original shape? What is this phenomenon an example of?

Signed Distance Functions (SDF)

Now let's go the other direction: given a shape described explicitly as a collection of line segments in the plane, we want to recover an implicit function f(x) that is negative inside the shape, and positive outside the shape. One way to do this is to evaluate the signed distance to the collection of line segments. The magnitude of the signed distance is equal to the distance to the closest point on any of the line segments. The sign of the signed distance is negative for points inside the shape, and positive for points outside the shape.

1. Suppose you already have a function d(x,p,q) that gives the (unsigned) distance from x to the line segment with endpoints p and q (we'll derive this function in a later lecture). Given two segments (p1,q1) and (p2,q2), how can you use the function d to get the closest point to the union of these two segments? More generally, given a collection of segments (p1,q1), (p2,q2), ..., (pN,qN), how can you get the unsigned distance to the closest point?
2. We can now compute the unsigned distance to the shape, but still need to determine the sign. What's a simple test we can perform to see if we're inside or outside?
3. Suppose we now use our algorithm to compute the signed distance on every vertex of a regular triangle grid. Then, we run marching triangles on this data. Will we recover the original polygons? Why or why not?