Between the two ears in the following bunny images, there are some degenerate triangles I want to detect. It looks like a volume-less thin slits.

If the question is not clear, please let me know.


enter image description here

enter image description here


1 Answer 1


What about this:

Step 1: For each edge $P_iP_j$, look at the two triangles that share it: $P_iP_jP_k$ and $P_lP_jP_i$.

Step 2: Compute the counter-clockwise normal on each of the two triangle: $$\vec{n}_{ijk} = \frac{\vec{P_iP_j} \times \vec{P_jP_k}}{\|\vec{P_iP_j} \times \vec{P_jP_k}\|} \,\,\, \text{ and }\,\,\, \vec{n}_{lji} = \frac{\vec{P_lP_j} \times \vec{P_jP_i}}{\|\vec{P_lP_j} \times \vec{P_jP_i}\|}$$

Step 3: Check the angle between the two normals: $\big(\vec{n}_{ijk} \cdot \vec{n}_{lji}\big) \approx -1$ (e.g. something like $\big(\vec{n}_{ijk} \cdot \vec{n}_{lji}\big) \leq -1 + \varepsilon$) means it is close to being $180^{\circ}$.

Step 4: In this case, you can remove the edge $P_iP_j$ and merge the two vertices $P_K$ and $P_l$: Replace $P_k$ and $P_l$ by the midpoint $P_m$ of the straight segment $P_kP_l$: $$P_m = \frac{1}{2}(P_k + P_l)$$

Step 5: Connect all remaining vertices, adjacent to the former vertices $P_k$ or $P_l$, to the new vertex $P_m$. Thus, the new triangulation has now three fewer edges and two fewer triangular faces.

Continue to iterate this procedure until there are no edges whose normals have the property $\big(\vec{n}_{ijk} \cdot \vec{n}_{lji}\big) \approx -1$.

Maybe this algorithm will remove the triangles between the bunny's years.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.