f



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

0
11/27/2006 5:00:37 PM
comp.graphics.algorithms 6674 articles. 1 followers. Post Follow

1 Replies
484 Views

Similar Articles

[PageSpeed] 17

You could try the routine from the book "Real Time Collision Detection"
on page 169. It basically uses a separating axis test, where the axes
correspond to the 3 face normals of the AABB, the face normal of the
triangle, the 9 cross product axes from the combination of the previous
2.

There are robustness issues with this routine, namely when the cross
product is 0.


Jason

0
11/27/2006 5:17:03 PM
Reply:

Similar Artilces:

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 ...

AABB/triangle intersection
Could someone tell me if this code for an AABB/triangle intersection looks correct? i know it's slow, but i'm just thinking about correctness now. float getmin(const vector<Point> &points, Vector axis) { float min = std::numeric_limits<float>::max(); for (int ctr = 0; ctr < points.size(); ctr++) { float dotprod = Dot(points[ctr], axis); if (dotprod < min) min = dotprod; } return min; } float getmax(const vector<Point> &points, Vector axis) { float max = -std::numeric_limits<float>::max(); for (int ctr = 0; ctr < points.size(); ctr++) { float dotprod = Dot(points[ctr], axis); if (dotprod > max) max = dotprod; } return max; } bool isect(const vector<Point> &points1, const vector<Point> &points2, Vector axis) { if (getmin(points1, axis) > getmax(points2, axis)) return false; if (getmax(points1, axis) < getmin(points2, axis)) return false; return true; } bool isectboxtri(float center[3], float r[3], float triverts[3][3]) { vector<Point> boxpoints; boxpoints.push_back(Point(center[0]+r[0], center[1]+r[1], center[2]+r[2])); boxpoints.push_back(Point(center[0]+r[0], center[1]+r[1], center[2]-r[2])); boxpoints.push_back(Point(center[0]+r[0], center[1]-r[1], center[2]+r[2])); boxpoints.push_back(Point(center[0]+r[0], center[1]-r[1], center[2]-r[2])); boxpoints.push_back(Point(center[0]-r[0], center[1]+r[1], center[2]+r[2])); ...

bounding box algorithm
Hi everyone! I'm looking for bounding box construction algorithm. Can you give me some hint where to look for it? with regards - m z - Micha� wrote: > Hi everyone! > > I'm looking for bounding box construction algorithm. Can you give me > some hint where to look for it? > Try "google"... -- <\___/> For email, remove my socks. / O O \ \_____/ FTB. Why isn't there mouse-flavored cat food? Take a look here http://www.magic-software.com/Containment.html ---------------------------------------------------------...

Graphics--triangle intersection
Hi, I'm new to Mathematica. I would like to solve following problem. I have a number of overlapping triangles. In the intersection of all triangles, I want to draw the biggest triangle possible. Sounds simple ? Could this be solved in mathematica ? Any help is appreciated. Thanks Link to the forum page for this post: http://www.mathematica-users.org/webMathematica/wiki/wiki.jsp?pageName=Special:Forum_ViewTopic&pid=10465#p10465 Posted through http://www.mathematica-users.org [[postId=10465]] Hi, does the function imsConvexIntersect from http://www.im...

Triangle-triangle intersection
Hello ! Does someone know where I could find a delphi code to test if 2 triangles intersect (in 3D)? Thank you very much in advance. On Thu, 24 Nov 2005 17:07:44 +0100, Bob wrote: > Hello ! > > Does someone know where I could find a delphi code to test if 2 triangles > intersect (in 3D)? > > Thank you very much in advance. try google : triangle triangle intersection -- Sam Hi, Thanks.. you're right, it's not so difficult to find on the web (but in C of course). I also need a method to know if a 3D point is inside a tetraedron or not, does someone have such an algorithme ? Thanks in advance. "Samuel Hornus" <SamueldotHornusatinriadotfr@nospam.com> a �crit dans le message de news:20051124175915.412bba83.SamueldotHornusatinriadotfr@nospam.com... > On Thu, 24 Nov 2005 17:07:44 +0100, Bob wrote: > > > Hello ! > > > > Does someone know where I could find a delphi code to test if 2 triangles > > intersect (in 3D)? > > > > Thank you very much in advance. > > try google : triangle triangle intersection > > -- > Sam On Thu, 24 Nov 2005 18:03:44 +0100, Bob wrote: > you're right, it's not so difficult to find on the web (but in C of course). yes. translating to delphi should not be difficult. > I also need a method to know if a 3D point is inside a tetraedron or not, > does someone have such an algorithme ? A simple solution is to check that your ...

triangle/triangle intersections
does anyone have any idea where to obtain a code to determine triangle/ triangle intersections and their intersection point(s)? it would be nice if this could also handle coplanar triangles. thanks On Aug 6, 7:58 pm, swars...@gmail.com wrote: > does anyone have any idea where to obtain a code to determine triangle/ > triangle intersections and their intersection point(s)? it would be > nice if this could also handle coplanar triangles. > > thanks Hi, try this one: http://jgt.akpeters.com/papers/Moller97/tritri.html Jindra ...

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, December 4, 2013 7:05:52 AM UTC+5:30, sparklingduce wrote: > 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! Please use dbProduceOverlap On Wednesday, December 4, 2013 3:57:04 AM UTC+5:30, sparklingduce wrote: > Given two bounding boxes A and B. How to find if A and B intersect or overlap? Thanks! > > > > -Swathi Please use dbProduceOverlap On 12/17/13 05:47, Ajith V wrote: > On Wednesday, December 4, 2013 7:05:52 AM UTC+5:30, sparklingduce wrote: >> On Tuesday, December 3, 2013 2:27:04 PM UTC-8, sparklingduce wrote: >>...

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 ...

Graphics bounding box in source coordinates?
Is there some way of getting the bounding box of Graphics in the source coordinate system? For example, Show can be used to display an array of objects on top of each other: showObj[z_]:=Graphics[{Circle[{z,z},z]}] objs=showObj/@Range[5]; Show[objs] But I want to display them side by side. The following can be used to offset each object by a fixed interval: graphicsArray[g_,x_]:=Graphics[MapIndexed[Translate[#1,{x (First[#2]-1),0}]&,First/@g]] graphicsArray[objs,5] But I would like the gaps between each object to be of fixed size. So I want a version of graphicsArray which d...

Compute bounding box of arbitrary graphics
How can you compute the bounding box (rectangle) of an arbitrary block of graphics commands - specifically, a Windows metafile converted to PostScript by the Adobe PDF driver or any other PostScript printer driver? This sequence of graphics commands may contain any PostScript command, including gsave/grestore, so simply getting the clipping rectangle will not work. Is there some trick to doing this? Can something be embedded in the metafile such that, when converted, the bounding box rectangle will be available in the output? Right now, I have a kludge where I draw a diagonal line which...

graphic's bounding box
Hi, I have problem in adding a logo to a letter head. pdflatex said i have no bounding box. can anyone help me to solve the problem? Thanks! regards dee dee schrieb: > Hi, > > I have problem in adding a logo to a letter head. > pdflatex said i have no bounding box. > can anyone help me to solve the problem? > Convert the graphic file to one of the following formats: .pdf, .png, .jpg If this doesn't help send a small example which shows what you have done. ....Rolf ...

triangle triangle intersection test
Hi ! I have two triangles that intersects (i know this before!). What i want to get are two vectors (one for each triangle) where the "collision center" of the triangle is. At this positions i want to display some action like an explosion. For example when all six vectors of the two triangles (rare case) i want to get the middle point (vector) of the triangles. googling around i found http://www.acm.org/jgt/papers/Moller97/tritri.html from Thomas M�ller but it seems it didn't sweet my needs because it only tests the collision -- that is what i'am already knowing. Any...

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 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. It is not clear from your post what type of intersection you are looking for. My distinctions are: 1. both objects stationary a. test if they are intersecting b. find the set of intersection 2. one object moving, one object stationary for some time interval 0 <= t <= tmax. a. test if they are initially intersecting (case 1.a.) b. find the set of intersection initially, if any (case 1.b.) c. test if they intersect at some time in [0,tmax] d. find the first time of contact T, if any e. find the contact set at time T 3. t...

Skinny triangle-triangle intersection
The problem I'am analyzing requires intersecting skinny triangles: 3-d triangle-triangle intersection, where triangles are rather skinny: ratio between the shortest and longest side between 1:100 and 1:1000. Is there a specific algorithm, or usual algorithms and double precision (roughly equivalent to C doubles) is sufficient ? A solution error of .001:.0001 (obtained_solution -'true'_solution/'true'_solution) is enough. Thanks in advance Gigi ...

Comparison of Ray-AABB Intersection Point Algorithms
I'm working on a volume renderer which uses raycasting to assign pixels their color. The first step to take is to determine where each ray intersects the volume (essentially, an AABB). A colleague has argued that splitting the volume into 6 quadrilaterals and then 12 triangles and using Moller-Trumbore ray-triangle intersection on the 12 triangles is the fastest way. This seems crazy to me. Does his idea have merit? Thanks for any help. I have examined the archives, which make me doubt my colleague's assertion. But things change. - Chris In article <1142009876.273122.100120@j33g2000cwa.googlegroups.com>, crjjrc@gmail.com says... > I'm working on a volume renderer which uses raycasting to assign pixels > their color. The first step to take is to determine where each ray > intersects the volume (essentially, an AABB). A colleague has argued > that splitting the volume into 6 quadrilaterals and then 12 triangles > and using Moller-Trumbore ray-triangle intersection on the 12 triangles > is the fastest way. This seems crazy to me. Does his idea have merit? There are faster algorithms than that. I would also guess that it takes careful tuning to get the algorithm work such that no "holes" (due to inprecision) are left to edges and vertices where triangles join. Google for "ray aabb", and I am sure you will find something. Dave Eberly certainly has one implementation in www.geometrictools.com As to inters...

An Efficient and Robust Ray-Box Intersection Algorithm
Hello, I have a question concerning the algorithm presented in the paper "An Efficient and Robust Ray-Box Intersection Algorithm" by Amy Williams, Steve Barrus, R. Keith Morley, and Peter Shirley. Here=B4s a link to the paper: http://www.cs.utah.edu/~awilliam/box/box.pdf I would first of all like to know a) what the intersection interval actually is b) if there is a way to extract the exact hit positions (entry and exit). I assume that when I know the answer to a) I can answer b) myself? Thanks in advance for any help > Here?s a link to the paper: http://www.cs.utah.edu/~awilliam/box/box.pdf > > I would first of all like to know > a) what the intersection interval actually is > b) if there is a way to extract the exact hit positions (entry and > exit). > > I assume that when I know the answer to a) I can answer b) myself? If the ray does intersect the box, then the parametric interval is given by [tmin, tmax]. Just few weeks ago I had a correspondence with Peter Shirley on that there is one situation where this algorithm produces wrong results. If you just want to know if there is an intersection, then it is ok, but in case you want also the interval, there are a few singular buggy cases to be aware of. Quoting my post: "A problem comes around when the ray origin is exactly on the aabb face on some coordinate axis. Consider the x-axis: If inverseDirection = -infinity and r.origin.x() == bounds[0].x() then tmax = 0!...

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) \ \ \ \ \ O p3(x3,y3) \ / \ O p4(x4,y4) \ | p6(x6,y6) O-------O p5(x5,y5) Question: ======= Is there a public algorithm, and/or C/C++ source code that can test the following; * If P1 and P2 intersect bool IsInterect(P1, P2); * If P1 covered by P2 (all vertices and edges of P1 are located in P2) bool IsCovered(P1,P2); * Total area of P1 float AreaOf(P1); * Area of intersection P1 and p2 float AreaOfIntersection(P1,P2); * Bounding box of P1 B1= BoundingBox(P1); (where B1 is a rectangle with 4 vertices) * Bounding Circle of P1 C1 = BoundingCircleOf(P1); (where C1 defined by center coordiante and radius) Regards, Albert "Albert Goodwill" <albertgoodwill@yahoo.com> wrote...

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) \...

Joe O'Rourkes minimum bounding box algorithm
Hi all, I'm hoping someone here can help me with this algorithm because I don't have any access to a library with the original paper. I've read in an older post that where the minimum box exists, one of two conditions will be true - that the minimum bounding box either has a hull facet and a hull edge, or three hull edges, on independent faces. What I'd like to know is a) the best way to traverse the hull, and b) how to construct the test boxes once you have either the facet and edge or the three edges. It's b) thats really stumping me, a) would be nice to know but not imperative as it'll be an offline function. Thanks in advance for any help, Jeff. "Jeff S" <mrfunston_alpha@yahoo.co.uk> wrote in message news:69d9a403.0406050316.13c2d4ac@posting.google.com... > What I'd like to know is a) the best way to traverse the hull, and b) > how to construct the test boxes once you have either the facet and > edge or the three edges. It's b) thats really stumping me, a) would be > nice to know but not imperative as it'll be an offline function. For the case of a facet-edge configuration, the projection of the convex hull onto the plane leads to a convex polygon. Use the method of rotating calipers to compute the minimum area bounding rectangle for the convex polygon. That rectangle necessarily contains an edge of the convex polygon. The polygon edge was projected from a convex hull edge. Once you have the bounding...

