C and vice versa.

**Ph.D. Thesis**

Programa de Doctorat en Computació

Departament de Llenguatges i Sistemes Informàtics

Programa de Doctorat en Computació

Departament de Llenguatges i Sistemes Informàtics

**by: Irving A. Cruz-Matías**

Advisor: Dr. Dolors Ayala

Advisor: Dr. Dolors Ayala

**Contribution to Structural Parameters Computation: Volume Models and Methods**

Introduction

Background

Main

Contributions

Practical

Applications

Conclusions

and F.Work

Outline

Representation Models

Structural Parameters

Model Simplification

An Improved

Decomposition Model

Connectivity

Lossless Orthogonal

Simplification

Sphericity and

Roundness

Virtual Porosimeter

CUDB-based

Virtual Porosimeter

MIP simulation that does not require the

skeleton computation.

Washburn’s equation:

D

= − (4W γ

cos

θ)/ρ . Each pressure ρ

is ρ related to a representative diameter

D

.

Iterative process that computes for each diameter

D

the

invaded region

R

:

Discarding process.

Narrow throats detection.

Mercury intrusion simulation.

Discarding Process

Pore regions smaller than the current

diameter

D

are discarded.

Three ABC-sorted CUDB are scanned.

Faster opening-like operation.

Narrow

Throats Detection

Treatment

of the Void Space

An OPP may have any number of rings on

faces, through holes and shells.

Merging

Faces Optimization

Two theorems:

Shape Preservation

Lossless

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

Comparison

with similar methods

Octree-based method:

Smaller storage size.

Better indication of the shape.

Motivation

Objectives

Devise a new compact representation model

for binary volumes that allows fast

neighborhood operations.

Samples

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.

Structural

Parameters Computation

Porosity, pore-size distribution.

Helps to interpret characteristics of porous samples.

Suitability of biomaterials to form new tissues.

Connectivity.

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.

Objetives

Bio-CAD refers to the computation of structural

parameters:

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.

Roundness

A true 3D roundness index is impractical.

Several methods use 2D projections (silhouettes).

Krumbein's chart: Roundness of pebble silhouettes.

Orientation,

Sphericity and Roundness

Orientation → rotation angles around a set

of orthogonal axes.

Sphericity = how spherical is a particle. Wadell's sphericity:

Manual measures of

S

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:

Connectivity

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:

Octree

Hierarchical Structures

Boundary Representations

Kd-tree

Contructive Solid

Geometry (CSG)

etc.

B-Rep

Chain Codes

Semi-boundary and Shell

Extreme Vertices Model & Ordered Union of Disjoint Boxes

etc.

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.

D

= -(4

W

γ

cos

θ) / ρ

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:

YZX-OUDB

YZX-CUDB

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.

i

i

i

X-discarding

Y-discarding

Resulting pore

region

Orthogonal throats

Single oblique

throat

General oblique

throat

i

Mercury

Intrusion Simulation

CCL applied to the partitioned pore space.

A labeled region

R

is produced.

Comparison with a skeleton-based method

Two strategies: Inclined rectangle and L-shape.

i

Pore-size distribution.

Connectivity Computation

Method derived from the classical method

used with a voxel model.

Computing

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.

i

Up to two orders of magnitude faster than the voxel-based method.

Up to an order of magnitude

faster than the EVM-based

method.

Total genus

computation

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.

Orientation

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.

Orthogonal

Throats Detection

Boxes in CUDB have neighboring boxes in the

A and B-direction. Othogonal throats are detected in

A-direction.

An orthogonal throat exists between consecutive boxes if the following conditions are satisfied:

Oblique

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.

EVM-Roundness

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

Publications

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.

Journals

International Conferences

National Conferences

Acknowledgments

Acknowledgments to the CICYT projects TIN2008-02903 and TIN2011-24220, and to the Doctoral grants of MAEC-AECID and

CONACYT-México.

Thanks for your attention

Questions?

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.

Finiteness

: 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

vSpace

closes the void space.

Two EVM properties that permit to perform unions and differences in some cases as simple point-wise

XOR operations.

Original

with shape

preservation

without shape preservation

CUDB-based collision algorithm used to detect 2D isolate faces.

EV classiffied into 3 categories.

B

A

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.

Conclusions

Future Work

CUDB:

A decomposition model, CUDB.

An EVM-based lossless simplification method

for OPP. Compared with similar methods:

Virtual porosimeter.

Connectivity

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.

OUDB CUDB

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

d

.

Two queries of simplification:

CCL process

Extreme vertices

: ending vertices of maximal segments.

ABC-ordering

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

Extreme

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

samples.

?