Mohamed S. Ebeida

PhD Candidate

Dept. of Mechanical and Aeronautical Engineering

University of California - Davis

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:

- Patrick M. Knupp
- Scott A. Mitchell
- Keith Dalbey
- Joseph E. Bishop
- Mario J. Martinez
- Vitus J. Leung

- A. H. Mahmoud
- M. A. Awad
- M. A. Mohammed

cache/wst.opf.4103746.xml

Transaction On Graphics (SIGGRAPH 2011)

- The first accurate grid-based solution to the MPS problem.

- 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.

- 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

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

- 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.

- 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.

Generalization of the MPS Problem:

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.

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.

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.

Copyright . Mohamed Ebeida. All rights reserved.