TriMesh::cast_local_ray_and_get_normal requires reading source code to use correctly. The issue is that if the ray intersects with a backface, the function sets feature to FeatureId::Face(best + self.indices().len() as u32). When I unwrap the index and attempt to read the triangle (using TriMesh::triangle), I get an index out of bounds error.

This behavior isn't documented clearly enough. Later I learned that I can use TriMesh::is_backface to check whether it's a backface, but even then I can't know how to get the "real index", except by reading the source code and relying on an implementation detail.

Here's a pseudocode to demonstrate the problem

let mesh = TriMesh::new( ... );
let ray = ..;
if let Some(intersection) = mesh.cast_local_ray_and_get_normal(&ray, 1000.0, false) {
    let tri_index = intersection.feature.unwrap_face();
    // if the face is a backface, the following line panics
    let tri = mesh.triangle(tri_index);
}

In some places, parry uses the FeatureId enum, but TrackedContent uses a plain u32 for its feature IDs. This is also easily confused with the subshape u32s in ContactManifold, which identify logical shapes but not individual geometric features of a single shape (i.e. not necessarily a specific face, edge, or vertex). It's also unclear whether feature IDs in contact manifolds are scoped to shapes or subshapes, whereas FeatureIds necessarily must be shape-scoped since they're e.g. returned by PointQuery.

See also Discord discussion. Opening an issue for tracking purposes.

When using segments_intersection2d, I get misleading results. Instead of first_loc1 being OnVertex(0), I get OnEdge([1.0, 0.0]). While they represent the same point, the result is misleading since the doc comment of OnEdge says
The point lies on the segment interior., and OnVertex would be more precise. One should also note that OnEdge([1.0, 0.0]) != OnVertex(0).

When I run the following code:

use rapier2d::prelude::*;

let seg1 = Segment::new(point![10.0, 0.0], point![10.0, 10.0]);
let seg2 = Segment::new(point![10.0, 0.0], point![10.0, 10.0]);

let intersection = rapier2d::parry::utils::segments_intersection2d(&seg1.a, &seg1.b, &seg2.a, &seg2.b, 0.0).unwrap();

let rapier2d::parry::utils::SegmentsIntersection::Segment { first_loc1, first_loc2, second_loc1, second_loc2 } = intersection else {
    unreachable!("The intersection should be a Segment intersection!");
};

dbg!(first_loc1);
dbg!(first_loc2);
dbg!(second_loc1);
dbg!(second_loc2);

The output is

first_loc1 = OnEdge([1.0, 0.0])
first_loc2 = OnVertex(0)
second_loc1 = OnEdge([0.0, 1.0,])
second_loc2 = OnVertex(1)

The output should be:

first_loc1 = OnVertex(0)
first_loc2 = OnVertex(0)
second_loc1 = OnVertex(1)
second_loc2 = OnVertex(1)

rustc: 1.65
parry2d: tested on 0.10 and 0.11.1

Running cargo build --features serde-serialize fails.

Specifically this issue is only for building the parry2d and parry2d-f64 packages.

One of the errors:

error[E0277]: the trait bound `ArrayVec<[TrackedContact<ContactData>; 2]>: Deserialize<'_>` is not satisfied
   --> build/parry2d/../../src/query/contact_manifolds/contact_manifold.rs:73:1

It seems that the "arrayvec/serde" feature is not enabled when the the serde-serialize feature is enabled.

partitioning is the easier of the two, as its just replacing std with alloc and importing Vec/vec

transformation would have to be changed slightly as you use HashMap and HashSetin a number of places. This might be able to be transition to hashbrown's HashMap and HashSet types.

I haven't looked into parry dependencies but it doesn't seem that much of it requires std. A quick skim of it seems to just be spade for the transformation module

convex_hull will panic on some degenerate inputs.

Repro with Parry3d 0.7.0 (f32):

    #[test]
    fn chull_panic()
    {
        use nalgebra as na;
        let points: [na::Point3<f32>; 4] = [
            [0.000000000000000000000023624029, 0.000000000000000000000013771984, 0.0000000000000000000000022062083].into(),
            [0.000000000000000000000013807439, 0.000000000000000000000018596945, -0.000000000000000000000001784406].into(),
            [0.000000000000000000000014174896, -0.000000000000000000000003200329, 0.000000000000000000000004664615].into(),
            [0.000000000000000000000013685897, 0.0000000000000000000000046402988, 0.0000000000000000000000022509113].into(),
        ];
        let _= parry3d::transformation::convex_hull(&points[..]);
    }

Backtrace:

running 1 test
thread 'meshutil::test::chull_panic' panicked at 'called `Option::unwrap()` on a `None` value', C:\Users\fake\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.0\src\transformation\convex_hull3\initial_mesh.rs:151:74
stack backtrace:
  [...]
  16:     0x7ff71159ea69 - enum$<core::option::Option<usize>>::unwrap<usize>
                               at /rustc/a178d0322ce20e33eac124758e837cbd80a6f633\library\core\src\option.rs:388
  17:     0x7ff7115ed82b - parry3d::transformation::convex_hull3::initial_mesh::get_initial_mesh
                               at C:\Users\fake\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.0\src\transformation\convex_hull3\initial_mesh.rs:151
  18:     0x7ff711590a2b - parry3d::transformation::convex_hull3::convex_hull::convex_hull
                               at C:\Users\fake\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.0\src\transformation\convex_hull3\convex_hull.rs:26
  19:     0x7ff7115415b6 - evogame::meshutil::test::chull_panic
                               at C:\pbox\dev\rust\evogame\src\meshutil.rs:113
  [...]

This bug has been around for a long time (inherited from ncollide). It looks like the problem is due to convex_hull_utils::normalize() . The bbox is nonempty, but in (max-min.norm()), the squared components underflow to 0, so let diag = na::distance(&aabb.mins, &aabb.maxs); returns 0, and then normalize divides by zero.

Later, support_point_id() fails because the points are all NaN, so all points fail the test for finding the support point.

Possible fixes:

