API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2016
92
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 32.91 KB | None | 0 0
raw download clone embed print report
  1. #pragma once
  2. #include <math.h>
  3.  
  4. #include "types.h"
  5. #include "vectormath.h"
  6. #include "matrixmath.h"
  7.  
  8. extern struct Game game;
  9.  
  10. inline int8_t sgn(const float input) {
  11. // Remove sign and check for ~= 0
  12. if ((float)((uint32_t)input & ~(1<<31)) < 0.00001f) return 0;
  13. int8_t values[] = { 1, -1 };
  14. return values[((uint32_t)input>>31)];
  15. }
  16.  
  17. inline bool object_fits_within(struct object_bb *o, const int64_t x0, const int64_t x1, const int64_t z0, const int64_t z1) {
  18. return (!(o->offset.f[0] + o->difference.f[0] > x1 || o->offset.f[0] - o->difference.f[0] < x0 ||
  19. o->offset.f[2] + o->difference.f[2] > z1 || o->offset.f[2] - o->difference.f[2] < z0));
  20. }
  21.  
  22. inline void gen_new_coords(const uint8_t quadrant, const int64_t x0, const int64_t x1, const int64_t z0, const int64_t z1, int64_t *new_x0, int64_t *new_x1, int64_t *new_z0, int64_t *new_z1) {
  23. assert(quadrant<=3);
  24. const uint64_t len_x = (uint64_t)((x1 - x0)/2),
  25. len_z = (uint64_t)((z1 - z0)/2);
  26.  
  27. if (quadrant == 0 || quadrant == 3) {
  28. *new_x0 = x0 + len_x;
  29. *new_x1 = x1;
  30. } else {
  31. *new_x0 = x0;
  32. *new_x1 = x0 + len_x;
  33. }
  34. // 0 or 1 else 2 or 3
  35. if (quadrant < 2) {
  36. *new_z0 = z0 + len_z;
  37. *new_z1 = z1;
  38. } else {
  39. *new_z0 = z0;
  40. *new_z1 = z0 + len_z;
  41. }
  42. }
  43.  
  44. // initial init, called each time a new node is created.
  45. void init_node(struct collision_node *node) {
  46. uint8_t x;
  47. const uint16_t default_entries = game.settings.bucket_size;
  48. for (x = 0; x < 4; ++x) {
  49. node->child[x] = NULL;
  50. }
  51. node->triangle = malloc(sizeof(union triangle) * default_entries);
  52. if (node->triangle == NULL) {
  53. // malloc error, tough break man
  54. }
  55. node->object_count = 0;
  56. node->max_objects = default_entries;
  57. }
  58.  
  59. inline float comparef_lower(const float f1, const float f2) {
  60. return (f1 < f2) ? f1 : f2;
  61. //else return f2;
  62. }
  63.  
  64. inline float comparef_higher(const float f1, const float f2) {
  65. return (f1 > f2) ? f1 : f2;
  66. }
  67.  
  68. /*
  69. inline void gen_bb(struct object_bb *o, const union triangle tri) {
  70. uint8_t x;
  71. float min,max,difference[3],offset[3];
  72. o->tri = tri;
  73. for (x = 0; x < 3; ++x) {
  74. min = comparef_lower(o->tri.f[x],o->tri.f[x+4]);
  75. min = comparef_lower(min,o->tri.f[x+8]);
  76. max = comparef_higher(o->tri.f[x],o->tri.f[x+4]);
  77. max = comparef_higher(max,o->tri.f[x+8]);
  78. difference[x] = ((max - min) * 0.5f);
  79. offset[x] = min + difference[x];
  80. }
  81. memcpy(&o->difference,difference,sizeof(float)*3);
  82. memcpy(&o->offset,offset,sizeof(float)*3);
  83. }*/
  84.  
  85.  
  86. void gen_bb(struct object_bb *o, const union triangle tri) {
  87. o->tri = tri;
  88.  
  89. union opt_vecf min, max;
  90. min.v = _mm_min_ps(tri.p[0].v, tri.p[1].v);
  91. min.v = _mm_min_ps(min.v, tri.p[2].v);
  92. max.v = _mm_max_ps(tri.p[0].v, tri.p[1].v);
  93. max.v = _mm_max_ps(max.v, tri.p[2].v);
  94.  
  95. o->difference = vec3dividef(vec3sub(max, min), 2.f);
  96. o->offset = vec3add(min, o->difference);
  97. }
  98.  
  99.  
  100. // recursive insert
  101. void qtins_auto(struct collision_node *node, struct object_bb *o, int64_t x0, int64_t x1, int64_t z0, int64_t z1) {
  102. if (node->object_count < node->max_objects) {
  103. node->triangle[node->object_count] = o->tri;
  104. node->object_count++;
  105. } else {
  106. int x,y,z;
  107. int64_t new_x0, new_x1, new_z0, new_z1;
  108. bool bottom_level = (x1-x0 == 1);
  109.  
  110. if (!bottom_level) {
  111. for (x = 0; x < 4; ++x) {
  112. gen_new_coords(x, x0, x1, z0, z1, &new_x0, &new_x1, &new_z0, &new_z1);
  113. if (object_fits_within(o, new_x0, new_x1, new_z0, new_z1)) {
  114. if (!node->child[x]) {
  115. node->child[x] = malloc(sizeof(struct collision_node));
  116. if (node->child[x]) {
  117. init_node(node->child[x]);
  118. }
  119. }
  120. qtins_auto(node->child[x],o,new_x0,new_x1,new_z0,new_z1);
  121. return;
  122. }
  123. }
  124. for (x = 0; x < 4; ++x) {
  125. gen_new_coords(x, x0, x1, z0, z1, &new_x0, &new_x1, &new_z0, &new_z1);
  126. struct object_bb new_bb;
  127. for (y = 0; y < node->object_count; ++y) {
  128. gen_bb(&new_bb,node->triangle[y]);
  129. if (object_fits_within(&new_bb,new_x0, new_x1, new_z0, new_z1)) {
  130. if (!node->child[x]) {
  131. node->child[x] = malloc(sizeof(struct collision_node));
  132. if (node->child[x] == NULL) {
  133. // malloc error
  134. } else {
  135. init_node(node->child[x]);
  136. }
  137. }
  138. qtins_auto(node->child[x], &new_bb, new_x0, new_x1, new_z0, new_z1);
  139. node->triangle[y] = o->tri;
  140. return;
  141. }
  142. }
  143. }
  144. }
  145. // couldn't find a target. resize our bucket and reinsert.
  146. const uint32_t new_size = (bottom_level) ? node->max_objects + 1 : node->max_objects * 2;
  147.  
  148. union triangle *ptr = malloc(sizeof(union triangle) * (new_size));
  149. if (ptr == NULL) {
  150. // malloc error
  151. printf("malloc error\n");
  152. } else {
  153. memcpy(ptr,node->triangle,sizeof(union triangle) * node->max_objects);
  154. free(node->triangle);
  155. node->triangle = ptr;
  156. node->max_objects = new_size;
  157. qtins_auto(node,o,x0,x1,z0,z1);
  158. }
  159. }
  160. }
  161. // parent insert
  162. void qtins(struct Game *game, struct collision_node *node, union triangle tri) {
  163. struct object_bb obj_bb;
  164. gen_bb(&obj_bb,tri);
  165. const int64_t size = game->settings.max_width;
  166. qtins_auto(node, &obj_bb, -size, size, -size, size);
  167. }
  168. // wrapper function for inserting objects.
  169. void insert_tri(struct Game *game, struct collision_tree *tree, union triangle tri) {
  170. tree->num_objects++;
  171. qtins(game,&tree->parent_node, tri);
  172. }
  173.  
  174. void init_tree(struct collision_tree *tree) {
  175. init_node(&tree->parent_node);
  176. tree->num_objects = 0;
  177. }
  178.  
  179. void clear_map(struct collision_node *node) {
  180. int x;
  181. free(node->triangle);
  182. for (x = 0; x < 4; ++x) {
  183. if (node->child[x]) {
  184. clear_map(node->child[x]);
  185. free(node->child[x]);
  186. node->child[x] = NULL;
  187. }
  188. }
  189. }
  190.  
  191. void print_node_debug_info(struct collision_node *node, int depth) {
  192. int x;
  193. for (x = 0; x < depth - 1; ++x) {
  194. if (x > 7) { printf("(%i)",depth); x = depth; }
  195. else printf("-");
  196. }
  197. printf(">%u/%u entities stored\n",node->object_count,node->max_objects);
  198. for (x = 0; x < 4; ++x) {
  199. if (node->child[x]) {
  200. printf("%i",x);
  201. print_node_debug_info(node->child[x],depth+1);
  202. }
  203. }
  204. }
  205.  
  206. void print_tree_debug_info(struct collision_tree *tree) {
  207. printf("\n------------------------------------------\nDebug info for collision tree:\n %lu total objects imported\n",tree->num_objects);
  208. print_node_debug_info(&tree->parent_node, 0);
  209. printf("End of collision tree debug info\n\n");
  210. }
  211.  
  212. void free_collision_tree(struct collision_tree *tree) {
  213. clear_map(&tree->parent_node);
  214. }
  215.  
  216. union triangle conv_spheroid(const union triangle source, const union opt_vecf radii) {
  217. union triangle out;
  218. out.p[0] = vec3divide(source.p[0], radii);
  219. out.p[1] = vec3divide(source.p[1], radii);
  220. out.p[2] = vec3divide(source.p[2], radii);
  221. return out;
  222. }
  223.  
  224. void check_triangle(struct collision_info *info, const union triangle tri) { //IN ESPACE
  225. struct tPlane triangle_plane = gen_tri_plane(tri);
  226. double t0, t1;
  227. bool embedded_in_plane = false;
  228. double signed_distance_to_triangle_plane = plane_signed_distance_to(info->base_point, triangle_plane);
  229. float normal_dot_velocity = dot(triangle_plane.normal,info->velocity);
  230. float slide_check = dot(triangle_plane.normal,vec3normalize(info->velocity));
  231.  
  232. if (normal_dot_velocity == 0.f) {
  233. if (fabs(signed_distance_to_triangle_plane) >= 1.f) {
  234. return;
  235. } else {
  236. embedded_in_plane = true;
  237. t0 = 0.f; //spheroid is colliding with triangle for the entire time interval
  238. t1 = 1.f;
  239. }
  240. } else {
  241. t0 = (-1.f - signed_distance_to_triangle_plane) / normal_dot_velocity;
  242. t1 = ( 1.f - signed_distance_to_triangle_plane) / normal_dot_velocity;
  243. if (t0 > t1) {
  244. double temp = t1;
  245. t1 = t0;
  246. t0 = temp;
  247. }
  248. if (t0 > 1.f || t1 < 0.f) {
  249. return;
  250. }
  251. if (t0 < 0.f) t0 = 0.f;
  252. if (t1 < 0.f) t1 = 0.f;
  253. if (t0 > 1.f) t0 = 1.f;
  254. if (t1 > 1.f) t1 = 1.f;
  255. }
  256. union opt_vecf collision_point;
  257. union opt_vecf velocity = info->velocity;
  258. union opt_vecf base = info->base_point;
  259. bool found_collision = false;
  260. float t = 1.f;
  261. if (!embedded_in_plane) {
  262. union opt_vecf plane_intersection_point = vec3add(vec3sub(info->base_point, triangle_plane.normal), vec3multf(info->velocity,t0));
  263. if (check_point_in_triangle(plane_intersection_point, tri)) {
  264. found_collision = true;
  265. t = t0;
  266. collision_point = plane_intersection_point;
  267. }
  268. }
  269. if (!found_collision) {
  270. union opt_vecf p1_minus_base = vec3sub(tri.p[0],base);
  271. union opt_vecf p2_minus_base = vec3sub(tri.p[1],base);
  272. union opt_vecf p3_minus_base = vec3sub(tri.p[2],base);
  273.  
  274.  
  275. float velocity_squared_length = dot(velocity, velocity);
  276. float a,b,c, new_t;
  277.  
  278. a = velocity_squared_length;
  279. b = 2.f * dot(velocity,vec3sub(base,tri.p[0]));
  280. c = dot(p1_minus_base,p1_minus_base) - 1.f;
  281.  
  282. if (get_lowest_root(a,b,c,t,&new_t)) {
  283. t = new_t;
  284. found_collision = true;
  285. collision_point = tri.p[0];
  286. }
  287.  
  288. b = 2.f * dot(velocity,vec3sub(base,tri.p[1]));
  289. c = dot(p2_minus_base,p2_minus_base) - 1.f;
  290. if (get_lowest_root(a,b,c,t,&new_t)) {
  291. t = new_t;
  292. found_collision = true;
  293. collision_point = tri.p[1];
  294. }
  295.  
  296. b = 2.f * dot(velocity,vec3sub(base,tri.p[2]));
  297. c = dot(p3_minus_base,p3_minus_base) - 1.f;
  298. if (get_lowest_root(a,b,c,t,&new_t)) {
  299. t = new_t;
  300. found_collision = true;
  301. collision_point = tri.p[2];
  302. }
  303.  
  304. union opt_vecf edge = vec3sub(tri.p[1], tri.p[0]);
  305. union opt_vecf base_to_vertex = vec3sub(tri.p[0], base);
  306.  
  307. float edge_squared_length = dot(edge,edge);
  308. float edge_dot_velocity = dot(edge,velocity);
  309. float edge_dot_base_to_vertex = dot(edge,base_to_vertex);
  310.  
  311. a = edge_squared_length * -velocity_squared_length +
  312. edge_dot_velocity * edge_dot_velocity;
  313. b = edge_squared_length * (2*dot(velocity,base_to_vertex)) -
  314. 2.0*edge_dot_velocity*edge_dot_base_to_vertex;
  315. c = edge_squared_length * (1-dot(base_to_vertex,base_to_vertex)) +
  316. edge_dot_base_to_vertex*edge_dot_base_to_vertex;
  317.  
  318. if (get_lowest_root(a,b,c,t,&new_t)) {
  319. float f = (edge_dot_velocity * new_t - edge_dot_base_to_vertex)/edge_squared_length;
  320. if (f >= 0.f && f <= 1.f) {
  321. t = new_t;
  322. found_collision = true;
  323. collision_point = vec3add(tri.p[0],vec3multf(edge,f));
  324. }
  325. }
  326.  
  327. edge = vec3sub(tri.p[2], tri.p[1]);
  328. base_to_vertex = vec3sub(tri.p[1], base);
  329.  
  330. edge_squared_length = dot(edge,edge);
  331. edge_dot_velocity = dot(edge,velocity);
  332. edge_dot_base_to_vertex = dot(edge,base_to_vertex);
  333.  
  334. a = edge_squared_length * -velocity_squared_length +
  335. edge_dot_velocity * edge_dot_velocity;
  336. b = edge_squared_length * (2*dot(velocity,base_to_vertex)) -
  337. 2.0*edge_dot_velocity*edge_dot_base_to_vertex;
  338. c = edge_squared_length * (1-dot(base_to_vertex,base_to_vertex)) +
  339. edge_dot_base_to_vertex*edge_dot_base_to_vertex;
  340.  
  341. if (get_lowest_root(a,b,c,t,&new_t)) {
  342. const float f = (edge_dot_velocity * new_t - edge_dot_base_to_vertex)/edge_squared_length;
  343. if (f >= 0.f && f <= 1.f) {
  344. t = new_t;
  345. found_collision = true;
  346. collision_point = vec3add(tri.p[1],vec3multf(edge,f));
  347. }
  348. }
  349.  
  350. edge = vec3sub(tri.p[0], tri.p[2]);
  351. base_to_vertex = vec3sub(tri.p[2], base);
  352.  
  353. edge_squared_length = dot(edge,edge);
  354. edge_dot_velocity = dot(edge,velocity);
  355. edge_dot_base_to_vertex = dot(edge,base_to_vertex);
  356.  
  357. a = edge_squared_length * -velocity_squared_length +
  358. edge_dot_velocity * edge_dot_velocity;
  359. b = edge_squared_length * (2*dot(velocity,base_to_vertex)) -
  360. 2.0*edge_dot_velocity*edge_dot_base_to_vertex;
  361. c = edge_squared_length * (1-dot(base_to_vertex,base_to_vertex)) +
  362. edge_dot_base_to_vertex*edge_dot_base_to_vertex;
  363.  
  364. if (get_lowest_root(a,b,c,t,&new_t)) {
  365. float f = (edge_dot_velocity * new_t - edge_dot_base_to_vertex)/edge_squared_length;
  366. if (f >= 0.f && f <= 1.f) {
  367. t = new_t;
  368. found_collision = true;
  369. collision_point = vec3add(tri.p[2],vec3multf(edge,f));
  370. }
  371. }
  372. }
  373. if (found_collision) {
  374. float distance_to_collision = t * vec3gen_length(info->velocity);
  375. if (!info->collision_found || distance_to_collision < info->nearest_distance) {
  376. info->nearest_distance = distance_to_collision;
  377. info->intersection_point = collision_point;
  378. info->collision_found = true;
  379. }
  380.  
  381. }
  382. }
  383.  
  384. void check_triangle_r3(struct collision_info_r3 *info, const union triangle tri) {
  385. struct tPlane triangle_plane = gen_tri_plane(tri);
  386. double signed_distance_to_triangle_plane = plane_signed_distance_to(info->r3_position, triangle_plane);
  387. float normal_dot_velocity = dot(triangle_plane.normal,info->r3_velocity);
  388.  
  389. if (normal_dot_velocity == 0.f) {
  390. return;
  391. }
  392. double t = -signed_distance_to_triangle_plane / normal_dot_velocity;
  393.  
  394. if(t > 1.f || t < 0.f) return;
  395.  
  396. union opt_vecf plane_intersection_point = vec3add(info->r3_position, vec3multf(info->r3_velocity,t));
  397.  
  398. if (check_point_in_triangle(plane_intersection_point, tri)) {
  399. float distance_to_collision = t * vec3gen_length(info->r3_velocity);
  400. if (!info->collision_found) {
  401. info->collision_found = true;
  402. }
  403. if (distance_to_collision < info->nearest_distance) {
  404. info->nearest_distance = distance_to_collision;
  405. info->intersection_point = plane_intersection_point;
  406. }
  407. }
  408. }
  409.  
  410. void check_collision_recursive(struct collision_node *node, struct collision_info *info, const int64_t x0, const int64_t x1, const int64_t z0, const int64_t z1) {
  411. int x;
  412. int i;
  413. normalized_velocity = info->normalized_velocity;
  414. for (x = 0; x < node->object_count; ++x) {
  415. const union triangle new_tri = conv_spheroid(node->triangle[x],info->e_radius);
  416. check_triangle(info, new_tri);
  417. }
  418.  
  419. //IMPLEMENT ACQUISITION OF MOVEMENT BOUND RECTANGE VERTICES
  420. //mb_x = movement bounds x coords
  421. //mb_z = movement bounds z coords
  422.  
  423.  
  424. /*info->velocity = e_space_velocity;
  425. info->normalized_velocity = vec3normalize(e_space_velocity);
  426. info->base_point = e_space_position;
  427. info->collision_found = false;
  428. info->normalized_velocity*/
  429.  
  430. //create vector called perp_normalized_velocity, switch x and z, make one negative.
  431.  
  432.  
  433. //outer edges of ellipsoid perpendicular to movement vector + radius vector or velocity vector and radius vector
  434.  
  435. //movement bounds vertices
  436.  
  437. /*double mb_x[4], mb_z[4], n_x0, n_x1, n_z0, n_z1;
  438.  
  439. mb_x[0] = info->base_point.x + perp_normalized_velocity.x - info->normalized_velocity.x;
  440. mb_y[0] = info->base_point.z + perp_normalized_velocity.z - info->normalized_velocity.z;
  441.  
  442. mb_x[1] = info->base_point.x - perp_normalized_velocity.x - info->normalized_velocity.x;
  443. mb_y[1] = info->base_point.z - perp_normalized_velocity.z - info->normalized_velocity.z;
  444.  
  445. mb_x[2] = info->base_point.x - perp_normalized_velocity.x + info->velocity.x + info->normalized_velocity.x;
  446. mb_y[2] = info->base_point.z - perp_normalized_velocity.z + info->velocity.z + info->normalized_velocity.z;
  447.  
  448. mb_x[3] = info->base_point.x + perp_normalized_velocity.x + info->velocity.x + info->normalized_velocity.x;
  449. mb_y[3] = info->base_point.z + perp_normalized_velocity.z + info->velocity.z + info->normalized_velocity.z;*/
  450.  
  451.  
  452.  
  453. uint8_t point2; //choose better data type
  454. bool up, down, left, right, in_x, in_y, checked;
  455. union opt_vecf normal1;
  456. union opt_vecf normal2;
  457. for (x = 0; x < 4; ++x ) {
  458. if (node->child[x]) {
  459. int64_t new_x0, new_x1, new_z0, new_z1;
  460. gen_new_coords(x,x0,x1,z0,z1,&new_x0,&new_x1,&new_z0,&new_z1);
  461. union opt_vecf base = info->base_point;
  462. union opt_vecf vel_y;
  463. bool embedded_in_plane;
  464. in_x = new_x0 <= base.x && base.x <= new_x1;
  465. in_y = new_z0 <= base.z && base.z <= new_z1;
  466.  
  467. if (in_x && in_y ) {
  468. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  469. }
  470. else {
  471. left = base.x < new_x0;
  472. right = base.x > new_x1;
  473. up = base.z < new_y0;
  474. down = base.z > new_y1;
  475. vel = info->e_space_velocity;
  476. vel_y = new_vec3(vel.x, 0, vel.z);
  477.  
  478.  
  479.  
  480. double t0, t1;
  481.  
  482.  
  483.  
  484.  
  485.  
  486. if(!in_x) {
  487. normal = new_vec3((float)(left * -1 + right * 1), 0, 0);
  488. embedded_in_plane = false;
  489. double signed_distance_to_line = plane_signed_distance_to(base, new_vec3((float)(new_x0 * (uint64_t)left + new_x1 * (uint64_t)right), 0, 0));
  490. float normal_dot_velocity = dot(normal, vel_y);
  491.  
  492. if (normal_dot_velocity == 0.f) {
  493. if (fabs(signed_distance_to_line) <= 1.f) {
  494. embedded_in_plane = true;
  495. t0 = 0.f; //spheroid is colliding with triangle for the entire time interval
  496. t1 = 1.f;
  497. }
  498. } else {
  499. t0 = (-1.f - signed_distance_to_line) / normal_dot_velocity;
  500. t1 = ( 1.f - signed_distance_to_line) / normal_dot_velocity;
  501. if (t0 > t1) {
  502. double temp = t1;
  503. t1 = t0;
  504. t0 = temp;
  505. }
  506. if (t0 > 1.f || t1 < 0.f) {
  507. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  508. continue;//move to next line
  509. }
  510. if (t0 < 0.f) t0 = 0.f;
  511. if (t1 < 0.f) t1 = 0.f;
  512. if (t0 > 1.f) t0 = 1.f;
  513. if (t1 > 1.f) t1 = 1.f;
  514. }
  515.  
  516. float t = 1.f;
  517. if (!embedded_in_plane) {
  518. union opt_vecf plane_intersection_point = vec3add(vec3sub(base, normal), vec3multf(vel_y, t0));
  519. if (plane_intersection_point.y >= y0 && plane_intersection_point.y <= y1) {
  520. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  521. continue;
  522. }
  523. }
  524. }
  525. if(!in_z) {
  526. normal = new_vec3(0, 0, (float)(up * 1 + down * -1));
  527. embedded_in_plane = false;
  528. double signed_distance_to_line = plane_signed_distance_to(base, new_vec3(0, 0, (float)(new_z0 * (uint64_t)down + new_z1 * (uint64_t)up));
  529. float normal_dot_velocity2 = dot(normal, vel_y);
  530.  
  531. if (normal_dot_velocity == 0.f) {
  532. if (fabs(signed_distance_to_line) <= 1.f) {
  533. embedded_in_plane = true;
  534. t0 = 0.f; //spheroid is colliding with triangle for the entire time interval
  535. t1 = 1.f;
  536. }
  537. } else {
  538. t0 = (-1.f - signed_distance_to_line) / normal_dot_velocity;
  539. t1 = ( 1.f - signed_distance_to_line) / normal_dot_velocity;
  540. if (t0 > t1) {
  541. double temp = t1;
  542. t1 = t0;
  543. t0 = temp;
  544. }
  545. if (t0 > 1.f || t1 < 0.f) {
  546. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  547. continue;//move to next line
  548. }
  549. if (t0 < 0.f) t0 = 0.f;
  550. if (t1 < 0.f) t1 = 0.f;
  551. if (t0 > 1.f) t0 = 1.f;
  552. if (t1 > 1.f) t1 = 1.f;
  553. }
  554.  
  555. float t = 1.f;
  556. if (!embedded_in_plane) {
  557. union opt_vecf plane_intersection_point = vec3add(vec3sub(base, normal), vec3multf(vel_y, t0));
  558. if (plane_intersection_point.y >= y0 && plane_intersection_point.y <= y1) {
  559. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  560. continue;
  561. }
  562. }
  563. }
  564.  
  565. union opt_vecf p1 = new_vec3(new_x0,0,new_y0);
  566. union opt_vecf p2 = new_vec3(new_x0,0,new_y1);
  567. union opt_vecf p3 = new_vec3(new_x1,0,new_y1);
  568. union opt_vecf p4 = new_vec3(new_x0,0,new_y1);
  569.  
  570. union opt_vecf p1_minus_base = vec3sub(p1,base);
  571. union opt_vecf p2_minus_base = vec3sub(p2,base);
  572. union opt_vecf p3_minus_base = vec3sub(p3,base);
  573. union opt_vecf p4_minus_base = vec3sub(p4,base);
  574.  
  575.  
  576. float velocity_squared_length = dot(velocity, velocity);
  577. float a,b,c, new_t;
  578.  
  579. a = velocity_squared_length;
  580. b = 2.f * dot(velocity,vec3sub(base,p1);
  581. c = dot(p1_minus_base,p1_minus_base) - 1.f;
  582.  
  583. if (get_lowest_root(a,b,c,t,&new_t)) {
  584. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  585. continue;
  586. }
  587.  
  588. b = 2.f * dot(velocity,vec3sub(base,p2));
  589. c = dot(p2_minus_base,p2_minus_base) - 1.f;
  590. if (get_lowest_root(a,b,c,t,&new_t)) {
  591. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  592. continue;
  593. }
  594.  
  595. b = 2.f * dot(velocity,vec3sub(base,tri.p3));
  596. c = dot(p3_minus_base,p3_minus_base) - 1.f;
  597. if (get_lowest_root(a,b,c,t,&new_t)) {
  598. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  599. continue;
  600. }
  601.  
  602. b = 2.f * dot(velocity,vec3sub(base,tri.p4));
  603. c = dot(p4_minus_base,p4_minus_base) - 1.f;
  604. if (get_lowest_root(a,b,c,t,&new_t)) {
  605. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  606. continue;
  607. }
  608.  
  609. }
  610. }
  611. }
  612. /*for (x = 0; x < 4; ++x ) {
  613. if (node->child[x]) {
  614. int64_t new_x0, new_x1, new_z0, new_z1;
  615. gen_new_coords(x,x0,x1,z0,z1,&new_x0,&new_x1,&new_z0,&new_z1);
  616.  
  617. n_x0 = (double) *new_x0;
  618. n_x1 = (double) *new_x1;
  619. n_z0 = (double) *new_z0;
  620. n_z1 = (double) *new_z1;
  621.  
  622. up = null;
  623.  
  624. //case 0: no x or z overlap with quadrant => do not check quadrant. Skip to next iteration of for loop.
  625.  
  626. for (int i = 0; i < 4; ++i) {
  627.  
  628. //can eliminate if statements by storing bools in an array and adding the elements of the array. If the sum > 0 for x or z, in_x or in_z respectively must be true. Can experiment with this once implemented.
  629. if(mb_x[i] > n_x0 && mb_x[i] < n_x1) in_x = true; //if a movement bounds vertex lies within the x range, note it
  630. if(mb_z[i] > n_z0 && mb_z[i] < n_z1) in_z = true; //if a movement bounds vertex lies within the z range, note it
  631. }
  632.  
  633. if(!(in_x || in_z)){ //if no x or z overlap, skip
  634. continue;
  635. }
  636.  
  637.  
  638.  
  639. //case 1: a vertex lies in a quadrant => check quadrant
  640. for (i = 0; i < 4; ++i) {
  641. if (mb_x[i] >= n_x0 && mb_x[i] <= n_x1) {
  642. if(mb_z[i] >= n_z0 && mb_z[i] <= n_z1){
  643. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  644. break;
  645. }
  646. }
  647. }
  648.  
  649. //case 2: a line is parallel to a quadrant => simple check to determine if it's inside (remember no vertices lie within bounds)
  650. if (mb_x[0] == mb_x[1] || mb_y[0] == mb_y[1]) { //lines are parallel to quadrant
  651. up = false;
  652. down = false;
  653. left = false;
  654. right = false;
  655.  
  656. checked = true; //marked so we don't re-check these booleans later
  657. for (int i = 0, i < 4, ++i) {
  658. //can eliminate if statements by storing bools in an array and adding the elements of the array. If the sum > 0 for any boolean's array dimension, the boolean is true. Can experiment with this once implemented.
  659. if (mb_x[i] > n_x1) right = true;
  660. if (mb_x[i] < n_x0) left = true;
  661. if (mb_z[i] > n_z1) up = true;
  662. if (mb_z[i] < n_z0) down = true;
  663.  
  664. if (left && right || up && down) { //if the parallel movement bounds crosses the quadrant across either x or z (we know the movement bounds lie within the x or z ranges from the check above)
  665. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  666. break;
  667. }
  668. }
  669. continue; //intersection impossible, do not check quadrant
  670. }
  671.  
  672. //case 3: no vertex lies in a quadrant and no vertex is parallel
  673. //case 3a: one vertex lies inside x or z bounds, adjacent vertex lies inside other coordinate's bounds => check for solution of line formed by the two points with edge of quadrant
  674. //case 3b: 3a's condition is not met, intersection is impossible. Do not check quadrant.
  675. //REWRITE THIS. IT DOESN'T EVEN KIND OF WORK.
  676. for (i = 0; i < 4; ++i) { //CAN RUN IF STATEMENTS TO ELIMINATE SOME OR ALL OF THESE CHECKS
  677.  
  678. point2 = (i+1)%4; //for the base case you take the vector from current point to point + 1, if i=3 you need a vector from the last point to the first point. This statement accomplishes this.
  679.  
  680.  
  681. if (!(n_x0 > mb_x[i] && n_x0 > mb_x[point2])) {
  682. //z_theta_new_x0 is the z value of the line from the first point to second point at new_x0, the leftmost vertical boundary of the quadrant. If z_theta lies within the z bounds of the quadrant and lies on the line segment, then the lines intersect.
  683. z_theta_new_x0 = (n_x0 - mb_x[i]) * (mb_z[point2] - mb_z[i]) / (mb_x[point2] - mb_x[i]) + mb_z[i];
  684. if (z_theta_new_x0 >= n_z0 && z_theta_new_x0 <= n_z1 ) {
  685. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  686. break;
  687. }
  688. continue;
  689. }
  690. if (!(n_x1 < mb_x[i] && n_x1 < mb_x[point2])) {
  691. z_theta_new_x1 = (n_x1 - mb_x[i]) * (mb_z[point2] - mb_z[i]) / (mb_x[point2] - mb_x[i]) + mb_z[i];
  692. if (z_theta_new_x1 >= n_z0 && z_theta_new_x1 <= n_z1 ) {
  693. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  694. break;
  695. }
  696. continue;
  697. }
  698. if (!(n_z0 > mb_z[i] && n_z0 > mb_z[point2])) {
  699. //x_theta_new_z0 is the x value of the line from the first point to second point at new_z0, the bottom horizontal boundary of the quadrant. If x_theta lies within the x bounds of the quadrant and lies on the line segment, then the lines intersect.
  700. x_theta_new_z0 = (n_z0 - mb_z[i]) * (mb_x[point2] - mb_x[i]) / (mb_z[point2] - mb_z[i]) + mb_x[i];
  701. if (x_theta_new_z0 >= n_x0 && x_theta_new_z0 <= n_x1 ) {
  702. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  703. break;
  704. }
  705. continue;
  706. }
  707. if (!(n_z1 < mb_y[i] && n_z0 < mb_y[point2])) {
  708. x_theta_new_z1 = (n_z1 - mb_z[i]) * (mb_x[point2] - mb_x[i]) / (mb_z[point2] - mb_z[i]) + mb_x[i];
  709. if (x_theta_new_z1 >= n_x0 && x_theta_new_z1 <= n_x1 ) {
  710. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  711. break;
  712. }
  713. continue;
  714. }
  715. }
  716.  
  717. //case 4: movement bounds enclose quadrant => check quadrant
  718.  
  719. if (checked = false) {
  720. up = false;
  721. down = false;
  722. left = false;
  723. right = false;
  724. for (int i = 0, i < 4, ++i) {
  725. if (mb_x[i] > n_x1) {
  726. right = true;
  727. }
  728. if (mb_x[i] < n_x0) {
  729. left = true;
  730. }
  731. if (mb_z[i] > n_z1) {
  732. up = true;
  733. }
  734. if (mb_z[i] < n_z0) {
  735. down = true;
  736. }
  737. }
  738. }
  739.  
  740.  
  741. if (up && down && left && right) {
  742. check_collision_recursive(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  743. }
  744.  
  745. }
  746. }*/
  747. }
  748.  
  749. void check_collision_recursive_r3(struct collision_node *node, struct collision_info_r3 *info, const int64_t x0, const int64_t x1, const int64_t z0, const int64_t z1) {
  750. uint32_t x;
  751. for (x = 0; x < node->object_count; ++x) {
  752. check_triangle_r3(info, node->triangle[x]);
  753. }
  754.  
  755. //IMPLEMENT ACQUISITION OF RECTANGE VERTICES
  756.  
  757.  
  758. /*for (x = 0; x < 4; ++x ) {
  759. if (node->child[x]) {
  760. int64_t new_x0, new_x1, new_z0, new_z1;
  761. gen_new_coords(x,x0,x1,z0,z1,&new_x0,&new_x1,&new_z0,&new_z1);
  762. const float e = 100.f; // change this to movement speed
  763. if (info->r3_position.f[0] + e >= new_x0 && info->r3_position.f[0] - e <= new_x1) {
  764. if (info->r3_position.f[2] + e >= new_z0 && info->r3_position.f[2] - e <= new_z1) {
  765. check_collision_recursive_r3(node->child[x],info,new_x0,new_x1,new_z0,new_z1);
  766. }
  767. }
  768. }
  769. }*/
  770. }
  771.  
  772.  
  773.  
  774. bool check_collision(struct collision_node *node, struct collision_info *info) {
  775. const int64_t max = game.settings.max_width;
  776. check_collision_recursive(node, info, -max, max, -max, max);
  777. return info->collision_found;
  778. }
  779.  
  780. bool check_collision_r3(struct collision_node *node, struct collision_info_r3 *info) {
  781. const int64_t max = game.settings.max_width;
  782. check_collision_recursive_r3(node, info, -max, max, -max, max);
  783. return info->collision_found;
  784. }
  785.  
  786. float gravity(struct Combat_entity *entity) {
  787. //edit constants
  788. const float acceleration = 0.0005f;
  789. const float max_speed = 0.95f;
  790. const float jump_speed = 0.171f;
  791. float gravity_speed;
  792. if (entity->jumping) {
  793. gravity_speed = jump_speed-acceleration*(game.current_time-entity->player_initial_fall_time-game.settings.target_tickrate);
  794. if (entity->touched_something_while_jumping && gravity_speed > 0.f) {
  795. entity->player_initial_fall_time = game.current_time;
  796. entity->jumping = false;
  797. return 0.f;
  798. }
  799. return gravity_speed;
  800. }
  801.  
  802. if (entity->gravity_acting) {
  803. gravity_speed = -acceleration*(game.current_time-entity->player_initial_fall_time-game.settings.target_tickrate);
  804. if (gravity_speed <= -max_speed) {
  805. return -max_speed;
  806. }
  807. return gravity_speed;
  808. } else {
  809. return 0.f;
  810. }
  811. }
  812.  
  813. union opt_vecf m(struct collision_node *node, struct collision_info *info, const uint8_t depth, union opt_vecf e_space_position, union opt_vecf e_space_velocity, struct Combat_entity *player) {
  814. if (depth > 4) {
  815. e_space_position.f[1] += 0.008f;
  816. puts("ERROR CONDITION OCCURED");fflush(stdout);
  817. return e_space_position;
  818. }
  819. //union opt_vecf original_velocity_vector;
  820. //if(depth == 0) {
  821. //original_velocity_vector = e_space_velocity;
  822. /*
  823. if(e_space_velocity.f[1] == 0.f) {
  824. //e_space_velocity.f[1] -= 0.1f; //adds some negative y vector fudge factor to keep you grounded if you travel downhill on a surface you can stand on.
  825. } //this should be changed to some generalized value to fit all cases
  826. */
  827. //} //the alternative to using a fudge factor is to use vector algebra to actually "snap" the player to the ground. I really cba.
  828.  
  829.  
  830. info->velocity = e_space_velocity;
  831. info->normalized_velocity = vec3normalize(e_space_velocity);
  832. info->base_point = e_space_position;
  833. info->collision_found = false;
  834. check_collision(node, info);
  835. if (!info->collision_found){
  836. return vec3add(e_space_position, e_space_velocity);
  837. }
  838. if (player->jumping) {
  839. player->touched_something_while_jumping = true;
  840. }
  841. if (vec3normalize(vec3sub(info->base_point,info->intersection_point)).f[1] > 0.8f) { //explain physical significance
  842. player->jumping = false;
  843. player->touched_something_while_jumping = false;
  844. player->gravity_acting = false;
  845. player->player_initial_fall_time = game.current_time;
  846. }
  847. if (vec3normalize(vec3sub(info->base_point,info->intersection_point)).f[1] < -0.93969262078f){ //explain physical significance
  848. player->jumping = false;
  849. player->player_initial_fall_time = game.current_time;
  850. }
  851. const float close_distance = 0.004f;
  852. union opt_vecf new_base_point = e_space_position;
  853.  
  854. if (info->nearest_distance >= close_distance) {
  855. union opt_vecf v = vec3set_length(e_space_velocity,info->nearest_distance-close_distance);
  856. new_base_point = vec3add(info->base_point,v);
  857. v = vec3normalize(v);
  858. info->intersection_point = vec3sub(info->intersection_point,vec3multf(v,close_distance));
  859. }
  860.  
  861. if (vec3normalize(vec3sub(info->base_point,info->intersection_point)).f[1] > 0.8f) {//if you're on a surface you can stand on
  862. if (player->gravity_acting && gravity(player) < -0.07f) { //if gravity is acting on you noticeably
  863. return new_base_point; //disallows sliding due to gravity
  864. }
  865. }
  866.  
  867.  
  868. if(depth == 0 && gravity(player) == 0.f) { //if you added a fudge factor to stay grounded earlier
  869. //e_space_velocity.f[1] += 0.1f; //subtracts out the y vector so it doesn't affect sliding.
  870. info->velocity = e_space_velocity; //corrects collision info information to account for this change
  871. //return m(node, info, depth+1, new_base_point, e_space_velocity, player);
  872. }
  873.  
  874. union opt_vecf destination_point = vec3add(e_space_position, e_space_velocity); //calculates destination point with new, fudge factor-less velocity
  875.  
  876.  
  877. union opt_vecf new_velocity_vector;
  878. struct tPlane sliding_plane;
  879. sliding_plane.normal = vec3normalize(vec3sub(new_base_point,info->intersection_point));
  880. sliding_plane.origin = info->intersection_point;
  881. sliding_plane.equation[3] = -dot(sliding_plane.normal, sliding_plane.origin);
  882.  
  883.  
  884. if(vec3normalize(vec3sub(new_base_point,info->intersection_point)).f[1] > 0.8f && info->sliding_plane.normal.f[1] != 0.f || !player->gravity_acting) { //add comments explaining snapping
  885. union opt_vecf intersection_plus_velocity = vec3add(info->intersection_point, new_vec3(e_space_velocity.f[0], 0.f, e_space_velocity.f[2]));
  886. union opt_vecf snapped_destination = find_point_in_plane_xz(sliding_plane, intersection_plus_velocity.f[0], intersection_plus_velocity.f[2]);
  887. new_velocity_vector = vec3sub(snapped_destination, info->intersection_point);
  888. if (vec3gen_length(new_velocity_vector) < close_distance) {
  889. return new_base_point;
  890. }
  891. return m(node, info, depth+1, new_base_point, new_velocity_vector, player);
  892. }
  893. union opt_vecf new_destination_point = vec3sub(destination_point,vec3multf(sliding_plane.normal,plane_signed_distance_to(destination_point,sliding_plane)));
  894. new_velocity_vector = vec3sub(new_destination_point,info->intersection_point);
  895.  
  896. /*if(!vec3normalize(vec3sub(info->base_point,info->intersection_point)).f[1] > 0.8f){
  897. new_velocity_vector.f[1] = 0;
  898. }*/
  899.  
  900. if (vec3gen_length(new_velocity_vector) < close_distance) {
  901. return new_base_point;
  902. }
  903. return m(node, info, depth+1, new_base_point, new_velocity_vector, player);
  904. }
  905.  
  906. bool check_los (struct collision_node *node, struct Combat_entity *player1, union opt_vecf r3_point) {
  907. struct collision_info_r3 info;
  908. info.r3_position = vec3add(player1->position, new_vec3(0.f,1.f,0.f)); //NEED TO STORE PLAYER RADII ON THE PLAYER OBJECT. ADD THE Y VALUE OF THE RADII VECTOR. ty dude
  909. info.r3_velocity = vec3sub(r3_point,player1->position);
  910. info.collision_found = false;
  911. check_collision_r3(node, &info);
  912. if (!info.collision_found) return true;
  913. return false;
  914. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!