Mohamed S. Ebeida
PhD Candidate
Dept. of Mechanical and Aeronautical Engineering
University of California - Davis

Research: Meshing
Well-spaced Random Sampling

In 2010, I joined Sandia National Laboratories. My first task was to create a random mesh for some arbitrary domain with internal cracks. This led to a Maximal Possion-disk Sampling problem, which is quite popular in the computer graphics community. I was surprised that this problem didn't have the same popularity in the Computational Geometry community despite that the theoretical quality guarantees associated with a Maximal Possion-disk Sample are the same as the Delaunay Refinement (DR) methods. However, MPS is superior to DR in that it generates a point cloud that strictly adhere to the input sizing function while the result of DR is unexpected since it doesn't really depend on a well defined sizing function! 

Since then I have been working on exploring MPS for meshing and uncertainty quantification (UQ) purposes with a great research team including:

Sandia National Laboratories:

University of Texas Austin:

Alexandria Univ. (EGYPT):
  • A. H. Mahmoud
  • M. A. Awad
  • M. A. Mohammed


During the two last years, we have proposed many algorithms to solve the MPS problem and apply the solution to meshing and UQ problems. In this page I will present briefly the accomplished projects so far.

New Solutions to the MPS Problem:

1. Efficient maximal Poisson-disk Sampling: 
    Transaction On Graphics (

  • The first accurate grid-based solution to the MPS problem. 
paper - slides - doi bibtex

2. A simple algorithm for maximal Poisson-disk sampling in high dimensions:
    Computer Graphics Forum (Eurographics 2012)

  • The fastest accurate algorithm in the literature with the lightest memory requirement.
  • Works for any number of dimensions (as long as you can afford it)
  • Maximal up to the round-off error. 
paper - slides - doi - bibtex

MPS for Delaunay/Voronoi Meshing:

1. Efficient and good Delaunay Meshes from Random Points: 
    Journal of Computer Aided Design (SIAM_GD 2011)
  • Compares MPS solutions to Delaunay Refinement solutions. 
  • Uniform sizing function - Non-convex two dimensional domains with multiple holes and cracks.
  • Linear run-time complexity for uniform sizing function
paper - slides - bibtex

2. Uniform Random Voronoi Meshing:
    20th IMR
  • Direct generation of Voronoi cells in 3d spaces
  • Uniform sizing function - Domains wirh Curved surfaces
  • Linear run-time complexity for unsiform sizing functions
paper - slides - bibtex

Sampling using higher dimensional flats:

1. k-d darts: Sampling by k-dimensional flat searches: 
    TOG (accept with minor revisions) - axiv version is available now
  • Solves a relaxed version of the MPS problem using higher dimensional flats.
  • The most affordable algorithm in the literature for generating Well spaced random point set in higher dimensional spaces (e.g. d = more than 10).
  • Useful for Stochastic integration in high dimensional spaces as well.
arxiv version - bibtex

2. High quality parallel depth-of-field using line samples

    High Performance Graphics 2012
  • Utilize an early version of kd-darts to solve a DOF rendering problem.
  • GPU implementation shows 4-5x spped up compared to conventional point samples.
paper - slidesbibtex

Generalization of the MPS Problem:

1. Variable Radii Poisson-disk sampling: 
CCCG 2012

  • Defines various conflict criteria for solving the MPS problem with varying sizing function.
  • Decouples the conflict radius from the coverage radius.
  • Shows the impact of these definitions on the quality of the final point set and the underlying mesh. 
    paper - slides - bibtex

2. Improving Spatial Coverage while Preserving Blue Noise: 
Journal of Computer Aided Design (SIAM_GD 2013)

  • Explores solving the MPS problem with a conflict radius that is larger than the coverage radius. 
  • Demonstrates the impact on meshing and image filtering. 

3. Sifted Disks: 
Computer Graphics Forum (EuroGraphics 2013)

  • Introduces a post-processing algorithm that significantly reduces the size of a given maximal sample. 
  • Preserves domain coverage using the same sizing function used for generating the original set.  
    paper - slides - bibtex