Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (803)
Games in Android Showcase (237)
games submitted by our members
Games in WIP (867)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Case Studies  (Read 12533 times)
0 Members and 1 Guest are viewing this topic.
Offline Roquen

JGO Kernel


Medals: 518



« Posted 2015-08-21 20:28:13 »


In current version of JOML, class Vector3f
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
    public float angleCos(Vector3f v) {
        double length1 = Math.sqrt(x * x + y * y + z * z);
        double length2 = Math.sqrt(v.x * v.x + v.y * v.y + v.z * v.z);
        double dot = x * v.x + y * v.y + z * v.z;
        return (float) (dot / (length1 * length2));
    }

   public float angle(Vector3f v) {
        float cos = angleCos(v);
        // This is because sometimes cos goes above 1 or below -1 because of lost precision
        cos = Math.min(cos, 1);
        cos = Math.max(cos, -1);
        return (float) Math.acos(cos);
    }


And Vector4f looks the same as the 3D (just extended).  The problem is 2D regardless of the number of dimensions, so you want to try to work it as a 2D problem.  The version is slower and has more error than is needed.

This is the exact sub-problem is the starting point of formulating slerp and the analysis of quaternion lerp.  The only difference between 2D problems in 2D vs. more than 2 is you have to find the plane. (and put it back in place if needed)
Offline theagentd
« Reply #1 - Posted 2015-08-21 20:55:31 »

You forgot your point.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #2 - Posted 2015-08-21 21:02:40 »

 This solution is lost in the equation.  I'm asking someone to reason about the meaning which is geometric.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen

JGO Kernel


Medals: 518



« Reply #3 - Posted 2015-08-21 21:21:03 »

Likewise for the divide and conquer nlerps.  2d and yet they are manipulating 4d values.  Also bisected an angle is reducible.  Say think a PBR half vector.
Offline CommanderKeith
« Reply #4 - Posted 2015-08-22 00:56:28 »

I never knew about this vector-replacement for finding the cosine of an angle. Great stuff. I couldn't find a version for Math.sin on google which is a pity.

I think the additional optimisation that @Roquen is suggesting is that the two square roots can be replaced by one.
Since sqrt(x)*sqrt(y) = sqrt(x*y)

Old:
1  
2  
3  
4  
5  
6  
    public float angleCos(Vector3f v) {
        double length1 = Math.sqrt(x * x + y * y + z * z);
        double length2 = Math.sqrt(v.x * v.x + v.y * v.y + v.z * v.z);
        double dot = x * v.x + y * v.y + z * v.z;
        return (float) (dot / (length1 * length2));
    }

New:
1  
2  
3  
4  
5  
6  
    public float angleCos(Vector3f v) {
        double lengthSq1 = x * x + y * y + z * z;
        double lengthSq2 = v.x * v.x + v.y * v.y + v.z * v.z;
        double dot = x * v.x + y * v.y + z * v.z;
        return (float) (dot / Math.sqrt(lengthSq1 * lengthSq2));
    }



Offline Husk

Senior Devvie


Medals: 20
Exp: 3 years


Want to learn everything.


« Reply #5 - Posted 2015-08-22 01:58:09 »

Useful tip, CommanderKeith, I'll certainly be using that in the future, thanks.

Would it be taking it too literally to be only using X, and Y, values of any size vector, in an attempt to make the problem 2D?

Edit: Removed previous post because it was wrong and just taking up space.

Offline theagentd
« Reply #6 - Posted 2015-08-22 08:47:39 »

I couldn't find a version for Math.sin on google which is a pity.
Sin can be calculated either using the cross product between two vectors if you need the sign as well, or if you don't need the sign by simply using the fact that (cos^2 + sin^2 = 1), which translates to
double sin = Math.sqrt(1 - cos*cos);
, but this is less useful.

The cos = dot-product can be used for lots of useful things. A common appliance is field-of-view testing for AI. Given an NPC that is facing a certain angle, you can precompute its normalized view vector each frame. If his field-of-view is 30 60 degrees, you can calculate cos(30). To check if someone is in the NPC's field-of-view:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
//Precomputed:
Vector3 normalizedViewVector = ...;
float cosCutoff = (float)Math.cos(30);

