Алгоритм Ньюелла

Два багатокутники, які не можуть бути впорядковані по глибині. Тому слід один з них розбити на два багатокутники.

Алгоритм Ньюелла — це процедура комп'ютерної 3D-графіки для ліквідації циклу з многокутників при сортування по глибині, який використовується для видалення невидимих ​​поверхонь[en]. Був запропонований в 1972 році Мартіном Ньюеллом, Діком Ньюеллом[en] і Т. Санча.

Основна ідея полягає у визначенні многокутників для сортування в залежності від відстані до глядача з тим, щоб потім, починаючи з найдальшого многокутника, намалювати їх усіх один за одним. При продовженні деталі будуть замінюватись на деталі більш близьких об'єктів, якщо вони повністю або частково перекривають попередньо оброблені. Якщо завдання буде виконано правильно, то ця процедура забезпечує правильний перегляд прихованої поверхні.

Сортування багатокутників

Циклічні багатокутники повинні бути усунені, щоб правильно сортувати їх по глибині

Починаємо з формування списку багатокутників, які впорядковуються по значенню zmin для кожного багатокутника. Першим у списку буде багатокутним з найменшим значенням zmin. Цей багатокутник найвіддаленіший по Z-напряму. Позначимо його через P, а наступний за ним через Q. Сортування багатокутників P і Q відбувається в кілька етапів, в яких з'ясовується їх взаємне розташування.

  1. Якщо крайні значення Z-координат усіх вершин P лежать далі, ніж Q, сортування тривіальне. P сортується пізніше.
  2. Якщо многокутники, що порівнюються, не перекриваються крайніми значеннями в площині X, У, їх не потрібно сортувати, оскільки вони не перетинаються.
  3. Якщо всі вершини P більш віддалені від глядача, ніж рівень в Q, то P упорядкований.
  4. Якщо всі вершини Q до глядача ближче, ніж на рівні P, то P упорядкований.
  5. Якщо X, Y значення P і Q перетинаються, то їх не потрібно сортувати.
  6. Якщо досі немає сортування і не вдалося циклічно перекрити многокутники, то у цьому випадку, вони повинні бути виділені і сортування буде продовжене з нециклічних частин. Поділ відбувається на одному з многокутників на розрізаній кромці з іншого многокутника.

Многокутники повинні бути плоскі, тобто, всі вершини повинні лежати на одній площині. Перевірте, чи є які-небудь вершини на площині, підставляючи координати всіх точок у рівняння площини.

Порядок кроків обирається таким чином, щоб прості тести були першими, а більш складні тести виконувались в кінці з метою мінімізації часу на обчислення.

Алгоритм Ньюелла використовує набагато менше ресурсів пам'яті, ніж, скажімо, алгоритм Z-буфера, який частіше використовується для прихованої поверхні обчислень, але явно поступається у швидкості.

Джерела

  • Д. Роджерс. Алгоритмические основы машинной графики. — Москва : Мир, 1989. — С. 331. — ISBN 5-03-000476-9.(рос.)
  • Sutherland, Ivan E.; Sproull, Robert F.; Schumacker, Robert A. (1974), A characterization of ten hidden-surface algorithms, Computing Surveys, 6 (1): 1—55, doi:10.1145/356625.356626(англ.)
  • Newell, M. E.; Newell, R. G.; Sancha, T. L. (1972), A new approach to the shaded picture problem, Proc. ACM National Conference, с. 443—450(англ.)

Read other articles:

Anna's Archive

Anna's ArchiveHalaman beranda Anna's Archive (26 September 2023)URLannas-archive.org beserta situs-situs alternatif lainnya[1]Tipe Mesin pencari perpustakaan digital berbagi berkas Service entry (en)10 November 2022; 15 bulan lalu (2022-11-10)[2]KeadaanAktifBlog resmihttps://annas-blog.org Anna's Archive adalah mesin pencari untuk perpustakaan-perpustakaan bayangan. Situs web ini dibentuk oleh sekelompok pengarsip dengan nama-nama yang tidak diketahui yakni Pirate Library...

 

Boljoon

Boljoon Munisipalitas di Filipina Tempat categoria:Articles mancats de coordenades Negara berdaulatFilipinaRegion di FilipinaVisayas TengahProvinsi di FilipinaCebu NegaraFilipina Pembagian administratifArbor (en) Baclayan (en) El Pardo (en) Granada (en) Lower Becerril (en) Lunop (en) Nangka (en) Poblacion (en) San Antonio (en) South Granada (en) Upper Becerril (en) PendudukTotal17.525  (2020 )Tempat tinggal4.106  (2020 )Bahasa resmiCebu dan Tagalog GeografiLuas wilayah117 km² ...

 

Bełżyce

