[Plib-devel] [BUG] in isect_triangles

[<jo...@lu...>]

Hi all,

I think I found a problem with the triangle-sphere intersection
function isect_triangles in ssgVtxTable (and ssgVTable). I try 
to explain this with some crude ASCII drawings in 2D (so ignore 
the 2nd dimension, so the planes through e.g. P1P2 and orthogonal 
to the P1P2P3 plane becomes simply the extended ('infinite') 
line through P1P2)

Consider the following triangle P1, P2, P3 where I extended
the edge P1P2 and P3P1 a little bit:

    |	    
  \ |	    
   \|       
    +    P1   
    |\	    
    | \	    
    |  \     
    |	\    
    |    \   
    |	  \  
    |	   \ 
    --------> 
   P2	    P3

Just before the last test in isect_triangles (please
read the source) it is known that 
- the sphere intersects the plane P1P2P3
  (or: as I have said, ignore the third dimension)
- the center S of the sphere which is tested 
  is not inside the triangle
- that the signed distance between the center of the 
  sphere S and each edge is either
  - negative, meaning that S is on the 'inside' side
    of the triangle,   or
  - that the distance between S and the extended 
    edges of the triangle is not more than the 
   sphere's radius r.

So if we draw the parallels to P1P2 and P1P3 with
a distance of r outside of the triangle, we get 
the following picture:

                         r    r
                      	\  \ | |
         		 \  \| |
	    		  \  \ |	  
	    		   \ |\|	  
	                    \|*\       	  
			     \ |\      	  
			     |\| \     	  
			     | +  \      P1	  
			     | |\  \   	  
			     | | \  \  	  
			     | |  \  \ 	  
			     | |   \  \	  
			     | |    \  \  
			     | |     \ 	\ 
			     | |      \	 \
			     | --------
                               P2      P3
Now consider the area marked *: it is possible that
S is in *, i.e. 
- close enough to the extended P1P2 and extended P1P3 
  line,  and
- on the inside side ('above' in the picture) of the extended P2P3 line

BUT the distance between S and P1 and therefore between the triangle 
and the center of the sphere can still be more 
than r. In this case a false intersection will be 
reported by the current algorithm,

Now, this case seems to be easy to fix:
if exactly two of the distances (please look at the
source code to) dp1, dp2, dp3 after the last test
are positive, the distance between S and the corresponding
triangle point (P1 in the example above) needs to be compared as well.

Unfortunately, there is a similar, slightly more complicated 
error, which can't be fixed that easily. Enlarging the
area around P1:
			 
	 |       	 
\	 | <--- parallel to P1P2 with distance r
 \	 |     	 	 
  \	 |       	 
   \	 |   	         
    \	 |  r	|        
     \	 |   	|        
      \	 |   	|        
       \ |   	|        
	\|   	|        
	 \   	|      	 
	 |\  	|        
	 |*\....|        
	 |  \   |        
	 |   \  |        
	 |    \ |        
	 |     \|        
	 |      +    P1  
	 |      |\       
	 |      | \      
	 |      |  \     
	 |%     |   \    
         |      |    \   
                -------  
	        P2     P3
	        			  
Consider the area marked *, which is outside
of a circle with radius R and center P1
(sorry, drawing the circle in ASCII looks horrible).

Any point in * has therefore a distance larger 
than r from P1, but is still close enough to the
extended line through P1P2 and P1P3 to be considered touching
the triangle (see the normal drawn with '....', which is shorter
than r). 

Assuming that I am not confused after having looked
at isect_triangles for far too long, it appears that this
case would indeed be considered an intersection by the current
algorithm, which it isn't, so there's another false positive. 

And I think that this case is somewhat harder to 
fix than the first case, since it is very similar
to a sphere with a center at '%' in the diagram, 
which will have a distance larger than r from any 
point of the triangle, but still touches the edge 
P1P2.

My current idea would be to use an algorithm to
intersect a sphere with a line segment (e.g.P1P2)
instead of computing the distance to the extended
line P1P2 ... This would actually solve the
first bug as well. But since I am no expert (and
maybe even mistaken), I am tossing this problem to
this email list :)

I hope this explanation is somewhat understandable,
if not, please let me know and I am happy to send
a jpg which will show this issue better (not sure if
attachments are allowed here).

Best regards,
    Joerg