[usdview] Concave polygons may not be drawn properly

[ft-lab]

Description of Issue

Mesh with concave polygons may not be displayed correctly in usdview.
I have created a simple sample.

sample file : simple_concave_polygons_usda.zip
When unzipped, it becomes a usda file.

Original :

usdview (21.05) :

It seems that "Concave2" in simple_concave_polygons.usda is not triangulating properly.
This is a polygon whose faceVertexIndices are as follows.

def Mesh "Concave2"
{
    int[] faceVertexCounts = [4]
    int[] faceVertexIndices = [0, 2, 3, 1]
    rel material:binding = </root/Materials/mat1>
    normal3f[] normals = [(0, 0, 1), (0, 0, 1), (0, 0, 1), (0, 0, 1)]
    point3f[] points = [(27, -2.5, 0), (17, -2.5, 0), (20, 0.5, 0), (17, 7.5, 0)]
    texCoord2f[] primvars:st = [(1, 0), (1, 1), (0, 1), (0, 0)] (
        interpolation = "faceVarying"
    )
    int[] primvars:st:indices = [0, 1, 2, 3]
    uniform token subdivisionScheme = "none"
}

Steps to Reproduce

1. Open simple_concave_polygons.usda in usdview

System Information (OS, Hardware)

Windows 10

Package Versions

21.02, 21.05

Build Flags

[jtran56]

Filed as internal issue #USD-6659

[asluk]

Hi @tcauchois and @davidgyu -- I'll have a developer on our OV Hydra team take a look at this. Thanks!

[tcauchois]

Great, thanks!

[rajabala]

@asluk Thanks! Here're some notes that may be relevant: We fan triangulate, so for the 4-vertex concave example, [0,2,3,1] would become [0,2,3] and [0,3,1].

[0,2,3] being clockwise gets culled (since we treat CCW as front-facing and we default to UsdImagingGL.CullStyle.CULL_STYLE_BACK_UNLESS_DOUBLE_SIDED in stageView.py), while [0,3,1] is drawn, which ends up drawing the convex hull of the topology.

[miguelh-nvidia]

I have a linear time algorithm that determines what is the right point to start triangulation, which would work for any star shaped polygons as the one presented here or in https://github.com/PixarAnimationStudios/USD/issues/1905. However most of the triangulation code deals with the topology and has no access to the points array (i.e. https://github.com/PixarAnimationStudios/USD/blob/release/pxr/imaging/hd/meshUtil.cpp).

Doing it at USD level would require swapping positions in multiple arrays (i.e. swap points -> swap normals, etc.). What would be a good point in the pipeline to deal with this problem?

[meshula]

That would be an improvement, but wouldn't solve the general problem of triangulating shapes. I used to use a homegrown earcut to solve this robustly, now I use https://github.com/mapbox/earcut.hpp. The trick is to pick the most orthogonal plane, (eg, the plane upon which the polygon has greatest bounds) and do the work there in 2d.

Personally I would think this would go where currently the code implements a fan.

(PS, earcut isn't a casual suggestion, I picked earcut after evaluating a bazillion alternatives and first going down the road of "better fan". earcut is least likely to be outsmarted by determined artists.)

[asluk]

Thanks for the insight, @meshula ! I believe @miguelh-nvidia 's implementation does involve some sort of earcut as well-- he'll keep at it and post a strawman PR if needed that can be iterated on further together. 🙏🏼

[meshula]

Apologies, I read @miguelh-nvidia's comment as saying he had a solution for star shaped polygons (which has special case solutions like adding a point in the center, and then triangle fanning*), so I was proposing earcut in order to get any shape, like a G or P ;)

* like I said, I investigated, like, a bazillion solutions ;)

[miguelh-nvidia]

Actually I have both @meshula . For this ticket and https://github.com/PixarAnimationStudios/USD/issues/1905, it is enough to find the right starting face index to start (i.e. different from 0), i.e. those are star shaped. The resulting operation translates in swapping elements in face indices (which implies the unfortunate effect of swapping elements in other primvars with interpolation faceVarying as well). The benefit is performance (quite fast and does not modify the number of elements).

If the polygon is not start shaped it will do ear cutting, which is slightly slower than the optimal linear algorithm and produce the even more unfortunate effect of creating more face indices and more elements in all primvars with interpolation faceVarying.

But having an initial look at the triangulation and topology classes, there does not seem other nicer alternative. I will post a draft PR after Easter and will be glad to discuss it with you.