Haloed Line Algorithm

A wireframe model with and without a halo

The Haloed Line algorithm is a computer graphics technique used to represent wireframe models or general three-dimensional lines. The drawn lines are given a contour (“halo”) that hides the lines behind them. This increases the impression of space. If the width of the halo is chosen large enough, the effect arises that only the visible areas are displayed, as in a full occlusion calculation .

functionality

preparation

Geometry of a line with halo. Line B behind line A is obscured by the halo.

The Haloed Line algorithm consists of a preparation routine and a display routine. During preparation, the image is divided into a grid, the fineness of which depends on the average length of the line. In addition, the coefficients of the corresponding straight line equation are saved for each line . The grid cells through which it runs are determined for each line . In a list, the lines belonging to each cell are noted as and sorted by cell. ${\displaystyle z=ax+by+d}$ ${\displaystyle L_{i}}$ ${\displaystyle (C_{i,\,j},\,L_{i})}$

For each cell, continuous lines and pairs are checked to see whether they intersect. If this is the case, the point of intersection of the two lines is determined. In addition, it is determined which of the lines at the point of intersection has the smaller z coordinate, i.e. which is closer to the viewer. If closer, the angle between and is calculated. The results are saved as in a table . Once all the grid cells have been processed, the table is to order. Lines that are not entered in the table do not intersect other lines and are therefore always visible; they are also entered in the table. ${\displaystyle L_{i}}$ ${\displaystyle L_{j}}$ ${\displaystyle I}$ ${\displaystyle L_{i}}$ ${\displaystyle \theta }$ ${\displaystyle L_{i}}$ ${\displaystyle L_{j}}$ ${\displaystyle (L_{i},\,I,\,\theta )}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle L_{i}}$

display

To view the lines, go through the table entry by entry. For each entry are means and the points and is calculated at which the Halo stop on the line to the intersection point around and begin again. The pairs and are stored in a table . In addition, the pairs and are saved, where and are the endpoints of the line. ${\displaystyle T}$ ${\displaystyle H}$ ${\displaystyle \theta }$ ${\displaystyle I_{1}}$ ${\displaystyle I_{2}}$ ${\displaystyle (I_{1},-1)}$ ${\displaystyle (I_{2},+1)}$ ${\displaystyle S}$ ${\displaystyle (E_{1},+1)}$ ${\displaystyle (E_{2},-1)}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$

The resulting table is now sorted by and worked through one after the other, adding up the respective values ​​+1 or −1. If the sum is 1, the line will start to be drawn, if it reaches a value ≤0, the line will stop again. ${\displaystyle S}$ ${\displaystyle L_{i}}$

This procedure is ended when all entries in the table have been processed. ${\displaystyle T}$

literature

• Arthur Appel et al: The Haloed Line Effect for Hidden Line Elimination. ACM SIGGRAPH Computer Graphics 13, 2 (Aug. 1979): 151-157, ISSN  0097-8930
• David F. Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5