Doom's use of the BSP node.

current idea.md

My current interpretation is as follows: A node represents the splitting pane is centered at (x,y) with a direction given by dx,dy.

Remember the cross product? u x v = (u1, u2, u3) X (v1, v2, v3) = (u2v3 - u3v2, u3v1 - u1v3, u1v2 - u2v1)

Node, splittin pane's vector is (dx, dy, 0) what direction does the viewer look at the line ? (viewx - x, viewy - y, 0) = (dvx, dvy, 0) so the cross product would be:

(viewy0 - 0dvy, 0dvx - viewx0, dxdvy - dydvx) = (0, 0, dxdvy - dydvx) which is similar to the below snippet (grep left/right):

int
R_PointOnSide
( fixed_t	x,
  fixed_t	y,
  node_t*	node )
{
    fixed_t	dx;
    fixed_t	dy;
    fixed_t	left;
    fixed_t	right;
	
    if (!node->dx)
    {
	if (x <= node->x)
	    return node->dy > 0;
	
	return node->dy < 0;
    }
    if (!node->dy)
    {
	if (y <= node->y)
	    return node->dx < 0;
	
	return node->dx > 0;
    }
	
    dx = (x - node->x);
    dy = (y - node->y);
	
    // Try to quickly decide by looking at sign bits.
    if ( (node->dy ^ node->dx ^ dx ^ dy)&0x80000000 )
    {
	if  ( (node->dy ^ dx) & 0x80000000 )
	{
	    // (left is negative)
	    return 1;
	}
	return 0;
    }

    left = FixedMul ( node->dy>>FRACBITS , dx );
    right = FixedMul ( dy , node->dx>>FRACBITS );
	
    if (right < left)
    {
	// front side
	return 0;
    }
    // back side
    return 1;			
}

So that would be why the 2 different delta's are multiplied.. to get the z-component of the cross product. above right-left > 0 would give a similar answer to the cross product.

doom_bsp_node_example.h

//bsp's described as folllows
typedef struct
{
    // Partition line.
    fixed_t	x;
    fixed_t	y;
    fixed_t	dx;
    fixed_t	dy;

    // Bounding box for each child.
    fixed_t	bbox[2][4];

    // If NF_SUBSECTOR its a subsector.
    unsigned short children[2];
    
} node_t;