OpenGL and FP accuracy in Trig

[deveraux]

Dear all,

I've been learning OpenGL on and off for a few years now, trying out different things. I've typically never really concerned myself with the inner workings of the library but more on just using it and playing with the results.

I finally decided to learn it properly so to speak, and got myself the Red Book and started studying from there. My question relates to something mentioned in the book when drawing circles whereby if you were to define all the relevant vectors/vertices in that circle using a loop to get the coordinates through sinf/cosf, you have to be careful when finally computing:

x = sinf(2.0f * M_PI * float(i) / float(EDGES))

Assuming i is the loop index and EDGES is the number of "divisions" you wish to have in that circle (e.g. EDGES = 36 means a circle has 36 unique points), when i = EDGES, the result will not be exactly 0.0f. It ultimately mentions that to prevent visual artifacts, to equate the final point and the first point, thereby avoiding any potential FP accuracy which is all fine and dandy. However, I am curious about the importance of including checks for the salient points whereby the result of a sine function would exactly equal 1.0f / -1.0f / 0.0f.

I've tried my best to explain this, though I'm not convinced I have to a sufficient degree. Eitherway, it is not a major issue, I am ultimately concerned with overdoing accuracy code that will slow down the loading portion for no real significant visual gains.

Thanks in advance for any help.

 

[Schmide]

If you use transcendentals or any complex math there is always going to be round off errors. Actually I don't believe you can truly draw a circle without errors as PI is irrational.

Edit: never mind you are using polar coordinates.

 

[Cogman]

Dear all,

I've been learning OpenGL on and off for a few years now, trying out different things. I've typically never really concerned myself with the inner workings of the library but more on just using it and playing with the results.

I finally decided to learn it properly so to speak, and got myself the Red Book and started studying from there. My question relates to something mentioned in the book when drawing circles whereby if you were to define all the relevant vectors/vertices in that circle using a loop to get the coordinates through sinf/cosf, you have to be careful when finally computing:

x = sinf(2.0f * M_PI * float(i) / float(EDGES))

Assuming i is the loop index and EDGES is the number of "divisions" you wish to have in that circle (e.g. EDGES = 36 means a circle has 36 unique points), when i = EDGES, the result will not be exactly 0.0f. It ultimately mentions that to prevent visual artifacts, to equate the final point and the first point, thereby avoiding any potential FP accuracy which is all fine and dandy. However, I am curious about the importance of including checks for the salient points whereby the result of a sine function would exactly equal 1.0f / -1.0f / 0.0f.

I've tried my best to explain this, though I'm not convinced I have to a sufficient degree. Eitherway, it is not a major issue, I am ultimately concerned with overdoing accuracy code that will slow down the loading portion for no real significant visual gains.

Thanks in advance for any help.

for exact values (ie, the corners of a cube) there shouldn't be any problem. you'll get the same point regardless of where that point is.

Generally, you shouldn't be performing a whole lot of trig functions on individual points, rather, you'll be doing the function on the initial identity matrix and then drawing your models.

It only becomes an issue when you start to try and do things like draw circles or spheres.

Either way, I wouldn't worry about it, it won't cause too many issues, and if it does, you'll know about it before hand. Some of those issues might be minimized by using doubles instead of floats

 

[eLiu]

I have no experience with graphics, so take this w/a grain of salt.

That said, one of the things that made Doom (or was it Quake) fast enough for hardware of the time was replacing sqrt by a very low order (linear, I believe) taylor series expansion. So if that is any measure, extreme accuracy is probably not a big deal. You're not solving some kind of ill-conditioned computational geometry problem.

That said, the above looks like C++. If you're using C++ or a language that follows the IEEE standard for floating point numbers, you should read up on how they work. Anyone working with numerical algorithms who is also concerned about precision should have a solid understanding of what a float/double can and cannot do.

