next »

[Martin 2BAM]

Hi, I'm reaching the limits of my math knowledge and wanted to know if any can help me with this problem.

Basically I want to build a particle emitter that emits at directions between two vectors, uniformly.

I know I could just lerp the angle and get the directions doing (cos(a), sin(a)) but I was trying to avoid those trigonometry function calls.

I'm working with AS3 for the time being and, correct me if I'm wrong but, function calls are expensive and using tables it's even more (because of internal safety bound checking).

Doing my research I found about using complex numbers was similar to using quaternions for 3D rotations and they could be lerped, but as with matrices, they need to call trigonometry functions.

These GDC2012 slides by Jim Van Verth have been very useful but I'm still at loss.

I don't need perfect-precision but would like as close as uniform distribution as I can get. I've read in the linked doc about simply lerping (not nlerp/slerp) complex numbers using a spline to counter act denormalization. Have any of you done that and could give me a hand?
I'v never used splines before.

Thanks in advance.
-Martín

[Trent]

I seem to remember caching cos/sin values in list in FlashPunk because it was faster. It's been a while since my AS3 days, but I'm fairly certain it was faster. 

[jgrams]

Well, Jonathan Blow has an archive of his column:
http://number-none.com/product/

That article says it's March 2002, which would appear to be this one.
http://number-none.com/product/Hacking%20Quaternions/index.html

But then of course there are the usual questions. Not saying you haven't done this, but you didn't say that you have...

Have you measured stuff to see what your needs actually are for speed/accuracy?

If the angle between your two vectors isn't too big, you may be able to get away with just linear interpolation. There will be more particles in the middle than toward the edge, which may not be noticeable, and they'll be slower (which might well be noticeable, but you can normalize to fix that).

If nlerp looks OK but is too slow, have you tried the fast inverse square root trick? Not sure if that makes sense on modern hardware, but it's simple enough that it would be worth a try.

If you really need a slerp, is it actually too slow?

--Josh

[Martin 2BAM]

Thanks for your answers.

jgrams: I did, I'm using loads and loads of particles because I need to and they're as performant as I could make them ^(*). They're an important part of the game. But using sin/cos for each of 2k particles in Flash would be overkill.

Now for velocities I'm overlapping the general direction with Cartesian ranges ^(**) but it looks like crap when the angle gets too far from an axis. I was wanting to be able to set an angle range instead of an x/y range, but keep the performance high.

I'm trying to avoid normalization also (sqrt()). AS3 function calls are expensive and I don't know if the VM has an optimization for sqrt, I think it doesn't.

Accuracy is not very important for me as uniform density. I'll be happy even with 10% error (0.9-1.1 "unit" vectors).

Even if it wouldn't turn to be an issue, being a nerd and all I'd like to know if there's a super cheap way with splines and complex numbers

Thanks again

^(*) pooled linked list (faster in AS3), virtually no object creation,  no function calls iterating, just sum and mult operations, ifs only for TTL and flags.

^(**) General direction is calc'd once for a whole pile of particles, two random numbers are calculated once for each particle's lifetime.
I.e. for each particle:
vel_x = dir_x * speed + random(range_x1,range_x2);
Same for y.

[gimymblert]

Just reading like that I say that normalization (vector/vector) and dot product help, but right now I don't remember how I do it ... I almost never use cos and sin again. But instead of angle you need to store a direction vector.

[jgrams]

jgrams: I did, I'm using loads and loads of particles because I need to and they're as performant as I could make them. They're an important part of the game. But using sin/cos for each of 2k particles in Flash would be overkill.

Even if it wouldn't turn to be an issue, being a nerd and all I'd like to know if there's a super cheap way with splines and complex numbers

Gosh, this got long. tl;dr: Jonathon Blow's article is excellent: basically he's doing a normalized lerp with a fast approximate normalization and is using a polynomial for `t` to smooth out the uneven distribution of the lerp.

OK, well, let me talk through what I know then...This is relatively basic and I'm guessing you know most of it, but maybe it will be useful to someone...

Disclaimer: this is off the top of my head, so you'll want to check it. And my terminology is horribly sloppy here: ignore that.

You can represent orientations by complex numbers (x + iy), where `i` is the imaginary unit (square root of -1). Then rotating is simply multiplying two complex numbers: the one representing the point to be rotated and the one representing the rotation.

An easy and less "mathy" way of thinking about this is to think of an orientation vector as being the direction of the rotated x-axis. Then in 2D the perpendicular of (a, b) is (-b, a), so you can use that as the new y-axis. To rotate a point P=(px, py), you do px*x_axis + py*y_axis. Collecting the "real" x and y factors, we get:

Code:

px2 = px*a - py*b
py2 = px*b + py*a

If you have a rotation `a+bi`, you can rotate in the opposite direction by multiplying by the complex conjugate `a-bi`.

