Best way to determine pad pitch

Hi,

the issue is that in order to find the minimum distance between any two pads, all combinations of pads have to be checked, which in your case results in a combinatorial explosion. If you can determine a cutoff value -- a value as small as possible but guaranteed to be at least as large as the pad pitch, you can first do a selection of pad pairs where the pads are within the cutoff distance of each other. This would result in comparatively few pad pairs, from which you can then find the minimum pitch. This is more efficient, since in order to find objects within a certain distance to each other Ravel uses a very efficient algorithm which arranges objects according to proximity and therefore does not have to process every possible combination.

Regards, Björn

Hi Björn,

I have attempted to implement your suggestion and got as close as I could to a working solution by subdividing the design into smaller "regions" to work with.  Simply combining 27K+ pads in order to do a selection of pad pairs below the cutoff distance crashes my session.  Subdividing the design into regions allowed me to combine a smaller subset of pads that met the cutoff distance.  However, because the design has 27K+ pads, I still run into a memory issue because even though the regions make pad pairs much more manageable, Ravel must still keep track of 70+ of these "region" tuples.

How would you implement your suggestion?  How do I create an initial tuple of pad pairs to even look at whether or not they meet a certain cutoff distance?  I understand your theory and what you are suggesting.  I just don't know how to implement it.  I can't do (combine bumppad bumppad) or the session will run out of memory.  So how do I begin?

Thanks for your help!!

Hi,

Yes, it is true that combining 27,000 objects with themselves in the general case would be prohibitely expensive. For many common operations however, the Ravel optimization engine recognizes and optimizes the evaluation such that the full combination never has to be formed. One such operation is measuring distance. The common pattern of combining two relations and selecting tuples where the distance between objects of the two input relations is lower than a given value is optimized with a sophisticated tree algorithm. This tree algorithm builds a spatial tree, essentially dynamically creating regions based on object proximity, where small regions of objects are arranged into larger regions in a tree structure. For this reason it is likely counterproductive to attempt to create your own regions, since it does not allow the Ravel optimization to work on the whole set of objects.

I do not have your testcase here, so I created a grid of points, 165x165 = 27,225, evenly separated. Combining these points with themselves, selecting pairs closer to each other than 11 (the pitch was 10), took roughly three minutes on my laptop, so not super fast but manageable. Here is a trace with RAVEL_TRACE_OPTIMIZATION turned on; You can see that thanks to the spatial tree algorithm it only has to do 243,049 direct object comparisons out of a possible 741,200,625 if all objects were pairwise compared:

(03:12:21) |(define neighbors (select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11))))
(03:12:21) ||(select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11)))
(03:12:21) >>> (select (p1 p2) (combine coordinate coordinate) (and (ordered? p1 p2) (lessp (distance p1 p2) 11))) => (select_combine (p1 p2) (and (ordered? p1 p2) (lessp (distance p1 p2) 11)) (coordinate coordinate))
(03:12:21) >>> Spatial box tree optimization:
(03:12:21) >>> Building tree for p1/point in ((p1 point))
(03:12:33) >>> # elements: 27225
(03:12:33) >>> node size: 16
(03:12:33) >>> height: 5
(03:12:33) >>> Reusing identical tree
(03:15:27) >>> # of comparisons: 243049/741200625 = 0.03%
(03:15:27)
(03:15:27) ||select --> #<relation:54120:(point point)>
(03:15:27) |define --> neighbors

Now, the question of what to use for a cut-off value is tricky in the general case, but if your objects are not randomly distributed but rather arranged in a grid, you could e.g. find the two smallest x coordinates and use the difference as a starting point:

(define xcoordinate
  (transform (p) bumppad
    ((xcoordinate (center p)))))

(define x1st
  (CHOOSE_MIN xcoordinate IDENTITY))

(define x2nd
  (CHOOSE_MIN (difference xcoordinate x1st) IDENTITY))

(define cutoff
  (transform (x1st x2nd) (combine x1st x2nd)
    ((difference x2nd x1st))))

Regards,

Björn

After some more investigation, I have found a more reliable method of finding a good cutoff value as per above:

;; Form pairs of x-y coordinates corresponding to each bump.
(define x_y
  (transform (bump) bumppad
    ((xcoordinate (center bump)) (ycoordinate (center bump)))))

;; Group y coordinates corresponding to the same x coordinate into
;; collections. They correspond to y coordinates of bumps on the same
;; "row", where each row has the same x coordinate.
(define ys
  (PAIR_2 (contract y (x y) x_y)))

;; Pick the "row" of y coordinates with the largest size. (Because the
;; probability is high that there is a pair with small pitch, giving a
;; small cutoff value.) Expand the collection to form a relation of
;; the y coordinates on this "row" (for a given x coordinate).
(define yrow
  (expand ys (ys)
    (PAIR_1 (CHOOSE_MAX_VALUE (transform (ys) ys
                                (ys (count ys)))))))

;; Find the cutoff value by finding the smallest different between y
;; coordinates in the "row" we are working with.
(define cutoff
  (CHOOSE_MIN (transform (y1 y2)
                  (select (y1 y2) (combine yrow yrow)
                    (ordered? y1 y2))
                ((abs (difference y1 y2))))
              IDENTITY))

It assumes that pads for the most part are placed in a grid-like pattern, and is fast and efficient even for a large number of pads.

Regards,

Björn