Inserting a convex boundary in a grid

Math and Physics Programming

Started by Sirisian March 16, 2007 10:09 PM

2 comments, last by oliii 17 years, 1 month ago

2,263

Author

March 16, 2007 10:09 PM

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]);
							}
						}
					}
				}
			}

flounder

100

March 16, 2007 10:23 PM

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.

agogsoft

oliii

2,202

March 17, 2007 04:27 AM

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;}

Everything is better with Metal.

oliii

2,202

March 17, 2007 04:42 AM

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;}

Everything is better with Metal.

Inserting a convex boundary in a grid

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Inserting a convex boundary in a grid

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines