opened
bikb
username_0
##### 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, ...)
triangulation problem
issue
created
WestLangley
username_1
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.
comment
created
bikb
username_0
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.
comment
created
bikb
username_0
Here is a version with 3 rectangles:
https://jsfiddle.net/6d20Lmu7/3/
https://jsfiddle.net/6d20Lmu7/4/

https://jsfiddle.net/6d20Lmu7/5/
I have set the parameter of "toShapes" :
var simpleShapes = constructPathShape.toShapes( true );
So in the last example even if the last group of commands is ignored why are there filled rectangles - they shouldn't be filled corresponding to isCCW is set to true!?
Docs:"By default solid shapes are defined clockwise (CW) and holes are defined counterclockwise (CCW). If isCCW is set to true, then those are flipped."
comment
created
Mugen87
username_2
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.

https://jsfiddle.net/gpkhuxtj/
https://jsfiddle.net/gpkhuxtj/1/
comment
created
bikb
username_0
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?
comment
created
Mugen87
username_2
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/username_4/three.js/blob/c411c0b7ff04f8b33369237e76f3de43b143f7ed/src/extras/core/ShapePath.js#L156-L157
comment
created
WestLangley
username_1
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.
```js
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:
```js
var shape = new THREE.Shape();
shape.moveTo( ... );
shape.lineTo( ... );
...

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

var geometry = new THREE.ExtrudeBufferGeometry( shape, settings );
```
comment
created
bikb
username_0
@username_2 Thank you for the hint.
@username_1 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?
comment
created
Mugen87
username_2
As far as I can see, these examples stick with 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.
comment
created
bikb
username_0
Thank you. I saved the wrong versions.
Here is a fiddle with the reproduced behaviour when using rectangles.
https://jsfiddle.net/ufpy6th5/
comment
created
Mugen87
username_2
AFAIK, the fiddle does not produce a correct result because you don't adhere the shaper order. Defining the outer shape first or last solves the issue:

https://jsfiddle.net/p49zo37a/1/
comment
created
bikb
username_0
comment
created
Mugen87
username_2
Consider to make a PR if you want to improve `ShapePath`. In this way, it will be easier to understand the code changes.
comment
created
Mugen87
username_2
We have a similar triangulation issue in the forum today:

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

@bkib Your presented code does also fix this issue. Do you want to make a PR? If not, I'm going to do this 😇
comment
created
WestLangley
username_1
@username_2 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.
comment
created
Mugen87
username_2
I think none of the two. It's a matter of how `ShapePath` internally organizes its path definitions. A properly triangulation algorithm can't something meaningful if your `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 for know to handle this one higher level.
comment
created
WestLangley
username_1
@username_2 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?
comment
created
tolyanor
username_3
Hi gays! I resolved my problem
https://discourse.threejs.org/t/svgloader-and-extrude-make-a-wrong-scene/8465/3?u=username_3
I hope this helps you
comment
created
Mugen87
username_2
As @username_3 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`.
comment
created
tolyanor
username_3
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](https://discourse.threejs.org/t/svgloader-and-extrude-make-a-wrong-scene/8465/4?u=username_3). I think it should not be ignored.
comment
created
mrdoob
username_4
/ping @username_5
comment
created
yomboprime
username_5
Sorry, I don't know the inners of the triangulation algorithm. I could look at it this weekend.
comment
created
mrdoob
username_4
Can we automatically reverse the counter-clockwise paths in the `SVGLoader`?
comment
created
WestLangley
username_1
Related https://github.com/username_4/three.js/issues/13653.
comment
created
yomboprime
username_5
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.
comment
created
Mugen87
username_2
The problem is that @username_3 SVG contains something like this:
`hhhSh`
which is currently not processed correctly by `ShapePath`. I think it's best to fix this in `SVGLoader` and ensure the contour/hole order is correct.
comment
created
yomboprime
username_5
Perhaps it should be an option, otherwise for example CNC applications that load SVG could suffer.
comment
created
yomboprime
username_5
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.
comment
created
bikb
username_0
@username_2: 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.
comment
created
bikb
username_0
@username_5: 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!
comment
created
bikb
username_0
@username_5: 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!
comment
created
yomboprime
username_5
@username_0 As username_2 said, you can make a PR with your solution. Tests should be made to ensure the algorithm is not broken.
comment
created
WestLangley
username_1
It's probably not good policy to tell users they can fix the bug themselves.
comment
created
yomboprime
username_5
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 post (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.
comment
created
PalashBansal96
username_6
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?
comment
created
Mugen87
username_2
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.
comment
created
bcrespy
username_7
"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." @username_6

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.
comment
created
PalashBansal96
username_6
@username_7 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/
comment
created
bcrespy
username_7
@username_6 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.
comment
created
bcrespy
username_7
@username_6 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](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.
comment
created
Ttommeke
username_8
@username_6 @username_7 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.
comment
created
yomboprime
username_5
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 not related to ```getPoints```.

![image](https://user-images.githubusercontent.com/2453652/107415219-63550900-6b13-11eb-8683-be2fcf631c68.png)
comment
created
yomboprime
username_5
@username_8 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.
comment
created
Ttommeke
username_8
@username_5 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](https://svgwg.org/svg2-draft/painting.html#WindingRule) 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

![github-issue](https://user-images.githubusercontent.com/7803949/108847096-90a7b980-75df-11eb-8ac0-affcbca686ae.png)
comment
created
yomboprime
username_5
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 to load yet the Tiger.svg, for example.
comment
created
PalashBansal96
username_6
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. 
@username_5 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?
comment
created
yomboprime
username_5
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 username_8 develop his approach. I will concentrate on other tasks, the last I want is to duplicate work time.
comment
created
Ttommeke
username_8
@username_6  This is basically what the scanline is for. Do you have a cheaper alternative?
comment
created
yomboprime
username_5
Sure I will! Basically, it's reusing temporary intersection objects instead of creating them in each call to ```intersectSegment```. 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.
comment
created
Ttommeke
username_8
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?
comment
closed
mrdoob
username_4
issue