Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

feat(universe_utils): add GJK implementation for 2D convex polygon collision check #7853

Merged
merged 14 commits into from
Jul 18, 2024
Merged

feat(universe_utils): add GJK implementation for 2D convex polygon collision check #7853

merged 14 commits into from
Jul 18, 2024

Conversation

maxime-clem
Copy link
Contributor

Description

Implement the GJK algorithm allowing ~4x speed compared to boost::geometry::intersects to determine if 2 polygons intersects.
⚠️ the polygons must be convex.

Related links

How was this PR tested?

Unit tests.

Notes for reviewers

None.

Interface changes

None.

Effects on system behavior

None.

@github-actions github-actions bot added the component:common Common packages from the autoware-common repository. (auto-assigned) label Jul 4, 2024
@github-actions GitHub Actions
Copy link

github-actions bot commented Jul 4, 2024 •
edited
Loading

Thank you for contributing to the Autoware project!

🚧 If your pull request is in progress, switch it to draft mode.

Please ensure:

@maxime-clem maxime-clem added the run:build-and-test-differential Mark to enable build-and-test-differential workflow. (used-by-ci) label Jul 4, 2024
@maxime-clem maxime-clem changed the title feat(universe_utils): add GJK implementation 2D convex polygon collision check feat(universe_utils): add GJK implementation for 2D convex polygon collision check Jul 4, 2024
@codecov Codecov
Copy link

codecov bot commented Jul 5, 2024 •
edited
Loading

Codecov Report

Attention: Patch coverage is 93.37349% with 11 lines in your changes missing coverage. Please review.

Project coverage is 29.03%. Comparing base (6e74c19) to head (7037fb1).
Report is 13 commits behind head on main.

Files Patch % Lines
...universe_utils/test/src/geometry/test_geometry.cpp 86.11% 1 Missing and 9 partials ⚠️
...on/autoware_universe_utils/src/geometry/gjk_2d.cpp 97.67% 0 Missing and 1 partial ⚠️
Additional details and impacted files 
@@            Coverage Diff             @@
##             main    #7853      +/-   ##
==========================================
+ Coverage   28.94%   29.03%   +0.09%     
==========================================
  Files        1607     1609       +2     
  Lines      117654   117820     +166     
  Branches    50633    50734     +101     
==========================================
+ Hits        34053    34208     +155     
- Misses      74482    74483       +1     
- Partials     9119     9129      +10
Flag Coverage Δ *Carryforward flag
differential 30.40% <93.37%> (?)
total 28.94% <ø> (ø) Carriedforward from 6e74c19

*This pull request uses carry forward flags. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@maxime-clem maxime-clem force-pushed the feat/gjk branch 7 times, most recently from 6bec783 to faad638 Compare July 11, 2024 02:05
@takayuki5168 takayuki5168 self-assigned this Jul 17, 2024
maxime-clem added 10 commits July 18, 2024 10:18
@maxime-clem
add 1st version of 2D GJK algorithm and unit tests
c17924e 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
update 2 edge cases (shared point, shared edge): no intersect found
db29340 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
split hpp/cpp files
70c5ee7 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
fix function name and comments
1123549 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
remove unused headers
69812c1 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
fix copyrights
6e82b82 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
fix unused function in header
0bb5477 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
fix unitialized variable
2ce8043 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
re-add includes
f596f6c 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
add docstrings and simplify the code a little
c157e77 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
slightly factorize the code
5f8ed65 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
Add non-trivial test with very small overlap
3a3fbb2 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
improve benchmark test
2525483 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem
rename function with _convex suffix and fix for clang-tidy
7037fb1 
Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
@maxime-clem maxime-clem merged commit 82081f2 into autowarefoundation:main Jul 18, 2024
27 of 30 checks passed
@maxime-clem maxime-clem deleted the feat/gjk branch July 18, 2024 04:34
yhisaki pushed a commit to yhisaki/autoware.universe that referenced this pull request Jul 19, 2024
@maxime-clem @yhisaki
feat(universe_utils): add GJK implementation for 2D convex polygon co…
1feeccd 
…llision check (autowarefoundation#7853)

Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
Signed-off-by: Y.Hisaki <yhisaki31@gmail.com>
Ariiees pushed a commit to Ariiees/autoware.universe that referenced this pull request Jul 22, 2024
@maxime-clem @Ariiees
feat(universe_utils): add GJK implementation for 2D convex polygon co…
bbcb858 
…llision check (autowarefoundation#7853)

Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
chihungtzeng pushed a commit to chihungtzeng/autoware.universe that referenced this pull request Jul 23, 2024
@maxime-clem
feat(universe_utils): add GJK implementation for 2D convex polygon co…
95f3fa3 
…llision check (autowarefoundation#7853)

Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
Signed-off-by: chtseng <chtseng@itri.org.tw>
esteve pushed a commit to esteve/autoware.universe that referenced this pull request Aug 13, 2024
@maxime-clem @esteve
feat(universe_utils): add GJK implementation for 2D convex polygon co…
f52e22c 
…llision check (autowarefoundation#7853)

Signed-off-by: Maxime CLEMENT <maxime.clement@tier4.jp>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@takayuki5168 takayuki5168 takayuki5168 approved these changes

@soblin soblin Awaiting requested review from soblin soblin is a code owner

@TakaHoribe TakaHoribe Awaiting requested review from TakaHoribe TakaHoribe is a code owner

Assignees

@takayuki5168 takayuki5168

Labels
component:common Common packages from the autoware-common repository. (auto-assigned) run:build-and-test-differential Mark to enable build-and-test-differential workflow. (used-by-ci)
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@maxime-clem @takayuki5168