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