Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
You can change this under Settings & Account at any time.
Transcript of PhD Presentation
C and vice versa.
Programa de Doctorat en Computació
Departament de Llenguatges i Sistemes Informàtics
by: Irving A. Cruz-Matías
Advisor: Dr. Dolors Ayala
Contribution to Structural Parameters Computation: Volume Models and Methods
MIP simulation that does not require the
= − (4W γ
θ)/ρ . Each pressure ρ
is ρ related to a representative diameter
Iterative process that computes for each diameter
Narrow throats detection.
Mercury intrusion simulation.
Pore regions smaller than the current
Three ABC-sorted CUDB are scanned.
Faster opening-like operation.
of the Void Space
An OPP may have any number of rings on
faces, through holes and shells.
Progressive Extreme Vertices Encoding (PEVE) stores the extreme vertices of the sequence of BOPP only once.
Quality distortion curves of 12 test datasets
as a function of the percentage of total bytes
with similar methods
Smaller storage size.
Better indication of the shape.
Devise a new compact representation model
for binary volumes that allows fast
Porous materials: Solid and pore space →
Pore space → Collection of pores interconnected by throats.
Real samples generate huge datasets.
In-silico experimentation = Mathematical
models + computers.
Imaging acquisition technologies + computer capabilities = processing and visualization of scientific data.
Porosity, pore-size distribution.
Helps to interpret characteristics of porous samples.
Suitability of biomaterials to form new tissues.
Used to measure the strength of bones or materials.
Sphericity and roundness.
Used in geology to classify particles and measure
their resistance to crushing or fragmenting.
Bio-CAD refers to the computation of structural
Physical properties of a sample
Used in biomaterials, medicine,
mineralogy, geology, etc.
Commonly used to represent medical
and scientific data.
Regular decomposition into a set of identical
Binary voxel model → porous and solid spaces.
High memory and computational
Extreme vertices: ending vertices of maximal segments.
ABC-ordering, Cuts (C), Slices, Sections (S).
Low memory footprint.
Fast Boolean operations:
Ordered Union of
Disjoint Boxes (OUDB)
Disjoint boxes derived by splitting an OPP at every internal cut.
Six different ABC-OUDB models.
Efficient for neighborhood operations,
e.g. volume and CCL.
A true 3D roundness index is impractical.
Several methods use 2D projections (silhouettes).
Krumbein's chart: Roundness of pebble silhouettes.
Sphericity and Roundness
Orientation → rotation angles around a set
of orthogonal axes.
Sphericity = how spherical is a particle. Wadell's sphericity:
Manual measures of
are very difficult. Alternatives use the three representative axes, e.g: Ψ=(c /ab)
Roundness = sharpness of a particle's edges and
corners. Wadell's 2D roundness:
Extensively applied to triangular meshes using geometric or morphological operations.
Representations such as octrees or BSP are used to simplify the geometry and topology.
Lossy and lossless methods preserve
the original topology or obtain an
Sometimes it is desirable to compute a bounding approximation, e.g.:
Fast collision detection between massive models.
Volume of interest computation.
Bounding structures: AABB, spheres, slab cut balls, etc.
Some simplification methods produce
hierarchies of either polygonal meshes
or polygonal convex volumes.
Binary Space Partition (BSP) tree
To reduce the memory footprint and
improve the performance:
Semi-boundary and Shell
Extreme Vertices Model & Ordered Union of Disjoint Boxes
Concise representation scheme for orthogonal
XYZ (8 boxes) XZY (7 boxes) YZX (9 boxes)
Usually computed with a mercury intrusion porosimeter (MIP).
Mercury intrusion at increasing pressures.
Washburn's equation → pore-size histogram.
θ) / ρ
Toxic products, samples cannot be reused.
Virtual porosimetry simulates MIP → Flood-fill methodology.
Alternatives: Heuristic methods and granulometry.
Skeleton computation is a very
Connectivity is related to genus.
Can be estimated from the Euler-Poincaré characteristic, χ:
Some methods use skeletons and
alternative models like EVM.
From a voxel model: χ = n - n + n - n
In theory of homology (betti numbers): χ = h - h + h
From a polyhedron: χ = V - E + F - R = 2(S - g)
0 1 2 3
0 1 2
Later methods give values linearly correlated with this chart.
Compact Union of Disjoint Boxes Model (CUDB)
A cell decomposition representation that improves OUDB:
Less number of boxes. Several contiguous boxes are merged into one.
Implicit order among boxes that defines their adjacency is lost; however, adjacency information is preserverd in the boxes.
CCL applied to the partitioned pore space.
A labeled region
Comparison with a skeleton-based method
Two strategies: Inclined rectangle and L-shape.
Method derived from the classical method
used with a voxel model.
Per each box, the number of enclosed voxels,
faces, edges and vertices are computed.
Compared with a voxel-based and a previous
Tested with a collection of 15 datasets.
All methods produce exactly the same results.
Fast computation of χ, < 1 second in all tests.
0 1 2 3
1 0 2
All possible overlaping regions are
taking into account.
Possible configurations of a box β with its backward neighbors.
Up to two orders of magnitude faster than the voxel-based method.
Up to an order of magnitude
faster than the EVM-based
Narrow throats are removed from the pore space to prevent the mercury invasion.
Max. difference: < 12% (inclined rectangle) < 3% (L-shape).
MIP simulation up to an order of magnitude faster.
It require a CUDB-represented object.
The contribution of unitary elements per box
are computed using the expresion suitable for the voxel model.
χ = n - n + n - n
Genus is computed applying CCL to get the connected components and cavities.
h = h + h - χ
Correlation with Krumbein’s chart = -0.898.
Computing OBB from the voxel model = -0.902.
Oriented bounding box (OBB) used to get
the three representative axes of an object.
OBB computed with the covariance method using extreme vertices instead of voxels.
Maximum volume difference < 8.5%.
Boxes in CUDB have neighboring boxes in the
A and B-direction. Othogonal throats are detected in
An orthogonal throat exists between consecutive boxes if the following conditions are satisfied:
An oblique throat exists between consecutive boxes if the following conditions are satisfied:
EVM-represented oblique throat created with the Bresenham’s algorithm.
A 3D roundness index using a ray-casting-like approach based on EVM. Three steps:
2. Transform the model such that the reference ellipsoid is in the origin.
3. Trace rays to each extreme vertex and
compute the deviation from the ellipsoid's surface.
1. Compute the OBB → Inscribed ellipsoid.
Correlation with a previous 3D roundness index = -0.938
and D. Ayala. A New Lossless Orthogonal Simplification Method for 3D Objects Based on Bounding Structures. Graphical Models, (Acceptable for publication provided minor revisions are made), 2013.
M. Garcia-Valles, H. Hafez,
, E. Vergés, M. Aly, J. Noguées, D. Ayala, and S. Martínez. Calculation of viscosity-temperature curves for glass obtained from four wastewater treatment plants in Egypt. Journal of Thermal Analysis and Calorimetry, 111:107–114, 2013.
, E. Vergés, and D. Ayala. A connected-component-labeling-based approach to virtual porosimetry. Graphical Models, 73:296-310, 2011.
and D. Ayala. Merging faces: A New Orthogonal Simplification of Solid Models. DGCI 2013, volume 7749 of LNCS, pages 143–154. Springer-Verlag, 2013.
and D. Ayala. An Efficient Alternative to Compute the Genus of Binary Volume Models. GRAPP 2013, pages 18–26, Barcelona, Spain, 2013.
D. Ayala, E. Vergés, and
. A Polyhedral Approach to Compute the Genus of a Volume Dataset. GRAPP 2012, pages 38–47, Rome, Italy, 2012.
and D. Ayala. Orthogonal Simplification of Objects Represented by the Extreme Vertices Model. GRAPP 2012, pages 193–196, Rome, Italy, 2012.
J. Rodr ́ıguez,
, E. Vergés, and D. Ayala. Skeletonless Porosimeter Simulation. XX Spanish Computer Graphics Conference-CEIG 2010, pages 49–56. Ed. Ibergarceta, 2010.
Acknowledgments to the CICYT projects TIN2008-02903 and TIN2011-24220, and to the Doctoral grants of MAEC-AECID and
Thanks for your attention
Displacement in pairs of OPP's faces in the
direction of their corresponding normal vector.
A level-of-detail sequence of bounding OPP (BOPP)
that satisfy the next properties:
Pore-size distribution: A simplified sample retains enough relevant information and is processed faster.
Connectivity: Datasets containing big holes preserve its genus until approximations with 10% of the elements.
Sphericity is better preserved than roundness throughout the simplification.
Any BOPP contains the previous one.
: The sequence is finite and ends with
the AABB shared by all BOPP.
New cuts that represent the merged faces and replace the original cuts are computed as:
A void space is given by :
The removal of
closes the void space.
Two EVM properties that permit to perform unions and differences in some cases as simple point-wise
without shape preservation
CUDB-based collision algorithm used to detect 2D isolate faces.
EV classiffied into 3 categories.
Maintain better the concavities.
Better indication of the shape.
Less storage cost.
Industrial uses of silica sand depend on its
purity and physical characteristics.
Grain Properties Computation
The more round and spherical are the particles, the more resistant they are to crushing or fragmenting.
A decomposition model, CUDB.
An EVM-based lossless simplification method
for OPP. Compared with similar methods:
Orientation and roundness index.
Pore space partitioning using a different approach to virtual porosimetry, e.g. compute all throats at once and analyze paths that connect the solid space.
An EVM or CUDB-based data
structure to encode
CUDB produces an optimal number of disjoint boxes ?
Computation of the CUDB complement.
Method that preserves the connectivity.
Extend the comparison to other methods.
CUDB implemented as an object with
a set of properties and methods.
Straightforward by doing a traversal
of the boxes.
Area (2D) and volume (3D) computation:
EVM ←→ CUDB conversion.
Similar conversions than OUDB.
Developed Methods (2)
Exact collision detection.
Connected Component Labeling (CCL).
Detection of connected components in graph theory.
Depth-first or breadth first search.
Takes advantage of the implicit order of boxes in CUDB.
Objects are tested simultaneously instead of in pairs.
EVM→CUDB. Compacting on the fly.
Three ABC-sorted CUDB are scanned.
Inclined rectangle L-Shape Skeleton-based method.
Less elements than EVM and OUDB.
CCL computation up to two orders of magnitud faster than the
Thirty 3D models of rocks.
Merging faces strategy takes consecutive
cuts in pairs. Merging conditions:
for Progressive Encoding
Unique (U): It appears once.
Consecutive (C): It has a consecutive occurrence.
Sporadic (S): It appears several times.
Maximum value for the distance.
Maximum number of EV in the last BOPP.
Theorem: The number of times a S-vertex can appear is <=2 (2D) and <=4 (3D).
Preprocessing: Conversion to 8-bit voxel model, scaling, binary threshold filter, and noise reduction.
A 32-bit gray scale dataset in RAW format with dimensions 131x281x332 of a silica nano CT.
Smaller storage and better performance
Three structural parameters methods with better run time than reference methods.
Better indication of the shape.
In some cases: Faster run time and
The method computes all the objects for successive values of displacement
Two queries of simplification:
: ending vertices of maximal segments.
: Sorted set of extreme vertices.
. Set of EV lying on a plane → FD and BD.
Slices: Prismatic region between cuts.
: Set of polygons, base of each slice.
Vertices Model (EVM)
Low memory footprint.
Fast Boolean operations.
A new approach for virtual porosimetry, which avoids the skeleton computation.
A method to compute the connectivity of binary volumes based on the proposed representation model.
Geometric methods to evaluate the sphericity and roudness.
A method to simplify binary volume and general orthogonal pseudo-polyhedra, in a lossless way.
Develop two practical applications using datasets coming from real