← Back to team overview

kicad-developers team mailing list archive

Re: Guidelines for KiROUND-ing


On 04/29/2013 09:51 PM, Lorenzo Marcantonio wrote:
On Mon, Apr 29, 2013 at 09:03:32PM +0200, Tomasz Wlostowski wrote:
My 0.001 cent - It's much simpler: just don't use floating point.

That what's we try to do when possible, to avoid rounding issues and
have better numerical stability (more or less... I'd like that stability
would be achieved only with that!).
Hi Lorenzo,

This is what we're trying to do in the Geometry Library. It's fixed-point only (and I hope we'll be able to check distances/clearance of arcs without FP calculations either or without numeric stability issues). The biggest problem I've encountered with FP calculations is that an intersection point of two segments derived with one algorithm may not be qualified as being exactly on that segment by another routine (and as a result, the P&S algorithm will go crazy...). So the P&S code doesn't use floats at all. And I'm happy with this.

 However there are three important
things that need to be done in floating point:

- Squaring (not completely sure about this, correct me if I'm wrong),
   since it exceeds the int dynamic range
(Int32_t * int32_t) fits in uint64_t (that is, VECTOR2<int>::ecoord_type to make things look cleaner).

- Square roots: to find distances and other geometrical stuff.
Compare squared distances...

- Trig stuff, for rotation, circles and similar things. Mostly sin/cos
   and some atan2, too (there is an ArcTangente which works from int
   values and returns the results in decidegrees; I'm trying to convert
   the code to use it when possible)
This is the tricky part. In case of P&S, it doesn't care about rotation and treats rotated objects as convex polygons. Whatever trigonometric, FP operations are required to generate their shapes, they are kept outside. I guess the same rule could be applied to future versions of DRC.

BTW. I noticed that TestForIntersectionOfStraightLineSegments() function that is used in the DRC will very likely cause false DRC errors when used with P&S. It uses y=mx+b line equation, with a numerically unstable division to calculate the slope m (that may result with large rounding error, above DRC tollerance - to be verified).

So, no, we can't not use a double here... in fact this whole review
comes from the angular type becoming a double (before it was an int).

Unless you have some magic/clever way to fit these in an int (I don't
dare to propose computing distances with a 64 bit integer square root.
Why not, what's wrong about this? I'm even using 96-bit operations for accurate intersection point computation, but this magic is hidden from the user. The simply returns the a VECTOR2<T>, whatever the type T is. Casting ints to doubles and back to ints simply doesn't work in my case.


Follow ups