Subdivision Algorithm in Computer Graphics
Partially visible and invisible lines which can’t be identified by checking and operating endpoint codes are subdivided into two equal segments by finding the midpoint. Each half is then separately considered and tested with endpoint codes for immediate identification of a totally visible and invisible state.
Segments that can’t be identified even then are further subdivided at the midpoint and each subdivision is subsequently tested. This bisection and testing procedure is continued until the intersection with a window edge is found with some specified accuracy.