SFML community forums

General => General discussions => Topic started by: xylr117z4 on November 09, 2015, 06:44:04 am

Title: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: xylr117z4 on November 09, 2015, 06:44:04 am
Hey Guys, I've been around SMFL since 1.6 was released and it's the main reason I've stuck with c++ for all my programming needs.
Recently I've been looking a lot more into better Collision detection and finding a simple way to handle that where I can actually understand it instead of just using a random algorithm I found online and brute forcing it.

After 3 weeks trying to understand SAT (separating axis theorem) I stumbled upon a forum post saying.
"Hey look at the area of a triangle, then check a point on another triangle by creating 3 segmented triangles inside the original.
Get those 3 triangle's areas and add them up, if they equal the original triangle's area that point is within the triangle."
Which is really easy for me to visualize and work with.

 I figured I'd make a tutorial video explaining it which will hopefully help those with a lesser understanding in maths have awesome collision detection.

If you care to watch it on youtube the link's: https://www.youtube.com/watch?v=vvaczEyI0Ho

TL;DR: I made a tutorial on collision detection. Let me know what you think about the way I describe it in the video and if you liked it. Also feel free to let me know if that way of checking sucks, lol. kthxbye

Edit: I was trying to keep the tutorial as generic as possible since a lot of people looking for that sort of thing use many languages but my real code directly uses SFML and I'll likely feature SFML as the main part of future tutorials.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 09, 2015, 07:34:58 am
Quote
After 3 weeks trying to understand SAT (separating axis theorem)

What's with SAT? I implemented it in my game, it's not very hard. If you have something you don't understand, I can help you.

Quote
I was trying to keep the tutorial as generic as possible since a lot of people looking for that sort of thing use many languages but my real code directly uses SFML

Posting your code somewhere like github would be great addition to the tutorial.  ;)
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: xylr117z4 on November 09, 2015, 07:40:30 am
Quote
What's with SAT? I implemented it in my game, it's not very hard. If you have something you don't understand, I can help you.

My only issue with SAT is I could never wrap my brain around why dot products and magnitudes were needed or rather what they do... This Area based detection is nice because it's really easy to visualize I feel.

Quote
Posting your code somewhere like github would be great addition to the tutorial.

that'd be a great place for it. I was just going to link to a download on my website but github's probably a preferable way to host it. I'll clean up my actual SFML code and put that in the description and this post tomorrow morning. it's getting a bit late tonight.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 09, 2015, 07:49:20 am
Quote
My only issue with SAT is I could never wrap my brain around why dot products and magnitudes were needed or rather what they do...

Magnitudes are needed to calculate normalized normals of convex' axes. Dot products - to calculate projection of a shape onto some axis.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: xylr117z4 on November 09, 2015, 08:00:37 am
Quote
Magnitudes are needed to calculate normalized normals of convex' axes. Dot products - to calculate projection of a shape onto some axis.


Yeah,  I have an understanding of them in that sense but I can't visualize it at all... The main reason I was trying to research and look into it is when you brute force things and just try to use an algorithm you find online you don't really gain any knowledge.

That and I never really got time to program it out, I've just been busy at work as we had a huge software release to get out by Nov 1st. (I'm only QA at the place sadly but working with devs who do this for a living is awesome)

I suppose my goal in working out collision detection was to know how it all works so that I can explain it to the other guy I like to program with so we both understand the code and can create bigger better things but dunno.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 09, 2015, 09:03:59 am
Yeah,  I have an understanding of them in that sense but I can't visualize it at all...

Try this tutorial (http://www.metanetsoftware.com/technique/tutorialA.html), it has interactive examples.

If you want, I can share my code when I get back home from work.
I will also watch your tutorial, in looks interesting, because I never used anything for collision detection except SAT or simple rectangle intersection.  :)
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: K.F on November 10, 2015, 10:43:40 am
So these triangles are not intersected using this algorithm?

