Sign in to follow this  
Sirisian

Inserting a convex boundary in a grid

Recommended Posts

Sirisian    2263
I guess this fits here. I've been struggling for a while on trying to find the grids that a convex boundary touches. I'm using a grid/tile spatial partitioning system. While I don't need it to be super fast, I might be calling this while loading on my continuous world so I can't have blips of lag. (if it helps I'm working for flash in this project). Don't mind the purple or the red dots. I was toying with the idea I could find the points inside to find any grids that aren't intersected by lines. I have ray/line transversal algorithms if that helps. They are very fast at transversing the grid. Anyone have any ideas? It's become like a logic puzzle for me. Take into account boundaries of any size and orientation might be used. Basically I don't want this algorithm to break in any way. If you have an idea no need to test it. I will look it over and try to implement it. I'm looking for anything that will get me to think of a probable solution. It's late for me, but here's some random code I was messing with to give you an idea of how my object boundaries are set up. A list of boundaries then each boundary has list of points.
			var startX:Number = int(gameObject_.minAABB.x/size);
			if(startX == gameObject_.minAABB.x/size){
				startX--;
			}
			var endX:Number = gameObject_.maxAABB.x/size;
			var startY:Number =gameObject_.minAABB.y/size;
			if(startY == gameObject_.minAABB.y/size){
				startY--;
			}
			var endY:Number = gameObject_.maxAABB.y/size;
			var b:BoundaryObjectArray = gameObject_.boundaries;
			var bp:Point = new Point();
			var xb:Boolean;
			var yb:Boolean;
			var cb:Boolean;
			for(var i:Number = 0; i < b.GetLength(); ++i){
				cb = true;
				for(var j:Number = 0; j < b.boundaryObjects(i).GetLength(); ++j){
					bp.x= b.boundaryObjects(i).points(j).x;
					bp.y= b.boundaryObjects(i).points(j).y;
					xb = (bp.x/size == int(bp.x/size))
					yb = (bp.y/size == int(bp.y/size))
					if(!xb && !yb){
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)][int(bp.y/size)]);
					}else if(xb && !yb){
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)-1][int(bp.y/size)]);
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)][int(bp.y/size)]);
					}else if(!xb && yb)(
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)][int(bp.y/size)-1]);
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)][int(bp.y/size)]);
					}else{
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)-1][int(bp.y/size)-1]);
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)][int(bp.y/size)-1]);
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)][int(bp.y/size)]);
						gameObject_.AddQuadrantCheck(QuadrantGrid[int(bp.x/size)-1][int(bp.y/size)]);
					}
					for(var X:Number = startX; X < endX; ++X){
						for(var Y:Number = startY; Y < endY; ++Y){
								QuadrantGrid[X][Y].objects.push(gameObject_);
								gameObject_.AddQuadrantCheck(QuadrantGrid[X][Y]);
							}
						}
					}
				}
			}

Share this post


Link to post
Share on other sites
flounder    100
A way to check would be to calculate a bounding box for the convex body, check what cells are in or on the bounding box, and then use the separating axis theorem on the body and those cells.

It's not the most efficient method, but it's all i can think of right now.

EDIT: another way that might be faster: for every cell corner that the body overlaps, all 4 cells with that corner are flagged as overlapping the body, every cell that a vertex lies in is also flagged, and so is every cell that has a wall that a body wall overlaps.

Share this post


Link to post
Share on other sites
oliii    2196
this is flounder's method, and my method of choice for what you need.

for each objects.

1) precompute the AABBox of the Convex Hull, in local space.
2) Transform the AABBOx into a OBox in world space.
3) compute the AABBox of the OOBox in world space.


To do the object-grid insertion.

1) Take the world space AABBox of the object, and find the cells covered by the box (a couple of into-to-float conversions).
2) For each covered cell, compute its AABox
3) Use the SAT to do the convex hull / cell intersection test.


bool ProjectConvexHullOnAxis(const Vector& axis, const C_ConvexHull& convex, float& min, float& max)
{
min = max = axis.DotProduct(convex.WorldVertex(0));
for(int i = 1; i < convex.NumVertices(); i ++)
{
float v = axis.DotProduct(convex.WorldVertex(i));
if(v < min) min = v;
if(v > max) max = v;
}
return true;
}

bool ProjectAABBoxOnAxis(const Vector& axis, const C_AABBox& box, float& min, float& max)
{
float c = axis.DotProduct(box.Centre());
float r = fabs(axis.DotProduct(box.HalfSize()));
min = c - r;
max = c + r;
return true;
}

bool AABBoxConvexHullSeparatedByAxis(const Vector& axis, const C_AABBox& box, const C_ConvexHull& convex)
{
float minb, maxb;
float minc, maxc;

ProjectAABBoxOnAxis(axis, box, minb, maxb);
ProjectConvexHullOnAxis(axis, convex, minc, maxc);

return (minb > maxc || maxb < minc);
}

bool AABBoxAABBoxIntersect(const C_AABBox& A, const C_AABBox& B)
{
if (A.Min().x > B.Min().x || A.Min().x < B.Min().x) return false;
if (A.Min().x > B.Min().x || A.Min().x < B.Min().x) return false;
if (A.Min().y > B.Min().y || A.Min().y < B.Min().y) return false;
if (A.Min().y > B.Min().y || A.Min().y < B.Min().y) return false;
return true;
}

bool AABBoxConvexHullIntersect(const C_AABBox& box, const C_ConvexHull& convex)
{
// test the global X and Y axes for separation
// this is equivalent to :
//if(AABBoxConvexHullSeparatedByAxis(Vector(1, 0), box, convex)) return false;
//if(AABBoxConvexHullSeparatedByAxis(Vector(0, 1), box, convex)) return false;
if(!AABBoxAABBoxIntersect(box, convex.WorldAABBox()) return false;

// test each edge normal of the convex hull for separation
int j = convex.NumVertices() - 1;
for(int i = 0; i < convex.NumVertices(); j=i,i++)
{
if(AABBoxConvexHullSeparatedByAxis(convex.WorldEdge(i).Perp(), box, convex)) return false; // Vector Vector::Perp() const { return Vector(-y, x); }
}
return true;
}


Share this post


Link to post
Share on other sites
oliii    2196
btw, to compute the AABBox of the convex hull directly, prior to inserting into the grid :


C_AABBox CalculateAABBoxForCOnvexHull(const C_ConvexHull& convex)
{
Vector Min, Max;
ProjectConvexHullOnAxis(Vector(1, 0), convex, Min.x, Max.x);
ProjectConvexHullOnAxis(Vector(0, 1), convex, Min.y, Max.y);

C_AABBox box;
box.SetCentre((Max + Min)* 0.5f);
box.SetHalfSize((Max - Min)* 0.5f);
return box;
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this