Module: Moon::SAT::Helper

Included in:
Moon::SAT
Defined in:
lib/moon/packages/physics/sat.rb

Constant Summary collapse

T_VECTORS =
Array.new(10) { Moon::Vector2.zero }
T_ARRAYS =
Array.new(5)  { [] }
T_RESPONSE =
Response.new
UNIT_SQUARE =
Box.new(Moon::Vector2.zero, 1, 1).to_polygon
LEFT_VORNOI_REGION =
-1
MIDDLE_VORNOI_REGION =
0
RIGHT_VORNOI_REGION =
1

Instance Method Summary collapse

Instance Method Details

#flatten_points_on(points, normal, result) ⇒ Object


185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
# File 'lib/moon/packages/physics/sat.rb', line 185

def flatten_points_on(points, normal, result)
  min = -0xFFFF
  max = 0xFFFF

  points.each_with_index do |p, i|
    dot = p.dot(normal)
    if dot < min
      min = dot
    end
    if dot > max
      max = dot
    end
  end

  result[0] = min
  result[1] = max
end

#is_separating_axis?(a_pos, b_pos, a_points, b_points, axis, response) ⇒ Boolean

Check whether two convex polygons are separated by the specified axis (must be a unit vector).


217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
# File 'lib/moon/packages/physics/sat.rb', line 217

def is_separating_axis?(a_pos, b_pos, a_points, b_points, axis, response)
  range_a = T_ARRAYS.pop
  range_b = T_ARRAYS.pop  # The magnitude of the offset between the two polygons
  #offset_v = T_VECTORS.pop.set(b_pos).sub(a_pos)

  offset_v = T_VECTORS.pop.set(b_pos) - a_pos
  projected_offset = offset_v.dot(axis)  # Project the polygons onto the axis.

  flatten_points_on(a_points, axis, range_a)
  flatten_points_on(b_points, axis, range_b)  # Move B's range to its position relative to A.

  range_b[0] += projected_offset
  range_b[1] += projected_offset  # Check if there is a gap. If there is, this is a separating axis and we can stop

  if range_a[0] > range_b[1] || range_b[0] > range_a[1]
    T_VECTORS.push(offset_v)
    T_ARRAYS.push(range_a)
    T_ARRAYS.push(range_b)
    return true
  end

  # This is not a separating axis. If we're calculating a response, calculate the overlap.
  if response
    overlap = 0    # A starts further left than B

    if range_a[0] < range_b[0]
      response.a_in_b = false      # A ends before B does. We have to pull A out of B

      if range_a[1] < range_b[1]
        overlap = range_a[1] - range_b[0]
        response.b_in_a = false      # B is fully inside A.  Pick the shortest way out.

      else
        option1 = range_a[1] - range_b[0]
        option2 = range_b[1] - range_a[0]
        overlap = option1 < option2 ? option1 : -option2
      end    # B starts further left than A

    else
      response.b_in_a = false      # B ends before A ends. We have to push A out of B

      if range_a[1] > range_b[1]
        overlap = range_a[0] - range_b[1]
        response.a_in_b = false      # A is fully inside B.  Pick the shortest way out.

      else
        option1 = range_a[1] - range_b[0]
        option2 = range_b[1] - range_a[0]
        overlap = option1 < option2 ? option1 : -option2
      end
    end    # If this is the smallest amount of overlap we've seen so far, set it as the minimum overlap.

    abs_overlap = overlap.abs
    if abs_overlap < response.overlap
      response.overlap = abs_overlap
      response.overlap_n.set(axis)
      if overlap < 0
        response.overlap_n.reverse
      end
    end
  end

  T_VECTORS.push(offset_v)
  T_ARRAYS.push(range_a)
  T_ARRAYS.push(range_b)

  false
end

#point_in_circle(p, c) ⇒ Boolean

Check if a point is inside a circle.


325
326
327
328
329
330
331
332
# File 'lib/moon/packages/physics/sat.rb', line 325

def point_in_circle(p, c)
  difference_v = T_VECTORS.pop.set(p) - c.position
  radius_sq = c.r * c.r
  distance_sq = difference_v.lengthsq
  T_VECTORS.push(difference_v)  # If the distance between is smaller than the radius then the point is inside the circle.

  distance_sq <= radius_sq
end

