Circle vs pie segment collision detection

[paul_nicholls]

Hi all,
I have added to The Probe a new element, a Sentry object (see figure 1). This object sweeps a beam (shaped like a pie segment) around itself (see figure 2), and I now want to add collision detection so that I know when the beam is touching the player.

Figure 1
111

Figure 2
112

I know the beam center point, the radius, and the width (angle).

I know the player center point, the radius.

Any ideas as to how I can quickly return true if the beam is over the circle representing the player?

cheers,
Paul

[WILL]

Well for a circle, if you know the centre, just use a simple distance calculation to determine if it's inside it. If you need only a 'slice' (or beam as you mentioned) to be detected, get the two angles of the line segments from centre and determine if it's within those.

I don't have my AdvancedMath.pas unit handy or I'd throw up the function for you.

For your solution you'd need to compare distance then determine the angle of the object to your sentry object's beam emitter. Once you have all of that information, just use the angles of your beam arcs and the rest is comparison. Just be 0/360 conscious when doing your angle range checks.

[paul_nicholls]

I am already comparing the distance between the circle and the beam, I just wasn't sure how to compare a circle against the two angles...

hmm...I might try looking at dot products or similar + the line normal and see if I can test against the 2 lines and circle that way :)

cheers,
Paul

[Ñuño Martínez]

An idea: transform the object/player coordinates to polar (you know: <angle, distance>) relative to the origin of your beam. In pseudocode:


IF vector_length (object.position - beam.position) < beam.radius THEN
new_object.position := object.position - beam.position;
polar_object := polar (new_object.position);
IF polar_object.angle BETWEEN beam.angle1 AND beam.angle2 THEN
object.hit ();
END IF;
END IF;

[User137]

With functions in my lib:

// Angle between 2 vectors, given in radians
function Angle(src,dest: single): single;
begin
result:=src-dest;
while result<-PI do result:=result+PI*2;
while result>PI do result:=result-PI*2;
end;

// By pythagoras a^2+b^2=c^2 you don't need Sqrt() to determine the equality
function PointInCircle(const p,circle: TVector2f; const radius: single): boolean;
var x,y: single;
begin
x:=circle.x-p.x; y:=circle.y-p.y;
PointInCircle:=(x*x+y*y)<(radius*radius);
end;
And knowing the angle_delta that is half of pie's slice angle, we can count if point is between them:


if PointInCircle(beam.position, player.position, radius) then
if abs(Angle(beam.angle, angle_from_beam_to_player)) < angle_delta then begin
Collide;
end;

You can also use this for the angle from beam to player:

function Angle(const px1,py1,px2,py2: single): single;
begin
result:=arctan2(py2-py1,px2-px1);
if result<0 then result:=result+PI*2;
end;

[paul_nicholls]

@?ëu?±o Mart??nez and User137: thanks guys, but you seem to have overlooked the fact that I want to check if a circle, not a point is between the 2 angle :)

cheers,
Paul

[Dan]

indeed it would have been a lot easier if it was a point vs pie. but anyway, I just had a quick look into the problem and here's what I came up with:


TCircle = record
public
c: TG2Vec2;
r: Single;
end;

TPie = record
public
c: TG2Vec2;
r: Single;
AngStart: Single;
AngEnd: Single;
end;
...
function CircleVsPieIntersect(const c: TCircle; const p: TPie): Boolean;
var v1, v2, n1, n2, n3, a1, a2: TG2Vec2;
var d1, d2, l: Single;
begin
l := (c.c - p.c).Len;
if l > c.r + p.r then
begin
Result := False;
Exit;
end;
G2SinCos(p.AngStart, v1.y, v1.x);
G2SinCos(p.AngEnd, v2.y, v2.x);
n3 := -(v1 + v2);
if (n3.Dot(c.c) > n3.Dot(p.c))
and (l > c.r) then
begin
Result := False;
Exit;
end;
n1 := v1.Perp; if n1.Dot(v1 - v2) < 0 then n1 := -n1;
n2 := v2.Perp; if n2.Dot(v2 - v1) < 0 then n2 := -n2;
d1 := n1.Dot(p.c) + c.r;
d2 := n2.Dot(p.c) + c.r;
if (n1.Dot(c.c) > d1)
or (n2.Dot(c.c) > d2) then
begin
Result := False;
Exit;
end;
a1 := p.c + v1 * p.r;
a2 := p.c + v2 * p.r;
if (
(n1.Dot(c.c) > n1.Dot(p.c))
and (v1.Dot(c.c) > v1.Dot(a1))
and ((c.c - a1).Len > c.r)
)
or (
(n2.Dot(c.c) > n2.Dot(p.c))
and (v2.Dot(c.c) > v2.Dot(a2))
and ((c.c - a2).Len > c.r)
) then
begin
Result := False;
Exit;
end;
Result := True;
end;


