Journal of Systems and Software 82 (3): 422-434 (2009)

PAT: A Pattern Classification Approach to Automatic Reference Oracles
for the Testing of Mesh Simplification Programs

W.K. Chan 2 , S.C. Cheung 3 , Jeffrey C.F. Ho 4 , and T.H. Tse 5

[paper from ScienceDirect | technical report TR-2007-10]


Graphics applications often need to manipulate numerous graphical objects stored as polygonal models. Mesh simplification is an approach to vary the levels of visual details as appropriate, thereby improving on the overall performance of the applications. Different mesh simplification algorithms may cater for different needs, producing diversified types of simplified polygonal model as a result. Testing mesh simplification implementations is essential to assure the quality of the graphics applications. However, it is very difficult to determine the oracles (or expected outcomes) of mesh simplification for the verification of test results.

A reference model is an implementation closely related to the program under test. Is it possible to use such reference models as pseudo-oracles for testing mesh simplification programs? If so, how effective are they?

This paper presents a fault-based pattern classification methodology, called PAT, to address the questions. In PAT, we train the C4.5 classifier using black-box features of samples from a reference model and its fault-based versions, in order to test samples from the subject program. We evaluate PAT using four implementations of mesh simplification algorithms as reference models applied to 44 open-source three-dimensional polygonal models. Empirical results reveal that the use of a reference model as a pseudo-oracle is effective for testing the implementations of resembling mesh simplification algorithms. However, the results also show a tradeoff: When compared with a simple reference model, the use of a resembling but sophisticated reference model is more effective and accurate but less robust.

Keywords: Test oracles, software testing, mesh simplification, graphics rendering, pattern classification reference models.

1. This research is supported in part by a CERG grant of the Research Grants Council of Hong Kong (project no. 714504), a grant of The University of Hong Kong, and a grant of City University of Hong Kong (project no. 7200079). A preliminary version of this paper was presented at the 30th Annual International Computer Software and Applications Conference (COMPSAC 2006).
2. (Corresponding author.)
City University of Hong Kong, Tat Chee Avenue, Hong Kong.
3. Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong.
4. University College London, Gower Street, London. Part of the research was done when Ho was with The University of Hong Kong, Pokfulam, Hong Kong.
5. The University of Hong Kong, Pokfulam, Hong Kong.


  Cumulative visitor count