Test for hidden points with triangular subdivision Algorithm 3.22

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.

a. General procedure

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=1 index to plane
while (total transmittance>0 and ip�number of planes)
if (either viewpoint or target point lies on plane) then goto lnext
if (angle between sightline and normal to plane
is greater than p/2)
then goto lnext
(algorithm 5.13)
(find distance
q from viewpoint to point of interception
of sightline and plane
algorithm 5.15)

if (in%=1 and q>r) or (in%=0 and q<r) then goto lnext
(find coordinates xi,yi,zi of point of interception
algorithm 5.15)

if (xi,yi,zi lies outside bounds of triangles on plane ip)
then goto lnext
(convert xi,yi,zi to local surface coordinates u,v on plane ip)
it=(index of first triangle on plane ip)
while it>empty
(recall local surface coordinates of vertices of triangle it)
call Tria(u,v,ua,va,ub,vb,uc,vc;hit%)
if hit% then
(find transmittance 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

b. Test whether lines intersect

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 +_.

if u1=u2 then
a%=(u=u1) and ((v�v1 and v�v2) or (v�v2 and v�v1)) point lies on vertical line segment
b%=false
else
if
(u�u1 and u�u2) or (u�u2 and u�u1) then
a%=(v=v1+(v2-v1)*(u-u1)/(u2-u1)) point lies on sloping segment
if(u>u1 and u<u2) or (u>u2 and u<u1) then
if down% then
b%=(v>v1+(v2-v1)*(u-u1)/(u2-u1)) line intersects sloping segment
else
b%=(v<v1+(v2-v1)*(u-u1)/(u2-u1))
end if
end if
else
a%=false point not on segment
b%=false line misses segment
end if
return

c. Test whether a point lies within a triangle

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 intersections
down%=(u=ua andv<va) or(u=ub andv<vb) or (u=uc and v<vc) test whether point lies directly below vertex
call Inte(u,v,ua,va,ub,vb,down%; a%,b%) side a-b
if a% then
hit%=a%
else
if b% then total=total+1
call Inte(u,v,ub,vb,uc,vc,down%; a%,b%) side b-c
if a% then
hit%=a%
else
if b% then total=total+1
call Inte(u,v,uc,vc,ua,va,down%; a%,b%) side c-a
if a% then
hit%=a%
else
if b% then total=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