Page MenuHome

Ngons creating unwanted lines in Freestyle
Open, Confirmed, MediumPublic

Description

Windows 7 Pro 64-bit
Intel Core i7-4770K CPU @3.50GHz
ASUS nVidia GeForce GTX 760 2GB GDDR5 DirectCU Mini

Broken: (example: 2.70 47e9057

...also broken in Blender official 2.69 and official 2.70

Freestyle has a problem rendering Ngons in such a way that extra, unwanted lines are generated.

It appears to be a faulty subdivision of the Ngons during that part of the render process where the information is passed through to Freestyle for creating the strokes.

If the Ngons are first triangulted – either by hand or else using the triangulate modifier – then the faulty lines do not appear in the Freestyle render.

The images show the problem.

Image 01 shows the render with the faulty lines indicated.

Image 02 shows the mesh. The Ngons that give the problems are selected.

Image 03 again shows the mesh, this time with the Ngons triangulated.

Image 04 shows the correct render following triangulation of the Ngons that give the trouble.

Here is the blend file.

Details

Type
To Do

Event Timeline

Ignatz (ignatz) added a project: BF Blender.
Ignatz (ignatz) set Type to Bug.
Ignatz (ignatz) added a subscriber: Ignatz (ignatz).
Ignatz (ignatz) created this task.
Ignatz (ignatz) raised the priority of this task from to Needs Triage by Developer.

Oh, I forgot to mention that the unwanted lines do not always show up in the same place.

If the rotation of the mesh object is changed or the camera angle is altered then Freestyle may render (or sometimes not) other unwanted lines within the same Ngons.

Willi (willi) added a subscriber: Willi (willi).EditedMay 12 2014, 7:49 PM

The problem is that the large ngon and the adjacent faces are not completely plane. Not all x and y values of all vertices belonging to a vertical line are also not completely equal. There are very small deviations, hence an edge is detected. For example -15.899984 and -15.899986.

Select these vertices, then Scale Y 0 Enter:

Same for the vertices on a same vertical line to the right. Now the freestyle edge has disappeared:

However, if you have to do it for the whole mesh (or many meshes), I don't know if there are edge detection settings to avoid this additional work.

EDIT: And wherever a mirror modifier is applicable, make use of it. ;)

Tamito Kajiyama (kjym3) triaged this task as Confirmed, Medium priority.May 13 2014, 6:08 AM

I believe the unwanted lines come from so-called degenerate faces (i.e., those whose area is zero). It is a known limitation that Freestyle line visibility calculation tend to fail with degenerate triangles and quads, although Freestyle makes attempts to fix degenerate faces as much as possible.

It is recalled that ngons are decomposed into a set of triangles and quads through an algorithm called tessellation. The default tessellation algorithm used for rendering seems to produce degenerate triangles from the ngons in the provided mesh data. Another tessellation algorithm available as the Triangulate mesh modifier does not have that issue.

As a workaround, I suggest using the Triangulate mesh modifier for now to avoid the issue of degenerate faces in Freestyle.

@Campbell Barton (campbellbarton): Is there any chance that the default tessellation algorithm used for rendering is replaced with a better algorithm such as the one available in the Triangulate mesh modifier that does not suffer from degenerate faces? (see my previous comment on this task for the rationale.)

For any further independent testing, I was using an extended version of BKE_mesh_validate()

to check degenerate faces from within Python as follows:

import bpy
ob = bpy.context.scene.objects['Body']
me = ob.data
me.calc_tessface()
me.validate(verbose=True)

I do not know if this helps, but I thought to provide some additional information regarding the origin of the mesh object that produces these.

The original object was made using the mirror modifier. This produced the acceptable render result which can be seen in image "A"... and the mesh, itself, in image "B".

Following that, the mirror modifier was applied, producing the mesh as seen in image "C". The render of this was the samel as in image "A".

Finally, I decidet od consolidate the planer faces in my mesh model. I did this by selecting one and then all linked planer faces using Ctrl-Shft-Alt-F

These selected faces were then converted to a single Ngon by pressing 'F'. The mesh result of that is seen in image "D".

With this Ngon the render now produces unwanted lines as seen in image "E".