Note that these orientation vectors are supposed to have length 1: otherwise multiplying by one will scale as well as rotate. Also note that they are cos(angle) + i*sin(angle).


Now, linear interpolation is the most basic way of blending two values. If you have two values `a` and `b`, and a blending parameter t which goes from 0 to 1, then the linear interpolation is:

Code:

c = t*a + (1-t)*b

We can do this with vectors, including our orientation vectors. But it interpolates in a straight line. So instead of going around the outside of the circle, it cuts straight across (forming a chord). So the farther apart your vectors are, the worse an approximation it is. If the vectors are directly opposite each other, it will be useless as it just cuts through the center of the circle. For this reason, some people use angle/2 instead of angle to generate their rotation vectors. Then you have to multiply twice to get the full rotation, but it packs a full 360 degrees into half a circle and avoids that nasty glitch in the interpolation.

We can (somewhat) adjust for the problems of linear interpolation by normalizing the result (scaling it back up so it has length 1 again). That at least keeps it on the circle, but they will be unevenly spaced along the circle (since they are evenly spaced along the chord).


So what Jonathan Blow is doing in that article is doing a normalized lerp and using a polynomial ("spline") to adjust the value of t.  Basically he found a polynomial which counteracts the unevenness of distribution that the lerp produces.

So Instead of going linearly from 0 to 1, he defines `t' = 2kt^2 + 3kt + 1 + k`, where `k=0.507 * (1 - 0.788 * cos(alpha))` and alpha is the difference between the two angles you're interpolating between. Note that cos(alpha) is the dot product of the two unit vectors...but you're only doing it once for each pair of vectors, and I'm guessing that you're generating lots of particles for each pair? So it shouldn't be too expensive.

He's also using an approximation to the inverse square root for the normalization step.

I recommend you read it (if you haven't already): he has good diagrams and so on: I think it's fairly easy to follow.


I also wonder if you couldn't roll it all into one. Instead of using t and 1-t in the lerp, come up with a pair of functions which take t and compute a `ta` and a `tb` which would both smooth the unevenness and give a roughly normalized vector in one step? It would be interesting to play with, anyway.

HTH,

--Josh

[Martin 2BAM]

Wow, thanks!

It's good to keep it for reference, your explanation was very easy to follow. Although I couldn't understand why the following would make a difference:

For this reason, some people use angle/2 instead of angle to generate their rotation vectors. Then you have to multiply twice to get the full rotation, but it packs a full 360 degrees into half a circle and avoids that nasty glitch in the interpolation.

I opened Blow's article in a tab and then forgot, but I'm reading it right now. Nice hacking, reminds me of Carmack's magic number for fast sqrt.

[jgrams]

I couldn't understand why the following would make a difference:

For this reason, some people use angle/2 instead of angle to generate their rotation vectors. Then you have to multiply twice to get the full rotation, but it packs a full 360
degrees into half a circle and avoids that nasty glitch in the interpolation.

Normally, the farthest apart two vectors can be is 180 degrees, right? After that they flip and start counting from -180 degrees back toward zero.

What happens if you interpolate between two vectors that are 180 degrees apart? All the points will fall on the line through the center of the circle, so if you normalize them, all you ever get is one or the other of the original points. And the halfway point is the origin, so you can't even normalize it at all. Ugly.

If you use half-angle vectors to represent the orientations, then the farthest apart those representations can ever be is 90 degrees, so you can interpolate between them without that singularity in the equations.

Does that make sense?

Wow, sixth post today. Can you tell I'm procrastinating? 

[Martin 2BAM]

Crystal clear, thanks again

Think that you're helping others and you wont feel that bad, hehe

[UltimateWalrus]

Just to throw in my two cents...

People drive themselves crazy trying to write code that is efficient from the get-go.  They think coding can be a one-step process:

1.) Write perfect code that won't need to be optimized or debugged   

In reality, there are inevitably multiple steps.  As I see it, there are at least four:

1.) Focus on writing clean, understandable, reusable code.
2.) Debug this code as it's inevitably full of runtime errors.
3.) Performance problems?  Figure out WHERE the performance problem is coming from (IMPORTANT)
4.) Fix the bottleneck and don't waste your time on anything else.

However many people (I used to do this as well) focus on efficiency when writing code and wind up with code that's obtuse, messy, and very much specialized to the task at hand (i.e. not reusable).  I once watched a lecture on best coding practices in which the lecturer said that "premature optimization is the root of all evil," and it really stuck with me.  Since then my code has been so much cleaner and I haven't really had any more performance problems than I would have anyway, since bottlenecks most frequently seem to reside in places you wouldn't expect.

So, you're delving into all this math and complexity just to get around making one call to sin/cos.  But you don't even know for a fact that it will actually cause performance problems.  Why waste your valuable time trying to solve a problem you don't even know for sure exists?  Come back to it later if it causes problems.