• Could be fixed by checking explicitly for that case (AABB.diagonal length = 0) and returning a 1-point degenerate hull in that case. (Just skipping the division would do it, since the eigenvalues would be near 0 and get_initial_mesh() would treat it as a 0-D case instead of 3-D).
• The dimensionality count (from the eigenvalues) counts NaN as a nonzero dimension, so this ends up in the 3D case instead of the 0D case. It could be fixed to not count NaN as a nonzero eigenvalues.

(I'm not actually sure why the normalization is being done in the first place; convex hull is in principle an exact operation, and normalizing the overall shape doesn't necessarily improve the conditioning of any particular triangles. It also means the returned points are no longer a subset of the input points. Maybe there are a bunch of epsilons in the code that assume approximately-unit overall scale?)

The comment for the time_of_impact query suggests the existence of a threshold distance but this has been removed since release 0.3. The old API was useful to me but I guess I can just shift pos2 by the threshold distance? Is there any chance of getting the old API back?

/// Computes the smallest time when two shapes under translational movement are separated by a
/// distance smaller or equal to `distance`.
///
/// Returns `0.0` if the objects are touching or penetrating.
pub fn time_of_impact(
    pos1: &Isometry<Real>,
    vel1: &Vector<Real>,
    g1: &dyn Shape,
    pos2: &Isometry<Real>,
    vel2: &Vector<Real>,
    g2: &dyn Shape,
    max_toi: Real,
) -> Result<Option<TOI>, Unsupported> {
    let pos12 = pos1.inv_mul(pos2);
    let vel12 = pos1.inverse_transform_vector(&(vel2 - vel1));
    DefaultQueryDispatcher.time_of_impact(&pos12, &vel12, g1, g2, max_toi)
}

Happened in #63, strange that this doesn't show as a warning.

The current QBVH implementation requires that the content type be aware of its own index within the QBVH, which means that any consumer needs to manage these values and correlate them directly.

An alternate perspective on this problem is that GenericQbvh isn't generic enough to meaningfully allow implementation of custom storages beyond "It's an array on (device)".

Problem

If I naively map application keys to arbitrary points in the usize space of IndexedData, memory usage explodes due to the current implementation creating a dense vector where the usize-index is the true offset into the vector, so 4 giga-elements are produced and default-initialized.

With the new "update" semantics from #113, it's possible to update the Qbvh instance on the fly, but any gap left in the index space produces areas in the array that are "gaps" of invalid entries. This isn't a problem, and is probably necessary for maintainable yet effective CUDA and SIMD implementations. This also isn't new- simply inserting values with prior

The problem is that correlation to application state that produces a changing space makes it very difficult to assign and manage keys efficiently, and keep them in sync with a non-fixed set of application-level entities.

Workaround

I've taken to using a SlabMap to correlate my application-specific keys to the slab IDs, and using those as the actual IndexedData key. Unfortunately, this means that I then need to produce custom visitors that resolve such IDs back to references to my actual key-type for further correlation back to application-level entities.

I've attempted to write a wrapper for this, but the generic functions to cross-correlate IDs result in a large amount of duplicate signatures from those in GenericQbvh.

Possible solution

If GenericQbvh were made to work in terms of a trait QbvhStorage<LeafData, LeafId> { ... } that was capable of defining the mapping from LeafId to LeafData references or even literal usize offsets into a vector of LeafData, then this dense representation could either be avoided for cases of truly-arbitrary Index values, or could be wrapped with a way of statefully assigning indexes to translate sparse keys to dense storage.

In other words, one of the following two options:

1. Allow arbitrary keys by providing a means of binding a HashMap representation or similar (may make SIMD implementation difficult)

2. Make storage generic enough to allow a definition which automatically manages the index space, given an arbitrary Eq + Ord + Hash key-type, while still providing the current method which "cares" which index it is, and assumes the application will manage these values.

I believe option 2 will be the best one to implement, as it maximizes functionality with minimal increase in maintenance cost. This assumes that it is possible to bake the trait-level mapping operations during insert/removal/update operations to maintain a dense storage efficiently without much impact to the SIMD and CUDA implementations.

Triangle::contains_point gives false-positives. I have a point and a triangle pair for which rapier3d::parry::query::PointQuery::distance_to_local_point returns 0.15627049. When I check the point and the triangle visually, the point is clearly NOT at/in the triangle. However, Triangle::contains_point returns true for the pair. Here's the code to reproduce.

        let p = na::Point3::new(22.01,3.7,-0.291);
        let tri = rapier3d::prelude::Triangle::new(
            na::Point3::new(21.94, 3.7, 0.0), 
            na::Point3::new(22.255, 3.7, -0.315),
            na::Point3::new(22.255, 3.5, -0.315)
        );
        let dist = rapier3d::parry::query::PointQuery::distance_to_local_point(&tri, &p, true);
        dbg!(dist); // 0.15627049
        assert!(!tri.contains_point(&p)); // FAILS

I'm using rapier3d 0.11.1, which still installs the old parry3d 0.7.1.

The following input panics:

thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 0', .../build/parry2d/../../src/shape/convex_polygon.rs:40:12

    let verts = vec![
     Point::new(0.04296875, -0.021484375),
        Point::new(0.041015625, -0.0234375),
        Point::new(0.0390625, -0.025390625),
        Point::new(0.037109375, -0.02734375),
        Point::new(0.03515625, -0.025390625),
        Point::new(0.033203125, -0.0234375),
        Point::new(0.029296875, -0.0234375),
        Point::new(0.02734375, -0.021484375),
        Point::new(0.029296875, -0.01953125),
        Point::new(0.033203125, -0.01953125),
        Point::new(0.037109375, -0.01953125),
        Point::new(0.041015625, -0.01953125),
        Point::new(0.04296875, -0.021484375),
    ];
    let indices = vec![
        [0, 1],
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 5],
        [5, 6],
        [6, 7],
        [7, 8],
        [8, 9],
        [9, 10],
        [10, 11],
        [11, 12],
    ];
    let shape =
       SharedShape::convex_decomposition_with_params(&verts, &indices, &VHACDParameters {
            resolution: 64,
            ..VHACDParameters::default()
        });

This seems to depend on the resolution, if I use 32 or more than 64 on this specific input, it works. I'd like to use 32 or 64 for speed. It does end up in this panic however occasionally with some inputs.

