Support concave and/or n-vertex faces

[rahwang]

Fixes #79 and #55.

Modify face-loading logic to support faces that are n-gons that may be concave.

Also replacing the box-triangles obj test file, because it didn't actually have triangular faces.

Can you review, @lilleyse ?

[pjcozzi]

CC @erich666

[rahwang]

@lilleyse and I discussed the broken tests -- looks like they differ only in the long generated string. Not sure what causes this? The test objs look fine though.

Also, my changes introduce quite a bit more computation per face. I'm not familiar with the sorts of usage this converter gets, but if really large models are common (and the n-gon / concave face cases are uncommon), it might be worth making this an option and using a simple face method for triangulation the default case.

[pjcozzi]

Performance will definitely be important here. Instead of relying on user input, can't we do a quick test to see if this is needed or not?

[erich666]

Right, I suspect 90% of the time it's a quick out, "there are three vertices." Another 9.9% of the time it'll be a quad, and maybe there's a quick out for those, but I don't know one off-hand. I'd use:

Graphics Gems IV: Schorn, Peter, and Fisher, Frederick, Testing the Convexity of a Polygon, p. 7-15, code: p. 11-15, convex_test/.

Code is here: http://www.realtimerendering.com/resources/GraphicsGems/gemsiv/convex_test/ - two versions, and I assume _opt.c is newer and better.

There might be something newer somewhere, but this is the one I know, and I recall it's pretty optimal (it can also identify degenerate polygons, which you can simply discard if you know they're part of a surface).

[pjcozzi]

Thanks for the reference, @erich666!

[rahwang]

Hey @lilleyse , would you like to start looking at this? I'm not sure what to do about winding ordering.

[rahwang]

Ok, I added winding order sanitization for when normals are provided.

I haven't added degenerate polygon sanitization, but this PR has already gotten a lot bigger than I originally intended, so perhaps that's best left to a follow up PR.

@lilleyse

[pjcozzi]

Bump @lilleyse

[pjcozzi]

Bump @lilleyse

[mramato]

@rahwang The reason the tests just look like really long string differences is because jasmine is doing a comparison of 2 gltf objects, this test fails because the output has changed. Jasmine doesn't know how to do anything other than stringify the objects as part of the error message (however this is enough for us to go on.)

If you diff the two strings provided by the error message, what you find is that the glTF buffers are different between master and this branch (since they are base64 encoded it's hard to say at a glance exactly what is different). Long story short, (too late) if you convert specs/data/box/box.obj in this branch, you end up with a different glTF than in master.

It's possible that your changes are still correct and that the test is too fragile and needs to be updated, but the important next step for you here is to convert box.obj both in master and in this branch and determine exactly what is different and why and which one is more correct. (I would also recommend you merge master into this branch before doing that just in case).

Hope that helps!

[rahwang]

Thank @mramato! I'll try to hunt down the differences once I get another chance to talk to Sean -- we were also considering moving the winding order correction into gltf pipeline.

[lilleyse]

It's possible that your changes are still correct and that the test is too fragile and needs to be updated

Originally those tests acted as "integration" tests, but they are too fragile and should probably be removed.

[rahwang]

Thanks for the suggestion, @lilleyse ! I reorganized the line buffering. This is ready for further review.

[rahwang]

Ok @lilleyse , ready for another look!

[rahwang]

Thanks for reviewing, @lilleyse ! Did requested cleanup edits.

[lilleyse]

@rahwang could you test out the model in #97? The triangulation is working but I think the winding order may be producing inconsistent results for 4-sided polygons.

In the second image I removed back face culling from the gltf.

[rahwang]

Thanks for catching that @lilleyse ! It was a small bug with some scratch cart3s. Fixed. The converted model now looks like this:

[03lafaye]

Awesome! Thanks!

[lilleyse]

Thanks a lot @rahwang!