Möller–Trumbore intersektionsalgoritm

Möller –Trumbore stråltriangelskärningsalgoritmen, uppkallad efter dess uppfinnare Tomas Möller och Ben Trumbore, är en snabb metod för att beräkna skärningspunkten mellan en stråle och en triangel i tre dimensioner utan att behöva förberäkning av planekvationen för planet som innehåller triangeln. . Bland andra användningsområden kan den användas i datorgrafik för att implementera strålspårningsberäkningar som involverar triangelnät .

Beräkning

Definitioner

Strålen definieras av en ursprungspunkt $O$ och en riktningsvektor ${\vec {v}}$ . Varje punkt på strålen kan uttryckas med ${\displaystyle {\vec {r}}(t)=O+t{\vec {v}}} ,$ där parametern $t$ sträcker sig från noll till oändligt. Triangeln definieras av tre hörn, benämnda $v_{1}$ , $v_{2}$ , $v_{3}$ . Planet som triangeln befinner sig på, som behövs för att beräkna stråltriangelns skärning, definieras av en punkt på planet, såsom $v_{1}$ , och en vektor som är ortogonal mot varje punkt på det planet, såsom korsprodukten mellan vektorn från $v_{1}$ till $v_{2}$ och vektorn från $v_{1}$ till $v_{3}$ :

${\vec {n}}\cdot (P_{1}-P_{2})=0$ , där ${\vec {n}}=(v_{2}-v_{1})\times (v_{3}-v_{1})$ och $P_{1}$ och $P_{2}$ är alla punkter på planet.

Kontrollera om strålen är parallell med triangeln

Ta först reda på om strålen skär det plan som triangeln befinner sig på, och om den gör det, hitta koordinaterna för den skärningspunkten. Det enda sättet att strålen inte kommer att skära planet är om strålens riktningsvektor är parallell med planet. När detta händer prickprodukten mellan strålens riktningsvektor och planets normalvektor noll. Annars skär strålen planet någonstans , men inte nödvändigtvis inom triangeln.

Kontrollera om stråle-plansskärningen ligger utanför triangeln

Med hjälp av barycentriska koordinater kan vilken punkt som helst på triangeln uttryckas som en konvex kombination av triangelns hörn: $P=wv_{1}+uv_{2}+vv_ {3}$

Koefficienterna måste vara icke-negativa och summera till 1, så w kan ersättas med $1-uv$ :

${\begin{aligned} P&=(1-uv)v_{1}+uv_{2}+vv_{3}\\P&=v_{1}+u(v_{2}-v_{1})+v(v_{3}- v_{1})\end{aligned}}$ , där $P$ är vilken punkt som helst på planet. Observera att ${\vec {e_{1}}}=v_{2}-v_{1}$ och ${\ vec {e_{2}}}=v_{3}-v_{1}$ är vektorer på kanten av triangeln, och tillsammans spänner de över ett plan (som går genom origo). Varje punkt på det planet kan skrivas som $ue_{1}+ve_{2}$ och kan översättas med $v_{1}$ för att "flytta" den punkten på det plan som triangeln befinner sig på.

För att hitta $u$ och $v$ för en viss skärningspunkt, ställ in stråluttrycket lika med det plana uttrycket och placera variablerna på ena sidan och konstanterna på den andra.

${\begin{aligned}O+tD&=v_{1}+u(v_{2}-v_{1})+v(v_{3}-v_{1})\\O-v_{ 1}&=-tD+u(v_{2}-v_{1})+v(v_{3}-v_{1})\end{aligned}}$

Detta är ett system av linjära ekvationer med tre ekvationer (en vardera för $x$ , $y$ , $z$ ) och tre okända ( $t$ , $u$ och $v$ ), och kan representeras som en matris-vektormultiplikation.

${\begin{bmatrix}\vert &\vert &\vert \\-d&(v2-v1)&(v3-v1)\\\vert &\vert &\vert \end{bmatrix}}{\begin{bmatrix}t\\u\\v\end{bmatrix}}=O-v_{1}$

Denna ekvation kommer alltid att ha en lösning när matrisen har tre linjärt oberoende kolumnvektorer i $\mathbb {R} ^{3}$ och därmed är inverterbar . Detta händer om och endast om triangelns höjdpunkter inte är kolinjära och strålen inte är parallell med planet.

Algoritmen kan använda Cramers regel för att hitta värdena $t$ , $u$ och $v$ för en skärningspunkt, och om den ligger inom triangeln kan skärningspunktens exakta koordinater hittas genom att koppla in $t$ till strålens ekvation.

C++ implementering

