Edit Star

`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:
$ \begin{equation}
p'\cdot vertex_j = (p\cdot vertex_j - V)\times k + V
\end{equation}$ `Output:`

The outputs are a list of tree nodes printed in the back-to-front order
Testing a Binary Space Partitioning Algorithm with Metamorphic Testing https://doi.org/10.1145/1982185.1982502

`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:`

`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:`

`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:`

`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:`

`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:`