Skip to content

Implement bounding volume intersections#11439

Merged
alice-i-cecile merged 7 commits intobevyengine:mainfrom
Jondolf:bounding-volume-intersections
Jan 22, 2024
Merged

Implement bounding volume intersections#11439
alice-i-cecile merged 7 commits intobevyengine:mainfrom
Jondolf:bounding-volume-intersections

Conversation

@Jondolf
Copy link
Copy Markdown
Contributor

@Jondolf Jondolf commented Jan 20, 2024

Objective

#10946 added bounding volume types and an IntersectsVolume trait, but didn't actually implement intersections between bounding volumes.

This PR implements AABB-AABB, circle-circle / sphere-sphere, and AABB-circle / AABB-sphere intersections.

Solution

Implement IntersectsVolume for bounding volume pairs. I also added closest_point methods to return the closest point on the surface / inside of bounding volumes. This is used for AABB-circle / AABB-sphere intersections.

@Jondolf Jondolf added C-Feature A new feature, making something new possible A-Math Fundamental domain-agnostic mathematical operations labels Jan 20, 2024
@Jondolf Jondolf added this to the 0.13 milestone Jan 20, 2024
IQuick143
IQuick143 suggested changes Jan 20, 2024
View reviewed changes
Copy link
Copy Markdown
Contributor

@IQuick143 IQuick143 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For consistency I'd change the < to <=, but other than that I haven't noticed any problems.

NiseVoid
NiseVoid reviewed Jan 20, 2024
View reviewed changes
Copy link
Copy Markdown
Contributor

@NiseVoid NiseVoid left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This seems correct. Didn't check the tests tho. And closest_point on sphere/circle appears to be unused. It might be useful, but I also feel like maybe it should be on the primitive types instead.

@Jondolf
Copy link
Copy Markdown
Contributor Author

Jondolf commented Jan 20, 2024 •
edited
Loading

For now, I moved the circle/sphere closest_points logic to the primitives (same for AABBs), but kept the methods on the bounding volumes too for consistency and convenience. I could also just remove the circle/sphere version since it's unused, or split it into a different PR, but I thought it'd be nice to have if AABBs have it anyway

IQuick143
IQuick143 approved these changes Jan 20, 2024
View reviewed changes
Copy link
Copy Markdown
Contributor

@IQuick143 IQuick143 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Seems good.

Although I'm not super convinced about implementing closest point on the primitives, because closest point seems to demand transform information (translation + rotation), which is addressed here by assuming default identity transform.
It's not a huge deal, because the user can use this to implement the general case simply by inversely transforming the point and then transforming the result.

@Jondolf
Copy link
Copy Markdown
Contributor Author

Jondolf commented Jan 20, 2024

FWIW, Parry has "global" and local versions of a ton of methods, like aabb/local_aabb, project_point/project_local_point, support_point/local_support_point, and so on. Both can be useful.

The closest_point methods on the primitives currently correspond the most to project_local_point, but with the shape always treated as "solid" (the returned point can be inside the shape instead of always being at the perimeter/surface). In the future we might want a trait for this and to implement it for all primitives

@Jondolf
Copy link
Copy Markdown
Contributor Author

Jondolf commented Jan 20, 2024

Here's a video of the bounding volume intersections working: (gray is the bounding volume)

2024-01-20.23-07-29.mp4

I can add this as an example if that'd be useful. Should I do it in this PR or a follow-up?

@NiseVoid
Copy link
Copy Markdown
Contributor

NiseVoid commented Jan 22, 2024 •
edited
Loading

Should I do it in this PR or a follow-up?

I guess a follow up PR that showcases the intersection tests (including raycasting and later sphere/aabb casting) and bounding types makes sense?

alice-i-cecile
alice-i-cecile approved these changes Jan 22, 2024
View reviewed changes
Copy link
Copy Markdown
Member

@alice-i-cecile alice-i-cecile left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good. Great docs, and thanks for including thorough tests.

@alice-i-cecile alice-i-cecile added the S-Ready-For-Final-Review This PR has been approved by the community. It's ready for a maintainer to consider merging it label Jan 22, 2024
@alice-i-cecile alice-i-cecile added this pull request to the merge queue Jan 22, 2024
Merged via the queue into bevyengine:main with commit 6a3b059 Jan 22, 2024
@Jondolf Jondolf deleted the bounding-volume-intersections branch January 22, 2024 18:21
@rparrett rparrett mentioned this pull request Jan 22, 2024
Closed
@nicopap nicopap mentioned this pull request Jan 29, 2024
Merged
@Jondolf Jondolf mentioned this pull request Feb 4, 2024
Open
41 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@alice-i-cecile alice-i-cecile alice-i-cecile approved these changes

+2 more reviewers

@NiseVoid NiseVoid NiseVoid left review comments

@IQuick143 IQuick143 IQuick143 approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

A-Math Fundamental domain-agnostic mathematical operations C-Feature A new feature, making something new possible S-Ready-For-Final-Review This PR has been approved by the community. It's ready for a maintainer to consider merging it

Projects

None yet

Milestone

0.13

Development

Successfully merging this pull request may close these issues.

4 participants

@Jondolf @NiseVoid @alice-i-cecile @IQuick143