Since the code is pretty short I thought it would be safe to post here
without starting a flame war.  
I was looking at prism objects seriously for the first time yesterday
because this was the first time I thought it would be useful for what I
was trying to make.  I realized that I could make a tetrahedron with
it.  Not that tetrahedrons actually have anything to do with my current
project.  I was just thinking that POV-Ray might handle prisms more
efficiently than plane intersections, because they are finite as opposed
to infinite objects.  It takes 4 points anywhere in space, and creates a
tetrahedron there.  I was only sidetracked by this idea for about 6
hours.  Most of that time was fixing bugs.  Anyone know if this approach
is actually faster than plane intersections?  

#include "colors.inc"
#include "transforms.inc"
#include "textures.inc"

light_source {<3,4,-5>*100 rgb 2}
camera {location <0,0,-15> look_at 0}

#macro Proj (U,V)  // projection of U onto V
        ((V)*(vdot((U),(V))/vdot((V),(V))))
#end
#macro H2tr(U1,U2,V1,V2) // Here to there rotation... two reference
points for initial and final positions
        #local X1 = vnormalize(U1);                // find basis vectors
of initial and
        #local Z1 = vnormalize(vcross(X1,U2));     // final refrence
frames
        #local Y1 = vcross(Z1,X1);                 
        #local X2 = vnormalize(V1);
        #local Z2 = vnormalize(vcross(X2,V2));
        #local Y2 = vcross(Z2,X2);
        #local Trans1 = transform{matrix
<X1.x,Y1.x,Z1.x,X1.y,Y1.y,Z1.y,X1.z,Y1.z,Z1.z,0,0,0>}
        #local Trans2 = transform{matrix
<vdot(X2,X1),vdot(X2,Y1),vdot(X2,Z1),vdot(Y2,X1),vdot(Y2,Y1),vdot(Y2,Z1),vdot(Z2,X1),vdot(Z2,Y1),vdot(Z2,Z1),0,0,0>}
        #local Trans3 = transform{Trans1 inverse}
        #local Rotation = transform {Trans1 Trans2 Trans3}
        Rotation
#end
#macro H2t (Oi,Ai,Ri,Of,Af,Rf)                // Here to there 
       transform{
       translate (- Oi)               // center, and two reference
points on object
       H2tr((Ai-Oi),(Ri-Oi),(Af-Of),(Rf-Of))  // New center, and
refrence point locations
       translate Of} 
#end   // (Origin, Absolute vector, Relative vector) initial, and final
orientations
#macro Tet_prism(Vec1,Vec2,Vec3,Vec4)
        #local Cross = vcross((Vec2)-(Vec1),(Vec3)-(Vec1));// Find
normal to plane three points are on
        #local STP = vdot(Cross,((Vec4)-(Vec1)));// Scalar Triple
Product
        #if (STP = 0) #error "degenerate tetrahedron volume = 0" #end
        #local Normal = ((STP > 0 ? -1 : 1)*vnormalize(Cross));// sign
corrected normal
        #local Basepoint = (Proj(Vec1,Normal));// point on base whose
normal points to Vec4
        #local Height = vlength((Basepoint)-(Vec4));// distance between
point 4, and the plane the other three points are on
        #local Transform = transform{H2t
(Basepoint,Vec4,Vec1,(Height*y),<0,0,0>,((Height*y)+x)) scale
(1/Height)}
        #local V1 = vtransform(Vec1, Transform);
        #local V2 = vtransform(Vec2, Transform);
        #local V3 = vtransform(Vec3, Transform);
        object {
                prism {
                conic_sweep
                linear_spline
                0, // sweep the following shape from here ...
                1, // ... up through here
                4, // the number of points making up the shape ...
                <V1.x,V1.z>,<V2.x,V2.z>,<V3.x,V3.z>,<V1.x,V1.z>
                transform {Transform inverse}
                        }//prism
                }//object 
#end//Tet_prism

object{Tet_prism(<1,1,1>,<-1,1,-1>,<1,-1,-1>,<-1,-1,1>) pigment{Green}}
object{Tet_prism(<1,1,1>,<-1,1,-1>,<-1,1,1>,<-1,6,1>) pigment{Orange}}
//object{Tet_prism(<1,0,0>,<0,0,1>,<-1,0,-1>,<0,5,0>)
pigment{Green}finish {ambient 1}}


-- 
Dan Johnson 

http://www.geocities.com/zapob

Post a reply to this message

Hello, Dan.

Great idea and thanks for sharing it!

Now, for your question... you can't really tell whether it will be
faster until you stress-test it. Put several thousands of those in a
scene and compare the render times of each approach. Also, while one
object may be faster, it may still be slower in CSG, so that's also
worth a try.

As of your concerns of starting a flame war, I doubt it :) It's just
that if someone looks for examples of code, macros, scenes etc., one
usually looks into the scene-files groups. In general, the chances of
finding something (not just a post) are greater if it's in the right
place (this from the guy whose view of order is "Throw everything
here, this way the more recent stuff requires less digging." :) )
Anyway, just a thought.


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

Dan Johnson <zap### [at] hotmailcom> wrote:
> Anyone know if this approach
> is actually faster than plane intersections?  

  There was once a long thread in some group about the most efficient way
of making a box with all six sides textured differently.
  Several approaches were made and their rendering times measured. For
example it was done with the intersection of six planes, the union of
six 2-dimensional boxes, six polygons and a mesh. (Also using a single
box with a clever pattern was suggested, but that's irrelevant in this case).
  Perhaps a bit surprisingly, with such a low triangle count the mesh was
not the fastest option. I don't remember which one was, but it might have
been the union of polygons. (The problem with it is that it's not usable
in CSG.)

  In your case the intersection of planes might be just ok. You simply have
to manually bound the tetrahedron eg. with a sphere.
  You might also try using a mesh (with inside_vector you can make it
CSG'able). If you don't need to use the tetrahedron in CSG, you might want
to try a union of four triangles, or even polygons, though I doubt it will
be faster than the union of triangles.
  I think that with such a low triangle count, the union of triangles may
be faster than a mesh.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Peter Popov wrote:
> 
> Hello, Dan.
> 
> Great idea and thanks for sharing it!

Aww shucks that makes the 6 hours I spent worth it.  Blessed feedback.
 
> Now, for your question... you can't really tell whether it will be
> faster until you stress-test it. Put several thousands of those in a
> scene and compare the render times of each approach. Also, while one
> object may be faster, it may still be slower in CSG, so that's also
> worth a try.

Yeah I figured that would be the way to do it.  I didn't feel like doing
all that testing though.  It sounded like a lot of work.  I thought
perhaps someone might have immediate need for millions of tetrahedrons. 
Well no I didn't, but I can dream can't I?  Today I was thinking, and I
believe that it is possible to make any finite polyhedron out of
tetrahedrons.  Maybe even only one per vertex.  It's even easy to split
a tetrahedron into two tetrahedrons.  So I was thinking about making a
polyhedra modeler that treated shapes as unions of tetrahedrons.  Maybe
I will have it working 6 months from now.  Well if I can motivate myself
that well.  
 
> As of your concerns of starting a flame war, I doubt it :) It's just
> that if someone looks for examples of code, macros, scenes etc., one
> usually looks into the scene-files groups. In general, the chances of
> finding something (not just a post) are greater if it's in the right
> place (this from the guy whose view of order is "Throw everything
> here, this way the more recent stuff requires less digging." :) )
> Anyway, just a thought.

My reasoning for putting it here is that tetrahedra are fairly simple
shapes, and I thought it was more of an intellectual thing.  Plus I
hardly ever get any replies when I post in scene-files groups.  I
thought it would get looked at here.  
 
> Peter Popov ICQ : 15002700
> Personal e-mail : pet### [at] vipbg
> TAG      e-mail : pet### [at] tagpovrayorg


-- 
Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

Warp wrote:
> 
> Dan Johnson <zap### [at] hotmailcom> wrote:
> > Anyone know if this approach
> > is actually faster than plane intersections?
> 
>   There was once a long thread in some group about the most efficient way
> of making a box with all six sides textured differently.
>   Several approaches were made and their rendering times measured. For
> example it was done with the intersection of six planes, the union of
> six 2-dimensional boxes, six polygons and a mesh. (Also using a single
> box with a clever pattern was suggested, but that's irrelevant in this case).
>   Perhaps a bit surprisingly, with such a low triangle count the mesh was
> not the fastest option. I don't remember which one was, but it might have
> been the union of polygons. (The problem with it is that it's not usable
> in CSG.)

Interesting..
 
>   In your case the intersection of planes might be just ok. You simply have
> to manually bound the tetrahedron eg. with a sphere.

If my thinking is correct that can be done such that each vertex is
exactly on the surface of the sphere.  

>   You might also try using a mesh (with inside_vector you can make it
> CSG'able). If you don't need to use the tetrahedron in CSG, you might want
> to try a union of four triangles, or even polygons, though I doubt it will
> be faster than the union of triangles.
>   I think that with such a low triangle count, the union of triangles may
> be faster than a mesh.

Of course a union of triangles is so much easier that what I did.  I
used more than one in the process of debugging my code.  CSG is
important for pretty much everything I ever do.
 
> --
> #macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
> N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
> N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -


-- 
Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

In article <3df1b593@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   In your case the intersection of planes might be just ok. You simply have
> to manually bound the tetrahedron eg. with a sphere.
>   You might also try using a mesh (with inside_vector you can make it
> CSG'able). If you don't need to use the tetrahedron in CSG, you might want
> to try a union of four triangles, or even polygons, though I doubt it will
> be faster than the union of triangles.
>   I think that with such a low triangle count, the union of triangles may
> be faster than a mesh.

Did anyone try using "heirarchy off"? With 4 triangles arranged like 
that, it has to be more overhead than benefit.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <3DF1C3CD.A9BA456F@hotmail.com>,
 Dan Johnson <zap### [at] hotmailcom> wrote:

> If my thinking is correct that can be done such that each vertex is
> exactly on the surface of the sphere. 

You are correct (assuming no uneven scaling or shearing), but I think a 
box would be a better choice. A sphere doesn't fit a tetrahedron that 
closely, a box isn't much if at all better but is faster to test.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

Christopher James Huff <chr### [at] maccom> wrote:
> You are correct (assuming no uneven scaling or shearing), but I think a 
> box would be a better choice. A sphere doesn't fit a tetrahedron that 
> closely, a box isn't much if at all better but is faster to test.

  Have you actually made the math, which shape "wastes" more space when
bounding (optimally) a regular tetrahedron ("regular" meaning all sides
have the same length), the sphere or the box?
  I wouldn't be so sure that the optimal box is smaller than the optimal
sphere ("smaller" meaning that its volume is smaller), although I can't
be sure of the contrary either.

  Also I think that a ray-sphere intersection is faster than a ray-box
intersection, so the sphere is in that sense a better bounding object.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Warp wrote:
> 
> Christopher James Huff <chr### [at] maccom> wrote:
> > You are correct (assuming no uneven scaling or shearing), but I think a
> > box would be a better choice. A sphere doesn't fit a tetrahedron that
> > closely, a box isn't much if at all better but is faster to test.
> 
>   Have you actually made the math, which shape "wastes" more space when
> bounding (optimally) a regular tetrahedron ("regular" meaning all sides
> have the same length), the sphere or the box?
>   I wouldn't be so sure that the optimal box is smaller than the optimal
> sphere ("smaller" meaning that its volume is smaller), although I can't
> be sure of the contrary either.

In my example one of the tetrahedrons is regular, and exactly fits
inside a 2X2X2 box.  Both exactly fit in a sphere with radius sqrt(3).  

object{Tet_prism(<1,1,1>,<-1,1,-1>,<1,-1,-1>,<-1,-1,1>) pigment{Green}
finish{Dull}}
box{-1,1 pigment{color rgbft<1,0,0,0,.6>}finish{Dull}}
sphere{0,pow(3,(1/2)) pigment{color rgbft<0,0,1,0,.8>}finish{Dull}}
sphere {<1,1,1>,.1 pigment{Yellow}}
sphere {<-1,1,-1>,.1 pigment{Yellow}}
sphere {<1,-1,-1>,.1 pigment{Yellow}}
sphere {<-1,-1,1>,.1 pigment{Yellow}}

Don't know about using a box to bound an irregular tetrahedron.  Sounds
relatively tricky.  

>   Also I think that a ray-sphere intersection is faster than a ray-box
> intersection, so the sphere is in that sense a better bounding object.
> 
> --
> #macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
> N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
> N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -


-- 
Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

In article <3df273e6@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   Have you actually made the math, which shape "wastes" more space when
> bounding (optimally) a regular tetrahedron ("regular" meaning all sides
> have the same length), the sphere or the box?

Ok, for a tetrahedron with these corners:
<-1, 1,-1>
< 1, 1, 1>
<-1,-1, 1>
< 1,-1,-1>
(regular tetrahedron, every point equidistant from the other three)
The radius of a perfect bounding sphere is sqrt(3). Volume is pi*3/4*r^3 
= 21.763 cubic units. The volume of the perfect axis-aligned bounding 
box is 8 cubic units, though it will increase for other orientations (I 
think the worst case makes for a bounding box sqrt(8)xsqrt(8)x2, 16 
cubic units.

I think the "average visible area" would make a better measurement than 
volume, though much harder to compute. And the difference is bigger than 
I expected, but I can't find anything wrong with my math, please 
re-check it.


>   Also I think that a ray-sphere intersection is faster than a ray-box
> intersection, so the sphere is in that sense a better bounding object.

Hmm...the bounding box calculation is very well optimized, I think it 
only requires 3 intersections with axis-aligned planes and some code for 
clipping that. A sphere is fast, but I think a bounding box is faster. 
However, I'm not too sure how the bounded_by keyword fits in with the 
bounding box heirarchy...it looks like a bounding box is always used, 
which bounds the bounding shapes (multiple?), which bound the object. 
Much of the bounding code seems to be very per-object...it's pretty 
disorganized, and probably not as fast as it could be.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <3DF2A029.A55D1FD2@hotmail.com>,
 Dan Johnson <zap### [at] hotmailcom> wrote:

> Don't know about using a box to bound an irregular tetrahedron.  Sounds
> relatively tricky.  

Finding an optimal axis-aligned bounding box is very easy, just find the 
min and max extents of all four points. A sphere or an aligned bounding 
box would be trickier.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

"Dan Johnson" <zap### [at] hotmailcom> wrote in message
news:3DF1C3CD.A9BA456F@hotmail.com...
> Warp wrote:
> >
> > Dan Johnson <zap### [at] hotmailcom> wrote:
> > > Anyone know if this approach
> > > is actually faster than plane intersections?
> >
> >   There was once a long thread in some group about the most efficient
way
> > of making a box with all six sides textured differently.
> >   Several approaches were made and their rendering times measured. For
> > example it was done with the intersection of six planes, the union of
> > six 2-dimensional boxes, six polygons and a mesh. (Also using a single
> > box with a clever pattern was suggested, but that's irrelevant in this
case).
> >   Perhaps a bit surprisingly, with such a low triangle count the mesh
was
> > not the fastest option. I don't remember which one was, but it might
have
> > been the union of polygons. (The problem with it is that it's not usable
> > in CSG.)
>
> Interesting..
>
> >   In your case the intersection of planes might be just ok. You simply
have
> > to manually bound the tetrahedron eg. with a sphere.
>
> If my thinking is correct that can be done such that each vertex is
> exactly on the surface of the sphere.

I bet the Graphics Gems books have code that will allow you to determine a
sphere tangential to 4 points in 3-space.  The code for those books can be
found on-line.

Post a reply to this message

> all that testing though.  It sounded like a lot of work.  I thought
> perhaps someone might have immediate need for millions of tetrahedrons.
> Well no I didn't, but I can dream can't I?  Today I was thinking, and I

Actually, I was considering rendering a D&D game with a 17,000,000th level
wizard casting Magic Missile...  ;-)

Rick

Post a reply to this message

Rick Gutleber wrote:
...
> > >   In your case the intersection of planes might be just ok. You simply
> have
> > > to manually bound the tetrahedron eg. with a sphere.
> >
> > If my thinking is correct that can be done such that each vertex is
> > exactly on the surface of the sphere.
> 
> I bet the Graphics Gems books have code that will allow you to determine a
> sphere tangential to 4 points in 3-space.  The code for those books can be
> found on-line.

I once made a macro for POV that finds such a sphere,
but I'm afraid that a sphere that tuches all the 4
vertexes will not be the optimal solution in all cases.

In fact it will sometimes be a very non-optimal sphere to
choose for bounding of tetrahedrons.

But if anyone is interested in having a look at my macro,
then it can be found here:

http://news.povray.org/povray.general/17701/?mtop=114652&moff=22
news://news.povray.org/3B82F267.36412849%40hotmail.com


Tor Olav

Post a reply to this message

On Wed, 11 Dec 2002 11:45:10 -0500, "Rick Gutleber" <ric### [at] hiscom>
wrote:

>I bet the Graphics Gems books have code that will allow you to determine a
>sphere tangential to 4 points in 3-space.  The code for those books can be
>found on-line.

There sure is, but keep in mind that the circumscribed sphere is
usually not the smallest sphere containing four points.


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

Rick Gutleber wrote:

> Actually, I was considering rendering a D&D game with a 17,000,000th level
> wizard casting Magic Missile...  ;-)
> 
> Rick

I didn't know that there have been enough hours since the game was
invented for anyone to get to the 17 millionth level.  Must be quite
some D&D player.  Or is this a theoretical character, or a non player
character.  I once encountered a game bug that gave me perfect stats. 
Well except for luck.  My luck in the game was so awful that people in
proximity to my character would do things like critically miss, and kill
themselves.  I had an aura of bad luck.  Or was that a different game?
-- 
Dan Johnson 

http://www.geocities.com/zapob

Post a reply to this message

If the points are _tangential_ to the sphere, wouldn't there only be one
solution?

"Peter Popov" <pet### [at] vipbg> wrote in message
news:6ldgvu8m3haqih3b2cud5narcqn8p82pvi@4ax.com...
> On Wed, 11 Dec 2002 11:45:10 -0500, "Rick Gutleber" <ric### [at] hiscom>
> wrote:
>
> >I bet the Graphics Gems books have code that will allow you to determine
a
> >sphere tangential to 4 points in 3-space.  The code for those books can
be
> >found on-line.
>
> There sure is, but keep in mind that the circumscribed sphere is
> usually not the smallest sphere containing four points.
>
>
> Peter Popov ICQ : 15002700
> Personal e-mail : pet### [at] vipbg
> TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

Rick Gutleber wrote:
>If the points are _tangential_ to the sphere, wouldn't there only be one
>solution?

Rick,
I don't think one can say about points
that they can be tangential to anything.

You probably mean that they are on the
surface of the sphere.

If you have four points in 3D space that
are not coplanar (*), then yes; there
are only one specific sphere that have
them all on its surface. (And the macro
I mentioned in my other post finds that
very sphere.)

This sphere will, of coarse, enclose a
tetrahedron that has these four points
as its vertices.

But as Peter and I pointed out, this is
not always the most optimal sphere to
choose for bounding of such a tetrahedron.

It will in some cases be possible to
find spheres with smaller radii, that
encloses the tetrahedron.

And in these cases only 2 or 3 of the
4 points (vertices) will be on the surface
of the sphere. The other 2 or 1 will be
inside it.

The problem is now to find the bounding
sphere with the smallest radius.


(*) More precisely I mean:
vdot(p1 - p0, vcross(p2 - p0, p3 - p0)) != 0


Tor Olav


>"Peter Popov" <pet### [at] vipbg> wrote in message
>news:6ldgvu8m3haqih3b2cud5narcqn8p82pvi[at]4ax.com...
>> On Wed, 11 Dec 2002 11:45:10 -0500, "Rick Gutleber" <ric### [at] hiscom>
>> wrote:
>>
>> >I bet the Graphics Gems books have code that will allow you to determine
>a
>> >sphere tangential to 4 points in 3-space.  The code for those books can
>be
>> >found on-line.
>>
>> There sure is, but keep in mind that the circumscribed sphere is
>> usually not the smallest sphere containing four points.

Post a reply to this message

In article <3dfe6b6f@news.povray.org>, "Rick Gutleber" <ric### [at] hiscom> 
wrote:

> If the points are _tangential_ to the sphere, wouldn't there only be one
> solution?

He said that the circumscribed sphere (with all points on the sphere) 
wasn't the smallest sphere *containing* the points. In some cases, the 
smallest sphere touches only 2 or 3 points.
For a regular tetrahedron, the smallest sphere does touch all 4 points.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

Tor Olav Kristensen wrote:
> It will in some cases be possible to
> find spheres with smaller radii, that
> encloses the tetrahedron.
> 
> And in these cases only 2 or 3 of the
> 4 points (vertices) will be on the surface
> of the sphere. The other 2 or 1 will be
> inside it.
> 
> The problem is now to find the bounding
> sphere with the smallest radius.

I seem to remember the sequence goes something like this:

Find the two points furthest apart and set a sphere so that they are on 
the diameter. If both other points are inside the sphere you are done.

If one or two points are outside the sphere find the point furthest 
outside the sphere. Produce the sphere that has the circumcircle of the 
three points as its great-circle. If the fourth point is inside this 
sphere you are done.

Otherwise find the sphere with all four points on the surface.

I think this is right ...

Mike Andrews.

Post a reply to this message

Michael Andrews wrote:
> 
> 
> I seem to remember the sequence goes something like this:
> 
> Find the two points furthest apart and set a sphere so that they are on
> the diameter. If both other points are inside the sphere you are done.
> 
> If one or two points are outside the sphere find the point furthest
> outside the sphere. Produce the sphere that has the circumcircle of the
> three points as its great-circle. If the fourth point is inside this
> sphere you are done.
> 
> Otherwise find the sphere with all four points on the surface.
> 
> I think this is right ...
> 
> Mike Andrews.

I think you are right.  I don't think it would be too hard to make a
macro to do that either.  Now I guess the next thing is to find the
smallest oriented bounding box, and see which one is smaller.  If one is
always smaller.  

-- 
Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

Dan Johnson wrote:

> 
> I think you are right.  I don't think it would be too hard to make a
> macro to do that either.  Now I guess the next thing is to find the
> smallest oriented bounding box, and see which one is smaller.  If one is
> always smaller.
> 

Do bounding boxes with sheer work?  If they do I think you can get even
closer.  Then you could define it as a cube, and a matrix.  I think that
in an ideal bounding box all vertices would also be vertices of the
inclosed tetrahedron.  

Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

Yes, of course, you're right about my wording.  I see what you are talking
about WRT to the smallest sphere, too.  Nearly coplanar points would produce
an enormous sphere if you only allowed the points to be on the surface of
the sphere.

"Tor Olav Kristensen" <tor### [at] hotmailcom> wrote in message
news:web.3dfe7e1187ba9bcf38149fba0@news.povray.org...
>
> Rick Gutleber wrote:
> >If the points are _tangential_ to the sphere, wouldn't there only be one
> >solution?
>
> Rick,
> I don't think one can say about points
> that they can be tangential to anything.
>
> You probably mean that they are on the
> surface of the sphere.
>
> If you have four points in 3D space that
> are not coplanar (*), then yes; there
> are only one specific sphere that have
> them all on its surface. (And the macro
> I mentioned in my other post finds that
> very sphere.)
>
> This sphere will, of coarse, enclose a
> tetrahedron that has these four points
> as its vertices.
>
> But as Peter and I pointed out, this is
> not always the most optimal sphere to
> choose for bounding of such a tetrahedron.
>
> It will in some cases be possible to
> find spheres with smaller radii, that
> encloses the tetrahedron.
>
> And in these cases only 2 or 3 of the
> 4 points (vertices) will be on the surface
> of the sphere. The other 2 or 1 will be
> inside it.
>
> The problem is now to find the bounding
> sphere with the smallest radius.
>
>
> (*) More precisely I mean:
> vdot(p1 - p0, vcross(p2 - p0, p3 - p0)) != 0
>
>
> Tor Olav
>
>
> >"Peter Popov" <pet### [at] vipbg> wrote in message
> >news:6ldgvu8m3haqih3b2cud5narcqn8p82pvi[at]4ax.com...
> >> On Wed, 11 Dec 2002 11:45:10 -0500, "Rick Gutleber" <ric### [at] hiscom>
> >> wrote:
> >>
> >> >I bet the Graphics Gems books have code that will allow you to
determine
> >a
> >> >sphere tangential to 4 points in 3-space.  The code for those books
can
> >be
> >> >found on-line.
> >>
> >> There sure is, but keep in mind that the circumscribed sphere is
> >> usually not the smallest sphere containing four points.
>
>

Post a reply to this message

In article <3DFF8126.37A7E1BE@hotmail.com>,
 Dan Johnson <zap### [at] hotmailcom> wrote:

> I think you are right.  I don't think it would be too hard to make a
> macro to do that either.  Now I guess the next thing is to find the
> smallest oriented bounding box, and see which one is smaller.  If one is
> always smaller.  

I am almost certain the box is always smaller. The optimal sphere 
bounding is a circumscribed sphere around a regular tetrahedron. The 
optimal box bounding of that tetrahedron would have each corner of the 
tetrahedron at a corner of the box, the least optimal (I think) would 
have two edges of the tetrahedron against opposing faces of the box, 
parallel to different axii (the best case, rotated 45 degrees around one 
axis).

For a regular tetrahedron with 1-unit edges, the best bounding sphere 
has a radius of sqrt(3)/sqrt(8) (~0.612), the best-case box a 
2/sqrt(8)-unit (~0.707) cube, the worst-case box a 1x1x2/sqrt(8) 
(1x1x~0.707) box. The sphere has a volume of 0.96 units^3, the cube 
0.353 units^3, and the box 0.707 units^3.

For optimal bounding of irregular tetrahedrons, both will be less 
efficient, but I think a box will always be better. Even if the 
tetrahedron is a thin rod along a diagonal of the box (the worst case), 
the sphere will have a larger volume (having a diameter about equal to 
the length of the diagonal of the box).

This is for axis-aligned boxes, if you use oriented boxes the bounding 
of a regular tetrahedron or some irregular tetrahedrons (those you can 
get by applying an affine transformation to a regular tetrahedron) is 
always the best case, for other tetrahedrons it still improves.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message