(http://i.imgur.com/KWPYxqh.jpg)

You can add line intersection detection to fix this. This method looks usable for simple geometry, but cutting complicated geometry to triangles will increase the detection time exponentially with each triangle.

Plus, tessellation could be more complicated than SAT - efficient and fast tessellation at least -, so you'd still need to wrap your head around something in the end  ;D
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Nexus on November 10, 2015, 01:01:27 pm
I don't understand why people keep re-implementing geometry algorithms again and again. Almost always worse than existing libraries with respect to performance, features and bugs, and even if it starts as "just for learning purposes", it ends up being used in production code.

There are tons of C++ libraries that provide exactly what you need. For example, Boost.Geometry is a really modern one. And please don't say "I don't want to use Boost" before even looking at it; every Boost library is different.

This is just my personal tip to use your time more meaningfully. One day you won't have enough of it anymore, and then you'll regret having spent most of it reinventing wheels and not developing games ;)
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 10, 2015, 04:05:17 pm
@Nexus, while I agree in general, most of the time times I want to use Boost, I just feel like I will write my own implementation faster and easier instead of using this ugly, not-very-userfriendly and not-very-quick-to-learn library.

Quote
bugs

It's ironical that Boost.Geometry page on github shows that master branch failed their own tests  :)
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Nexus on November 10, 2015, 04:39:41 pm
There's a reason why I wrote
And please don't say "I don't want to use Boost" before even looking at it; every Boost library is different.
yet you did exactly that. Have at least a look at it before judging. The API of Boost.Geometry is very user-friendly and powerful, and you definitely can't just write something even close to it by yourself.

By the way, Boost is not a library, it's a collection of libraries, written by different authors with different design philosophies. That's why your prejudging generalization is flawed.

About bugs: there are development versions and there are stable releases. Complex software tends to contain bugs, and this won't be any different if you write it yourself.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 10, 2015, 05:35:58 pm
Have at least a look at it before judging.
Of course I did. It's all subjective, but I find Boost code style extremely ugly, and having user to define some macros or specializations for templates before using it does not really souse like "encapsulation and simple interface" to me.

and powerful, and you definitely can't just write something even close to it by yourself.
The thing is, in 90% of projects I will need specific 20% of this library. So "powerful" and "can't write yourself" do not always apply. How much time will I spend on writing, say, SAT collision detection or triangulation algorithm and how much time will I spend to adopt boost to solve that problems?

Quote
About bugs: there are development versions and there are stable releases. Complex software tends to contain bugs, and this won't be any different if you write it yourself.
I am very good with github, but I thought that "master" brunch = stable brunch, unlike "development" brunch. I may be wrong though.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Jesper Juhl on November 10, 2015, 07:02:22 pm
I am very good with github, but I thought that "master" brunch = stable brunch, unlike "development" brunch. I may be wrong though.
For many (most?) projects, the 'master' branch is the continuously evolving development branch and stable releases are forked off as their own branches.
Pretty common and makes sense when you think about it.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 10, 2015, 07:05:20 pm
For many (most?) projects, the 'master' branch is the continuously evolving development branch and stable releases are forked off as their own branches.
Pretty common and makes sense when you think about it.

Oh, I see. Thanks for clarifying.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: SpeCter on November 10, 2015, 07:12:19 pm
Have at least a look at it before judging.
Of course I did. It's all subjective, but I find Boost code style extremely ugly, and having user to define some macros or specializations for templates before using it does not really souse like "encapsulation and simple interface" to me.

Are you sure that you looked at the documentation for Boost.Geometry?
You don't have to define any macros or template specializations to use it.
The only thing I see right now, is the possibility to register your own classes as points to make it easier to use them if you don't want to convert your own types to their point class and use for example sf::Vector2 directly...
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: xylr117z4 on November 10, 2015, 10:38:34 pm
Quote
Plus, tessellation could be more complicated than SAT - efficient and fast tessellation at least -, so you'd still need to wrap your head around something in the end  ;D

That's definitely true.


Quote
So these triangles are not intersected using this algorithm?

As far as the over lapping triangles.  You'll typically respond to the collision far before they get into that state is why I don't take it into account.

Quote
There are tons of C++ libraries that provide exactly what you need. For example, Boost.Geometry is a really modern one. And please don't say "I don't want to use Boost" before even looking at it; every Boost library is different.