Investigation:
The decomp.compute_exact_convex_hulls(&vertices, &indices) after decompose outputs some empty vertex vectors and passes them to ConvexPolygon::from_convex_polyline. Which then panics when indexing first normal[0] when checking if first vertex should be removed.

Two fix ideas:

1. Figure out why compute_exact_convex_hulls outputs empty sets of points, fix that or just filter empty parts out.
2. Don't allow ConvexPolygon::from_convex_polyline to work on empty vectors... (return early if points.len() == 0.

Hi, I want use parry3d::transformation::intersect_meshes on some meshes that i constrict from points and faces.

Acc to the documentation intersect_meshes require that halfedges have been computed.
It seems like compute_topology does exatly what i want, to enable intersect_meshes

Why is compute_topology a private method?

Can it or something similar to it be made public?

I'm running convex decomposition on this model: model.tar.gz

I get the following panic:

thread 'main' panicked at 'attempt to subtract with overflow', /Users/will/.cargo/registry/src/github.com-1ecc6299db9ec823/parry3d-0.5.1/src/shape/convex_polyhedron.rs:119:22
stack backtrace:
   0: _rust_begin_unwind
   1: core::panicking::panic_fmt
   2: core::panicking::panic
   3: parry3d::shape::convex_polyhedron::ConvexPolyhedron::from_convex_mesh
             at /Users/will/.cargo/registry/src/github.com-1ecc6299db9ec823/parry3d-0.5.1/src/shape/convex_polyhedron.rs:119:22
   4: parry3d::shape::shared_shape::SharedShape::convex_mesh
             at /Users/will/.cargo/registry/src/github.com-1ecc6299db9ec823/parry3d-0.5.1/src/shape/shared_shape.rs:269:9
   5: parry3d::shape::shared_shape::SharedShape::convex_decomposition_with_params
             at /Users/will/.cargo/registry/src/github.com-1ecc6299db9ec823/parry3d-0.5.1/src/shape/shared_shape.rs:212:35
   6: parry3d::shape::shared_shape::SharedShape::convex_decomposition
             at /Users/will/.cargo/registry/src/github.com-1ecc6299db9ec823/parry3d-0.5.1/src/shape/shared_shape.rs:175:9
   7: preprocess_model::after_spawn
             at ./src/bin/preprocess-model/main.rs:58:18

This happens because a convex hull passed to SharedShape::convex_mesh has fewer than 2 total vertices and indices (presumably empty).

Hi!

I don't know whether this is a bug or a problem in the docs, but if you do a convex decomposition with a clockwise polygon, each shape in the decomposition will also be clockwise, and therefore will not work properly with SharedShape::convex_polyline. In turn, this means that the resulting compound shape will not work as expected.

The docs for SharedShape::convex_decomposition don't mention that shapes have to be counter-clockwise, and neither do the user guides. Similarly, the docs for SharedShape::convex_polyline don't mention that either, and it's only when looking at ConvexPolygon::from_convex_polyline that the counter-clockwise condition is ever mentioned.

Thanks for the amazing engine btw :-) people who played my LDJam game kept saying they were impressed by the physics, for which y'all are 100% responsible.

I'd like to be able to create a TriMesh from non-convex 2D polygons.

I have a PR ready implementing the ear-clipping algorithm. Once we have this, we can think about adding the Hertel-Mehlhorn algorithm that combines the triangles into convex polygons again, to give a good convex decomposition.

The reason for this is that, at least in my experiments, the VHACD algorithm is orders of magnitude slower than this method.

The current implementation of TriMesh forces me to have two copies of my vertex buffer, because I have a custom Vertex type that
has additional data associated with it and TriMesh only stores points as vertices.

The simplest solution that comes to my mind, would be to allow a generic parameter for the specific vertex type together with a Vertex trait which provides one method, which is get_point.

What do you think?

Sweeping a capsule through a cuboid with repeated intersection tests seems to produce multiple false negatives:

use parry3d::{
    na::{Isometry3, Translation3, Unit, Vector3},
    query::intersection_test,
    shape::{Ball, Capsule, Cuboid, HalfSpace},
};

fn main() {
    let capsule = Capsule::new([0.0, -0.5, 0.0].into(), [0.0, 0.5, 0.0].into(), 0.5);

    // This capsule, equivalent to the ball, also produces false negatives
    // let capsule = Capsule::new([0.0, 0.0, 0.0].into(), [0.0, 0.0, 0.0].into(), 0.5);

    let ball = Ball::new(0.5);

    let halfspace = HalfSpace::new(Unit::new_normalize(Vector3::from([0.0, 1.0, 0.0])));

    // Upper face of the cuboid is coplanar with the outer face of the halfspace
    let cuboid = Cuboid::new([50.0, 50.0, 50.0].into());
    let cuboid_pos = Isometry3 {
        translation: Translation3::from(Vector3::from([0.0, -50.0, 0.0])),
        ..Default::default()
    };

    let steps = 200;
    let y_max = 0.5;
    let y_min = -0.5;
    let step_size = (y_max - y_min) / steps as f32;

    let mut capsule_cuboid = 0;
    let mut capsule_halfspace = 0;
    let mut ball_cuboid = 0;
    let mut ball_halfspace = 0;

    for step in 0..steps {
        let y = y_min + step_size * step as f32;

        let test_pos = Isometry3 {
            translation: Translation3::from([0.0, y, 0.0]),
            ..Default::default()
        };

        if intersection_test(&test_pos, &capsule, &Isometry3::default(), &halfspace).unwrap() {
            capsule_halfspace += 1;
        }

        if intersection_test(&test_pos, &capsule, &cuboid_pos, &cuboid).unwrap() {
            capsule_cuboid += 1;
        }

        if intersection_test(&test_pos, &ball, &Isometry3::default(), &halfspace).unwrap() {
            ball_halfspace += 1;
        }

        if intersection_test(&test_pos, &ball, &cuboid_pos, &cuboid).unwrap() {
            ball_cuboid += 1;
        }
    }

    println!("capsule-cuboid intersections:    {}/{}", capsule_cuboid, steps);
    println!("capsule-halfspace intersections: {}/{}", capsule_halfspace, steps);
    println!("ball-cuboid intersections:       {}/{}", ball_cuboid, steps);
    println!("ball-halfspace intersections:    {}/{}", ball_halfspace, steps);
}

