Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ShapePath: Triangulation problem #16950

Open
bikb opened this issue Jun 29, 2019 · 34 comments

Comments

Projects
None yet
6 participants
@bikb
Copy link

commented Jun 29, 2019

Description of the problem

When creating a polygon with constructPathShape.toShapes the order of the constructpathshapes commands plays a role which shouldn't be the case. (I think so)
I am adding a hole than the outer vertice then again a hole.
The last hole is not recognized.
https://jsfiddle.net/0g9bdar5/2/

The only thing which was changed is the order of the constructpathshape commands.
If I add the two holes at the beginning the polygon is rendered correctly.
https://jsfiddle.net/0g9bdar5/3/

Three.js version
  • latest
Browser
  • All of them
  • Chrome
  • Firefox
  • Internet Explorer
OS
  • All of them
  • Windows
  • macOS
  • Linux
  • Android
  • iOS
Hardware Requirements (graphics card, VR Device, ...)
@WestLangley

This comment has been minimized.

Copy link
Collaborator

commented Jun 30, 2019

You are instantiating 60 meshes per second and failing to dispose of the geometries properly when they are removed from the scene.

None of that should be necessary to demonstrate your issue. You can remove the animation loop and only render on load and on mouse clicks.

Also, try to demonstrate your issue with a simpler example -- such as a rectangle with two rectangular holes.

We can then decide if this is a three.js bug or a user error.

@bikb

This comment has been minimized.

Copy link
Author

commented Jun 30, 2019

OK, here is the simplified version:
wrong rendering:
https://jsfiddle.net/6d20Lmu7/1/

correct version:
https://jsfiddle.net/6d20Lmu7/2/

I will try it with rectangles too.

@bikb

This comment has been minimized.

Copy link
Author

commented Jun 30, 2019

Here is a version with 3 rectangles:
https://jsfiddle.net/6d20Lmu7/3/
https://jsfiddle.net/6d20Lmu7/4/
https://jsfiddle.net/6d20Lmu7/5/

All works fine. So why not the other example?

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jun 30, 2019

AFAIK, ShapePath.toShapes() expects that all hole definitions are grouped together. It does not matter if they are defined at first or last but it's not valid to mix them up with the contour. You are exactly doing this in your first fiddle.

Check out the following fiddles which order the definitions of the shape.

https://jsfiddle.net/gpkhuxtj/
https://jsfiddle.net/gpkhuxtj/1/

@bikb

This comment has been minimized.

Copy link
Author

commented Jun 30, 2019

OK the version https://jsfiddle.net/6d20Lmu7/1/ shows the one with the problem.
First the upper hole is added, then the contour and then the lower hole. But the lower hole does not appear. You say it is not the right order. But the example with the rectangles works despite of the wrong grouping.
If I execute the commands excactly in the same order in canvas 2d API or in svg there is no problem:
https://jsfiddle.net/0k7j3qsf/
Do you have a hint how to fix the problem?
Reordering should be done in my app or in the three js library?

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jun 30, 2019

Reordering should be done in my app or in the three js library?

For now, it has to be done in your app. I have not debugged the issue in detail but the code in ShapePath provides some hints:

var holesFirst = ! isClockWise( subPaths[ 0 ].getPoints() );
holesFirst = isCCW ? ! holesFirst : holesFirst;

@WestLangley

This comment has been minimized.

Copy link
Collaborator

commented Jun 30, 2019

Unrelated, but as I said, learn how to dispose of geometries properly when you remove objects from the scene. Add this, and you will see what is happening.

console.log( renderer.info );

Use the non-minified version of three.js for development and debugging. You should be able to step through your code and understand why the holes cannot be interleaved.

Also, try this pattern:

var shape = new THREE.Shape();
shape.moveTo( ... );
shape.lineTo( ... );
...

shape.holes.push( hole1 );
shape.holes.push( hole2 );

var geometry = new THREE.ExtrudeBufferGeometry( shape, settings );
@bikb

This comment has been minimized.

Copy link
Author

