I've read metanetsoftware's tutorials many times, and I've already made a working SAT check, but I wasn't able to implement Circle vs Box collision check.
Someone could explain me better how to:
1)calculate voronoi regions of a polygon?
2)know to which voronoi region a circle is inside?I guess voronoi regions are faster than a simple distance check vs all polygon vertex.
any help would be very appreciated...I'm a bit frustrated... :(
Circle vs Box collision questions..Voronoi Regions
I would recommend looking at separating axis theorem, no I am not familiar with using voronoi regions for collision. Are we talking about convex hulls?
Author
The SAT for Box vs Box collision works ok.
For Box To Circle collision I have to find the closest vertex of the box to the circle center using Voronoi regions.
Quote from metanetsoftware.com tutorial:
Naively testing the distance to each vertex would undermine the whole point of finding the closest vertex, which is to be able to reject the other vertices trivially, without expensive distance calculations. The very useful concept of voronoi regions can be used.
For Box To Circle collision I have to find the closest vertex of the box to the circle center using Voronoi regions.
Quote from metanetsoftware.com tutorial:
Naively testing the distance to each vertex would undermine the whole point of finding the closest vertex, which is to be able to reject the other vertices trivially, without expensive distance calculations. The very useful concept of voronoi regions can be used.
Quote:Original post by forrestuv
For Box To Circle collision I have to find the closest vertex of the box to the circle center using Voronoi regions.
Look at the Intersection page and find the section "Intersection of boxes and circles (2D). Includes the cases of moving circles and rectangles." The cases in the code are based on Voronoi regions.
I guess we should have gone into more detail, sorry! You should definitely not have to explicitly calculate VR geometry or anything like that.
We just used the same approach presented in James Arvo's "A Simple Method for Box-Sphere Intersection Testing" in the book Graphics Gems. You can find the code example here: http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c
The basic idea is that the result of axis tests for box-vs-box contain all the information you need in order to infer which corner of the box is closest to the circle's center, and whether the circle's center is in the VR of that corner. If you draw it all out on paper it becomes a lot more obvious than just staring at the math.
We just used the same approach presented in James Arvo's "A Simple Method for Box-Sphere Intersection Testing" in the book Graphics Gems. You can find the code example here: http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c
The basic idea is that the result of axis tests for box-vs-box contain all the information you need in order to infer which corner of the box is closest to the circle's center, and whether the circle's center is in the VR of that corner. If you draw it all out on paper it becomes a lot more obvious than just staring at the math.
Author
Therefore the steps are:
1)calculate sat box min/max, projecting circle center, on each box axis.
2)check if box and circle are colliding writing the piece of code below.(I don't need a third axis?)
/* Solid Box and Solid Sphere */
dmin = 0;
for( i = 0; i < n; i++ ) {
if( C < Bmin ) dmin += SQR( C - Bmin ); else
if( C > Bmax ) dmin += SQR( C - Bmax );
}
if( dmin <= r2 ) return TRUE;
then? how to obtain the mtv?
Damn...can't yet understand sorry :(
Could you please go into more detail?..I guess I'm not a very talented programmer..
[Edited by - forrestuv on August 2, 2010 9:44:30 AM]
1)calculate sat box min/max, projecting circle center, on each box axis.
2)check if box and circle are colliding writing the piece of code below.(I don't need a third axis?)
/* Solid Box and Solid Sphere */
dmin = 0;
for( i = 0; i < n; i++ ) {
if( C < Bmin ) dmin += SQR( C - Bmin ); else
if( C > Bmax ) dmin += SQR( C - Bmax );
}
if( dmin <= r2 ) return TRUE;
then? how to obtain the mtv?
Damn...can't yet understand sorry :(
Could you please go into more detail?..I guess I'm not a very talented programmer..
[Edited by - forrestuv on August 2, 2010 9:44:30 AM]
Sorry, that code is a bit confusing -- I didn't realize that they're only determining a boolean result and not contact points or MTV, it's been a while.
The basic idea is the same though -- note that they're using += to accumulate the squared distances along each axis. This means that if the circle is in the VR region of an edge, only a single value will be added (x or y) whereas if the circle is in a corner VR, two values will be added (squared distance along both x and y) which means dmin will end up with squared distance from the closest corner to the circle center.
A simple approach that works in all cases is to clamp the position of the circle's center to the box's extents; the resulting point will be your contact point on the box:
contact_x = min(box.max_x, max(box.min_x, circle.x))
contact_y = min(box.max_y, max(box.min_y, circle.y))
this works but doesn't give you any "early outs". I would guess that performance of this code isn't going to be a bottleneck, so simple+readable should be good enough until it turns up in a profile :)
The basic idea is the same though -- note that they're using += to accumulate the squared distances along each axis. This means that if the circle is in the VR region of an edge, only a single value will be added (x or y) whereas if the circle is in a corner VR, two values will be added (squared distance along both x and y) which means dmin will end up with squared distance from the closest corner to the circle center.
A simple approach that works in all cases is to clamp the position of the circle's center to the box's extents; the resulting point will be your contact point on the box:
contact_x = min(box.max_x, max(box.min_x, circle.x))
contact_y = min(box.max_y, max(box.min_y, circle.y))
this works but doesn't give you any "early outs". I would guess that performance of this code isn't going to be a bottleneck, so simple+readable should be good enough until it turns up in a profile :)
Author
To do that have I to transform the rotated box to axis aligned first?
this is what I've found by searching the forum..
Is it the fastest method?Because I need a fast one..
this is what I've found by searching the forum..
Is it the fastest method?Because I need a fast one..
Vector ClosestPointOnOrientedBox(const Vector& Point, const Vector& Centre, const Vector& Extent, const Matrix33& Orientation, bool& inside){ Vector Delta = (Point - Centre).MultiplyByTransposeMatrix(Orientation); inside = true; if (fabs(Delta.x) > Extent.x) { inside = false; Delta.x = Extent.x * sign(Delta.x); } if (fabs(Delta.y) > Extent.y) { inside = false; Delta.y = Extent.y * sign(Delta.y); } if (fabs(Delta.z) > Extent.z) { inside = false; Delta.z = Extent.z * sign(Delta.z); } // point was found outside. all good. if(!inside) { return Centre + Delta.MultiplyByMatrix(Orientation); } // point was found inside. Find which face is closest to our point. if (fabs(Delta.x) < fabs(Delta.y)) { Delta.y = 0.0f; if (fabs(Delta.z) < fabs(Delta.x)) Delta.x = 0.0f; else Delta.z = 0.0f; } else { Delta.x = 0.0f; if (fabs(Delta.z) < fabs(Delta.y)) Delta.y = 0.0f; else Delta.z = 0.0f; } return Centre + Delta.MultiplyByMatrix(Orientation);}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement