A test whether two points on different surfaces are mutually hidden is whether a ray between them passes through an opaque zone on an intervening plane. The point of intersection of the ray and plane is given by algorithm 5.15. In the following procedures, local surface coordinates of the plane are used. The conversion from general coordinates is given by algorithm 5.11c. It is assumed that the data structure is of the form described in algorithm 3.21.

This procedure calculates the total transmittance of all planes lying along
on a line through a viewpoint (at distance 0) and another point (at distance
*r*). The points are hidden from each other if any of the intervening
surfaces is opaque. The procedure uses the subroutines given below to test
whether the sightline intersects an intervening plane within one of the
triangles on the plane. This is computationally expensive, so prior tests are
whether the intervening plane faces the viewpoint and whether the intersection
is within the overall *x,y,z* limits of triangles on the plane.

The boolean variable in% takes the value 1 if the test is to apply to planes
a distance between 0 and *r* from the viewpoint, or the value 0 if the test
is to apply to planes between distance *r* and infinity (ie. test for
external obstructions).

total transmittance=1

ip=1index to planewhile(total transmittance>0andip�number of planes)

if(either viewpoint or target point lies on plane)then gotolnext

if(angle between sightline and normal to plane

is greater than p/2)then gotolnext

(algorithm 5.13)q

(find distancefrom viewpoint to point of interception

of sightline and plane

algorithm 5.15)

if(in%=1andq>r)or(in%=0andq<r)thengotolnext

(find coordinatesxi,yi,ziof point of interception

algorithm 5.15)

if(xi,yi,zilies outside bounds of triangles on planeip)

then gotolnext

(convertxi,yi,zito local surface coordinatesu,von planeip)

it=(index of first triangle on planeip)

whileit>empty

(recall local surface coordinates of vertices of triangleit)

callTria(u,v,ua,va,ub,vb,uc,vc;hit%)

ifhit%then

(findtransmittance of triangle material)

total transmittance=total transmittance * transmittance of triangle material

it=empty

else

it=next triangle

end if

end while

lnext:

ip=ip+1

end while

This subroutine determines whether a given point (u,v) on a surface lies on a line segment from (u1,v1) to (u2,v2); it tests also whether a vertical line from (u,v) towards v at either infinity or minus infinity would intersect the segment.

**subroutine** Inte(u,v,u1,v1,u2,v2,down%; a%,b%)

*The subroutine returns boolean variable a%= true if the point lies
on the line segment or b%=true if the test line crosses the segment. If
down%=true then the test line goes to -_ otherwise +_.*

ifu1=u2thena%=(u=u1)

and((v�v1andv�v2)or(v�v2andv�v1))point lies on vertical line segmentb%=

false(u�u1

else

ifandu�u2)or(u�u2andu�u1)thena%=(v=v1+(v2-v1)*(u-u1)/(u2-u1))

point lies on sloping segment

if(u>u1andu<u2)or(u>u2andu<u1)then

ifdown%thenb%=(v>v1+(v2-v1)*(u-u1)/(u2-u1))

line intersects sloping segment

elseb%=(v<v1+(v2-v1)*(u-u1)/(u2-u1))

endif

endif

elsea%=

falsepoint not on segmentb%=

falseline misses segment

endif

return

A point lies within a triangle if any line drawn on the surface from that point towards infinity would cross only one triangle side.

This procedure uses the subroutine above to test each side in turn of a triangle with vertices (ua,va), (ub,vb) and (uc,vc). After each call the procedure tests whether the point lies on the line: if so, the point is considered inside; if not, the remaining sides are tested and the number of intersections counted.

The procedure may be adapted to test any convex polygon by simply repeating the subroutine call for all sides. With a polygon having one or more re-entrant angles, the test must be whether there is an odd number of intersections; if so, the point lies within the polygon.

**subroutine **Tria(u,v,ua,va,ub,vb,uc,vc;hit%)*boolean variable
hit%= true if the point lies within the triangle*

total=0

count of intersectionsdown%=(u=ua

andv<va)or(u=ubandv<vb)or(u=ucandv<vc)test whether point lies directly below vertex

callInte(u,v,ua,va,ub,vb,down%; a%,b%)side a-b

ifa%thenhit%=a%

else

ifb%thentotal=total+1

callInte(u,v,ub,vb,uc,vc,down%; a%,b%)side b-c

ifa%thenhit%=a%

else

ifb%thentotal=total+1

callInte(u,v,uc,vc,ua,va,down%; a%,b%)side c-a

ifa%thenhit%=a%

else

ifb%thentotal=total+1

hit%=(total=1)

end if

end if

end if

return

*Source*- The subroutines are derived from procedures described by Rogers(1)

References - 1. Rogers D F
*Procedural elements for computer graphics*(New York: McGraw-Hill) (1985)

Go Back to Subtask C Contents