Följande är en implementering av algoritmen i C++ :

   
                             
                            
                            

        
       
         
       
         
     
        
        
      
      
           
             
      
        
        
           
         
      
        
             
         
    
         
        
    
              
         
    
     
         
 bool  RayIntersectsTriangle  (  Vector3D  rayOrigin  ,  Vector3D  rayVector  ,  Triangle  *  inTriangle  ,  Vector3D  &  outIntersectionPoint  )  {  const  float  EPSILON  =  0,0000001  ;  Vector3D  vertex0  =  inTriangle  ->  vertex0  ;  Vector3D  vertex1  =  inTriangle  ->  vertex1  ;  Vector3D  vertex2  =  inTriangle  ->  vertex2  ;  Vector3D  edge1  ,  edge2  ,  h  ,  s  ,  q  ;  flyta  a  ,  f  ,  u  ,  v  ;  kant1  =  vertex1  -  vertex0  ;  kant2  =  vertex2  -  vertex0  ;  h  =  rayVector  .  crossProduct  (  kant2  );  a  =  kant1  .  dotProduct  (  h  );  if  (  a  >  -  EPSILON  &&  a  <  EPSILON  )  returnerar  false  ;  // Denna stråle är parallell med denna triangel.  f  =  1,0  /  a  ;  s  =  rayOrigin  -  vertex0  ;  u  =  f  *  s  .  dotProduct  (  h  );  if  (  u  <  0,0  ||  u  >  1,0  )  returnerar  falskt  ;  q  =  s  .  crossProduct  (  edge1  );  v  =  f  *  rayVector  .  dotProduct  (  q  );  if  (  v  <  0,0  ||  u  +  v  >  1,0  )  returnerar  falskt  ;  // I detta skede kan vi beräkna t för att ta reda på var skärningspunkten är på linjen.  flyta  t  =  f  *  kant2  .  dotProduct  (  q  );  if  (  t  >  EPSILON  )  // ray intersection  {  outIntersectionPoint  =  rayOrigin  +  rayVector  *  t  ;  returnera  sant  ;  }  else  // Detta betyder att det finns en linjeskärning men inte en strålkorsning.  returnera  falskt  ;  } 

Java implementering

Följande är en implementering av algoritmen i Java med javax.vecmath från Java 3D API:

   

          

         
                                                 
                                                 
                                                  
           
           
           
            
            
            
            
            
            
         
         
         
          
                
                 
        
            
         
            
                
             
        
         
            
                  
             
        
        
             
            
        
              
              
             
          
        
             
        
    
 public  class  MollerTrumbore  {  private  static  final  double  EPSILON  =  0,0000001  ;  public  static  boolean  rayIntersectsTriangle  (  Point3d  rayOrigin  ,  Vector3d  rayVector  ,  Triangle  inTriangle  ,  Point3d  outIntersectionPoint  )  {  Point3d  vertex0  =  inTriangle  .  getVertex0  ();  Point3d  vertex1  =  intriangel  .  getVertex1  ();  Point3d  vertex2  =  intriangel  .  getVertex2  ();  Vector3d  edge1  =  new  Vector3d  ();  Vector3d  edge2  =  new  Vector3d  ();  Vector3d  h  =  ny  Vector3d  ();  Vector3d  s  =  ny  Vector3d  ();  Vector3d  q  =  ny  Vector3d  ();  dubbla  a  ,  f  ,  u  ,  v  ;  kant1  .  sub  (  vertex1  ,  vertex0  );  kant2  .  sub  (  vertex2  ,  vertex0  );  h  .  kors  (  rayVector  ,  edge2  );  a  =  kant1  .  punkt  (  h  );  if  (  a  >  -  EPSILON  &&  a  <  EPSILON  )  {  return  false  ;  // Denna stråle är parallell med denna triangel.  }  f  =  1,0  /  a  ;  s  .  sub  (  rayOrigin  ,  vertex0  );  u  =  f  *  (  s  .  punkt  (  h  ));  if  (  u  <  0,0  ||  u  >  1,0  )  {  return  false  ;  }  q  .  kors  (  s  ,  kant1  );  v  =  f  *  rayVector  .  punkt  (  q  );  if  (  v  <  0,0  ||  u  +  v  >  1,0  )  {  return  false  ;  }  // I detta skede kan vi beräkna t för att ta reda på var skärningspunkten är på linjen.  dubbel  t  =  f  *  kant2  .  punkt  (  q  );  if  (  t  >  EPSILON  )  // ray intersection  {  outIntersectionPoint  .  set  (  0,0  ,  0,0  ,  0,0  );  outIntersectionPoint  .  scaleAdd  (  t  ,  rayVector  ,  rayOrigin  );  returnera  sant  ;  }  else  // Detta betyder att det finns en linjeskärning men inte en strålkorsning.  {  return  false  ;  }  }  } 

Se även

• Badouel skärningsalgoritm
• MATLAB version av denna algoritm (mycket vektoriserad)
• Baldwin-Weber strål-triangel skärningsalgoritm
• Schlick–Subrenat-algoritm för strål-fyrsidig skärning

Länkar

• Snabb Minimal Storage Ray-Triangle Intersection
• Optimering av den grundläggande algoritmen av Möller & Trumbore , kod från journal of graphics tools
• Ray-Tracing: Återge en triangel