Disk Density Tuning of a Maximal Random Packing

Mohamed S. Ebeida, Ahmad A. Rushdi, Muhammad A. Awad, Ahmed H. Mahmoud, Dong Ming Yan, Shawn A. English, John D. Owens, Chandrajit L. Bajaj, Scott A. Mitchell

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We introduce an algorithmic framework for tuning the spatial density of disks in a maximal random packing, without changing the sizing function or radii of disks. Starting from any maximal random packing such as a Maximal Poisson-disk Sampling (MPS), we iteratively relocate, inject (add), or eject (remove) disks, using a set of three successively more-aggressive local operations. We may achieve a user-defined density, either more dense or more sparse, almost up to the theoretical structured limits. The tuned samples are conflict-free, retain coverage maximality, and, except in the extremes, retain the blue noise randomness properties of the input. We change the density of the packing one disk at a time, maintaining the minimum disk separation distance and the maximum domain coverage distance required of any maximal packing. These properties are local, and we can handle spatially-varying sizing functions. Using fewer points to satisfy a sizing function improves the efficiency of some applications. We apply the framework to improve the quality of meshes, removing non-obtuse angles; and to more accurately model fiber reinforced polymers for elastic and failure simulations.

Original languageEnglish (US)
Pages (from-to)259-269
Number of pages11
JournalComputer Graphics Forum
Issue number5
StatePublished - Aug 1 2016
Externally publishedYes

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Disk Density Tuning of a Maximal Random Packing'. Together they form a unique fingerprint.

Cite this