looking for algorithms to detect intersection between a line and a 18-dop bounding volume
hi, I have implemented a 18-dop tree to bound a polygonal model in 3D space according to the paper of klosowski. now I am looking for algorithms to detect the intersection situation between a line( ray or segment) and a 18-dop bounding volume. since my major is mechanical engineering, i don't have much knowlege of computer graphics. Is there anybody who can help me? thanks in advance xiangyang.ren@uni-dortmund.de (X. Y. Ren) writes: > hi, > > I have implemented a 18-dop tree to bound a polygonal model in 3D > space according to the paper of klosowski. now I am looking for > algorithms to detect the intersection situation between a line( ray or > segment) and a 18-dop bounding volume. since my major is mechanical > engineering, i don't have much knowlege of computer graphics. Is there > anybody who can help me? It's pretty straightforward. Any k-dop is convex and totally determined by 9 pairs of planes. Each pair of planes divides space into 3 parts, which we can call "left", "middle", and "right". If any point on the line segment is within the k-dop, which is to say is between each pair of planes, the line segment and k-dop intersect. So if for every pair of planes, your line segment's endpoints either straddle the k-dop (left/right or right/left), or one or both of them are inside it (middle), they intersect, otherwise not. And (to spell out the boundary case) if for any pair, the segment to...

