Three.js: Incorrect shape with holes, when one area eclosed by another

Created on 21 Mar 2018 · 22Comments · Source: mrdoob/three.js

Description of the problem

Hi!
Problem description:
I have a svg path with holes and i want to extrude geometry from it, everything is fine except usecase where i have a isolated inner figure in source svg path

here is a fiddle with example of problem

dev-branch fiddle

at top of the scene: is the final result of extruding

at bottom: separated subshapes, one hole related to another polygon

edit: i dig into three.js code and figured out that is a bug of ShapePath.toShapes method.
the part of code with detection of correct hole target is bugged. case when one area enclosed my another (countour hierarchy) is not handled properly

Three.js version

[x] Dev
[x] r91
[ ] ...

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, ...)

Source

strangerintheq

Most helpful comment

input paths should be clockwise, holes counterclockwise. Users have to ensure that their data corresponds to this standard.

I would call it an SVG option, set by the SVG fill-rule property.

It is a three.js standard, however -- subject to the value of the toShapes() argument isCCW.

Note that three.js fills by triangulation, while SVG fills per pixel.

WestLangley on 30 Mar 2018

👍4

All 22 comments

the part of code with detection of correct hole target is bugged. case when one area enclosed my another (countour hierarchy) is not handled properly

Can you please link to the mentioned code section? Besides, what would you do different?

Mugen87 on 21 Mar 2018

https://github.com/mrdoob/three.js/blob/dev/src/extras/core/ShapePath.js

Scroll down source to last return statement.
Look at the value of return variable, in my case it contains two shapes, one with hole from another. Code above is trying to resolve the relations between shapes and holes, but..

strangerintheq on 21 Mar 2018

Pasting the path from the fiddle into webgl_geometry_extrude_shapes2.html produces this:

screen shot 2018-03-21 at 1 01 53 pm

WestLangley on 21 Mar 2018

@strangerintheq What is your intended visual output?

Mugen87 on 21 Mar 2018

I mean can you please specify the expected visual output with a screenshot? TBH, i don't understand what you are trying to achieve...

Mugen87 on 21 Mar 2018

@Mugen87 here is expected result fiddle
it achieved by manual managing of svg path subpaths sequence

strangerintheq on 21 Mar 2018

What does "manual managing" mean?

WestLangley on 21 Mar 2018

@WestLangley original svg path is the external input data for my app, in fiddle above i took last subpath and moved it to place after second subpath (1 2 3 4 5 -> 1 2 5 3 4)

strangerintheq on 21 Mar 2018

moved it to place after second subpath (1 2 3 4 5 -> 1 2 5 3 4)

Why do you think that worked?

Are your subpaths clockwise or counterclockwise or both?

WestLangley on 21 Mar 2018

It seems that all my paths and sub paths is always clockwise

strangerintheq on 21 Mar 2018

I was fixed bug in my case by adding following code at the end of:
https://github.com/mrdoob/three.js/blob/dev/src/extras/core/ShapePath.js
it is not an optimal solution, but it enough for me, and it handles more complex shapes that in my example...

Thanks for fast response guys!

return fixShapesHoles(shapes);

function fixShapesHoles(shapes) {
    if (shapes.length > 1) {
        var holesToShapeMap = [];
        var allHoles = shapes.reduce(function (acc, shape) {
            acc.holes = acc.holes.concat(shape.holes)
            return acc;
        }).holes;
        shapes.forEach(function (shape) {
            shape.holes = [];
        });
        allHoles.forEach(function (hole, i) {
            holesToShapeMap[i] = findEnclosingShapes(hole, shapes)
        });
        holesToShapeMap.forEach(function (shapes, i) {
            var targetShapeIndex = shapes.length === 1 ? 0 :
                findLastInnerShapeIndex(shapes);
            shapes[targetShapeIndex].holes.push(allHoles[i]);
        });
    }
    return shapes;
}

function findEnclosingShapes(hole, shapes) {
    return shapes.filter(function (shape) {
        return isPointInsidePolygon(hole.currentPoint, shape.getPoints());
    });
}

function findAllInnerShapes(shape, possibleInnerShapes) {
    return possibleInnerShapes.filter(function (s) {
        return isPointInsidePolygon(s.getPoints()[0], shape.getPoints());
    });
}

function findLastInnerShapeIndex(shapes) {
    return shapes.map (function (shape, i) {
        var copy = shapes.slice(0);
        copy.splice(copy.indexOf(shape), 1);
        return {
            index: i,
            shapes: findAllInnerShapes(shape, copy)
        };
    }).find(function (item) {
        return item.shapes.length === 0;
    }).index;
}

strangerintheq on 21 Mar 2018

PS: let me know if you interesting in pull request

strangerintheq on 22 Mar 2018

It seems that all my paths and sub paths is always clockwise

By default, paths should be clockwise; holes counterclockwise. Please try it.

WestLangley on 22 Mar 2018

@WestLangley but how? it is a input data for me, i cant determine where is shape or hole to reverse hole path

By default, paths should be clockwise; holes counterclockwise. Please try it.

is this a three-js define? or svg spec?

strangerintheq on 23 Mar 2018

See this SVG fill-rule property demo.

WestLangley on 23 Mar 2018

❤1

I think we can close this issue. Like @WestLangley mentioned, input paths should be clockwise, holes counterclockwise. Users have to ensure that their data corresponds to this standard.

Mugen87 on 30 Mar 2018