bmoren / p5.collide2D

A collision detection library for 2D geometry in p5.js
Other
582 stars 296 forks source link

boundingBoxPolyVector (Performance) #47

Closed MyNameIsNotMNINM closed 2 years ago

MyNameIsNotMNINM commented 3 years ago

I like your project and I've been using this library and needed to detect Poly to X collision and had a bit of a hard time with a large poly vertex count, so I implemented a simple bounding box detection to rule out some big poly comparisons and had a gigantic performance gain. (I've never contributed before so I don't really know what to do here. Anyway have my code.)

bmoren commented 3 years ago

Hello! I just woke up and have not had a full cup of coffee yet, so hopefully I'm making sense! This looks super interesting! Thanks for the implementation / Idea :)

let me see If I'm getting this right – This adds a bounding box 'layer' in front of the polygon detection that says, Hey, if you don't collide this simple geom first, don't do anything... Then once the simple geom is collided, then it does the more complex polygonal detection. This seemingly would be a significant performance boost seeing as you wouldn't need to calculate every point of the multi-poly collision on every frame (very expensive)

Did you test each function to make sure everything is working properly?

Do you think there is a scenario where a user might want to utilize the boundingBoxPoly() function in some other way that is worth writing up documentation for? It seems unlikely to me but I'm curious about your thoughts on it. We could do the documentation just for completeness I guess?

If this is all seemingly good I'm happy to pull this into main and draft a new release! Again, thank you for this idea, looks great!

bmoren commented 3 years ago

Don't worry about the failed checks here in github, this has nothing to do with your code :) it's the auto-deploy scripts mis-firing since I didn't merge it into the main branch yet!

MyNameIsNotMNINM commented 3 years ago

Hey It's a pleasure to help, I believe boundingBoxPoly() is something a user could need although usually he would get the benefits of this implementation without thinking about the bounding box. In contrast to that, I've implemented a spacial hash grid so it wasn't needed to test collision between geometries that were far enough apart (kinda like this https://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/) the boundingBoxPoly() allowed me to determine which grid spaces the polygon occupied making it a RectRect instead of a PolyRect. I believe it could help people making a more specific collision detection tool based on colide2D. If you like, I could help you write the documentation and provide some examples.

bmoren commented 3 years ago

Ok! Excellent!

Lets add some documentation for the boundingBoxPoly() function then and if you could add some examples for how it might get used, like that awesome spatial hashing idea (that looks really awesome !!!), that would be amazing!

I've got an account going on the p5.js editor, so the easiest thing to do for the examples is to make them on the editor and then I can fork that over into that unified account and we can link them accordingly. (I can update the README.md with the proper account's links once everything is complete)

To sum up – 2 things should happen for the documentation:

  1. edit the README.md to include the function
    • please reference the other examples for formatting
    • please include a short discription
    • please include the most simplified example possible
  2. make a live example in p5.js editor
    • please include the simplified example from above in a functioning manner
    • please include any more complex / cool examples you are willing / able to write! (the spatial hashing)
MyNameIsNotMNINM commented 3 years ago

Hey, this afternoon I started working on the examples, it's only missing the hashmap and in the process of making it I've found some interesting cases that you might want to see. I've found some of them. It does look small it's an export from my example

bmoren commented 3 years ago

oh yeah, that is an interesting case. My guess is that this has to do with the floating point definitions in the polygons and since p5's grid system is aligned to pixels (ints) it's getting really confused since I think it's technically getting bumped/rounded to the nearest pixel for rendering?

Although I'll admit I would think overlapping that much would trigger it, so there must be something else going on here?

The other examples are looking good too!

bmoren commented 3 years ago

ok, yes I believe my idea above to be the a solution (well, sort of solution, it does change things....)

See line 19 here: https://editor.p5js.org/bmoren/sketches/VZXri-ehL

Renders true as expected.

bmoren commented 3 years ago

there are a couple of solutions that could likely be implemented off the top of my head.

Easiest is to do nothing, and write ab out it in documentation Next easiest is to add int conversion to the functions last easiest is to add support directly for floating point numbers.

Now that this has come up, I'm curious if this float issue is there regardless of your additional performance additions and was always a bug that I just never noticed? (I'll test this in a minute and report back accordingly.)

I can see how float support could be really helpful, especially if you export polygons from a vector data drawing program and use it!

bmoren commented 3 years ago

yes, verified that this is a part of the new implementation, running floats in the original library is fine.

confirmed here: https://editor.p5js.org/bmoren/sketches/U8G5LwBPn (edit:wrong link) && by replacing the original library code in your example above.

How do you think it should be handled?

MyNameIsNotMNINM commented 3 years ago

I was thinking about the js floating point number doing the crazy stuff, but I've looked at it and I think it shouldn't be a problem. I wanted to help figure out the reason and fix with you. You gave me a hint with a good place to look.