(aside: in the case that it does cause problems, I would be inclined to simply generate precomputed sin/cos arrays as this is much simpler than delving into complex numbers)

[Martin 2BAM]

It's just that this time isn't premature and it's an academic inclined discussion.

Your comment sounds patronizing, as if you skipped through the whole discussion and just played the pre-recorded expert programmer speech.

To summarize:
1) AS3 is slow (vectors too). No tables.
2) I'm not on a schedule.
3) I wanted to know anyhow.

[nikki]

It's been mentioned before but how about a simple cached sin cos ?

Code:

cached_sin = new Array(360)
cached_cos = new Array(360)

for i in [0 ... 360]
  cached_sin[i] = Math.sin(i)
  cached_cos[i] = Math.cos(i)

[Trent]

In support of lookup tables, and an alternative, FastMath

http://jacksondunstan.com/articles/1190

https://code.google.com/p/apparat/source/browse/as3/Apparat.Library.AS3/src/apparat/math/FastMath.as?r=c8b764b3a535184a604e9d2309655de99be1d8b8

Because fuck the police.  

[ThemsAllTook]

I had to clean up some alarmingly drama-filled posts in this thread. Let's keep technical discussion technical, please. This forum is not the place to attack people's character.

[gimymblert]

So I tried to remember how I did it. I don't know how much good it will help you need but basically instead of using angle I used a kind of unit rotation vector. Basically I just add each frame a multiplication of that "unit rotation vector" (urv) plus the normal of the "original direction" that never change. Basically I use the result on the frame and then forget it afterwards remultiplying it to a different "angle" each time. Basically the number of addition is the angle and are multiple of the original urv. That was design for doing stuff when I programmed on casio. Don't really know how it fare against other solution.

[J-Snake]

Don't know it has been mentioned yet or it is what Gimmy suggests but complex numbers provide a native solution to that. A complex multiplication of 2 complex numbers (or vectors if you treat them like that for your purpose) corresponds to multiplying their magnitudes and adding their angles.

So simply define a unit vector with a slight angle offset ("rotateVector"). Now if you want to rotate a vector then simply "complex-multiply" it by that rotateVector. The magnitude won't change (because unit vector) but the angle of the rotateVector will be added.

[jgrams]

Don't know it has been mentioned yet or it is what Gimmy suggests but complex numbers provide a native solution to that.

Yes to both, I think. Dunno how it plays out in practice on various platforms compared to other techniques, but the bit about using complex numbers as a 2D analogue of quaternions (and techniques for interpolating them) is what the OP was curious about, near as I can tell.

--Josh

[Martin 2BAM]

Yup. Thank you guys!

Thanks for pointing to FastMath (which took the sin/cos snippet from here)
Building with Apparat to inline those functions and harness performance seems too complicated, but that snippet manually inlined is golden.

I think multipling several times (with a for?) would be less performant than the sin/cos calls or table because of repeated conditional checking, worse if you want smaller angle intervals. I'd like to compare the "fastTrig" approach to Blow's approximation normalization method.

The other day I tested if inlining code (even with a lot of "object." prefixing) was faster than calling an object function that does all the operations, and it very much is. You can check my results.

@ThemsAllTook: Sorry for the drama if I took part on it. Was probably having a bad day.


EDIT: I hate to be proven wrong but the fastest method seems to be using local tables (fixed Vector.<Number>) of power-of-two elements because & is faster than % for clamping the index. I'm going to try Blow's method (when I decypher it) and see if it can outperform atan2/sin/cos with spline/invSqrt
 
I'll be posting results and charts soon for sin/cos, sqrt and atan2.

[Martin 2BAM]

Sorry for the delay, I totally forgot and moved on.

The best solution for my case was to use a sine/cosine table of power-of-two elements without anti-aliasing/lerp, to roto-transform a base direction with a given relative angle range.

Strangely, I found that apparently in AIR/AS3, single line operations (r=a; r+=b; r&=c;) are a tiny bit faster than all in one line (r=(a+b)&c) operations.

Here's the AIR source and FlashDevelop project (You must click on the window to start the benchmark)

And a chart
SLO stands for single line ops (explained above).
"good angle" expect a good-formed angle (0 to 2pi) and makes no corrections.
"sin+cos" means two different tables instead of re-using the sine table for cosines.
"pow2" are power-of-two sized tables (using bitwise and & instad of modulus % for clamping)

[FranLesko]

Just finished reading the whole thing. Quick question: did you try approximating those functions with polynomials? If accuracy is not that important, you could even use a simple tylor polynomial centered around an average value to ease out the error. If you did think about it, why did you discard it? (Since it was the first thing I thought I wanna learn if it is a good approach or not   ).

Edit: Nvm, just found out that the best way to do it is with a square fit of the function. It was inside one of the links provided in this post. My bad.