Test for hidden points with triangular subdivision Algorithm 3.22

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)