This is just my personal tip to use your time more meaningfully. One day you won't have enough of it anymore, and then you'll regret having spent most of it reinventing wheels and not developing games ;)

I'm not opposed to using existing libraries, hence using SFML for graphics handling.

The issue is many libraries don't have good distributions where I can just pop them into a folder and start using them.

SFML is awesome because there is a pre-made distro that I can just pop in, put in my linker and get running.

I've only set up cmake once to build SFML 2.0 (pre-release) and I remember it took like 2 hours of my time so building something simple I figure is cool but dunno. 
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: K.F on November 11, 2015, 07:17:28 am
I don't understand why people keep re-implementing geometry algorithms again and again. Almost always worse than existing libraries with respect to performance, features and bugs, and even if it starts as "just for learning purposes", it ends up being used in production code.

Control and modifiability, I prefer taking a week to implement a feature I have full control and understanding over, than use an external library that could introduce a single bug that will destroy months of work, or needing a modification in a feature that I need, but I can't do much about that library's bugs and features without wasting a ton of time.

But that is true for simple features only, complicated features that would take months to implement is worth the risk of using a library.

This is just my personal tip to use your time more meaningfully. One day you won't have enough of it anymore, and then you'll regret having spent most of it reinventing wheels and not developing games ;)

Words of wisdom, too bad it is already too late for me  ;D
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Nexus on November 11, 2015, 09:28:11 am
Of course I did [have a look at it]. [...] having user to define some macros or specializations for templates before using it [...]
I.e. you did not ;) As SpeCter stated, this is only needed for customizability, if you want Boost.Geometry to work with your types directly.

And even if the API doesn't please you, it's trivial to write an adapter on top of it, allowing you to exploit all the other advantages. I've also done this in some parts (for PImpl reasons, not because of the style).

How much time will I spend on writing, say, SAT collision detection or triangulation algorithm and how much time will I spend to adopt boost to solve that problems?
I can't talk about SAT, but I implemented Delaunay triangulation, and it has cost me a few weeks (of course not full time, but still). And years later, bugs in special cases still appeared. In retrospect, it may not have been the wisest decision, but I didn't want to enforce another dependency on Thor users back then.

The issue is many libraries don't have good distributions where I can just pop them into a folder and start using them.

SFML is awesome because there is a pre-made distro that I can just pop in, put in my linker and get running.

I've only set up cmake once to build SFML 2.0 (pre-release) and I remember it took like 2 hours of my time so building something simple I figure is cool but dunno.
Boost is probably the most widely used C++ library (maybe besides Qt), so you can be certain that well-maintained distributions exist. Using Boost.Geometry is even simpler than SFML, because it's header-only: you don't have to build, configure or link anything. Include the header and you're done.

You guys should really have a closer look at things before deciding whether or not to use them :P
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: xylr117z4 on November 12, 2015, 12:48:53 am
Boost is probably the most widely used C++ library (maybe besides Qt), so you can be certain that well-maintained distributions exist. Using Boost.Geometry is even simpler than SFML, because it's header-only: you don't have to build, configure or link anything. Include the header and you're done.

You guys should really have a closer look at things before deciding whether or not to use them :P

I see, I think I was just looking at boost the wrong way then. I figured it'd be a library like SFML not just a header. I'm still not too experienced with every part of c++. It's mainly a hobby I mess around with whenever I have spare time.

I have to agree with a couple of the other comments however, the triangle hit detecting I talk about in my shitty youtube tutorial only took me 2 hours to implement (maybe 6 if you count thinking about it durring work and figuring out how I'd turn the math into code.)

Plus isn't it cool to do something on your own even with it being a waste of time? (at least when it's only a hobby lol.)

I've spent a lot more time on collision response stuff since then however but that's the complex part of things (well I'd say.)
My next step is tessellation (making paths [being sets of points] into triangles for use with this algorithm.)
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: xylr117z4 on November 24, 2015, 06:13:56 am
Alright Senpai, I looked into boost.geometry/boost.index it's actually pretty hard core. I'll probably just go with that.  Thanks for pointing it out, Boost was just a little overwhelming at first now it makes a lot more sense reading into it.

P.S. the senpai part is a joke calm down...
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Nexus on November 25, 2015, 12:24:24 pm
Seems like this "hardcore" myth is unkillable ::)

