Geometric Mesh Processing:
Mesh Generation
Fabio Ganovelli
[email protected]
ISTI- CNR
Introduzione
Tipi di mesh: mesh strutturate
Una mesh regolare è una decomposizione in elementi i cui vertici
sono espressi come mapping di un dominio più semplice
Γ' = f ( Γ )
f ( 0 ,1 )
Γ = [ 0,1] × [ 0,1]
f
f ( 1,1 )
Γ'
f ( 1,0 )
f ( 0 ,0 )
• Richiedono poca memoria
• Facilità di applicazione del metodo
alle differenze finite
• difficile determinare mapping che
approssimino “bene” domini complessi
• non sempre possibile
Introduzione
Tipi di mesh: mesh non strutturate
Decomposizione in elementi finiti
• possibilità di approssimare domini
arbitrariamente complessi
• Maggiore richiesta di memoria per la
memorizzazione
Da dove vengono le mesh?
Mesh Generation
Triangolazione di punti in 2D
• Definizione del problema
• Qualche algoritmo
Superfici 2D embedded in 3D
• Ricostruzione da sezioni planari (tiling)
• Marching Cubes
• Ball Pivoting
Mesh di volume
• Misure di Qualità
– Poliedri non triangolabili
– Punti di Steiner
• Triangolazione di poliedri
– Advancing front approach
– Medial axis transform
– Bubble Meshing (ricostruzione di domini non manifold)
• Triangolazione di Point set
– Alpha shapes
Introduzione
Definizioni
• Una mesh è una decomposizione di un sottoinsieme compatto
n
di R in celle.
• Un simplesso in n dimensioni è il luogo dei punti ottenuti come
combinazione convessa di n+1 punti
• Un complesso simpliciale Σ in n dimensioni è un insieme di
simplessi tale che:
– 1. tutte le facce di ogni n-simplesso appartengono a Σ
– 2. per ogni coppia di simplessi σ e τ vale:
∅
σ Iτ = 
 una faccia di entrambi
