David Wallace <dar### [at] earthlinknet> wrote:
> 1. The surface is convex at all vertices.

  Unfortunately triangles meshes seldom are (purely convex surfaces are
usually rather boring and useless).

-- 
#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:
>...
>   And I can believe that there could be a shortcut to see if a line
> intersects a triangle. It's just too complicated for me to think being
> this tired (and lazy) :)

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)


Tor Olav


// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Copyright 2002 by Tor Olav Kristensen
// Email: tor### [at] hotmailcom
// http://www.crosswinds.net/~tok/povray
// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

#version 3.5;
#include "colors.inc"

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Intersection macros

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

  #local vRA = pA - pRay;
  #local vRB = pB - pRay;
  #local vRC = pC - pRay;
  #local vABN = vcross(vRA, vRB);
  #local vBCN = vcross(vRB, vRC);
  #local vCAN = vcross(vRC, vRA);
  #local STP = vdot(vABN, vRC);
  #if (STP = 0)
    #debug "Macro RayIntersectsTriangle: "
    #debug "Degenerate triangle or "
    #debug "origin of ray lies in same plane as triangle\n"
    #local Intersect = false;
  #else
    #local AB = vdot(vRay, vABN);
    #local BC = vdot(vRay, vBCN);
    #local CA = vdot(vRay, vCAN);
    #if (AB = 0 | BC = 0 | CA = 0)
      #local Intersect = true; // Intersection at one or two edges
    #else
      #if (STP > 0)
        #local Intersect = (AB > 0 & BC > 0 & CA > 0);
      #else
        #local Intersect = (AB < 0 & BC < 0 & CA < 0);
      #end // if
    #end // if
  #end // if

  Intersect
      
#end // macro RayIntersectsTriangle


#macro LinePlaneIntersection(pLine, vLine, pPlane, vPlane)

  (pLine + vLine*vdot(pPlane - pLine, vPlane)/vdot(vLine, vPlane))

#end // macro LinePlaneIntersection

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Set up and show triangle

#declare p0 = <1, 3, -2>;
#declare p1 = <2, -3, 3>;
#declare p2 = <-2, 1, -3>;

triangle {
  p0, p1, p2
  pigment { color rgbf <1, 1, 0, 0.2> }
}

union {
  sphere { p0, 0.03 }
  sphere { p1, 0.03 }
  sphere { p2, 0.03 }
  pigment { color Magenta*2 }
}

union {
  cylinder { p0, p1, 0.02 }
  cylinder { p1, p2, 0.02 }
  cylinder { p2, p0, 0.02 }
  pigment { color Cyan*2 }
}

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Shoot some random rays and highlight those that hits the triangle

#declare R = 4;
#declare S = seed(5);

#declare Cnt = 0;
#while (Cnt < 150)
  #declare pR = (<1, 1, 1> - 2*<rand(S), rand(S), rand(S)>)*R;
  #declare vR = (<1, 1, 1> - 2*<rand(S), rand(S), rand(S)>);
  #if (vlength(vR) > 0)
    sphere {
      pR, 0.04
      pigment { color Green*2 }
    }
    cylinder {
      pR, pR + 100*vnormalize(vR), 0.02
      pigment { color White }
    }
    #if (RayIntersectsTriangle(pR, vR, p0, p1, p2))
      #local vPlaneNormal = vcross(p1 - p0, p2 - p0);
      #local pIntersect = 
        LinePlaneIntersection(pR, vR, p0, vPlaneNormal);
      cylinder {
        pR, pIntersect, 0.021
        pigment { color White*4 }
      }
      sphere {
        pIntersect, 0.06
        pigment { color Red*2 }
      }
    #end // if
  #end // if  
  #declare Cnt = Cnt + 1;
#end // while

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

background { color Blue/2 }

light_source {
  <1, 1, -3>*100 color White
  shadowless
}

camera {
  location -10*z
  look_at <0, 0, 0>
}

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

Post a reply to this message

Ooops.
I think that my "Intersection at one or two edges"
comment in the code I just posted is wrong.

See my new RayIntersectsTriangle() macro below.

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.


Tor Olav


Tor Olav Kristensen 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.
>...
> // ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
> // Copyright 2002 by Tor Olav Kristensen
> // Email: tor### [at] hotmailcom
> // http://www.crosswinds.net/~tok/povray
> // ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
> 
> #version 3.5;
> #include "colors.inc"
> 
> // ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
> // Intersection macros
> 
> #macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
> 
>   #local vRA = pA - pRay;
>   #local vRB = pB - pRay;
>   #local vRC = pC - pRay;
>   #local vABN = vcross(vRA, vRB);
>   #local vBCN = vcross(vRB, vRC);
>   #local vCAN = vcross(vRC, vRA);
>   #local STP = vdot(vABN, vRC);
>   #if (STP = 0)
>     #debug "Macro RayIntersectsTriangle: "
>     #debug "Degenerate triangle or "
>     #debug "origin of ray lies in same plane as triangle\n"
>     #local Intersect = false;
>   #else
>     #local AB = vdot(vRay, vABN);
>     #local BC = vdot(vRay, vBCN);
>     #local CA = vdot(vRay, vCAN);
>     #if (AB = 0 | BC = 0 | CA = 0)
>       #local Intersect = true; // Intersection at one or two edges
>     #else
>       #if (STP > 0)
>         #local Intersect = (AB > 0 & BC > 0 & CA > 0);
>       #else
>         #local Intersect = (AB < 0 & BC < 0 & CA < 0);
>       #end // if
>     #end // if
>   #end // if
> 
>   Intersect
> 
> #end // macro RayIntersectsTriangle

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

  #local vRA = pA - pRay;
  #local vRB = pB - pRay;
  #local vRC = pC - pRay;
  #local vABN = vcross(vRA, vRB);
  #local vBCN = vcross(vRB, vRC);
  #local vCAN = vcross(vRC, vRA);
  #local STP = vdot(vABN, vRC);
  #if (STP = 0)
    #debug "Macro RayIntersectsTriangle: "
    #debug "Degenerate triangle or "
    #debug "origin of ray lies in same plane as triangle\n"
    #local Intersect = false;
  #else
    #local AB = vdot(vRay, vABN);
    #local BC = vdot(vRay, vBCN);
    #local CA = vdot(vRay, vCAN);
    #if (STP > 0)
      #local Intersect = (AB >= 0 & BC >= 0 & CA >= 0);
    #else
      #local Intersect = (AB <= 0 & BC <= 0 & CA <= 0);
    #end // if
  #end // if

  Intersect
      
#end // macro RayIntersectsTriangle

Post a reply to this message

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).

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

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?

#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

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

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