Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
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  
  Complex number cookbook  (Read 8400 times)
0 Members and 1 Guest are viewing this topic.
Offline Wiki Duke

?





« Posted 2013-03-14 17:44:34 »

By representing an orientation (or rotation) by a complex number instead of an explicit angle we can drop a fair number of expensive operations.  So instead of storing angle 'a', we store complex number (cos(a), sin(a)).

Another potential advantage is the algebra framework (just manipulating algebra) and reasoning.  Algebra's like complex number, vectors, quaternions, etc allow thinking in terms of relative information which can greatly simplify the process.

We will assume that standard mathematical convention of the X axis pointing the to right and the Y axis pointing up.  Additionally we will assume that the reference orientation of objects is pointing straight right. Combining these together when thinking about some specific entity, we can think in terms of its center being at the origin and its facing straight down the X axis.

NOTE: Although angles are talked about, this is for understanding and thinking purposes and not computation.

Basic examples in code:

Common definitions
Capital letter are complex number and small are scalars.
  X=(a,b)
  Y=(c,d)
  P=(x,y)
  R=(cos(a), sin(a))
  S=(cos(b), sin(b))
  

Complex number basics


Complex numbers are represented by two numbers, which we will denote as a pair (a,b).  The first number we will call 'x' and the second 'y'.

Conjugate
X* = (a,b)* = (a,-b)
R* = (cos(a),sin(a))* = (cos(a),-sin(a)) = (cos(-a),sin(-a))

So the conjugate reflects (wikipedia) about the X axis, which is the same as negating the angular information. (SEE: Trig identities: Symmetry)

Addition/Subtraction
X+Y = (a,b)+(c,d) = (a+c,b+d)
X-Y = (a,b)-(c,d) = (a-c,b-d)


Operation is component-wise.  Can represent translation.

Product
XY = (a,b)(c,d)
   = (ac-bd, ad+bc)
RP = (cos(a), sin(a))(x,y)
   = (x cos(a) - y sin(a), y cos(a) + x sin(a))
RS = (cos(a), sin(a))(cos(b), sin(b))
   = (cos(a)cos(b) - sin(a)sin(b), cos(b)sin(a) + cos(a)sin(b))
   = (cos(a+b), sin(a+b))


So the product sums the angular information of the two inputs. (SEE: Trig identities: angle sum)

SEE: C2D.mul(C2D)

Product combined with conjugate
X*Y = (a,b)*(c,d) = (a,-b)(c,d) = (ac+bd, ad-bc)
R*S = (cos(a),sin(a))*(cos(b),sin(b))
               = (cos(-a),sin(-a))(cos(b),sin(b))
               = (cos(a)cos(b)+sin(a)sin(b), -cos(b)sin(a)+cos(a)sin(b))
               = (cos(b-a),sin(b-a))


Since we can add angles with the product and can negate an angle with the conjugate, the two together allow us to subtract angles.  (AKA get relative angular information)

SEE: C2D.mulc(C2D) & C2D.cmul(C2D)

Magnitude (L2 norm)
|X| = |XX*| = |(a,b)(a,-b)| = sqrt(a2+b2)

Notice that we're not calling this length.  Complex numbers, vectors, etc do not have lengths (nor positions).  What they represent in a give instance might have a length equal to its magnitude.

Unit complex and trig form
Unit complex numbers have a magnitude of one and can be written in 'trig form':
  (cos(t),sin(t)).

Since scale factors can be pulled out (see scalar product) all complex numbers can also be written in 'trig form':
  m(cos(t),sin(t)).

Scalar product
sX = s(a,b) = (s,0)(a,b) = (sa, sb)

This can be reversed, so all scale factors can be pulled out.

Inverse
1/X = X*/(XX*) = (a,-b)/(a2+b2)
1/R = (cos(-a),sin(-a))/(cos(a)2+sin(a)2)
    = (cos(-a),sin(-a))
    = R*


The multiplicative inverse of a unit complex is the same as its conjugate.

SEE: C2D.inv()

