# Evelope Containment Checking Through Distance Field

In the field of geometry processing, meshing algorithms often require determining whether a surface deviates a certain distance from another surface in 3-dimensional Euclidean space. In discrete settings, this problem involves checking if a triangle T lies within a specified distance of a triangle mesh surface S. We propose a two-stage approach to address this problem: first, we construct an approximated signed distance field F for the triangle mesh surface S; then, we predict if the evaluations of F on triangle T are within the specified distance. We aim to achieve exactness by incorporating a conservative stage one and an accurate stage two.

[Working log](https://hackmd.io/zQr8TaXpRRy8h57FbXeWuQ)
---

computing Hausdorff distance: (https://content.iospress.com/articles/integrated-computer-aided-engineering/ica544)

Given a surface $S$ and a target $e$, an edge in 2D or a triangle in 3D, decide whether $e$ is within a small distance $\epsilon$ of $S$.

There are two stages for this algorithm:
1. construct a distance field $F: M \to \mathbb{R},$ where $S \subset M$ (in floating point)
2. check if the condition $-\epsilon < F|_e < \epsilon$ holds

## Stage 1: Construct Distance Field
The domain of $F$ is a mesh M such that every node of the M will store the distance to the input surface $S$.

$F$ is piecewise linearly defined on the interior of mesh $M$ as
$$F_t(x) = \sum_{i \in t} s_i \phi_i^t(x)$$

## Stage 2: Check the target
When point $x \in T$, a simplex,
$$F_T'(x) = \sum_{i \in T} s_i \nabla \phi_i^T$$
since $\phi_i^T(x)$ is linear function, $\nabla \phi_i^T$ is constant. The min or max of $F | _e$ is taken at the end points of $e$ inside $T$.

[Jupyter Notebook Experiments](http://localhost:8888/notebooks/PycharmProjects/test/InstersectionsCheck.ipynb#2D-cases-simulation)

A possible good try to represent intersections: [**plucker coordinates**](http://users.uop.gr/~nplatis/files/PlatisTheoharisRayTetra.pdf).

#### 3D cases

When a plane intersects with a tetrahedron $TT$, the possible cases are


Considering a triangle $T$ and tetrahedron $TT$'s facets $f_i, i=1,2,3,4$, $F|_T$ inside $TT$ is bounded by
$$
\min{F(S)} \leq F|_T^{TT} \leq \max{F(S)}
$$
where $S = \{$`LIP` $(e_i, f_i)$ $\cup$ `LIP` $(l_i, T)$, $e_i \in E(T), f_i \in F(TT), l_i \in E(f_j) \}$
where $E(x)$ is the edge set of triangle $x$, $F(xx)$ is the facet set of tetrahedron $xx$.
<details>
<summary> Psudocode</summary>

- For each edge $e = (s,r)$ of tetmesh, check whether $$- \epsilon \leq F(r) \leq \epsilon \\
-\epsilon \leq F(s) \leq \epsilon$$
- if yes, check whether triangle $T = (u,v,t)$ intersects with $e=(s,r)$
- if yes, check
$$
\alpha(F(s) - F(r)) < \beta(\epsilon - F(r))\\
\alpha(F(s) - F(r)) > \beta(-\epsilon - F(r))
$$
where $\alpha = det(r-t, u-t, v-t), \beta = det(r-s, u-t, v-t)$.
- For each edge $e = (s,r)$ of the Triangle $T$
- For each triangle facet $tt = (u,v,r)$ of tetmesh, check whether
$$
-\epsilon \leq F(u), F(v), F(r) \leq \epsilon
$$
- if yes, check whether $e = (s,t)$ intersects with $tt=(u,v,r)$
- if yes, check
$$
-\gamma \epsilon < \alpha(F(v)- F(r)) + \beta(F(u) - F(r)) + \gamma F(r) < \gamma \epsilon
$$

</details>

## LIP($l_i$, T) intersection of one edge of tetrahedron and the triangle

Consider one edge $l_i$ of tetrahedron $TT$, determined by $\bf{s}$, $\bf{r} \in \mathbb{R}^3$, the triangle $T$ is determined by $\bf{u}$, $\bf{v}$, $\bf{t}\in \mathbb{R}^3$.

$$
F(P) = F(r) + \frac{\alpha}{\beta} \cdot (F(s) - F(r))
\\
\alpha = det(r-t,u-t,v-t), \beta = det(r-s,u-t,v-t)
$$
where $\det(\vec{u}, \vec{v}, \vec{w})$ denotes the determinant of the matrix formed by the column vectors $\vec{u}, \vec{v}, \vec{w}$.

So need to check
$$
\alpha(F(s) - F(r)) < \beta(\epsilon - F(r))\\
\alpha(F(s) - F(r)) > \beta(-\epsilon - F(r))
$$
<details>
<summary>Some expansion for beta</summary>

$\beta = \begin{aligned}
&r_1t_2u_3-r_1t_2v_3-r_1t_3u_2+r_1t_3v_2+r_1u_2v_3-r_1u_3v_2-r_2t_1u_3+r_2t_1v_3+r_2t_3u_1- \\
&r_2t_3v_1-r_2u_1v_3+r_2u_3v_1+r_3t_1u_2-r_3t_1v_2-r_3t_2u_1+r_3t_2v_1+r_3u_1v_2-r_3u_2v_1 \\
-&s_1t_2u_3+s_1t_2v_3+s_1t_3u_2-s_1t_3v_2-s_1u_2v_3+s_1u_3v_2+s_2t_1u_3-s_2t_1v_3-s_2t_3u_1+ \\
&s_2t_3v_1+s_2u_1v_3-s_2u_3v_1-s_3t_1u_2+s_3t_1v_2+s_3t_2u_1-s_3t_2v_1-s_3u_1v_2+s_3u_2v_1
\end{aligned}$

</details>

## LIP($e_i$,$f_i$), $e_i\in E(T)$, $f_i \in F(TT)$ intersection of one edge of triangle and a facet of tetrahedron

Consider an edge $s,t$ of triangle $T$ and a facet $u,v,r$ of the tetrahedron $TT$.

$$
F(p) = \frac{\alpha}{\gamma} \cdot F(v) + \frac{\beta}{\gamma}\cdot F(u) + \frac{\gamma - \alpha - \beta}{\gamma} \cdot F(r)\\
\alpha = det(s-r, u-r, t-s), \beta = det(v-r, s-r, t-s), \gamma = det(v-r, u-r, t-s)
$$

### Accuracy discussion
1. rational representation: when converting a floating point to a rational
2. [**GMP**](https://https://home.cs.colorado.edu/~srirams/courses/csci2824-spr14/gmpTutorial.html) system working principle:
3. filter + interval operation

## Problems to discuss:
0. Exactness/accuracy discussion
1. sliding window for sampling and creating the distance field.
2. the checking stage's optimization is heavily depending on the form of distance field

## References
0. 3d collisions
https://gdbooks.gitbooks.io/3dcollisions/content/Chapter4/point_in_triangle.html

1. Checking $F|_e$ within a range without calculating its minmum and maximum, reference: https://cs.nyu.edu/exact/core_pages/downloads.html

2. Some but not all tetrahedron and triangle relations: https://cims.nyu.edu/gcl/papers/2020-fTetWild.pdf

3. 2d: Line segments intersections: https://blogs.sas.com/content/iml/2018/07/09/intersection-line-segments.html#:~:text=Define%20b%20%3D%20q1%20%2D%20p1%20and,the%20segments%20do%20not%20intersect.

4. 3d: line segment intersects with a triangle plane
https://math.stackexchange.com/questions/1417693/segment-intersecting-a-tetrahedron

5. tetrahedron understanding: https://www.quantamagazine.org/triangles-are-easy-tetrahedra-are-hard-20220131/

6. Ray-tetradheron intersection **plucker coordinate**: http://users.uop.gr/~nplatis/files/PlatisTheoharisRayTetra.pdf

7. line-segment and triangle intersection: https://members.loria.fr/SLazard/ARC-Visi3D/Pant-project/files/Line_Segment_Triangle.html

## Directions:
Experiment in rational number(infinite precision ): https://realpython.com/python-fractions/