Outputs:

capsule-cuboid intersections:    86/200
capsule-halfspace intersections: 200/200
ball-cuboid intersections:       200/200
ball-halfspace intersections:    200/200

The documentation says:

Tests if the given point is inside of a polygon with arbitrary orientation.

which sounds like it should work with any arbitrary polygon. However, in my application, I have non-convex polygons I tested against, and while there are no false positives, it leaves parts of the polygon out:

(the tracing is inexact, I'm just spawning a dot whenever the mouse is detected to be inside the polygon)

Based on the output I'd guess it only works for convex polygons (although I don't understand the algorithm), in which case it would be nice to have a mention of this in the docs.

I've been trying to track down an issue for a while in my game where the character "glitches" into walls while sliding against them. I'm using a time-of-impact query via Qbvh. It seemed to happen relatively consistently in roughly the same spots, so I collected position and velocity traces and came up with the following case that seems to 100% reproduce the issue. It appears the Qbvh TOI query inexplicably returns no intersections in cases where it definitely should.

Consider the following minimum reproducible example:

// == Setup ==

let b = Ball::new(96.0);
let b_pos = na::Vector2::new(216.02324, -1632.0032);
let b_vel = na::Vector2::new(-636.3961, -636.3961);

let c = Cuboid::new(na::Vector2::new(2560.0 / 2.0, 192.0 / 2.0));
let c_pos = na::Vector2::new(0.0, -1824.0);

// == TOI via DefaultQueryDispatcher directly ==

let pos12 = na::Isometry2::new(b_pos - c_pos, 0.0);
let res = DefaultQueryDispatcher{}.time_of_impact(
	&pos12,
	&b_vel,
	&b,
	&c,
	1.0 / 60.0,
	true,
);
println!("{:?}", res);
// Ok(Some(TOI { toi: 3.3994795e-8, witness1: [0.59887993, 95.9968], witness2: [-215.42442, -96.0], normal1: [[-0.0, 1.0]], normal2: [[0.0, -1.0]], status: Converged }))

// == TOI via Qbvh ==

#[derive(Copy, Clone)]
pub struct DummyData;

impl IndexedData for DummyData {
	fn default() -> Self { DummyData{} }
	fn index(&self) -> usize { 0 }
}

pub struct SingleCompositeShape<'a> {
	bvh: &'a Qbvh::<DummyData>,
	pos: &'a na::Vector2<Real>,
	shape: &'a Cuboid,
}

impl<'a> TypedSimdCompositeShape for SingleCompositeShape<'a> {
	type PartShape = dyn Shape;
	type PartId = DummyData;
	type QbvhStorage = DefaultStorage;

	fn map_typed_part_at(
		&self,
		_: Self::PartId,
		mut f: impl FnMut(Option<&Isometry<Real>>, &Self::PartShape),
	) {
		f(Some(&Isometry2::new(*self.pos, 0.0)), self.shape);
	}

	fn map_untyped_part_at(
		&self,
		shape_id: Self::PartId,
		f: impl FnMut(Option<&Isometry<Real>>, &Self::PartShape),
	) {
		self.map_typed_part_at(shape_id, f);
	}

	fn typed_qbvh(&self) -> &Qbvh<DummyData> {
		&self.bvh
	}
}

struct SingleDataGenerator {
	aabb: Aabb,
}

impl QbvhDataGenerator<DummyData> for SingleDataGenerator {
	fn size_hint(&self) -> usize { 1 }
	fn for_each(&mut self, mut f: impl FnMut(DummyData, Aabb)) {
		f(DummyData{}, self.aabb);
	}
}

let mut bvh = Qbvh::<DummyData>::new();
let gen = SingleDataGenerator {
	aabb: c.compute_aabb(&Isometry2::new(c_pos, 0.0)),
};
bvh.clear_and_rebuild( gen, 0.0);

let dispatcher = DefaultQueryDispatcher{};
let shapes = SingleCompositeShape { bvh: &bvh, pos: &c_pos, shape: &c };
let b_iso = Isometry2::new(b_pos, 0.0);
let mut visitor = TOICompositeShapeShapeBestFirstVisitor::new(
	&dispatcher,
	&b_iso,
	&b_vel,
	&shapes,
	&b,
	1.0/60.0,
	true,
);

match bvh.traverse_best_first(&mut visitor).map(|h| h.1) {
	Some((_, toi)) => println!("Result: {:?}", toi),
	None => println!("Result: None"),
}
// Result: None

As commented in the code, the above code results in the following console output:

Ok(Some(TOI { toi: 3.3994795e-8, witness1: [0.59887993, 95.9968], witness2: [-215.42442, -96.0], normal1: [[-0.0, 1.0]], normal2: [[0.0, -1.0]], status: Converged }))
Result: None

We get the expected results when invoking DefaultQueryDispatcher::time_of_impact() directly, but get no results when calling bvh.traverse_best_first(TOICompositeShapeShapeBestFirstVisitor) with the same data. However, if we tweak the ball's position slightly, we get the expected result in both cases:

let b_pos = na::Vector2::new(216.02324, -1632.0); // instead of (216.02324, -1632.0032)

We then get the following output:

Ok(Some(TOI { toi: 3.0255871e-6, witness1: [0.0, -0.0017995844], witness2: [-216.02127, -191.99988], normal1: [[-0.0, 1.0]], normal2: [[0.0, -1.0]], status: Converged }))
Result: TOI { toi: 3.0255871e-6, witness1: [-0.0016784668, -1824.0018], witness2: [-216.02295, -191.99988], normal1: [[-0.0, 1.0]], normal2: [[0.0, -1.0]], status: Converged }

My Cargo.toml has

parry2d = { version = "0.11.1", features = [ "enhanced-determinism" ] }

Obviously not all issues are applicable to this new crate, but there could be issues to take note of from ncollide.

Maybe this could be a huge breaking change to ncollide?

When using rotated Polyline time_of_impact returns a result as it is not rotated. See tests below for details.

This test fails because time_of_impact returns None:

#[test]
fn time_of_impact_should_return_toi_for_ball_and_rotated_polyline() {
    let ball_isometry = Isometry2::identity();
    let ball_velocity = Vector2::new(1.0, 0.0);
    let ball = Ball::new(0.5);
    let polyline_isometry = Isometry2::rotation(-std::f32::consts::FRAC_PI_2);
    let polyline_velocity = Vector2::zeros();
    let polyline = Polyline::new(vec![Point2::new(1.0, 1.0), Point2::new(-1.0, 1.0)], None);

    assert_eq!(polyline_isometry.transform_point(&Point2::new(1.0, 1.0)), Point2::new(0.99999994, -1.0));
    assert_eq!(polyline_isometry.transform_point(&Point2::new(-1.0, 1.0)), Point2::new(1.0, 0.99999994));

    let toi = query::time_of_impact(
        &ball_isometry, &ball_velocity, &ball,
        &polyline_isometry, &polyline_velocity, &polyline,
        1.0, 0.0,
    ).unwrap();

    assert_eq!(toi.unwrap().toi, 0.5);
}

But this one succeed when Ball with given velocity should not reach polyline at all:

#[test]
fn invalid_time_of_impact_should_return_toi_for_ball_and_rotated_polyline() {
    let ball_isometry = Isometry2::identity();
    let ball_velocity = Vector2::new(0.0, 1.0);
    let ball = Ball::new(0.5);
    let polyline_isometry = Isometry2::rotation(-std::f32::consts::FRAC_PI_2);
    let polyline_velocity = Vector2::zeros();
    let polyline = Polyline::new(vec![Point2::new(1.0, 1.0), Point2::new(-1.0, 1.0)], None);

    assert_eq!(polyline_isometry.transform_point(&Point2::new(1.0, 1.0)), Point2::new(0.99999994, -1.0));
    assert_eq!(polyline_isometry.transform_point(&Point2::new(-1.0, 1.0)), Point2::new(1.0, 0.99999994));

    let toi = query::time_of_impact(
        &ball_isometry, &ball_velocity, &ball,
        &polyline_isometry, &polyline_velocity, &polyline,
        1.0, 0.0,
    ).unwrap();

    assert_eq!(toi.unwrap().toi, 0.5);
}

However when using a Segment time_of_impact behaves correctly:

#[test]
fn time_of_impact_should_return_toi_for_ball_and_rotated_segment() {
    let ball_isometry = Isometry2::identity();
    let ball_velocity = Vector2::new(1.0, 0.0);
    let ball = Ball::new(0.5);
    let segment_isometry = Isometry2::rotation(-std::f32::consts::FRAC_PI_2);
    let segment_velocity = Vector2::zeros();
    let segment = Segment::new(Point2::new(1.0, 1.0), Point2::new(-1.0, 1.0));

    assert_eq!(segment_isometry.transform_point(&Point2::new(1.0, 1.0)), Point2::new(0.99999994, -1.0));
    assert_eq!(segment_isometry.transform_point(&Point2::new(-1.0, 1.0)), Point2::new(1.0, 0.99999994));

    let toi = query::time_of_impact(
        &ball_isometry, &ball_velocity, &ball,
        &segment_isometry, &segment_velocity, &segment,
        1.0, 0.0,
    ).unwrap();

    assert_eq!(toi.unwrap().toi, 0.49999994);
}

When trying to ray cast with AABB with min and max=0. Gives the following error:

thread 'main' panicked at 'Matrix index out of bounds.', /Users/fredrik/.cargo/registry/src/github.com-1ecc6299db9ec823/parry3d-0.7.1/src/query/clip/clip_aabb_line.rs:141:13

I'm getting a wrong result from corner_direction for a specific set of points. The following test fails, even though the points are clearly not on a line:

#[test]
fn corner_direction_bug() {
    let p1 = Point::from([-0.5, 0.8660254037844387]);
    let p2 = Point::from([1., 1.7320508075688772]);
    let p3 = Point::from([-2., 0.]);

    assert_ne!(corner_direction(&p1, &p2, &p3), Orientation::None);
}

I don't know what is special about these values. These just happened to be the points I've seen this issue with in my code base (modulo some light rounding). If I round the longer values (to 0.9 or 1.7), the test no longer fails.

Due to a division by 0 in Sum<MassProperties> it is possible to get NaN values.

This can happen when e.g. trying to compute the MassProperties of a HeighField.

I believe the sum function should either panic or return as soon as it detects the total mass is 0.

Reproduction project:

// src/main.rs

use rapier3d::pipeline::*;
use rapier3d::dynamics::*;
use rapier3d::geometry::*;
use rapier3d::na::*;

fn main() {

	let mut pipeline = PhysicsPipeline::new();
	let gravity = Vector3::new(0.0, -9.81, 0.0);
	let integration_parameters = IntegrationParameters::default();
	let mut broad_phase = BroadPhase::new();
	let mut narrow_phase = NarrowPhase::new();
	let mut bodies = RigidBodySet::new();
	let mut colliders = ColliderSet::new();
	let mut joints = JointSet::new();
	let physics_hooks = ();
	let event_handler = ();

	let body = RigidBodyBuilder::new_dynamic().translation(0.0, 1.01, 0.0).build();
	let handle = bodies.insert(body);
	let collider = ColliderBuilder::ball(1.0).build();
	colliders.insert(collider, handle, &mut bodies);

	let shape = SharedShape::heightfield(DMatrix::zeros(10, 10), Vector3::new(9.0, 1.0, 9.0));
	let collider = ColliderBuilder::new(shape.clone()).build();
	let mut body = RigidBodyBuilder::new_static().build();
	let position = *body.position();
	let mp = MassProperties::from_compound(1.0, &vec![(position, shape)][..]);
	dbg!(collider.mass_properties()); // This is fine
	dbg!(mp); // This has NaN center of mass
	body.set_mass_properties(mp, true);
	let handle = bodies.insert(body);
	colliders.insert(collider, handle, &mut bodies);

	loop {
		pipeline.step(
			&gravity,
			&integration_parameters,
			&mut broad_phase,
			&mut narrow_phase,
			&mut bodies,
			&mut colliders,
			&mut joints,
			&physics_hooks,
			&event_handler,
		);
		for (_, b) in bodies.iter() {
			if b.is_dynamic() {
				// The position of the ball also becomes NaN due to this
				println!("{}", b.position());
				assert!(!b.position().translation.x.is_nan());
			}
		}
	}
}