Just to prove how simple and powerful Boost.Geometry is:
namespace bg = boost::geometry;
typedef bg::model::d2::point_xy<float> Point;
typedef bg::model::polygon<Point>      Polygon;

// Create polygon geometry
Polygon polygon;
bg::append(polygon, Point(x0, y0));
bg::append(polygon, Point(x1, y1));
...

// Create point geometry
Point point(x, y);
bool pointInPolygon = bg::within(point, polygon);

And please don't complain about the type definitions, you have them a single time in your code and that's it. On the contrary, this allows you to use arbitrary geometry types. For example, you can easily make everything based on sf::Vector2f, to integrate your entire geometry logic with SFML in a matter of minutes.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Satus on November 25, 2015, 05:29:43 pm
I tried to google how use boost.geometry to detect collision between two shapes and get MTV and didn't find anything. As I can see, it can detect the fact of intersection and return the shape, formed by this intersection, but what to do with this shape?
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Kojay on November 25, 2015, 08:13:18 pm
Seems like this "hardcore" myth is unkillable ::)

Just to prove how simple and powerful Boost.Geometry is:
namespace bg = boost::geometry;
typedef bg::model::d2::point_xy<float> Point;
typedef bg::model::polygon<Point>      Polygon;

// Create polygon geometry
Polygon polygon;
bg::append(polygon, Point(x0, y0));
bg::append(polygon, Point(x1, y1));
...

// Create point geometry
Point point(x, y);
bool pointInPolygon = bg::within(point, polygon);

And please don't complain about the type definitions, you have them a single time in your code and that's it. On the contrary, this allows you to use arbitrary geometry types. For example, you can easily make everything based on sf::Vector2f, to integrate your entire geometry logic with SFML in a matter of minutes.

Yes, you can make everything based on sf::Vector2f. Have you done this? If so, would you share your efforts with the community by any chance?

I am asking, because this has been on my mind for a while. My own efforts are not quite as polished as I 'd like, i.e. a uniform treatment of sf::Shape, sf::Sprite, sf::VertexArray and user-defined ranges of sf::Vector2f. And it required definining metafunctions.

Not that I disagree with your other points. Boost libraries are not only a way to avoid reinventing the wheel, they are also instructive; some APIs are controversial, even among Boost developers themselves, however there are always reasons why things are the way there are.

On the other hand there is no substitute for the instructive value of hand-implementing something; only then you get to wrestle with the problems and truly understand the implementation, performance considerations as well as interface choices.
Title: Re: Simple Triangle Based 2D Collision Detection / Start of a tutorial series
Post by: Kojay on December 24, 2015, 10:22:21 pm
To follow up on the matter of Boost.Geometry, I have put some of my efforts here (https://github.com/Kojirion/SF.Boost.Geometry).

sf::Vector2f is adapted to model the Point concept, very simply with the macro BG provides.
sf::FloatRect is adapted to model the Box concept (https://github.com/Kojirion/SF.Boost.Geometry/blob/master/include/Box.hpp). (the macro can't be used out of the box, as BG represents the Box in terms of bottom left and top right corner, rather than top left and size)

Already by doing these two, it is possible to insert the FloatRect into BG's rtree (a spatial indexing structure like a quad tree). An example of using the tree to determine collisions can be seen in this rudimentary invaders prototype (https://github.com/Kojirion/SF.Boost.Geometry/blob/master/examples/invaders.cpp).

The rest is unfinished, as an ideal design is not clear. I think that rather than registering SFML classes as any particular geometry, there should be lightweight 'views' that are registered instead, so that for example a sf::Shape may be viewed as either a filled or unfilled polygon. A sf::VertexArray could be a polygon but also just a linestring, etc

One neat free side-benefit is that registered geometries can be output in pretty text or SVG. For example

sf::FloatRect rect(0.f, 10.f, 10.f, 10.f);
std::cout << bg::wkt(rect) << '\n';

gives
POLYGON((0 0,0 10,10 10,10 0,0 0))