Cartesian to angle
 

Given arbitrary (x,y) Cartesian coordinates, how do you program the calculation of the 0-to-2pi angle clockwise from the +Y axis?


Note: I accidentally wiped out the original post. If the reconstructed wording above is not exactly what I originally posted, let me know and I will fix it.

Re: Cartesian to angle
 

I use "atan2(x,y)". It's not 100% what you're looking for (measured (-pi,pi] from the x-axis clockwise) but it does all of the "hard work" in the standard library so it should be efficient in the general case. The conversion from there to what you want is straight forward.

Don't feed it (0,0) :)

Wikipedia gives a good description.

How do you?

Re: Cartesian to angle
 

from the +y axis? atan2(-x,y) seems to do the trick.

Re: Cartesian to angle
 

atan2(x,y) gives +/-pi clockwise from the +Y axis. That puts the discontinuity on the -Y axis, which then requires you to add conditional logic to fix it. There's a better way.


BTW, concerning atan2(0,0), many modern implementations, such as the microcode in the FP unit of the Pentium*, helpfully return zero when both arguments are zero. Does anyone know what the FRC versions of LabVIEW, C++, and Java do?


* here's a short test code written in Delphi:

USES windows, sysutils;


Function FPatan2(y : extended; x : extended): Extended;
Assembler;
asm fld [y] ; fld [x] ; fpatan end ;


BEGIN

write(FPatan2(0,0),' Pentium FP processor built-in microcode');

END.

Re: Cartesian to angle
 

atan2(-x,y) gives you angles counter-clockwise from the +Y axis.

Re: Cartesian to angle
 

Just to be clear, all references to atan2 in any of my posts, UOS, refer to the standard definition of the order of the parameters, not the reversed-order of, say, Microsoft Excel spreadsheet.

Re: Cartesian to angle
 

atan2(-x,-y)+pi seems to avoid excessive logic.

Re: Cartesian to angle
 

That's what I use. Here's a cheatsheet for other angle choices.

Re: Cartesian to angle
 

A look up table?

Re: Cartesian to angle
 

Why? That's terribly cumbersome compared to the methods already posted.

Re: Cartesian to angle
 

Well, it takes less clock cycles to just retrieve data from an array compared to calculating the angle on the fly. Even though a look up table does take up considerable amount of space in the RAM (Not really since we are dealing with 64 MB of RAM...) Also given the level of accuracy we only really need, about ± pi/180 radian. I think it should be fine.

Re: Cartesian to angle
 

The cycles are a nonissue on the cRIO, and using the function is substantially less code/setup time.

Re: Cartesian to angle
 

Where do you get your information ?

Re: Cartesian to angle
 

You must spread some Reputation around before giving it to Ether again.

Re: Cartesian to angle
 

Fantastic!

I though you were going to post the trig logic to do all of the calculations. :) "atan2" is certainly the way to go, transforming coordinates before using it is great.

I need to look at a clock again... right hand rule = CCW!!! :ahh: See my earlier post.


From a readability perspective, consider defining a macro statement such that.

angle = HEADING(0,0);



atan2(0,0) is undefined in the standard. So for cross platform use, you should check for this as an arbitrary compiler can throw an exception.

if y == 0.0 then y = 1e-8.

Assuming you aren't working with nano-bots :) this will do nicely and leave your (0,0) point at 0. Unfortunately this adds a comparison operation which, as implied here, are commonly the most costly operations and what you are trying to avoid. :( This is a prety good arguement for changing the standard.


I did some reading, and as Ether pointed out, ALL recent Intel chips define (0,0) as 0 and this is on the chip and part of the FPU. If you use a look-up table, you need an unbounded (or large) 2D table in x and y... You can manage this by normalization or conversion to a one dimensional problem but atan2 solves it right there in the silicon. There are a host of other issues with the look-up table but the one that strikes me is the effort associated with continually moving a table back and forth through the layers of cache on the chip (Cache is MUCH smaller than RAM). It's not a good option and should not be faster (coding or execution with other intensive code in the loop) or portable to higher resolution applications. In the interest of exhausting all alternatives, the look-up table certainly is "out of the box" and I like it. Keep up the good work!

With the Intel FPU, most modern PC's and Macs will get (0,0) = 0 "right" provided the compiler actually accesses the FPU directly for this calculation (that would be most compilers including gcc). But what does the cRIO do? Is the FPGA intel based? Looks like "Xilinx Virtex" is a custom processor for FPGA? So you need documentation of a firm commitment to define the result as 0, or you need to test and a re-test every time the chip is upgraded which could happen without a "model" change to cRIO.

Re: Cartesian to angle
 

I'm pretty sure LabVIEW has two different atan commands in its Math/Trig library (which I believe is supported on the cRio). The first takes a float which should be your y/x value, and then spits out theta on the interval (+pi/2, -pi/2) relative to +X (note the inability to deal with infinite slope, one of the problems avoided by the other command). The other takes an x and a y separately, then does all the logic for you to return theta on the interval [0,2pi) from +X. To find the angle from +Y, you can subtract 90 (careful of wrapping, if it matters), or feed y in for x and -x in for y (the second one is waaaaay better).

