🔒 Locked

C++ and integer math rounding quest.

Started by dawidjoubert Jul 1, 2006 at 6:50 AM 10 replies 1.1k views

Original Post

Jul 1, 2006 at 6:50 AM

Hi, I am working on a line algorithm that first clips the line to the screen and then renders it. For accuracy I am doing everything in Integer math (aka dy/dx is never resolved into a fraction) But I notice that C++ integer division doesn't round the answer. I dont need floating point accuracy because at the end of the day it is for pixel rendering and so 1.43 means no more to me than 1. But sometimes the correct answer (using algebra) is 1.998 and then the value stored in c++ is 1, is there any CHEAP way of getting rounding done? Regards and Thanks in Advance. Here is some of my code


	int deltaX = x2-x1;
	int deltaY = y2-y1;

	// The line equation is y = mx+c or
	// y = m1/m2 *x + c, now multiply m2 out
	// m2y = m1x + m2c
	// c = (m2y - m1x) / m2c
	// m1 = dy and m2 = dx

	// Find the C-Cut
	int c = (deltaX * y1 - deltaY * x1)/deltaX;

	// CLIP the line using the two x axeses
	int sx = x1;
	int ex = x2;
	if (sx < 0) sx = 0;
	if (ex >= g_iWidth) ex = g_iWidth-1;
	// Now we must find the corrosponding y values
	// y = mx+c
	int sy = (deltaY * sx)/deltaX + c;
	int ey = (deltaY * ex)/deltaX + c;

haegarr

Jul 1, 2006 at 7:01 AM

In FP one can add 0.5 to simulate a "round to nearest" when having only a "round to lower" (at least for positive values). So it may work for you if you do something like adding half of the divisor before doing the division:
a / b + 0.5 = a / b + 0.5 b / b = ( a + 0.5 b ) / b

Trap

Jul 1, 2006 at 7:27 AM

0.5 is a float, if you want integer math you should do something like that (haven't checked if it works for a<0 or b<0):

int res = a/b;if(a-b*res>=b/2) ++res;

int mod = a%b;int res = a/b;if(mod>=b/2) ++res;

joanusdmentia

Jul 1, 2006 at 7:43 AM

This'll work:

int div_rounded(int num, int den){    if((num<0)==(den>0)) return (num - den/2) / den;    return (num + den/2) / den;}

EDIT: Fixed for numerator and denominator having different signs, can't see an easy & portable way to get rid of the comparison though.

bubu LV

Jul 1, 2006 at 7:46 AM

int x = a/b; // rounds down, like floor
int x = (a + b/2)/b; // rounds to nearest
int x = (a + b-1)/b; // rounds up, like ceil

dawidjoubert

Jul 1, 2006 at 7:48 AM

Quote:
Original post by joanusdmentia
This'll work:
int div_rounded(int num, int den){    return (num + den/2) / den;}

Thanks yeah this wil work great. A quick test
round (10 / 6) = (10 + 6/2) / 6 = 13/6 = 2.1666 which in integer math becomes 2

And 10/6 = 1.66666, round 1.6666 to the nearest integer and you get 2. Thanks

dawidjoubert

Jul 1, 2006 at 7:59 AM

Quote:
Original post by bubu LV
int x = a/b; // rounds down, like floor
int x = (a + b/2)/b; // rounds to nearest
int x = (a + b-1)/b; // rounds up, like ceil

Second one and possible others work one for positive integers

I tried a way around this but felt the extra performance loss vs the gained accuracy is not worth it. Here is my modified version:

int div_rounded(int num, int den){	bool pos = ((num >= 0 ? 1 : 0) + (den >= 0 ? 1 : 0)) != 1 ? true : false;	num = abs(num);	den = abs(den);	return pos ? (num + den/2) / den : -(num + den/2) / den;}

joanusdmentia

Jul 1, 2006 at 8:40 AM

Quote:
Original post by dawidjoubert
Second one and possible others work one for positive integers

I tried a way around this but felt the extra performance loss vs the gained accuracy is not worth it. Here is my modified version:
*** Source Snippet Removed ***

Mine worked for both are +ve or -ve, but not when the signs differ. Take a look at it again as I've fixed it, but I wasn't able to figure out a way to do it without the branch.

iMalc

Jul 1, 2006 at 4:38 PM

Quote:

	int c = (deltaX * y1 - deltaY * x1)/deltaX;	// CLIP the line using the two x axeses	int sx = x1;	int ex = x2;	if (sx < 0) sx = 0;	if (ex >= g_iWidth) ex = g_iWidth-1;	// Now we must find the corrosponding y values	// y = mx+c	int sy = (deltaY * sx)/deltaX + c;	int ey = (deltaY * ex)/deltaX + c;

c, sy, and ey are both being divided by deltaX, but sy & ey also use c. So, I wonder if you could also increase accuracy by doing something like:

	// CLIP the line using the two x axeses	int sx = x1;	int ex = x2;	if (sx < 0) sx = 0;	if (ex >= g_iWidth) ex = g_iWidth-1;	int cDeltaX = (deltaX * y1 - deltaY * x1);	int sy = (deltaY * sx + cDeltaX)/deltaX;	int ey = (deltaY * ex + cDeltaX)/deltaX;

or taking that furthur by expanding cDeltaX, and then grouping like terms:

	int sy = (deltaY * (sx - x1) + deltaX * y1)/deltaX;	int ey = (deltaY * (ex - x1) + deltaX * y1)/deltaX;

Which you can simplify furthur to:

	int sy = (deltaY * (sx - x1))/deltaX + y1;	int ey = (deltaY * (ex - x1))/deltaX + y1;

Now add your deltaX/2 rounding factor before doing the divide.
Does all that help also? It's simpler, more accurate, and faster.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.