#point_in_polygon(p, poly) ⇒ Boolean

Check if a point is inside a convex polygon.


340
341
342
343
344
345
346
# File 'lib/moon/packages/physics/sat.rb', line 340

def point_in_polygon(p, poly)
  UNIT_SQUARE.position.set(p)
  T_RESPONSE.clear
  result = test_polygon_polygon(UNIT_SQUARE, poly, T_RESPONSE)
  result = T_RESPONSE.a_in_b if result
  result
end

#test_circle_circle(a, b, response) ⇒ Boolean

Check if two circles collide.


355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
# File 'lib/moon/packages/physics/sat.rb', line 355

def test_circle_circle(a, b, response)
  # Check if the distance between the centers of the two
  # circles is greater than their combined radius.
  difference_v = T_VECTORS.pop.set(b.position) - a.position
  total_radius = a.r + b.r
  total_radius_sq = total_radius * total_radius
  distance_sq = difference_v.lengthsq  # If the distance is bigger than the combined radius, they don't intersect.

  if distance_sq > total_radius_sq
    T_VECTORS.push(difference_v)
    return false
  end  # They intersect.  If we're calculating a response, calculate the overlap.

  if response
    dist = Math.sqrt(distance_sq)
    response.a = a
    response.b = b
    response.overlap = total_radius - dist
    response.overlap_n = difference_v.normalize
    response.overlap_v = difference_v * response.overlap
    response.a_in_b = a.r <= b.r && dist <= b.r - a.r
    response.b_in_a = b.r <= a.r && dist <= a.r - b.r
  end
  T_VECTORS.push(difference_v)
  return true
end

#test_circle_polygon(circle, polygon, response) ⇒ boolean

Check if a circle and a polygon collide.

*NOTE:* This is slightly less efficient than polygonCircle as it just runs polygonCircle and reverses everything at the end.


528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
# File 'lib/moon/packages/physics/sat.rb', line 528

def test_circle_polygon(circle, polygon, response)
  # Test the polygon against the circle.
  result = test_polygon_circle(polygon, circle, response)
  if result && response    # Swap A and B in the response.

    a = response.a
    a_in_b = response.a_in_b
    response.overlap_n = -response.overlap_n
    response.overlap_v = -response.overlap_v
    response.a = response.b
    response.b = a
    response.a_in_b = response.b_in_a
    response.b_in_a = a_in_b
  end
  result
end

#test_polygon_circle(polygon, circle, response) ⇒ boolean

Check if a polygon and a circle collide.


389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
# File 'lib/moon/packages/physics/sat.rb', line 389

