Christopher James Huff <chr### [at] maccom> wrote:
> I haven't really been following this conversation, so I might be missing 
> something, but wouldn't this be a better way?

> #macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
>     #local iNorm = < 0, 0, 0>;
>     #local tmpTri = triangle {pA, pB, pC}
>     #local Scrap = trace(tmpTri, pRay, vRay, iNorm);
>     (iNorm.x != 0 | iNorm.y != 0 | iNorm.z != 0)
> #end

  The whole idea was to code that trace() function in C++.
  Even though POV-Ray has a trace() function, C++ doesn't. :P

-- 
#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

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

> Christopher James Huff <chr### [at] maccom> wrote:
> > I haven't really been following this conversation, so I might be missing 
> > something, but wouldn't this be a better way?
> 
> > #macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
> >     #local iNorm = < 0, 0, 0>;
> >     #local tmpTri = triangle {pA, pB, pC}
> >     #local Scrap = trace(tmpTri, pRay, vRay, iNorm);
> >     (iNorm.x != 0 | iNorm.y != 0 | iNorm.z != 0)
> > #end
> 
>   The whole idea was to code that trace() function in C++.

Ah...maybe these links would be of help:

http://www.2tothex.com/raytracing/
http://www.faqs.org/faqs/graphics/algorithms-faq/
http://www.cfxweb.net/files/Sources/Effects/Raytrace/
http://www.3dspot.com/raytracing.html

-- 
Christopher James Huff <chr### [at] maccom>
POV-Ray TAG e-mail: chr### [at] tagpovrayorg
TAG web site: http://tag.povray.org/

Post a reply to this message

Warp wrote:
> 
> Tor Olav Kristensen <tor### [at] hotmailcom> wrote:
> > If one does not want the edges and vertices to count as
> > part of the triangle, then just replace the >= and <=
> > operators below with > and < operators.
> 
>   My suggestion was that if such case is detected, then the whole ray is
> discarded and another ray is shot to another direction. The reason being
> that it's easier to do that than to figure out whether the intersection
> should be counted or not (there are cases where it has to be counted and
> cases where it must not be counted). Making the wrong decision can result
> in the wrong result (since the result of the test is a yes/no answer,
> giving the wrong answer is catastrophical).

Ok, I think I understand now.

Then I propose something similar to the approach
in the macro below. It detects several cases.

But it could even be refined further:

E.g. it could detect whether the ray hits an edge
or a vertice, even if the ray origin lies in the
same plane as the triangle.

And it could be improved so that it takes care of
round off problems (in programming languages other
than POV-Ray SDL).

Note that this macro has not been tested very
thoroughly, but for me it seems to work ok.


Tor Olav


#macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)

  #local DegenTri = -2;
  #local InPlane  = -1;
  #local Outside  =  0;
  #local Edge     =  1;
  #local Vertice  =  2;
  #local Inside   =  3;
  #local vRA = pA - pRay;
  #local vRB = pB - pRay;
  #local vRC = pC - pRay;
  #local vABN = vcross(vRA, vRB);
  #local STP = vdot(vABN, vRC);
  #if (STP = 0)
    #if (vlength(vcross(pB - pA, pC - pA)) = 0)
      #local State = DegenTri;
    #else
      #local State = InPlane;
    #end // if
  #else
    #local vBCN = vcross(vRB, vRC);
    #local vCAN = vcross(vRC, vRA);
    #local AB = vdot(vRay, vABN);
    #local BC = vdot(vRay, vBCN);
    #local CA = vdot(vRay, vCAN);
    #if (STP > 0)
      #if (AB < 0 | BC < 0 | CA < 0)
        #local State = Outside;
      #else
        #if (AB > 0 & BC > 0 & CA > 0)
          #local State = Inside;
        #else
          #if ((CA = 0 & AB = 0) | (AB = 0 & BC = 0) | (BC = 0 & CA = 0))
            #local State = Vertice;
          #else
            #local State = Edge;
          #end // if
        #end // if
      #end // if
    #else
      #if (AB > 0 | BC > 0 | CA > 0)
        #local State = Outside;
      #else
        #if (AB < 0 & BC < 0 & CA < 0)
          #local State = Inside;
        #else
          #if ((CA = 0 & AB = 0) | (AB = 0 & BC = 0) | (BC = 0 & CA = 0))
            #local State = Vertice;
          #else
            #local State = Edge;
          #end // if
        #end // if
      #end // if
    #end // if
  #end // if
  #debug "Macro RayIntersectsTriangle: "
  #switch (State)
    #case (DegenTri)
      #debug "Degenerate triangle"
    #break
    #case (InPlane)
      #debug "Ray origin lies in triangle plane"
    #break
    #case (Outside)
      #debug "Ray does not hit triangle"
    #break
    #case (Edge)
      #debug "Ray hits an edge of triangle"
    #break
    #case (Vertice)
      #debug "Ray hits a vertice of triangle"
    #break
    #case (Inside)
      #debug "Ray hits inside triangle"
    #break
  #end // switch
  #debug "\n"

  State

