dimforge / parry Goto Github PK
View Code? Open in Web Editor NEW2D and 3D collision-detection library for Rust.
Home Page: https://parry.rs
License: Apache License 2.0
2D and 3D collision-detection library for Rust.
Home Page: https://parry.rs
License: Apache License 2.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);
}
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
The documentation for SharedShape::convex_polyline
should mention that the polygon needs to be given in counter-clockwise orientation:
parry/src/shape/shared_shape.rs
Lines 256 to 262 in d4b01c5
First pointed out in #55.
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:
parry/src/partitioning/qbvh.rs
Line 274 in 167e094
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.
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
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?
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
The same was true in ncollide.
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:
get_initial_mesh()
would treat it as a 0-D case instead of 3-D).(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?)
As of the 0.7 release:
2D Shapes that implement PartialEq:
2D Shapes that don't implement PartialEq:
3D Shapes that implement PartialEq:
3D Shapes that don't implement PartialEq:
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
}
}
Line 40 in c3f2838
This line should be self.to_polyline(nsubdivs)
instead of Self::new(0.5).to_polyline(nsubdivs)
.
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);
}
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
#59 added non-convex polygon to TriMesh
conversions. For more efficient operations, we want to turn those TriMesh
es into Compound
shapes, while merging neighboring triangles into convex polygons. I have a pull request ready that achieves this using the Hertel-Mehlhorn algorithm.
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
},
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.
Maybe this could be a huge breaking change to ncollide?
Obviously not all issues are applicable to this new crate, but there could be issues to take note of from ncollide.
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
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.
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?
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)".
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 insert
ing 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.
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
.
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:
Allow arbitrary keys by providing a means of binding a HashMap representation or similar (may make SIMD implementation difficult)
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.
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,
);
}
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 chain
able 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.
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" ] }
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.
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 HashSet
in 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
As in title. I have the feeling you guys might be seriously underestimating the importance of this.
Examples required:
Even if you just 'dump' say 10 code examples in the index of the documentation, that would already go a long way.
use parry2d::math::*;
use parry2d::query::{Ray, RayCast};
use parry2d::shape::Segment;
fn main() {
// never intersect each other
let ray = Ray::new(Point::new(0.0, 0.0), Vector::new(1.0, 0.0));
let segment = Segment {
a: Point::new(10.0, 10.0),
b: Point::new(10.0, 10.0),
};
// returns true
let hit = segment.intersects_ray(&Isometry::identity(), &ray, std::f32::MAX);
assert_eq!(hit, false);
}
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.
parry/src/shape/shared_shape.rs
Lines 200 to 208 in d4b01c5
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.
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.
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
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.
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?
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.
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.
Happened in #63, strange that this doesn't show as a warning.
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:
compute_exact_convex_hulls
outputs empty sets of points, fix that or just filter empty parts
out.ConvexPolygon::from_convex_polyline
to work on empty vectors... (return early if points.len() == 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
.
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.
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 u32
s 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 FeatureId
s necessarily must be shape-scoped since they're e.g. returned by PointQuery
.
See also Discord discussion. Opening an issue for tracking purposes.
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.
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
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
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).
Due to a division by 0 in Sum<MassProperties>
it is possible to get NaN values.
parry/src/mass_properties/mass_properties.rs
Line 386 in 8241547
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 = "*"
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)
}
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
parry2d = { version = "0.9", features = ["serde"] }
to the Cargo.toml
cargo check
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);
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.