BełżyceGereja Pertobatan Santo Paulus BenderaLambang kebesaranKoordinat: 51°11′N 22°16′E / 51.183°N 22.267°E / 51.183; 22.267Koordinat: 51°11′N 22°16′E / 51.183°N 22.267°E / 51.183; 22.267Negara PolandiaVoivodeshipProvinsi LublinPowiatPowiat LublinGminaBełżyceHak kota1417–1869, 1958Pemerintahan • Wali kotaIreneusz Paweł Łucka[1]Luas • Total23,46 km2 (906 sq mi)Populasi&#...

The Age

The Age adalah sebuah surat kabar harian yang diterbitkan di Melbourne, Australia dan merupakan salah satu dari dua koran lokal besar selain Herald Sun. Diterbitkan sejak tahun 1854, The Age berbentuk lembar lebar dan umumnya dipandang sebagai surat kabar yang memuat berita-berita yang lebih serius dibandingkan dengan Sun. Pranala luar (Inggris) Situs resmi Artikel bertopik jurnalisme ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs

 

Takeru Satoh

Takeru SatohSatoh saat premiere Rurouni Kenshin: Kyoto Inferno pada bulan Juni 2014Nama asal佐藤 健Lahir21 Maret 1989 (umur 35)Iwatsuki-ku, Saitama, JepangPekerjaanAktorTahun aktif2006–kiniAgenAmuse, Inc.Situs websatohtakeru.com Takeru Satoh (佐藤 健code: ja is deprecated , Satō Takeru, lahir pada 21 Maret 1989) adalah aktor asal Jepang yang terkenal dengan perannya sebagai Ryotaro Nogami dalam serial tokusatsu Kamen Rider Den-O, dan sebagai Himura Kenshin di film lag...

 

Red-crested turaco