Fast Triangle/Triangle Intersection Test
Does anyone have the algorithm and sample code for a fast triangle-triangle intersection test. I've read somewhere that the test in the ERIT package is simpler and sometimes faster than Moller's method. Does any have know about ERIT's test or possibly an even faster one? Secondly, a new book claims the following which may speed up a lot of graphics code by replacing standard functions like cosine, sine, square root completely. Here is the URL: http://web.maths.unsw.edu.au/~norman/book.htm DIVINE PROPORTIONS: Rational Trigonometry to Universal Geometry by N J Wildberger Revolutionary content This text introduces a new and simplified approach to trigonometry and a major restructuring of Euclidean geometry. It replaces cos, sin, tan and all those other transcendental trig functions with rational functions and elementary arithmetic. It develops a complete theory of planar Euclidean geometry over a general field without any reliance on `axioms'. And it shows how to apply this new theory to a wide range of practical problems from engineering, physics, surveying and calculus. New formulas and theorems Divine Proportions: Rational Trigonometry to Universal Geometry contains dozens of new and important formulas, and almost a hundred theorems. The formulas are mostly polynomial or rational, and the basic ones, such as the Triple Quad formula, the Spread Law, the Cross law and the Triple Spread formula are quadratic in any variable. The theorems are often based o...