I had disabled my code on polypoly but not linepoly. once I commented the linerect comparison it ran as expected which is curious. So I went to investigate the reason.

some cases that I could find:

I've made a version with the fix for these problems. I wanted to ask if you find the way I handled the collisions compatible with your vision of the project, if you do, I could make a new version and pull. if not we could find a different way like making another comparison on the loop or something. (edit: different line of thought)

Anyway, sorry about showing a problem and not a solution, I was a bit tired and sent without checking if I had finished my thoughts

bmoren commented 3 years ago

I’ll have a look when I return from a work trip on Wednesday! I’m happy to keep the discussion going here and I hunk it’s good to talk about adding new features out in the open so no worries about showing a problem. Solving problems is good!

Sent from my iPhone

On Jun 7, 2021, at 2:52 PM, MynameIsNotMninm @.***> wrote:

 I was thinking about the js floating point number doing the crazy stuff, but I've looked at it and I think it shouldn't be a problem. I wanted to help figure out the reason and fix with you. You gave me a hint with a good place to look.

I had disabled my code on polypoly but not linepoly. once I commented the linerect comparison it ran as expected which is curious. So I went to investigate the reason.

some cases that I could find:

A line inside a rectangle does not return as a collision. It's not a problem if any line of a poly intersects with the poligon but i found this case with this fix somehow with small polys maybe a some sort of "tunneling" occurred, it explains why both polys were so inside on another and yet no LineRect collision was detected. it solved the problem in my simulation. A circle completely inside a poly doesn't collide but a circle completely inside a primitive form does collide. It does depend on how should the library be used but I believe it could be standardized for consistency. I've made a version with the fix for these problems. I wanted to ask you if find the way I handled the collisions (that should return something other than boolean) compatible with your vision of the project, if you do, i could make a new version and pull. if not we could find a different way like making another comparison on the loop or something.

Anyway, sorry about showing a problem and not a solution, I was a bit tired and sent without checking if I had finished my thoughts

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.

bmoren commented 3 years ago

hello! I'm back, thank you for working on this so much, a lot more bugs getting sorted out here than expected which is awesome!

In response to a few items:

A line inside a rectangle does not return as a collision. It's not a problem if any line of a poly intersects with the poligon but i found this case with this fix somehow with small polys maybe a some sort of "tunneling" occurred, it explains why both polys were so inside on another and yet no LineRect collision was detected. it solved the problem in my simulation.

This is super interesting, nice find. I definitely had not tested that (literal) edge case!

A circle completely inside a poly doesn't collide but a circle completely inside a primitive form does collide. It does depend on how should the library be used but I believe it could be standardized for consistency.`

I agree that this should be standardized in some way for consistency. The way it's handled on poly functions is to disable the interior collision and add in a boolean parameter to enable it as a setting in the function. For example this from collidepolypoly: Takes an optional 3rd 'true' boolean parameter which enables the collision detection if the polygon is wholly inside the other polygon. I understand you're perspective on this in that it's kind of opposite of the primitive functions. My original thought on this was performance saving, thinking that the primary use cases would be coming from exterior to interior collisions and so it would not really be 'worth' the computational cost. However, now with your performance gains here, perhaps it makes sense to simply enable the interior collisions all of the time?

I can see a small use case where someone might want to have a shape interior to a polygon and detect when it's trying to escape, but perhaps there are other ways of doing that sort of thing.

It might make sense to keep that boolean control for this interior/exterior behavior (or even offload it to a universal function like interiorCollideMode() ?) for those kind of specific use cases where it could be utilized?

-->

I'm open to your ideas on this issue. I do think if we 'flip' the behavior that we'll need to issue a new major version as it would be breaking for some past code (and update the readme to reflect the change)

By the way, I have no issues with the boundingBoxPoly() not returning a boolean since it's really looking at a much more complex piece of data. We just need to update the readme to reflect :)

bmoren commented 3 years ago

hey, I wanted to follow up and see if we could get some momentum back into committing this merge! Let me know what you think and where you're at with it!

Thanks!

MyNameIsNotMNINM commented 3 years ago

Hey sorry about that, I've got a bit caught up in work, but I still interested in helping. I even made a "version" that includes the sqrt distance performance boost.

But then I've hit some walls, first I didn't know how to acctually make it into a feature, since doing that really shortens the euclidian space before an overflow. making it optional was the only way I found to solve it. Then I've started working on polygon collision detection with GJK that's still pretty broken (for now) but I think in the future we could make a standardized way of getting the collision points using a collision object as response.

Anyways I think I should've just sent the fix and pull the bounding box before going on a tangent and let my vacation end 😅

bmoren commented 3 years ago

I want to leave this open, as it seems like there is still a performance enhancement that can come out of it. eve if we just look at the the simpler version that looks at the bounding box. and re-route the energy for the sqrt distance feature and the GJK stuff into a future pull once those things are more developed.

Are you still interested in working on getting just the bounding box version up and running in a way that can be wrapped into the library?