Binary Space Partitioning Algorithm

### Program Information

Name: Binary Space Partitioning Algorithm
Domain: Algorithm
Functionality: Deals with the surface visibility using the BSP tree named BSP tree visible surface (abbreviated as “BSP-treeVS”) algorithm.
Input: The inputs to the BSP-treeVS algorithm include a set of surfaces $(P)$ and the viewer’s coordinate in the space. We will use $V=(v_x ,v_y ,v_z)$ to denote the viewer’s coordinate. The subtree’s nodes on the same side are denoted as frontN($n$), while those on the opposite side are denoted as backN($n$). Equation 1 shows how to obtain each vertex of each resultant surface: $$$p'\cdot vertex_j = (p\cdot vertex_j - V)\times k + V$$$
Output: The outputs are a list of tree nodes printed in the back-to-front order

#### Reference

 Testing a Binary Space Partitioning Algorithm with Metamorphic Testing https://doi.org/10.1145/1982185.1982502

### MR Information

#### MR1------

Description:
Property: Given any list of surfaces as the source test input $(P)$,the follow-up test input $P'$ is generated by uniformly scaling all the surfaces of $P$ with the scaling factor $k = 2$. The source and follow-up tests are expected to produce the same output, provided that the viewer’s coordinate is unchanged (as a reminder, the viewer’s coordinate is hard-coded in the BSP-treeVS software, so this setting will definitely remain the same throughout our testing.).
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:

#### MR2------

Description:
Property: Randomly select one surface $p_q$ from the source test input $P$, such that $f_q(v_x,v_y,v_z)\neq 0$ (so the viewer is not a point in $p_q$). Construct the follow-up test input $P'$ by appending one additional surface $p'$ to $P$, where $p'$ is constructed from $p_q$ using Equation 1 and $k = 1.5$. The follow-up test is expected to output at least one section of $p'$ before all sections of $p_q$ .
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:

#### MR3------

Description:
Property: Given a source test input $P$, where no input surfaces contain $V$ as a point, construct the follow-up test input $P'$ by projecting each surface $p$ of $P$ to the other side of $V$ . The source and follow-up tests are expected to produce the same output.
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:

#### MR4------

Description:
Property: Use the Figure.1's $P$ as the source test input to run the software. Construct the follow-up test input ($P'$) by having $p_1$ as its first listed surface, followed by $P_{front}$ . This setting is to prune the backN($p_1$) in the BSP tree of the follow-up test. Consequently, the follow-up test output will exclude backN($p_1$), but retain the same output sequence for $p_1$ and frontN($p_1$ ).
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:

#### MR5------

Description:
Property: Use the above $P$ as the source test input to run the software. Construct the follow-up test input $P'$ by appending another surface $p'$ to $P$, where $p'$ is on the same side as $P$ back with respect to $p_1$ (so $p'$ or its sections will be part of backN($p_1$)). This setting is to increase the size of backN($p_1$) in the BSP tree of the follow-up test. The source and follow-up tests are expected to print the same nodes in the same order after $p_1$ (because the change made in $P'$ should not affect the frontN($p_1$)), whereas they may print different nodes in different orders before $p_1$.
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:
Insert title here