I am developing a primitive DOOM-style 3D engine for a low-end platform, and need help clipping walls that are partially outside the viewing area to being inside it before they are transformed to the screen. The points which are within the view are inside the area y > 0, x < y and x > -y.

\         / 
 \       / 
  \     / 
   \   /...x=-y
    \ / 
-----X-----> x
    /|\ 
   /#|#\ 
  /##|##\...x=y
 /###|###\ 
/####V#y##\ 

The area marked with the hashes (#) is where a valid point may lie. I'm having problems, but these are mainly checking whether a line falls inside the view at all. Clearly, if the y coordinates of both ends are less than 0, it's behind the camera. If both points fall inside the "hashed" area, no clipping is required and so the line is transformed as normal. If both points fall inside the same "zone" (of which there are 6), it's not visible. Beyond that, it gets a bit tricky. I have a byte containing two 3-bit values with one bit set for y < 0, one bit set for y > x and one bit set for y < -x. One 3-bit value is for the start of the line, one for the end. Clipping a point, which requires a number of multiplication and divisions, is a slow operation (the CPU has no hardware multiplication/division), so clipping any point that is out of bounds then checking if both ys are > 0 is not really an option. My current problem is more that sometimes a line gets clipped and jumps into the view, even though it was completely outside it beforehand. Am I barking up the wrong tree? How would you go about doing this?

1. y < 0 for both points -> reject
   2) y < x for both points -> reject
   2) y < -x for both points -> reject
   2) if one point has y<0, and the other point has y outside [-x,x], there is 2 possibilities
   
   • both end's x has the same sign -> reject
     
   • time for math: let P1 and P2 be your points,
     The line equation that goes from P1 to P2 is y = Ax + B. If B is > 0; it is obvious that the line is partly visible; if B is < 0, the line is not visible.
     If I'm not completely rusty, B = (P1.y * P2.x - P1.x * P2.y) / (P2.x - P1.x).
     If we make sure that P1.x < P2.x, we have to compare B with (P1.y * P2.x - P1.x * P2.y) (this is not really needed: if (P1.y * P2.x - P1.x * P2.y) and (P2.x - P1.x) have the same sign, then B >= 0).
     I know, this is still 2 muls. I'm not sure I'll be able to find a better solution [sad]

Regards,