Estimating the efficiency of a uniform-grid two-dimensional hashing algorithm for hidden line and surface removal in computer graphics (Q1107336)

A uniform-grid two-dimensional hashing algorithm is described and applied to hidden line and surface removal and some theoretical bounds on its efficiency are derived under the following assumptions: there exist constants \(d>0\), \(c\geq 1\) such that for any surface \(\Gamma\) there are circles \(B_{d/c}\) and \(B_{dc}\) in the plane of the surface (of radii d/c and dc, respectively) such that \[ B_{d/c}\subset \Gamma \subset B_{dc} \] (these assumptions are true for finite element models). The upper bounds of the efficiency of the derived algorithm are given for separate directions and averaged over all directions, and its optimality is proved. Practical details of using the algorithm are also discussed.