commented Jul 1, 2019

@Mugen87 Thank you for the hint.
@WestLangley Thank you. I was not aware of correct disposing. I have found this link:
https://threejs.org/docs/#manual/en/introduction/How-to-dispose-of-objects
In my real app I will take care. Thanks!

Unfortunately I cannot use the pattern because my source of objects doesn't tell me anything about the used holes. I have to detect them on my own. I will try to add hole detection to my app and use the suggested pattern.

I was wondering why the rectangles example was working. Perhaps you can have a look at the differences of the reactangle example and example https://jsfiddle.net/6d20Lmu7/1/ meanwhile?

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 1, 2019

I was wondering why the rectangles example was working.

As far as I can see, these examples stick to the mentioned order rule.

https://jsfiddle.net/6d20Lmu7/3/ and https://jsfiddle.net/6d20Lmu7/4/ define the outer shape first.
https://jsfiddle.net/6d20Lmu7/5/ defines the holes first.

@bikb

This comment has been minimized.

Copy link
Author

commented Jul 1, 2019

Thank you. I saved the wrong versions.
Here is a fiddle with the reproduced behaviour when using rectangles.
https://jsfiddle.net/ufpy6th5/

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 2, 2019

I was wondering why the rectangles example was working.

The fiddle does not produce a correct result because you don't adhere the shaper order. Defining the holes first or last solves the issue:

https://jsfiddle.net/p49zo37a/1/

@bikb

This comment has been minimized.

Copy link
Author

commented Jul 3, 2019

Today I had time to debug.
In my case of source objects this added code solves the problems:


for ( var i = 0, il = newShapes.length; i < il; i ++ ) {
...
}

// add remaining holes
      for ( ; i < newShapeHoles.length; i ++ ) {
        tmpHoles = newShapeHoles[ i ];

        for ( var j = 0, jl = tmpHoles.length; j < jl; j ++ ) {

          tmpShape.holes.push( tmpHoles[ j ].h );

        }

      }
@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 7, 2019

Consider to make a PR if you want to improve ShapePath. In this way, it will be easier to understand the code changes.

@Mugen87 Mugen87 changed the title triangulation problem ShapePath: Triangulation problem Jul 11, 2019

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 11, 2019

We have a similar triangulation issue in the forum today:

https://discourse.threejs.org/t/svgloader-and-extrude-make-a-wrong-scene/8465

However, I'm not sure the presented code is a good solution. It does work with a single shape definition with holes. However I'm not sure it works with multiple shape definitions. It might be possible that holes are assigned to the wrong shape. Hence, I'm not sure it's better to sort the path data before calling ShapePath.toShapes().

@WestLangley

This comment has been minimized.

Copy link
Collaborator

commented Jul 11, 2019

@Mugen87 Can we make a clear statement as to what the problem is -- something like "svg paths containing interleaved shapes and holes do not triangulate correctly" -- but hopefully more precise than that?

Also, what happens if there is a shape containing a hole which in turn contains a shape?

Is this a triangulation problem or an extrusion problem? I assume it is the former, but to be honest, I haven't studied it carefully.

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 11, 2019

Also, what happens if there is a shape containing a hole which in turn contains a shape?

Nested structures are not supported. Triangulation algorithms in general do not concern about stuff like that. They usually work with a sequence of vertices representing the contour and optionally a definition of holes.

Is this a triangulation problem or an extrusion problem?

I think none of the two. It's a matter of how ShapePath internally organizes its path definitions. A properly triangulation algorithm can't do something meaningful if the Shape definition is wrong or incomplete. But as mentioned before, I'm not sure how to improve the current logic in a robust way. It might be easier to handle this one higher level for now.

@WestLangley

This comment has been minimized.

Copy link
Collaborator

commented Jul 11, 2019

@Mugen87 Thanks. You are more familiar with this than I am... So should the triangulation and extrusion of any svg shape be supported? I assume the answer is "yes", but If I understand you, you are saying that is not the problem -- the problem is somewhere else. Right?

@tolyanor

