Warnock algorithm
Encyclopedia
The Warnock algorithm is a hidden surface algorithm
invented by John Warnock
that is typically used in the field of computer graphics
.
It solves the problem of rendering a complicated image by recursive subdivision of a scene until areas are obtained that are trivial to compute. In other words, if the scene is simple enough to compute efficiently then it is rendered; otherwise it is divided into smaller parts which are likewise tested for simplicity.
This is a divide and conquer algorithm
with run-time
of
, where n is the number of polygons and p is the number of pixels in the viewport.
The inputs are a list of polygons and a viewport. The best case is that if the list of polygons is simple, then draw the polygons in the viewport. Simple is defined as one polygon or a viewport that is one pixel in size. The continuous step is to split the viewport into 4 equally sized quadrants and to recursively call the algorithm for each quadrant, with a polygon list modified such that it only contains polygons that are visible in that quadrant.
Hidden surface determination
In 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint...
invented by John Warnock
John Warnock
John Edward Warnock is an American computer scientist best known as the co-founder with Charles Geschke of Adobe Systems Inc., the graphics and publishing software company. Dr. Warnock was President of Adobe for his first two years and Chairman and CEO for his remaining sixteen years at the company...
that is typically used in the field of computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
.
It solves the problem of rendering a complicated image by recursive subdivision of a scene until areas are obtained that are trivial to compute. In other words, if the scene is simple enough to compute efficiently then it is rendered; otherwise it is divided into smaller parts which are likewise tested for simplicity.
This is a divide and conquer algorithm
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
with run-time
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
of
, where n is the number of polygons and p is the number of pixels in the viewport.The inputs are a list of polygons and a viewport. The best case is that if the list of polygons is simple, then draw the polygons in the viewport. Simple is defined as one polygon or a viewport that is one pixel in size. The continuous step is to split the viewport into 4 equally sized quadrants and to recursively call the algorithm for each quadrant, with a polygon list modified such that it only contains polygons that are visible in that quadrant.