Moller triangle triangle intersection test
Hi, I'm trying to figure out Moller triangle triangle intersection test. Here's a quick pdf. http://www.cs.lth.se/home/Tomas_Akenine_Moller/pubs/tritri.pdf The problem is I'm stuck at equation 4: I don't understand how Moller figures out the parametric value t1 from the similar triangles. Any tips will be greatly appreciated! Thanxs DuritzTheRealOne@gmail.com wrote: > Hi, > > I'm trying to figure out Moller triangle triangle intersection test. > Here's a quick pdf. > > http://www.cs.lth.se/home/Tomas_Akenine_Moller/pubs/tritri.pdf > > The problem is I'm stuck at equation 4: I don't understand how Moller > figures out the parametric value t1 from the similar triangles. > > Any tips will be greatly appreciated! > > Thanxs > What you need to be aware of is that there are two types of projections. Firstly, in order to find the intersection parameters on an edge of a triangle you need to project the edge's vertices onto the normal of triangle (i.e. the signed distance computation). With these parameters you could compute the 3D points of intersection and then project them onto the line L. However, Moeller performs these two steps in one step by using the intersection parameter (d0 / (do - d1)) directly onto the projected vertices. I'm not sure if you gain anything by doing this but that's another issue. Does this make sense? Gino van den Bergen www.dtecta.com On 13 Lug, 12:45, Gin...

