1  // 

2  // Lol Engine 

3  // 

4  // Copyright: (c) 20102013 Sam Hocevar <sam@hocevar.net> 

5  // (c) 20102013 Benjamin "Touky" Huet <huet.benjamin@gmail.com> 

6  // This program is free software; you can redistribute it and/or 

7  // modify it under the terms of the Do What The Fuck You Want To 

8  // Public License, Version 2, as published by Sam Hocevar. See 

9  // http://www.wtfpl.net/ for more details. 

10  // 

11  

12  #if defined HAVE_CONFIG_H 

13  # include "config.h" 

14  #endif 

15  

16  #if defined _XBOX 

17  # define _USE_MATH_DEFINES /* for M_PI */ 

18  # include <xtl.h> 

19  # undef near /* Fuck Microsoft */ 

20  # undef far /* Fuck Microsoft again */ 

21  #elif defined _WIN32 

22  # define _USE_MATH_DEFINES /* for M_PI */ 

23  # define WIN32_LEAN_AND_MEAN 

24  # include <windows.h> 

25  # undef near /* Fuck Microsoft */ 

26  # undef far /* Fuck Microsoft again */ 

27  #endif 

28  

29  #include <cstdlib> /* free() */ 

30  #include <cstring> /* strdup() */ 

31  

32  #include <ostream> /* std::ostream */ 

33  

34  #include "core.h" 

35  

36  using namespace std; 

37  

38  namespace lol 

