World Library  
Flag as Inappropriate
Email this Article

Warnock algorithm

Article Id: WHEBN0008545410
Reproduction Date:

Title: Warnock algorithm  
Author: World Heritage Encyclopedia
Language: English
Subject: Hidden surface determination, List of algorithms
Collection: Computer Graphics Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Warnock algorithm

Polygon visibility in a given viewport: a) polygon fills the viewport, b) polygon partially and c) completely visible, d) polygon invisible.
Four steps of a viewport divisions for a simple scene

The Warnock algorithm is a hidden surface algorithm invented by John Warnock that is typically used in the field of computer graphics.[1] 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.[2]

This is a divide and conquer algorithm with run-time of O(np), 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 (then the polygon or its part is drawn in appropriate part of a viewport) or a viewport that is one pixel in size (then that pixel gets a color of the polygon closest to the observer). 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.

References

  1. ^  , 32 pages
    Also: http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD753671&Location=U2&doc=GetTRDoc.pdf
  2. ^ Daintith, John; Wright, Edmund (2009). Oxford Dictionary of Computing. Oxford University Press.  , 608 pages

External links

  • A summary of the Warnock Algorithm


This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.