G4TessellatedGeometryAlgorithms.cc

Go to the documentation of this file.
00001 //
00002 // ********************************************************************
00003 // * License and Disclaimer                                           *
00004 // *                                                                  *
00005 // * The  Geant4 software  is  copyright of the Copyright Holders  of *
00006 // * the Geant4 Collaboration.  It is provided  under  the terms  and *
00007 // * conditions of the Geant4 Software License,  included in the file *
00008 // * LICENSE and available at  http://cern.ch/geant4/license .  These *
00009 // * include a list of copyright holders.                             *
00010 // *                                                                  *
00011 // * Neither the authors of this software system, nor their employing *
00012 // * institutes,nor the agencies providing financial support for this *
00013 // * work  make  any representation or  warranty, express or implied, *
00014 // * regarding  this  software system or assume any liability for its *
00015 // * use.  Please see the license in the file  LICENSE  and URL above *
00016 // * for the full disclaimer and the limitation of liability.         *
00017 // *                                                                  *
00018 // * This  code  implementation is the result of  the  scientific and *
00019 // * technical work of the GEANT4 collaboration and of QinetiQ Ltd,   *
00020 // * subject to DEFCON 705 IPR conditions.                            *
00021 // * By using,  copying,  modifying or  distributing the software (or *
00022 // * any work based  on the software)  you  agree  to acknowledge its *
00023 // * use  in  resulting  scientific  publications,  and indicate your *
00024 // * acceptance of all terms of the Geant4 Software license.          *
00025 // ********************************************************************
00026 //
00027 //
00028 // $Id: G4TessellatedGeometryAlgorithms.cc 67011 2013-01-29 16:17:41Z gcosmo $
00029 //
00030 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00031 //
00032 // CHANGE HISTORY
00033 // --------------
00034 //
00035 // 07 August 2007, P R Truscott, QinetiQ Ltd, UK - Created, with member
00036 //                 functions based on the work of Rickard Holmberg.
00037 //
00038 // 26 September 2007
00039 //                 P R Truscott, qinetiQ Ltd, UK
00040 //                 Updated to assign values of location array, not update
00041 //                 just the pointer.
00042 //
00043 // 12 October 2012, M Gayer, CERN, - Reviewed optimized implementation.
00044 //
00046 
00047 #include "G4TessellatedGeometryAlgorithms.hh"
00048 
00049 #include <cfloat> 
00050 
00052 //
00053 // IntersectLineAndTriangle2D
00054 //
00055 // Determines whether there is an intersection between a line defined
00056 // by r = p + s.v and a triangle defined by verticies p0, p0+e0 and p0+e1.
00057 //
00058 // Here:
00059 //        p = 2D vector
00060 //        s = scaler on [0,infinity)
00061 //        v = 2D vector
00062 //        p0, e0 and e1 are 2D vectors
00063 // Information about where the intersection occurs is returned in the
00064 // variable location.
00065 //
00066 // This is based on the work of Rickard Holmberg.
00067 //
00068 G4bool G4TessellatedGeometryAlgorithms::IntersectLineAndTriangle2D (
00069   const G4TwoVector &p,  const G4TwoVector &v,
00070   const G4TwoVector &p0, const G4TwoVector &e0, const G4TwoVector &e1,
00071   G4TwoVector location[2])
00072 {
00073   G4TwoVector loc0[2];
00074   G4int e0i = IntersectLineAndLineSegment2D (p,v,p0,e0,loc0);
00075   if (e0i == 2)
00076   {
00077     location[0] = loc0[0];
00078     location[1] = loc0[1];
00079     return true;
00080   }
00081 
00082   G4TwoVector loc1[2];
00083   G4int e1i = IntersectLineAndLineSegment2D (p,v,p0,e1,loc1);
00084   if (e1i == 2)
00085   {
00086     location[0] = loc1[0];
00087     location[1] = loc1[1];
00088     return true;
00089   }
00090 
00091   if ((e0i == 1) && (e1i == 1))
00092   {
00093     if ((loc0[0]-p).mag2() < (loc1[0]-p).mag2())
00094     {
00095       location[0] = loc0[0];
00096       location[1] = loc1[0];
00097     }
00098     else
00099     {
00100       location[0] = loc1[0];
00101       location[1] = loc0[0];
00102     }
00103     return true;
00104   }
00105 
00106   G4TwoVector p1 = p0 + e0;
00107   G4TwoVector DE = e1 - e0;
00108   G4TwoVector loc2[2];
00109   G4int e2i = IntersectLineAndLineSegment2D (p,v,p1,DE,loc2);
00110   if (e2i == 2)
00111   {
00112     location[0] = loc2[0];
00113     location[1] = loc2[1];
00114     return true;
00115   }
00116 
00117   if ((e0i == 0) && (e1i == 0) && (e2i == 0)) return false;
00118 
00119   if ((e0i == 1) && (e2i == 1))
00120   {
00121     if ((loc0[0]-p).mag2() < (loc2[0]-p).mag2())
00122     {
00123       location[0] = loc0[0];
00124       location[1] = loc2[0];
00125     }
00126     else
00127     {
00128       location[0] = loc2[0];
00129       location[1] = loc0[0];
00130     }
00131     return true;
00132   }
00133 
00134   if ((e1i == 1) && (e2i == 1))
00135   {
00136     if ((loc1[0]-p).mag2() < (loc2[0]-p).mag2())
00137     {
00138       location[0] = loc1[0];
00139       location[1] = loc2[0];
00140     }
00141     else
00142     {
00143       location[0] = loc2[0];
00144       location[1] = loc1[0];
00145     }
00146     return true;
00147   }
00148 
00149   return false;
00150 }
00151 
00153 //
00154 // IntersectLineAndLineSegment2D
00155 //
00156 // Determines whether there is an intersection between a line defined
00157 // by r = p0 + s.d0 and a line-segment with endpoints p1 and p1+d1.
00158 // Here:
00159 //        p0 = 2D vector
00160 //        s  = scaler on [0,infinity)
00161 //        d0 = 2D vector
00162 //        p1 and d1 are 2D vectors
00163 //
00164 // This function returns:
00165 // 0 - if there is no intersection;
00166 // 1 - if there is a unique intersection;
00167 // 2 - if the line and line-segments overlap, and the intersection is a
00168 //     segment itself.
00169 // Information about where the intersection occurs is returned in the
00170 // as ??.
00171 //
00172 // This is based on the work of Rickard Holmberg as well as material published
00173 // by Philip J Schneider and David H Eberly, "Geometric Tools for Computer
00174 // Graphics," ISBN 1-55860-694-0, pp 244-245, 2003.
00175 //
00176 G4int G4TessellatedGeometryAlgorithms::IntersectLineAndLineSegment2D (
00177   const G4TwoVector &p0, const G4TwoVector &d0,
00178   const G4TwoVector &p1, const G4TwoVector &d1,
00179   G4TwoVector location[2])
00180 {
00181   G4TwoVector e     = p1 - p0;
00182   G4double kross    = cross(d0,d1);
00183   G4double sqrKross = kross * kross;
00184   G4double sqrLen0  = d0.mag2();
00185   G4double sqrLen1  = d1.mag2();
00186   location[0]       = G4TwoVector(0.0,0.0);
00187   location[1]       = G4TwoVector(0.0,0.0);
00188 
00189   if (sqrKross > DBL_EPSILON * DBL_EPSILON * sqrLen0 * sqrLen1)
00190   {
00191     //
00192     // The line and line segment are not parallel. Determine if the intersection
00193     // is in positive s where r=p0 + s*d0, and for 0<=t<=1 where r=p1 + t*d1.
00194     //
00195     G4double ss = cross(e,d1)/kross;
00196     if (ss < 0)         return 0; // Intersection does not occur for positive ss
00197     G4double t = cross(e,d0)/kross;
00198     if (t < 0 || t > 1) return 0; // Intersection does not occur on line-segment
00199     //
00200     // Intersection of lines is a single point on the forward-propagating line
00201     // defined by r=p0 + ss*d0, and the line segment defined by  r=p1 + t*d1.
00202     //
00203     location[0] = p0 + ss*d0;
00204     return 1;
00205   }
00206   //
00207   // Line and line segment are parallel. Determine whether they overlap or not.
00208   //
00209   G4double sqrLenE = e.mag2();
00210   kross            = cross(e,d0);
00211   sqrKross         = kross * kross;
00212   if (sqrKross > DBL_EPSILON * DBL_EPSILON * sqrLen0 * sqrLenE)
00213   {
00214     return 0; //Lines are different.
00215   }
00216   //
00217   // Lines are the same.  Test for overlap.
00218   //
00219   G4double s0   = d0.dot(e)/sqrLen0;
00220   G4double s1   = s0 + d0.dot(d1)/sqrLen0;
00221   G4double smin = 0.0;
00222   G4double smax = 0.0;
00223 
00224   if (s0 < s1) {smin = s0; smax = s1;}
00225   else         {smin = s1; smax = s0;}
00226 
00227   if (smax < 0.0) return 0;
00228   else if (smin < 0.0)
00229   {
00230     location[0] = p0;
00231     location[1] = p0 + smax*d0;
00232     return 2;
00233   }
00234   else
00235   {
00236     location[0] = p0 + smin*d0;
00237     location[1] = p0 + smax*d0;
00238     return 2;
00239   }
00240 }
00241 
00243 //
00244 // CrossProduct
00245 //
00246 // This is just a ficticious "cross-product" function for two 2D vectors...
00247 // "ficticious" because such an operation is not relevant to 2D space compared
00248 // with 3D space.
00249 //
00250 G4double G4TessellatedGeometryAlgorithms::cross(const G4TwoVector &v1,
00251                                                 const G4TwoVector &v2)
00252 {
00253   return v1.x()*v2.y() - v1.y()*v2.x();
00254 }

Generated on Mon May 27 17:49:57 2013 for Geant4 by  doxygen 1.4.7