Counterclockwise rotation of point about the origin
Falls directly out of the product.  Given rotation (R) and point (P), the point after rotation (P'):
P' = RP
   = (cos(a), sin(a))(x,y)
   = (x cos(a) - y sin(a), y cos(a) + x sin(a))


Example:
  P  = (3,3)
  R  = (cos(pi/4), sin(pi/4)) = (.707107, .707107)
  P' = (3,3)(.707107, .707107)
     = (0, 4.24264)


How do I find rotation of A into B
Solve the above.  Assuming A & B are unit vectors:
  RA = B
  R  = B(1/A)
  R  = BA*


Example:
  A  = (0.809017, 0.587785)
  B  = (0.5, -0.866025)
  R  = BA*
     = (0.5, -0.866025)(0.809017, 0.587785)*
     = (0.5, -0.866025)(0.809017, -0.587785)
     = (-0.104528, -0.994522)


Counterclockwise rotation of point about arbitrary point
We can rotate about the origin, to rotate about an arbitrary point (C) translate the system to the origin, perform the rotation and then undo the translation.
P' = R(P-C)+C
   = RP-RC+C
   = RP+C-RC
   = RP+C(1-R)
   = RP+T


where T = C(1-R).  Look at the last line. It is telling you that the rotation R about point C is equivalent to a rotation about the origin R followed by a translation T.  And C is recoverable from T & R: C = T/(1-R) (assuming R isn't 1...or no rotation).

Composition of rotations
Falls directly out of the product.  Given rotation (R) followed by rotation (S):
RS = (cos(a+b), sin(a+b))

Orthogonal direction
To find a direction orthogonal in a right-handed sense is the same as rotating by pi/2 radians (90 degrees), which is to multiply by (cos[pi/2], sin[pi/2) = (0,1).

ortho(X) = ortho((a,b)) = (a,b)(0,1) = (-b,a)

Relation to dot and cross products
Falls directly from the product where one is conjugated:
X*Y = (a,b)*(c,d) = (a,-b)(c,d) = (ac+bd, ad-bc)

dot(X,Y)   = ac+bd
cross(X,Y) = ad-bc

The dot product is the parallel projection and the cross is the orthogonal projection.  Cross product is related to dot product by: cross(X,Y) = dot(ortho(X),Y).

Basic geometry



On which side of a line is a point?
A line can be represented by a direction (L) and a point on the line (A).  The simplest case is a line which coincides with the X axis, L=(1,0) & P=(0,0), in which case we can simply examine the 'y' value of a test point (P).  If 'y' is positive, then it is above, zero on the line and if negative then it is below.  Moreover the value is the orthogonal distance of the point from the line.

Next let's consider an arbitrary line through the origin with unit direction L.  We can simply rotate the system such that the line coincides with the X axis as above and we're done.  Our modified test point becomes: P'=PL*.  Now the 'y' of P' is exactly the same as above.  To fully generalize we simply need to move the line to the origin which give us: P'=(P-A)L*.

If we were to plug in symbolic values: P=(px,py), L=(lx,ly) & A=(ax,ay) and expand we would see that we have unused intermediate values.  This is because we are ultimately only examining a single component..we're only examining the orthogonal projection of the point into the line (SEE: cross product above).

Additionally the direction of the line does not need to be normalized if we're only interested in above, on or below line question.  The reason is because we only care about the sign of the result to answer our question.

So the 'which side' question reduces to: cross(L,P-A), which expands to the following pseudo-code:

  return lx*(py-ay)-ly*(px-ax)

Aside: the previous can be expanded to cross(L,P)-cross(L,A) = cross(L,P)-m.  The scalar 'm' can be stored instead of the point 'A' to represent the line.  This value 'm' is commonly called the 'moment about the origin'.

Basic examples


At the top we say we can represent an entity by its position and orientation and think about its center as being at the origin and facing straight down the X axis (the reason for this is because that's the entity's local coordinate frame).

Let's call it's position E and orientation F and we have some test point P.  We can translate the system to the origin (P-E) and then we can undo the rotation of the system by multiplying by F*, which gives us: (P-E)F*.  So P in the reference frame of our entity is:

P' = (P-E)F*

Example:
  P  = (100,100)
  E  = (200,200)
  F  = (.92388, .382683)  <- Pi/8 or 22.5 degrees
  P' = ((200,200)-(100,100))(.92388, -.382683)
     = (130.656, 54.1196)


If you've ever worked with vectors, this should seem similar: find the delta distance and perform the dot and/or cross product. The above equation is finding the delta distance and then effectively computing both. (Obviously you only compute one if only need one).  So the dot product is simply the 'x' coordinate in the local coordinate frame (parallel projection) and the cross is the 'y' coordinate (orthogonal projection).

What's my unit direction vector?
It's pretending the unit complex number of the orientation is a unit vector. It has the same numeric values for 'x' & 'y'.

Is it behind me?
As noted above the dot product is 'x' in the local coordinate frame, so the sign of the dot product.  If negative it's behind the center point with respect to facing and positive if forward.

Turn clockwise or counterclockwise?
As noted above the cross product is 'y' in the local coordinate frame, so the sign of the cross product.  If positive the shortest turn is counter clockwise, if negative it's clockwise and if zero it's straight ahead.  

Turn toward point with constant angular velocity
Again, the sign of cross product tells the minimum direction. Take a constant angular velocity, store as a unit complex number 'A'.  If the sign of the cross product is negative, we need to conjugate A (negate it's 'y' component). Multiply the current facing 'F' by the potentially modified 'A'. Take our new 'F' and cross again.  If the sign has changed, we've overshot the target.

Is point within field of view
Given an entity in its local coordinate frame:  image some field of view (<= Pi or 180 degrees), which become a pair of line segments symmetric about the X-axis (or triangle or cone).  We can immediately note a couple of things.  The first is that if our x component of a test point P=(px,py) is negative that it cannot be inside.  The second is that given the symmetry about the X-axis, P and P* will always return the same results. Given the second we can form a new test point P'=(px,|py|).  Now the problem is identical to on which side a point falls with respect to a line through the origin and we the first observation isn't required to compute the result. Since we're asking 'below' the line, we negate the result to convert into the convention of positive is inside, yielding the following pseudo-code:

  return ly*px-lx*Math.abs(py);

As with the point to line test, our direction L does not need to be normalized and L is half of the field-of-view.

Which unit direction forms the minimum angle with the local X axis.
Although related to point/line and view-of-view, this case reduces to simply the direction with the greatest x component.

Bounce reflection
Given a vector (v) of something that hits a surface with normal (n) the resulting vector (v') has the same orthogonal part and the parallel part is negated.  The parallel part is dot(n,v), so v-n(dot(n,v)) removes the parallel part and v-2n(dot(n,v)) results in the parallel part being negated.

For point reflections: negate the bounce reflection equation.
SEE: C2D.uref (this is point refection implementation)
This wiki entry has had 5 revisions with contributions from 1 members. (more info)
Online delt0r

JGO Knight


Medals: 26
Exp: 18 years


Computers can do that?


« Reply #1 - Posted 2013-03-14 18:04:55 »

That is a pretty complicated intro/explanation.

Really for representing angles you can keep it much simpler. Forget useless definitions like complex numbers don't have length. Who cares? You can interpret them as a vector, in which case they do. They are just a vector pointing in the direction they represent.

By some fluke of math, complex multiplication is the same as adding angles. Division is subtracting angles. Pure interpolation with normalization works well enough for interpolation. The real part is the same as cos, the imaginary part the same as sin. tan=sin/cos. To compare to angles we use the fact that atan2(x,y) >=< tan2(x',y') is the same as comparing y/x to y'/x'. Just take care of the degen you get with x tending to 0 and really compare yx' to y'x and you get the same result. Now you can check to see if something is withing a bracketed set of angles.

Perhaps i should expand a little. But really i don't even follow the why of what is the previous post.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Roquen
« Reply #2 - Posted 2013-03-15 16:34:53 »

Some suggesting on how to make it easier to understand would be helpful. Smiley  This is a wiki page and I certainly won't cry if you modify it.  To address some of your points.

Why mention length != mag?  Because un-learning stuff you've learned wrong is hard and lots of text say vectors have lengths and/or are centered at the 'origin' and make it sound like direction and position vectors are somehow different things.  And I've seen people struggle to unlearn stuff they've mis-learned.  Personally I had a heck of of time unlearning that the cross product of vectors in 3-space isn't a vector and wish someone would has said something like: "the cross product of two vectors is a bi-vector.  What's a bi-vector?  Something we're going to pretend is a vector for the moment.  Don't worry about it for now, just keep this is the back of your head.".  But having said that, I don't have any strong opinion about keeping that sentence...it's simply my reasoning for having there in the first place.zZ

Quote
By some fluke of math, complex multiplication is the same as adding angles. Division is subtracting angles.
I don't like black boxes.  You give people black-boxes they're stuck with what you've spoon feed them.  As examples, consider the three reflection implementations from my toy complex class: here.  Or the rectangle vs. point and circles intersection tests.

Quote
Pure interpolation with normalization works well enough for interpolation.
Here I assume you mean for angle parametrization: lerp instead of slerp.  While true for probably most cases, I'm of the opinion that it's better to understand how slerp works and want you get if you straight lerp instead.  As an example, a many entity game could have a simulation rate as low as 10 Hz, with smoothing on the rendering side.  Straight lerp is highly likely to cause noticeable defects.  Of course this is easy to fix, but you only can if you understand how the parts work.

Quote
The real part is the same as cos, the imaginary part the same as sin.
I like to avoid using "real" and "imaginary" as I find terminology is a source of confusion.  Forget "i".

Quote
To compare to angles we use the fact that atan2(x,y) >=< tan2(x',y') is the same as comparing y/x to y'/x'. Just take care of the degen you get with x tending to 0 and really compare yx' to y'x and you get the same result.
I'm slow today and am not understanding what you're saying here.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2013-03-19 17:24:09 »

Added a couple of examples: field-of-view and point/line test with supporting stuff.
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #4 - Posted 2014-04-15 10:49:26 »

I think it's really hard to understand without any pictures describing what is going on. I have to do this in my mind and that only works if I have already understood it. It's the Bret-Victor-Syndrom I'm talking about Grin Someone made a really nice intro to Complex numbers and why they can be used to represent sqrt(-1) and how we should picture them:

http://acko.net/blog/how-to-fold-a-julia-fractal/
See the first Presentation on that page (Initially shows the number line).

You might like other things from him as well, so check his blog out, he does exactly what Bret Victor initially encouraged to do Smiley

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Roquen
« Reply #5 - Posted 2014-04-15 15:22:08 »

Yeah I've seen that site.  Diagrams are great and very helpful...interactive is even better.  And I can't motivate myself to do either.
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #6 - Posted 2014-04-15 15:32:19 »

Yeah I've seen that site.  Diagrams are great and very helpful...interactive is even better.  And I can't motivate myself to do either.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Roquen
« Reply #7 - Posted 2014-04-17 16:05:43 »

Think about integers for a second.  We start with 0 (or 1 depending on who to talk to) and they're formed by repeatedly adding 1.  Each time giving you the next number in the sequence.  Then you get wild-and-crazy and extend the concept to extend in the negative direction.  Negative numbers!  What?  You can't say have a negative number of cows!!  Madness!  At least to the ancient greek math-heads it was...they didn't have the concept.  Now jump to complex numbers.  Constructed by using two instead of one number where the 'second' has a magic basis that squares to -1.  Placing special "meaning" to the sqrt(-1) in complex numbers is the same as placing special meaning to subtracting 1 in integers.  Neither are interesting as operations.  The sqrt(-1) is meaningless in reals just as you can't give away a cow you don't have.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 741
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2014-04-17 16:33:36 »

<offtopic>

Unless you are among the federal farmers, which can accumulate cow-depth by loaning imaginary cows to peasants, skimming off the milk for profits.

</offtopic>


In other news: blasting newbies with a 'succinct specification' is a sure way to turn them off. It doesn't really matter whether you are correct, if your audience can't follow your step by step reasoning. A few visualisations will help enlighten them, but given the amount of work required, and the already available resources on the internet, I doubt anybody here would be willing to make the effort. Emo

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #9 - Posted 2014-04-17 16:42:10 »

Yeah: I know.  My main barrier is I doubt that enough people would bother to understand even with "aids" to make the effort worthwhile.
Pages: [1]
  ignore  |  Print  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (32 views)
2014-07-17 21:55:21

Zero Volt (28 views)
2014-07-17 14:47:54

danieldean (24 views)
2014-07-17 14:41:23

MustardPeter (25 views)
2014-07-16 14:30:00

Cero (40 views)
2014-07-15 15:42:17

Riven (42 views)
2014-07-14 09:02:53

OpenGLShaders (29 views)
2014-07-14 07:23:47

Riven (29 views)
2014-07-14 02:51:35

quew8 (26 views)
2014-07-13 04:57:52

SHC (63 views)
2014-07-12 08:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!