#end // macro RayIntersectsTriangle

Post a reply to this message

Christopher James Huff wrote:
> 
> In article <3D2389CA.9E4E78B2@hotmail.com>,
>  Tor Olav Kristensen <tor### [at] hotmailcom> wrote:
> 
> > I think that my RayIntersectsTriangle() macro in the code below
> > provides such a shortcut (*), but I'm not sure yet if it is optimal.
> >
> > (*) Not really for lines, but for rays (which has a defined direction)
> 
> I haven't really been following this conversation, so I might be missing
> something, but wouldn't this be a better way?

Warp explained why I did not make it that way.

I just chose a programming language that many
in these groups know.  ;)

The algorithms I suggested should be quite
easy to see, even if they are provided as POV
scripts.

As a bonus POV-Ray makes it easy to illustrate
the workings of such graphic algorithms.
(Because most people that read these groups
have a common "platform": POV-Ray.)


Tor Olav

Post a reply to this message

"Jim Kress" <nos### [at] kressworkscom> wrote in message
news:3d20b74c$1@news.povray.org...
> > 1. The surface is convex at all vertices.
>
> What exactly do you mean by this?  For example, if you have a kidney
shaped
> surface, which is a closed surface but curves in and out, does that meet
> your assumption?
>
> Jim
>
That's why I suggested a "local" center to base the assumption on (the
centroid of the subset of points within a certain radius of the target
triangle).  Problematic surfaces look more like 3D crescents, the result of
CSG difference of nearly identical spheres, usually separated by a small
translation of the center.  The "interior" surface, created by the cutaway
sphere, would be the real issue.  Kidneys have but a small region that might
be similarly affected.

A better approach is to weight the contribution of the points by their
distance from the centroid of the triangle.  Say you have a list of the
object's vertices V[i] and a triangle <P1, P2, P3> or <I1, I2, I3> if you
are using indexed triangles via mesh2.  First you calculate the triangle
centroid:

#local oTri = (P1+P2+P3)/3; // (V[I1], V[I2], V[I3])/3 if indexed

Then you start adding the weights:

#local wgtTotal = 0;
#local pntTotal = <0,0,0>;
#local i = 0;
#while (i<numPoints)
    #local pntDist = vlength(V[i]-oTri);
    #if (pntDist<wgtThresh)
        #local wgtPoint = pow(pntDist, -wgtPower);
        #local wgtTotal = wgtTotal + wgtPoint;
        #local pntTotal = pntTotal + V[i]*wgtPoint;
    #end
    #local i = i + 1;
#end

#local oLocal = pntTotal/wgtTotal;

Now you can use this local center to check your triangle:

#local triNorm = vcross(P3-P1, P2-P1); // Again, replace Pn with V[In] if
using indexes
#local triDir = vdot(triNorm. P1-oLocal);
#if (triDir>0) true #else false #end

This is a rather computationally expensive process that scales poorly with
object size/vertex density.

Post a reply to this message

