EXTERIOR
INTERIOR
g p
S S
1 2
p foot
Figure 6.3: Illustration of voxels whose distance values are erroneous when computed with the min technique. White voxels are erroneous
approach does not have this problem.
6.2 Correcting the Distance Field
Ideally, we want the result of the CSG operation to be the signed distance to the boundary of the union of the operands. None of the previous methods produce a result that is correct in this sense. However, the approach based on min is most promising as a starting point. For most voxels, the minimum of the distances is the correct distance to the union. Therefore, a possible solution would be to use the min technique but correct the distances that are wrong. This entails two new problems: First we need to detect the voxels that would be erroneous after a min CSG operation, and, secondly, the correct distances must be computed.
The aim of the next proposition is to help us find out if the distance needs to be recomputed. The proposition asserts that the combined distance is equal to the minimum of the distances if there is a point,q, belonging to the boundary of the union whose distance to the voxel at positionpis equal to the minimum.
Proposition 6.1 Let S =S1SS2 where S1, S2 ⊂R3. Given a pointp∈R3 and a point q∈∂S. Leti= argminj∈{1,2}dSj(p)
kq−pk=|dSi(p)| =⇒ dS(p) =dSi(p) (6.4)
Proof: To simplify the discussion, we assume arbitrarily thati= 1.
Case 1: p is outside both solids, i.e. 0 ≤ dS1(p)≤ dS2(p). In this case, the right hand side of (6.4) is always true. Assuming otherwise would mean that dS(p)6=dS1(p) which amounts to saying that the distance to the union is not the shorter of the distance to either solid which is clearly a contradiction.
Case 2: p is inside S1 and outside S2, i.e. dS1(p) < 0 ≤ dS2(p). This case can be treated in the same way as case 3 wherepis inside bothS1 andS2, i.e.
dS1(p)≤dS2(p)<0.
We can construct a ballb−pdS1(p) ⊂S1. Any point closer topthan−dS1(p) is interior to that ball and hence cannot belong to the boundary. By assumption q ∈ ∂S and by the l.h.s. of (6.4), q ∈ ∂S lies on the boundary of the ball.
Hence,qisaclosest boundary point which implies the r.h.s. of (6.4). 2 Notice that the solids are not assumed to be permissible or even closed.
To give an example of how this proposition should be applied, assume again that dS1(p)≤dS2(p) and the boundary mappingBS1(p) yields a point that is exterior with respect to the other solid (i.e. dS2(BS1(p))≥0) then we know that dS(p) =dS1(p). Of course this example (but not the proposition) assumes that the boundary mapping is defined atp. Since this is true except on the medial surface which is infinitely thin, we can assume that the boundary mapping is defined everywhere. If a point should lie on the medial surface, an arbitrary closest point can be assigned.
In practice we are not dealing with continuous solids and distance fields but sampled voxel gridsG1 andG2. However, the gradientgcan be estimated e.g.
using central differences and then we can compute the foot point of a voxelpby BG1(p) =p−G1[p]g. If the interpolated valueG2(pfoot)<0, the distance at voxel p needs to be recomputed. There is an illustration in Figure 6.3 where the white voxels have foot points that are interior after the CSG operation.
However, if G1[p] = −r where r is the size of the transition region, then the distance need not be recomputed. Recall that the distances are clamped to the range [−r, r], and a value of−rindicates that the voxel is outside the transition region. As noted, the boundary cannot move closer, hencepremains an interior voxel if it is interior with respect to eitherS1or S2.
The second problem is recomputing the distances. In Chapter 5, we discussed
6.2 Correcting the Distance Field 111
the Fast Marching Method and the higher accuracy variant. This method can be used to recompute the distances at incorrect voxels: We simply freeze the voxels whose distances are known to be correct. Here, it is important that min yields the correct distance values for all voxels that have positive distances to both solids. This means that we are guaranteed a closed shell of voxels whose distances are known – namely all voxels in the transition region whose distance values are positive. These voxels can be used as the initial condition for the Fast Marching Method. In fact, we could leave it at that and recompute all voxels where min(G1, G2)<0. However, it is unavoidable that some numerical error is introduced and to avoid gratuitous errors it is best to recompute only where needed. To sum up, the idea is to freeze all voxels whose distance values are correct, and to rebuild the remaining voxels using the Fast Marching Method.
We will call this technique the FMM technique and the algorithm is detailed below:
• Input: Voxel gridsG1andG2.
• Output: GridGrepresenting the union.
For each voxelp
else add voxel position to list L.
For each voxelpcomputeG[p]←min(G1[p], G2[p]).
For each voxelpin L MarkG[p] as interior.
Call FMM (rebuild distance field using frozen voxels as initial condition).
Copy recomputed voxels toG
In order to compare this technique to the min technique, an experiment was conducted. The experiment is to subtract a number of spheres from a cube in a random fashion. The experiment was carried out using both the min technique and the FMM technique, and images of the results are shown in Figure 6.4.
These images have been rendered using point rendering. The basic idea is to find a set of foot points from voxels in the transition region and to render these foot points so large that the surface is covered. This method requires that the distance field is reasonably precise. The technique will be discussed in detail in Chapter 8.
Figure 6.4: Point Rendered images. min CSG (left) FMM CSG (right).
The black parts of the min CSG image are caused by foot points pointing away from the viewer. Since the boundary surface is supposed to be a closed 2D manifold this is clearly an error. We also observe some spurious structures in the min CSG image that are not present in the FMM CSG image. Unfortunately, the result produced by the FMM technique is not perfect: Some noise is present along the edge. This is aggravated by the point rendering technique; a large point size is used to ensure that the rendered points cover the surface but this simple approach makes edges look bad. However, the fundamental problem is that the volume representation cannot represent features that are significantly smaller than the grid spacing. The problem has two solutions. The first solution is to use a deformative technique to remove the sharp edges by smoothing. The second is to use a technique for volumetric CSG that blends the input solids and, hence, does not introduce sharp edges. A deformative tool for smoothing is discussed in the next chapter, and the next section is devoted to a CSG technique which avoids sharp edges.