def test_polygon_circle(polygon, circle, response)
  # Get the position of the circle relative to the polygon.
  circle_pos = T_VECTORS.pop.set(circle.position - polygon.position)
  radius = circle.r
  radius2 = radius * radius
  points = polygon.calc_points
  len = points.size
  edge = T_VECTORS.pop
  point = T_VECTORS.pop

  # For each edge in the polygon:
  points.size.times do |i|
    nxt = i == len - 1 ? 0 : i + 1
    prev = i == 0 ? len - 1 : i - 1
    overlap = 0
    overlap_n = nil

    # Get the edge.
    edge.set(polygon.edges[i])    # Calculate the center of the circle relative to the starting point of the edge.

    point.set(circle_pos - points[i])

    # If the distance between the center of the circle and the point
    # is bigger than the radius, the polygon is definitely not fully in
    # the circle.
    if response && point.lengthsq > radius2
      response.a_in_b = false
    end

    # Calculate which Vornoi region the center of the circle is in.
    region = vornoi_region(edge, point)    # If it's the left region:

    if region == LEFT_VORNOI_REGION      # We need to make sure we're in the RIGHT_VORNOI_REGION of the previous edge.

      edge.set(polygon.edges[prev])      # Calculate the center of the circle relative the starting point of the previous edge

      point2 = T_VECTORS.pop.set(circle_pos - points[prev])
      region = vornoi_region(edge, point2)
      if region == RIGHT_VORNOI_REGION        # It's in the region we want.  Check if the circle intersects the point.

        dist = point.length
        if dist > radius          # No intersection

          T_VECTORS.push(circle_pos)
          T_VECTORS.push(edge)
          T_VECTORS.push(point)
          T_VECTORS.push(point2)
          return false
        elsif response          # It intersects, calculate the overlap.

          response.b_in_a = false
          overlap_n = point.normalize
          overlap = radius - dist
        end
      end
      T_VECTORS.push(point2)    # If it's the right region:

    elsif region == RIGHT_VORNOI_REGION      # We need to make sure we're in the left region on the next edge

      edge.set(polygon.edges[nxt])      # Calculate the center of the circle relative to the starting point of the next edge.

      point.set(circle_pos - points[nxt])
      region = vornoi_region(edge, point)
      if region == LEFT_VORNOI_REGION        # It's in the region we want.  Check if the circle intersects the point.

        dist = point.length
        if dist > radius          # No intersection

          T_VECTORS.push(circle_pos)
          T_VECTORS.push(edge)
          T_VECTORS.push(point)
          return false
        elsif response          # It intersects, calculate the overlap.

          response.b_in_a = false
          overlap_n = point.normalize
          overlap = radius - dist
        end
      end    # Otherwise, it's the middle region:

    else
      # Need to check if the circle is intersecting the edge,
      # Change the edge into its "edge normal".
      normal = edge.perp.normalize      # Find the perpendicular distance between the center of the
      # circle and the edge.

      dist = point.dot(normal)
      dist_abs = Math.abs(dist)      # If the circle is on the outside of the edge, there is no intersection.

      if dist > 0 && dist_abs > radius        # No intersection

        T_VECTORS.push(circle_pos)
        T_VECTORS.push(normal)
        T_VECTORS.push(point)
        return false
      elsif response        # It intersects, calculate the overlap.

        overlap_n = normal
        overlap = radius - dist        # If the center of the circle is on the outside of the edge, or part of the
        # circle is on the outside, the circle is not fully inside the polygon.

        if dist >= 0 || overlap < 2 * radius
          response.b_in_a = false
        end
      end
    end

    # If this is the smallest overlap we've seen, keep it.
    # (overlap_n may be nil if the circle was in the wrong Vornoi region).
    if overlap_n && response && overlap.abs < response.overlap.abs
      response.overlap = overlap
      response.overlap_n.set(overlap_n)
    end
  end

  # Calculate the final overlap vector - based on the smallest overlap.
  if response
    response.a = polygon
    response.b = circle
    response.overlap_v = response.overlap_n * response.overlap
  end

  T_VECTORS.push(circle_pos)
  T_VECTORS.push(edge)
  T_VECTORS.push(point)

  true
end

#test_polygon_polygon(a, b, response) ⇒ boolean

Checks whether polygons collide.


552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
# File 'lib/moon/packages/physics/sat.rb', line 552

def test_polygon_polygon(a, b, response)
  a_points = a.calc_points
  b_points = b.calc_points  # If any of the edge normals of A is a separating axis, no intersection.

  a.normals.each_with_index do |normal, i|
    if is_separating_axis?(a.position, b.position, a_points, b_points, normal, response)
      return false
    end
  end  # If any of the edge normals of B is a separating axis, no intersection.

  b.normals.each_with_index do |normal, i|
    if is_separating_axis?(a.position, b.position, a_points, b_points, normal, response)
      return false
    end
  end  # Since none of the edge normals of A or B are a separating axis, there is an intersection
  # and we've already calculated the smallest overlap (in is_separating_axis?).  Calculate the
  # final overlap vector.

  if response
    response.a = a
    response.b = b
    response.overlap_v.set(response.overlap_n * response.overlap)
  end
  return true
end

#vornoi_region(line, point) ⇒ Moon::Numeric

Calculates which Vornoi region a point is on a line segment. It is assumed that both the line and the point are relative to `(0,0)`

       |       (0)      |
(-1)  [S]--------------[E]  (1)
       |       (0)      |

303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
# File 'lib/moon/packages/physics/sat.rb', line 303

def vornoi_region(line, point)
  lengthsq = line.lengthsq
  dp = point.dot(line)  # If the point is beyond the start of the line, it is in the
  # left vornoi region.

  if dp < 0
    LEFT_VORNOI_REGION  # If the point is beyond the end of the line, it is in the
  # right vornoi region.

  elsif dp > lengthsq
    RIGHT_VORNOI_REGION  # Otherwise, it's in the middle one.

  else
    MIDDLE_VORNOI_REGION
  end
end