Edit: Theta is counter-clockwise from reference point, of course. All x and y inputs are on [-1, 1] as one would expect on a unit circle.

Edit: And now I see that you asked for clockwise from +Y. Simply flip your inputs around the y-axis: give it y for x and +x for y.

Re: Cartesian to angle
 

In theory, this two parameter atan calculation only needs to do the following:

Take the arc cosine of x, which is on [-1, 1] to get theta on [0, pi], via whatever method is effective (lookup table, polynomial approximation, etc.) If y is less than 0, subtract theta from 2pi. Done. Theta is on the interval [0, 2pi), counterclockwise from the positive x-axis.

Then you swap inputs as outlined above to get the special, non conventional stuff the OP is asking for. This effectively flips the whole situation about y=x, which is equivalent to the relationship between his question and convention.

Re: Cartesian to angle
 

Two things:

1) The question was asked in the context of the handling of atan2(0,0) for FRC. The answer, for LabVIEW, is that it returns 0, at least according to the simple test I ran on a desktop PC (not in a cRIO). Not being a LabVIEW guru, I don't know if it sets any error flags which might have side effects elsewhere. Does anyone know what the FRC versions of C++ and Java do when running on cRIO?

2) LabVIEW atan2 does not return [0,2pi). It returns an answer in the range (-pi..pi] (not surprisingly).


You are given arbitrary (x,y). So you must take the arc cosine of x/sqrt(x²+y²). Not that it matters for purposes of FRC, but numerically that is inferior to a properly implemented atan2(y,x) (and also suffers from the 0,0 problem). Also, since the sign of y is lost in the squaring operation, additional conditional logic is necessary to get the desired range.

Re: Cartesian to angle
 

There were a number of questions raised. I'll respond to the ones I remember.

What is atan2 of 0 and 0. In LabVIEW, it is 0, at least on an Intel mac. I don't have a cRIO in front of me. I hope/suspect that the PPC LV will return the same, but since I don't have the LV test suite in front of me to prove that is a tested result, I'll speculate that it returns zero. The applied mathematicians on the LV team tend to be picky about things like that, so they have test suites that enforce the results across platforms. Can someone test for sure?

What does the FPGA do? Is it Intel? It is not Intel, and it doesn't natively do FPU operations. It is a field programmable gate array, a bunch of low level logic operations. In order for it to do an integer addition, an adder has to be constructed in it. If you also wish to multiply, a multiplier has to be constructed. The results of those operations are determined by the adder or multiplier you emit to the FPGA. The FPGA image used for FRC contains no floating point trig operations, and in fact I doubt it contains any floating point operations at all as they consume gates very quickly.

Which is faster/better, the atan2 operation, or a lookup table? I have my suspicion/opinion, but this is the sort of thing where the actual answer is ... it depends. Rather than take someone's answer, the approach I'd encourage you to take is to implement both and learn the magnitude of the operations involved. If the lookup table is pretty fast, what if you interpolate for more precision. My point is that knowing A is faster than B is useful info, but more useful is to know the rest of the tradeoffs, and to know how much faster and why.

Greg McKaskle

Re: Cartesian to angle
 

There seems to be a lot of confusion as to what an FPGA is, specifically what the FPGA in the cRIO is, if anyone is so inclined it may be of value for someone to write up a description about it. It seems that despite being tucked well within NI's system there is a lot of curiosity about it.

To answer quickly FPGA's and processors are inherently different things. an FPGA or field programmable gate array is basically a huge array of gates, basically if you could take millions of nand gates and organize them in an array such that you can combine them in any way you like you would have the functional equivalent of an FPGA. Obviously the execution of an FPGA is a bit mor ecomplicated but you can visualize what is happening this way. By combining the gates in the FPGA in different ways you can create any logic circuits within the chip, including processors. The Xilinx Virtex is simply the family of FPGA's the one on board the cRIO belongs to. Xilinx is the manufacturer, Virtex is the family. Xilinx does have a few different soft core processors (processors created wthin the FPGA) that you can load onto the chip (MicroBlaze, PicoBlaze etc.). I do not howeve know whether these (or any thing simmilar) are implemented in the FPGA, I would guess they are not.

Re: Cartesian to angle
 

Floating point operations are not done in the FPGA on cRIO, they are done in the PPC core's FPU. You can look at the details for it here: http://cache.freescale.com/files/32b...e300coreRM.pdf

Edit: FP instructions are in section 3.2.4.2 (pg 119).

Re: Cartesian to angle
 

Why would you want atan2(0,0) to return 0, as opposed to any other value? If your point is at the origin, the line between the origin and your point could point in any direction. What is the use case for atan2(0,0) = 0 being helpful?

Re: Cartesian to angle
 

Some atan2 implementations throw an exception at (0,0), which is more "correct" mathematically but a pain to deal with as a programmer. You either need to pre-test for (0,0) or wrap it with a try..catch.

Some implementations return NaN (Not a Number). You need to test for this, since NaN can "poison" your result - the result of operations with NaN as an operand is NaN.

