Three.js: ShapePath: Wrong processing of mixed winding orders and nested shapes.

[bikb]

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

• [x] latest

Browser

• [x] All of them
• [ ] Chrome
• [ ] Firefox
• [ ] Internet Explorer

OS

• [x] All of them
• [ ] Windows
• [ ] macOS
• [ ] Linux
• [ ] Android
• [ ] iOS

Hardware Requirements (graphics card, VR Device, ...)

[WestLangley]

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]

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]

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]

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]

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]

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:

https://github.com/mrdoob/three.js/blob/c411c0b7ff04f8b33369237e76f3de43b143f7ed/src/extras/core/ShapePath.js#L156-L157

[WestLangley]

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]

@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]

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]

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

[Mugen87]

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]

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]

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

[Mugen87]

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]

@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]

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]

@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]

Hi guys! I resolved my problem
https://discourse.threejs.org/t/svgloader-and-extrude-make-a-wrong-scene/8465/3?u=tolyanor
I hope this helps you

[Mugen87]

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]

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]

/ping @yomboprime

[yomboprime]

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

[mrdoob]

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

[WestLangley]

Related https://github.com/mrdoob/three.js/issues/13653.

[yomboprime]

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]

The problem is that @tolyanor's SVG contains something like this:
hhhSh
which is not processed correctly by ShapePath.

[yomboprime]

The problem is that @tolyanor's SVG contains something like this:
hhhSh
which is not processed correctly by ShapePath.

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

[yomboprime]

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]

@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]

@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]

@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]

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

[WestLangley]

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

[yomboprime]

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.

[PalashBansal96]

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.

some context: I am using three.js to render user-uploaded SVGs with simple shapes and it is not possible to ask the users the rearrange their SVG files that are exported from some tool.

Right now, the algorithm assumes that in a path all holes and all shapes have the same winding, which is not a part of SVG spec. So, a lot of editors that export SVGs, export paths that can have multiple shapes that are not connected and have opposite winding.

An example SVG: http://logosvg.com/wp-content/uploads/AirAsia_logo.svg
jsfiddle with this: https://jsfiddle.net/0oxLhjnd/52/
Here, the SVG parsing is working fine but the characters i and r are incorrectly categorized as holes. If I set isCCW to false, then other characters are messed up.

For cases like this, we can group the sub-paths into multiple paths based using the convex hull and call ShapePath.toShapes() separately for each group. I have tried a quick implementation here: https://jsfiddle.net/0oxLhjnd/53/
What do you guys think? Would this break something else in the toShapes logic, or is there a simpler way to do this without the computing the hull?
Also, I am thinking that isCCW parameter can be automatically determined by taking the winding of the subpath with the largest area in a group. Could that work?

[Mugen87]

The current implementation of ShapePath.toShapes() is limited and the root cause for many issues.

I think it's worth investigating an implementation that does not require an isCCW parameter and that can handle different winding orders without breaking the shape. It might be useful to check how existing SVG renderers (like resvg) handle this aspect.

I would do this first before working at a custom solution.

[bcrespy]

"some context: I am using three.js to render user-uploaded SVGs with simple shapes and it is not possible to ask the users the rearrange their SVG files that are exported from some tool." @PalashBansal96

I am currently developing the same feature and facing the exact same issue. Unfortunately, expecting customers to serve a proper SVG is not a solution, and it is expected that a SVG path rendering properly on a browser should be renderer properly in the application.

Here is another fiddle demonstrating the issue:

https://jsfiddle.net/ciphrd/fkws31a7/18/

I tried to apply Palash's solution to this particular case but unfortunately it didn't work. Hope it can help you in the resolution of this issue.

In the meantime, are you aware of potential solutions to "convert" any SVG into something that can be interpreted correctly by the ShapePath.toShapes() method ? I'm not even sure that such a solution exists, and I wasn't able to find one from my research.

[PalashBansal96]

@bcrespy I tried my solution on your fiddle and it seems to be working fine, just flipped in Y, that's a separate thing i guess. You can see here: https://jsfiddle.net/0apf21qs/2/ Had to set isCCW to false for this SVG.

I also improved a bit upon this by automatically calculating isCCW by getting the Path with the max area in a group(since that would be the outermost) and assuming that winding to be for a shape and other for holes. Also, I have sorted the objects in a group based on area so that the holes are always the first. I have tested this with a lot of complex files and so far this is working pretty good with the toShapes logic and also with your example: https://jsfiddle.net/0apf21qs/5/

[bcrespy]

@PalashBansal96 great news ! and thanks for the efforts you're putting into this. I will make some tests using the files in my database and get back to you with some results.

[bcrespy]

@PalashBansal96 So I did some tests with some files in my database, and it works well but I found some issues with some SVG exported from inkscape. When I clean the SVG, it renders fine but otherwise it doesn't. Here is a file in which their is the issue:

https://pastebin.com/nQyLwcbm

For now I will do some SVG clean-up before saving the files to the database so it will work well, but this might be something to take in consideration if you plan on merging your fix. Sorry for not providing running examples I'm really short on time, hope it can help you in some ways.