WIP, RFC: Bounding sphere decimation

[h3mosphere]

This adds LOD decimation based on bounding spheres. This works for me, I wrote it about a week ago, and I just wanted to show it, in case you find the use case intriguing.

I'm not 100% sure about the implementation, and that I got the the generic trait bounds correct.

One thing I thought of was, instead of having nested bounding spheres, have an origin, radius, initial error, and error increment per distance unit, for continuous LOD.

Anyway, thanks for the cool library, and it was pretty nice how easy it was to add this functionality, without it having necessarily being a use case you had envisioned. :+1:

[h3mosphere]

Also, the hide some unused warnings commit snuck in there without me noticing. Apologies there.

[h3mosphere]

Reworking the code, I realized that perhaps instead of MaxError, the trait could be

trait DecimateEdge {
    fn should_decimate(&self, cost: ScalarType, mesh: &TMesh, edge: &TMesh::EdgeDescriptor) -> bool
}

This allows for essentially NOOP for the case where we disable MaxError. i.e. we could default to IdentityDecimateEdge, which always returns false(?)

[h3mosphere]

I also removed the assets/surface*.stl files, the source was 11MB. I'll add back in a 2d triangulation for the source plane.

[dima634]

Reworking the code, I realized that perhaps instead of MaxError, the trait could be

trait DecimateEdge {
    fn should_decimate(&self, cost: ScalarType, mesh: &TMesh, edge: &TMesh::EdgeDescriptor) -> bool
}

This allows for essentially NOOP for the case where we disable MaxError. i.e. we could default to IdentityDecimateEdge, which always returns false(?)

Totally makes sense. I think this would be a cleaner solution.

[h3mosphere]

OK, I'll rework this. Probably have an update tomorrow.

Thanks!

[h3mosphere]

OK, MaxError trait has been renamed to EdgeDecimationCriteria.

There is not currently an IdentityDecimationCriteria, this may make sense where None is passed as the decimation_criteria, to allow essentially a NOOP. This however depends on the type that is set, or inferred. Currently setting the decimator to None requires the TEdgeDecimationCriteria to be qualified. It's a bit of a code smell, but not 100% sure what to do here. I hope I've explained this well enough. For example in examples/simplification.rs, setting line 15 to:

let mut decimator = EdgeDecimator::new().decimation_criteria(None);

Causes an error.

However this works: let mut decimator = EdgeDecimator::<_, ConstantErrorDecimationCriteria<_>>::new().decimation_criteria(None);

This might need some architectural re-jig.

[dima634]

OK, MaxError trait has been renamed to EdgeDecimationCriteria.

There is not currently an IdentityDecimationCriteria, this may make sense where None is passed as the decimation_criteria, to allow essentially a NOOP. This however depends on the type that is set, or inferred. Currently setting the decimator to None requires the TEdgeDecimationCriteria to be qualified. It's a bit of a code smell, but not 100% sure what to do here. I hope I've explained this well enough. For example in examples/simplification.rs, setting line 15 to:

let mut decimator = EdgeDecimator::new().decimation_criteria(None);

Causes an error.

However this works: let mut decimator = EdgeDecimator::<_, ConstantErrorDecimationCriteria<_>>::new().decimation_criteria(None);

This might need some architectural re-jig.

As an option, instead of None we can have DecimateAlways struct implementing EdgeDecimationCriteria trait. So instead of passing None you can set criteria to DecimateAlways. In this case, the compiler will be able to infer the generic type correctly and the code remains readable. The drawback is that users have to specify decimation_criteria explicitly every time but I think it is not such a big deal.

// edge_decimation.rs
pub struct IncrementalDecimator<TMesh, TCollapseStrategy, TEdgeDecimationCriteria>
where 
    TMesh: EditableMesh + TopologicalMesh + MeshMarker, 
    TCollapseStrategy: CollapseStrategy<TMesh>,
    TEdgeDecimationCriteria: EdgeDecimationCriteria<TMesh>

{
    decimation_criteria: Option<TEdgeDecimationCriteria>, // Remove `Option` here
    min_faces_count: usize,
    min_face_quality: TMesh::ScalarType,
    priority_queue: BinaryHeap<Contraction<TMesh>>,
    not_safe_collapses: Vec<Contraction<TMesh>>,
    collapse_strategy: TCollapseStrategy
}

#[derive(Debug, Default)]
pub struct DecimateAlways;

impl<TMesh: Mesh> EdgeDecimationCriteria<TMesh> for DecimateAlways {
    fn should_decimate(&self, _error: TMesh::ScalarType, _mesh: &TMesh, _edge: &TMesh::EdgeDescriptor) -> bool {
        return true;
    }
}

// simplification.rs
let mut decimator2 = EdgeDecimator::new().decimation_criteria(ConstantErrorDecimationCriteria::new(0.01f32));
decimator2.decimate(&mut mesh);
let mut decimator1 = EdgeDecimator::new().decimation_criteria(DecimateAlways);
decimator1.decimate(&mut mesh);

What do you think about it?

[h3mosphere]

As an option, instead of None we can have DecimateAlways struct implementing EdgeDecimationCriteria trait. So instead of passing None you can set criteria to DecimateAlways. In this case, the compiler will be able to infer the generic type correctly and the code remains readable. The drawback is that users have to specify decimation_criteria explicitly every time but I think it is not such a big deal.

This sounds good, I'm happy with whatever you decide is best for the library.

The behaviour may have changed a little bit with respect to how decimation_criteria and min_faces_count interact with each other, in a default behaviour mode. But I havent used the code enough to have an opinion on that.

Regardless, I'll make those changes.

[h3mosphere]

OK, I have made those changes.

I added AlwaysDecimate, and NeverDecimate trait implementors. Changed from DecimateAlways, as DecimateNever seemed awkward.

Also updated usage comments where appropriate, and documented the new trait.

Please rename anything as you see appropriate. I don't like naming myself, and have no opinions.

Hopefully this is now done :D

[h3mosphere]

Little screenshot:

[h3mosphere]

It would be nice to leave edges alone on non-manifold meshes. Not sure if this is possible, any thoughts appreciated.

[dima634]

Approved. Feel free to merge it. Thanks for working on the comments.

It would be nice to leave edges alone on non-manifold meshes. Not sure if this is possible, any thoughts appreciated.

I think it is possible. We just need to make sure that these edges stay topologically unconnected to the opposites. Otherwise, iterators that are doing topological queries may get stuck in an infinite loop. Overall, it is probably more complicated than sounds. Right now non-manifold edges are removed here.

[h3mosphere]

Not sure what you mean by merge..? I don't have commit rights..

[dima634]

Didn't know that. Sorry for the confusion.

[dima634]

Would you like to get collaborator access?

[h3mosphere]

Would you like to get collaborator access?

Thanks! For the moment, I am just beginning my journey with geometry processing for my own purposes. I'm happy for the moment to just go with pull requests. Once I get up more to speed, and understand baby_shark better, sure. Thanks for the offer though..