# point within ellipse arc question

This topic is 3662 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am working on a older star trek game engine remake, with existing game data files. A particular problem happened with how the game dealt with ship "phasers", it specifies a phaser object's matrix, and a ellipse (width & height), arc part of the ellipse is then used, which usually goes along the graphical model's phaser curve. The ellipse can be ofcourse turned into a straight line and rotated by the matrix to fit most complex scenarios. Here's one such phaser, red indicates horisontal start & stop angles, blue specifies vertical angles: Top angles (start & stop): Side angles (start & stop): This is kinda how it looks, but the shape is NOT a frustum! My problem is, how do i know when a point is within these angles, and therefore the "phaser" beam can fire at it?

##### Share on other sites
I'm not quite sure I understand the constraining shape, but I assume it's a cone of some sort. In general for cone type things you can simply iterate through all the cone's faces and test against each face (point on side of plane). If your cone is generated by a curve (like an ellipse or circle) you can also just project into a plane and then you have a 2d problem of point inside curve (ellipse). You just have to be careful that your plane is normal to the generating curve. Think of it like putting a curtain behind the point, shining a light on it from your phaser, and then asking if the point is inside the light.

##### Share on other sites
It's not a cone.

Someone on irc made another picture of what i want to do here:

##### Share on other sites
Ok, I think I see it. Does the vertical angle constraint start at the ellipse or at the origin? I assume at the ellipse.

The top half of the surface (above) and the same thing mirrored vertically would be the bottom - if I understand you correctly.

I still say project, project, project! Break it into two problems.

First the obvious constraint shown so well in your view of the top of the ship. The ellipse is sitting in a plane. If you project your point into that plane, it's fairly straightforward to tell whether it's within the start and stop angle. There's some ambiguity here about angles, since you have an ellipse and not a circle. If you want to throw out the center of the ellipse, you'd do that here.

Now for the other constraint which is a bit more challenging. You want a plane that contains the point in question, is normal to the ellipse plane, and contains some point, as yet to be determined, on the ellipse (the tricky part). For your cutting plane to make sense, it has to be normal to the ellipse. If it is, then the intersection of the two gives a simple cone in the plane. Then just project to the plane and compare with the cone.

The big question remaining then is how to find the point on the ellipse closest to the point in question. Uhh. I'm not quite sure, but I'll bet we can figure it out or look it up.

For circles instead of ellipses, this is all much easier. I kind of wonder if you couldn't get roughly the same results by assuming a circle.

I hope I understood you correctly. I enjoy these geometry problems. =)

##### Share on other sites
The angle checks are done all from ellipse origin, not a point of ellipse, the ellipse itself is used just for graphical effects and emmiter point for raycasting if anything got hit.

I have now some code that transforms the points from global into local space for the beam weapons, now doing the top-down check is pretty straightforward (by calculating the angle), however vertical angle is more complex, because it involves the first angle before any check can be done using a dot product (if i am properly understanding what i was told in gamedev irc channel yesterday), so i would have to additionally unrotate the point for second check before i compare the angles on XZ axis? am i thinking this right? i will try to make this code work when i get home from work.

##### Share on other sites
Alright, so you have the easy case. This case doesn't cover a long thin phaser though. Er, I guess you could hack it by non-uniform scaling.

Anyway, let O be the origin of the phaser, P be the point in question and X,Y,Z be the obvious local unit vectors on the phaser (where X is forward, Y is to the side and Z is up). We first want to be working at the origin, so let's just subtract O from P and rename P-O to P. =P If you wanted, you could work totally in object local space. Hit everything with the inverse of the phaser object's transform and X,Y, and Z would become the standard unit vectors.

For the easy angle constraint, we just want to project P into the X,Y plane. That puts us in 2d, and the coordinate for that point is just (P*X,P*Y) where * is the dot product. Now you can do your first angle comparison.

Next, the harder vertical constraint. We'll need the projection of P into the X,Y plane. But we just calculated that, P'=normalized(P*X,P*Y,0) - needs to be normalized though since we want a unit vector. The P',Z plane is now exactly what we want. Project P into that plane to get the 2d coordinates, (P'*P,Z*P). And on that point you can do your second angle comparison.

Hope that made sense. You can be fancier with matrices, but I think the more explicit vector notation makes it clearer what's going on. *crosses fingers and hopes he didn't make any mistakes*

##### Share on other sites
I solved this, the PT point is already translated into ship local space before processing, this is the code that checks for valid area:

<src>
function TBeamWeaponHardpoint.LocalShipPointInRange(pt: Tvector3f): boolean;
var
mt: TMatrix;
checkTD, CT2: TVector3f;
Zangle: single;
Vangle: single;

function inbetween(val, start, stop: single): boolean;
begin
Result := (val > start) and (val < stop);
end;

begin

move(matrix, mt, sizeof(mt));
InvertMatrix(mt);
localpt := VectorTransform(pt, mt);

checkTD := localpt;
checkTD := Normalize(checkTD);

Zangle := arctan2(checkTD[1], checkTD[0]);
Result := inbetween(Zangle, ArcWidthAngles[0], ArcWidthAngles[1]);

if Result = False then

checkTD := VectorRotateAroundZ(checkTD, Zangle);
Vangle := arctan2(checkTD[2], checkTD[0]);
Result := inbetween(Vangle, ArcHeightAngles[0], ArcHeightAngles[1]);
end;
</src>

I did as you said with first check, but for second i just rotated the target point along the Z vector by the "heading" difference to get it rotated so it is only a 2D plane left and i do the second check.

So now i need to add a closest point on ellipse check to have it working as the original game did :)

The result, sorry for crappy low-res vid:

To to anyone interested in the project, this is a opensource project i started here: https://sourceforge.net/projects/st-sc

##### Share on other sites

http://www.geometrictools.com/Documentation/DistancePointToEllipse2.pdf

##### Share on other sites
Thanks, it is all working now, i'll probably post the result in IOTD forum :)

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633669
• Total Posts
3013257
×