# Cargo.toml

[package]
name = "rapier3d_heightfield_nan"
version = "0.1.0"
authors = ["David Hoppenbrouwers <[email protected]>"]
edition = "2018"

[dependencies]
rapier3d = "*"

This line should be self.to_polyline(nsubdivs) instead of Self::new(0.5).to_polyline(nsubdivs).

Because AABB is POD you can do #[archive(as = "AABB")] in the struct definition and then users of archived buffers can get AABB with zero-copy deserialization.

closest_points panics when a Cylinder and Trimesh are tested and the objects are not within max_dist of each other. I believe the function is actually supposed to return Disjoint instead. Here is a specific example I've found:

use parry3d::{math::*, query, shape::*};

fn main() {
    let cylinder = Cylinder::new(0.5, 1.0);

    let vertices = vec![
        Point::new(1.0, -1.0, 0.0),
        Point::new(-1.0, -1.0, 0.0),
        Point::new(0.0, -1.0, 1.0),
    ];
    let indices = vec![[0, 1, 2]];
    let trimesh = TriMesh::new(vertices, indices);

    // let max_dist = 0.5; // Fine
    let max_dist = 0.49; // Panics

    let _ = query::closest_points(
        &Isometry::identity(),
        cylinder.clone_box().as_ref(),
        &Isometry::identity(),
        trimesh.clone_box().as_ref(),
        max_dist,
    );
}

As in title. I have the feeling you guys might be seriously underestimating the importance of this.

Examples required:

• how to get the distance between points, or a point and a segment
• how to do intersections between segments
• how to do ray casting, and get the intersecting point
• how to use the polygon shape (figuring out whether it is closed loop, doing intersections etc)

Even if you just 'dump' say 10 code examples in the index of the documentation, that would already go a long way.

TriMeshConnectedComponents.face_groups data contains lots of duplicate values. Here's a minimalist test code to reproduce the problem.

    #[test]
    fn test_components_grouped_faces() {
        let verts = vec![
            // Originally face 126
            na::Point3::new(15.82, 6.455, -0.15),
            na::Point3::new(9.915, 6.455, -0.15),
            na::Point3::new(9.915, 6.4, 0.0),

            // Originally face 127
            na::Point3::new(15.82, 6.455, -0.15),
            na::Point3::new(9.915, 6.4, 0.0),
            na::Point3::new(15.82, 6.4, 0.0),
        ];

        let mut roof = TriMesh::new(
            verts,
            vec![[0, 1, 2], [3, 4, 5]],
        );

        if let Err(e) = roof.set_flags(TriMeshFlags::MERGE_DUPLICATE_VERTICES | TriMeshFlags::CONNECTED_COMPONENTS) {
            dbg!(e);
            assert!(false);
        }

        let components = roof.connected_components().unwrap();
        dbg!(components);
    }

Output:

[X] components = TriMeshConnectedComponents {
    face_colors: [0, 0,],
    grouped_faces: [0, 1, 1, 0, 0, ],
    ranges: [ 0, 5,],
}

I think the duplicates should be eliminated by parry. Otherwise downstream is forced to make sure their code works with duplicate faces.

I noticed this first on parry3d 0.10.0, but it appears with parry3d 0.11.1 as well.
rustc 1.66.0

Since parry2d doesn't have much documentation yet, I found this example from ncollide: https://www.ncollide.org/geometric_queries/#contact

However, in parry, it doesn't find any collision, and we get Ok(None). Am I misunderstanding some difference between ncollide and parry here?

#[test]
fn test_contact_example() {
    let contact = query::contact(
        &Isometry::translation(1.0, 1.0),
        &Ball::new(1.0),
        &Isometry::identity(),
        &Cuboid::new(Vector2::new(1.0, 1.0)),
        1.0,
    )
    .unwrap()
    .unwrap();

    assert!(contact.dist < 0.0);
}

ShapeType's options are all rather specific, preventing an implementer of Shape from introducing significantly diverse custom shapes. A ShapeType::Custom might be missing, or perhaps Shape::shape_type should return Option.

As of the 0.7 release:

2D Shapes that implement PartialEq:

• Ball
• Cuboid
• Segment
• Triangle
• HalfSpace

2D Shapes that don't implement PartialEq:

• Capsule
• TriMesh
• Polyline
• HeightField
• Compound
• ConvexPolygon
• RoundCuboid
• RoundTriangle
• RoundConvexPolygon

3D Shapes that implement PartialEq:

• Ball
• Cuboid
• Segment
• Triangle
• HalfSpace
• ConvexPolyhedron
• Cylinder
• Cone

3D Shapes that don't implement PartialEq:

• Capsule
• TriMesh
• Polyline
• HeightField
• Compound
• RoundCuboid
• RoundTriangle
• RoundCylinder
• RoundCone
• RoundConvexPolyhedron

I don't understand why some of these shapes don't implement PartialEq<Self>. Is there any particular reason for this?

Compound would be harder because of SharedShape, but the rest mostly seem like they could derive it.

RoundShape could implement it with the following:

impl<S: Shape + PartialEq> PartialEq for RoundShape<S> {
  fn eq(&self, other: &Self) -> bool {
    self.border_radius == other.border_radius && self.base_shape == other.base_shape
  }
}

We should add an automatic computation of triangle-mesh mass properties.
This would implicitly assume that the TriMesh is manifold and have consistent winding.

That paper suggests that this should be fairly easy to implement, based on the existing code that computes ConvexPolyhedron mass properties.