On Sat, 29 Jun 2002 23:34:06 -0400, Jim Kress wrote:
>> that comes to mind is: Shoot a ray from the surface of the triangle to one
>> side of it (it doesn't really matter which direction), and if hits an even
>> amount of other triangles (also 0 is even), that side is is outside, else
>> it's inside.
> 
> Got any suggestions how I would do this?  I've looked through the Internet
> and have not been able to find an algorithum (or code) that would show me
> how this is done.

There's an easier way.  Find the vertex V that is closest to an arbitrary
faraway point P ("faraway" is ill-defined here, but 100x the size of the 
bounding box away from any point of the bounding box is probably far enough.)  
Now, find a triangles that abuts the vertex V and is closer to P than the 
other triangles that abut V (put all the other vertices W0..Wn of all the 
other triangles in a pile, pick the closest one of those and call it W.  Now,
you've narrowed it down to two triangles.  Whichever of those has the closest
third vertex is your triangle.)  If the dot-product of that triangle's normal 
with the vector P-V is positive, it's oriented correctly and you can use it 
to fix the orientation of the rest of the triangles as Warp described.  
Otherwise, it's oriented incorrectly and you just need to flip it.

This definitely works in 2d with line segments instead of triangles; I haven't 
checked it in 3d.

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

On 10 Jul 2002 17:52:36 -0400, Ron Parker wrote:
> other triangles that abut V (put all the other vertices W0..Wn of all the 
> other triangles in a pile, pick the closest one of those and call it W.  Now,
> you've narrowed it down to two triangles.  Whichever of those has the closest
> third vertex is your triangle.)  If the dot-product of that triangle's normal 

Ron, you ignorant git, you got it all wrong.  The closest triangle is harder
to find than that; you have to scale all the vectors W0-Wn so they fall on a 
unit (hemi)sphere centered on V first, then do the above.


--
#macro R(L P)sphere{L __}cylinder{L P __}#end#macro P(_1)union{R(z+_ z)R(-z _-z)
R(_-z*3_+z)torus{1__ clipped_by{plane{_ 0}}}translate z+_1}#end#macro S(_)9-(_1-
_)*(_1-_)#end#macro Z(_1 _ __)union{P(_)P(-_)R(y-z-1_)translate.1*_1-y*8pigment{
rgb<S(7)S(5)S(3)>}}#if(_1)Z(_1-__,_,__)#end#end Z(10x*-2,.2)camera{rotate x*90}

Post a reply to this message

Thanks Ron.

Got another question for you.  In a triangle mesh, only the x,y,z
coordinates of the verticies are given for each triangle.  How does povray
establish the numbering of the associated verticies?  I need to find a good
way to asign numerical indicies to verticies so I can specify a triangle by
giving its vertex numbers (VRML requires this information).  Any suggestions
how I can do this?

Thanks.

JIm

Post a reply to this message

On Fri, 12 Jul 2002 13:36:46 -0400, Jim Kress wrote:
> Thanks Ron.
> 
> Got another question for you.  In a triangle mesh, only the x,y,z
> coordinates of the verticies are given for each triangle.  How does povray
> establish the numbering of the associated verticies?  I need to find a good
> way to asign numerical indicies to verticies so I can specify a triangle by
> giving its vertex numbers (VRML requires this information).  Any suggestions
> how I can do this?

Well, you could start with a mesh2, which is already in a format like that.
Alternatively, just throw all the vertices in a container that can only 
contain one copy of each data item you put in, and then iterate over its 
members and assign a number to each member.

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
> Well, you could start with a mesh2, which is already in a format like that.
> Alternatively, just throw all the vertices in a container that can only 
> contain one copy of each data item you put in, and then iterate over its 
> members and assign a number to each member.

  Btw, doesn't POV-Ray internally use a hash table for this purpose (ie.
a container which can contain only unique elements)? I seem to remember
something like that when I was looking at the code (for the tesselation patch).

  The other (and perhaps more natural) alternative is to use a binary tree
(which should be weighted if average speed of all cases should be the
maximum). However, a binary tree usually takes more memory than a hash table
solution and it's not usually faster (if the hash table is done with expertise,
it's often faster than a binary tree).
  Neither of these containers are trivial to implement (unless an unweighted
binary tree is enough for your purposes, in which case it's the simplest to
implement).

-- 
#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