//For each enemy:
Vector3 vectorToEnemy = target.position - me.position;
boolean canSee = dot(me.normalizedViewVector, vectorToEnemy) / vectorToEnemy.length() > cosCutoff;
if(canSee){
    ...
}


This has extremely good performance as it only uses conventional math plus a single square root to calculate length(). The precomputation is generally cheap as it only needs to be done N times per frame, while the enemy testing may be done up to N^2 times.

EDIT:
The dot-product calculates the cosine of the angle from the view vector, so for a 90 degree field of view, you calculate cos(45). This even works for values over 90 degrees, i.e to give the NPC a blind spot directly behind it.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #7 - Posted 2015-08-22 16:18:08 »

I had in mind geometric reasoning...but this is all headed in the right direction.  Gosh we have |a||b|cos(t), if we could cheaply find |a||b|sin(t) we could use atan2.

vectorToEnemy.length() is positive.
Offline theagentd
« Reply #8 - Posted 2015-08-22 17:38:18 »

I had in mind geometric reasoning...but this is all headed in the right direction.  Gosh we have |a||b|cos(t), if we could cheaply find |a||b|sin(t) we could use atan2.
Why is atan2() so much better than acos()?

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #9 - Posted 2015-08-22 18:03:25 »

Short answer atan & atan2 are (vs. acos and asin):
1) faster to compute
2) don't have input domain issues
3) are more robust.

I can give some details if you want.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #10 - Posted 2015-08-22 18:50:16 »

Is it possible to make arc-cos, arc-sin and arc-tan using vectors too?

The alternative cos and sin implementations with vectors are very interesting. I suppose that tan can be calculated as sinAngle/cosAngle which reduces to the cross/dot.

By the way, one disadvantage of the new angleCos method that does just one square root is a higher chance of numerical overflow if the x and y coordinates are very large. This is because they get multiplied together one extra time before being square rooted. I believe that many robust topographical API's such as JTS (https://en.wikipedia.org/wiki/JTS_Topology_Suite) first 'normalise' the coordinates by shrinking or growing the vectors to manageable distances first. Given that JOML probably favours performance over edge-case stability, perhaps it's an acceptable trade-off.

PS: thanks for the detailed explanation theagentd

Offline theagentd
« Reply #11 - Posted 2015-08-22 18:58:37 »

Short answer atan & atan2 are (vs. acos and asin):
1) faster to compute
2) don't have input domain issues
3) are more robust.

I can give some details if you want.
Hmm, interesting. 2 and 3 I can understand, but why is it faster to compute?

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #12 - Posted 2015-08-24 07:47:47 »

Short answer: http://www.wolframalpha.com/input/?i=Plot%5B%7BArcCos%28x%29%2C+ArcTan%28x%29%7D%2C+%7Bx%2C0%2C1%7D%5D

I can expand on this if desired.


Offline Roquen

JGO Kernel


Medals: 518



« Reply #13 - Posted 2015-08-24 08:08:58 »