I have a triangle and a point for which I need to compute the distance. However, when the triangle is degenerate, the result can be very very wrong. Here's a test to demonstrate the issue:

        let p = na::Point3::new(1.10000002, -7.9000001, 16.5879993);

        let a = na::Point3::new(2.27699995, -7.9000001, 16.3180008);
        let b = na::Point3::new(-0.569999993, -8.10000038, 16.6070004);
        let c = na::Point3::new(-0.569999993, -8.10000038, 16.6070004);

        let line = rapier3d::parry::shape::Polyline::new(vec![a, b], None);

        let tri = rapier3d::parry::shape::Triangle::new(a, b, c);

        assert_eq!(tri.area(), 0.0);

        assert!(tri.local_aabb().contains_local_point(&p));

        let tri_dist = rapier3d::parry::query::PointQuery::distance_to_local_point(&tri, &p, true);
        let line_dist = rapier3d::parry::query::PointQuery::distance_to_local_point(&line, &p, true);
        
        assert!(line_dist > 0.0);
        assert_eq!(tri_dist, line_dist);

        // :tri_pt_dist_degen' panicked at 'assertion failed: `(left == right)`
        // left: `0.0`,
        // right: `0.17147861`'

If I treat the triangle as a line, the distance is computed correctly. At least it looks correct visually judging.

I'm using rapier3d 0.11.1, which still installs the old parry3d 0.7.1.0

Not sure how this slips through the compiler or linter. But I think it's because QBVHNode is in a private module without an explicit re-export.

The documentation for SharedShape::convex_polyline should mention that the polygon needs to be given in counter-clockwise orientation:

First pointed out in #55.

When I compute the area of a triangle with the provided Triangle::area -function, the area can be very wrong.

    let tri = Triangle::new(
        na::Point3::new(1.811, -2.871, 17.464),
        na::Point3::new(1.811, 1.629, 17.464),
        na::Point3::new(1.811, -1.521, 17.464),
    );

    let area = tri.area();

    dbg!(area);

[src/main.rs:37] area = 0.0010679931

Since the triangle is degenerate, the area should be 0. Perhaps ironically, if I calculate with Heron's formula (which tends to give more inaccurate results for needle-like triangles) the resulting area is 0 as it should be. A f64-implementation of Triangle::area also works.

Now I'm not an expert of floating point mathematics nor mathematics in general, but I wonder if Kahan's formula could be replaced with something else? Something called Graham's determinant (f32) also produced 0 when I tried it, but I wonder how its accuracy compares with Kahan's in general. And of course it would be possible to use f64 internally.

This is not the most important issue to solve I think. After all, this is just how Kahan's formula works, and one can use parry-f64 or implement the formula with f64 instead.

Issue

Compiling parry 0.9.0 generates a lot of errors about the types used by parry to implementing Serializable. All the problematic types can be traced back to nalgebra: OPoint, Unit, Matrix

Steps to reproduce

1. Create an empty project
2. Add parry2d = { version = "0.9", features = ["serde"] } to the Cargo.toml
3. Run cargo check

Face color computation doesn't seem to work. In my simple test case, all the values were equal to u32::MAX.

    let verts = vec![
        // Tri 1
        na::Point3::new(0.0, 0.0, 0.0),
        na::Point3::new(10.0, 0.0, 0.0),
        na::Point3::new(10.0, 0.0, 10.0),
        // Tri 2
        na::Point3::new(0.0, 1.0, 0.0),
        na::Point3::new(10.0, 1.0, 0.0),
        na::Point3::new(10.0, 1.0, -1.0)
    ];

    let trimesh = TriMesh::with_flags(
        verts,
        vec![[0, 1, 2], [3, 4, 5]],
        TriMeshFlags::CONNECTED_COMPONENTS
    );

    let components = trimesh.connected_components().unwrap();

    dbg!(components);

    assert!(components.face_colors.iter().all(|v| *v != u32::MAX)); // Fails! All of the values are equal to u32::MAX

Here's the output of dbg!(components)

[src/main.rs:24] components = TriMeshConnectedComponents {
    face_colors: [
        4294967295,
        4294967295,
    ],
    grouped_faces: [
        0,
        1,
    ],
    ranges: [
        0,
        1,
        2,
    ],
}

I noticed this first on parry3d 0.10.0, but it appears with parry3d 0.11.1 as well.
rustc: 1.65.0

Hi, I'm a web developer, I don't know rust language, I got only .rlib and .d files after executing cargo build --target wasm32-unknown-emscripten command, no .wasm and .js files, please What should I do? ---- from translation software

In v0.11.1, time-of-impact queries are returning inconsistent results for toi=0, depending on which shapes are involved.