This comment has been minimized.

Copy link

commented Jul 12, 2019

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

As @tolyanor mentioned in the forum, it's a matter of contour and hole order. I'm not yet sure how to handle this in three.js.

@tolyanor

This comment has been minimized.

Copy link

commented Jul 12, 2019

The svg format has no rules defining the order of the contour and holes. Thus, all the programs and browsers correctly show SVGs with holes in the first place. Threejs make it wrong. There is also a problem with winding the path counterclockwise, I described it on the forum. I think it should not be ignored.

@mrdoob

This comment has been minimized.

Copy link
Owner

commented Jul 12, 2019

/ping @yomboprime

@yomboprime

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

Sorry, I don't know the inners of the triangulation algorithm. I could look at it this weekend.

@mrdoob

This comment has been minimized.

Copy link
Owner

commented Jul 12, 2019

Can we automatically reverse the counter-clockwise paths in the SVGLoader?

@WestLangley

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

Related #13653.

@yomboprime

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

Can we automatically reverse the counter-clockwise paths in the SVGLoader?

I guess so, but ShapePath already handles the winding. In fact, winding is what defines what's a shape and what's a hole.

Valid input sequences are (S = Shape, h = hole):
ShhhShhhhShhh
and
hhhhShhShhhS

You specify a winding order (ccW or cW) in the call to ShapePath.toShapes(). If the first subpath has the same winding as the parameter, then the shape comes first, then comes the holes of that shape. If not, the holes comes before the shape.

So, multiple shapes are supported, but you have to have control of the winding of shapes and holes (at least with this algorithm).

@Mugen87

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

The problem is that @tolyanor's SVG contains something like this:
hhhSh
which is not processed correctly by ShapePath. I think it's best to fix this in SVGLoader and ensure the contour/hole order is correct.

@yomboprime

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

The problem is that @tolyanor's SVG contains something like this:
hhhSh
which is not processed correctly by ShapePath. I think it's best to fix this in SVGLoader and ensure the contour/hole order is correct.

Perhaps it should be an option, otherwise for example CNC applications that load SVG could suffer.

@yomboprime

This comment has been minimized.

Copy link
Collaborator

commented Jul 12, 2019

After investigating a bit, I find it is not simple to define a general solution, since holes can be defined in multiple ways not supported by the current SVGLoader, such as masks. So the holes format depends on the application that generated the SVG.

@bikb

This comment has been minimized.

Copy link
Author

commented Jul 18, 2019

@Mugen87: The problem is that ShapePath does not return the remaining holes. hhSh is processed as hhS. My solution works well with PDF source objects. I did not encounter any problems. I have tested a lot of PDF files with complex geometry. But I cannot say how the solution behaves to other rules used for example in svg.

@bikb

This comment has been minimized.

Copy link
Author

commented Jul 18, 2019

@yomboprime: Perhaps we can test with special test svg files. If one day no more bug is found we can close the issue. But to do nothing and telling "it depends on the app" is NO solution!

@bikb

This comment has been minimized.

Copy link
Author

commented Jul 18, 2019

@yomboprime: You write "Perhaps it should be an option, otherwise for example CNC applications that load SVG could suffer." But perhaps it could be the opposite -> Faster and more reliable apps with no more bugs!

@yomboprime

This comment has been minimized.

Copy link
Collaborator

commented Jul 18, 2019

@bikb As Mugen87 said, you can make a PR with your solution. Tests should be made to ensure the algorithm is not broken.

@WestLangley

This comment has been minimized.

Copy link
Collaborator

commented Jul 18, 2019

It's probably not good policy to tell users they can fix the bug themselves.

@yomboprime

This comment has been minimized.

Copy link
Collaborator

commented Jul 18, 2019

It's probably not good policy to tell users they can fix the bug themselves.

All right, I'm sorry. Perhaps i was a bit rude.

But please note that I was referring to the solution he has already found and posted (not suggesting to find one). It is a patch to solve his issues, and alters what the algorithm is supposed to do. I don't know the implications and it worries me.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.