----- Rick Collins <[email protected]> wrote: > At 09:12 AM 8/16/2010, you wrote: > I'm not sure I follow. I was thinking of this when I saw your first > post. This is a similar problem to displaying graphics using 3D > information. I have seen a speed up method for that which uses the > extra memory that typically is left over from working with three > dimensions, in essence a fourth dimension. They precompute an > approximate Z position (relative to the eye) which they use to > quickly scan the data to see which planes to display first which are > most likely to be partially or fully overwritten. > > In your case, for each feature (your own definition of feature which > works optimally) a working radius is computed which includes the > furthest extent of the feature from it's origin plus what ever > clearance is needed. All features are checked against one another > still, but now it is just a matter of comparing origins against the > working radii which is a much faster operation than checking each > feature in detail (even a bounding box). Only the features that fail > this test are then checked in detail, greatly speeding up the > operation. Yes, you need to precompute the working radius of each > "feature" on the board and store it, so that you only do this once > and save that computing time for each display update. >
I like this. Since many features on a PCB are traces, which are long and thin, I wonder if we could achieve an even-greater speedup by using "bounding ellipses" rather than circles. With rounded-up sine tables I think we can do the check nearly as fast as we could with simple circles (will have to check my calc book), and we'd eliminate a -lot- more components in the initial scan. Andrew _______________________________________________ geda-user mailing list [email protected] http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
