Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

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


PhD Presentation

No description

Irving Cruz

on 16 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PhD Presentation

Isolated faces are not displaced. Faces of C disjoint with

C and vice versa.
Ph.D. Thesis
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
and F.Work
Representation Models
Structural Parameters
Model Simplification
An Improved
Decomposition Model
Lossless Orthogonal
Sphericity and
Virtual Porosimeter
Virtual Porosimeter
MIP simulation that does not require the
skeleton computation.

Washburn’s equation:
= − (4W γ
θ)/ρ . Each pressure ρ
is ρ related to a representative diameter

Iterative process that computes for each diameter
invaded region

Discarding process.

Narrow throats detection.

Mercury intrusion simulation.
Discarding Process
Pore regions smaller than the current
are discarded.
Three ABC-sorted CUDB are scanned.
Faster opening-like operation.
Throats Detection
of the Void Space
An OPP may have any number of rings on
faces, through holes and shells.
Faces Optimization
Two theorems:

Shape Preservation
Progressive Encoding
Progressive Extreme Vertices Encoding (PEVE) stores the extreme vertices of the sequence of BOPP only once.
Quality Distortion
Quality distortion curves of 12 test datasets
as a function of the percentage of total bytes
decoded (transmitted).
with similar methods
Octree-based method:
Smaller storage size.
Better indication of the shape.
Devise a new compact representation model
for binary volumes that allows fast
neighborhood operations.
Porous materials: Solid and pore space →
Binary volumes.

Pore space → Collection of pores interconnected by throats.

Real samples generate huge datasets.
Structural Parameters
In-silico experimentation = Mathematical
models + computers.
Imaging acquisition technologies + computer capabilities = processing and visualization of scientific data.
Parameters Computation
Porosity, pore-size distribution.
Helps to interpret characteristics of porous samples.
Suitability of biomaterials to form new tissues.

Topology-preservation evaluations.
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.
Voxel Model
Commonly used to represent medical
and scientific data.
Regular decomposition into a set of identical
cubic cells.

Binary voxel model → porous and solid spaces.
High memory and computational
power requirements.
Extreme Vertices
Model (EVM)

Extreme vertices: ending vertices of maximal segments.
ABC-ordering, Cuts (C), Slices, Sections (S).
Low memory footprint.
Fast Boolean operations:
Recursive 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:
Pore-size Distribution
Model Simplification
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
approximated shape.
Bounding Volumes
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
Other Representations
To reduce the memory footprint and
improve the performance:
Hierarchical Structures

Boundary Representations
Contructive Solid
Geometry (CSG)
Chain Codes
Semi-boundary and Shell
Extreme Vertices Model & Ordered Union of Disjoint Boxes
Concise representation scheme for orthogonal
pseudo-polyhedra (OPP).
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.
= -(4
θ) / ρ

Toxic products, samples cannot be reused.
Virtual porosimetry simulates MIP → Flood-fill methodology.

Alternatives: Heuristic methods and granulometry.

Skeleton computation is a very
time-consuming process.
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
2 1/3
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.
Resulting pore
Orthogonal throats
Single oblique
General oblique
Intrusion Simulation
CCL applied to the partitioned pore space.

A labeled region
is produced.
Comparison with a skeleton-based method
Two strategies: Inclined rectangle and L-shape.
Pore-size distribution.
Connectivity Computation
Method derived from the classical method
used with a voxel model.
Unitary Elements
Per each box, the number of enclosed voxels,
faces, edges and vertices are computed.
Compared with a voxel-based and a previous
EVM-based method.

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
Total genus
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 - χ
Method Performance
EVM-Roundness Correlation
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%.

Faster computation.
Throats Detection
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:
Throats Detection
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

I. Cruz-Matías
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,
I. Cruz-Matías
, 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.
J. Rodríguez,
I. Cruz
, E. Vergés, and D. Ayala. A connected-component-labeling-based approach to virtual porosimetry. Graphical Models, 73:296-310, 2011.

I. Cruz-Matías
and D. Ayala. Merging faces: A New Orthogonal Simplification of Solid Models. DGCI 2013, volume 7749 of LNCS, pages 143–154. Springer-Verlag, 2013.
I. Cruz-Matías
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
I. Cruz-Matías
. A Polyhedral Approach to Compute the Genus of a Volume Dataset. GRAPP 2012, pages 38–47, Rome, Italy, 2012.
I. Cruz-Matías
and D. Ayala. Orthogonal Simplification of Objects Represented by the Extreme Vertices Model. GRAPP 2012, pages 193–196, Rome, Italy, 2012.

J. Rodr ́ıguez,
I. Cruz
, E. Vergés, and D. Ayala. Skeletonless Porosimeter Simulation. XX Spanish Computer Graphics Conference-CEIG 2010, pages 49–56. Ed. Ibergarceta, 2010.
International Conferences
National Conferences
Acknowledgments to the CICYT projects TIN2008-02903 and TIN2011-24220, and to the Doctoral grants of MAEC-AECID and
Thanks for your attention
Basic Merging
Displacement in pairs of OPP's faces in the
direction of their corresponding normal vector.
Orthogonal Simplification
A level-of-detail sequence of bounding OPP (BOPP)
that satisfy the next properties:
PEVE and
Structural Parameters
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.
Incremental method:
Subset property:
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
XOR operations.
with shape
without shape preservation
CUDB-based collision algorithm used to detect 2D isolate faces.
EV classiffied into 3 categories.
BSP-based method:
Faster run-time.
Maintain better the concavities.
BP-Octree-based method:
Faster run-time.
Better indication of the shape.
Less storage cost.
Silica nano
CT dataset
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.
Future Work
A decomposition model, CUDB.
An EVM-based lossless simplification method
for OPP. Compared with similar methods:
Virtual porosimeter.
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.
Simplification method:
An EVM or CUDB-based data
structure to encode
time-varying datasets.
CUDB produces an optimal number of disjoint boxes ?
Computation of the CUDB complement.
Method that preserves the connectivity.
Extend the comparison to other methods.
Developed 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.
CUDB Performance
Less elements than EVM and OUDB.

CCL computation up to two orders of magnitud faster than the
OUDB-based method.
Thirty 3D models of rocks.
Lossy Simplification
Merging faces strategy takes consecutive
cuts in pairs. Merging conditions:

Data Structure
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).
Practical Application
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
than OUDB.
Three structural parameters methods with better run time than reference methods.
Better indication of the shape.
In some cases: Faster run time and
less stoge.
The method computes all the objects for successive values of displacement
Two queries of simplification:
CCL process

Extreme vertices
: ending vertices of maximal segments.
: Sorted set of extreme vertices.
Cuts (C)
. Set of EV lying on a plane → FD and BD.
Slices: Prismatic region between cuts.
Sections (S)
: 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
Full transcript