If both shapes are balls, toi=0 results in status=converged (https://github.com/dimforge/parry/blob/v0.11.1/src/query/time_of_impact/time_of_impact_ball_ball.rs#L45)

	 let status = if inside && center.coords.norm_squared() < rsum * rsum {
	 	 TOIStatus::Penetrating
	 } else {
	 	 TOIStatus::Converged
	 };

If one shape is a cuboid, and the other a ball, toi=0 results in status=penetrating (https://github.com/dimforge/parry/blob/v0.11.1/src/query/time_of_impact/time_of_impact_support_map_support_map.rs#L50):

	status: if toi.is_zero() {
		TOIStatus::Penetrating
	} else {
		TOIStatus::Converged
	},

Throughout the repo, there are various links to the supposed homepage of the project, cdl.org. This however is very obviously not the the project's homepage, nor would it ever include links to its documentation.

Issue occurred after converting vertex input to Angstroms, resulting in very small vertex list:

vertices = [
  [-0.5, -0.5, 0.5],
  [0.5, -0.5, 0.5],
  [-0.5, 0.5, 0.5],
  [0.5, 0.5, 0.5],
  [-0.5, 0.5, -0.5],
  [0.5, 0.5, -0.5],
  [-0.5, -0.5, -0.5],
  [0.5, -0.5, -0.5],
]
indices = [
  [3, 1, 0],
  [2, 3, 0],
  [5, 3, 2],
  [4, 5, 2],
  [7, 5, 4],
  [6, 7, 4],
  [1, 7, 6],
  [0, 1, 6],
  [5, 7, 1],
  [3, 5, 1],
  [2, 0, 6],
  [4, 2, 6]
]

If length_unit below is 1E-10 (1 Angstrom):

let points = input.vertices.iter().map(|p| Point::new(p[0]*length_unit as f32, p[1]*length_unit as f32, p[2]*length_unit as f32)).collect();
let trimesh = TriMesh::new(points, input.indices.clone());

When calling distance_to_local_point(&p, true), parry3d-f32 panics at:

thread 'main' panicked at 'called Option::unwrap() on a None value', C:\Users\Jarat\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.2.0\src\query\point\point_composite_shape.rs:126:59

Debug output from failing quadtree below:
quadtree_debug.txt

I'm trying to serialize a GenericTriMesh in a way that's faster then using bincode since we're seeing some pretty big performance issues with it; however it looks like the combination of simd and rkyv doesn't work nicely;

parry3d = { version = "0.13", features = ["rkyv-serialize", "simd-stable"] }

This is leading to the following compile errors;

error[E0277]: the trait bound `WideF32x4: Archive` is not satisfied
  --> C:\Users\Jasper\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.13.0\src\shape\polyline.rs:16:27
   |
16 |     derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
   |                           ^^^^^^^^^^^^^^^^^ the trait `Archive` is not implemented for `WideF32x4`
   |
   = help: the following other types implement trait `Archive`:
             ()
             (T0,)
             (T1, T0)
             (T10, T9, T8, T7, T6, T5, T4, T3, T2, T1, T0)
             (T11, T10, T9, T8, T7, T6, T5, T4, T3, T2, T1, T0)
             (T2, T1, T0)
             (T3, T2, T1, T0)
             (T4, T3, T2, T1, T0)
           and 192 others
   = note: required for `OPoint<WideF32x4, Const<3>>` to implement `Archive`
   = note: 4 redundant requirements hidden
   = note: required for `GenericQbvh<u32, DefaultStorage>` to implement `Archive`
   = help: see issue #48214
   = note: this error originates in the derive macro `rkyv::Deserialize` (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0277]: the trait bound `WideF32x4: Archive` is not satisfied
  --> C:\Users\Jasper\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.13.0\src\shape\polyline.rs:16:46
   |
16 |     derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
   |                                              ^^^^^^^^^^^^^^^ the trait `Archive` is not implemented for `WideF32x4`
   |
   = help: the following other types implement trait `Archive`:
             ()
             (T0,)
             (T1, T0)
             (T10, T9, T8, T7, T6, T5, T4, T3, T2, T1, T0)
             (T11, T10, T9, T8, T7, T6, T5, T4, T3, T2, T1, T0)
             (T2, T1, T0)
             (T3, T2, T1, T0)
             (T4, T3, T2, T1, T0)
           and 192 others
   = note: required for `OPoint<WideF32x4, Const<3>>` to implement `Archive`
   = note: 4 redundant requirements hidden
   = note: required for `GenericQbvh<u32, DefaultStorage>` to implement `Archive`
   = help: see issue #48214
   = note: this error originates in the derive macro `rkyv::Serialize` (in Nightly builds, run with -Z macro-backtrace for more info)

It seems to be indicating that WideF32x4 in samba doesn't implement the rkyv derives?

When processing queries on a compound shape, QueryDispatcher methods must be invoked recursively. This makes it infeasible for custom shapes that occur inside compound shapes to be handled. Ideally downstream code could provide chainable QueryDispatcher impls that only handle the shapes they introduce and otherwise return Unsupported, but in that case a compound shape would fall through to the default dispatcher, which would recurse internally and fail to handle custom shapes it encounters. Similar issues affect any user-defined composite shapes. This could be fixed by adding a root_dispatcher: &dyn QueryDispatcher argument to every trait method. The same issue also affects PersistentQueryDispatcher.

I can bang this out, but it's a bunch of boilerplate updates and given that this logic was not preserved from ncollide I want to be sure it's welcome before proceeding.

#59 added non-convex polygon to TriMesh conversions. For more efficient operations, we want to turn those TriMeshes into Compound shapes, while merging neighboring triangles into convex polygons. I have a pull request ready that achieves this using the Hertel-Mehlhorn algorithm.

The same was true in ncollide.

This is likely not a bug in Rapier but I wanted to open this issue for visibility in case anyone ever hits this.

I believe there's a miscompilation of some sort of likely happening in Chrome's WebAssembly backend that causes errors in Parry's BVH generation only when Simd128 is used.

Specifically this call to merge within qbvh.rs produces incorrect results:

What I was seeing is this AABB:

AABB { mins: OPoint { coords: Matrix { data: [[0.0, -50.0, 0.0]] } }, maxs: OPoint { coords: Matrix { data: [[199.90764, 175.0, 197.43108]] } } }
when merged with this AABB:
AABB { mins: OPoint { coords: Matrix { data: [[-2824.0708, 46.78899, 948.4769]] } }, maxs: OPoint { coords: Matrix { data: [[-2822.8105, 47.78899, 949.73706]] } } }

would produce this faulty AABB:
AABB { mins: OPoint { coords: Matrix { data: [[-2824.0708, -50.0, 0.0]] } }, maxs: OPoint { coords: Matrix { data: [[0.0, 175.0, 949.73706]] } } }

If I insert log statements that log to the browser console nearby then the code works correctly. Also if the browser console is opened then this code would work correctly until the page is refreshed.

This issue does not reproduce if I replace the call to my_aabb.merge(&aabbs[*id]); with this:

use crate::na::SimdPartialOrd;
let other = aabbs[*id];
my_aabb.mins = my_aabb.mins.coords.zip_map(&other.mins.coords, |a, b| {
    a.simd_min(b)
}).into();
my_aabb.maxs = my_aabb.maxs.coords.zip_map(&other.maxs.coords, |a, b| {
    a.simd_max(b)
}).into();

But does reproduce if I replace it with this:

 my_aabb.mins =  my_aabb.mins.coords.inf(&other.mins.coords).into();
 my_aabb.maxs =  my_aabb.maxs.coords.sup(&other.maxs.coords).into();

Based on how this occurs I'd assume this is a bug in Chrome's WebAssembly backend that occurs only for certain permutations of generated code. Perhaps when the console is opened Chrome runs more conservatievly to facilitate debugging so it does not trigger this behavior?

I may end the investigation here as I've already spent over a day on this, but given how absurdly hard to diagnose this is I wanted to open an issue in case anyone else ever sees something similar.

Potentially relevant: I've only tested this on an M1 Macbook Air.