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