help with graphic a circle and triangles on the same graphic.
Hi , i made a program (.m file) that calculates de area of a circle by adding isoceles triangles (polygons) so tehn it shows the errors and stuff , so you can put how many trianges you want to inscribe in the circle but now i need to graphic the circle and the triangles , and i just can't do that , help me please , by email im from chile thanks. ...

robust 3D triangle-triangle intersection test
I wonder if there's any robust 3D triangle-triangle intersection predicate? I am dealing with triangular mesh with very small and close triangles. It seems that the most widely used 3D triangle-triangle intersection routine is Tomas Moller's routine. I've tried his code, but it didn't produce robust results for my cases. For example, there are two triangles: REAL V0[3] = {29.433118660881500971981949987821, 32.03032197612869680369840352796, 24} ; REAL V1[3] = {29.433118660881500971981949987821, 32.03032197612869680369840352796, 29.5} ; REAL V2[3] = {32.583610623198097755448543466628, 28.819408716276900150887740892358, 29.5} ; REAL U0[3] = {29.433118660881401495998943573795, 32.03032197612869680369840352796, 19.3000000000000007105427357601} ; REAL U1[3] = {29.433118660881500971981949987821, 32.03032197612869680369840352796, 22} ; REAL U2[3] = {32.583610623198097755448543466628, 28.819408716276900150887740892358, 19.3000000000000007105427357601} ; Moller's routine has an epsilon threshold. The above triangles are actually pretty far apart, but they are nearly coplanar. If Moller's routine think they the coplanar, then it would correctly claim they don't intersect. But the routine is very...

Web resources about - Bounding box of Triangle / AABB intersection - comp.graphics.algorithms

Intersection (set theory) - Wikipedia, the free encyclopedia
More generally, one can take the intersection of several sets at once. The intersection of A , B , C , and D , for example, is A ∩ B ∩ C ∩ D ...

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 ...

Flickr: Intersection Consulting's Photostream
... and visual thinker that uses a casual, no-nonsense approach to help organizations achieve their goals using the dynamics of web 2.0 www.int ...

Richard Serra at MoMA - Intersection II (1992) - YouTube
Video walkthrough of Richard Serra's sculpture Intersection II (1992) on display at MoMA as part of the exhibition Richard Serra Sculpture: Forty ...

Left turn on red light allowed at more Brisbane intersections
Council has expanded the number of intersections at which drivers can turn left on red lights.

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.

The seven worst intersections for crashes in Victoria
Some people would never have a reason to call triple-0. Jason Stangherlin is sent scrambling to call emergency services at least once a month. ...

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: 3/7/2016 7:12:28 PM