Thread: RE: [Algorithms] Bounding Volume from Intersecting Planes
Brought to you by:
vexxed72
From: <c.s...@ph...> - 2004-08-28 11:17:56
|
Isn't exactly that the problem? Finding the vertices of N half spaces is = computationally equivalent of finding the convex hull of N points, by = duality. -----Original Message----- From: gda...@li... on behalf of Megan = Fox Sent: Fri 8/27/2004 8:31 PM To: gda...@li... Cc:=09 Subject: Re: [Algorithms] Bounding Volume from Intersecting Planes It's a simplist method, but - find the intersection points of the planes (if line segments, store the end-points), determine the center point of this point soup via an average, find the point the farthest from this center point, and the distance to that point is the radius of your bounding sphere. -Megan Fox |
From: <c.s...@ph...> - 2004-08-30 15:36:12
|
I you are confused, they were probably talking about this stuff: http://home.student.utwente.nl/j.suter/ga_primer.pdf http://www.wordiq.com/definition/Geometric_algebra http://modelingnts.la.asu.edu/html/IntroPrimerGeometricAlgebra.html besides, who will ever be going to implement this conformal 5D-zeugs in = an actual application, I mean, 32x32 matrix products anyone? -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of John = Paquin Sent: Monday, August 30, 2004 2:37 PM To: gda...@li... Subject: Re: [Algorithms] Bounding Volume from Intersecting Planes Jonathan, I went to the site you.. um.. sited, and I still have *no=20 idea* what you and Robin are writing about. I'm sure that what you guys = are proposing is a great solution, but my poor head is like a big, soft=20 musk-melon. There's only so much abuse it can take before it turns into = a useless slurry of old x86 assembly routines and Star Trek quotes. So I'm forced through outright ignorance to with my original idea which=20 is very similar to Megan's suggestion. I'm going to take the planes in groups of the 3 and find the single=20 intersection point of the three planes (if it exists). Then (and here's = an important step for me that's missing from Megan's description) test=20 that point against all the planes to make sure it falls on the boundary=20 of the convex volume being described. This is important, because a lot=20 of the points will be off in the hinterland outside of the volume. Then = I'll take the points that pass and construct the bounding volume. This is slow, but carries the advantage of not containing the words=20 "invert" or "MEET" :) -john |
From: <rob...@pl...> - 2004-08-30 17:33:35
|
If I may veer OT for a second, yes, you are right. 5D conformal GA is=20 inefficient on current machine architectures. But if you analyse the algori= thms=20 used in terms of the parallelism of individual operations you'll find that = most=20 operations inside, say, a JOIN or a MEET operation are independent of each = other. If we were to create a machine that executes 32-way MIMD, you would = end=20 up with fewer cycles to generate a more accurate result, and without except= ions=20 in the algorithm (e.g. no need for tests for coplanar elements, it just wor= ks). GA is faster, but not on current hardware and there's basically a free PhD = and=20 a guaranteed career in there for the first person to do the analysis and=20 propose the machine architecture. At the moment it seems to me that the=20 Mathematicians are off admiring GA's elegance and trying to prove basic=20 assertions (e.g. multivectors never occur in typical usage), the Physicists= are=20 off recoding old proofs in the new form to get better insights and the Comp= Sci=20 people are... well... sitting on their thumbs as far as I can tell. I mean, you know, I *would* work on it, but I'm just a little busy with thi= s=20 thing right now. - Robin Green. Christian Sch=FCler wrote: >=20 > Besides, who will ever be going to implement this conformal 5D-zeugs in a= n actual > application, I mean, 32x32 matrix products anyone? >=20 |
From: Jonathan B. <jo...@nu...> - 2004-08-30 18:39:07
|
Also there's a big difference between solving a problem on paper using=20 GA, and writing code that manipulates GA entities. I find that GA is the natural way that I approach a lot of problems when=20 I am thinking about them in my notebook. (Though, uhh, I don't do the=20 5D conformal stuff). But usually I use it to figure out the answer,=20 then see what equations the answer turns into. Invariably it's=20 something that doesn't require generic multivector manipulation. Though for bigger problems as we go into the future, that may no longer=20 be a practical approach. Hard to say. Anyway, I like GA, but I don't write GA code, even for 3D... -J. rob...@pl... wrote: > > If I may veer OT for a second, yes, you are right. 5D conformal GA is=20 > inefficient on current machine architectures. But if you analyse the=20 > algorithms used in terms of the parallelism of individual operations=20 > you'll find that most operations inside, say, a JOIN or a MEET=20 > operation are independent of each other. If we were to create a=20 > machine that executes 32-way MIMD, you would end up with fewer cycles=20 > to generate a more accurate result, and without exceptions in the=20 > algorithm (e.g. no need for tests for coplanar elements, it just works). > > GA is faster, but not on current hardware and there's basically a free=20 > PhD and a guaranteed career in there for the first person to do the=20 > analysis and propose the machine architecture. At the moment it seems=20 > to me that the Mathematicians are off admiring GA's elegance and=20 > trying to prove basic assertions (e.g. multivectors never occur in=20 > typical usage), the Physicists are off recoding old proofs in the new=20 > form to get better insights and the CompSci people are... well...=20 > sitting on their thumbs as far as I can tell. > > I mean, you know, I *would* work on it, but I'm just a little busy=20 > with this thing right now. > > - Robin Green. > > > Christian Sch=FCler wrote: > >> >> Besides, who will ever be going to implement this conformal 5D-zeugs=20 >> in an actual > > > application, I mean, 32x32 matrix products anyone? > >> > > > ------------------------------------------------------- > This SF.Net email is sponsored by BEA Weblogic Workshop > FREE Java Enterprise J2EE developer tools! > Get your free copy of BEA WebLogic Workshop 8.1 today. > http://ads.osdn.com/?ad_idP47&alloc_id=10808&op=CCk > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > |
From: Charles B. <cb...@cb...> - 2004-08-30 19:31:25
|
The advantages of GA are also its disadvantages. GA is=20 dimension-independent and coordinate frame free, but in practical problems= =20 there are a lot of advantages to knowing what dimension you're in and=20 special-casing to coordinate axes. GA is generally a very nice way to=20 write the laws of the universe in a vacuum, but not very convenient for=20 solving 2d and 3d geometry problems. 0d through 3d are very weird special= =20 dimensions that we live in. Everything 4d and up is sort of "normal" in=20 the sense of not having all the strange properties of the lower dimensions;= =20 the rotation groups of 3d and lower are very unusual, as is the topology of= =20 the space itself and the symmetry groups. At 01:38 PM 8/30/2004 -0500, Jonathan Blow wrote: >Also there's a big difference between solving a problem on paper using GA,= =20 >and writing code that manipulates GA entities. > >I find that GA is the natural way that I approach a lot of problems when I= =20 >am thinking about them in my notebook. (Though, uhh, I don't do the 5D=20 >conformal stuff). But usually I use it to figure out the answer, then see= =20 >what equations the answer turns into. Invariably it's something that=20 >doesn't require generic multivector manipulation. > >Though for bigger problems as we go into the future, that may no longer be= =20 >a practical approach. Hard to say. > >Anyway, I like GA, but I don't write GA code, even for 3D... > > -J. > > >rob...@pl... wrote: > >> >>If I may veer OT for a second, yes, you are right. 5D conformal GA is=20 >>inefficient on current machine architectures. But if you analyse the=20 >>algorithms used in terms of the parallelism of individual operations=20 >>you'll find that most operations inside, say, a JOIN or a MEET operation= =20 >>are independent of each other. If we were to create a machine that=20 >>executes 32-way MIMD, you would end up with fewer cycles to generate a=20 >>more accurate result, and without exceptions in the algorithm (e.g. no=20 >>need for tests for coplanar elements, it just works). >> >>GA is faster, but not on current hardware and there's basically a free=20 >>PhD and a guaranteed career in there for the first person to do the=20 >>analysis and propose the machine architecture. At the moment it seems to= =20 >>me that the Mathematicians are off admiring GA's elegance and trying to=20 >>prove basic assertions (e.g. multivectors never occur in typical usage),= =20 >>the Physicists are off recoding old proofs in the new form to get better= =20 >>insights and the CompSci people are... well... sitting on their thumbs as= =20 >>far as I can tell. >> >>I mean, you know, I *would* work on it, but I'm just a little busy with=20 >>this thing right now. >> >>- Robin Green. >> >> >>Christian Sch=FCler wrote: >> >>> >>>Besides, who will ever be going to implement this conformal 5D-zeugs in= =20 >>>an actual >> >> > application, I mean, 32x32 matrix products anyone? >> >> >> >>------------------------------------------------------- >>This SF.Net email is sponsored by BEA Weblogic Workshop >>FREE Java Enterprise J2EE developer tools! >>Get your free copy of BEA WebLogic Workshop 8.1 today. >>_______________________________________________ >>GDAlgorithms-list mailing list >>GDA...@li... >>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>Archives: >>http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > >------------------------------------------------------- >This SF.Net email is sponsored by BEA Weblogic Workshop >FREE Java Enterprise J2EE developer tools! >Get your free copy of BEA WebLogic Workshop 8.1 today. >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 ---------------------------------------------------- Charles Bloom email "cb" http://www.cbloom.com |
From: Simon F. <sim...@po...> - 2004-08-31 09:41:39
|
John Paquin [mailto:jp...@br...] wrote > > Is there an easy way to get the bounding volume (sphere say) of the > intersection of multiple planes? > > I want to do a volume intersection test where the caller specifies a > series of planes which intersect to form some convex volume. If it's of any help, I just started with a large cube and let the planes slice pieces off. Simon ****************** This e-mail has been sent from Imagination Technologies Limited. PowerVR, Metagence, Ensigma and PURE Digital are divisions of Imagination Technologies Limited. The information contained in this e-mail, including any attachment, is confidential and may be legally privileged. It is intended solely for the addressee(s) and access to this e-mail by anyone else is unauthorised. If you are not the intended recipient, any disclosure, copying or distribution or use of the information contained in this e-mail, is prohibited and may be unlawful. If you have received this e-mail in error, please notify the sender by return e-mail and then delete it from your system. Internet communications cannot be guaranteed to be secure, error or virus-free. The sender does not accept liability for any errors or omissions which arise as a result. Any views expressed in this message are those of the author, except where the author specifies and, with authority, states them to be the views of Imagination Technologies Ltd. |
From: Gino v. d. B. <gva...@pl...> - 2004-08-31 10:15:46
|
Qhull http://www.qhull.org/html/qhalf.htm performs halfspace intersection. Note that you need to provide an interior point of the intersection. The resulting polytope is output as a set of vertices for which you can compute a bounding volume in the usual way. Qhull can be compiled as a static library. Gino van den Bergen Playlogic Game Factory www.playlogicgames.com > -----Original Message----- > From: gda...@li... [mailto:gdalgorithms- > lis...@li...] On Behalf Of Simon Fenney > Sent: Tuesday, August 31, 2004 11:41 > To: 'gda...@li...' > Subject: RE: [Algorithms] Bounding Volume from Intersecting Planes >=20 >=20 > John Paquin [mailto:jp...@br...] wrote > > > > Is there an easy way to get the bounding volume (sphere say) of the > > intersection of multiple planes? > > > > I want to do a volume intersection test where the caller specifies a > > series of planes which intersect to form some convex volume. >=20 > If it's of any help, I just started with a large cube and let the planes > slice pieces off. >=20 > Simon > ****************** > This e-mail has been sent from Imagination Technologies Limited. > PowerVR, Metagence, Ensigma and PURE Digital are divisions > of Imagination Technologies Limited. >=20 > The information contained in this e-mail, including any attachment, > is confidential and may be legally privileged. It is intended solely > for the addressee(s) and access to this e-mail by anyone else is > unauthorised. If you are not the intended recipient, any disclosure, > copying or distribution or use of the information contained in this > e-mail, is prohibited and may be unlawful. If you have received this > e-mail in error, please notify the sender by return e-mail and then > delete it from your system. >=20 > Internet communications cannot be guaranteed to be secure, > error or virus-free. The sender does not accept liability for any errors > or omissions which arise as a result. >=20 > Any views expressed in this message are those of the author, except > where the author specifies and, with authority, states them to be the > views of Imagination Technologies Ltd. >=20 >=20 >=20 > ------------------------------------------------------- > This SF.Net email is sponsored by BEA Weblogic Workshop > FREE Java Enterprise J2EE developer tools! > Get your free copy of BEA WebLogic Workshop 8.1 today. > http://ads.osdn.com/?ad_id=3D5047&alloc_id=3D10808&op=3Dclick > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 |