search

coin3d / coin

Coin3D core library
BSD 3-Clause "New" or "Revised" License
289 stars 109 forks source link

Render is missing Triangles #177

Open VolkerEnderlein opened 5 years ago

VolkerEnderlein commented 5 years ago

Original report by Anonymous.

Attachments: Render is missing triangles.iv | (Issue 177) Render is missing triangles (round 2).iv | 2019-Sept-23_missing_triangles.iv | Issue_177_Render_is_missing_Triangles_2019-Nov-4.iv

A Part of two IndexedFaceSet (IFS) are not rendering.

I saw these flaws in a larger program I pared down the graph, and opened Open the attached .iv in a simple program with an ExaminerViewer, and saw the same problems.

While working with the .iv, I found that the problem is specific to certain data I can "fix" the problem by - Rem'ing out the camera I can "fix" the problem by - Rem'ing out the RotationXYZ or certain Transforms (see additional notes inside of the .iv)

I wonder if the problem is related to an initial rendering, which requires the camera to initially view certain geometry.

In the .iv I have 3 placements of the same IFS, I've found that all 3 will render the same (either correct or flawed)

VolkerEnderlein commented 5 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

Hi,

I could reproduce the issue with current source code version of Coin.

But when displayed with a very outdated TGS Inventor version 2.5 (from 2000) the file displayed fine. So it’s definitely a Coin bug.

Cheers, Volker

VolkerEnderlein commented 5 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

Just prepared a pull request #360 that handles this issue (same issue and PR number is pure coincidence). Can you test that PR in your larger environment and report back whether it solves the effects and more important does not harm performance?

If you ever face a similar bug again and need a quick fix, you may set the environment variable COIN_PREFER_GLU_TESSELLATOR to 1. Then, if available, the tessellation is done by the underlying GLU library. The Coin devs considered it to be buggy, but it did the right thing and helped me to figure out where to start looking for the bug.

Cheers, Volker

VolkerEnderlein commented 5 years ago

Original comment by Mark Goldberg (Bitbucket: MarkGoldberg, GitHub: MarkGoldberg).

Thank you so much for your work on this issue. I'm truly impressed.

Your change did fix quite a few cases.

But we’re still seeing the problem.

Here is another .iv, I haven’t simplified anywhere close to as much as I simplified the initial report.

It’s just one example, I have no idea if it’s truly representative.

Note: sorry for not responding sooner, I only noticed your update on the issue today. I am now "watching" the issue.

NOTE: SET COIN_PREFER_GLU_TESSELLATOR=1 does solve the problem with this example .iv
however in my real program with other examples, with that setting I got dozens of

"Coin error in SbGLUTessellator::cb_error() GLU library tessellation error: 'need combine callback'
and one part of the graph still failed even with the setting, but the rendering was much better than without the setting.
In one case (so far) the rendering is worse with the environment variable.

VolkerEnderlein commented 5 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

Thanks for your feedback Mark, I’ll give it another try. I could reduce the issue to a polygon with 92 vertices, so i can examine the effects more easily. Cheers, Volker

VolkerEnderlein commented 5 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

I just committed another fix for the additional issue. Can you re-test the pull request and report back whether it fixes all of your issues with tesselation? Cheers Volker

VolkerEnderlein commented 5 years ago

Original comment by Mark Goldberg (Bitbucket: MarkGoldberg, GitHub: MarkGoldberg).

Again thank so much for your work on this issue.

The last change did solve the last example.

But I easily found more examples of missing triangles in users data in our program.

I spent a couple of hours isolating and simplifying a graph for you that shows missing triangles.

Again I have no idea if this example is representative of the overall issue.

Edit: I tested the same data with COIN_PREFER_GLU_TESSELLATOR=1 and it solves the problem in the example I gave you. However in the full example, there are parts missing - note: they seem more rectangular than triangular with the environment variable on.

VolkerEnderlein commented 5 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

Thanks for the feedback, Mark.

I thought I finally found the reason for the faulty behaviour in the implementation, but that does not seem to be the case.

This leads me to the assumption, that the Delaunay triangulation is not properly implemented. I need some more time to figure out what is really causing this horrible triangulation errors.

Cheers, Volker

VolkerEnderlein commented 5 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

I found another issue with the current implementation of the Delaunay triangulation for the tessellation, Mark. Can you re-test whether the updated pull request solves your issues? Cheers, Volker

VolkerEnderlein commented 5 years ago

Original comment by Mark Goldberg (Bitbucket: MarkGoldberg, GitHub: MarkGoldberg).

Thanks again for digging into this.

This fix seemed to solve a number of problems, but we’re not yet at 100% correct.

I tested the same data with COIN_PREFER_GLU_TESSELLATOR=1 and it solves the problem in the example I gave you. However in the full example, there are parts missing

VolkerEnderlein commented 4 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

Hi Mark,

after carefully examining the examples you provided I found the reason for this erroneously behaviour. The last example you provided contains many holes. The algorithm used for tessellation in Coin does not support holes or self intersecting polygons. It does implement a simple Delaunay triangulation. For considering holes and other non simple polygons a Constrained Delaunay triangulation is needed or COIN_PREFER_GLU_TESSELLATOR=1 needs to be set. I guess the decision of the original implementers to implement only a simple Delaunay triangulation was driven by speed concerns.

If your application generates those complex polygons that seem to consist of mostly rectangular areas, you should provide the triangulation information too, i.e. you should provide the upfront triangulation in the coordIndex array. This will also significantly speed up the application as the Delaunay triangulation does not need to be performed.

I will merge the current state of the pull request #360 as it fixes a number of errors with the current implementation. If needed, we should open a new issue that requests for the implementation of a Constrained Delaunay triangulation.

Cheers, Volker

VolkerEnderlein commented 4 years ago

Original comment by Mark Goldberg (Bitbucket: MarkGoldberg, GitHub: MarkGoldberg).

Hi Volker,

Thank you for your continued efforts on this issue, it is really really appreciated.

I’m surprised to hear that there are any holes. Prior to sending my geometry to Coin, I call a polygon clean up method that (among other things) removes all holes by splitting contours with holes into multiple contours. Polygon contours are then extruded into faces and represented by IndexedFaceSets. So there shouldn’t be any holes … of course it’s always possible the polygon clean up code has a bug.

Note: it’s not uncommon for my program to generate concave faces - is that what you mean by a hole

?Thanks for the performance suggestion of breaking my faces down into triangles, I know I should’ve done that a long time ago. If I do that will I see even more performance gain by replacing the SoIndexedFaceSet with SoTriangleStripSet ?

Thanks again,

Mark

VolkerEnderlein commented 4 years ago

Original comment by Volker Enderlein (Bitbucket: VolkerEnderlein, GitHub: VolkerEnderlein).

Hi Mark,

the last file you provided on 04 Nov contains two large IndexedFaceSets, a purple one and a red one and other stuff. The red one surrounds parts of the purple one and is connected by single edges. This enclosed purple areas will be considered as holes when doing the Delaunay triangulation of the red area. They are separate areas, and the Delaunay triangulation is done per area. Concave faces are handled correctly by the triangulation. You may have a look into the coin/models/tessellation directory for some examples of concave areas that are handled correctly.

In terms of performance breaking down your complex concave faces to quads and using SoIndexedFaceSets should be comparable to using SoTriangleStripSets for the quads.

Cheers Volker

‌