Help: Floating Point PRoblem
in [MFC]
|
Prev: How to limit a dialog's width while dragging the edge?
Next: capture magnetic stripe input invisibly
From: Somebody on 18 May 2008 00:14 I have a GUI something like this: <column splitter> <data> < column splitter> < data > etc. Each column has a vertical splitter where the user can adjust the columns. One of the requirements was that when the user sizes the app, the columns should scale accordingly. For example... say the app was 100 pixels wide and column A was at 25, column B at 50 and column C at 75... if the app got resized to 200 pixels wide, column A would now be at 50, B at 100 and C at 150. Since a column could be divided arbitrarily by the user (horizontally and vertically), we implemented a tree structure that would hold all this information. We used an "int nRatio" design. So for example, an even split, the left node would get a nRatio=50 and the right node would get a nRatio=50. As we went along with the implementation, we found that we would get the splitters jumping around by a few pixels here and there. Debugging showed round off errors with our division. So we changed "int nRatio" to "float fRatio". That improved a bit, but we would still get cases where the splitters jumped around by a few pixels, so we tried "double dRatio". Still same problem. Finally, we ended up multiplying the numerator by 10,000 to get more decimal precision. That seemed to work, but then we got a bug opened where in following example: A | B | C | D moving splitter A|B or B|C would cause splitters to the right to move. Think about it: A|B was 50%, B|C was 50%, C|D was 50%... so moving A|B without adjusting the ratios for B|C and C|D would cause them to scale as if the app was being resized :(. We came up with a solution where if I moved A|B, we would recalculate the ratios for the other splitters to keep "rectSplitter" in the same place... Oops... you guessed it, round off errors popped up, even with it multiplied by 10,000. Our whole layout algorithms work based on this "left node gets 50%, right node gets 50%" concept, so changing to something else might be a huge re-write. I understand that I can not have "fractional" pixels though. We need to somehow recalculate the ratios because we can't layout by saying "make the splitter appear at x,y" since as I said, its based around this ratio calculations. We could try bumping up our multiplier to something bigger then 10,000 like 100,000 or 1,000,000, but I'm concerned we'll always get round off errors. Any ideas?
From: Joseph M. Newcomer on 18 May 2008 00:35 See below... On Sat, 17 May 2008 21:14:51 -0700, "Somebody" <somebody(a)cox.net> wrote: >I have a GUI something like this: > ><column splitter> <data> < column splitter> < data > etc. > >Each column has a vertical splitter where the user can adjust the columns. > >One of the requirements was that when the user sizes the app, the columns >should scale accordingly. > >For example... say the app was 100 pixels wide and column A was at 25, >column B at 50 and column C at 75... if the app got resized to 200 pixels >wide, column A would now be at 50, B at 100 and C at 150. > >Since a column could be divided arbitrarily by the user (horizontally and >vertically), we implemented a tree structure that would hold all this >information. We used an "int nRatio" design. So for example, an even split, >the left node would get a nRatio=50 and the right node would get a >nRatio=50. > >As we went along with the implementation, we found that we would get the >splitters jumping around by a few pixels here and there. Debugging showed >round off errors with our division. So we changed "int nRatio" to "float >fRatio". That improved a bit, but we would still get cases where the >splitters jumped around by a few pixels, so we tried "double dRatio". Still >same problem. Finally, we ended up multiplying the numerator by 10,000 to >get more decimal precision. **** Yes, this is typical of using integers. Double will not change the phenomenon, because you are essentially working at about 1 decimal place, and going from 8 to 15 decimal places isn't going to fix your problem. Key here is that you need to keep the ratios strictly as percentages. If you are using uniform spacing, this is easy. Otherwise, when the user resizes, you need to compute the ratios of the column size to client area size, for example 0.25, 0.50, 0.25 (if the user wants a wide column in the middle). Then you will always resize based on these ratios and the client area. If the user resizes the columns (changes their ratio, adds columns, etc.) then you compute new ratios. But at no point do you remember column sizes in pixels, only in percentages. Otherwise, your use of flating point has created no real additional precision. **** > >That seemed to work, but then we got a bug opened where in following >example: > >A | B | C | D > >moving splitter A|B or B|C would cause splitters to the right to move. Think >about it: A|B was 50%, B|C was 50%, C|D was 50%... so moving A|B without >adjusting the ratios for B|C and C|D would cause them to scale as if the app >was being resized :(. **** You are confusing relative widths with absolute widths. You need to compute the position from the left margin, and round THAT value to a pixel position. If you round to pixels and add the pixels, you're back doing integer arithmetic. So if the widths are 0.25, 0.50, 0.25 then the first width would be 0.25*client.Width(), the second width would be 0.75 * client.Width() - 0.25 * client.Width(), and the third width would be 1.00 * client.Width() - (0.75 * client.Width()). Otherwise, the "jumping" you are seeing is an expected phenomenon, caused by roundoff when you compute the x position of the right of the column as based on the computation in floating point plus the x position of the left of the column (because truncation or rounding would change the left edge +/- 1 pixel, and this error would then accumulate across the columns). You should expect, and cannot prevent, +/- 1 pixel errors, the trick is to keep them from being cumulative. **** > >We came up with a solution where if I moved A|B, we would recalculate the >ratios for the other splitters to keep "rectSplitter" in the same place... > >Oops... you guessed it, round off errors popped up, even with it multiplied >by 10,000. > >Our whole layout algorithms work based on this "left node gets 50%, right >node gets 50%" concept, so changing to something else might be a huge >re-write. **** Well, as soon as you convert to pixels, you lose precision, so as you move up the tree, the 1-pixel errors accumulate. You have to propagate positions in floating point upwards, and don't do roundoff until final rendering. Remember that every time you have an odd number of pixels involved, one of the computations will always be off-by-1 if you truncate or round (it doesn't matter which). **** > >I understand that I can not have "fractional" pixels though. We need to >somehow recalculate the ratios because we can't layout by saying "make the >splitter appear at x,y" since as I said, its based around this ratio >calculations. **** Yes, you keep fractional pixels in your tree; only when you go to render them will you truncate or round to integers. This way, errors do not accumulate as you move up the tree, and your maximum error will be +/- 1 pixel. You could provide some heuristic based on tree depth to decide whether to truncate or round, or something like that, but I think the problem is just cumulative roundoff errors. **** > >We could try bumping up our multiplier to something bigger then 10,000 like >100,000 or 1,000,000, but I'm concerned we'll always get round off errors. **** You will always get roundoff errors. The trick is to keep them from being cumulative. So if two columns end up at 38 1/4 pixels wide, it doesn't matter; they will both be 38, but there's a 1/2-pixel width that propagates upward. Eventually, these will cancel out. I had problems like this in PostScript layout until I understood how to avoid cumulative pixel errors. joe **** > >Any ideas? > Joseph M. Newcomer [MVP] email: newcomer(a)flounder.com Web: http://www.flounder.com MVP Tips: http://www.flounder.com/mvp_tips.htm
From: Somebody on 18 May 2008 00:58 Thanks for the feedback Joe... Unfortunately, I can not calculate from the top/left corner because there is no such concept in my UI. A "cell" knows nothing about its surrounding cells, or where its located, etc. The concept is: start with rect A split rect A horizontally OR vertically by x% to form rects A/B split rect B horizontally OR vertically by x% to form rects B/C etc. Ie... a rect can only be split once in a single direction, but I can split the split rectangles to form nested cells. So in the above example: start with rect A split rect A horizontally by 50% to form rects A/B split rect B horizontally by 50% to form rects B/C So now... A|B's ratio is 50%, but so is B|C because its a recursive thing: root is 100 pixels wide A gets 50% of that... A's right node which is B|C gets 50% B gets 50% of what A passed down (essentially 25% of the full width) and C gets the other 50%... The problem occurs if say, I move to pixel x = 100 and the width is 300. By storing the ratio, I'll *never* recover 100 exactly. So I'm thinking, instead of storing the ratio as a float, why not store the numerator and denomenator as ints? 100 / 300 = 0.33 ..33 * 300 = 99 (OFF BY 1 PIXEL) BUT... 100 * 300 / 300 = 100 (exact)... Sound like a reasonable idea? "Joseph M. Newcomer" <newcomer(a)flounder.com> wrote in message news:gibv2411fcurfaugkmod3gmi3sbcitj2dq(a)4ax.com... > See below... > On Sat, 17 May 2008 21:14:51 -0700, "Somebody" <somebody(a)cox.net> wrote: > >>I have a GUI something like this: >> >><column splitter> <data> < column splitter> < data > etc. >> >>Each column has a vertical splitter where the user can adjust the columns. >> >>One of the requirements was that when the user sizes the app, the columns >>should scale accordingly. >> >>For example... say the app was 100 pixels wide and column A was at 25, >>column B at 50 and column C at 75... if the app got resized to 200 pixels >>wide, column A would now be at 50, B at 100 and C at 150. >> >>Since a column could be divided arbitrarily by the user (horizontally and >>vertically), we implemented a tree structure that would hold all this >>information. We used an "int nRatio" design. So for example, an even >>split, >>the left node would get a nRatio=50 and the right node would get a >>nRatio=50. >> >>As we went along with the implementation, we found that we would get the >>splitters jumping around by a few pixels here and there. Debugging showed >>round off errors with our division. So we changed "int nRatio" to "float >>fRatio". That improved a bit, but we would still get cases where the >>splitters jumped around by a few pixels, so we tried "double dRatio". >>Still >>same problem. Finally, we ended up multiplying the numerator by 10,000 to >>get more decimal precision. > **** > Yes, this is typical of using integers. Double will not change the > phenomenon, because > you are essentially working at about 1 decimal place, and going from 8 to > 15 decimal > places isn't going to fix your problem. > > Key here is that you need to keep the ratios strictly as percentages. If > you are using > uniform spacing, this is easy. Otherwise, when the user resizes, you need > to compute the > ratios of the column size to client area size, for example 0.25, 0.50, > 0.25 (if the user > wants a wide column in the middle). Then you will always resize based on > these ratios and > the client area. If the user resizes the columns (changes their ratio, > adds columns, > etc.) then you compute new ratios. But at no point do you remember column > sizes in > pixels, only in percentages. Otherwise, your use of flating point has > created no real > additional precision. > **** >> >>That seemed to work, but then we got a bug opened where in following >>example: >> >>A | B | C | D >> >>moving splitter A|B or B|C would cause splitters to the right to move. >>Think >>about it: A|B was 50%, B|C was 50%, C|D was 50%... so moving A|B without >>adjusting the ratios for B|C and C|D would cause them to scale as if the >>app >>was being resized :(. > **** > You are confusing relative widths with absolute widths. You need to > compute the position > from the left margin, and round THAT value to a pixel position. If you > round to pixels > and add the pixels, you're back doing integer arithmetic. So if the > widths are > > 0.25, 0.50, 0.25 > > then the first width would be 0.25*client.Width(), the second width would > be > 0.75 * client.Width() - 0.25 * client.Width(), and the third width would > be 1.00 * > client.Width() - (0.75 * client.Width()). Otherwise, the "jumping" you > are seeing is an > expected phenomenon, caused by roundoff when you compute the x position of > the right of > the column as based on the computation in floating point plus the x > position of the left > of the column (because truncation or rounding would change the left edge > +/- 1 pixel, and > this error would then accumulate across the columns). You should expect, > and cannot > prevent, +/- 1 pixel errors, the trick is to keep them from being > cumulative. > **** >> >>We came up with a solution where if I moved A|B, we would recalculate the >>ratios for the other splitters to keep "rectSplitter" in the same place... >> >>Oops... you guessed it, round off errors popped up, even with it >>multiplied >>by 10,000. >> >>Our whole layout algorithms work based on this "left node gets 50%, right >>node gets 50%" concept, so changing to something else might be a huge >>re-write. > **** > Well, as soon as you convert to pixels, you lose precision, so as you move > up the tree, > the 1-pixel errors accumulate. You have to propagate positions in > floating point upwards, > and don't do roundoff until final rendering. Remember that every time you > have an odd > number of pixels involved, one of the computations will always be off-by-1 > if you truncate > or round (it doesn't matter which). > **** >> >>I understand that I can not have "fractional" pixels though. We need to >>somehow recalculate the ratios because we can't layout by saying "make the >>splitter appear at x,y" since as I said, its based around this ratio >>calculations. > **** > Yes, you keep fractional pixels in your tree; only when you go to render > them will you > truncate or round to integers. This way, errors do not accumulate as you > move up the > tree, and your maximum error will be +/- 1 pixel. You could provide some > heuristic based > on tree depth to decide whether to truncate or round, or something like > that, but I think > the problem is just cumulative roundoff errors. > **** >> >>We could try bumping up our multiplier to something bigger then 10,000 >>like >>100,000 or 1,000,000, but I'm concerned we'll always get round off errors. > **** > You will always get roundoff errors. The trick is to keep them from being > cumulative. So > if two columns end up at 38 1/4 pixels wide, it doesn't matter; they will > both be 38, but > there's a 1/2-pixel width that propagates upward. Eventually, these will > cancel out. > > I had problems like this in PostScript layout until I understood how to > avoid cumulative > pixel errors. > joe > **** >> >>Any ideas? >> > Joseph M. Newcomer [MVP] > email: newcomer(a)flounder.com > Web: http://www.flounder.com > MVP Tips: http://www.flounder.com/mvp_tips.htm
From: Joseph M. Newcomer on 18 May 2008 04:40 In order to draw anything on the screen, you need to have the coordinates. So you must have some way to get this information. But if you have to keep doing relative computations, the cumulative roundoff is going to get you. What you need to pass down is not pixel sizes, but the pair <total size, percentage factor> the key here is that you must not convert to pixels until the latest possible time; each time you pass down a pixel size, you introduce the possibility that you will get a roundoff error that will cause exactly the kinds of errors you are seeing. Yes, an alternative to floating point is rational arithmetic, but it introduces the same problem, which is that you have to pass the values down all the way. joe On Sat, 17 May 2008 21:58:50 -0700, "Somebody" <somebody(a)cox.net> wrote: >Thanks for the feedback Joe... > >Unfortunately, I can not calculate from the top/left corner because there is >no such concept in my UI. A "cell" knows nothing about its surrounding >cells, or where its located, etc. > >The concept is: > >start with rect A >split rect A horizontally OR vertically by x% to form rects A/B >split rect B horizontally OR vertically by x% to form rects B/C >etc. > >Ie... a rect can only be split once in a single direction, but I can split >the split rectangles to form nested cells. > >So in the above example: > >start with rect A >split rect A horizontally by 50% to form rects A/B >split rect B horizontally by 50% to form rects B/C > >So now... A|B's ratio is 50%, but so is B|C because its a recursive thing: > >root is 100 pixels wide >A gets 50% of that... A's right node which is B|C gets 50% >B gets 50% of what A passed down (essentially 25% of the full width) and C >gets the other 50%... > >The problem occurs if say, I move to pixel x = 100 and the width is 300. By >storing the ratio, I'll *never* recover 100 exactly. > >So I'm thinking, instead of storing the ratio as a float, why not store the >numerator and denomenator as ints? > >100 / 300 = 0.33 >.33 * 300 = 99 (OFF BY 1 PIXEL) > >BUT... > >100 * 300 / 300 = 100 (exact)... > >Sound like a reasonable idea? > >"Joseph M. Newcomer" <newcomer(a)flounder.com> wrote in message >news:gibv2411fcurfaugkmod3gmi3sbcitj2dq(a)4ax.com... >> See below... >> On Sat, 17 May 2008 21:14:51 -0700, "Somebody" <somebody(a)cox.net> wrote: >> >>>I have a GUI something like this: >>> >>><column splitter> <data> < column splitter> < data > etc. >>> >>>Each column has a vertical splitter where the user can adjust the columns. >>> >>>One of the requirements was that when the user sizes the app, the columns >>>should scale accordingly. >>> >>>For example... say the app was 100 pixels wide and column A was at 25, >>>column B at 50 and column C at 75... if the app got resized to 200 pixels >>>wide, column A would now be at 50, B at 100 and C at 150. >>> >>>Since a column could be divided arbitrarily by the user (horizontally and >>>vertically), we implemented a tree structure that would hold all this >>>information. We used an "int nRatio" design. So for example, an even >>>split, >>>the left node would get a nRatio=50 and the right node would get a >>>nRatio=50. >>> >>>As we went along with the implementation, we found that we would get the >>>splitters jumping around by a few pixels here and there. Debugging showed >>>round off errors with our division. So we changed "int nRatio" to "float >>>fRatio". That improved a bit, but we would still get cases where the >>>splitters jumped around by a few pixels, so we tried "double dRatio". >>>Still >>>same problem. Finally, we ended up multiplying the numerator by 10,000 to >>>get more decimal precision. >> **** >> Yes, this is typical of using integers. Double will not change the >> phenomenon, because >> you are essentially working at about 1 decimal place, and going from 8 to >> 15 decimal >> places isn't going to fix your problem. >> >> Key here is that you need to keep the ratios strictly as percentages. If >> you are using >> uniform spacing, this is easy. Otherwise, when the user resizes, you need >> to compute the >> ratios of the column size to client area size, for example 0.25, 0.50, >> 0.25 (if the user >> wants a wide column in the middle). Then you will always resize based on >> these ratios and >> the client area. If the user resizes the columns (changes their ratio, >> adds columns, >> etc.) then you compute new ratios. But at no point do you remember column >> sizes in >> pixels, only in percentages. Otherwise, your use of flating point has >> created no real >> additional precision. >> **** >>> >>>That seemed to work, but then we got a bug opened where in following >>>example: >>> >>>A | B | C | D >>> >>>moving splitter A|B or B|C would cause splitters to the right to move. >>>Think >>>about it: A|B was 50%, B|C was 50%, C|D was 50%... so moving A|B without >>>adjusting the ratios for B|C and C|D would cause them to scale as if the >>>app >>>was being resized :(. >> **** >> You are confusing relative widths with absolute widths. You need to >> compute the position >> from the left margin, and round THAT value to a pixel position. If you >> round to pixels >> and add the pixels, you're back doing integer arithmetic. So if the >> widths are >> >> 0.25, 0.50, 0.25 >> >> then the first width would be 0.25*client.Width(), the second width would >> be >> 0.75 * client.Width() - 0.25 * client.Width(), and the third width would >> be 1.00 * >> client.Width() - (0.75 * client.Width()). Otherwise, the "jumping" you >> are seeing is an >> expected phenomenon, caused by roundoff when you compute the x position of >> the right of >> the column as based on the computation in floating point plus the x >> position of the left >> of the column (because truncation or rounding would change the left edge >> +/- 1 pixel, and >> this error would then accumulate across the columns). You should expect, >> and cannot >> prevent, +/- 1 pixel errors, the trick is to keep them from being >> cumulative. >> **** >>> >>>We came up with a solution where if I moved A|B, we would recalculate the >>>ratios for the other splitters to keep "rectSplitter" in the same place... >>> >>>Oops... you guessed it, round off errors popped up, even with it >>>multiplied >>>by 10,000. >>> >>>Our whole layout algorithms work based on this "left node gets 50%, right >>>node gets 50%" concept, so changing to something else might be a huge >>>re-write. >> **** >> Well, as soon as you convert to pixels, you lose precision, so as you move >> up the tree, >> the 1-pixel errors accumulate. You have to propagate positions in >> floating point upwards, >> and don't do roundoff until final rendering. Remember that every time you >> have an odd >> number of pixels involved, one of the computations will always be off-by-1 >> if you truncate >> or round (it doesn't matter which). >> **** >>> >>>I understand that I can not have "fractional" pixels though. We need to >>>somehow recalculate the ratios because we can't layout by saying "make the >>>splitter appear at x,y" since as I said, its based around this ratio >>>calculations. >> **** >> Yes, you keep fractional pixels in your tree; only when you go to render >> them will you >> truncate or round to integers. This way, errors do not accumulate as you >> move up the >> tree, and your maximum error will be +/- 1 pixel. You could provide some >> heuristic based >> on tree depth to decide whether to truncate or round, or something like >> that, but I think >> the problem is just cumulative roundoff errors. >> **** >>> >>>We could try bumping up our multiplier to something bigger then 10,000 >>>like >>>100,000 or 1,000,000, but I'm concerned we'll always get round off errors. >> **** >> You will always get roundoff errors. The trick is to keep them from being >> cumulative. So >> if two columns end up at 38 1/4 pixels wide, it doesn't matter; they will >> both be 38, but >> there's a 1/2-pixel width that propagates upward. Eventually, these will >> cancel out. >> >> I had problems like this in PostScript layout until I understood how to >> avoid cumulative >> pixel errors. >> joe >> **** >>> >>>Any ideas? >>> >> Joseph M. Newcomer [MVP] >> email: newcomer(a)flounder.com >> Web: http://www.flounder.com >> MVP Tips: http://www.flounder.com/mvp_tips.htm > Joseph M. Newcomer [MVP] email: newcomer(a)flounder.com Web: http://www.flounder.com MVP Tips: http://www.flounder.com/mvp_tips.htm
From: Alexander Grigoriev on 18 May 2008 09:45
"Joseph M. Newcomer" <newcomer(a)flounder.com> wrote in message news:gibv2411fcurfaugkmod3gmi3sbcitj2dq(a)4ax.com... > See below... > Key here is that you need to keep the ratios strictly as percentages. If > you are using > uniform spacing, this is easy. Otherwise, when the user resizes, you need > to compute the > ratios of the column size to client area size, for example 0.25, 0.50, > 0.25 (if the user > wants a wide column in the middle). Then you will always resize based on > these ratios and > the client area. If the user resizes the columns (changes their ratio, > adds columns, > etc.) then you compute new ratios. But at no point do you remember column > sizes in > pixels, only in percentages. Otherwise, your use of flating point has > created no real > additional precision. > **** I suggest the other way around. The ratios are always kept as "ratios". You keep integer table that corresponds to column sizes, like: 100, 50, 100; one per column or group of columns of equal width. These are not pixels. When an user resizes a column, you replace the table with new column widths in pixels. This will guarantee that any recalculation will leave other columns unchanged. When an user resizes the whole window, you calculate new column widths based on ratios between these, but the table doesn't change. MulDiv function is very handy in all these calculations. Make sure to handle zero window width correctly, though. As you may guess, when you resize the window width, the splitters may move at different rate, sometimes one splitter moves by a pixel and another stays, and the other way around. This is normal, because a splitter cannot move half pixel. As long as you keep the ratios, it guarantees that your layout won't creep. |