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

[K.F]

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 

[Nexus]

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

[xylr117z4]

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

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

[xylr117z4]

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

[Nexus]

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.

[Satus]

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?

[Kojay]

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.

[Kojay]

To follow up on the matter of Boost.Geometry, I have put some of my efforts here.

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

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