TR-IIS-03-009    PDF format

Abstract

This paper is concerned with designing an efficient algorithm for computing the intersection of two unstructured meshes.The algorithm uses a background quadtree of the first unstructured mesh and a self-avoiding walk (SAW) of the second unstructured mesh. Due to the neighboring relationships of consecutive triangles in the triangle sequence of a SAW, we can keep track of the location of each triangle in the second unstructured mesh by means of the background quadtree. This allows us to design a linear time algorithm for computing the mesh intersection. Experimental studies show that our efficient algorithm for computing the mesh intersection can save a lot of execution time in comparison with that needed by other naive algorithms. We also present two new SAW's. Using our first-in-first-out (FIFO) SAW can save an additional 5% of the execution time in comparison with that needed when using other SAW's. This is because our FIFO SAW employs better data locality, which is especially beneficial for the current hierarchical-memory computer architectures.

Keywords: advancing front method, background quadtree, first-in-first-out queue, last-in-first-out queue, mesh intersection, self-avoiding walk, unstructured mesh.