LineSegment assertions during degenerate vertices checks

[zilmarinen]

Since updating to 0.5.0 I am seeing a lot of errors when attempting to merge two meshes together with Mesh.union. In particular, pointsAreSelfIntersecting is failing due to the assertion in the LineSegment initialiser.

I have some fairly complex meshes with vertices that are generated programmatically with lots of vertices that are incredibly close to each other especially when two meshes are intersecting.

Prior to 0.5.0 I had decent looking results. Since updating the LineSegment assertions fire so frequently that I can no longer union two or more meshes together where the intersections are extremely close.

Here are two vectors being passed to the LineSegment initialiser:

▿ Start Vector
- x : 0.128732497095
- y : -0.0053554244909999995
- z : 0.0

▿ End Vector
- x : 0.128733302962
- y : -0.005356203166
- z : 0.0

I am exploring alternate means to try to minimise the likelihood of the intersecting points being close-but-not-quite-equal. However, given that this is not something I have encountered in prior versions I thought it worth raising either for visibility or for clarification.

Thanks again for the awesome work!

[nicklockwood]

@CaptainRedmuff sorry about that. Can you share some sample code/meshes that demonstrate the problem? It might just be a matter of fine-tuning the tolerances.

[zilmarinen]

I am unable to provide a concrete example at the moment but I have encoded a mesh that will hopefully help reproduce the problem.

My implementation is something along the lines of;

var mesh = Mesh([]) //start with empty mesh

//create foliage
for number of fronds in canopy {

  let frond = Frond(position, rotation) //instance of the mesh example

  mesh = mesh.union(Mesh(frond.build())) //union into one big mesh
}

//additional mesh generation

It appears that the problem is when the innermost polygons intersect when merging each individual frond into a canopy. I encountered similar issues with a different part of the mesh but managed to resolve this by ensuring that each polygon had no more than 3 vertices. This did not seem to make a difference when merging the leaves however and presumably has negative performance implications.

Hopefully you can reproduce this by trying to merge two instances of this together from the "center". Let me know if there is any further info I can provide to assist.

[nicklockwood]

@CaptainRedmuff I tried loading your encoded mesh and merging your leaves together, but I wasn't able to trigger any assertions. I'm not sure if I'm merging them the way you meant (see screenshot).

I've pushed my test code to this branch - maybe you can take a look and modify it to try to recreate the error?

[zilmarinen]

@nicklockwood It looks like the mesh is rotated incorrectly in this test.

The fronds should be joined at the thinnest part of the mesh as in this screenshot (using Euclid 0.4.0)

I have added a gist with the trunk and fronds if this is any use in debugging although at this point the fronds have already been merged into a single mesh (again, using 0.4.0) but there is still an error when merging the trunk mesh with the foliage.

I am not sure how to create a fork from your line-segment-assertion-test branch but I will copy this into my own fork to try reproduce.

[nicklockwood]

@CaptainRedmuff I've still not been able to trigger any assertions no matter how I try to combine the meshes you sent. Perhaps the serialization process is somehow correcting the issues in the mesh that lead to the assertions?

[zilmarinen]

@nicklockwood This took me a little longer to abstract out of my project but I have managed to reproduce the issue and raised a PR.

I really hope this is not another case of invalid mesh generation on my behalf again 😅 Let me know if there is anything further I can do to assist.

[nicklockwood]

@CaptainRedmuff OK, well I've worked out both why the assertion is happening and (more worryingly for me) why it only happens occasionally.

The assertion was due to a mismatch in the way LineSegment checked for equality between the start and end points - in one case it checked for exact equality, but in the assertion it checked for approximate equality. I've pushed a fix for this to the develop and master branches, and I'll include it in the next tagged release.

The reason it wasn't happening every time was due to these lines in your Frond.swift file, and not any non-deterministic behavior of Euclid itself (phew!).

let cut0 = Double.random(in: 0...10) <= 1
let cut1 = Double.random(in: 0...10) <= 1

FWIW, when using random elements in procedural generation, I think it's usually a good idea to use a seeded generator, so that the results can be repeated. This makes it much easier to reproduce the conditions of a bug (as in this case), but also is just generally useful e.g. so if you like a particular result you can recreate it exactly.

Swift makes it quite easy to do this by supplying your own RNG. The one I use in Euclid is this:

// See https://github.com/wangyi-fudan/wyhash/
struct DeterministicRNG: RandomNumberGenerator {
    private var seed: UInt64 = 0 // change this to get a different sequence

    mutating func next() -> UInt64 {
        seed &+= 0xA0761D6478BD642F
        let result = seed.multipliedFullWidth(by: seed ^ 0xE7037ED1A0B428DB)
        return result.high ^ result.low
    }
}

Which you'd use like this:

// Make this global, or wrap it in a class that you can pass between
// Frond instances, otherwise they'll each end up the same
var rng = DeterministicRNG()

...

let cut0 = Double.random(in: 0 ... 10, using: &rng) <= 1
let cut1 = Double.random(in: 0 ... 10, using: &rng) <= 1

[nicklockwood]

I've pushed a DeterministicRNG implementation to the line-segment-assertion-test branch.

[zilmarinen]

@nicklockwood Some great sleuthing there in working out where the problem lies. However, I am still seeing some assertions firing with this fix.

shortestLineBetween sometimes fails on either of its two assertions. It took a few runs to catch this in the example app but it is still prevalent even with your RNG changes.

I have made a PR with more robust example of how the shape is created using a curve for the trunk (defined by the trunk.spread value).

If you run the example it should crash instantly. If you change the RNG seed from 1 to 2 it will run correctly.

With regards to the RNG, In my project I am using a seeded GKPerlinNoiseSource but did not include this in the example for the sake of brevity. Your DeterministicRNG example is extremely useful though for repeatable results and I shall make use of this in the future.

[nicklockwood]

@CaptainRedmuff OK, I've fixed the assertion on the develop branch.

[zilmarinen]

@nicklockwood Top notch. I can confirm that I am no longer seeing any problematic assertions with this fix 👍

[nicklockwood]

Great! The changes are included in 0.5.2.