f



bounding box/bounding box intersection.

Hi guys,

thanks so much for your recent help with my collision detection problems.

I just have one more thing then I think I've got all I need to start coding 
it up.

I have two Axis Aligned Bounding Boxes. One is stationary. One is moving 
(the reason for this is that it simplifies things - 2 boxes moving relative 
to each other can be considered as one stationary and the other moving)

I have 2 questions, but 2 is more important cos it assumes you know the 
answer to 1)


Now I have a "velocity vector" for the moving box (i.e it moves in a certain 
direction at x meters per second)



1) Now, given time t, how can I tell if the two boxes will intersect?

The problem here is not *are* they intersecting but *will* they? For 
example, on the way from the starting position of the moving box, to its end 
position, it may pass OVER and no longer be touching the stationary box. It 
which case it will appear as if no "collision" has occurred.

I know how to do this for circles. (this : 
http://www.gamasutra.com/features/20020118/vandenhuevel_01.htm article 
explains how)

That is, given a stationary circle and a moving circle with velocity v, I 
can work out how long it is before they collide.

2) What I need to know, is how to do this for boxes, or rather rectangles.

I hope this makes sense.....


Thanks again

Dean


0
Dean
4/6/2005 12:48:27 AM
comp.games.programming.misc 1186 articles. 0 followers. jonathanfigaro (52) is leader. Post Follow

3 Replies
518 Views

Similar Articles

[PageSpeed] 7

In article <vlG4e.7026$JO6.6920@newsfe6-win.ntli.net>, 
nospam@nospam.com says...

> 1) Now, given time t, how can I tell if the two boxes will intersect?

> That is, given a stationary circle and a moving circle with velocity v, I 
> can work out how long it is before they collide.
> 
> 2) What I need to know, is how to do this for boxes, or rather rectangles.
> 
> I hope this makes sense.....

I assume that the boxes are not already intersecting.

A simple if uneconomical solution would to test the trajectories of all 
eight corners against the four edges of the other box, and find the 
first collision.  This will give you the answer unless the boxes meet 
along parallel edges.

To eliminate the case of parallel edges, a simple if sleazy solution is 
to tilt one box by a thousandth of a degree.  Or you can work out a 
proper test for a 'parallel' intersection.  (Of course if you know the 
boxes are parallel, you can probably simplify the whole solution quite 
a bit.)

- Gerry Quinn
0
Gerry
4/6/2005 9:34:18 AM
Dean Ware wrote:

> Hi guys,
> 
> thanks so much for your recent help with my collision detection problems.
> 
> I just have one more thing then I think I've got all I need to start coding 
> it up.
> 
> I have two Axis Aligned Bounding Boxes. One is stationary. One is moving 
> (the reason for this is that it simplifies things - 2 boxes moving relative 
> to each other can be considered as one stationary and the other moving)
> 
> I have 2 questions, but 2 is more important cos it assumes you know the 
> answer to 1)
> 
> 
> Now I have a "velocity vector" for the moving box (i.e it moves in a certain 
> direction at x meters per second)
> 
> 
> 
> 1) Now, given time t, how can I tell if the two boxes will intersect?

    Maintain axis-sorted lists of the bounding boxes in
three axes.  Change of relative position in the list will tell you
of possible intersections.  Only then do you run the box-against-box
test.

    This works fine for very large numbers of boxes.  You should
be able to handle 10,000 to 100,000 moving objects without
any problems.

    This algorithm first appeared in I-COLLIDE.  It's in the
literature and there's code available.  (You'll want to rewrite it;
I-COLLIDE was derived from a LISP program and predates
collection libraries, so there's too much low-level pointer
manipulation.)

    I-COLLIDE only detected
actual box overlap.  But with some additional work, you can detect
potential fly-throughs, which is what you're asking for.
We used an improved version in Falling Bodies.

					John Nagle
					Animats
0
John
4/6/2005 6:59:59 PM
In article <PkW4e.10363$FN4.9195@newssvr21.news.prodigy.com>, 
nagle@animats.com says...
> [...] This algorithm first appeared in I-COLLIDE.

Actually Baraff described the basic algorithm ealier.

-- 
Christer Ericson
http://realtimecollisiondetection.net/
0
Christer
4/7/2005 5:02:07 AM
Reply:

Similar Artilces:

