Igor and I have been discus= sing pcb geometry kernel design, I'm ccing the list in case anyone has = strong opinions.

[snip]

<= /div>

Question is: should a big geometry refactoring fix old bugs or questionalbe= numeric conversions or just do the same thing with different code org?

For all the time, I assumed the first.

= I agree, but we may have different ideas of what the fix would be.=C2=A0 If= you want to stop using floating point entirely, it's a huge effort, an= d ints won't do what you want either, you need rationals.=C2=A0 If by f= ix you mean acknowlege intrinsic issues like https://bugs.launchpad.net/pcb/= +bug/1013358

and explain how users can avoid them, that's= what I think would be good.=C2=A0 So then it just becomes a matter of wher= e you actually put the=C2=A0

conversions.=C2=A0 At the boundary o= f an all-floating point math kernel is one logical place...

I use pcb-rnd, which I forked from an older PCB code. That code already had= support for 32 and 64 bit coords and had the nanometer conversion. The max= imum board size the preferences window permits is about 1073*1073 mm. I jus= t made a board of 1000*1000 mm. Zoom went crazy: can't draw on the shee= t at all.

I suspect this one is already fxed in later versions of mainline, but to me= , this suggests the original easy approach on floats and ints is just not= =C2=A0

good enough. Question is whether you w= ant a lib that attempts to centralize the fix for such bugs, or you want a = lib that does the low level

It s= till does it.=C2=A0 This is probably related to the widget and/or window co= ordinates (type int IIRC), which is a different layer from the coordinate g= rid.

