2
$\begingroup$

I am currently reading Differentiable Surface Triangulation presented at Siggraph Asia 2021.

I think most of the paper is clear to me, though I keep re-reading through to see if I miss details.

The bit "Parametrizing triangle existence with respect to $V$" is what's confusing me, which I quote below for reference, questions are in the stated in bold.

For any triangle $t_i = (v_j,v_k,v_l)$, we consider the three reduced Voronoi cells $a_{j|i}, a_{k|i}, a_{l|i}$ respectively around the triangle's vertices $v_j,v_k,v_l$, where we define a reduced Voronoi cell created by ignoring the two other vertices of the triangle.

Question 1: Just to make sure I understood this definition correctly. If The Voronoi cell around $v_j$ is defined as

$a[j] := \bigcap_{m \neq j} H_{j < m}$ Namely the intersection of all the half spaces around $v_j$. Isn't the reduced cell just equivalent to:

$$ a_{j|i} := \bigcap_{m \neq j,k,l} H_{j < m} \text{ ?} $$

Continuing ...

The triangle $t_i$ is part of the triangulation T as long as its circumcenter $c_i$ remains inside the reduced Voronoi cells around its vertices. Similarly $t_i$ is not part of $T$ as long as its circumcenter remains outside its three reduced Voronoi cells. Not that, by construction, the circumcenter simultaneously enters or exits the three reduced Voronoi cells.

I am trying to make sure I fully understand the statement above, which might sound trivial but it is a bit confusing to me. I believe the purpose of such statement is to show an equivalence between two equivalent formulations of the existance function defined earlier in the paper. I'll give the necessary definitions below but they're written earlier in the paper and then I'll try to formulate the questions.

Preliminary Definitions (from the paper) If $V$ is a set of vertices, $T* = \left\{ (v_j,v_k,v_l) : v_j, v_k,v_l \in V \right\}$ (sets of all possible triangles). If $T \subset T^*$ we define an existance function $e_i : T^* \to \left\{ 0, 1\right\}$ as $$ e_i = \begin{cases} 1 & t \in T \\ 0 & t \notin T \end{cases} $$ We also define $a_j$ as the Voronoi cell around the vertex $v_j \in V$

With such definitions the can re-define the existance function as

$$ e_i = \begin{cases} 1 & \text{if } c_i \in c_j \cap a_k \cap a_l \\ 0 & \text{otherwise} \end{cases} \tag 3 $$

Which the statement quoted justifies the equivalence to the following

$$ e_i = \begin{cases} 1 & \text{if } c_i \in a_{x | i} \text{for any } x \in \left\{j,k,l\right\} \\ 0 & \text{otherwise} \end{cases} \tag 4 $$

Now with reference with (4) and the quote I'll reformulate my question

Question 2: The first bit of the quote

The triangle $t_i$ is part of the triangulation $T$ as long as its circumcenter remains inside the the reduced Voronoi cells around its vertices.

The way I interpreted this statement is the following $t_i \in T \iff c_i \in a_{j | i} \cap a_{k | i} \cap a_{l | i}$ Is this interpretation correct?

Question 3: Assuming my interpretation is correct I've tried to prove it because I can't see it intuitively but I got stuck so I have a doubt my understanding is actually correct

Proof: $t_i \in T \Rightarrow c_i \in a_{j | i} \cap a_{k | i} \cap a_{l | i}$

This is easy because $t_i \in T \Rightarrow c_i \in a_j \cap a_k \cap a_l$. Since each Voronoi cell is a subset of the reduced one (this is evident from the definition) we have $t_i \in T \Rightarrow c_i \in a_{j | i} \cap a_{k | i} \cap a_{l | i}$

The other direction ($a_{j | i} \cap a_{k | i} \cap a_{l | i} \Rightarrow t_i \in T$) I cannot manage to show it so I suspect I don't get the quote fully.

Question 4 Moreover formula (4) returns $1$ is $c_i \in a_{x | i} \text{ for any } x \in \left\{j,k,l\right\}$ which I might actually interpret as $$ t_i \in T \iff c_i \in a_{j | i} \cup a_{j | k} \cup a_{j | l} $$ Notice the "union" instead of intersection. Is this interpretation the correct one of the quote then?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.