Where does my line intersect (or not) my bounding box.
Known: P and Q, two points on the infinite length line L. Wanted: segment l=(p,q) of L that intersects a box specified by x,y,w,h. All the algorithms I have seen so far require the (p,q) segment apriori, but I only have P and Q. L is to be a crease in a paper folding application (java). I hope to use segment l and the box to create java2d areas that are intersections or subtractions of a subject area. One of the areas would be flipped about the crease to emulate a folding action. -- Richard A. DeVenezia "Richard A. DeVenezia" <radevenz@ix.netcom.com> wrote in message ...

Intersection of two bounding boxes
Given two bounding boxes A and B. How to find if A and B intersect or overlap? Thanks! -Swathi On Tuesday, December 3, 2013 2:27:04 PM UTC-8, sparklingduce wrote: > Given two bounding boxes A and B. How to find if A and B intersect or overlap? Thanks! > > > > -Swathi I tried the command dbBBoxIntersect. It says "undefined function". Thanks! On Tuesday, December 3, 2013 4:27:04 PM UTC-6, sparklingduce wrote: > Given two bounding boxes A and B. How to find if A and B intersect or overlap? Thanks! > > > > -Swathi On Wednesday, ...

bounding box
Hi everybody, I would like to obtain max and min dimensions in each X,Y,Z of an object I visualized. In practice i would like to obtain a boundig box range. How can I get it? please reply to giancarlo.amati@mail.ing.unibo.it Thank you Giancarlo Giancarlo Amati <giancarlo.amati@mail.ing.unibo.it> writes: > I would like to obtain max and min dimensions in each X,Y,Z of an > object I visualized. In practice i would like to obtain a boundig > box range. How can I get it? Use SoGetBoundingBoxAction. Morten -- <URL:http://www.coin3d.org> yes but...

Bounding Box
What do I need to do to correct this observation: !Latex Error: Cannot determine size of graphic in XXX.eps (no BoundingBox) The graphic size is 150px. X 100px. Thanks Bernard Bernard Murphy <ber_murphy@eircom.net> wrote: > What do I need to do to correct this observation: > > !Latex Error: Cannot determine size of graphic in XXX.eps (no BoundingBox) > The graphic size is 150px. X 100px. For a quick fix you could just put a line %%BoundingBox: 0 0 <x> <y> at the beginning of your file, where <x> and <y> stand for the desired width and heigh...

Bounding box?
A program generates 3 files, stst.dat, march1.dat and march2.dat, and I have file 0.8 lying (a vertical line). I use this script: #------------------------------ gnuplots # gnuplot << eoi set term postscript eps enh 24 set output 'march.slab.eps' set nokey set size 1, 2.1 set pointsize 2.0 set multiplot # u_0 vs delta: set size 1, 1 set origin 0, 1.05 set xrange [0:1] set yrange [0:3] set ytics 0, 1, 3 set xlabel '{/Symbol=28 d}' set ylabel '{/Italic=28 u_0}' rotate by 0 plot 'stst.dat' w l lt 1, '0.8' w l ...

Bounding box
Please kindly help me, I want to find the bounding box from an inverted binary image from a signature recognition, I'm confused ...

bounding boxes
Hi everyone! I'm looking for a good explanation of minimal bounding boxes creation. I found some mathematical papers f.e. at www.magic-software.com, but they're a little bit too tough. Please, help if you know any other. regards - m z - "Micha�" <firewire1@wp.pl> schrieb im Newsbeitrag news:c0algb$nkn$1@nemesis.news.tpi.pl... > Hi everyone! > > I'm looking for a good explanation of minimal bounding boxes > creation. I found some mathematical papers f.e. at > www.magic-software.com, but they're a little bit too tough. Pleas...

Bounding box?
Is there a utility that could tell me the bounding box of a TrueType font? I need to find the biggest font size that fits in a given vertical space. The utility should check also non-Latin codepages. -Pertti ...

bounding box
can anyone pls help with how to draw a bounding box for an irregular shaped image. You look for minimum enclosing rectangle in Matlab Forum for your problem. I hope you will get it. Yumnam Kirani Singh Tronglaobi Awang Leikai "meena rao" <meenaraos@yahoo.co.in> wrote in message <ies80t$ph9$1@fred.mathworks.com>... > can anyone pls help with how to draw a bounding box for an irregular shaped image. On Dec 22, 2:06=A0am, "meena rao" <meenar...@yahoo.co.in> wrote: > can anyone pls help with how to draw a bounding box for an irregular shap...

