RangeFinder: Accelerating ball-interference queries against steady lattices. (July 2019)

• Record Type: Journal Article
• Authors: Kurzeja, Kelsey; Rossignac, Jarek
• Is Part Of: Computer aided design. Volume 112(2019)
• Page Start: 14
• Page End: 22
• Publication Date: 2019-07
• Subjects: Lattice -- Pattern -- Query -- Point-membership classification -- Procedural modeling -- Steady affine motions; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2019.03.002
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Advances in additive manufacturing techniques are enabling the fabrication of new microstructures and materials. These may often be defined in terms of a set of balls and of beams that each connects two balls. To support application needs, we must efficiently support structures with billions of beams. To address this challenge, we advocate steady lattices, which implicitly define a u × v × w array of groups of balls such that each consecutive pair of groups in a given direction is related by the same similarity transformation and such that the beams are defined to periodically connect the same corresponding, relatively-indexed pairs of balls. We propose an algorithm that accelerates theBall-Interference Query (BIQ ), which establishes which balls and beams of the lattice interfere with a query ball Q . OurRangeFinder solution reduces the asymptotic time-complexity of BIQ from O ( u v w ) to O ( u v ) . For special cases, it reduces the complexity even further down to O ( u ) and O ( 1 ) . In our tests, RangeFinder reduced the query time by up to a factor of 9420 times. RangeFinder does not use any spatial occupancy data structure and can be trivially parallelized. We demonstrate the effectiveness of RangeFinder on standard lattices and also on their multi-levelLattice-in-Lattice (LiL ) variants. Highlights: O(1) test for interference between a ball and similarity-based patterns. Reduced asymptotic cost of ball-interference queries (BIQs) against steady lattices. Accelerated generation of multi-level lattices, called Lattice-in-Lattice (LiL).