kicad-developers team mailing list archive

[Lorenzo Marcantonio <l.marcantonio@xxxxxxxxxxxx>]

On Tue, Apr 30, 2013 at 12:28:56AM +0200, Tomasz Wlostowski wrote:
> >- 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).

Look, I have this 'political' situation here: I added a typedef for the
layer identifier (search for the LAYER_NUM) to better identify it and be
ready for whatever thing we decide to use when we add more layers.
I almost got lynched since they said 'int is more legible' (LAYER was
already taken:P)

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

Well, when I need a radius to draw I have to root it :D however even
a simple Newton convergence would do the trick in many many places,
without the tricks used for DSP (or maybe the DSP rooter is in fact
accurate:P). It's also needed for the vector norm (used when projecting,
for example). It's difficult to do linear algebra without sqrt:D

> 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.

Well... it's not exactly the last trend but... have you tried CORDIC?
I don't *actually* get the math behind, but should work. Also, in fact,
everything we need is a sin/cos for the unity circle and atan2 for
measuring angles. Hey, it even has a square root:D

Sadly the most common case (45 degrees!) has the dreaded sqrt(2)
creeping in (so even with fixed point manipulation has to be kept to
a minimum).

> 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).

These functions have other issues too. For example one of the
intersection (I don't remember if it's the same you said) computes a lot
of stuff (included distances) even if not requested to. In fact come out
at 22% time in a redisplay profiling. The funny thing is that elsewhere
probably there is another intersection done in a saner way.

> >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.

For someone in there that's 'bullshit'. They changed the angles to double
but don't care (at the moment) to check if they are stuffed to int and
back elsewhere (which they do, even in the DRC). Not to mention some
places where it goes from radians (from atan2) to decidegrees (in an
int) and back to radians for a rotation. And it's all done with wxPoint
so no serious vector work for you (also a huge work if it would to change).

Also, it seems that apparently I'm not qualified for a code review or
touching things that 'already work'...  what appreciation :D

-- 
Lorenzo Marcantonio
Logos Srl