Simple Triangle Based 2D Collision Detection / Start of a tutorial series

[xylr117z4]

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:

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.

[Satus]

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.

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. 

[xylr117z4]

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.

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.

[Satus]

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.

[xylr117z4]

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.

[Satus]

Yeah,  I have an understanding of them in that sense but I can't visualize it at all...

Try this tutorial, 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. 

[K.F]

So these triangles are not intersected using this algorithm?



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 

[Nexus]

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

[Satus]

@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.

bugs

It's ironical that Boost.Geometry page on github shows that master branch failed their own tests 

[Nexus]

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.

[Satus]

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?

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.

[Jesper Juhl]

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.

[Satus]

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.

[SpeCter]

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...

[xylr117z4]

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 

That's definitely true.

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.

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.