– 3. n è il massimo ordine dei simplessi di Σ
Mesh Generation in due dimensioni
Mesh simpliciali in
Input
Poligono
Semplice
Compl.
in tempo O(n)
Poligono
con buchi
O(n log h)
R
2
PSLG (Planar Point Set
Straight Line
Graph)
O( n log n)
O(n log n)
Problemi NP-completi:
– dire se un PSLG (con intersezioni) contiene una triangolazione [Lloyd77]
– dire se una collezione di triangoli contiene una triangolazione
Mesh Generation in due dimensioni
Criteri di ottimalità
Un criterio di ottimalità si definisce con funzioni f: T → R, di tipo:
f = max[min]{ f ( τ ) : τ ∈ Γ}
o
f =
f (τ )
∑
τ
∈Γ
dove f (t) misura la bontà di un triangolo
perché f sia ben definita deve avere un solo minimo in
corrispondenza del triangolo ideale (es: equilatero) e massimo non
limitato
f (τ ) può basarsi sull’angolo minimo o massimo, sulla lunghezza
del lato più lungo/corto, sull’area del più piccolo/grande cerchio
inscritto/circoscritto, sull’aspect ratio tra tutti i triangoli della mesh
Mesh Generation in due dimensioni
Es: Aspect Ratio
Def: L’aspect ratio è data dal rapporto tra il lato più lungo e
l’altezza relativa a tale lato
b
c
h
a
a
f (t )=
h
2
≤ f ( t ) ≤ +∞
3
min
2
3
a
h
L’aspect ratio è legata
all’angolo minimo θ :
1
2
≤ f (t )≤
sinθ
sinθ
f (t )=
h
a
max
f ( t ) → +∞
Mesh Generation in due dimensioni
Triangolazione di Delaunay
• Def: Cella di Voronoi di un punto p∈ S:
cVi = { x ∈ ℜ :| xpi |≤| xp j |∀p j ∈ S }
h
• Def: Diagramma di Voronoi di un point set S:
V = UcVi
• Def: Triangolazione di Delaunay di un point set S:
triangolazione contenente tutti e soli i lati che connettono due
punti che condividono un lato della cella di Voronoi (duale del
diagramma di Voronoi)
Mesh Generation in due dimensioni
Qualche proprieta’ ….
Dato un insieme di vertici, un edge {a,b} appartiene a DT sse esiste
un cerchio passante per a e b non contenente nessun altro vertice
b
b
a
a
Dato un insieme di vertici, un triangolo {a,b,c} appartiene a DT
sse il cerchio passante per a,b e c non contiene nessun altro
vertice
b
c
a
b
c
a
Preview di domani
• Lift-transformation
ψ : ℜ n → ℜ n +1
n
ψ ( x1 , K , xn ) = x1 , K, xn , ∑ xi2
i =0
ψ ( x, y ) = ( x , y , x 2 + y 2 )
• Proprieta’ incredibile:
– La proiezione sul piano dell’intersezione dei piani tangenti ai punti
“lifted” produce in diagramma di Voronoi dei punti sul piano
Mesh Generation in due dimensioni
Ottimizzazioni di DT
• Ottimizza :
– massimizza il minimo angolo
– minimizza il massimo circumcircle
– minimizza il massimo min-containment circle
Mesh Generation in due dimensioni
Ottimizzazione: algoritmo di flipping [Lawson77]
Procedura di ricerca locale
d
T
c
a
f (T ' ) = f ( abd ) + f (bcd ) <
f (abc) + f ( acd ) = f (T )
b
Complessità O(n2)
T’
d
c
a
b
Mesh Generation in due dimensioni
Ottimi globali
Variando il criterio per decidere quando due triangoli adiacenti
devono essere “flippati” si possono ottimizzare diverse misure, es.:
– max-min angle (Delaunay)
– min-max circumcircle (Delaunay) ….
– Min-max min containment circle (Delaunay)
Ci sono criteri per i quali l’algoritmo di flipping termina in un ottimo
locale, es.:
– min-max angle
– minimum total edge length (MWT)
Mesh Generation in due dimensioni
Edge insertion [Edelsbrunner92]
Generalizzazione dell’algoritmo di flipping
T1
Aggiunta di un
lato candidato
a
b
T2
Retriangolazione
T1
migliore
n
Ripristina
precedente
s
a
T2
b
Mesh Generation in due dimensioni
Anchor property
Def: data T , un vertice a di un triangolo abc è un anchor vertex se ∀
T’ : f(T’) < f(T), T’ contiene un lato ad che interseca il triangolo in bc
Def: vale la weak anchor property per f sse :
∀ T, ∀ abc ∈ T : f(abc) = f(T), uno dei vertici è un anchor vertex. Se ∀
abc ∈ T , uno dei vertici è un anchor vertex vale la strong anchor
property
Es: f(T) = max-angle gode della Weak Anchor Property
Teorema: se f soddisfa la WAP ⇒ l’algoritmo Edge Insertion
determina l’ottimo globale in O(n3)
Se vale SAP la complessità scende a O(n2log n)
Mesh Generation in due dimensioni
Poligoni Semplici:Programmazione dinamica
Una triangolazione di un poligono semplice che ottimizzi una
funzione decomponibile può essere calcolata in O(n3)
[Klincsek80]
Sia un poligono P, una sua diagonale ab e siano T e T’ due
triangolazioni delle due parti del poligono diviso da ab
Def: f(T) è decomponibile se:
• ∃g : f ( T ) = g ( f ( T1 ), f ( T2 ), a ,b ) monotona
• g è calcolabile in O(1)
• se T è un triangolo, f(T) è calcolabile in O(1)
T1
a
T2
b
f ( T ) = min Area
g( f1 , f 2 ,a ,b ) = max( f1 , f 2 )
f ( T ) = MWT
g ( f1 , f 2 ,a ,b ) = f1 + f 2 − ab
Mesh Generation in due dimensioni
dati vi ,v j , P( i , j ) = poligono formato dai vertici vi ,vi +1 ,K ,v j
ottimo di f su P( i , j ) se ( vi ,v j ) è una diagonale
F( i, j )= 
altrimenti
+ ∞
F ( 1,k ) = ottimo globale
F ( i , j ) = min g ( g ( f ( vi v j vk ), F ( i ,k ),vi ,vk ), F ( k , j ),vk ,v j )
i≤k ≤ j
1424
3
vj
vk
F ( 1,n ) = ottimo di f
Nell’implementazione F(1,k) è
calcolato iterativamente
vn
vi
Mesh Generation in due dimensioni
Un Problema aperto: Minimum Weight
Triangulation
Esiste un algoritmo polinomiale per determinare la triangolazione di
un point set che minimizzi la lunghezza totale dei lati (o che la
approssimi per O(1))? O il problema è NP-completo ? [Garey &
Johnson79]
Se la funzione sui lati è generale, non correlata alla lunghezza, MWT è
NP-completo [Lloyd77]
Qualunque triangolazione ha lunghezza totale O(n) volte l’ottimo
[Kirkpatrik80]
La triangolazione di Delaunay può essere fino a Ω(n) volte l’ottimo
[Manacher79]
Per poligoni convessi, la strategia greedy fornisce una approssimazione
O(1) [Levcopoulus77]
Mesh Generation in due dimensioni
Minimum Weight Triangulation: migliore
approssimazione
1. Partizione del convex hull in poligoni convessi
2. Triangolazione greedy dei poligoni
L’algoritmo fornisce una approssimazione O(log n) [Plaisted & Hong 87]
Mesh Generation in 3 dimensioni
Superfici 2D embedded in 3D
• Ricostruzione da sezioni planari (tiling)
• Marching Cubes
• Ball Pivoting
3D Mesh Generation
• Misure di Qualità
– Poliedri non triangolabili
– Punti di Steiner
• Triangolazione di poliedri
– Advancing front approach
– Medial axis transform
– Bubble Meshing (ricostruzione di domini non manifold)
• Triangolazione di Point set
– Alpha shapes
Generazione di Mesh Superficiali
Ricostruzione da sezioni planari [Bajaj96]
• Caso particolare di Point Set: i punti sono distribuiti su un
insieme di piani paralleli (slices)
• Input: insieme di slices, ognuna contenente un insieme di
poligoni
Problema: ricostruire la superficie dell’oggetto (degli oggetti)
conoscendo i contorni su ogni slice
Slice 1
Slice 2
Generazione di Mesh Superficiali
Ricostruzione della superficie da sezioni
planari
Criteri:
1. La superficie ricostruita e le regioni sugli slices formano un insieme di
superfici chiuse
2. L’intersezione tra una qualunque linea verticale passante per i due
slices e la superficie ricostruita è un punto, un lato o è vuota
3. Il resampling della superficie ricostruita deve consistere nei contorni
originali
Generazione di Mesh Superficiali
Il problema della corrispondenza
• Determinare in modo “corretto” (decidere in modo consistente)
la corrispondenza tra i contorni
Generazione di Mesh Superficiali
Il Problema della copertura (Tiling)
• Costruire le strisce di triangoli tra i contorni corrispondenti
Criteri:
• minima superficie
• minimo volume racchiuso
• minima lunghezza dei lati
Problema di matching su grafi
bipartiti
Generazione di Mesh Superficiali
Il Problema della copertura (Tiling)
Esistono coppie poligoni per cui non è possibile effettuare un tiling
Generazione di Mesh Superficiali
Il problema di branching
• Costruire la copertura (tiling) quando la corrispondenza tra i
contorni non è 1:1
• Le tecniche adottate in c,d ed e violano il criterio (3)
Generazione di Mesh Superficiali
Marching Cube:estrazione di isosuperfici
da dataset volumetrici [Lorensen87] :
Input:
- una griglia di punti regolare (quindi un insieme di celle cubiche)
dove ad ogni punto (vertice) è associato un valore reale f (campo)
- un valore scalare α
Output: superficie con valore α e con derivata lungo la normale
non nulla (isosuperficie)
Il valore del campo in un punto p è ottenuto per interpolazione
trilineare del valore nei vertici della cella che lo contiene
p01
p11
10
1
5
∑f
i , j =0
y
α = 7.5
f = 7.5
7
0,0
f ( x, y ) =
i , j =1
x
1
3
p00
p10
ij ⋅( 1 −
x )1−i x i ( 1 − y )1− j y j
Generazione di Mesh Superficiali
Marching Cube: configurazioni
• Configurazioni possibili: 2^8=256, ma si riducono a quattordici
classi di equivalenza considerando rotazioni mirroring e
complemento
Generazione di Mesh Superficiali
Marching Cube: LookUp Table
7
3
LookUpTable
5
0
1
2
3
2
4
0
6
1
0 0 0 0 0 0 0 1
76 5 4 3 2 10
: nil
: {e0,e4,e8}
: ….
: ….
….
…
255: nil
Per ogni permutazione del valore del campo rispetto alla soglia,
memorizza I triangoli della configurazione corrispondente
Generazione di Mesh Superficiali
Marching Cubes: Implementazione
• “Marching”. L’algoritmo procede cella per cella, riga per riga,
slice per slice. Da ogni cella si produce una triangolazione.
• Tranne che per le celle sul bordo della griglia considerare una
nuova cella richiede solo valutare tre nuovi edges
• Se non si vuole duplicare i vertici occorre ricordarsi i vertici
calcolati su edge condivisi da celle gia’ processate
Generazione di Mesh Superficiali
Marching Cubes: pros/issues
• Pros:
– Facile da implementare
– Veloce e non memory consuming
– Molto robusto
• Allora perche’ dall’87 ci hanno pubblicato fantastilioni di papers?
Issues:
• Consistenza. Produrre una mesh C0 e manifold: casi
ambigui
• Correttezza: Approssimare bene l’isosuperificie
• Mesh complexity: il numero di triangoli prodotti da MC non
dipende dalla forma della reale isosuperficie
• Mesh quality: triangoli arbitrariamente brutti
Generazione di Mesh Superficiali
Marching Cubes: casi ambigui
?
Generazione di Mesh Superficiali
Marching Cubes: casi ambigui
?
Generazione di Mesh Superficiali
Punti di sella
Valore del campo su una faccia
f ( 0 , x , y ) = c yz + d y + g z + h
 ∂f ( 0 , x' , y'

∂y

 ∂f ( 0 , x' , y'

∂x
)
d
c
)
g
= c y' + g = 0 ⇒ y' = c
= c z' + d = 0 ⇒ z' = -
α
α
f ( 0 , x' , y' )
Generazione di Mesh Superficiali
ELUT: Exhaustive LUT
…..
Face saddle points
body saddle point
ELUT:
Per ogni configurazione ambigua determina la triangolazione
coerente in base ai valori dei punti di sella
Generazione di Mesh Superficiali
Marching Tetrahedra
•
•
•
•
Celle tetraedrali invece che cubiche
Solo 3 configurazioni (dalle 2^4 combinazioni di segno del vertice)
Risove le ambiguita’
?
Generazione di Mesh Superficiali
Marching Tetrahedra
• Approccio originale: le celle cubiche vengono divise in 5 (o 6)
tetraedri.
– La suddivisione determina la topologia
• Body centered cubic lattice: aggiunta di un
vertice nel centro del cubo, suddivisione
a diamanti
– Suddivisione unica non ambigua
– Tutti tetraedri uguali
– Migliore superficie risultante
Generazione di Mesh Superficiali
Adaptive triangulation
• Invece di fermarsi alla configurazione iniziale si puo’ raffinare
(refine) selettivamente la superficie per approssimare meglio
l’isosuperficie
Generazione di Mesh Superficiali
Extended MC
Y
D2Y > 0
X
Surface
Exact intersection
point
D1Y < 0
D1X < 0
D3X > 0
Generazione di Mesh Superficiali
MC
tangent element
normal
Reconstructed
surface
normal
tangent element
Generazione di Mesh Superficiali
Extended MC
Marching Cubes
Extended Marching Cubes
Generazione di Mesh Superficiali
Discretized Marching Cubes
• Il punto di attraversamento dell’isosuperficie e’ sempre il punto
medio
• Stesse configurazione del MC standard
• Tutte le facce generate sono su un insieme si 13 piani
• Dopo l’estrazione viene effettuato un passo di “merging” per
ottenere poligoni coplanari piu’ grandi
Generazione di Mesh Superficiali
Dual Marching Cubes
• Un vertice per ogni patch generata da MC
• Un quad per ogni edge intersecato (i 4 vertici associati alle
patch delle celle che condividono l’edge)
• Tende ad eliminare triangoli brutti
Vertice del dual MC
Vertice di MC
Generazione di Mesh Superficiali
Generazione da punti: Ball Pivoting
• Una sfera di raggio ro “rotola” sui punti, ogni tripla di punti che
tocca contemporaneamente forma un triangolo
• La superficie creata e’ interpolante
• Raggio della sfera?
Generazione di Mesh Superficiali
Generazione da punti: Ball Pivoting
• BPA puo’ essere usato come tecnica di remeshing
– Distribuisci punti uniformemente su una superficie esistente
– Esegui BPA
• Quando e’ garantito che la topologia della mesh risultante e’
uguale alla mesh di partenza?
• Due condizioni sul sampling (o, dualmente, sul raggio della
sfera)
– L’intersezione di qualunque sfera di raggio ro con la superficie e’
omeomorfo a un disco
– Qualunque sfera di raggio ro centrata in un punto della superficie
contiene almeno un vertice
Mesh di Volume
Introduzione
Mesh Volumetriche
• Visualizzazione di oggetti o
campi scalari nello spazio
tridimensionale (es: applicazioni
diagnostiche in medicina)
• Risoluzione di sistemi di
equazioni differenziali su domini
non banali (analisi strutturale dei
materiali, deformable object
modeling)
Generazione di Mesh di volume
Misure di qualità
• Topologica:
1 n
εt =
δι − D
=
0
i
n
6 triangoli
D=
12 tetraedri
∑
• Geometrica:
Def ( più comune): L’Aspect Ratio di un tetraedro è il rapporto
tra il raggio della sfera circoscritta e il raggio di quella inscritta

r
 A − i
i =0
Ri

0.5 triangoli

A= 2
 11 tetraedri

1
εg =
m
∑
m



r
R
Generazione di Mesh di volume
Qualità geometrica: casi pessimi
Needle
Sliver
Wedge
Cap
La Triangolazione di Delaunay 3D:
minimizza il raggio della min-containment sphere con raggio
massimo
non ottimizza l’Aspect Ratio
Generazione di Mesh di volume
Triangolazione di Poliedri
Poliedri non triangolabili: es. di Schonhardt
Nessun vertice di un triangolo
può essere collegato ad uno
del triangolo opposto con un
segmento che non intersechi
una faccia [Schonhardt28]
Generazione di Mesh di volume
Punti di Steiner
I punti di steiner sono punti aggiuntivi all’input che:
• rendono possibile la triangolazione di ogni poliedro
• rendono possibile ogni ottimizzazione
Es: Il poliedro di Schonhardt può essere triangolato aggiungendo
un punto di Steiner
2
Si può costruire un poliedro semplice che necessita di n punti
di Steiner per poter essere diviso in regioni convesse (lower
bound per la triangolazione) [Chazelle91]
2
Ogni poliedro può essere triangolato con n punti di Steiner
È un problema NP-completo decidere se un poliedro è
triangolabile senza aggiungere punti di Steiner
[Garey&Johnson79]
Generazione di Mesh di volume
Triangolazione di Poliedri
Input: Descrizione di un poliedro limitato: vertici, lati e facce
• Punti di Steiner necessari in ogni caso pratico
Vantaggio
La superficie della triangolazione da costruire è nota è può
essere usata come base nella costruzione
Svantaggio
La superficie della triangolazione da costruire è nota e quindi
la triangolazione è constrained: più difficile e meno gradi di
libertà nelle ottimizzazioni
Generazione di Mesh di volume
Advancing Front Tetraedralization (AFT)
Idea: partire da una triangolazione della superficie (il fronte iniziale
della triangolazione 3D) e “riempire” il poliedro
Control Background
Fronte iniziale
Scelta di una faccia
Selezione di un quarto vertice e
costruzione di un tetraedro
Aggiornamento del fronte
N
Il fronte è vuoto
S
end
Generazione di Mesh di volume
Advancing Front Tetraedralization
Fronte iniziale
Costruzione fronte di offset
Triangolazione dello strato tra i fronti
Offset front
N
Il fronte è vuoto
Costruzione del fronte di offset
Generazione di punti lungo le
normali alle facce
+
correzione del fronte di offset
S
end
Generazione di Mesh di volume
Medial Axis Transform
• Idea: suddividere l’oggetto in un insieme di sottodomini per i
quali è più semplice costruire una mesh
• Def: Il medial axis di un poligono (poliedro) semplice è
l’insieme dei punti centro di un cerchio (una sfera) di diametro
massimale tangente al poligono (poliedro)
•
def: Il medial axis transform è il
medial axis + una funzione che
assegna ad ogni punto il valore del
raggio del corrispondente cerchio
• I medial vertices sono i punti di
discontinuità del primo ordine del
raggio
medial axis
•
Con un taglio su ogni medial edge si
può partizionare qualunque dominio
bi-dimensionale in regioni convesse
Generazione di Mesh di volume
Medial Axis Transform
• I sottodomini convessi sono ulteriormente partizionati in regioni
“meshabili” con mesh standard mediante Mid Point
Subdivision
Mid Point Subdivision
1. Aggiunta di un punto su ogni lato
2. Aggiunta di un punto interno
3. Nuovi lati tra i mid points sui lati e
quello interno
Risultato: le regioni ottenute sono
quadrilateri
Generazione di Mesh di volume
Medial Axis Transform
Condizioni per le mesh di una
regione:
m1 = n2

n1 = p2
p = m
 1
2
Condizioni per la corrispondenza tra
regioni adiacenti:
m1 + m2 = M 1 + M 2
L’insieme delle condizioni è un set di
vincoli di un problema di
ottimizzazione combinatoria
Generazione di Mesh di volume
Generazione di Mesh di volume
Bubble Meshing [Shimada-Gossard]
Physically-Based non-manifold meshing
Input:
• un dominio non-manifold
• una funzione di
distribuzione d(x,y,z)
Oss: un insieme di packed
spheres è “simile” al
diagramma di Voronoi dei
centri delle sfere
Output:
• una mesh triangolare hyriddimension
Generazione di Mesh di volume
Algoritmo:
1) filling: riempire il dominio con sfere di raggio proporzionale alla
densità specificata
2) relaxation: aggiustare la posizione delle sfere in modo da
minimizzare “overlapping” e “gap”
Filling (caso celle unidimensionali):
due sfere di vengono
posizionate agli estremi
dell’elemento
se non c’è overlapping, una
sfera viene aggiunta nel
punto medio
L’algoritmo procede
ricorsivamente fino al
riempimento
x2
x1
d ( x1 )
d ( x2 )
x2
x3
x1
Il raggio delle sfere è determinato dalla
funzione densità
Generazione di Mesh di volume
Relaxation:
La finale disposizione delle sfere è ottenuta stabilizzando la
posizione delle sfere rispetto alla forza agente su di esse definita
come:
al 3 + bl 2 + cl + d
f (l )= 
0
0 ≤ l ≤ 1.5 l0
1.5l0 ≤ l
f ( l0 ) = f ( 1.5l0 ) = 0 , f ' ( l0 ) = −k0
L’equazione del moto:
d 2 xi ( t )
dxi ( t )
mi
+
c
= fi ( t )
i
2
dt
dt
È integrata sul tempo (metodo Runge-Kutta del IV ordine)
Generazione di Mesh di volume
Controllo della popolazione:
- sfere con un eccessivo grado di overlapping sono eliminate
- vengono aggiunte sfere dove si sono creati dei “gap”
Generazione di Mesh di volume
Alpha Shapes [Edelsbrunner94]
Problema: qual è la superficie di un oggetto espresso come
insieme di punti?
Il Convex Hull dei punti è una possibile definizione della superficie
Def: Convex hull di { p0 , p1,K, ph }
CH ∈ ℜn
CH = I HSi , ∀p j ∈ CH
∀CH ' = I HS'i' ,∀p j ∈ CH ⇒ CH ⊆ CH '
Def: Empty half-space EHS:
Semispazio non contenente punti di S
Def: Convex hull di S
CH = ℜn \ U EHS
∞
Generazione di Mesh di volume
Alpha Shapes
• Def: empty α-ball Palla di raggio α non contenente punti del
point set S
• Def: α--Hull Complemento dell’unione di tutte le empty α-ball
αH = R n \ U EαBall
∞
• L’alpha-shape è un politopo non necessariamente convesso e
non necessariamente connesso derivabile dalla triangolazione
“pesata” di Delaunay con peso α∈[0,∞)
Generazione di Mesh di volume
Diagramma di Voronoi
Triang. Di Delaunay
Point Set
Alpha Diagram
Alpha triangolazione
Generazione di Mesh di volume
Delaunay Shape
Alpha Shape
• Se α = 0 l’ α -shape è il point set
• Se α →∞ l’ α -shape è il convex hull
• Un numero finito di soglie α 0 < α1 < α 2 < L < α h definisce tutte
le shapes possibili (al più 2n 2 − 5n )
Generazione di Mesh di volume
Generazione di Mesh di volume
Alpha Shapes: generalizzazioni
• Scale density alpha-shape
α non è una costante ma una funzione della densità dei punti:
migliora il risultato quando la densità di distribuzione dei punti
nel dominio non è costante
• Anisotropic alpha-shape
ellissoidi in luogo di sfere i.e. metrica definita da un ellissoide
alpha-shape
scaled
Scaled & anisotropic