Disk Density Tuning of a Maximal Random Packing

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

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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
Volume35
Issue number5
DOIs
StatePublished - Aug 1 2016

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Cite this