-
Notifications
You must be signed in to change notification settings - Fork 0
/
AlphaReconciliation.txt
57 lines (42 loc) · 3.75 KB
/
AlphaReconciliation.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
An alpha shape is not necessarily equivalent to a hull (a surface defined on some points which encloses all
other points). We identify two possibilities for how an alpha shape could fail to be a hull:
- The alpha shape has a subset which is a valid hull, but possibly includes extraneous facets in the
interior
- The alpha shape does not include a valid hull
This document describes an algorithm for reconciling the first issue. In this application, the first is the
primary concern, so we focus on reconciling it. With proper interpolation, the second can be made unlikely.
Make no mistake that we do not claim this to be a general procedure which guarantees proper classification or
reconciliation of all hulls from alpha shapes. Rather, this is a computational method which performs well when
the numerical parameters render the problem "nice".
Procedure:
- Compute rectangular bounds on the point cloud (x_min, x_max, y_min, y_max, z_min, z_max).
- Using these bounds, select a point p_0 which is near the point cloud but outside of it. An arbitratily
distant point could be used instead, but this method avoids numerical issues when the coordinates of the
point cloud are entirely unknown and possibly far from the orgin. Additionally, include some element of
randomness in this selection. The exact selection process used here is as follows:
Let r1 and r2 be two random numbers uniformly sampled between 0 and 1. p_0 is then calculated as
x = x_min - 0.5 * (x_max - x_min)
y = y_min + r1 * (y_max - y_min)
z = z_min + r2 * (z_max - z_min)
- Now, randomly select any triangular facet in the alpha shape. Let the centroid of the triangle be p_1.
- Now construct a ray from p_0 --> p_1. This ray has the convenient property that it begins outside the
desired hull and must intersect at least one triangular facet on or inside the hull. (Barring an extremely
small chance that the ray is in plane with the facet selected above, which is addressed below)
- Now test every facet in the alpha shape to detect which intersect the ray. The facet which intersects
the ray closest to p_0 is necessarily on the hull (if a hull exists). Furthermore, we can compute a normal
vector to this facet which points "outside" the shape.
- Beginning with the facet identified above, traverse adjacent facets, marking them as part of the hull.
If a facet only has one neighbor, then it must be a part of the hull. If it has more than one, the normal
vector can be used to identify which is the outermost.
- At the completion of the traversal, we have either marked a set of facets which form the desired hull.
There is a very small chance of erroneous results due to a degenerate randomly selected p_0 and p_1, we
assume that the random choice of p_0 makes this unlikely.
It is possible that a facet could lack a full set of neighbors; this is likely to happen when two distinct
sections of a set join together. In fact, we use this algorithm to handle such cases elegantly. Any facet
detected by this algorithm which does not have a complete set of neighbors is excluded from the final results.
However, if all of the points in that facet are not included in some other valid facet, this is reported as an
error and the method terminates. This has the benefit of avoiding inaccurate interpolation when two distinct
sections of a set join together while behaving elgantly in the presence of concavities.
There is one significant possibility that this algorithm does not consider. There could be a valid surface
which does not contain all points in the cloud. In our case this is unlikely due to the interpolation
strategy and we do not address it here. This procedure could be extended to address that case.