Species of bird Red-crested turaco Red-crested turaco, Niagara Falls Aviary, Canada Conservation status Least Concern  (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Musophagiformes Family: Musophagidae Genus: Tauraco Species: T. erythrolophus Binomial name Tauraco erythrolophus(Vieillot, 1819) The red-crested turaco (Tauraco erythrolophus) is a turaco, a group of African otidimorph birds. It is a frugivorous b...

Ankylosaurus

Ankylosaurid dinosaur genus from the Late Cretaceous Period Not to be confused with Ankylosuchus. AnkylosaurusTemporal range: Late Cretaceous (Maastrichtian), 68–66 Ma PreꞒ Ꞓ O S D C P T J K Pg N ↓ Cast of Ankylosaurus skull (AMNH 5214) in front view, Museum of the Rockies Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Clade: Dinosauria Clade: †Ornithischia Clade: †Thyreophora Clade: †Ankylosauria Family: †Ankylosauridae Subfamily: †A...

 

Max Hastings

English journalist, editor, historian and author (born 1945) SirMax HastingsFRSL FRHistSHastings in 2013BornMax Hugh Macdonald Hastings (1945-12-28) 28 December 1945 (age 78)Lambeth, London, EnglandEducationUniversity College, OxfordOccupation(s)Journalist, editor, authorEmployersBBCEvening StandardThe Daily TelegraphSpouses Patricia Edmondson ​ ​(m. 1972; div. 1994)​ Penelope Levinson ​ ​(m. 1999)​Chi...

 

Meade Lux Lewis

Meade Lux LewisLewis negli anni quaranta Nazionalità Stati Uniti GenereJazzHonky tonkBluesBoogie-woogie StrumentoPianoforte Modifica dati su Wikidata · Manuale Meade Lewis, detto Lux (Chicago, 4 settembre 1905 – Minneapolis, 7 giugno 1964), è stato un pianista e compositore statunitense. Indice 1 Storia 2 Biografia 3 Note 4 Bibliografia 5 Altri progetti 6 Collegamenti esterni Storia È famoso per i suoi contributi nel genere boogie-woogie. Il suo pezzo più famoso, Honky To...

Hove, Belgium

Municipality in Flemish Community, BelgiumHoveMunicipalityTown hall FlagCoat of armsLocation of Hove HoveLocation in Belgium Location of Hove in the province of Antwerp Coordinates: 51°09′N 04°28′E / 51.150°N 4.467°E / 51.150; 4.467Country BelgiumCommunityFlemish CommunityRegionFlemish RegionProvinceAntwerpArrondissementAntwerpGovernment • MayorBart Van Couwenberge (N-VA) • Governing party/iesN-VA, Fan Van HoveArea •...

 

Bailiwick

The area of jurisdiction of a bailiff A bailiwick (/ˈbeɪlɪwɪk/)[1] is usually the area of jurisdiction of a bailiff, and once also applied to territories in which a privately appointed bailiff exercised the sheriff's functions under a royal or imperial writ. In English, the original French bailie combined with -wic, the Anglo-Saxon suffix (meaning a village) to produce a term meaning literally 'bailiff's village'—the original geographic scope of a bailiwick. In the 19th cen...

 

Messale

Modena, Archivio capitolare, Messale del XII secolo. Il Messale, nella Chiesa cattolica, è un libro liturgico contenente tutte le informazioni (testi, orazioni, canti, gli stessi gesti e le rubriche) necessarie al celebrante per la celebrazione della Messa o Eucaristia secondo l'anno liturgico[1]. Indice 1 Origine 2 I diversi messali 3 Note 4 Voci correlate 5 Altri progetti 6 Collegamenti esterni Origine Il messale, detto Missale plenum, fece la sua comparsa nella Chiesa latina attor...

Fairport Convention

British folk rock group Fairport ConventionFairport Convention performing in 2023Background informationAlso known asFairportOriginLondon, EnglandGenresFolk rockfolkYears active1967–19791985–presentLabelsPolydorIslandA&MVertigoRough TradeTransatlanticWoodwormMatty GroovesSpinoffs The Albion Band Fotheringay Matthews Southern Comfort Plainsong Steeleye Span Members Simon Nicol Dave Mattacks Dave Pegg Ric Sanders Chris Leslie Past members Richard Thompson Ashley Hutchings Shaun Frater Ma...

 

Харьков в филателии

Марка Украины к 350-летию Харькова с изображением герба города, Благовещенского собора, Госпрома и Успенского собора, 2004 (Mi #661; Sc #558) Герб ХарьковаИстория Харькова Харьков Герб ФлагXVII—XVIII века Харько Происхождение названия Крепость Казацкий полк Наместничество Губерна...

 

Metromedia

Defunct American media company This article is about the media company. For other uses, see Metromedia (disambiguation). Metromedia, Inc.Company typePublicIndustryMediaPredecessorAllen B. DuMont LaboratoriesDuMont Broadcasting CorporationMetropolitan Broadcasting CorporationFounded1931; 93 years ago (1931) as Allen B. DuMont LabsDefunct1997; 27 years ago (1997) (as a media company)FateSold off. Corporate name continues as owner of MetroMedia Technologies.&#...

Radio Deejay

La neutralità di questa voce o sezione sull'argomento radio è stata messa in dubbio. Motivo: Toni enfatici e celebrativi da fan page, eccesso di dettaglio sui palinsesti (Wikipedia non è una guida ai programmi radiofonici) Per contribuire, correggi i toni enfatici o di parte e partecipa alla discussione. Non rimuovere questo avviso finché la disputa non è risolta. Segui i suggerimenti del progetto di riferimento. Radio DeejayPaese Italia Data di lancio1º febbraio 1982 Share d...

 

1Lib1Ref

Judul yang benar dari artikel ini adalah #1Lib1Ref. Judulnya terlihat keliru karena keterbatasan teknis. #1Lib1RefSeorang pustakawan Israel sedang memakai Wikipedia (foto publisitas untuk proyek tersebut)LokasiDaringAcara pertama15 Januari 2016 (2016-01-15) – 23 Januari 2016 (2016-01-23)Acara sebelumnya15 Mei 2022 (2022-05-15) – 5 Juni 2022 (2022-06-5)Acara berikutnya15 Mei 2023 (2023-05-15) – 5 Juni 2023 (2023-06-5)Situs web1lib1ref.org #1Lib1Ref (Satu Pus...

 

شادي رياض

شادي رياض معلومات شخصية الميلاد 17 يونيو 2003 (العمر 21 سنة)ميورقة  الطول 1.87 م (6 قدم 1 1⁄2 بوصة) مركز اللعب مدافع الجنسية المغرب  معلومات النادي النادي الحالي ريال بيتيس(مُعاراً من برشلونة) الرقم 28 مسيرة الشباب سنوات فريق 2009–2011 Atlético Rafal 2011–2014 ريال مايوركا 2014–20...

The Insider (film)

Artikel ini bukan mengenai The Inside (film) atau Inside Man. The InsiderPoster rilis teatrikalSutradaraMichael MannProduserPieter Jan BruggeMichael MannSkenarioEric RothMichael MannBerdasarkanThe Man Who Knew Too Mucholeh Marie BrennerPemeran Al Pacino Russell Crowe Christopher Plummer Diane Venora Philip Baker Hall Lindsay Crouse Debi Mazar Penata musikPieter BourkeLisa GerrardSinematograferDante SpinottiPenyuntingWilliam GoldenbergDavid RosenbloomPaul RubellPerusahaanproduksiTouchsto...

 

Laurelton station

Long Island Rail Road station in Queens, New York LaureltonA staircase at the Laurelton station, prior to its 2018-19 renovation.General informationLocation224th Street and 141st RoadLaurelton, Queens, New YorkCoordinates40°40′07″N 73°45′06″W / 40.66853°N 73.7518°W / 40.66853; -73.7518Owned byLong Island Rail RoadLine(s)Atlantic BranchDistance13.1 mi (21.1 km) from Atlantic Terminal[1]Platforms1 island platformTracks2Connections NYCT Bus: ...