Pseudo-code for more robust computation (but we're not dropping real missiles into real teacups):
1  
2  
3  
4  
5  
6  
7  
{
  ma = magnitude(a);
  mb = magnitude(b);
  y  = magnitude(a*mb - b*ma);
  x  = mangitude(a*mb + b*ma);
  return 2 * atan2(y, x)
}
Offline Roquen

JGO Kernel


Medals: 518



« Reply #14 - Posted 2015-09-06 00:06:41 »

OK: we're at we could use atan2 and compute the 'y' with |cross(a,b)| and 'x' with dot(a,b).  'y' seems reducible.  The inside of the root looks like:  dot( cross(a,b), cross(a,b) )
Offline Roquen

JGO Kernel


Medals: 518



« Reply #15 - Posted 2015-09-07 11:15:31 »

I'll answer my own question.  If we look at a table of basic vector identities one will be:

(a×b) · (c×d) = (a·c)(b·d) - (b·c)(a·d)

Neat the cross product disappeared.  And we have:

(a×b) · (a×b) = (a·a)(b·b) - (b·a)(a·b) = (a·a)(b·b) - (a·b)2

tying all of this together into pseudo-code:
1  
2  
3  
px = dot(a,b);                       // scaled projection in 'x'
py = sqrt(dot(a,a)*dot(b,b)-px*px);  // scaled projection in 'y'
return atan2(py, px);


the update JOML version (with CommanderKeith's sqrt comment) in pseudo-code:
1  
2  
3  
4  
t = sqrt(dot(a,a)*dot(b,b));  // composed scale of a and b
t = dot(a,b)/t;               // cos(angle)
t = clamp(t,-1,1);            // clamp to legal range to account for compounding errors
return acos(t);        


One thing to note here is that both of these work in any number of dimension(1).  WHAT?  Notice how the cross product above disappeared?  The reason is simple:

THIS IS A 2D PROBLEM:  SO WHY AREN'T WE WORKING A 2D PROBLEM???

(1) Ok...there are a couple of assumptions here, but not important for this monologue.

(EDIT: forgot the acos return for the JOML version)
Offline CommanderKeith
« Reply #16 - Posted 2015-09-07 13:20:28 »

Interesting, thanks for explaining.
An additional computation saving might be making an atan2Sq which gives the square atan2 and therefore avoids the square root, and adds just a multiplication of the dot product in the numerator.
As agentd explained, this can be compared to the atan2 squared of the NPC view angle

Offline Roquen

JGO Kernel


Medals: 518



« Reply #17 - Posted 2015-09-07 13:41:33 »

Something I hinted at but didn't say was:

1  
boolean canSee = dot(me.normalizedViewVector, vectorToEnemy) / vectorToEnemy.length() > cosCutoff;


which I said:  "vectorToEnemy.length() is positive."

This is because is the length is positive, you can multiply both sides by it without changing the comparison.  Then you can loose the root.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #18 - Posted 2015-09-08 09:13:14 »

I'm going to now very quickly repeat everything above but directly in 2D.  If someone wants an informal visualization aid then let me know.  We have two vectors 'a' & 'b' (directions or coordinates) in N dimensions (but let's think 3..the number doesn't matter).  We visualize the vectors in the standard way:  tails starting from some origin and their magnitude as a length with little arrows drawn at the end.  Assuming that 'a' and 'b' are not pointing in the same or opposite directions (in the visualization they don't fall on the same line), then there is a plane which contains both of them.  We're using 'a' as our reference direction so it falls on the positive x-axis.  For our positive 'y' axis we're going to choose the direction that contains 'b'.  We're forcing the visualization of 'b' to be above the x-axis (in the first or second quadrant).  From the head of 'b' (the tip of the arrow), we can draw a vertical line to the x-axis and label the point it cross as 'px'.  Likewise we can draw a horizontal line and label the point it cross the y-axis as 'py'.  These values are: px = parallel projection of 'b' onto the x-axis and parallel projection of 'b' onto the y-axis.  These two values give us a local 2D coordinate of 'b'.

So in this local 2D coordinate system we have (assuming b is unit, |b|=1):

a = |a|(1,0)
b = |b|(px,py)

if 'b' isn't unit then the |b| is already contained in our px and py.  Showing it this way because we can also express 'b' as:

b = |b|(cos(t), sin(t))

From this point of view what the trig operations are really saying is: cos(t) = how much is in 'x' and sin(t) = how much is in 'y'.  Now I'm really still making this overly complicated because I attempt to give a picture of how the pieces fit together.  Now we're ready for the punch-line:

Let X=|b|px, Y=|b|py and H=|b|

X2+Y2=H2 or (s cos(t))2+(s sin(t))2 = s2

So we've done a long dog-and-pony show to derive:  Pythagorean theorem

The Pythagorean theorem doesn't care about the scale of things.  The relation is independent of uniform scaling.  Given two of values we can find the third.  The only higher order math notion required is the dot product which is typically shown as:

(a·b) = |a||b|cos(t)

which is a parallel projection(1) of b onto a , which is a scaled parallel projection onto the local x-axis.  This extra scale factor of |a| doesn't matter since the Pythagorean theorem doesn't care about it.  That gives us a 'how much in x' and we know the magnitude of 'b' so our unknown is 'how much in y'.  Solve for Y:

X2+Y2 = H2  ->  Y2 = H2 - X2


X2 =(a·b)2
H2 = (a·a)(b·b)

Y2 = (a·a)(b·b) - (a·b)2

H may not be immediately clear.  (b·b) is the magnitude squared of 'b'.   The magnitude of 'a' squared (a·a) is being multiplied in to account for the extra scaling on X.

Now for some other parts.  If we wanted to know the unit vector in the direction of the positive 'x' axis then it's simply: a/|a|.  Now what about the same for 'y'?  Let's do the dog-and-pony vector version.

(a×b) would give us a vector orthogonal to the local plane.  Then if we cross that again with 'a' would give us the direction of 'y'.  So:  (a×b)×a.

This is a form of the vector triple product: (a×b)×c = (a·c)b - (b·c)a

So our 'y' direction is:  (a×b)×a = (a·a)b - (b·a)a = (a·a)b - (a·b)a

if |a| = 1, then (a·a)=1 and it would be: b - (a·b)a

the (a·b) is "how much in X" which we multiply by 'a' to get it back into a direction instead of a scalar.  And we're subtracting that from 'b'.  The end result is we're taking 'b' and removing the part of it that's in the 'x' direction.  Or in other words we're zeroing out the x-component in the local coordinate system.  When |a| isn't 1 then the extra (a·a) is accounting for the scaling introduced by (a·b).  The magnitude of the computed Y direction is Pythagorean result above.

Yeah I could have made this easier to understand, but it's already long enough.  If something isn't clear and you care then ask.

(1) Or 'a' onto 'b'...the projection is the same.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #19 - Posted 2015-09-08 11:39:35 »

Ha Ha!  Jerkface.  Made some dumb-ass mistakes trying to bang that out quickly.  Each mistake found before I correct the post get's a medal!
Offline Roquen

JGO Kernel


Medals: 518



« Reply #20 - Posted 2015-09-24 14:09:52 »

Quick review:  If we have two directions, vectors, coordinates in any number of dimensions that we want to find out how they are related and if they are independent then there is a unique plane which contains them.  Otherwise they fall on the same line through the origin and there is an infinite number of planes, so this is a potential hedge case.  And with FP computations they don't have to be exactly linear.  Choose one to be the reference "a" and that is the direction of the positive x-axis of the plane (a Cartesian coordinate system) and some of the relations (with how they relate to trig) are:

unit direction of positive x a/|a| = a/sqrt(a·a)
scaled projection of 'b' onto the x axis (a·b)|a||b| cos(t)
scaled projection of 'b' onto the y axis sqrt((a·a)(b·b) - (a·b)2)sqrt(|a|2|b|2 - (|a||b| cos(t))2) = |a||b| sin(t)
unit direction of positive y ((a·a)b - (a·b)a)/sqrt((a·a)(b·b) - (a·b)2)

One thing I forgot to point out before was why 'b' magically is projected into the positive 'y' axis.  This is because how we would compute the direction of 'y' if we actually needed.  If 'a' and 'b' fall on the same line through the origin, then the projection into 'y' is zero and if we were to attempt to compute the unit direction of it the equation would explode.  This is common when an equation expects a unique solution and there is in fact none or an infinite number.

An example, walking through @theagentd code above, translates into:

We have an entity at point (p) with a unit direction facing of (f) and we want to know if some other entity at point (e) is inside a view cone, which is centered about the facing and the outer edge has some angle (t) with respect to the facing.  If we choose (f) to be the reference direction (a=f), then the relative direction to the other entity is (b=e-p).  Pre-compute: k=cos(t), then

(a·b) = |a||b| cos(s), and since |a|=1, (a·b) = |b| cos(s), where 's' is the unknown angle

and since we want to know if s < t, we can change that to cos(s) > cos(t) given the properties of cos.  Since |b| is unknown, theagentd balances out the scale by computing:  (a·b)/|b| > k.  The thing I mentioned earlier is a property of inequalities:  multiplying both side by a positive number is valid and doesn't change the direction.  So this can be computed as:

(a·b) > |b| k

For geometry (and math in general) it's always true that "a change in coordinate system doesn't change the problem".  In this case the extra uniform scaling on the problem does effect the relation.

If restricting the maximal half-angle of the cone to >= Pi/2, then

(a·b)2 > (b·b) k2, where k2 could be the pre computed value.

---
EDIT: had dot(a,b)...instead of dot(b,b) on that last left-hand side, which is |b|^2...opps.  Also the restriction can be lifted, but need to inequality properties typed up...and this whole scaled projection into a direction is half of how SAT works.
 
 


Offline Roquen

JGO Kernel


Medals: 518



« Reply #21 - Posted 2015-09-25 08:18:49 »

Put a brute force shader visualization here:  http://glslsandbox.com/e#27884.1

Hide the code...change the sampling from 2 to 1.  You can pan around with left-click drag (and less useful zoom with right-click)

There some set-up at the top, junk to draw the sample at the bottom.  A macro value FOV which is the half angle of the cone in degrees..another TURN_RATE to make the facing rotate.  Otherwise the stuff is as from above, other than the comparison has be changed...the left hand side as been subtracted through so we're always comparing against zero.  You can fiddle with the macros and just uncomment the various computations.  They are as follows:

Original version with a root and divide k-dot(a,b)/length(b)
Multiply through to loose the divide: length(b)*k-dot(a,b)
Square to loose the root, but now need to handle the behind case.
Purposefully not in the visualization. Also limits maximum FOV. Sad
dot(b,b)*k2-dot(a,b)*dot(a,b)
But x*|x| is like squaring and maintains the sign! Smiley 
Bye Bye artificially introduced restrictions!
dot(b,b)*k2-dot(a,b)*abs(dot(a,b))
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #22 - Posted 2015-09-28 15:34:42 »

Monologue granted Pointing

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Roquen

JGO Kernel


Medals: 518



« Reply #23 - Posted 2015-09-28 16:16:17 »

Cheers.

Something that may not be clear is that these unit directions derived above are only needed if you're going to perform some 2D calculations and then take the 2D result and place it back into the original space of the problem.  If you're not going to do that then you don't even care about them or if the plane is not unique.  The axis unit directions in the 2D space are always what you expect:

X = (1,0)
Y = (0,1)

and the coordinates in the 2D plane are:

A = (|a|,0)
B = (a·b, sqrt((a·a)(b·b)-(a·b)2)

back to @theagentd's example we have (since a.a=1), the a in the plane is A, and b is B:

A = (1,0)
B = (a·b, sqrt((b·b)-(a·b)2)

then the n-D computation:

|b|k-(a·b)

should be identical to the 2D:

|B|k-(A·B)

(A·B) = dot((1,0), (a·b, sqrt((a·a)(b·b)-(a·b)2)) = a·b
|B| = sqrt((a·b)2 + (b·b)-(a·b)2) = sqrt(b·b)

So, as expected, they are identical. We're logically performing a rotation into a known plane since a rotation is n (number of dimensions) parallel projections into the target coordinate system.

In this 2D space we can think of the pre-computed value: k=cos(t) as the projection into 'x' (the axis of the cone) of the direction of the surface of the cone.  So in the 2D slice the surface of the cone is a line through the origin, the unit direction (C) of that line would dot with C·X = k.  And our test above is:  Is B on the positive side of this line.

Let me break it down by parts.  We have |B|.  That is how far from the origin the point B is.  'k' is how much in 'x', which is the same as how much in 'a'.  Some point on the line that has a distance of |B| from the origin will parallel project into 'a' as |B|k.  Our test point B projects into x as (A·B)=(a·b). The set of all point at a distance |B| from origin fall on a circle of radius B.  And those below our test line will have (a·b) > k|B|
Pages: [1]
  ignore  |  Print  
 
 

 
Riven (397 views)
2019-09-04 15:33:17

hadezbladez (5280 views)
2018-11-16 13:46:03

hadezbladez (2204 views)
2018-11-16 13:41:33

hadezbladez (5544 views)
2018-11-16 13:35:35

hadezbladez (1150 views)
2018-11-16 13:32:03

EgonOlsen (4584 views)
2018-06-10 19:43:48

EgonOlsen (5462 views)
2018-06-10 19:43:44

EgonOlsen (3119 views)
2018-06-10 19:43:20

DesertCoockie (4015 views)
2018-05-13 18:23:11

nelsongames (4708 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!