I have attached the blend file also.

I'm using freestyle for hatching on surfaces and this happens often. Isn't it a solution to filter out triangles with too short edges? After the tesselation. Or maybe not completely filter out, but force their normal values to the average of the neighbours... Also sometimes floating point over/underflows (Inf or NaN results) happen specially when there are near-zero distances. Are these cases handled?

My example is a subdivided plane. I just created the plane, subdivided it and marked the edges I need. If you render, you can see the extra line in the middle.

I have an idea to solve this...if the following is possible: I think this happens because during triangulation there comes some degenerated triangles where it is not possible to calculate the normals correctly. But there is the original polygon (what is triangulated) with a hopefully correct normal... Isn't it possible to use the original polygon's normal instead of calculating the normals for the generated triangles?

A new example file is here, as simple as possible. It is a plane with some subdivisions. If you render it, there is the problematic line in the middle and nothing else (tested with 517094a)

Now I know the normals are calculated in the init_render_mesh() function of render/intern/source/convertblender.c. For the degenerated triangles of the tesselated ngons, this function gives wrong normal vectors. My question, why is it necessary to calculate the normals for each triangles individually? You get different normals only if the original ngon is not completely flat. If the triangles could use the normal calculated from the original ngon, 1) it's a speedup, 2) there are no wrong normals for the degenerated triangles.

Alternatively, it could use this only for the degenerated triangles.

Argh, there are other problems here. In line 2521 of this convertblender.c there is

if (len==0) obr->totvlak--;

This means if the cross product in the normal calculation was exactly(!) zero, drop the face away. But this actually won't drop most of the degenerated triangles because of floating point inaccuracies (I've tested this in debugging and many passed). An "if (len < epsilon)" form probably better. But... if you drop the face away, its edge features are also dropped... So for example a freestyle marked edge could disappear if both connecting (degenerated) faces are dropped. Perhaps some freestyle features could work more-or-less correctly only because this (len==0) comparison is weak... Something really wrong in this logic here!

Hi @Fazekas Laszlo (totoro), thanks for the continued effort on the investigation of the issue.

It is true that dropping degenerate faces is not a good idea as you pointed out. By dropping them, it is also likely that we have new (unwanted) border edges.

Ngons are not necessarily flat, so using "the original polygon's normal" is not a general solution.

Thanks to your observation about unwanted crease lines due to wrong normals of degenerate faces, I tried a partial fix of the reported problem:

.

It is recalled that an edge is considered a crease line if the angle between the two adjacent faces A and B on both sides of the edge is smaller than a threshold. The angle is computed based on the face normals of A and B. The reported problem is observed when at least one of the two faces (B for instance) is degenerate, and thus the face normal cannot be computed properly.

The solution implemented here is to use the face normal of a non-degenerate adjacent face of B that does not touch the edge in question.

This solution may and may not work depending on input scenes, because degenerate face detection is a tricky problem by itself. Finding degenerate faces relies on a threshold parameter whose value (set to 5e-5 for now) is difficult to uniquely determine so as to work in all input scenes.

The patch works fine with

and , but not perfectly with . I would not merge the fix into Git master, because it is also not a general solution and may create new problems.

Many years of Freestyle development have shown that addressing degenerate faces in Freestyle is a very tricky exercise. It is my impression that degenerate faces coming from Ngons should be addressed in the first place through a better tessellation algorithm.

Hello @Tamito Kajiyama (kjym3),

About the better tesselation algorithm, I see how complicated the bmesh code now, so I don't expect too much about it. Probably most of the degenerated faces could be eliminated if these edge segments are handled the same way as the concave parts.

The loss of the edge mark flag because of the degenerated faces is a real possibility I think. But removing the (len==0) is probably dangerous, too...

About the threshold: perhaps a small value multiplied by the perimeter of the polygon.

However, I've made a patch for convertblender.c you may take a look at this too. I'm not absolutely sure it is correct but it's here:

Put the code below after L3375 in render/intern/source/convertblender.c (after the normals calculation). It's also not perfect for the FS_bad_Ngon_render.blend...