Checking for exact floating point equality is generally not necessary unless there's something in particular you care about. Like avoiding division by 0, lol. That said, if your algorithm can divide by 0, you really should re-think it. Also, for sin/cos, generally sin(x) == 1.0 exactly for x = pi/2 +/- sqrt(eps), similarly around -1.0. You'll only get sin(x) == 0.0 exactly when x is 0 or denormal. (It is not a coincidence that sine is harder to compute near locations where its derivative is 0). Similar statement holds for cosine (though cos(pi/2) usually does not give 0.0 b/c the floating point representation of pi/2 is too distant from the exact value of pi/2).

Also, if you are concerned about speed, and this part of the code is taking a noticeable amount of time, there are a few things you can improve in your statement:
0) Make sure your program is being compiled with SSE2 enabled.
1) Don't cast. EDGES seems like some kind of #define macro. Set up a variable that's the floating point version of EDGES... like 100.0 instead of 100. i looks like a loop variable. Add an additional loop variable that's a float, like:
ifloat = 0.0f;
for(i=0; i<EDGES; i++, ifloat += 1.0f)
1b) Floating point literals are usually double by default. If you're using X87, conversion btwn double & float is free. If you're in SSE2, it isn't. You want to make sure then that you aren't mixing types. So it might be necessary to do something like "static const float MY_PI = 3.14159..." instead of using a macro.
2) This will tend to decrease accuracy, but 2.0*Pi/edges is invariant. Compute once & store.
3) flush denormalized numbers to 0. For graphics I doubt you'll need them. If you're on gcc, setting an option like "fast-math" would be good unless it causes issues. For intel, the equivalent is like, ftz, no-prec-div, no-prec-sqrt, fast-transcendentals.
4) If you have it, the intel "vector math libaries" perform standard math functions on vector (XMM) registers.

The compiler may or may not automatically handle the points in 1 and 2; this depends heavily on the compiler you're using and how strictly you instruct the compiler to follow the IEEE standard. Compilers are generally pretty cautious about floating point optimizations b/c it does typically change the answer, so it's best to perform optimizations you believe/know to be safe yourself.

 

[ILIKE3D]

You have to compute both x / y with cos / sin! buuuuuttt...

This kinda shit in your draw will cause you to drop frames pretty badly though the efficient way of plotting a circle would be generate the vertice structure and pass it back to a model struct then draw the circle 1 time with out any loops.

#define DIAMETER 1.0f
#define PI 3.1415926535897932

typedef struct
{
	unsigned short u, v;
	short x, y, z;
}
Vertex;

void *GenerateACircle(int DEGREES, float DIAMETER)
{
	void *vertices;
	vertices = (Vertex*) malloc(sizeof(Vertex* DEGREES));
	Vertex* ptr = (Vertex*)vertices;
	
	float i;
	for(i=0;i<360;i+=360.0f/DEGREES)
	{
		ptr[i].x=cos(i*PI/180)*DIAMETER+sin(i*PI/180)*DIAMETER, 
		ptr[i].y=cos(i*PI/180)*DIAMETER-sin(i*PI/180)*DIAMETER, 
		ptr[i].z=0.0f
	}
	
	return vertices;
	
}

void *ACirc = GenerateACircle(360, 1.0f);

then pass "ACirc" (with out quotations clearly) as a parameter for vertices in the function call you use to draw your mesh.

 

[iCyborg]

That said, one of the things that made Doom (or was it Quake) fast enough for hardware of the time was replacing sqrt by a very low order (linear, I believe) taylor series expansion. So if that is any measure, extreme accuracy is probably not a big deal. You're not solving some kind of ill-conditioned computational geometry problem.

If you're referring to the fast inverse square root trick, that was Quake 3, and it wasn't really about taylor series, but a trick where float was cast into an integer and some "magic" was used to get a good enough approximation. Specifically, there was a strange use of a hex constant 0x5f3759df which was really about exploiting some details of float point spec. It's quite amazing how someone developed it though, see wiki for "fast inverse square root".

The first time I heard about this is when some dev ran into performance related delays with the project, and said something like "it'll take some more time, it's not every day you run into 0x5f3759df", and then had to google the hex number to see wtf is he talking about...