[World] Solid Progress

[Daniel Phillips]

Progress marches on

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.

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.

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.

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.

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.

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.

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.

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.

Intersection arcs may be entirely missed

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.

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.

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.

Implementation strategy

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.

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.

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.

A typical debugging session

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.

Regards,

Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/world/attachments/20120707/8ceea303/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid26.png
Type: image/png
Size: 159303 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120707/8ceea303/attachment-0001.png>