Roberts algorithm
The Roberts algorithm is a method from computer graphics for calculating the masking of polyhedra . It was published in 1963, making it the oldest algorithm for computation of masking.
principle
The Roberts algorithm processes polygon edges and assumes that these belong to convex polyhedra ( polygon meshes ). Concave bodies must first be divided into several convex ones.
The Roberts algorithm first uses backface culling to remove edges belonging to invisible polygons. Each remaining edge is then gradually tested against any polyhedron that might obscure it. Many edges can be eliminated trivially by simply comparing the coordinates.
When comparing an edge with a surface spanned by a polyhedron, three cases could arise:
- The start and end point are in front of the surface: in this case the edge is not covered.
- The start and end point are behind the surface: here the intersection points with all edges of the surface must first be determined in order to determine the part of the edge that lies within the surface and can therefore be deleted. If there are no intersections, the edge is either completely inside or completely outside the tested polyhedron.
- The start and end point are on different sides of the plane: here too, the intersection point at which the edge is divided must be determined. Proceed as described above with the resulting two partial edges.
The visibility test of the Roberts algorithm uses linear optimization to determine the values of the straight line equation for which the projection ray passes through a polyhedron and thus the corresponding point is hidden.
Since every edge is tested against every polyhedron, the Roberts algorithm theoretically has a quadratic running time . This and the greater interest in image-precise methods for computation of masking led to the Roberts algorithm receiving little attention. However, it can be improved by a prior sorting according to the z -coordinates and simple bounding volume tests so that it has an almost linear running time.
literature
- Lawrence G. Roberts : Machine Perception Of Three-Dimensional Solids. Lincoln Laboratory, TR 315, MIT, Cambridge 1963 ( online )
- David F. Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5
Individual evidence
- ^ Rogers: Procedural Elements for Computer Graphics, p. 303