<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN" "http://www.w3.org/TR/REC-html40/strict.dtd">
<html><head><meta name="qrichtext" content="1" /><style type="text/css">
p, li { white-space: pre-wrap; }
</style></head><body style=" font-family:'Ubuntu'; font-size:11pt; font-weight:400; font-style:normal;">
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Progress marches on</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Progress continues on mesh intersection. I expected this to be a challenging project, and it is. But the rewards of producing a fast, powerful and reliable mesh intersection algorithm are large. For one thing, this will support a simple, intuitive solid modeling editor design I intend to demonstrate that as soon as I get through the tedium of turning that nice clean algorithm that works well for non-degenerate cases into a less clean but far more useful algorithm that always works.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">I did not need to look far to find a poster child for degenerate intersection. A simple pair of cubes, offset so that three edges of each intersect midpoints of three faces of the other produces a scary number of degenerate alignments. Dividing the cube faces into triangles causes the problem. Each diagonal may or may make glancing intersections with the other cube at zero, one or two faces. What actually happens is essentially random, depending on the exact behavior of low order bits of floating point calculations as it does.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Note that the problem is not floating point imprecision per se. If we were to use exact arithmetic, as some existing boolean composition algorithms do, we might be able to determine reliably that a given edge/face intersection lies exactly on some other edge, but we would still be left with the nontrivial problem of how to employ that knowledge. Since exact arithmetic is far slower than floating point arithmetic and can consume an impractical amount of memory, I prefer to just suck it up and put in the hard work to deal consistently with effectively random floating point precision effects.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">After contemplating the issue for some time, I settled on the following approach. First, I rely on the nice, clean and fast algorithm that works well in general position (no degenerate alignments) and detect where that fails. If it is going to fail, it always fails while trying to trace out an intersection arc, by failing to find a topologically valid candidate intersection for the next arc hop.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">When the arc trace becomes blocked, I assume that it must be because of degenerate alignment. The next intersection the arc either was completely missed by the initial edge/face intersection detection pass or it was assigned to the "wrong" face, which must lie very close to the "right" face. I theorize that it is sufficient to compare each edge of the arc's last intersected face to each edge of the face of the pair of the last intersecting edge. Whew, does that sound weird? I think it is correct, because all topologically valid continuations of the arc involve the face last intersected and the face paired to the intersecting edge.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Because our mesh is restricted to triangles, we need to perform nine fairly expensive edge/edge comparisons to find any valid candidates for the next arc hop. We may find multiple topologically valid candidates, any of which should produce correct results, but some will yield fewer arc hops than others. For now, I just randomly choose the first candidate.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Once having found a valid continuation, the edge/face intersection database is updated to reflect that re-interpretation. The candidate intersection might already be present in the database, in which case it must be found and deleted. After possibly deleting the "alias" intersection, the new intersection is added and we jump back into the arc trace algorithm at the point it was interrupted.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">There is plenty of room for error here. We could easily end up in an infinite loop, reinterpreting the same near miss intersection candidate over and over again. I theorize that this can never happen if only topologically valid continuations are chosen at each step, but this remains to be demonstrated.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Intersection arcs may be entirely missed</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">The above recovery algorithm relies on the assumption that at least one intersection point of every intersection arc was discovered in the initial edge/face intersection pass. In rare cases, this might not be true. I was able to construct an example with just two triangles: even though they "obviously" intersect, every edge one face can be a near miss on the other face.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">This proves that the initial edge/face intersection pass must detect near misses in addition to edge/face hits. Adding this extra geometric test is not horribly expensive, and over time, a greater mathematician then me will probably reformulate the two tests to make the additional expense largely vanish.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">In any case, the result of the extra near miss testing is a list of near misses, which may be added to the intersection database wherever no topologically equivalent face hit is already present. Near misses should be particularly rare in "organic" meshes, in which edges and faces rarely have a simple geometric relation to each other. This is where efficiency will be most critical, so that is nice.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Implementation strategy</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Implementing this algorithm is slow going, mainly because of the difficulty of sorting out precisely what is happening topologically. The strategy I have chosen is to start with an algorithm that often works and incrementally improve it until it always works. That it will eventually get to the latter point is an article of faith. I estimate that I am still a few weekends away from proving it one way of the other.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">The failure recovery code described above is potentially complex, however it does have one saving grace: it must by definition implement exactly the same topological logic as the algorithm that is already known to work. Therefore, the existing, simpler algorithm can be used as "documentation" and to cross check the more complex recovery algorithm.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">In fact, the algorithm for general position could be completely discarded and we could just fail and recover at each arc hop. This would require nine relatively expensive edge/edge comparisons per hop, so it is clearly a good idea to keep the existing error-prone algorithm around, because it is fast. Much like a deathray: if it works it always destroys all your enemies, but sometimes it just explodes instead.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">A typical debugging session</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">The attached image shows a typical debugging session. Easy, right? This is the "simple" cube/cube intersection. There are 14 possible diagonal/face intersections, of which 6 happen to be detected. The edge highlighted in white is one of the edge/face intersections, which I can step through and examine one at a time using keyboard controls. The face intersected is indicated by a line from the intersection point to the center of the face. The intersection arc trace fails on the first hop, shown as "e36" in white. Happy hunting.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Regards,</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Daniel</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p></body></html>