Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Hidden-line removal
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Problem of finding obscured edges in a wire-frame 3D model}} [[File:Obj lineremoval.png|thumb|200px|A wire-frame image using hidden-line removal]] In [[3D computer graphics]], [[Solid geometry|solid objects]] are usually modeled by [[polyhedra]]. A face of a polyhedron is a planar [[polygon]] bounded by straight line segments, called [[Edge (geometry)|edges]]. Curved surfaces are [[Computer representation of surfaces|usually approximated]] by a [[polygon mesh]]. Computer programs for [[Wire-frame model|line drawings]] of opaque objects must be able to decide which edges or which parts of the edges are [[Hidden line|hidden]] by an object itself or by other objects, so that those edges can be [[Clipping (computer graphics)|clipped]] during [[Rendering (computer graphics)|rendering]]. This problem is known as '''hidden-line removal'''. The first known solution to the hidden-line problem was devised by L. G. Roberts<ref>L. G. Roberts. ''[https://dspace.mit.edu/bitstream/handle/1721.1/11589/33959125-MIT.pdf?sequence=2 Machine perception of three-dimensional solids]''. PhD thesis, Massachusetts Institute of Technology, 1963.</ref> in 1963. However, it severely restricts the model: it requires that all objects be [[Convex set|convex]]. [[Ruth A. Weiss]] of Bell Labs documented her 1964 solution to this problem in a 1965 paper.<ref>Ruth A. Weiss ''[https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/bevision-weiss.pdf BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces ]''</ref> In 1966 [[Ivan E. Sutherland]] listed 10 unsolved problems in computer graphics.<ref>I. E. Sutherland. Ten unsolved problems in computer graphics. ''Datamation'', 12(5):22β27, 1966.</ref> Problem number seven was ''"hidden-line removal"''. In terms of [[computational complexity]], this problem was solved by Frank Devai in 1986.<ref name=Devai86>F. Devai. Quadratic bounds for hidden line elimination. In ''Proc. 2nd Annual Symp. on Computational Geometry'', SCG β86, pp. 269β275, New York, NY, USA, 1986.</ref> Models, e.g. in [[computer-aided design]], can have thousands or millions of edges. Therefore, a computational-complexity approach expressing resource requirements (such as time and memory) as the function of problem sizes is crucial. Time requirements are particularly important in interactive systems. Problem sizes for hidden-line removal are the total number {{mvar|n}} of the edges of the model and the total number {{mvar|v}} of the visible segments of the edges. Visibility can change at the intersection points of the images of the edges. Let {{mvar|k}} denote the total number of the intersection points of the images of the edges. Both {{math|1=''k'' = Ξ(''n''<sup>2</sup>)}} and {{math|1=''v'' = Ξ(''n''<sup>2</sup>)}} in the worst case,<ref name=Devai86 /> but usually {{math|''v'' < ''k''}}.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)