1 /*
2 * Copyright (C) Volition, Inc. 1999. All rights reserved.
3 *
4 * All source code herein is the property of Volition, Inc. You may not sell
5 * or otherwise commercially exploit the source or things you created based on the
6 * source.
7 *
8 */
9
10
11 #include "globalincs/linklist.h"
12 #include "io/timer.h"
13 #include "object/objcollide.h"
14 #include "object/object.h"
15 #include "object/objectdock.h"
16 #include "ship/ship.h"
17 #include "tracing/tracing.h"
18 #include "weapon/beam.h"
19 #include "weapon/weapon.h"
20 #include "tracing/Monitor.h"
21
22
23 // the next 2 variables are used for pair statistics
24 // also in weapon.cpp there is Weapons_created.
25 int Num_pairs = 0;
26 int Num_pairs_checked = 0;
27
28 SCP_vector<int> Collision_sort_list;
29
30 class collider_pair
31 {
32 public:
33 object *a;
34 object *b;
35 int signature_a;
36 int signature_b;
37 int next_check_time;
38 bool initialized;
39
40 // we need to define a constructor because the hash map can
41 // implicitly insert an object when we use the [] operator
collider_pair()42 collider_pair()
43 : a(nullptr), b(nullptr), signature_a(-1), signature_b(-1), next_check_time(-1), initialized(false)
44 {}
45 };
46
47 SCP_unordered_map<uint, collider_pair> Collision_cached_pairs;
48
49 class checkobject;
50 extern checkobject CheckObjects[MAX_OBJECTS];
51
52 // returns true if we should reject object pair if one is child of other.
reject_obj_pair_on_parent(object * A,object * B)53 int reject_obj_pair_on_parent(object *A, object *B)
54 {
55 if (A->flags[Object::Object_Flags::Collides_with_parent] || B->flags[Object::Object_Flags::Collides_with_parent])
56 return 0;
57
58 if (A->type == OBJ_SHIP) {
59 if (B->type == OBJ_DEBRIS) {
60 if (B->parent_sig == A->signature) {
61 return 0;
62 }
63 }
64 }
65
66 if (B->type == OBJ_SHIP) {
67 if (A->type == OBJ_DEBRIS) {
68 if (A->parent_sig == B->signature) {
69 return 0;
70 }
71 }
72 }
73
74 if (A->parent_sig == B->signature) {
75 return 1;
76 }
77
78 if (B->parent_sig == A->signature) {
79 return 1;
80 }
81
82 return 0;
83 }
84
reject_due_collision_groups(object * A,object * B)85 int reject_due_collision_groups(object *A, object *B)
86 {
87 if (A->collision_group_id == 0 || B->collision_group_id == 0)
88 return 0;
89
90 return (A->collision_group_id & B->collision_group_id);
91 }
92
93 MONITOR(NumPairs)
MONITOR(NumPairsChecked)94 MONITOR(NumPairsChecked)
95
96 // See if two lines intersect by doing recursive subdivision.
97 // Bails out if larger distance traveled is less than sum of radii + 1.0f.
98 int collide_subdivide(vec3d *p0, vec3d *p1, float prad, vec3d *q0, vec3d *q1, float qrad)
99 {
100 float a_dist = vm_vec_dist(p0, p1);
101 float b_dist = vm_vec_dist(q0, q1);
102 float ab_dist = vm_vec_dist(p1, q1);
103
104 // See if their spheres intersect
105 if (ab_dist < a_dist + b_dist + prad + qrad) {
106 if (ab_dist < prad + qrad)
107 return 1;
108 else if (vm_vec_dist(p0, q0) < prad + qrad)
109 return 1;
110 else if (MAX(a_dist, b_dist) < prad + qrad + 1.0f)
111 return 0;
112 else {
113 int r1, r2 = 0;
114 vec3d pa, qa;
115
116 vm_vec_avg(&pa, p0, p1);
117 vm_vec_avg(&qa, q0, q1);
118 r1 = collide_subdivide(p0, &pa, prad, q0, &qa, qrad);
119 if (!r1)
120 r2 = collide_subdivide(&pa, p1, prad, &qa, q1, qrad);
121
122 return r1 | r2;
123 }
124 } else
125 return 0;
126 }
127
128
129
130 // Return true if object A is expected to collide with object B within time duration
131 // For purposes of this check, the first object moves from current location to predicted
132 // location. The second object is assumed to be where it will be at time duration, NOT
133 // where it currently is.
134 // radius_scale is used to control the precision of the check.
135 // If 0.0, then use polygon models to perform check, slow and accurate
136 // If !0.0, then use as a scale on the radius of the objects. 1.0 is Descent style
137 // collisions. Larger values can be used to be sloppy about the collisions which
138 // is useful if a moving object wants to prevent a collision.
objects_will_collide(object * A,object * B,float duration,float radius_scale)139 int objects_will_collide(object *A, object *B, float duration, float radius_scale)
140 {
141 vec3d hitpos;
142 int ret;
143
144
145 vec3d prev_pos = A->pos;
146 vm_vec_scale_add2(&A->pos, &A->phys_info.vel, duration);
147
148 if (radius_scale == 0.0f) {
149 ret = ship_check_collision_fast(B, A, &hitpos);
150 } else {
151 vec3d nearest_point;
152
153 const float size_A = A->radius * radius_scale;
154 const float size_B = B->radius * radius_scale;
155
156 // If A is moving, check along vector.
157 if (A->phys_info.speed != 0.0f) {
158 const float r = find_nearest_point_on_line(&nearest_point, &prev_pos, &A->pos, &B->pos);
159 if (r < 0) {
160 nearest_point = prev_pos;
161 } else if (r > 1) {
162 nearest_point = A->pos;
163 }
164 const float dist = vm_vec_dist_quick(&B->pos, &nearest_point);
165 ret = (dist < size_A + size_B);
166 } else {
167 ret = vm_vec_dist_quick(&B->pos, &prev_pos) < size_A + size_B;
168 }
169 }
170
171 // Reset the position to the previous value
172 A->pos = prev_pos;
173
174 return ret;
175 }
176
177 // Return true if the vector from *start_pos to *end_pos is within objp->radius*radius_scale of *objp
vector_object_collision(vec3d * start_pos,vec3d * end_pos,object * objp,float radius_scale)178 int vector_object_collision(vec3d *start_pos, vec3d *end_pos, object *objp, float radius_scale)
179 {
180 vec3d nearest_point;
181
182 float r = find_nearest_point_on_line(&nearest_point, start_pos, end_pos, &objp->pos);
183 if ((r >= 0.0f) && (r <= 1.0f)) {
184 float dist = vm_vec_dist_quick(&objp->pos, &nearest_point);
185
186 return (dist < objp->radius * radius_scale);
187 } else
188 return 0;
189 }
190
191 // Returns TRUE if the weapon will never hit the other object.
192 // If it can it predicts how long until these two objects need
193 // to be checked and fills the time in in current_pair.
weapon_will_never_hit(object * obj_weapon,object * other,obj_pair * current_pair)194 int weapon_will_never_hit( object *obj_weapon, object *other, obj_pair * current_pair )
195 {
196
197 Assert( obj_weapon->type == OBJ_WEAPON );
198 weapon *wp = &Weapons[obj_weapon->instance];
199 weapon_info *wip = &Weapon_info[wp->weapon_info_index];
200
201 // Do some checks for weapons that don't turn
202 if ( !(wip->wi_flags[Weapon::Info_Flags::Turns]) ) {
203
204 // This first check is to see if a weapon is behind an object, and they
205 // are heading in opposite directions. If so, we don't need to ever check
206 // them again. This is only valid for weapons that don't turn.
207
208 float vdot;
209 if (wip->subtype == WP_LASER) {
210 vec3d velocity_rel_weapon;
211 vm_vec_sub(&velocity_rel_weapon, &obj_weapon->phys_info.vel, &other->phys_info.vel);
212 vdot = -vm_vec_dot(&velocity_rel_weapon, &obj_weapon->orient.vec.fvec);
213 } else {
214 vdot = vm_vec_dot( &other->phys_info.vel, &obj_weapon->phys_info.vel);
215 }
216 if ( vdot <= 0.0f ) {
217 // They're heading in opposite directions...
218 // check their positions
219 vec3d weapon2other;
220 vm_vec_sub( &weapon2other, &other->pos, &obj_weapon->pos );
221 float pdot = vm_vec_dot( &obj_weapon->orient.vec.fvec, &weapon2other );
222 if ( pdot <= -other->radius ) {
223 // The other object is behind the weapon by more than
224 // its radius, so it will never hit...
225 return 1;
226 }
227 }
228
229 // FUTURE ENHANCEMENT IDEAS
230
231 // Given a laser does it hit a slow or not moving object
232 // in its life or the next n seconds? We'd actually need to check the
233 // model for this.
234 }
235
236
237 // This check doesn't care about orient, only looks at the maximum speed
238 // of the two objects, so it knows that in the next n seconds, they can't
239 // go further than some distance, so don't bother checking collisions for
240 // that time. This is very rough, but is so general that it works for
241 // everything and immidiately gets rid of a lot of cases.
242
243 if ( current_pair ) {
244 // Find the time it will take before these get within each others distances.
245 // tmp->next_check_time = timestamp(500);
246 //vector max_vel; //maximum foward velocity in x,y,z
247
248 float max_vel_weapon;
249
250 //SUSHI: Fix bug where additive weapon velocity screws up collisions
251 //If the PF_CONST_VEL flag is set, we can safely assume it doesn't change speed.
252 if (obj_weapon->phys_info.flags & PF_CONST_VEL)
253 max_vel_weapon = obj_weapon->phys_info.speed;
254 else if (wp->lssm_stage==5)
255 max_vel_weapon = wip->lssm_stage5_vel;
256 else
257 max_vel_weapon = wp->weapon_max_vel;
258
259 float max_vel_other = other->phys_info.max_vel.xyz.z;
260 if (max_vel_other < 10.0f) {
261 if ( vm_vec_mag_squared( &other->phys_info.vel ) > 100 ) {
262 // bump up velocity from collision
263 max_vel_other = vm_vec_mag( &other->phys_info.vel ) + 10.0f;
264 } else {
265 max_vel_other = 10.0f; // object may move from collision
266 }
267 }
268
269 // check weapon that does not turn against sphere expanding at ship maxvel
270 // compare (weapon) ray with expanding sphere (ship) to find earliest possible collision time
271 // look for two time solutions to Xw = Xs, where Xw = Xw0 + Vwt*t Xs = Xs + Vs*(t+dt), where Vs*dt = radius of ship
272 // Since direction of Vs is unknown, solve for (Vs*t) and find norm of both sides
273 if ( !(wip->wi_flags[Weapon::Info_Flags::Turns]) && (obj_weapon->phys_info.flags & PF_CONST_VEL) ) {
274 vec3d delta_x, weapon_vel;
275 float a,b,c, delta_x_dot_vl, delta_t;
276 float root1, root2, root, earliest_time;
277
278 vm_vec_sub( &delta_x, &obj_weapon->pos, &other->pos );
279 weapon_vel = obj_weapon->phys_info.vel;
280 float weapon_speed = vm_vec_mag(&weapon_vel);
281
282 if (weapon_speed == max_vel_other) {
283 // this will give us NAN using the below formula, so check every frame
284 current_pair->next_check_time = timestamp(0);
285 return 0;
286 }
287
288 // vm_vec_copy_scale( &laser_vel, &weapon->orient.vec.fvec, max_vel_weapon );
289 delta_t = (other->radius + 10.0f) / max_vel_other; // time to get from center to radius of other obj
290 delta_x_dot_vl = vm_vec_dot( &delta_x, &weapon_vel);
291
292 a = weapon_speed * weapon_speed - max_vel_other*max_vel_other;
293 b = 2.0f * (delta_x_dot_vl - max_vel_other*max_vel_other*delta_t);
294 c = vm_vec_mag_squared( &delta_x ) - max_vel_other*max_vel_other*delta_t*delta_t;
295
296 float discriminant = b*b - 4.0f*a*c;
297 if ( discriminant < 0) {
298 // neither entity passes the other
299 if (c < 0) {
300 // ship outpaces weapon
301 current_pair->next_check_time = timestamp(0); // check next time
302 return 0;
303 } else {
304 // weapon outpaces ship; will never hit
305 return 1;
306 }
307 } else {
308 root = fl_sqrt( discriminant );
309 root1 = (-b + root) / (2.0f * a) * 1000.0f; // get time in ms
310 root2 = (-b - root) / (2.0f * a) * 1000.0f; // get time in ms
311 }
312
313 // standard algorithm
314 if (weapon_speed > max_vel_other) {
315 // find earliest positive time
316 if ( root1 > root2 ) {
317 float temp = root1;
318 root1 = root2;
319 root2 = temp;
320 }
321
322 if (root1 > 0) {
323 earliest_time = root1;
324 } else if (root2 > 0) {
325 // root1 < 0 and root2 > 0, so we're inside sphere and next check should be next frame
326 current_pair->next_check_time = timestamp(0); // check next time
327 return 0;
328 } else {
329 // both times negative, so never collides
330 return 1;
331 }
332 }
333 // need to modify it for weapons that are slower than ships
334 else {
335 if (root2 > 0) {
336 earliest_time = root2;
337 } else {
338 current_pair->next_check_time = timestamp(0);
339 return 0;
340 }
341 }
342
343 // check if possible collision occurs after weapon expires
344 if ( earliest_time > 1000*wp->lifeleft )
345 return 1;
346
347 // Allow one worst case frametime to elapse (~5 fps)
348 earliest_time -= 200.0f;
349
350 if (earliest_time > 100) {
351 current_pair->next_check_time = timestamp( fl2i(earliest_time) );
352 return 0;
353 } else {
354 current_pair->next_check_time = timestamp(0); // check next time
355 return 0;
356 }
357
358 } else {
359 const float max_vel = max_vel_weapon + max_vel_other;
360
361 // suggest that fudge factor for other radius be changed to other_radius + const (~10)
362 const float dist = vm_vec_dist( &other->pos, &obj_weapon->pos ) - (other->radius + 10.0f);
363 if ( dist > 0.0f ) {
364 const float time = (dist*1000.0f) / max_vel;
365 int time_ms = fl2i(time);
366
367 // check if possible collision occurs after weapon expires
368 if ( time_ms > 1000*wp->lifeleft )
369 return 1;
370
371 time_ms -= 200; // Allow at least one worst case frametime to elapse (~5 fps)
372
373 if ( time_ms > 100 ) { // If it takes longer than 1/10th of a second, then delay it
374 current_pair->next_check_time = timestamp(time_ms);
375 //mprintf(( "Delaying %d ms\n", time_ms ));
376 return 0;
377 }
378 }
379 current_pair->next_check_time = timestamp(0); // check next time
380
381 }
382 }
383
384 return 0;
385 }
386
387 // Return true if vector from *curpos to *goalpos intersects with object *goalobjp
388 // Else, return false.
389 // radius is radius of object moving from curpos to goalpos.
pp_collide(vec3d * curpos,vec3d * goalpos,object * goalobjp,float radius)390 int pp_collide(vec3d *curpos, vec3d *goalpos, object *goalobjp, float radius)
391 {
392 mc_info mc;
393 mc_info_init(&mc);
394
395 Assert(goalobjp->type == OBJ_SHIP);
396
397 mc.model_instance_num = Ships[goalobjp->instance].model_instance_num;
398 mc.model_num = Ship_info[Ships[goalobjp->instance].ship_info_index].model_num; // Fill in the model to check
399 mc.orient = &goalobjp->orient; // The object's orient
400 mc.pos = &goalobjp->pos; // The object's position
401 mc.p0 = curpos; // Point 1 of ray to check
402 mc.p1 = goalpos; // Point 2 of ray to check
403 mc.flags = MC_CHECK_MODEL | MC_CHECK_SPHERELINE;
404 mc.radius = radius;
405
406 model_collide(&mc);
407
408 return mc.num_hits;
409 }
410
411 // Setup and call pp_collide for collide_predict_large_ship
412 // Returns true if objp will collide with objp2 before it reaches goal_pos.
cpls_aux(vec3d * goal_pos,object * objp2,object * objp)413 int cpls_aux(vec3d *goal_pos, object *objp2, object *objp)
414 {
415 float radius = objp->radius;
416 if (1.5f * radius < 70.0f)
417 radius *= 1.5f;
418 else
419 radius = 70.0f;
420
421 if (pp_collide(&objp->pos, goal_pos, objp2, radius))
422 return 1;
423 else
424 return 0;
425 }
426
427 // Return true if objp will collide with some large object.
428 // Don't check for an object this ship is docked to.
collide_predict_large_ship(object * objp,float distance)429 int collide_predict_large_ship(object *objp, float distance)
430 {
431 object *objp2;
432 vec3d goal_pos;
433 ship_info* sip = &Ship_info[Ships[objp->instance].ship_info_index];
434
435 vec3d cur_pos = objp->pos;
436
437 vm_vec_scale_add(&goal_pos, &cur_pos, &objp->orient.vec.fvec, distance);
438
439 for ( objp2 = GET_FIRST(&obj_used_list); objp2 != END_OF_LIST(&obj_used_list); objp2 = GET_NEXT(objp2) ) {
440 if ((objp != objp2) && (objp2->type == OBJ_SHIP)) {
441 if (Ship_info[Ships[objp2->instance].ship_info_index].is_big_or_huge()) {
442 if (dock_check_find_docked_object(objp, objp2))
443 continue;
444
445 if (cpls_aux(&goal_pos, objp2, objp))
446 return 1;
447 }
448 } else if (!(sip->is_big_or_huge()) && (objp2->type == OBJ_ASTEROID)) {
449 if (vm_vec_dist_quick(&objp2->pos, &objp->pos) < (distance + objp2->radius)*2.5f) {
450 vec3d delvec;
451
452 const float d1 = 2.5f * distance + objp2->radius;
453 auto count = (int) (d1/(objp2->radius + objp->radius)); // Scale up distance, else looks like there would be a collision.
454 vec3d pos = cur_pos;
455 vm_vec_normalized_dir(&delvec, &goal_pos, &cur_pos);
456 vm_vec_scale(&delvec, d1/count);
457
458 for (; count>0; count--) {
459 if (vm_vec_dist_quick(&pos, &objp2->pos) < objp->radius + objp2->radius)
460 return 1;
461 vm_vec_add2(&pos, &delvec);
462 }
463 }
464 }
465 }
466
467 return 0;
468 }
469
470 // function to iterate through all object collision pairs looking for weapons
471 // which could be deleted since they are not going to hit anything. Passed into this
472 // function is a 'time' parameter used as watermark for which weapons to check.
473
474 #define CRW_NO_OBJECT -1
475 #define CRW_NO_PAIR 0
476 #define CRW_IN_PAIR 1
477 #define CRW_CAN_DELETE 2
478
479 #define CRW_MAX_TO_DELETE 4
480
481 char crw_status[MAX_WEAPONS];
482
crw_check_weapon(int weapon_num,int collide_next_check)483 void crw_check_weapon( int weapon_num, int collide_next_check )
484 {
485 weapon *wp = &Weapons[weapon_num];
486
487 // if this weapons life left > time before next collision, then we cannot remove it
488 crw_status[WEAPON_INDEX(wp)] = CRW_IN_PAIR;
489 const float next_check_time = ((float)(timestamp_until(collide_next_check)) / 1000.0f);
490 if ( wp->lifeleft < next_check_time )
491 crw_status[WEAPON_INDEX(wp)] = CRW_CAN_DELETE;
492 }
493
collide_remove_weapons()494 int collide_remove_weapons( )
495 {
496 // setup remove_weapon array. assume we can remove it.
497 for (int i = 0; i < MAX_WEAPONS; i++ ) {
498 if ( Weapons[i].objnum == -1 )
499 crw_status[i] = CRW_NO_OBJECT;
500 else
501 crw_status[i] = CRW_NO_PAIR;
502 }
503
504 // first pass is to see if any of the weapons don't have collision pairs.
505 for (auto& pair : Collision_cached_pairs) {
506 collider_pair* pair_obj = &pair.second;
507
508 if (!pair_obj->initialized) {
509 continue;
510 }
511
512 if (pair_obj->a->type == OBJ_WEAPON && pair_obj->signature_a == pair_obj->a->signature) {
513 crw_check_weapon(pair_obj->a->instance, pair_obj->next_check_time);
514
515 if (crw_status[pair_obj->a->instance] == CRW_CAN_DELETE) {
516 pair_obj->initialized = false;
517 }
518 }
519
520 if (pair_obj->b->type == OBJ_WEAPON && pair_obj->signature_b == pair_obj->b->signature) {
521 crw_check_weapon(pair_obj->b->instance, pair_obj->next_check_time);
522
523 if (crw_status[pair_obj->b->instance] == CRW_CAN_DELETE) {
524 pair_obj->initialized = false;
525 }
526 }
527 }
528
529 // for each weapon which could be removed, delete the object
530 int num_deleted = 0;
531 for (int i = 0; i < MAX_WEAPONS; i++ ) {
532 if ( crw_status[i] == CRW_CAN_DELETE ) {
533 Assert( Weapons[i].objnum != -1 );
534 obj_delete( Weapons[i].objnum );
535 num_deleted++;
536 }
537 }
538
539 // stop here because any other weapon could currently be involved in a collision and can cause crashes
540 return num_deleted;
541
542 }
543
set_hit_struct_info(collision_info_struct * hit,mc_info * mc,int submodel_rot_hit)544 void set_hit_struct_info(collision_info_struct *hit, mc_info *mc, int submodel_rot_hit)
545 {
546 hit->edge_hit = mc->edge_hit;
547 hit->hit_pos = mc->hit_point_world;
548 hit->hit_time = mc->hit_dist;
549 hit->submodel_num = mc->hit_submodel;
550
551 hit->submodel_rot_hit = submodel_rot_hit;
552 }
553
554 //Previously, this was done with
555 //memset(&ship_ship_hit_info, -1, sizeof(collision_info_struct));
556 //All those -1s are to replicate that logic
init_collision_info_struct(collision_info_struct * cis)557 void init_collision_info_struct(collision_info_struct *cis)
558 {
559 memset(cis, -1, sizeof(collision_info_struct));
560 cis->is_landing = false;
561 }
562
obj_add_collider(int obj_index)563 void obj_add_collider(int obj_index)
564 {
565 object *objp = &Objects[obj_index];
566
567 #ifdef OBJECT_CHECK
568 CheckObjects[obj_index].type = objp->type;
569 CheckObjects[obj_index].signature = objp->signature;
570 CheckObjects[obj_index].flags = objp->flags - Object::Object_Flags::Not_in_coll;
571 CheckObjects[obj_index].parent_sig = objp->parent_sig;
572 CheckObjects[obj_index].parent_type = objp->parent_type;
573 #endif
574
575 if(!(objp->flags[Object::Object_Flags::Not_in_coll])){
576 return;
577 }
578
579 Collision_sort_list.push_back(obj_index);
580
581 objp->flags.remove(Object::Object_Flags::Not_in_coll);
582 }
583
obj_remove_collider(int obj_index)584 void obj_remove_collider(int obj_index)
585 {
586 #ifdef OBJECT_CHECK
587 CheckObjects[obj_index].flags.set(Object::Object_Flags::Not_in_coll);
588 #endif
589
590 for (size_t i = 0; i < Collision_sort_list.size(); ++i ) {
591 if ( Collision_sort_list[i] == obj_index ) {
592 Collision_sort_list[i] = Collision_sort_list.back();
593 Collision_sort_list.pop_back();
594 break;
595 }
596 }
597
598 Objects[obj_index].flags.set(Object::Object_Flags::Not_in_coll);
599 }
600
obj_reset_colliders()601 void obj_reset_colliders()
602 {
603 Collision_sort_list.clear();
604 Collision_cached_pairs.clear();
605 }
606
obj_collide_retime_cached_pairs()607 void obj_collide_retime_cached_pairs()
608 {
609 for ( auto& pair : Collision_cached_pairs ) {
610 pair.second.next_check_time = timestamp(0);
611 }
612 }
613
614 //local helper functions only used in objcollide.cpp
615 namespace
616 {
617
obj_get_collider_endpoint(int obj_num,int axis,bool min)618 float obj_get_collider_endpoint(int obj_num, int axis, bool min)
619 {
620 if ( Objects[obj_num].type == OBJ_BEAM ) {
621 beam *b = &Beams[Objects[obj_num].instance];
622
623 // use the last start and last shot as endpoints
624 float min_end, max_end;
625 if ( b->last_start.a1d[axis] > b->last_shot.a1d[axis] ) {
626 min_end = b->last_shot.a1d[axis];
627 max_end = b->last_start.a1d[axis];
628 } else {
629 min_end = b->last_start.a1d[axis];
630 max_end = b->last_shot.a1d[axis];
631 }
632
633 if ( min ) {
634 return min_end;
635 } else {
636 return max_end;
637 }
638 } else if ( Objects[obj_num].type == OBJ_WEAPON ) {
639 float min_end, max_end;
640
641 if ( Objects[obj_num].pos.a1d[axis] > Objects[obj_num].last_pos.a1d[axis] ) {
642 min_end = Objects[obj_num].last_pos.a1d[axis];
643 max_end = Objects[obj_num].pos.a1d[axis];
644 } else {
645 min_end = Objects[obj_num].pos.a1d[axis];
646 max_end = Objects[obj_num].last_pos.a1d[axis];
647 }
648
649 if ( min ) {
650 return min_end - Objects[obj_num].radius;
651 } else {
652 return max_end + Objects[obj_num].radius;
653 }
654 } else {
655 vec3d *pos = &Objects[obj_num].pos;
656
657 if ( min ) {
658 return pos->a1d[axis] - Objects[obj_num].radius;
659 } else {
660 return pos->a1d[axis] + Objects[obj_num].radius;
661 }
662 }
663 }
664
obj_quicksort_colliders(SCP_vector<int> * list,int left,int right,int axis)665 void obj_quicksort_colliders(SCP_vector<int> *list, int left, int right, int axis)
666 {
667 Assert( axis >= 0 );
668 Assert( axis <= 2 );
669
670 if ( right > left ) {
671 int pivot_index = left + (right - left) / 2;
672
673 float pivot_value = obj_get_collider_endpoint((*list)[pivot_index], axis, true);
674
675 // swap!
676 int temp = (*list)[pivot_index];
677 (*list)[pivot_index] = (*list)[right];
678 (*list)[right] = temp;
679
680 int store_index = left;
681
682 for (int i = left; i < right; ++i ) {
683 if ( obj_get_collider_endpoint((*list)[i], axis, true) <= pivot_value ) {
684 temp = (*list)[i];
685 (*list)[i] = (*list)[store_index];
686 (*list)[store_index] = temp;
687 store_index++;
688 }
689 }
690
691 temp = (*list)[right];
692 (*list)[right] = (*list)[store_index];
693 (*list)[store_index] = temp;
694
695 obj_quicksort_colliders(list, left, store_index - 1, axis);
696 obj_quicksort_colliders(list, store_index + 1, right, axis);
697 }
698 }
699
obj_collide_pair(object * A,object * B)700 void obj_collide_pair(object *A, object *B)
701 {
702 TRACE_SCOPE(tracing::CollidePair);
703
704 int (*check_collision)( obj_pair *pair ) = nullptr;
705 int swapped = 0;
706
707 if ( A==B ) return; // Don't check collisions with yourself
708
709 if ( !(A->flags[Object::Object_Flags::Collides]) ) return; // This object doesn't collide with anything
710 if ( !(B->flags[Object::Object_Flags::Collides]) ) return; // This object doesn't collide with anything
711
712 if ((A->flags[Object::Object_Flags::Immobile]) && (B->flags[Object::Object_Flags::Immobile])) return; // Two immobile objects will never collide with each other
713
714 // Make sure you're not checking a parent with it's kid or vicy-versy
715 if ( reject_obj_pair_on_parent(A,B) ) {
716 return;
717 }
718
719 Assert( A->type < 127 );
720 Assert( B->type < 127 );
721
722 uint ctype = COLLISION_OF(A->type,B->type);
723 switch( ctype ) {
724 case COLLISION_OF(OBJ_WEAPON,OBJ_SHIP):
725 swapped = 1;
726 check_collision = collide_ship_weapon;
727 break;
728 case COLLISION_OF(OBJ_SHIP, OBJ_WEAPON):
729 check_collision = collide_ship_weapon;
730 break;
731 case COLLISION_OF(OBJ_DEBRIS, OBJ_WEAPON):
732 check_collision = collide_debris_weapon;
733 break;
734 case COLLISION_OF(OBJ_WEAPON, OBJ_DEBRIS):
735 swapped = 1;
736 check_collision = collide_debris_weapon;
737 break;
738 case COLLISION_OF(OBJ_DEBRIS, OBJ_SHIP):
739 check_collision = collide_debris_ship;
740 break;
741 case COLLISION_OF(OBJ_SHIP, OBJ_DEBRIS):
742 check_collision = collide_debris_ship;
743 swapped = 1;
744 break;
745 case COLLISION_OF(OBJ_ASTEROID, OBJ_WEAPON):
746 check_collision = collide_asteroid_weapon;
747 break;
748 case COLLISION_OF(OBJ_WEAPON, OBJ_ASTEROID):
749 swapped = 1;
750 check_collision = collide_asteroid_weapon;
751 break;
752 case COLLISION_OF(OBJ_ASTEROID, OBJ_SHIP):
753 check_collision = collide_asteroid_ship;
754 break;
755 case COLLISION_OF(OBJ_SHIP, OBJ_ASTEROID):
756 check_collision = collide_asteroid_ship;
757 swapped = 1;
758 break;
759 case COLLISION_OF(OBJ_SHIP,OBJ_SHIP):
760 check_collision = collide_ship_ship;
761 break;
762
763 case COLLISION_OF(OBJ_SHIP, OBJ_BEAM):
764 if(beam_collide_early_out(B, A)){
765 return;
766 }
767 swapped = 1;
768 check_collision = beam_collide_ship;
769 break;
770
771 case COLLISION_OF(OBJ_BEAM, OBJ_SHIP):
772 if(beam_collide_early_out(A, B)){
773 return;
774 }
775 check_collision = beam_collide_ship;
776 break;
777
778 case COLLISION_OF(OBJ_ASTEROID, OBJ_BEAM):
779 if(beam_collide_early_out(B, A)) {
780 return;
781 }
782 swapped = 1;
783 check_collision = beam_collide_asteroid;
784 break;
785
786 case COLLISION_OF(OBJ_BEAM, OBJ_ASTEROID):
787 if(beam_collide_early_out(A, B)){
788 return;
789 }
790 check_collision = beam_collide_asteroid;
791 break;
792 case COLLISION_OF(OBJ_DEBRIS, OBJ_BEAM):
793 if(beam_collide_early_out(B, A)) {
794 return;
795 }
796 swapped = 1;
797 check_collision = beam_collide_debris;
798 break;
799 case COLLISION_OF(OBJ_BEAM, OBJ_DEBRIS):
800 if(beam_collide_early_out(A, B)){
801 return;
802 }
803 check_collision = beam_collide_debris;
804 break;
805 case COLLISION_OF(OBJ_WEAPON, OBJ_BEAM):
806 if(beam_collide_early_out(B, A)) {
807 return;
808 }
809 swapped = 1;
810 check_collision = beam_collide_missile;
811 break;
812
813 case COLLISION_OF(OBJ_BEAM, OBJ_WEAPON):
814 if(beam_collide_early_out(A, B)){
815 return;
816 }
817 check_collision = beam_collide_missile;
818 break;
819
820 case COLLISION_OF(OBJ_WEAPON, OBJ_WEAPON): {
821 weapon_info* awip = &Weapon_info[Weapons[A->instance].weapon_info_index];
822 weapon_info* bwip = &Weapon_info[Weapons[B->instance].weapon_info_index];
823
824 if ((awip->weapon_hitpoints > 0) || (bwip->weapon_hitpoints > 0)) {
825 if (bwip->weapon_hitpoints == 0) {
826 check_collision = collide_weapon_weapon;
827 swapped=1;
828 } else {
829 check_collision = collide_weapon_weapon;
830 }
831 }
832
833 break;
834 }
835
836 default:
837 return;
838 }
839
840 if ( !check_collision ) return;
841
842 // Swap them if needed
843 if ( swapped ) {
844 std::swap(A,B);
845 }
846
847 bool valid = false;
848 uint key = (OBJ_INDEX(A) << 12) + OBJ_INDEX(B);
849
850 collider_pair* collision_info = &Collision_cached_pairs[key];
851
852 if ( collision_info->initialized ) {
853 // make sure we're referring to the correct objects in case the original pair was deleted
854 if ( collision_info->signature_a == collision_info->a->signature &&
855 collision_info->signature_b == collision_info->b->signature ) {
856 valid = true;
857 } else {
858 collision_info->a = A;
859 collision_info->b = B;
860 collision_info->signature_a = A->signature;
861 collision_info->signature_b = B->signature;
862 collision_info->next_check_time = timestamp(0);
863 }
864 } else {
865 collision_info->a = A;
866 collision_info->b = B;
867 collision_info->signature_a = A->signature;
868 collision_info->signature_b = B->signature;
869 collision_info->initialized = true;
870 collision_info->next_check_time = timestamp(0);
871 }
872
873 if ( valid ) {
874 // if this signature is valid, make the necessary checks to see if we need to collide check
875 if ( collision_info->next_check_time == -1 ) {
876 return;
877 } else {
878 if ( !timestamp_elapsed(collision_info->next_check_time) ) {
879 return;
880 }
881 }
882 } else {
883 // only check debris:weapon collisions for player
884 if (check_collision == collide_debris_weapon) {
885 // weapon is B
886 if ( !(Weapon_info[Weapons[B->instance].weapon_info_index].wi_flags[Weapon::Info_Flags::Turns]) ) {
887 // check for dumbfire weapon
888 // check if debris is behind laser
889 float vdot;
890 if (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) {
891 vec3d velocity_rel_weapon;
892 vm_vec_sub(&velocity_rel_weapon, &B->phys_info.vel, &A->phys_info.vel);
893 vdot = -vm_vec_dot(&velocity_rel_weapon, &B->orient.vec.fvec);
894 } else {
895 vdot = vm_vec_dot( &A->phys_info.vel, &B->phys_info.vel);
896 }
897 if ( vdot <= 0.0f ) {
898 // They're heading in opposite directions...
899 // check their positions
900 vec3d weapon2other;
901 vm_vec_sub( &weapon2other, &A->pos, &B->pos );
902 float pdot = vm_vec_dot( &B->orient.vec.fvec, &weapon2other );
903 if ( pdot <= -A->radius ) {
904 // The other object is behind the weapon by more than
905 // its radius, so it will never hit...
906 collision_info->next_check_time = -1;
907 return;
908 }
909 }
910
911 // check dist vs. dist moved during weapon lifetime
912 vec3d delta_v;
913 vm_vec_sub(&delta_v, &B->phys_info.vel, &A->phys_info.vel);
914 if (vm_vec_dist_squared(&A->pos, &B->pos) > (vm_vec_mag_squared(&delta_v)*Weapons[B->instance].lifeleft*Weapons[B->instance].lifeleft)) {
915 collision_info->next_check_time = -1;
916 return;
917 }
918
919 // for nonplayer ships, only create collision pair if close enough
920 if ( (B->parent >= 0) && !((Objects[B->parent].signature == B->parent_sig) && (Objects[B->parent].flags[Object::Object_Flags::Player_ship])) && (vm_vec_dist(&B->pos, &A->pos) < (4.0f*A->radius + 200.0f)) ) {
921 collision_info->next_check_time = -1;
922 return;
923 }
924 }
925 }
926
927 // don't check same team laser:ship collisions on small ships if not player
928 if (check_collision == collide_ship_weapon) {
929 // weapon is B
930 if ( (B->parent >= 0)
931 && (Objects[B->parent].signature == B->parent_sig)
932 && !(Objects[B->parent].flags[Object::Object_Flags::Player_ship])
933 && (Ships[Objects[B->parent].instance].team == Ships[A->instance].team)
934 && (Ship_info[Ships[A->instance].ship_info_index].is_small_ship())
935 && (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) ) {
936 collision_info->next_check_time = -1;
937 return;
938 }
939 }
940 }
941
942 obj_pair new_pair;
943
944 new_pair.a = A;
945 new_pair.b = B;
946 new_pair.next_check_time = collision_info->next_check_time;
947
948 if ( check_collision(&new_pair) ) {
949 // don't have to check ever again
950 collision_info->next_check_time = -1;
951 } else {
952 collision_info->next_check_time = new_pair.next_check_time;
953 }
954 }
955
obj_find_overlap_colliders(SCP_vector<int> & overlap_list_out,SCP_vector<int> & list,int axis,bool collide)956 void obj_find_overlap_colliders(SCP_vector<int> &overlap_list_out, SCP_vector<int> &list, int axis, bool collide)
957 {
958 TRACE_SCOPE(tracing::FindOverlapColliders);
959
960 bool first_not_added = true;
961 SCP_vector<int> overlappers;
962
963 for (int in_index : list){
964 bool overlapped = false;
965
966 const float min = obj_get_collider_endpoint(in_index, axis, true);
967
968 for (size_t j = 0; j < overlappers.size(); ) {
969 const float overlap_max = obj_get_collider_endpoint(overlappers[j], axis, false);
970 if ( min <= overlap_max ) {
971 overlapped = true;
972
973 if ( overlappers.size() == 1 && first_not_added ) {
974 first_not_added = false;
975 overlap_list_out.push_back(overlappers[j]);
976 }
977
978 if ( collide ) {
979 obj_collide_pair(&Objects[in_index], &Objects[overlappers[j]]);
980 }
981 } else {
982 overlappers[j] = overlappers.back();
983 overlappers.pop_back();
984 continue;
985 }
986
987 ++j;
988 }
989
990 if ( overlappers.empty() ) {
991 first_not_added = true;
992 }
993
994 if ( overlapped ) {
995 overlap_list_out.push_back(in_index);
996 }
997
998 overlappers.push_back(in_index);
999 }
1000 }
1001 } //anon namespace
1002
1003 // used only in obj_sort_and_collide()
1004 static SCP_vector<int> sort_list_y;
1005 static SCP_vector<int> sort_list_z;
1006
obj_sort_and_collide(SCP_vector<int> * Collision_list)1007 void obj_sort_and_collide(SCP_vector<int>* Collision_list)
1008 {
1009 if (Cmdline_dis_collisions)
1010 return;
1011
1012 if ( !(Game_detail_flags & DETAIL_FLAG_COLLISION) )
1013 return;
1014
1015 // the main use case is to go through the main Collision detection list, so use that if
1016 // nothing is defined.
1017 if (Collision_list == nullptr) {
1018 Collision_list = &Collision_sort_list;
1019 }
1020
1021 sort_list_y.clear();
1022 {
1023 TRACE_SCOPE(tracing::SortColliders);
1024 obj_quicksort_colliders(Collision_list, 0, (int)(Collision_list->size() - 1), 0);
1025 }
1026 obj_find_overlap_colliders(sort_list_y, *Collision_list, 0, false);
1027
1028 sort_list_z.clear();
1029 {
1030 TRACE_SCOPE(tracing::SortColliders);
1031 obj_quicksort_colliders(&sort_list_y, 0, (int)(sort_list_y.size() - 1), 1);
1032 }
1033 obj_find_overlap_colliders(sort_list_z, sort_list_y, 1, false);
1034
1035 sort_list_y.clear();
1036 {
1037 TRACE_SCOPE(tracing::SortColliders);
1038 obj_quicksort_colliders(&sort_list_z, 0, (int)(sort_list_z.size() - 1), 2);
1039 }
1040 obj_find_overlap_colliders(sort_list_y, sort_list_z, 2, true);
1041 }
1042