Specification
The aim of the Geometry Library is to clean up and unify Kicad's 2D
geometry engine and provide a solid base
for tools demanding more complex geometry operations, such as a
Push&Shove
router.
Rationale
Currently every object on a PCB/Schematic has its own notion of geometric shape.
Different subsystems deal with basic 2D geometry operations in their own
way.
There are at least 5 of such places:
- drawing
- plotting
- hit testing
- DRC/polygon processing
- LIB_ITEM derived classes in eeschema.
Adding another pad type could serve as an example of how much existing
code would have to be modified to full support the new pads in all
subsystems.
Need for extra geometry processing functions:
- Push & Shove requires spatial indexing and convex hull generation.
- Convex partitions may be required for rendering polygons (unless
some
sophisticated polygon cache is implemented inside the GAL). DRC may also
require need them to fully check polygon-to-anything-else clearance (including
graphical objects). - DRC needs many more checks to be implemented - for example
mask/silkscreen clearance, which require any-to-any shape distance check. - Smart selection (i.e. guessing what the user wanted to select in
case of
clicking over multiple objects, depending on the neighbourhood) requires fast conversion
of complex shapes to to polygons, clipping and polygon area & coverage calculation.
In case of the DRC, geometry functions are very model-specific, so
they
cannot be easily reused on different types of objects.
This results in artificial limitations, such as inability to stitch
polygons (because DRC redoes them instead of just checking the
clearances) or place arcs on copper layers (e.g. teardrops or
mitered traces, a must-have for high speed designs).
Numerical consistency between subsystems:
Any numerical differences between different geometry implementations
will very likely result with DRC dropping lots of clearance errors
caused by P&S and P&S unnecessarily adjusting objects that have
passed
the DRC.
Current geometry operations take a lot of code to maintain.
... and sometimes they are not very well designed (like
polygon/math_for_graphics.cpp).
In many places, intersection and distance calculations internally use
floating point
(basing all calculations on y=mx + b line equations),
which results with rounding errors for more vertical lines.
Functional requirements
The Geometry library incorporates the 3 parts:
- basic classes for 2D vector, axis-aligned bounding box, line segment and angle.
- collection of basic 2D shapes used in schematics and PCB geometry
- shape groups (a set of shapes treated as a single solid shape) and indexes.