Triangulate faces sometimes produces degenerate triangle faces #103913

New Issue

Jesse Yurkovich · 2023-01-16T11:35:29+01:00

Jesse Yurkovich commented

2023-01-16 11:35:29 +01:00

System Information
Operating system: Windows-10-10.0.19044-SP0 64 Bits
Graphics card: NVIDIA GeForce GTX 1070 with Max-Q Design/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 511.09

Blender Version
Broken: version: 3.5.0 Alpha, branch: master, commit date: 2023-01-04 23:36, hash: a7cc6e015c
Broken: version: 3.3.2, branch: master, commit date: 2022-12-06 18:19, hash: bf24652e38
Broken: version: 2.93.10, branch: master, commit date: 2022-08-02 18:21, hash: 0a65e1a8e7
Broken: version: 2.79 ...
Worked: n/a

Short description of error
While investigating #103707 (UV Select Overlap incorrectly detects some faces as overlaps) we noticed bad triangulation coming from BLI_polyfill_calc. Sure enough, I can reproduce the effect using regular geometry editing as well.

Exact steps for others to reproduce the error
triangulate_faces.blend

Load attached .blend or create an ngon face similar to screen shot 1
Triangulate the face (CTRL+T) using the ngon "CLIP" mode (Beauty mode does not have the issue). Notice that while there's 6 faces, only 5 can be seen (screen shot 2)
1 of them is degenerate and can be seen if you pull a vertex away (screen shot 3)

[Shot 1]

[Shot 2]

[Shot 3]

**System Information** Operating system: Windows-10-10.0.19044-SP0 64 Bits Graphics card: NVIDIA GeForce GTX 1070 with Max-Q Design/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 511.09 **Blender Version** Broken: version: 3.5.0 Alpha, branch: master, commit date: 2023-01-04 23:36, hash: `a7cc6e015c` Broken: version: 3.3.2, branch: master, commit date: 2022-12-06 18:19, hash: `bf24652e38` Broken: version: 2.93.10, branch: master, commit date: 2022-08-02 18:21, hash: `0a65e1a8e7` Broken: version: 2.79 ... Worked: n/a **Short description of error** While investigating #103707 (UV Select Overlap incorrectly detects some faces as overlaps) we noticed bad triangulation coming from `BLI_polyfill_calc`. Sure enough, I can reproduce the effect using regular geometry editing as well. **Exact steps for others to reproduce the error** [triangulate_faces.blend](https://archive.blender.org/developer/F14152681/triangulate_faces.blend) - Load attached .blend or create an ngon face similar to screen shot 1 - Triangulate the face (CTRL+T) using the ngon "CLIP" mode (Beauty mode does not have the issue). Notice that while there's 6 faces, only 5 can be seen (screen shot 2) - 1 of them is degenerate and can be seen if you pull a vertex away (screen shot 3) [Shot 1] ![image.png](https://archive.blender.org/developer/F14152690/image.png) [Shot 2] ![image.png](https://archive.blender.org/developer/F14152692/image.png) [Shot 3] ![image.png](https://archive.blender.org/developer/F14152694/image.png)

Jesse Yurkovich commented

2023-01-16 11:35:29 +01:00

Added subscriber: @deadpin

Germano Cavalcante commented

2023-01-16 20:27:32 +01:00

Added subscriber: @mano-wii

Germano Cavalcante commented

2023-01-16 20:27:32 +01:00

Changed status from 'Needs Triage' to: 'Needs Developer To Reproduce'

Germano Cavalcante commented

2023-01-16 20:27:32 +01:00

It is known that some of Blender's triangulation methods can create degenerate triangles.
This is old stuff and as far as I know it's not considered bug.

We have to be careful changing something so ingrained in Blender's code.

I'll let the #modeling team decide what to do here.

It is known that some of Blender's triangulation methods can create degenerate triangles. This is old stuff and as far as I know it's not considered bug. We have to be careful changing something so ingrained in Blender's code. I'll let the #modeling team decide what to do here.

Campbell Barton referenced this issue from a commit

2023-02-08 07:11:15 +01:00

Fix #103913: Triangulate sometimes creates degenerate triangles

Campbell Barton closed this issue

2023-02-08 07:11:16 +01:00

Blender Bot added

Status

Resolved

and removed

Status

Needs Info from Developers

labels 2023-02-08 07:11:17 +01:00

Campbell Barton commented

2023-02-08 07:33:15 +01:00

@deadpin committed a fix however this is an edge case, had there been significant down-sides or slow-downs to avoiding the case in this report, then I think it would be reasonable to close. Even with the fix - near zero area faces are still possible so from a user perspective the problem may still exist in some situations.

This is the reason "Beauty" is the default tessellation method when triangulating N-Gons, as noted in code-comments, more work could be done to avoid small faces but this would take extra computation. In cases where this is needed the caller might as well use beauty-tessellation. The main reason to keep ear-clip is that it matches tessellation used in the 3D view-port.

@deadpin committed a fix however this is an edge case, had there been significant down-sides or slow-downs to avoiding the case in this report, then I think it would be reasonable to close. Even with the fix - *near* zero area faces are still possible so from a user perspective the problem may still exist in some situations. This is the reason "Beauty" is the default tessellation method when triangulating N-Gons, as noted in code-comments, more work could be done to avoid small faces but this would take extra computation. In cases where this is needed the caller might as well use beauty-tessellation. The main reason to keep ear-clip is that it matches tessellation used in the 3D view-port.

Joseph Eagar referenced this issue from a commit

2023-02-11 21:53:09 +01:00

Fix #103913: Triangulate sometimes creates degenerate triangles

Campbell Barton referenced this issue from a commit

2023-02-12 06:28:30 +01:00

Tests: add polyfill2d test to ensure the result has no zero area tris

Sign in to join this conversation.