#ifdef WITH_FREESTYLE

							if (len < 0.00001) { /* please put a correct epsilon here */

								/* degenerated face, replace normal from the original poly */

								int index = (index_mf_to_mpoly) ? index_mf_to_mpoly[a] : a;
								MPoly *mp= me->mpoly+index;

								BKE_mesh_calc_poly_normal(mp,me->mloop + mp->loopstart,me->mvert,vlr->n);
								mul_transposed_m3_v3(imat, vlr->n);
								len= normalize_v3(vlr->n);
								negate_v3(vlr->n);
							}

#endif

Unfortunately I think my solution is not correct with modifiers. The vertices must come from the derivedmesh, and not from the original mesh. But I don't know how to calculate the normal then.

Now I'm looking at your solution and thinking what is the best sign of a degenerate face. I think it's not important how the triangle behaves generally, only how it behaves in the calculation of its normal. Perhaps the length of the cross product vector (ie. the area of the triangle) is a good sign and it is calculated already in convertblender.c . Maybe you can put a marking flag there if (len < threshold). There are already such Freestyle related flags for the edges and the face mark. In my tests I observed that the degenerate triangles also have a valid but wrong normal vector. It was a very short cross product vector originally, enlarged to 1.0 length. But together with its floating point truncations and inaccuracies and this causes the wrong direction. But maybe this wrong vector still contains some information about the right direction of the normal.

What if the program compares this wrong normal with the non-degenerate neighbours and choose the closest one to replace it?

@Tamito Kajiyama (kjym3): I've tried to set a new face flag in convertblender.c, forget it, not better at all. But choosing the best matching normal seems good even with

, so here is my version to replace your FEdgeXDetector::getFaceNormal() :

Something more information:

Now I've got evidence that the if (len == 0) obr->totvlak--; row in render/intern/source/convertblender.c (line 3381) removes some necessary degenerate triangles from the mesh. This causes undetectable holes in the mesh for Freestyle. Some artefacts are there because of this. If I remove this line (no triangles dropped) it seems everything is fine, no crash, good rendering etc. I don't know why is this line in the code. Can somebody check this?

I've tried another version of getFaceNormal() where I used dot product instead of the length of cross product. It's faster, but strangely leaves more fake lines. Maybe the normal vector tends to invert the direction for degenerate faces, I don't know.

As a conclusion, I think there is no good solution for this. The triangulate modifier does the trick, from now I'll use it always with Freestyle. A possible hacky solution to call an extra triangulate modifier at the end of the modifier stack if:

  • freestyle enabled,
  • crease edge enabled in freestyle,
  • there is no triangulate modifier on the stack,
  • there are ngons in the mesh.

@Tamito Kajiyama (kjym3), thank you for your effort to solve this. Now I recommend to close this thread.

note, that polyfill can be modified to support this specific case, but I don't really want to apply it, since similar errors will remain with different ngons.

Really freestyle should be able to ignore internal edges (edges created by tessellation).

Nevertheless, heres a patch which tweaks tessellation.

1diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c
2index dd829e5..7f680d7 100644
3--- a/source/blender/blenlib/intern/polyfill2d.c
4+++ b/source/blender/blenlib/intern/polyfill2d.c
5@@ -54,7 +54,7 @@
6 #define USE_CLIP_EVEN
7 #define USE_CONVEX_SKIP
8 /* sweep back-and-forth about convex ears (avoids lop-sided fans) */
9-#define USE_CLIP_SWEEP
10+// #define USE_CLIP_SWEEP
11 // #define USE_CONVEX_SKIP_TEST
12
13 #ifdef USE_CONVEX_SKIP
14@@ -167,9 +167,10 @@ static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip);
15
16 BLI_INLINE eSign signum_i(float a)
17 {
18- if (UNLIKELY(a == 0.0f))
19+ const float e = 1e-5f;
20+ if (UNLIKELY(a == e))
21 return 0;
22- else if (a > 0.0f)
23+ else if (a > e)
24 return 1;
25 else
26 return -1;

Setting this as a TODO. Freestyle just doesnt handle near-zero area filled-faces at the moment. - http://wiki.blender.org/index.php/Dev:2.5/Source/Development/Todo/Render#Render_Engine_.28Freestyle.29