kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

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.

Regards,
Tom