Simple(yet not so simple) overlap problem

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
User avatar
krautersuppe
Posts: 91
Joined: September 14th, 2015, 10:58 pm
Location: Istanbul

Simple(yet not so simple) overlap problem

Post by krautersuppe » November 17th, 2018, 12:56 pm

I have a rectangle

Code: Select all

void Graphics::DrawRect(int x0, int y0, int x1, int y1, Color c){
	if (x0 > x1) {std::swap(x0, x1);}
	if (y0 > y1) {std::swap(y0, y1);}
	for (int y = y0 ; y < y1; ++y)
	{
		for (int x = x0; x < x1; ++x)
		{
			PutPixel(x, y,c);
		}
	}
}
that moves down one pixel each frame. There is a pixel on the screen which activates and turns red only when rectangle passes over it.
overlap.png
overlap.png (1.37 KiB) Viewed 1294 times
This is of course the simplified version of the problem. I am looking for a solution for any form and number of shapes , not only rectangle and a pixel .
Do you have any ideas? I only come up with crazy stuff like checking all pixels of the background if they have changed color and then set it to another value.
DSU
Discord: dsu1, GitHub: https://github.com/DSpUz

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Simple(yet not so simple) overlap problem

Post by albinopapa » November 17th, 2018, 7:10 pm

Point in [ insert shape ] is probably mostly pretty easy.

// Point in Circle
Check distance from center to point; if less or equal then change point

// Point in Triangle
Check barycentric coordinate, if all three coordinates are between 0.f and 1.f then point is in triangle

// Point in Rect
Check if greater than left and top, and less than right and bottom

// Polygon with convex hull, ( all left turns or all right turns to each vertex )
Check bounding rect first, then if passes, since it's a convex polygon, you can easily check barycentric coordinates of generated triangles using the center ( sum of all vertices / total number of vertices ) as a vertex. If there are a lot of vertices, you could even break the polygon into quadrants ( think quadtree ).

For more complex shapes and point, like concave polygon and point I'm not entirely sure. I want to say I've seen an algorithm somewhere or maybe even in one of chili's old Advanced or HUGS videos where he makes the ship.

For different shapes colliding with different shapes, there's circle/circle, ray/circle, rect/circle, segment/segment, rect/segment, rect/rect, polygone/circle, segment/polygon.

I'm sure there are more, came across a post while looking up contact manifold that talked about point/cylinder and cylinder/cone for 3D collision, though I didn't fully understand everything they were discussing.

On a project awhile back, I needed to figure out if a line was going through a rectangle. I still don't know how to do it "the right way", but what I ended up doing was getting the slope of the line and comparing it to the slopes of the lines going from each of the corners of the rectangle to the origin of the original line ( in this case it was a ship firing a laser, so I guess a ray is more accurate ). This seemed to work for my purposes though if I recall, there was a fair bit of branching.

Since you understand quite a bit of math, you might look through the Box2D library and see if it gives you some ideas for the different types of collision detection that is supports, perhaps it has something you could use.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Simple(yet not so simple) overlap problem

Post by chili » November 18th, 2018, 7:16 am

yeah, in general for a point, you will have point, rect, circle, triangle, convex hull, and composite convex hull. Ahything beyond that and it starts getting slow fast (like elipses) and you start getting into the realm of very slow to calculate for any decent number of bodies. The way most engines do it is approximate more complex geometry with polygon/polyline.
Chili

Post Reply