kicaddevelopers team mailing list archive

kicaddevelopers team

Mailing list archive

Message #10194
Re: Guidelines for KiROUNDing
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
fixedpoint 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 96bit 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
Follow ups
References