Probably the conversion calculation overflows at = some intermediate point, which could be fixed.=C2=A0 In the meantime we cou= ld limit board size to 400mm square (which works, 500mm doesn't).=C2=A0=

calculations and fix these sort of e= rrors everywhere in the code after switching over to the lib. If it was me,= I'd go for centralizing the fix.

<snip>

=C2=A0 =C2=A0 =C2=A0Btw, what's the case where detectig identical cente= rs is
=C2=A0 =C2=A0 =C2=A0impossible in geometry.[ch] because of the API?

Well if you use floating point, comparing the center coordinates for
equality is something of a no-no.=C2=A0 You would want an epsilon value ins= tead.

And tha't sthe tricky part: what's a good epsilon? See later.

It makes sense besides the taboo factor, since almost-identical centers are=
likely to lead to underflow in the subsequent arc intersection
calculations.=C2=A0 Epsilon values and handling are another example of some= thing

Note: we do the same with integer coords: you simply can't put somethin= in between two nanometers, and we say epsilon is 1 nanometer (no matter ho= w big your board is).=C2=A0

you could put into geometry.h, or not, depending on how aggressive you want=
to be about encapsulating things in there.=C2=A0 But note that in the case = of
pcb, it would be useless to put them in, because you probably just want to<= br> check for identical coordinates in integer-land instead.=C2=A0 In trying to= allow

And this was exactly my point: if the lib knows the coord format is integer= , an "are_these_points_the_same()" can do the right thing: compar= e integers.=C2=A0 Yes, this is a bunch of #ifdefs. This makes the library l= ook ugly. I have a many such libraries in other domains, where my explicit = goal is to collect all such ugliness in a module and hide it behind an API.=

Rationale: there are two problmes here. One is the low level problem, the &= quot;how": e.g. how do we calculate intersection of two objects. The o= ther one is the high level problem, the "why": e.g. the drc decid= es which objects to bloat and compare for intersection (=3D=3D why to run t= he low level function to calculate the intersection of two objects). My exp= erience is that the real hard part in long term maintaining a complex proje= ct is in the high level part. Thus I tend to prefer moving the ugliness int= o the low level part that is much easer to take away to a test bench and ma= ke tests on.

Hmm.=C2=A0 I had intended = the geometry.h as a sort of portable source library, without any encapsulat= ed pcb-specific decisions.=C2=A0 As it happens I already have pcb_geometry.= h as well which does some adaptation.=C2=A0 Perhaps the latter just needs t= o grow a bit, at which point our ideas of how to handle this are probably a= bout the same.

=C2=A0

[snip]

<= /div>

Well, I think it's possible to do:

=C2=A0- consistent integer-only high and low level

=C2=A0- consistent float-only high and low level

=C2=A0- integer high level with consistent conversions to a float low level=

This is in effect what we h= ave now, and changing it seems unrealistic.=C2=A0 The question is how to do= it.

=C2=A0

=C2=A0- and mixed integer and float levels with careless conversions (which=
=C2=A0 =C2=A0was, I believe, the case with pcb before geometry.h)=C2=A0

However, before you decide, there is a fine-print about floats. (You probab= ly well aware of this, so sorry if I repeat the obvious.)

Floats may look better than ints because they seemingly solve all these unp= leasant problems about rounding and being precise with the "just use a= n epsilon and don't trust LSB bits too much". However, if we step = back and look at integers and floats from a more theoretical perspective...= What's ur problem with fixed point integers (like the nanometers PCB h= as now)? That calculations go nasty with small values, because we can not r= epresent intermediate results that fall between two numbers we have ion our= set, that is, between two integers.

So let's go float! But wait: float has the very same problem: it has a = finite stepping between its numbers as well. What's worse, unlike with = (fixed point) integers, this stepping keep on changing with the magnitue of= the value! Try this in C: float f =3D 100000000; printf with %.12f; then f= =3Df+1.0; printf again. This trick works with 1000000 and +0.1, 100000+0.01= , etc. (Actually shouldn't do it in decimal).

=
I believe I know what you mean here.=C2=A0 If you had= to summarize the consequences, you might say that although ints may get in= accurate for small numbers, floats (at least of the same size) will do so f= or big ones, and you can't say which is worse in general.=C2=A0 As it h= appens, for pcb screwing up the big numbers is probably worse.
= =C2=A0
This has many consequences. I claim: as many as fixed point int's "= ;what happens with small numbers" has. An obvious one is that you can&= #39;t always go with a single fixed epsilon for coords, but epsilon needs t= o be scaled with the magnitude of the coord. This is not obvious for coord =

Here's one attempt at a gen= eral approach to this problem:

http://www.gnu.org/software/gsl/manual/html_node/Approxima= te-Comparison-of-Floating-Point-Numbers.html#Approximate-Comparison-of-Floa= ting-Point-Numbers
=C2=A0
compariso= n (there a small epsilon works for the large cases). But if you ever want t= o make a coord loop=C2=A0 or want to find the "next valid coord to the= right" (for bloating or whatever), you can't avoid this nasty que= siton. This even means if your board is large enough, DRC will miss errors = because bloating things by 10 units there result in the same object you sta= rted from!

Just using doubles or long doubles or "something even wider" does= n't solve this. What solves this is careful programming - and this, I b= elieve, can not be avoided, whichever type combination you pick.

I'm not sure about this.=C2=A0 A w= ider float type can actually represent everything in a narrower int type.= =C2=A0 Consider:

=C2=A0 =C2=A0 =C2=A0#i= nclude <float.h>
=C2=A0 =C2=A0 =C2=A0#include <stdint.h&= gt;
=C2=A0 =C2=A0 =C2=A0#include <math.h>
=C2=A0 = =C2=A0 =C2=A0#include <stdio.h>
=C2=A0=C2=A0
=C2= =A0 =C2=A0 =C2=A0int
=C2=A0 =C2=A0 =C2=A0main (void)
= =C2=A0 =C2=A0 =C2=A0{
=C2=A0 =C2=A0 =C2=A0 =C2=A0printf (
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 "INT32_MAX: =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0%i\n&= quot;, INT32_MAX);

=C2=A0 =C2=A0 =C2=A0 =C2=A0printf (

= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0"pow (FLT_RADIX, DBL_MANT_DIG= ) - 1: =C2=A0%f\n",

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0pow (FLT_RADIX, DBL_MANT_DIG) - 1 );

=C2=A0 =C2=A0 =C2=A0 =C2= =A0printf (

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0"pow (F= LT_RADIX, DBL_MANT_DIG): =C2=A0 =C2=A0 =C2=A0%f\n",

=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0pow (FLT_RADIX, DBL_MANT_DIG) );

=C2=A0 =C2=A0 =C2=A0 =C2=A0printf (

=C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0"pow (FLT_RADIX, DBL_MANT_DIG) + 1: =C2=A0%f\n",

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0pow (FLT_RADIX, DBL_MANT_D= IG) + 1 );

=C2=A0 =C2=A0 =C2=A0 =C2=A0return 0;

=C2=A0 =C2=A0 =C2=A0}

which gives:
=

=C2=A0 =C2=A0 =C2=A0 $= gcc --std=3Dc11 -Wall -Wextra -Werror text.c=C2=A0

=C2=A0 =C2=A0= =C2=A0 $ ./a.out=C2=A0

=C2=A0 =C2=A0 = =C2=A0 INT32_MAX: =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A02147483647

=C2=A0 =C2=A0 =C2=A0= pow (FLT_RADIX, DBL_MANT_DIG) - 1: =C2=A09007199254740991.000000

= =C2=A0 =C2=A0 =C2=A0pow (FLT_RADIX, DBL_MANT_DIG): =C2=A0 =C2=A0 =C2=A09007= 199254740992.000000

=C2=A0 =C2=A0 =C2=A0pow (FLT_RADIX, DBL_MANT_= DIG) + 1: =C2=A09007199254740992.000000

=C2=A0 =C2=A0 =C2=A0$=C2= =A0

The largest double to which y= ou can count "by ones" is much greater than INT32_MAX.

My conclusion:

00. all the below problems will be present. You absolutely can not suppress= or overcome or work around them. The only questions are where you deal wit= h them (caller or callee) and which pain you choose.

0. in any case you need to be careful how to pick the widths of the interna= l calculation type and the API type (or alternatively, how you scale betwee= n the two).

Yes, the relatio= nship must be such that e.g.=C2=A0pow (FLT_RADIX, DBL_MANT_DIG) > INT32_= MAX (or whatever largest coord you want to handle), or else you have to wor= ry about the exact consequences for every case (impractical).

=C2= =A0

1. if you do an int-int, you have to be very careful what to do with small = numbers; have to detect the cases and do extra moves to make it work. If yo= u make a mistake, it's likely to be recognized with real-life sized boa= rds and real-life requirements on precision/resolution

Yes.

=C2=A0

2. if you do an int-float, you have to be very careful how you make the con= version forth and back, each time you need to do the conversion. If you mak= e a mistake, it's likely to be detected only in corners (=3D=3D harder = to find the bugs than in 1.)

My claim on this is that if your float type entirely contains the set of y= our int type, there's no doubt about how the conversion in one directio= n should work.=C2=A0 I agree that when you round a result to snap back to t= he int grid there's no escaping thinking about which way you should rou= nd given the context, which is why a general rounding policy might not work= .=C2=A0 On the other hand giving up automatic rounding for correctness on t= hat last 1 nm might be insane.=C2=A0 If your overall design depends on that= you have problems anyway.=C2=A0 For example pcb, should probably be honest= and somehow tell the user that setting DRC clearance, line width, and grid= size all the same is more or less guaranteed to blow up, despite the theor= etical correctness.

=C2=A0

3. you do a float-float, so there's no conversion; due to the stepping = mentioned above, your code will very soon work on small boords and common p= recision. If you made mistakes, they will be very hard to detect as not onl= y corner cases you need, but also very big and/or very small values too. To= me, this means bugs are much harder to find here than in 2.

In short: using floats won't solve your problem, just hide them. Been t= here, done that. This why we designed so many gemoetric tasks to be specifi= ed with integers at challenge24 (http://ch24.org): we figured carefully using int= egers yield much less hard-to-handle special cases than just using scaled u= p ints. I suspect PCB programmers had a similar conclusion when settling wi= th integers.

Thus I am not saying PCB must use integers. I merely claim that whichever w= ay you chose will require about the same amount of cruft, and that chosing = floats _in order to_ avoid the cruft totally might be a mistake.

You could very well be right.=C2=A0 If we = had some math library that avoided floats entirely it might be good.=C2=A0 = But the reality is we're using them, one way or another, and it's a= question of how to handle the conversions involved.=C2=A0 I'm fairly c= ertain now that mixing ints and floats in the kernel itself is a mistake.= =C2=A0 What I'm not sure about is whether it's worth adding a layer= that implements a general rounding and comparison policy for pcb, or if in= dividual points that call into the kernel need to decide this for themselve= s on a case-by-case basis.

=C2=A0

Britton

--047d7b5d3e643391b005289d2728--