By returning a valid number you can avoid having to explicitly test for (0,0) when you don't care. For example, in cartesian -> polar conversions. This makes those calculations a bit easier. For cases where you do care about (0,0), you need to explicitly test before the calculation - but you would have had to do this in the previous methods any way.

As you said, it could point in any direction. The decision to return 0 is arbitrary but convenient. It could just as easily return 0.1234567... but that would confuse us humans.


The wikipedia article goes a little bit into the history if you are interested: http://en.wikipedia.org/wiki/Atan2


I did an fixed-point assembly implementation of Atan2 for the M3-Cortex when I worked for TI. I had a(n extremely nerdy) blast doing it - the arctrig functions have some cool features that make their approximations interesting.

Re: Cartesian to angle
 

Joe,

Thanks for the link to this document! For those interested, the latency (in cycles) of each instruction on the PPC is listed starting on page 300 (section 7.7). Hopefully this can be a tool to help settle arguments in the future.

Re: Cartesian to angle
 

I'm by no means an FPGA expert, but I'll attempt to quench some of the curiosity.

FPGA stands for "field programmable gate array". NI uses it in our RIO platform of products, which stands for "reconfigurable I/O". Both the FP and R in the acronym attempt to convey that this piece of HW is user-definable, configurable, perhaps even programmable -- given that you have the tools and the know-how. The GA in the acronym declares that the elements being configured are discrete logic gates, as opposed to analog op-amps or other electronic elements. In the RIO family of products, the FPGA is used for highly deterministic triggers, filters, and timing of I/O pins on the modules. It is connected to the processor bus and I/O configuration and values can be accessed by the traditional CPU also running flexible user code.

Rather than think of the FPGA as a processor, think of it as a user-configurable digital logic circuit board, something like a very very dense protoboard which is populated with NAND gates. As with a protoboard, you build the circuit by wiring between the logic elements to produce the circuit you need. Fortunately, as with the circuit board, your tools allow you to use higher level circuit elements than just NAND gates. You can declare registers, flip-flops, adders, etc. Unlike the attached protoboard image, you cannot include capacitors or other analog circuit elements.
=

For FRC, the circuit produces the pulses for lots of PWMs, clocks I2C pins, decodes quadrature signals, accumulate the values returned from rate gyros, etc. The "circuit" could instead have been designed and "burned" into an ASIC I/O chip that was connected to the PPC's PCI bus. I suppose FIRST could alternately send a tub of TTL level logic and have you build your own I/O circuit on a very large protoboard. Instead, this circuit was programmed in the LV FPGA tools -- other FPGA tools could have been used. It is then compiled using the XILINX tools into an FPGA image, and "burned" by telling the RIO driver to upload the file to the FPGA chip.

Rather than dig deeper into what an FPGA is, or why the cRIO uses one in addition to running a realtime OS on a traditional CPU, let me reference an article on NI's website. LINK

FPGAs are a relatively new technology, but are already embedded in many devices where low-jitter, high performance, and flexible field-updates are required. The XILINX site can give examples other than the cRIO and its integrated I/O usage.

Greg McKaskle

Re: Cartesian to angle
 

Wait, the crio only has 64 MB of ram? ::rtm:: Yes, it does indeed. You learn something new every day I guess.

Re: Cartesian to angle
 

... and the new cRIO-FRC2 has 128 MB of RAM.

Re: Cartesian to angle
 

Thanks for the link Joe.

Using two fmadds instructions¹, at one cycle each², you can get arctangent(x) in the first octant accurate to +/- 0.25 degrees. Pretty tough to beat with a lookup table.

Wrap 3 compares, 1 divide, and 1 more add around that, and you've got atan2(y,x) accurate to +/- 0.25 degrees good for all four quadrants.



¹Para 3.2.4.2.2 Table 3-9

²Para 1.1

Re: Cartesian to angle
 

Just out of curiosity, would it be more beneficial for the algorithm to give angles in the range (0, 2pi], or [0, 2pi)? (Our team doesn't usually have to do much with angle conversions.) For getting angles in (0, 2pi], the method Dmentor suggested seems best; for the latter, something like pi - atan2(-x, y) seems like it would work.

Re: Cartesian to angle
 

Here's a simple C function CWYdeg(x,y) which returns an angle from 0 to 360 degrees measured clockwise from the +Y Cartesian axis when given Cartesian coordinates (x,y).

Using single-precision floats, the accuracy is better than +/-0.17 degree over the entire 0 to 360 range.

Using a similar technique, it is straightforward to create a function which returns angles either clockwise or counterclockwise, from the +X or -X or +Y or -Y axis, in the range 0 to 360 or -180 to +180 or 0 to 2pi or -pi to pi

Re: Cartesian to angle
 

I've refined the solution. I like these coefficients better:

a = -15.6526435831
b = 60.6626425889
c = -0.0049997982

Although the accuracy is ever so slightly less with these revised coefficients (+/-0.21 instead of +/-0.17 degrees), there is virtually no discontinuity (0.01 degree) at the octant boundaries.