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.

[repalash]

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.

[ciphrd]

"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.

[repalash]

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

[ciphrd]

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

[ciphrd]

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

[Ttommeke]

@PalashBansal96 @bcrespy I have the same use case. I developed my own solution to the issue.

DISCLAIMER: a threw a bunch of code together, very unorganized. I might clean it up... When i get around to it.

Instead of looking for the largest area, my solution involves a scanline through the middle of each path. On this scan line it will look for intersections with other paths. These intersections are then labeled and sorted on their X values. Lowest X first. with these labelled intersections, in combination with the CW or CCW orientation, you now know which path is in which other path and to whom it is a hole.

The idea of a scanline comes from rendering an svg pixel by pixel. (See examples)

An advantage: It does not require the same orientation for paths that are holes or for paths that are solids. It uses the other paths orientation to determine whether its orientation might mean that it is a hole or a solid. A drawback is its speed. And it doe not handle intersections.

It also seems that there is a small issue in the getPoints function on a CurvePath? The letter R results in NAN numbers.

My problem SVG: https://jsfiddle.net/r52d9pgs/30/ Airbus logo: https://jsfiddle.net/r52d9pgs/27/

Hope it might be inspiring.

[yomboprime]

Nice work!

I've tested that the missing 'R' shows up when you substitute by 0.0001 the 10e-4 in the 'G74' SVG node. This is probably related to the recent change in parsing floats in #17306 , so is not related to getPoints.

[yomboprime]

@Ttommeke Have you got plans to make a PR shortly? I could put some time in it.

I find your algorithm very good, that's why I doubt asking you the following:

I think the isCCW calculations are not needed, and the intersections give enough information inside the isHoleTo function. The isUseless flag is useless (LOL) and could be discarded. What do you think?

This way it could handle more SVG files, independently of ccw ordering.

[Ttommeke]

@yomboprime Thanks!

I did not have the initial intention of creating a PR because I am not aware of all the requirements for this feature. However, I would love to help. I have some time this weekend to create a PR.

To answer your questions: when there is only one path or if there are multiple paths that are not nested in each other in any way, it's unnecessary. The isCCW calculations are necessary in case of holes. I've created a small reference image of a path in svg (I hope no one ever creates a similar image this way). The image below shows path A with path B and path C inside of it. However only C should be a hole because its direction is in the opposite direction of path A. Then inside hole C there are two paths. Even dough each of them has a different direction they'll still both form a shape because the orientation only matters to holes. Then inside path D you find again two paths with opposite directions. The one in the opposing direction creating a hole.

At least these seem to be the the rules Inkscape and Chrome use. If I read through the documentation Winding rule it would care about the orientation of paths(like path D and path E) inside a hole(path C) of another path. I might also be confused? The EvenOdd rule is something our implementation would not be able to handle at the moment. But it seems to work like you have described by using the intersection data.

The isUseless flag is used to filter out shapes like path B and path G that fill the same area as another path. Thus removing "useless" paths. But now that you mention it, i totally forgot that these paths could still display a stroke. so maybe it is indeed a useless flag. LOL

[yomboprime]

I see. Thanks!

I was going to make some performance tests before the PR, and try to optimize it (mainly the findEdgeIntersection and classifyPoint functions) Because there are temporary objects and arrays that could be reused, and these 2 function execute a lot of times (since they are in the inner double loop on path segments). I've not tried yet to load the Tiger.svg, for example.

[repalash]

I have been using paperjs to fix the path orientation before loading in threejs to support both evenodd and non-zero fill rules and fix other problems. This has been working pretty good for me to support many cases. @yomboprime If you are working on a PR, you may also check the reorient function there which does most of the work. http://paperjs.org/reference/pathitem/#reorient

I have also tested the scanline method, it works really good, but takes a lot of time with SVGs with many shapes. I think it could be worth it to first cheaply group paths into 'islands' and build a hierarchy(like 2D BVH maybe), then run the scanline. Basically like how we trace rays. Plus with all this data, supporting evenodd shouldn't be very complicated for non-intersecting shapes, what's the problem with that?

[yomboprime]

what's the problem with that?

No problem at all, just was thinking it was unnecessary and looking for optimization.

A simple path bounding box could be a good optimization when intersecting the scanline. I don't know any cheap algorithms that calculate the hierarchy cheaper than the scanline method itself.

About the PR, let Ttommeke develop his approach. I will concentrate on other tasks, the last I want is to duplicate work time.

[Ttommeke]

@yomboprime I'll attempt to create a PR this weekend. I had not really concidered performance before. It makes sence that the scanline method has really horrible perfomance on SVGs with a lots of shapes. When i have developed my approach please look into it to see how it could be faster.

A simple path bounding box could be a good optimization when intersecting the scanline.

That would be a good improvement. I'll include it.

I think it could be worth it to first cheaply group paths into 'islands' and build a hierarchy(like 2D BVH maybe), then run the scanline. Basically like how we trace rays.

@PalashBansal96 This is basically what the scanline is for. Do you have a cheaper alternative?

[yomboprime]

When i have developed my approach please look into it to see how it could be faster.

Sure I will! Basically, it's reusing temporary intersection objects instead of creating them in each call to findEdgeIntersection. Also remove some arrays created for passing as parameters. Removing the polarAngle part, which is not used. Change the string comparisons by integer comparisons. That's basically it. There is a lot of overhead multiplied by a lot of nested loops.

[Ttommeke]

I believe my PR is finished. I do break compatibility by removing some parameters and replacing them with other in the toShapes function. I don't know how you guys feel about that?