this is not a best solution, just my solution :)
One limitation though, the algorithm will consider the pie to be the lesser part of the circle.
for example if the angle of your pie is > 180 then the algorithm will reverse the pie and use its smaller part.
so basically if you use a pie with an angle < 180, the algorithm will work.
There are a few methods from my game engine, so if you have any trouble understanding them - let me know.

[paul_nicholls]

Nice! Thanks Dan...I will modify it and see if it works for me :)

EDIT hmm...is TG2Vec2 a class or a record with methods?

cheers
Paul

[Dan]

it's a record:


TG2Vec2 = record
strict private
function GetArr(const Index: Integer): Single; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
procedure SetArr(const Index: Integer; const Value: Single); {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
public
x, y: Single;
property Arr[const Index: Integer]: Single read GetArr write SetArr; default;
class operator Negative(const v: TG2Vec2): TG2Vec2;
class operator Explicit(const v: TG2Vec2): TG2Vec2Ref;
class operator Explicit(const v: TG2Vec2Ref): TG2Vec2;
class operator Explicit(const v: TPoint): TG2Vec2;
class operator Implicit(const v: TG2Vec2): TG2Vec2Ref;
class operator Implicit(const v: TG2Vec2Ref): TG2Vec2;
class operator Implicit(const v: TPoint): TG2Vec2;
class operator Equal(const v1, v2: TG2Vec2): Boolean;
class operator NotEqual(const v1, v2: TG2Vec2): Boolean;
class operator Add(const v1, v2: TG2Vec2): TG2Vec2;
class operator Add(const v: TG2Vec2; const s: Single): TG2Vec2;
class operator Subtract(const v1, v2: TG2Vec2): TG2Vec2;
class operator Subtract(const v: TG2Vec2; const s: Single): TG2Vec2;
class operator Multiply(const v1, v2: TG2Vec2): Single;
class operator Multiply(const v: TG2Vec2; const s: Single): TG2Vec2;
class operator Multiply(const v: TG2Vec2; const m: TG2Mat): TG2Vec2;
class operator Multiply(const v: TG2Vec2; const m: TG2Mat2): TG2Vec2;
class operator Divide(const v: TG2Vec2; const s: Single): TG2Vec2;
procedure SetValue(const _X, _Y: Single); {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
procedure Normalize; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Normalized: TG2Vec2; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Len: Single; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function LenSq: Single; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Dot(const v: TG2Vec2): Single; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Cross(const v: TG2Vec2): Single; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Angle(const v: TG2Vec2): Single; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Perp: TG2Vec2; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Reflect(const n: TG2Vec2): TG2Vec2; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
function Rotate(const Angle: Single): TG2Vec2; {$IFDEF G2_USE_INLINE} inline; {$ENDIF}
end;


if you want I could just attach the whole math unit here.

[paul_nicholls]

Thanks :)

That would probably be easier ;)

cheers,
Paul

[Dan]

ok here it is

[paul_nicholls]

ok here it is

Thanks mate, I will post back and let you know if I got it working :)

Thanks again for your time :)

EDIT: what about the file "Gen2.inc" that G2Math.pas uses?

cheers,
Paul

[Dan]

You can just cut that out, you mostly just want the TG2Vec2 record and the methods that go with it, Gen2.inc controls some of the compiler directives which you don't need.

EDIT: I took the time and put all the stuff that you may need here ;)


TVec2 = record
public
x, y: Single;
class operator Negative(const v: TVec2): TVec2;
class operator Add(const v1, v2: TVec2): TVec2;
class operator Subtract(const v1, v2: TVec2): TVec2;
class operator Multiply(const v: TVec2; const s: Single): TVec2;
procedure SetValue(const _X, _Y: Single);
function Len: Single;
function Dot(const v: TVec2): Single;
function Perp: TVec2;
end;

TCircle = record
public
c: TVec2;
r: Single;
end;

TPie = record
public
c: TVec2;
r: Single;
AngStart: Single;
AngEnd: Single;
end;

...

class operator TVec2.Negative(const v: TVec2): TVec2;
begin
Result.x := -v.x;
Result.y := -v.y;
end;

class operator TVec2.Add(const v1, v2: TVec2): TVec2;
begin
Result.x := v1.x + v2.x;
Result.y := v1.y + v2.y;
end;

class operator TVec2.Subtract(const v1, v2: TVec2): TVec2;
begin
Result.x := v1.x - v2.x;
Result.y := v1.y - v2.y;
end;

class operator TVec2.Multiply(const v: TVec2; const s: Single): TVec2;
begin
Result.x := v.x * s;
Result.y := v.y * s;
end;

procedure TVec2.SetValue(const _X, _Y: Single);
begin
x := _X; y := _Y;
end;