Bounding box of Triangle / AABB intersection
Hi, I've been looking for a fast triangle/AABB intersection algorithm that will return the bounding box of the intersecting region (if there is any). I'm aquainted with Tomas Moller's excellent code, but extracting the intersection positions didn't seem to extend naturally from it - and I wondered whether a different algorithm might be more applicable. I thought I'd ask whether anyone here had any useful pointers. Best Regards Matt You could try the routine from the book "Real Time Collision Detection" on page 169. It basically uses a separating axis test, w...

Bounding Box
Anyone know of a way to use the results of the model size measurement (bounding box) in a relation or analysis feature? I need to have the overall size of an assembly returned as a value, preferably in the 3 axes. Thanks. I don't know if you can do it the way you say, but you can slap datum curves along the extents of the model, align them to the model extents and dimension them (the dimensions will appear as extras) then use relations to push the dimensions into parameters which you can use. This is not a robust method, there must be a more elegant way to achieve this &...

Bounding Box
Using SW3 I have two questions for consideration. Thank you to all are kind enough to offer help. 1) Since SW is smart enough to automatically create a bounding box around a component, is there a way to access and use the size of this box for a BOM Material Size entry? Right now I am linking each xyz dim to a Special Property. 2) Can a macro be written that will link a part on sheet 2,3,etc. to the BOM Item# on sheet 1? If so, I would like to discuss $$ for someone to do it for me. This is why: I always use multiple sheets and include an informational Block with each of several items deta...

Capsule/Axis-aligned bounding box intersection
Hi, I'm looking for an algorithm that can compute the intersection between a capsule and an axis aligned bounding box (AABB). On the magic-software.com website there is an algorithm for computing the intersection between a sphere and an AABB so even if someone knows where I could find an algorithm for cylinder/AABB intersection that would be sufficient as well. Any ideas? Omair "Omair-Inam Abdul-Matin" <oiinamul@cs.uwaterloo.ca> wrote in message news:cb7str$hvd$1@rumours.uwaterloo.ca... > I'm looking for an algorithm that can compute the intersection betwee...

Polygon intersection, coverage, area, bounding box/circle,
Hi, Assume we have two non-intersection polygons P1 = p1(x1,y1), p2(x2,y2),..., pN(xN,yN) P2 = p1(x1,y1), p2(x2,y2),..., pM(xM,yM) where "Pi" is the polygon constructed with the ordered 2D points "pi(xi,yi)", ie. vertices. They could be convex or concave. Following are two simple example polygons P1 and P2, with 4 and 6 vertices respectively. P1 : === p1(x1,y1) O----------O p2(x2,y2) \ / \ / p1(x4,y4) O-------O p3(x3,y3) P2 : === p1(x1,y1) O----------O p2(x2,y2) \...

Web resources about - bounding box/bounding box intersection. - comp.games.programming.misc

Intersection theory - Wikipedia, the free encyclopedia
In mathematics , intersection theory is a branch of algebraic geometry , where subvarieties are intersected on an algebraic variety , and of ...

The nonexistent intersection of the NFL's popularity and its violence - Grantland
Football is the most popular sport in America and probably the most dangerous. One has nothing to do with the other, and won't.

Cars Rush - The Road Traffic Intersection Run Hour Challenge on the App Store
Read reviews, compare customer ratings, see screenshots, and learn more about Cars Rush - The Road Traffic Intersection Run Hour Challenge. Download ...

Intersection
At the busiest intersections in Groningen, all bicycle traffic lights in every direction turn green at the same time. As 57% of all traffic in ...

Drivers navigate chaotic intersection in Ethiopia - YouTube
Mesmerizing footage of Meskel Square in Addis Ababa, Ethiopia. The massive intersection is a free-for-all for drivers, who manage to navigate ...

An uncomfortable intersection of political interests
On&nbsp;Sunday, thousands of fair dinkum real Aussies will gather at rallies across Australia, raising the Australian flag and shouting slogans. ...

Boy killed video - Residents want intersection fixed, Kallangur
Residents at Kallangur urge authorities to "fix this intersection" after five-year-old Myles Sparling was killed while riding his bike with family. ...

This One Intersection Explains Why Housing Is So Expensive In San Francisco
San Francisco is a great place to live, if you can afford it.

Canberra's worst intersections revealed as NRMA backs Barton Highway flyover
Former Labor minister Kate Lundy has said figures on&nbsp;the capital's worst crash intersections&nbsp;back the Canberra Liberals' argument for ...

Woman killed after hit by car at major Gold Coast intersection - The Courier-Mail Search Search
A WOMAN has been killed after being hit by a car at a major Gold Coast intersection.

Resources last updated: 1/28/2016 12:06:54 PM