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