function TVec2.Len: Single;
begin
Result := Sqrt(Sqr(x) + Sqr(y));
end;

function TVec2.Dot(const v: TVec2): Single;
begin
Result := x * v.x + y * v.y;
end;

function TVec2.Perp: TVec2;
begin
Result.SetValue(-y, x);
end;

procedure SinCos(const Angle: Single; var s, c: Single);
asm
fld Angle
fsincos
fstp [edx]
fstp [eax]
fwait
end;

function CircleVsPieIntersect(const c: TCircle; const p: TPie): Boolean;
var v1, v2, n1, n2, n3, a1, a2: TVec2;
var d1, d2, l: Single;
begin
l := (c.c - p.c).Len;
if l > c.r + p.r then
begin
Result := False;
Exit;
end;
SinCos(p.AngStart, v1.y, v1.x);
SinCos(p.AngEnd, v2.y, v2.x);
n3 := -(v1 + v2);
if (n3.Dot(c.c) > n3.Dot(p.c))
and (l > c.r) then
begin
Result := False;
Exit;
end;
n1 := v1.Perp; if n1.Dot(v1 - v2) < 0 then n1 := -n1;
n2 := v2.Perp; if n2.Dot(v2 - v1) < 0 then n2 := -n2;
d1 := n1.Dot(p.c) + c.r;
d2 := n2.Dot(p.c) + c.r;
if (n1.Dot(c.c) > d1)
or (n2.Dot(c.c) > d2) then
begin
Result := False;
Exit;
end;
a1 := p.c + v1 * p.r;
a2 := p.c + v2 * p.r;
if (
(n1.Dot(c.c) > n1.Dot(p.c))
and (v1.Dot(c.c) > v1.Dot(a1))
and ((c.c - a1).Len > c.r)
)
or (
(n2.Dot(c.c) > n2.Dot(p.c))
and (v2.Dot(c.c) > v2.Dot(a2))
and ((c.c - a2).Len > c.r)
) then
begin
Result := False;
Exit;
end;
Result := True;
end;

[paul_nicholls]

You can just cut that out, you mostly just want the TG2Vec2 record and the methods that go with it, Gen2.inc controls some of the compiler directives which you don't need.

Ah ok, no worries :)

cheers,
Paul

[paul_nicholls]

hmm...the code seems to be returning true for me most of the time, so I get flickering energy discharges at the target as it thinks the circle and pie are intersecting lots...

I am setting up the circle and pie like this:



BeamHasHitPlayer := False;

if Assigned(FPlayer) then
begin
Circle.c := G2Vec2(FPlayer.x,FPlayer.y);
Circle.r := FPlayer.Width * 0.4;

Pie.c := G2Vec2(aSentry.x,aSentry.y);
Pie.r := aSentry.BeamRange;
Pie.AngStart := aSentry.Angle - aSentry.BeamWidth/2;
Pie.AngEnd := aSentry.Angle + aSentry.BeamWidth/2;

BeamHasHitPlayer := CircleVsPieIntersect(Circle,Pie);
end;

Any ideas?

If it helps, the beam width is 50 degrees wide, and the screen coordinate system being used is this (if it makes a difference?):


0,0
+---------------------- +X
|
|
|
|
|
|
|

+Y

cheers,
Paul

[Dan]

The function assumes that the angles are in radians so you might need to multiply your degree angles by (Pi / 180).
EDIT: Here's my test app.

[paul_nicholls]

The function assumes that the angles are in radians so you might need to multiply your degree angles by (Pi / 180)

<Drumroll...> that was it...it is now working, sweet!! thanks mate :)

<gives a beer>

Now that it is working, I might convert the function to use my plain, vanilla records so lesser versions of Delphi can compile the code too ;)

cheers,
Paul

[Dan]

it was an interesting problem to solve.

[paul_nicholls]

Here is a picture of the Sentry zapping the user character :)

http://img530.imageshack.us/img530/9752/screenshothb.th.png (http://img530.imageshack.us/i/screenshothb.png/)

Thanks again :)

cheers,
Paul

[User137]

@?ëu?±o Mart??nez and User137: thanks guys, but you seem to have overlooked the fact that I want to check if a circle, not a point is between the 2 angle :)
Well..

if PointInCircle(beam.position, player.position, radius) then
would change into

if PointInCircle(beam.position, player.position, radius+playerRadius) then
That leaves the "triangle check" remaining to be fixed. It could really be a circle vs triangle check.

[Ñuño Martínez]

@?ëu?±o Mart??nez and User137: thanks guys, but you seem to have overlooked the fact that I want to check if a circle, not a point is between the 2 angle :)
Details... BTW that was teh first idea I had, and I'm sure it made you think, don't you? ;)