39  { 

40  //Projects Point on Plane : Normal must be given normalized. returns point on plane. 

41  vec3 ProjPointOnPlane(vec3 const &point, vec3 const &planeP, vec3 const &planeN)


42  {


43  vec3 o2p = point  planeP;


44  float d = dot(o2p, planeN);


45  return point + d * planeN;


46  }


47  

48  //gets the dist from a Point to a Plane : Normal must be given normalized. returns distance. 

49  float PointDistToPlane(vec3 const &point, vec3 const &planeP, vec3 const &planeN)


50  {


51  vec3 o2p = point  planeP;


52  return abs(dot(o2p, planeN));


53  }


54  

55  // Line/triangle : sets vIsec as the intersection point & return true if ok. 

56  bool RayIsectTriangle(vec3 const &rayP, vec3 const &rayD,


57  vec3 const &triV0, vec3 const &triV1, vec3 const &triV2,


58  vec3 &vIsec)


59  {


60  vec3 v01, v02, h, v0P, q;


61  float a, f, triU, triV;


62 


63  //


64  v01 = triV1  triV0;


65  v02 = triV2  triV0;


66 


67  h = cross(rayD, v02);


68  a = dot(v01, h);


69 


70  //rayDir is coplanar to the triangle, exit.


71  if (a > CSG_EPSILON && a < CSG_EPSILON)


72  return false;


73 


74  f = 1 / a;


75  v0P = rayP  triV0;


76  triU = f * (dot(v0P, h));


77 


78  //point is supposed to have an U on the segment v01


79  if (triU < CSG_EPSILON  triU > 1.0)


80  return false;


81 


82  q = cross(v0P, v01);


83  triV = f * dot(rayD, q);


84 


85  //point is not in the triangle


86  if (triV < CSG_EPSILON  triU + triV > 1.0)


87  return false;


88 


89  // at this stage we can compute t to find out where


90  // the intersection point is on the line


91  float t = f * dot(v02, q);


92 


93  if (t > CSG_EPSILON) // ray intersection


94  {


95  vIsec = triV0 + v01 * triU + v02 * triV;


96  return true;


97  }


98  else // this means that there is a line intersection


99  // but not a ray intersection


100  return false;


101  } 

102  

103  // Triangle/Triangle 

104  bool TriangleIsectTriangle(vec3 const &v00, vec3 const &v01, vec3 const &v02, //triangle 0 

105  vec3 const &v10, vec3 const &v11, vec3 const &v12, //triangle 1 

106  vec3 &iP00, vec3 &iP10) //triangle intersection, iPx means gives the actual intersection points. 

107  { 

108  vec3 isec[2] = { vec3(0, 0, 0), vec3(0, 0, 0) }; 

109  vec3 triV[6] = { v00, v01, v02, 

110  v10, v11, v12 }; 

111  vec3 triD[6] = { v01  v00, v02  v01, v00  v02, 

112  v11  v10, v12  v11, v10  v12 }; 

113  int isecIdx = 0; 

114  vec3 vIsec(0);


115  

116  //Check the normal before doing any other calculations 

117  vec3 plane_norm[2] = { cross(normalize(triD[0]), normalize(triD[1])), 

118  cross(normalize(triD[3]), normalize(triD[4])) }; 

119  if (abs(dot(plane_norm[0], plane_norm[1])) == 1.0f)


120  return false;


121 


122  #if 0 

123  //Precheck to verify if two point of one of the triA are on triB, and vice versa. 

124  int zero_dist[2] = { 0, 0 }; 

125  for (int i = 0; i < 3; i++) 

126  { 

127  if (PointDistToPlane(triV[i], triV[3], plane_norm[1]) < CSG_EPSILON) 

128  zero_dist[0]++; 

129  if (PointDistToPlane(triV[i + 3], triV[0], plane_norm[0]) < CSG_EPSILON) 

130  zero_dist[1]++; 

131  } 

132  

133  if (zero_dist[0] >= 2  zero_dist[0] >= 2) 

134  return false; 

135  #endif 

136  

137  //We first need to find two points intersecting, no matter on which triangle. 

138  for (int i = 0; i < 2 && isecIdx < 2; i++) 

139  { 

140  int found_isec = 1; 

141  for (int j = 0; j < 3 && isecIdx < 2; j++) 

142  { 

143  int pIdx = j + i * 3; 

144  int tIdx = (1  i) * 3; 

145  if (RayIsectTriangle(triV[pIdx], triD[pIdx], 

146  triV[tIdx + 0], triV[tIdx + 1], triV[tIdx + 2], 

147  isec[isecIdx])) 

148  { 

149  #if 1 //if the point is near one the given entry, consider it as being the same point. 

150  for (int k = 0; k < 6; k++) 

151  { 

152  if (length(isec[isecIdx]  triV[k]) < CSG_EPSILON) 

153  { 

154  isec[isecIdx] = triV[k]; 

155  break; 

156  } 

157  } 

158  #endif 

159  

160  //Automatic pass on the first intersection 

161  if (isecIdx == 0  

162  //If we have already found an intersection, pass if it's on this triangle. 

163  /*found_isec == i */ 

164  //if it's the second intersection, we need it to be different from the first one. 

165  (isecIdx == 1 && length(isec[0]  isec[1]) > CSG_EPSILON)) 

166  { 

167  found_isec = i; 

168  isecIdx++; 

169  } 

170  } 

171  } 

172  } 

173  

174  if (isecIdx >= 2) 

175  { 

176  iP00 = isec[0]; 

177  iP10 = isec[1]; 

178  return true; 

179  } 

180  return false; 

181  } 

182  

183  //Ray/Line : returns one of the RAY_ISECT_* defines. 

184  int RayIsectRay(vec3 const &rayP00, vec3 const &rayP01,


185  vec3 const &rayP10, vec3 const &rayP11,


186  vec3 &vIsec)


187  { 

188  vec3 rayD0 = rayP01  rayP00; 

189  float rayS0 = length(rayD0); 

190  vec3 rayD0N = normalize(rayD0); 

191  

192  vec3 rayD1 = rayP11  rayP10; 

193  float rayS1 = length(rayD1); 

194  vec3 rayD1N = normalize(rayD1); 

195  

196  vec3 rayP0P1 = rayP10  rayP00; 

197  vec3 c01 = cross(rayD0N, rayD1N); 

198  float crs01S = length(c01); 

199  

200  if (crs01S > CSG_EPSILON && crs01S < CSG_EPSILON)


201  return 0; 

202  

203  mat3 m0 = mat3(rayP0P1, rayD1N, c01); 

204  float t0 = determinant(m0) / (crs01S * crs01S); 

205  vec3 isec0 = rayP00 + rayD0N * t0; 

206  

207  mat3 m1 = mat3(rayP0P1, rayD0N, c01); 

208  float t1 = determinant(m1) / (crs01S * crs01S); 

209  vec3 isec1 = rayP10 + rayD1N * t1; 

210  

211  if (sqlength(isec0  isec1) < CSG_EPSILON) //ray intersection


212  {


213  vIsec = (isec0 + isec0) * .5f;


214  float d0 = (length(rayP01  vIsec) < CSG_EPSILON  length(rayP00  vIsec) < CSG_EPSILON)?


215  (1.0f):


216  (dot(rayP00  vIsec, rayP01  vIsec));


217  float d1 = (length(rayP10  vIsec) < CSG_EPSILON  length(rayP11  vIsec) < CSG_EPSILON)?


218  (1.0f):


219  (dot(rayP10  vIsec, rayP11  vIsec));


220 


221  //if the dot is negative, your point is in each ray, so say OK.


222  if (d0 < .0f && d1 < .0f)


223  return RAY_ISECT_ALL;


224  if (d0 < .0f)


225  return RAY_ISECT_P0;


226  if (d1 < .0f)


227  return RAY_ISECT_P1;


228  return RAY_ISECT_NONE;


229  }


230  else // this means that there is a line intersection


231  // but not a ray intersection


232  return RAY_ISECT_NOTHING;


233  } 

234  

235  //Ray/Plane : Normal must be given normalized. returns 1 if succeeded. 

236  bool RayIsectPlane(vec3 const &rayP0, vec3 const &rayP1,


237  vec3 const &planeP, vec3 const &planeN,


238  vec3 &vIsec, bool test_line_only)


239  {


240  vec3 ray_dir = rayP1  rayP0;


241  float d = dot(ray_dir, planeN);


242 


243  if (d > CSG_EPSILON && d < CSG_EPSILON)


244  return false;


245 


246  vec3 o2p1 = rayP1  planeP;


247  vec3 o2p0 = rayP0  planeP;


248 


249  if (!test_line_only)


250  {


251  d = dot(o2p1, planeN);


252  d *= dot(o2p0, planeN);


253 


254  //point are on the same side, so ray can intersect.


255  if (d > .0f)


256  return false;


257  }


258 


259  float t = (dot(ProjPointOnPlane(rayP0, planeP, planeN)  rayP0, planeN)) / dot(ray_dir, planeN);


260 


261  if (!test_line_only && (t < CSG_EPSILON  t > 1.0f))


262  return false;


263 


264  vIsec = rayP0 + t * ray_dir;


265  return true;


266  }


267  

268  //used to find the intersecting points between a triangle side and a coplanar line. 

269  bool RayIsectTriangleSide(vec3 const &v0, vec3 const &v1, vec3 const &v2, 

270  vec3 const &iP0, vec3 const &iP1, 

271  vec3 &iV0, int &iIdx0, vec3 &iV1, int &iIdx1) 

272  { 

273  vec3 isecV[2] = { vec3(.0f), vec3(.0f) }; 

274  int isecI[2] = { 1, 1 }; 

275  

276  vec3 triV[3] = { v0, v1, v2 }; 

277  int isecIdx = 0; 

278  vec3 vIsec(0);


279  

280  //Two points given, so we test each triangle side to find the intersect 

281  isecIdx = 0; 

282  for (int j = 0; j < 3 && isecIdx < 2; j++) 

283  { 

284  int Result = RayIsectRay(triV[j], triV[(j + 1) % 3], iP0, iP1, vIsec); 

285  if (Result == RAY_ISECT_P0  Result == RAY_ISECT_ALL) 

286  { 

287  isecV[isecIdx] = vIsec; 

288  isecI[isecIdx] = j; 

289  isecIdx++; 

290  } 

291  } 

292  

293  if (isecIdx < 2) 

294  return false; 

295  

296  //We send the infos back to the parent. 

297  //TODO : that can be better than this horrible thing. 

298  iV0 = isecV[0]; 

299  iV1 = isecV[1];


300  iIdx0 = isecI[0];


301  iIdx1 = isecI[1];


302  return true; 

303  } 

304  

305  } /* namespace lol */ 

306  
