分類: 3C資訊

  • 緬甸發現新物種「波巴葉猴」 僅剩250隻瀕臨絕種

    摘錄自2020年11月11日自由時報報導

    科學家發現一種生活在緬甸中部森林的靈長類新物種「波巴葉猴」(Popa langur,暫譯),但這種體型輕巧的樹棲動物目前數量極少,已瀕臨滅絕。

    《法新社》報導,週三發表於《Zoologic Research》期刊的一份詳細研究報告指出,研究員透過森林中採集的糞便和倫敦自然歷史博物館收藏的標本,發現波巴葉猴是一個新物種,已存在至少100萬年。其腹部呈灰棕色和白色,手和腕毛髮為黑色,尾巴將近1公尺比身體還長,重約8公斤。但是,波巴葉猴目前野外只剩下200至250隻,大約100隻生活在波巴山,因此專家建議,將這種食葉動物列為極危物種(Critically Endangered)。

    研究發現,由於農地擴張、非法和不可持續性的林業開採,導致這種帶有「白眼圈」的猴子受到狩獵、棲息地喪失、退化等各方面的威脅。FFI緬甸計畫的靈長類動物學家Ngwe Lwin說,迫切需要進行其他野外調查和保護措施。

    生物多樣性
    國際新聞
    緬甸
    瀕危物種
    猴子

    本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    台北網頁設計公司這麼多該如何選擇?

    ※智慧手機時代的來臨,RWD網頁設計為架站首選

    ※評比南投搬家公司費用收費行情懶人包大公開

    ※回頭車貨運收費標準

    網頁設計最專業,超強功能平台可客製化

    ※別再煩惱如何寫文案,掌握八大原則!

  • 聯合國氣候峰會 川普出席15分鐘

    摘錄自2019年9月24日公共電視、中央社報導

    第74屆聯合國大會,23日在美國紐約召開,全球有約60國領袖,出席聯合國氣候行動峰會。

    原本預計會缺席的美國總統川普,也意外現身,但沒有發言,只待了15分鐘後,聽了印度總理莫迪,和德國總理梅克爾的演說後就離席。而梅克爾發言時表示,德國在2030年時,希望將二氧化碳排放量,減少到1990年的55%,並且在2050年時達到零碳排。

    瑞典16歲環保少女童貝里激動地痛斥各國領袖不解決碳排,背叛她這個世代;媒體還捕捉到美國總統川普意外現身,童貝里怒瞪川普的畫面。不過肢體語言專家伍德(Patti Wood)伍德解釋,童貝里的肢體反應有可能被誇大。

    政策
    公約
    環境政策
    全球變遷
    氣候變遷
    國際新聞
    美國
    川普
    全球暖化

    本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

    南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

    ※教你寫出一流的銷售文案?

    ※超省錢租車方案

    ※回頭車貨運收費標準

  • 美國蘿蔓生菜染大腸桿菌 12/27前禁輸入

    摘錄自2019年11月28日公視報導

    美國加州傳出蘿蔓生菜遭出血型大腸桿菌污染中毒事件,我國食藥署昨(27日)傍晚緊急宣布,從今天起一個月,暫停受理美國蘿蔓生菜進口查驗申請;也提醒民眾要注意。

    感恩節前,美國又再度爆發蘿蔓生菜遭出血型大腸桿菌污染中毒事件,目前已知有19州、67例確定病例,美國疾病管制署日前發出安全警告,而我國衛福部食藥署27號傍晚也宣布,從28號起到下個月27號,暫停受理美國蘿蔓生菜輸入查驗申請。

    食藥署食品組科長廖姿婷說:「在邊境是需要檢附未有受污染的證明文件,我們才可以受理它報驗,如果來自美國的生菜是沒有相關的證明文件的話,我們邊境是不會允許它受理報驗。」

    食藥署表示,美國從9月底開始,就陸續傳出「O157:H7型」大腸桿菌污染蘿蔓生菜案例,而這種大腸桿菌傳染途徑、大多與飲食有關,例如吃到未煮熟又遭汙染的牛肉、蔬果等,臨床症狀包括噁心、嘔吐、出血性腹瀉,嚴重者會出現溶血性尿毒症,甚至腎衰竭而死亡,台灣曾在2001年出現過一例。

    醫師提醒,家中如果還有美國蘿蔓生菜,建議丟棄不要食用或煮熟後再吃,而根據食藥署統計,今年1月至今,國內共進口蘿蔓生菜約4000公噸,以美國為大宗,流向大多為果菜市場、大賣場等。

    生活環境
    國際新聞
    美國
    生菜
    大腸桿菌
    中毒
    食藥署
    食品安全

    本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※Google地圖已可更新顯示潭子電動車充電站設置地點!!

    ※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

    ※別再煩惱如何寫文案,掌握八大原則!

    網頁設計最專業,超強功能平台可客製化

    ※回頭車貨運收費標準

    【其他文章推薦】

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※Google地圖已可更新顯示潭子電動車充電站設置地點!!

    ※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

    ※別再煩惱如何寫文案,掌握八大原則!

    網頁設計最專業,超強功能平台可客製化

    ※回頭車貨運收費標準

  • 暖化、伐木威脅馬達加斯加 東部雨林、特有種可能在50年後消失

    暖化、伐木威脅馬達加斯加 東部雨林、特有種可能在50年後消失

    環境資訊中心外電;姜唯 翻譯;林大利 審校;稿源:ENS

    紐約市立大學研究生中心的研究發現,若再不積極因應森林砍伐和人類引起的氣候變遷問題,兩者的綜合效應到了2070年可能使整個馬達加斯加東部的雨林消失,影響該島國特有的數千種植物、哺乳動物、爬行動物和兩棲動物。

    研究發表在當期《自然氣候變遷》(Nature Climate Change)期刊。研究指出,保護區有助於減輕破壞,而環境人士則致力於尋求長期解決方案,以解決溫室氣體排放失控和隨之而來的氣候變遷。

    研究確立了應優先保護的完整森林區域,以加強受威脅物種的恢復能力和生存能力。

    位於馬達加斯加境內拉努馬法納國家公園外,由於農業用途而遭到砍燒的森林。照片來源:Nina Beeby(CC BY-ND 4.0)

    馬達加斯加位於印度洋,是僅次於澳洲的世界第二大島國,距東非海岸250英里(400公里)。由於與周邊各大洲長期處於隔離狀態,馬達加斯加有許多其他地方所沒有的動植物。

    馬達加斯加是生物多樣性熱點,80%至90%的動植物物種為特有種,但數十年來的濫墾濫伐破壞了許多特殊和瀕危野生動物的棲地,包括瀕危的狐猴。

    目前有兩種領狐猴瀕臨滅絕,牠們在生態系統中的角色是散播植物種子,而這些植物為雨林中的其他動物提供食物和庇護所。

    研究主要作者、紐約市立大學研究生中心和亨特學院人類學教授巴登(Andrea Baden)博士說:「由於狐猴是重要的種子傳播者,對生活環境劣化也很敏感,因此牠是馬達加斯加整個東部雨林健康狀況的關鍵指標。」

    非政府組織保護國際(Conservation International)認為,狐猴是馬達加斯加的代表性哺乳動物。在沒有猴子和其他競爭者的情況下,這些靈長類動物已經適應了當地遼闊的棲息地,並演化出許多不同的物種。

    由於狐猴是重要的種子傳播者,因此牠是馬達加斯加整個東部雨林健康狀況的關鍵指標。照片來源:Franck Rabenahy(CC BY-ND 4.0)

    截至2012年,已正式確立103個狐猴的物種和亞種,其中有39種是動物學家在2000年至2008年間發現的。牠們幾乎都是稀有、易危或瀕危物種。自人類抵達馬達加斯加以來,至少有17種狐猴滅絕。

    巴登博士和她的團隊在馬達加斯加研究兩種極度瀕危的領狐猴,利用長達三十年的研究資料,分析該國東部熱帶雨林面臨的威脅。

    巴登說:「我們預測森林砍伐和氣候變遷的影響時,發現光是森林砍伐和氣候變遷兩個因素,就足以使狐猴棲息地減少50%以上。更令人震驚的是,這兩個因素到本世紀末將明顯減少熱帶雨林棲息地。」

    研究人員的資料顯示,馬達加斯加東部雨林破壞的速度和強度將取決於該國是否制定嚴格的保護措施來防止毀林或因應鬆散的政策。

    森林是狐猴的庇護所,也是連接牠們活動範圍的生態廊道。保護森林的工作非常重要,因為狐猴是當地的關鍵物種,在這個全球生物多樣性最豐富的地區,牠們的存續和許多其他動植物的存續息息相關。

    自人類抵達馬達加斯加以來,至少有17種狐猴滅絕。照片來源:Varecia Garbutt(CC BY-ND 4.0)

    馬達加斯加有許多特有哺乳動物,例如馬島獴(Fossa, Cryptoprocta ferox)。島上記錄到300多種鳥類,其中60%以上是特有種,還有全世界三分之二的變色龍物種,包括已知最小的一種。科學家認為。馬達加斯加可能是所有變色龍的起源地。

    在馬達加斯加的14,883種植物中,有80%以上是特有種,包括五個植物科。島上許多原生植物物種被用作草藥。像長春花鹼和長春新鹼都是馬達加斯加長春花的生物鹼,用於治療霍奇金氏病、白血病和其他癌症。

    巴登說:「我們的研究結果能幫助非營利組織、國家公園管理和更廣泛的狐猴群聚保育。結果顯示,森林覆蓋度和連結度是領狐猴和所有棲息於森林的野生動物生存的關鍵。保護區對於物種的生存至關重要。」

    非營利組織已經在著手保護這個獨特而受威脅的地區。保護國際自1996年起就在馬達加斯加東部進行自然保育計畫。總部位於美國的「保護國際」正在協助馬達加斯加政府制定和實施「具有保育意識的永續發展策略」。

    保護國際正在馬達加斯加東部的Ankeniheny-Zahamena廊道執行測試計畫,目的是產生碳信用額度,可以出售給想抵消碳排放量的公司或其他買家。這個計畫由外部審核方雨林聯盟(Rainforest Alliance)驗證,透過保護協議吸引社區參與、提供社區財政激勵措施,保護他們的森林並監測威脅。

    世界野生動物基金會(WWF)在該地區也已經耕耘了三十多年,與當地社區合作保護馬達加斯加的獨特環境。

    2020年是馬達加斯加脫離法國獨立60週年,將種下6000萬棵幼苗綠化馬達加斯加。在環境與永續發展部的邀請下,約有20個環境組織和多所大學的學生會參與這項公民活動。

    環境與永續發展部植樹造林與景觀和森林管理總監傑克斯(Jaozandry Jean Jacques)表示,植樹造林活動將在2020年1月展開。

    Climate, Logging Menace Madagascar’s Unique Ecology JOHANNESBURG,New York,January 2, 2020 (ENS)

    Left unchecked, the combined effects of deforestation and human-induced climate change could eliminate Madagascar’s entire eastern rainforest habitat by 2070, impacting thousands of plants, mammals, reptiles, and amphibians endemic to the island nation, finds new research from The Graduate Center at the City University of New York, CUNY.

    Published in the current issue of the journal “Nature Climate Change,” the study also shows that protected areas will help to lessen the devastation while environmentalists work toward long-term solutions for ending runaway greenhouse gas emissions and the resulting climate change.

    The study identifies areas of intact forest that could be prioritized for protection to enable resilience and survival of threatened species.

    Madagascar, the world’s second-largest island country after Australia, lies in the Indian Ocean, 250 miles (400 kilometers) off the coast of East Africa. As a result of the island’s long isolation from neighboring continents, Madagascar is inhabited by animals and plants found nowhere else on Earth

    It is a biodiversity hotspot where 80 to 90 percent of its animal and plant species are exclusive to the area, but the land has been devasted by decades of deforestation and overharvesting, destroying much of the land cover that provides habitat for unique animals, including endangered varieties of lemurs.

    In particular, two species of ruffed lemurs are now critically endangered, and these animals play a central role in dispersing the seeds of plant species that provide food and shelter for other animals across the rainforest.

    “Because of their essential role as seed dispersers and their sensitivity to habitat degradation, ruffed lemurs serve as a critical indicator of the health of Madagascar’s entire eastern rainforest,” said Dr. Andrea Baden, a professor of anthropology at The Graduate Center, CUNY and Hunter College and the study’s primary investigator.

    Lemurs have been characterized as “Madagascar’s flagship mammal species” by Conservation International. In the absence of monkeys and other competitors, these primates have adapted to a wide range of habitats and diversified into numerous species.

    As of 2012, there were officially 103 species and subspecies of lemur, 39 of which were described by zoologists between 2000 and 2008. They are almost all classified as rare, vulnerable, or endangered. At least 17 species of lemur have become extinct since humans arrived on Madagascar.

    Dr. Baden and her team employed a case study of the two critically endangered ruffed lemurs using three decades of research throughout Madagascar to analyze threats to the country’s eastern tropical rainforest.

    “When we projected the impact of deforestation and climate change, we found that deforestation alone and climate change alone could reduce ruffed lemur habitat by over 50 percent,” said Baden. “Even more alarming, these two factors together are projected to essentially decimate suitable rainforest habitat by the end of the century.”

    The researchers’ data suggest that the speed and intensity of destruction to Madagascar’s eastern rainforest will be determined by whether the country institutes strict protections against deforestation or a relaxed set of policies.

    Protecting forested areas that provide shelter to ruffed lemurs and serve as corridor links to their strongholds is particularly important to survival given their role as a keystone species that enables the survival of a large number of other animal and plant species in one of the world’s most biodiverse regions.

    A number of other mammals, including the cat-like fossa, are endemic to Madagascar. Over 300 species of birds have been recorded on the island, of which over 60 percent are endemic. The island nation is inhabited by two-thirds of the world’s chameleon species, including the smallest known, and scientists have proposed that Madagascar may be the origin of all chameleons.

    More than 80 percent of Madagascar’s 14,883 plant species are found nowhere else in the world, including five plant families. Many plant species native to the island are used as herbal remedies. The drugs vinblastine and vincristine are vinca alkaloids, used to treat Hodgkin’s disease, leukemia, and other cancers, were derived from the Madagascar periwinkle.

    “The results from our study will be useful to nonprofit organizations, park management, and the broader conservation community,” Baden said. “Our results indicate potential conservation opportunities for ruffed lemurs and any of the rainforest-dwellers that rely on forest cover and connectivity. Protected areas are vital to species persistence.”

    Nonprofit gorups are already at work protecting this unique and threatened area.

    Conservation International has had conservation projects in eastern Madagascar since 1996. The nonprofit organization based in the United States is currently supporting the government of Madagascar in the development and implementation of “a conservation-conscious sustainable development strategy for the area.”

    Conservation International has developed a pilot project in the Ankeniheny-Zahamena Corridor of eastern Madagascar that aims to generate carbon credits that can be sold to companies or other buyers looking to offset carbon emissions. Validated by an external auditor, the Rainforest Alliance, the project engages communities through conservation agreements that give these communities financial incentives to conserve their forests and monitor threats.

    The World Wildlife Fund, WWF, has been active there for more than three decades, working with local communities to protect Madagascar’s unique environment.

    For the 60th anniversary of Madagascar’s independence from France in 1960, 60 million young plants will be planted to green Madagascar.

    In response to an invitation from the Ministry of the Environment and Sustainable Development, MEDD, some 20 environmental organizations and several university students are involved in this citizen mobilization.

    Jaozandry Jean Jacques, director of Reforestation and Management of Landscapes and Forests within the MEDD, says, “We plan to officially open reforestation in Madagascar in January 2020.”

    ※ 全文及圖片詳見:ENS

    ※ 本文與 行政院農業委員會 林務局  合作刊登

    森林砍伐
    氣候變遷
    熱帶雨林
    狐猴
    特有種
    種樹
    森林
    國際新聞
    馬達加斯加
    全球變遷
    生態保育
    生物多樣性
    氣候變遷

    作者

    姜唯

    如果有一件事是重要的,如果能為孩子實現一個願望,那就是人類與大自然和諧共存。

    林大利

    於特有生物研究保育中心服務,小鳥和棲地是主要的研究對象。是龜毛的讀者,認為龜毛是探索世界的美德。

    本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

    ※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

    南投搬家公司費用需注意的眉眉角角,別等搬了再說!

    ※教你寫出一流的銷售文案?

    ※回頭車貨運收費標準

    ※別再煩惱如何寫文案,掌握八大原則!

  • 昆州將建澳洲最大鋰電池 可為5.7萬家庭供電

    摘錄自2020年1月30日大紀元報導

    昆州與能源巨頭AGL達成協議,建造澳洲最大的電池。通過彌補風能和太陽能的間歇性特性,這組鋰電池將增強電網從煤炭供電轉向可再生能源供電的能力。

    昆州政府週三表示,獨立電力供應商Vena Energy將在18個月內在萬多恩(Wandoan)建造一座新的巨型電網級電池,耗資1.2億澳元。

    該電池與美國科技界億萬富翁馬斯克(Elon Musk)在南澳建造的最大鋰電池規模相近,有100兆瓦的容量,可儲存150兆瓦小時的電力,足夠5萬7000個家庭使用。

    去年,上市公司AGL與可再生能源公司茂能集團(Maoneng Group)簽署了一項為期15年的協議,將在新州建造四塊大型電池,為2023年利德爾(Liddell)燃煤發電廠的關閉做準備。

    再生能源
    能源議題
    能源轉型
    國際新聞
    澳洲
    鋰電池
    電力

    本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    ※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    ※想知道最厲害的網頁設計公司"嚨底家"!

    ※別再煩惱如何寫文案,掌握八大原則!

    ※產品缺大量曝光嗎?你需要的是一流包裝設計!

    ※回頭車貨運收費標準

    台中搬家公司費用怎麼算?

  • DirectX11 With Windows SDK–31 陰影映射

    DirectX11 With Windows SDK–31 陰影映射

    前言

    陰影既暗示着光源相對於觀察者的位置關係,也從側面傳達了場景中各物體之間的相對位置。本章將起底最基礎的陰影映射算法,而像複雜如級聯陰影映射這樣的技術,也是在陰影映射的基礎上發展而來的。

    學習目標:

    1. 掌握基本的陰影映射算法
    2. 熟悉投影紋理貼圖的工作原理
    3. 了解陰影圖走樣的問題並學習修正該問題的常用策略

    DirectX11 With Windows SDK完整目錄

    Github項目源碼

    歡迎加入QQ群: 727623616 可以一起探討DX11,以及有什麼問題也可以在這裏彙報。

    核心思想

    陰影映射技術的核心思想其實不複雜。對於場景中的一點,如果該點能夠被攝像機觀察到,卻不能被光源定義的虛擬攝像機所觀察到,那麼場景中的這一點則可以被判定為光源所照射不到的陰影區域。

    以下圖為例,眼睛觀察到地面上最左邊的一點,並且從光源處觀察也能看到該點。因此該點不會產生陰影。

    再看下面的圖,眼睛可以觀察到地面上中間那一點,但是從光源處觀察不能看到該點。因此該點會產生陰影。

    具體落實下來應該怎麼做呢?對於點光源來說,由於它的光是朝所有方向四射散開的,但為了方便,我們可以像攝像機那樣選取視錐體區域(使用一個觀察矩陣 + 透視投影矩陣來定義),然後經過正常的變換后就能計算出光源到區域內物體的深度值;而對於平行光(方向光)來說,我們可以採用正交投影的方式來選取一個長方體區域(使用一個觀察矩陣 + 正交投影矩陣定義)。和一般的渲染流程不同的是,我們只需要記錄深度值到深度緩衝區,而不需要將顏色繪製到後備緩衝區。

    陰影貼圖

    陰影貼圖技術也是一種變相的“渲染到紋理”技術。它以光源的視角來渲染場景深度信息,即在光源處有一個虛擬攝像機,它將觀察到的物體的深度信息保存到深度緩衝區中。這樣我們就可以知道那些離光源最近的像素片元信息,同時這些點自然是不在陰影範圍之中。

    通常該技術需要用到一個深度/模板緩衝區、一個與之對應的視口、針對該深度/模板緩衝區的着色器資源視圖(SRV)和深度/模板視圖(DSV),而用於陰影貼圖的那個深度/模板緩衝區也被稱為陰影貼圖

    光源的投影

    在考慮點光源的投影和方向光的投影時可能會有些困難,但這兩個問題其實可以轉化成虛擬攝像機的透視投影和正交投影。

    對於透視投影來說,其實我們也已經非常熟悉了。在這種做法下我們只考慮虛擬攝像機的視錐體區域(即儘管點光源是朝任意方向照射的,但我們只看點光源往該視錐體範圍內照射的區域),然後對物體慣例進行世界變換、以光源為視角的觀察變換、光源的透視投影變換,這樣物體就被變換到了以光源為視角的NDC空間。

    而對於正交投影而言,我們也是一樣的做法。正交投影的視景體是一個軸對齊於觀察坐標系的長方體。儘管我們不好描述一個方向光的光源,但為了方便,我們把光源定義在視景體xOy切面中心所處的那條直線上。這樣我們就只需要給出視景體的寬度、高度、近平面、遠平面信息就可以構造出一個正交投影矩陣了。

    我們可以看到,正交投影的投影線均平行於觀察空間的z軸。

    正交投影矩陣在第四章變換已經講過,就不再贅述。

    投影紋理坐標

    投影紋理貼圖技術能夠將紋理投射到任意形狀的幾何體上,又因為其原理與投影機的工作方式比較相似,由此得名。例如下圖中,右邊的骷髏頭紋理被投射到左邊場景中的多個幾何體上。

    投影紋理貼圖的關鍵在於為每個像素生成對應的投影紋理坐標,從視覺上給人一種紋理被投射到幾何體上的感覺。

    下圖是光源觀察的視野,其中點p是待渲染的一點,而紋理坐標(u, v)則指定了應當被投射到3D點p上的紋素,並且坐標(u, v)與投影到屏幕上的NDC坐標有特定聯繫。我們可以將投影紋理坐標的生成過程分為如下步驟:

    1. 將3D空間中一點p投影到光源的投影窗口,並將其變換到NDC空間。
    2. 將投影坐標從NDC空間變換到紋理空間,以此將它們轉換為紋理坐標

    而步驟2中的變換過程則取決於下面的坐標變換:

    \[u=0.5x+0.5\\ v=-0.5y+0.5 \]

    即從x, y∈[-1, 1]映射到u, v∈[0, 1]。(y軸和v軸是相反的)

    這種線性變換可以用矩陣表示:

    \[\mathbf{T}=\begin{bmatrix} 0.5 & 0 & 0 & 0 \\ 0 & -0.5 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0.5 & 0.5 & 0 & 1 \\ \end{bmatrix}\\ \begin{bmatrix} x & y & 0 & 1 \end{bmatrix}\mathbf{T}=\begin{bmatrix} u & v & 0 & 1 \end{bmatrix} \]

    那麼物體上的一點p從局部坐標繫到最終的紋理坐標點t的變換過程為:

    \[\mathbf{p}\mathbf{W_{Obj}}\mathbf{V_{Light}}\mathbf{P_{Light}}\mathbf{T}=\mathbf{t} \]

    這裏補上了世界變換矩陣,是因為這一步容易在後面的代碼實踐中被漏掉。但此時的t還需要經過透視除法,才是我們最終需要的紋理坐標。

    HLSL代碼

    下面的HLSL代碼展示了頂點着色器計算投影紋理坐標的過程:

    // 頂點着色器
    VertexPosHWNormalTexShadowPosH VS(VertexPosNormalTex vIn)
    {
        VertexPosHWNormalTexShadowPosH vOut;
        
        matrix viewProj = mul(g_View, g_Proj);
        vector posW = mul(float4(vIn.PosL, 1.0f), g_World);
    
        vOut.PosW = posW.xyz;
        
        // ...
        
        // 把頂點變換到光源的投影空間
        vOut.ShadowPosH = mul(posW, g_ShadowTransform);
        return vOut;
    }
    
    // 像素着色器
    float4 PS(VertexPosHWNormalTexShadowPosH pIn) : SV_Target
    {
        // 透視除法
        pIn.ShadowPosH.xyz /= pIn.ShadowPosH.w;
        
        // NDC空間中的深度值
        float depth = pIn.ShadowPosH.z;
        
        // 通過投影紋理坐標來對紋理採樣
        // 採樣出的r分量即為光源觀察該點時的深度值
        float4 c = g_ShadowMap.Sample(g_Sam, pIn.ShadowPosH.xy);
        
        // ...
    }
    
    

    視錐體之外的點

    在渲染管線中,位於視錐體之外的幾何體是要被裁剪掉的。但是,在我們以光源設置的視角投影幾何體而為之生成投影紋理坐標時,並不需要執行裁剪操作——只需要簡單投影頂點即可。因此,位於視錐體之外的幾何體頂點會得到[0, 1]區間之外的投影紋理坐標。然後具體的採樣行為則需要依賴於我們設置的採樣器。

    一般來說,我們並不希望對位於視錐體外的幾何體頂點進行貼圖,因為這並沒有任何意義。考慮到可視深度在NDC空間的最大值為1.0f,我們可以採用邊界深度值為1.0f的邊框尋址模式

    另一種做法則是結合聚光燈的策略,使聚光燈照射範圍之外的部分不受光照,亦即不在陰影的計算範圍內。

    透視除法與投影的其他問題

    來到正交投影,因為我們依然是要計算出NDC坐標,對於NDC空間範圍外的點,我們依然可以採用上面的尋址模式策略,但聚光燈的策略就不適用了。

    此外,正交投影無需進行透視除法,因為正交投影后的坐標w值總是1.0f。但保留透視除法可以讓我們的這套着色器可以同時工作在正交投影和透視投影上。如果沒有透視除法,則只能在正交投影中工作。

    算法思路

    1. 從光源的視角將場景深度以“渲染到紋理”的形式繪製到名為陰影貼圖的深度緩衝區中
    2. 從玩家攝像機的視角渲染場景,計算出該點在光源視角下NDC坐標,其中z值為深度值,記為d(p)
    3. 上面算出的NDC坐標的xy分量變換為陰影貼圖的紋理坐標uv,然後進行深度值採樣,得到s(p)
    4. 當d(p) > s(p)時, 像素p位於陰影範圍之內;自然相反地,當d(p) <= s(p)時,像素p位於陰影範圍之外(至於為什麼還有<,後面會提到)

    改進TextureRender

    既然陰影貼圖和RTT有着許多相似的地方,那何不把它也放到TextureRender裏面共用呢?只要添加一個開關控制該RTT是否用作陰影貼圖即可。

    class TextureRender
    {
    public:
        template<class T>
        using ComPtr = Microsoft::WRL::ComPtr<T>;
    
        TextureRender() = default;
        ~TextureRender() = default;
        // 不允許拷貝,允許移動
        TextureRender(const TextureRender&) = delete;
        TextureRender& operator=(const TextureRender&) = delete;
        TextureRender(TextureRender&&) = default;
        TextureRender& operator=(TextureRender&&) = default;
    
    
        HRESULT InitResource(ID3D11Device* device,
            int texWidth,
            int texHeight,
            bool shadowMap = false,
            bool generateMips = false);
    
        // 開始對當前紋理進行渲染
        // 陰影貼圖無需提供背景色
        void Begin(ID3D11DeviceContext* deviceContext, const FLOAT backgroundColor[4]);
        // 結束對當前紋理的渲染,還原狀態
        void End(ID3D11DeviceContext * deviceContext);
        // 獲取渲染好的紋理的着色器資源視圖
        // 陰影貼圖返回的是深度緩衝區
        // 引用數不增加,僅用於傳參
        ID3D11ShaderResourceView* GetOutputTexture();
    
        // 設置調試對象名
        void SetDebugObjectName(const std::string& name);
    
    private:
        ComPtr<ID3D11ShaderResourceView>        m_pOutputTextureSRV;          // 輸出的紋理(或陰影貼圖)對應的着色器資源視圖
        ComPtr<ID3D11RenderTargetView>          m_pOutputTextureRTV;          // 輸出的紋理對應的渲染目標視圖
        ComPtr<ID3D11DepthStencilView>          m_pOutputTextureDSV;          // 輸出紋理所用的深度/模板視圖(或陰影貼圖)
        D3D11_VIEWPORT                          m_OutputViewPort = {};        // 輸出所用的視口
    
        ComPtr<ID3D11RenderTargetView>          m_pCacheRTV;                  // 臨時緩存的後備緩衝區
        ComPtr<ID3D11DepthStencilView>          m_pCacheDSV;                  // 臨時緩存的深度/模板緩衝區
        D3D11_VIEWPORT                          m_CacheViewPort = {};         // 臨時緩存的視口
    
        bool                                    m_GenerateMips = false;       // 是否生成mipmap鏈
        bool                                    m_ShadowMap = false;          // 是否為陰影貼圖
    
    };
    

    在作為RTT時,需要創建紋理與它的SRV和RTV、深度/模板緩衝區和它的DSV、視口

    而作為陰影貼圖時,需要創建深度緩衝區與它的SRV和DSV、視口

    下面的代碼只關注創建陰影貼圖的部分:

    HRESULT TextureRender::InitResource(ID3D11Device* device, int texWidth, int texHeight, bool shadowMap, bool generateMips)
    {
        // 防止重複初始化造成內存泄漏
        m_pOutputTextureSRV.Reset();
        m_pOutputTextureRTV.Reset();
        m_pOutputTextureDSV.Reset();
        m_pCacheRTV.Reset();
        m_pCacheDSV.Reset();
    
        m_ShadowMap = shadowMap;
        m_GenerateMips = false;
        HRESULT hr;
        
        // ...
        
        // ******************
        // 創建與紋理等寬高的深度/模板緩衝區或陰影貼圖,以及對應的視圖
        //
        CD3D11_TEXTURE2D_DESC texDesc((m_ShadowMap ? DXGI_FORMAT_R24G8_TYPELESS : DXGI_FORMAT_D24_UNORM_S8_UINT),
            texWidth, texHeight, 1, 1,
            D3D11_BIND_DEPTH_STENCIL | (m_ShadowMap ? D3D11_BIND_SHADER_RESOURCE : 0));
    
        ComPtr<ID3D11Texture2D> depthTex;
        hr = device->CreateTexture2D(&texDesc, nullptr, depthTex.GetAddressOf());
        if (FAILED(hr))
            return hr;
    
        CD3D11_DEPTH_STENCIL_VIEW_DESC dsvDesc(depthTex.Get(), D3D11_DSV_DIMENSION_TEXTURE2D, DXGI_FORMAT_D24_UNORM_S8_UINT);
    
        hr = device->CreateDepthStencilView(depthTex.Get(), &dsvDesc,
            m_pOutputTextureDSV.GetAddressOf());
        if (FAILED(hr))
            return hr;
    
        if (m_ShadowMap)
        {
            // 陰影貼圖的SRV
            CD3D11_SHADER_RESOURCE_VIEW_DESC srvDesc(depthTex.Get(), D3D11_SRV_DIMENSION_TEXTURE2D, DXGI_FORMAT_R24_UNORM_X8_TYPELESS);
    
            hr = device->CreateShaderResourceView(depthTex.Get(), &srvDesc,
                m_pOutputTextureSRV.GetAddressOf());
            if (FAILED(hr))
                return hr;
        }
    
        // ******************
        // 初始化視口
        //
        m_OutputViewPort.TopLeftX = 0.0f;
        m_OutputViewPort.TopLeftY = 0.0f;
        m_OutputViewPort.Width = static_cast<float>(texWidth);
        m_OutputViewPort.Height = static_cast<float>(texHeight);
        m_OutputViewPort.MinDepth = 0.0f;
        m_OutputViewPort.MaxDepth = 1.0f;
    
        return S_OK;
    }
    
    

    需要注意的是,在創建深度緩衝區時,如果還想為他創建SRV,就不能將DXGI格式定義成DXGI_FORMAT_D24_UNORM_S8_UINT這些帶D的類型,而應該是DXGI_FORMAT_R24G8_TYPELESS

    然後在創建陰影貼圖的SRV時,則需要指定為DXGI_FORMAT_R24_UNORM_X8_TYPELESS

    開始陰影貼圖的渲染前,不需要設置RTV,只需要綁定DSV。

    void TextureRender::Begin(ID3D11DeviceContext* deviceContext, const FLOAT backgroundColor[4])
    {
        // 緩存渲染目標和深度模板視圖
        deviceContext->OMGetRenderTargets(1, m_pCacheRTV.GetAddressOf(), m_pCacheDSV.GetAddressOf());
        // 緩存視口
        UINT num_Viewports = 1;
        deviceContext->RSGetViewports(&num_Viewports, &m_CacheViewPort);
    
        // 清空緩衝區
        // ... 
        deviceContext->ClearDepthStencilView(m_pOutputTextureDSV.Get(), D3D11_CLEAR_DEPTH | (m_ShadowMap ? 0 : D3D11_CLEAR_STENCIL), 1.0f, 0);
        
        // 設置渲染目標和深度模板視圖
        deviceContext->OMSetRenderTargets((m_ShadowMap ? 0 : 1), 
            (m_ShadowMap ? nullptr : m_pOutputTextureRTV.GetAddressOf()), 
            m_pOutputTextureDSV.Get());
        // 設置視口
        deviceContext->RSSetViewports(1, &m_OutputViewPort);
    }
    

    渲染完成后,和往常一樣還原即可。

    偏移與走樣

    陰影圖存儲的是距離光源最近的可視像素深度值,但是它的分辨率有限,導致每一個陰影圖紋素都要表示場景中的一片區域。因此,陰影圖只是以光源視角針對場景深度進行的離散採樣,這將會導致所謂的陰影粉刺等圖像走樣問題。如下圖所示(注意圖中地面上光影之間輪流交替的“階梯狀”條紋):

    而下圖則簡單展示了為什麼會發生陰影粉刺這種現象。由於陰影圖的分辨率有限,所以每個陰影圖紋素要對應於長江中的一塊區域(而不是點對點的關係,一個坡面代表陰影圖中一個紋素的對應範圍)。從觀察點E查看場景中的兩個點p1與p2,它們分別對應於兩個不同的屏幕像素。但是,從光源的觀察角度來看,它們卻都有着相同的陰影圖紋素(即s(p1)=s(p2)=s,由於分辨率的原因)。當我們在執行陰影圖檢測時,會得到d(p1) > s 及 d(p2) <= s這兩個測試結果,這樣一來,p1將會被繪製為如同它在陰影中的顏色,p2將被渲染為好似它在陰影之外的顏色,從而導致陰影粉刺。

    因此,我們可以通過偏移陰影圖中的深度值來防止出現錯誤的陰影效果。此時我們就可以保證d(p1) <= s 及 d(p2) <= s。但是尋找合適的深度偏移需要反覆嘗試。

    偏移量過大會導致名為peter-panning(彼得·潘,即小飛俠,他曾在一次逃跑時弄丟了自己的影子)的失真效果,使得陰影看起來與物體相分離。

    然而,並沒有哪一種固定的偏移量可以正確地運用於所有幾何體的陰影繪製。特別是下圖那種(從光源的角度來看)有着極大斜率的三角形,這時候就需要選取更大的偏移量。但是,如果試圖通過一個過大的深度偏移量來處理所有的斜邊,則又會造成peter-panning問題。

    因此,我們繪製陰影的方式就是先以光源視角度量多邊形斜面的斜率,併為斜率較大的多邊形應用更大的偏移量。而圖形硬件內部對此有相關技術的支持,我們通過名為斜率縮放偏移的光柵化狀態屬性就能夠輕鬆實現。

    typedef struct D3D11_RASTERIZER_DESC {
        // ...
        INT             DepthBias;
        FLOAT           DepthBiasClamp;
        FLOAT           SlopeScaledDepthBias;
        BOOL            DepthClipEnable;
        // ...
    } D3D11_RASTERIZER_DESC;
    
    1. DepthBias:一個固定的應用偏移量。
    2. DepthBiasClamp:所允許的最大深度偏移量。以此來設置深度偏移量的上限。不難想象,及其陡峭的傾斜度會導致斜率縮放偏移量過大,從而造成peter-panning失真
    3. SlopeScaledDepthBias:根據多邊形的斜率來控制偏移程度的縮放因子。

    注意,在將場景渲染至陰影貼圖時,便會應用該斜率縮放偏移量。這是由於我們希望以光源的視角基於多邊形的斜率而進行偏移操作,從而避免陰影失真。因此,我們就會對陰影圖中的數值進行偏移計算(即由硬件將像素的深度值與偏移值相加)。在本Demo中採用的具體數值如下:

    // [出自MSDN]
    // 如果當前的深度緩衝區採用UNORM格式並且綁定在輸出合併階段,或深度緩衝區還沒有被綁定
    // 則偏移量的計算過程如下:
    //
    // Bias = (float)DepthBias * r + SlopeScaledDepthBias * MaxDepthSlope;
    //
    // 這裏的r是在深度緩衝區格式轉換為float32類型后,其深度值可取到大於0的最小可表示的值
    // MaxDepthSlope則是像素在水平方向和豎直方向上的深度斜率的最大值
    // [結束MSDN引用]
    //
    // 對於一個24位的深度緩衝區來說, r = 1 / 2^24
    //
    // 例如:DepthBias = 100000 ==> 實際的DepthBias = 100000/2^24 = .006
    //
    // 本Demo中的方向光始終與地面法線呈45度夾角,故取斜率為1.0f
    // 以下數據極其依賴於實際場景,因此我們需要對特定場景反覆嘗試才能找到最合適
    rsDesc.DepthBias = 100000;
    rsDesc.DepthBiasClamp = 0.0f;
    rsDesc.SlopeScaledDepthBias = 1.0f
    

    注意:深度偏移發生在光柵化期間(裁剪之後),因此不會對幾何體裁剪造成影響。

    RenderStates中我們添加了這樣一個光柵化狀態:

    // 深度偏移模式
    rasterizerDesc.FillMode = D3D11_FILL_SOLID;
    rasterizerDesc.CullMode = D3D11_CULL_BACK;
    rasterizerDesc.FrontCounterClockwise = false;
    rasterizerDesc.DepthClipEnable = true;
    rasterizerDesc.DepthBias = 100000;
    rasterizerDesc.DepthBiasClamp = 0.0f;
    rasterizerDesc.SlopeScaledDepthBias = 1.0f;
    HR(device->CreateRasterizerState(&rasterizerDesc, RSDepth.GetAddressOf()));
    

    MSDN文檔Depth Bias講述了該技術相關的全部規則,並且介紹了如何使用浮點深度緩衝區進行工作。

    百分比漸近過濾(PCF)

    在使用投影紋理坐標(u, v)對陰影圖進行採樣時,往往不會命中陰影圖中紋素的準確位置,而是通常位於陰影圖中的4個紋素之間。然而,我們不應該對深度值採用雙線性插值法,因為4個紋素之間的深度值不一定滿足線性過渡,插值出來的深度值跟實際的深度值有偏差,這樣可能會導致把像素錯誤標入陰影中這樣的錯誤結果(因此我們也不能為陰影圖生成mipmap)。

    出於這樣的原因,我們應該對採樣的結果進行插值,而不是對深度值進行插值。這種做法稱為——百分比漸近過濾。即我們以點過濾(MIN_MAG_MIP_POINT)的方式在坐標(u, v)、(u+△x, v)、(u, v+△x)、(u+△x, v+△x)處對紋理進行採樣,其中△x=1/SHADOW_MAP_SIZE(除以的是引用貼圖的寬高)。由於是點採樣,這4個採樣點分別命中的是圍繞坐標(u, v)最近的4個陰影圖紋素s0、s1、s2、s3,如下圖所示。

    接下來,我們會對這些採集的深度值進行陰影圖檢測,並對測試的結果展開雙線性插值。

    static const float SMAP_SIZE = 2048.0f;
    static const float SMAP_DX = 1.0f / SMAP_SIZE;
    
    // ...
    
    //
    // 採樣操作
    //
    
    // 對陰影圖進行採樣以獲取離光源最近的深度值
    float s0 = g_ShadowMap.Sample(g_SamShadow, tex.xy).r;
    float s1 = g_ShadowMap.Sample(g_SamShadow, tex.xy + float2(SMAP_DX, 0)).r;
    float s2 = g_ShadowMap.Sample(g_SamShadow, tex.xy + float2(0, SMAP_DX)).r;
    float s3 = g_ShadowMap.Sample(g_SamShadow, tex.xy + float2(SMAP_DX, SMAP_DX)).r;
    
    // 該像素的深度值是否小於等於陰影圖中的深度值
    float r0 = (depth <= s0);
    float r1 = (depth <= s1);
    float r2 = (depth <= s2);
    float r3 = (depth <= s3);
    
    //
    // 雙線性插值操作
    //
    
    // 變換到紋素空間
    float2 texelPos = SMAP_SIZE * tex.xy;
    
    // 確定插值係數(frac()返回浮點數的小數部分)
    float2 t = frac(texelPos);
    
    // 對比較結果進行雙線性插值
    return lerp(lerp(r0, r1, t.x), lerp(r2, r3, t.x), t.y);
    
    

    若採用這種計算方法,則一個像素就可能局部處於陰影之中,而不是非0即1.例如,若有4個樣本,三個在陰影中,一個在陰影外,那麼該像素有75%處於陰影之中。這就讓陰影內外的像素之間有了更加平滑的過渡,而不是稜角分明。

    但這種過濾方法產生的陰影看起來仍然非常生硬,且鋸齒失真問題的最終處理效果還是不能令人十分滿意。PCF的主要缺點是需要4個紋理樣本,而紋理採樣本身就是現代GPU代價較高的操作之一,因為存儲器的帶寬與延遲並沒有隨着GPU計算能力的劇增而得到相近程度的巨大改良。幸運的是,Direct3D 11+版本的圖形硬件對PCF技術已經有了內部支持,上面的一大堆代碼可以用SampleCmpLevelZero函數來替代。

    float percentage = g_ShadowMap.SampleCmpLevelZero(g_SamShadow, shadowPosH.xy, depth).r;
    

    方法中的LevelZero部分意味着它只能在最高的mipmap層級中進行採樣。另外,該方法使用的並非一般的採樣器對象,而是比較採樣器。這使得硬件能夠執行陰影圖的比較測試,並且需要在過濾採樣結果之前完成。對於PCF技術來說,我們需要使用的是D3D11_FILTER_COMPARISON_MIN_MAG_LINEAR_MIP_POINT過濾器,並將比較函數設置為LESS_EQUAL(由於對深度值進行了偏移,所以也要用到LESS比較函數)。

    函數中傳入的depth將會出現在比較運算符的左邊,即:

    depth <= sampleDepth
    

    RenderStates中我們添加了這樣一個採樣器:

    ComPtr<ID3D11SamplerState> RenderStates::SSShadow = nullptr;
    
    // 採樣器狀態:深度比較與Border模式
    ZeroMemory(&sampDesc, sizeof(sampDesc));
    sampDesc.Filter = D3D11_FILTER_COMPARISON_MIN_MAG_LINEAR_MIP_POINT;
    sampDesc.AddressU = D3D11_TEXTURE_ADDRESS_BORDER;
    sampDesc.AddressV = D3D11_TEXTURE_ADDRESS_BORDER;
    sampDesc.AddressW = D3D11_TEXTURE_ADDRESS_BORDER;
    sampDesc.ComparisonFunc = D3D11_COMPARISON_LESS_EQUAL;
    sampDesc.BorderColor[0] = { 1.0f };
    sampDesc.MinLOD = 0;
    sampDesc.MaxLOD = D3D11_FLOAT32_MAX;
    HR(device->CreateSamplerState(&sampDesc, SSShadow.GetAddressOf()));
    

    注意:根據SDK文檔所述,只有R32_FLOAT_X8X24_TYPELESSR32_FLOATR24_UNORM_X8_TYPELESSR16_UNORM格式才能用於比較過濾器。

    在PCF的基礎上進行均值濾波

    到目前為止,我們在本節中一直使用的是4-tap PCF核(輸入4個樣本來執行的PCF)。PCF核越大,陰影的邊緣輪廓也就越豐滿、越平滑,當然,花費在SampleCmpLevelZero函數上的開銷也就越大。在本Demo中,我們是按3×3正方形的均值濾波方式來執行PCF。由於每次調用SampleCmpLevelZero函數實際所執行的都是4-tap PCF,所以一共採樣了36次,其中有4×4個獨立採樣點。此外,採用過大的濾波核還會導致之前所述的陰影粉刺問題,但本章不打算講述,有興趣可以回到龍書閱讀(過大的PCF核)。

    顯然,PCF技術一般來說只需在陰影的邊緣進行,因為陰影內外兩部分並不涉及混合操作(只有陰影邊緣才是漸變的)。基於此,只要能對陰影邊緣的PCF設計相應的處理方案就好了。但這種做法一般要求我們所用的PCF核足夠大(5×5及更大)時才划算(因為動態分支也有開銷)。不過最終是要效率還是要畫質還是取決於你自己。

    注意:實際工程中所用的PCF核不一定是方形的過濾柵格。不少文獻也指出,隨機的拾取點也可以作為PCF核。

    考慮到在做比較時,如果處於陰影外的值為1,在陰影內的值為0,在採用SampleCmpLevelZero和均值濾波后,我們用範圍值0~1來表示處於陰影外的程度。隨着值的增加,該點也變得越亮。我們可以使用下面的函數來計算3×3正方形的均值濾波下的陰影因子:

    float CalcShadowFactor(SamplerComparisonState samShadow, Texture2D shadowMap, float4 shadowPosH)
    {
    	// 透視除法
        shadowPosH.xyz /= shadowPosH.w;
    	
    	// NDC空間的深度值
        float depth = shadowPosH.z;
    
    	// 紋素在紋理坐標下的寬高
        const float dx = SMAP_DX;
    
        float percentLit = 0.0f;
        const float2 offsets[9] =
        {
            float2(-dx, -dx), float2(0.0f, -dx), float2(dx, -dx),
    		float2(-dx, 0.0f), float2(0.0f, 0.0f), float2(dx, 0.0f),
    		float2(-dx, +dx), float2(0.0f, +dx), float2(dx, +dx)
        };
                          
    	[unroll]
        for (int i = 0; i < 9; ++i)
        {
            percentLit += shadowMap.SampleCmpLevelZero(samShadow,
    			shadowPosH.xy + offsets[i], depth).r;
        }
        
        return percentLit /= 9.0f;
    }
    

    然後在我們的光照模型中,只有第一個方向光才參与到陰影的計算,並且陰影因子將與直接光照(漫反射和鏡面反射光)項相乘。

    // ...
    float shadow[5] = { 1.0f, 1.0f, 1.0f, 1.0f, 1.0f };
     
    // 僅第一個方向光用於計算陰影
    shadow[0] = CalcShadowFactor(g_SamShadow, g_ShadowMap, pIn.ShadowPosH);
        
    [unroll]
    for (i = 0; i < 5; ++i)
    {
        ComputeDirectionalLight(g_Material, g_DirLight[i], pIn.NormalW, toEyeW, A, D, S);
        ambient += A;
        diffuse += shadow[i] * D;
        spec += shadow[i] * S;
    }
    
    // ...
    

    由於環境光是間接光,所以陰影因子不受影響。並且,陰影因子也不會對來自環境映射的反射光構成影響。

    C++端代碼實現

    EffectHelper的引入

    本章開始的代碼引入了EffectHelper來管理着色器所需的資源(我們可以無需手動創建並交給它來託管),並應用在了所有的Effect類當中。除了IEffect接口類,目前還引入了IEffectTransform接口類來統一變換的設置。隨着抽象類的增加,像GameObject這樣的類就可以對IEffect接口類對象查詢是否有某一特定接口類或具體類來執行額外的複雜操作。

    此外,SkyRender類也因此有了輕微的變動。具體想了解還是去源碼翻閱,這裏不展開。

    構建陰影貼圖與更新

    首先我們要在GameApp::InitResource中創建一副2048×2048的陰影貼圖:

    m_pShadowMap = std::make_unique<TextureRender>();
    HR(m_pShadowMap->InitResource(m_pd3dDevice.Get(), 2048, 2048, true));
    

    在本Demo中,光照方向每幀都在變動,我們希望讓投影立方體與光照所屬的變換軸對齊,並且中心能夠坐落在原點。因此在GameApp::UpdateScene可以這麼做:

    //
    // 投影區域為正方體,以原點為中心,以方向光為+Z朝向
    //
    XMMATRIX LightView = XMMatrixLookAtLH(dirVec * 20.0f * (-2.0f), g_XMZero, g_XMIdentityR1);
    m_pShadowEffect->SetViewMatrix(LightView);
    
    // 將NDC空間 [-1, +1]^2 變換到紋理坐標空間 [0, 1]^2
    static XMMATRIX T(
        0.5f, 0.0f, 0.0f, 0.0f,
        0.0f, -0.5f, 0.0f, 0.0f,
        0.0f, 0.0f, 1.0f, 0.0f,
        0.5f, 0.5f, 0.0f, 1.0f);
    // S = V * P * T
    m_pBasicEffect->SetShadowTransformMatrix(LightView * XMMatrixOrthographicLH(40.0f, 40.0f, 20.0f, 60.0f) * T);
    

    至於繪製部分,本Demo將和陰影有聯繫的場景對象放入了另一個重載函數DrawScene中(具體實現不在這給出),總體情況如下:

    void GameApp::DrawScene()
    {
        // ...
    
        // ******************
        // 繪製到陰影貼圖
    
        m_pShadowMap->Begin(m_pd3dImmediateContext.Get(), nullptr);
        {
            DrawScene(true);
        }
        m_pShadowMap->End(m_pd3dImmediateContext.Get());
    
        // ******************
        // 正常繪製場景
        m_pBasicEffect->SetTextureShadowMap(m_pShadowMap->GetOutputTexture());
        DrawScene(false, m_EnableNormalMap);
    
        // 繪製天空盒
        m_pDesert->Draw(m_pd3dImmediateContext.Get(), *m_pSkyEffect, *m_pCamera);
    
        // 解除深度緩衝區綁定
        m_pBasicEffect->SetTextureShadowMap(nullptr);
        m_pBasicEffect->Apply(m_pd3dImmediateContext.Get());
    
        // ...
    
    }
    

    演示

    本Demo提供了5種斜率下的方向光,對應主鍵盤数字鍵1-5,Q鍵開關法線貼圖,E鍵開關陰影貼圖的显示,G鍵切換陰影貼圖的显示模式。

    透明物體的陰影繪製

    但我們的例程還沒有處理透明物體的陰影繪製。如果我們直接在場景中繪製一顆樹(貼圖存在Alpha值為0的部分),可以看到下圖的陰影並不正確:

    因此,我們需要在繪製陰影貼圖的時候增加一個像素着色器用以進行Alpha裁剪,把Alpha值低於0.1的紋素給剔除掉,不要讓其寫入到陰影貼圖:

    Texture2D g_DiffuseMap : register(t0);
    SamplerState g_Sam : register(s0);
    
    struct VertexPosHTex
    {
        float4 PosH : SV_POSITION;
        float2 Tex : TEXCOORD;
    };
    
    // 這僅僅用於Alpha幾何裁剪,以保證陰影的显示正確。
    // 對於不需要進行紋理採樣操作的幾何體可以直接將像素
    // 着色器設為nullptr
    void PS(VertexPosHTex pIn)
    {
        float4 diffuse = g_DiffuseMap.Sample(g_Sam, pIn.Tex);
        
        // 不要將透明像素寫入深度貼圖
        clip(diffuse.a - 0.1f);
    }
    
    

    我們只在繪製樹的時候使用帶有像素着色器的版本,其餘物體照常繪製。並且因為我們的BasicEffect默認繪製就帶有Alpha裁剪,無需做這部分改動。最終效果如下:

    練習題

    1. 嘗試4096×4096、1024×1024、512×512、256×256這幾種不同分辨率的陰影貼圖
    2. 嘗試以單次點採樣陰影檢測來修改本演示程序(即不採用PCF)。我們將欣賞到硬陰影與鋸齒狀的陰影邊緣
    3. 關閉斜率縮放偏移來觀察陰影粉刺
    4. 將斜率縮放偏移值放大10倍,觀察peter panning失真的效果
    5. 實現單點光源下的陰影(必要時可以考慮像CubeMap那樣使用6個正方形貼圖)
    6. 修改項目代碼,把繪製房屋改成繪製上圖中的樹(模型已給出),要求陰影显示正確

    DirectX11 With Windows SDK完整目錄

    Github項目源碼

    歡迎加入QQ群: 727623616 可以一起探討DX11,以及有什麼問題也可以在這裏彙報。

    本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    台北網頁設計公司這麼多該如何選擇?

    ※智慧手機時代的來臨,RWD網頁設計為架站首選

    ※評比南投搬家公司費用收費行情懶人包大公開

    ※回頭車貨運收費標準

    網頁設計最專業,超強功能平台可客製化

    ※別再煩惱如何寫文案,掌握八大原則!

  • Spring事務的傳播屬性

    前言

    Spring在TransactionDefinition接口中規定了7種類型的事務傳播行為。事務傳播行為是Spring框架獨有的事務增強特性,他不屬於的事務實際提供方數據庫行為。這是Spring為我們提供的強大的工具箱,使用事務傳播行可以為我們的開發工作提供許多便利。但是人們對他的誤解也頗多,你一定也聽過“service方法事務最好不要嵌套”的傳言。要想正確的使用工具首先需要了解工具。

    基礎概念

    1. 什麼是事務傳播行為?

    事務傳播行為用來描述由某一個事務傳播行為修飾的方法被嵌套進另一個方法的時事務如何傳播。

    用偽代碼說明:

    1 @Transaction(Propagation=XXX)
    2  public void methodA(){
    3     methodB();
    4     //doSomething
    5  }
    6  
    7  public void methodB(){
    8     //doSomething
    9  }

    methodA中存在事務,他又調用了methodB。methodB事物的一些特性由methodA決定,這就是事務的傳播行為。

    2. Spring中七種事務傳播行為

    事務傳播行為類型 說明
    PROPAGATION_REQUIRED 如果當前沒有事務,就新建一個事務,如果已經存在一個事務中,加入到這個事務中。這是最常見的選擇。
    PROPAGATION_SUPPORTS 支持當前事務,如果當前沒有事務,就以非事務方式執行。
    PROPAGATION_MANDATORY 使用當前的事務,如果當前沒有事務,就拋出異常。
    PROPAGATION_REQUIRES_NEW 新建事務,如果當前存在事務,把當前事務掛起。
    PROPAGATION_NOT_SUPPORTED 以非事務方式執行操作,如果當前存在事務,就把當前事務掛起。
    PROPAGATION_NEVER 以非事務方式執行,如果當前存在事務,則拋出異常。
    PROPAGATION_NESTED 如果當前存在事務,則在嵌套事務內執行。如果當前沒有事務,則執行與PROPAGATION_REQUIRED類似的操作。

    定義非常簡單,也很好理解,下面我們就進入代碼測試部分,驗證我們的理解是否正確。

    代碼驗證

    第一種情況。內部均為 propagation = Propagation.REQUIRED

     1 @Transactional(propagation = Propagation.REQUIRED, isolation = Isolation.REPEATABLE_READ)  2 @Override
     3 public void testTransactional() {
     4     int insert = downloadImgDao.test1();
     5     log.info("insert1 = {}", insert);
     6 
     7     insert = downloadImgDao.test2();
     8     log.info("insert2 = {}", insert);
     9 }
    10 
    11 @Transactional(propagation = Propagation.REQUIRED, isolation = Isolation.REPEATABLE_READ) 12 @Override
    13 public int test1() {
    14     DownloadImg downloadImg = new DownloadImg();
    15     downloadImg.setId(666L);
    16     downloadImg.setLink("張三");
    17     downloadImg.setLinkname("16");
    18     int res = downloadImgMapper.insertSelective(downloadImg);
    19     log.info("res1 = {}", res);
    20     return res;
    21 }
    22 
    23 
    24 @Transactional(propagation = Propagation.REQUIRED, isolation = Isolation.REPEATABLE_READ) 25 @Override
    26 public int test2() {
    27     DownloadImg downloadImg = new DownloadImg();
    28     downloadImg.setId(888L);
    29     downloadImg.setLink("李四");
    30     downloadImg.setLinkname("18");
    31     int res = downloadImgMapper.insertSelective(downloadImg);
    32     log.info("res2 = {}", res);
    33 
    34     int i = 5 / 0;
    35     return res;
    36 }

    張三,李四插入均失敗。

     

    第二種情況。內部一種為 propagation = Propagation.REQUIRED,一種為Propagation.REQUIRES_NEW

     1 @Transactional(propagation = Propagation.REQUIRES_NEW, isolation = Isolation.REPEATABLE_READ)  2 @Override
     3 public int test1() {
     4     DownloadImg downloadImg = new DownloadImg();
     5     downloadImg.setId(666L);
     6     downloadImg.setLink("張三");
     7     downloadImg.setLinkname("16");
     8     int res = downloadImgMapper.insertSelective(downloadImg);
     9     log.info("res1 = {}", res);
    10     return res;
    11 }
    12 
    13 
    14 @Transactional(propagation = Propagation.REQUIRED, isolation = Isolation.REPEATABLE_READ) 15 @Override
    16 public int test2() {
    17     DownloadImg downloadImg = new DownloadImg();
    18     downloadImg.setId(888L);
    19     downloadImg.setLink("李四");
    20     downloadImg.setLinkname("18");
    21     int res = downloadImgMapper.insertSelective(downloadImg);
    22     log.info("res2 = {}", res);
    23 
    24     int i = 5 / 0;
    25     return res;
    26 }

    張三插入成功,李四插入失敗。

     

    第三種情況。內部均為Propagation.REQUIRES_NEW

    跟我們現象的是一樣的,如果哪個test異常,哪個就失敗,無異常的就成功。

    還有一種情況是,外圍拋異常了,內部都不拋異常,兩種內部插入也都會成功。

    結論

    本程序是實驗了PROPAGATION_REQUIRED以及Propagation.REQUIRES_NEW。

    事務默認以PROPAGATION_REQUIRED來隔離。

    1: 如果內部是PROPAGATION_REQUIRED隔離級別,內部只要一個方法出錯,那麼整個事務都會回滾。

    2: 如果內部有方法以Propagation.REQUIRES_NEW來隔離。那麼他會創建一個新的事務來運行,如果他拋異常了,並不會影響其他事務的以及外部的事務。

     

    spring事務官方文檔:https://docs.spring.io/spring/docs/5.2.6.RELEASE/spring-framework-reference/data-access.html#tx-propagation

    參考文檔:https://segmentfault.com/a/1190000013341344

     

    本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

    南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

    ※教你寫出一流的銷售文案?

    ※超省錢租車方案

    ※回頭車貨運收費標準

  • (數據科學學習手札86)全平台支持的pandas運算加速神器

    (數據科學學習手札86)全平台支持的pandas運算加速神器

    本文示例代碼已上傳至我的Github倉庫https://github.com/CNFeffery/DataScienceStudyNotes

    1 簡介

      隨着其功能的不斷優化與擴充,pandas已然成為數據分析領域最受歡迎的工具之一,但其仍然有着一個不容忽視的短板——難以快速處理大型數據集,這是由於pandas中的工作流往往是建立在單進程的基礎上,使得其只能利用單個處理器核心來實現各種計算操作,這就使得pandas在處理百萬級、千萬級甚至更大數據量時,出現了明顯的性能瓶頸。

      本文要介紹的工具modin就是一個致力於在改變代碼量最少的前提下,調用起多核計算資源,對pandas的計算過程進行并行化改造的Python庫,並且隨着其近期的一系列內容更新,modin基於Dask開始對Windows系統同樣進行了支持,使得我們只需要改變一行代碼,就可以在所有平台上獲得部分pandas功能可觀的計算效率提升。

    圖1

    2 基於modin的pandas運算加速

      modin支持WindowsLinux以及Mac系統,其中LinuxMac平台版本的modin工作時可基於并行運算框架RayDask,而Windows平台版本目前只支持Dask作為計算後端(因為Ray沒有Win版本),安裝起來十分方便,可以用如下3種命令來安裝具有不同後端的modin

    pip install modin[dask] # 安裝dask後端
    pip install modin[ray] # 安裝ray後端(windows不支持)
    pip install modin[all] # 推薦方式,自動安裝當前系統支持的所有後端
    

      本文在Win10系統上演示modin的功能,執行命令:

    pip install modin[all]
    

      成功安裝modin+dask之後,在使用modin時,只需要將我們習慣的import pandas as pd變更為import modin.pandas as pd即可,接下來我們來看一下在一些常見功能上,pandasVSmodin性能差異情況,首先我們分別使用pandasmodin讀入一個大小為1.1G的csv文件esea_master_dmg_demos.part1.csv,來自kaggle(https://www.kaggle.com/skihikingkevin/csgo-matchmaking-damage/data),記錄了關於熱門遊戲CS:GO的一些玩家行為數據,因為體積過大,請感興趣的讀者朋友自行去下載:

    圖2

      為了區分他們,在導入時暫時將modin.pandas命名為mpd

    圖3

      可以看到因為是Win平台,所以使用的計算後端為Dask,首先我們來分別讀入文件查看耗時:

    圖4

      藉助jupyter notebook記錄計算時間的插件,可以看到原生的pandas耗時14.8秒,而modin只用了5.32秒,接着我們再來試試concat操作:

    圖5

      可以看到在pandas花了8.78秒才完成任務的情況下,modin僅用了0.174秒,取得了驚人的效率提升。接下來我們再來執行常見的檢查每列缺失情況的任務:

    圖6

      這時耗時差距雖然不如concat操作時那麼巨大,也是比較可觀的,但是modin畢竟是一個處理快速開發迭代階段的工具,其針對pandas的并行化改造尚未覆蓋全部的功能,譬如分組聚合功能。對於這部分功能,modin會在執行代碼時檢查自己是否支持,對於尚未支持的功能modin會自動切換到pandas單核後端來執行運算,但由於modin中組織數據的形式與pandas不相同,所以中間需要經歷轉換:

    圖7

      這種時候modin的運算反而會比pandas慢很多:

    圖8

      因此我對modin持有的態度是在處理大型數據集時,部分應用場景可以用其替換pandas,即其已經完成可靠并行化改造的pandas功能,你可以在官網對應界面(https://modin.readthedocs.io/en/latest/supported_apis/index.html )查看其已經支持及尚未良好支持的功能,,因為modin還處於快速開發階段,很多目前無法支持的功能也許未來不久就會被加入modin

    圖9

      以上就是本文的全部內容,如有疑問歡迎在評論區與我討論。

    本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※Google地圖已可更新顯示潭子電動車充電站設置地點!!

    ※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

    ※別再煩惱如何寫文案,掌握八大原則!

    網頁設計最專業,超強功能平台可客製化

    ※回頭車貨運收費標準

  • 樹莓派使用 OLED 屏显示圖片及文字

    樹莓派使用 OLED 屏显示圖片及文字

    樹莓派默認是不帶显示屏的,如果想要查看系統的一些信息,需要使用電腦登錄到樹莓派,或者通過 HDMI 連接外接显示器查看。這樣做總是有點麻煩,我們可以通過外接一個 OLED 屏來显示一些關鍵參數或者圖片。本文將詳細介紹操作方法。

    OLED 模組介紹

    OLED 屏主要有兩種:128×32 和 128×64 ,主要顏色是白、黃、藍。OLED 屏的特點是功耗低,價格便宜,使用 I2C 接口與主機連接。本文所使用的是 128×64 尺寸的屏幕,外形如下:

    它的接口很簡單,只有 4 個 Pin 腳:VCC,GND,SDA,SCL,所以它與樹莓派的連接也很簡單,如下圖所示(本文使用樹莓派 3B):

    開啟 I2C 接口

    樹莓派默認是不開啟 I2C 接口的,所以我們需要手動打開它。執行以下命令:

    $ sudo apt-get install -y python-smbus
    $ sudo apt-get install -y i2c-tools
    $ sudo raspi-config
    

    然後按以下動圖方式開啟 I2C 功能。

    安裝 OLED 屏的 Python 庫

    為了在 OLED 屏上显示文字或圖像,我們需要使用到 Adafruit 的 Python 庫,這個庫支持所有的 SSD1306 相關的显示屏,包括 128×32 和 128×64 屏幕。

    首先我們需要下載這個庫:

    $ git clone https://github.com/adafruit/Adafruit_Python_SSD1306.git
    

    然後進入到目錄,再進行安裝:

    $ cd Adafruit_Python_SSD1306
    $ sudo python3 setup.py install	# 如果使用 Python2 ,則使用對應命令
    

    找到 OLED 模組地址

    安裝好 Python 庫之後,我們可以使用 i2cdetect 命令來找到 OLED 屏的物理地址:

    $ i2cdetect -y 1
    

    我們會得到類似這樣的輸出:

    不同的模組可能得到不同的輸出。這裏我們的 I2C 地址就是 0x3C。如果你使用的是初代樹莓派(256MB的樹莓派1代B),那麼需要使用下面的命令:

    $ i2cdetect -y 0
    

    使用 OLED 屏显示圖像及文字

    在剛剛下載的那個庫文件里,有一個 examples 目錄,在那個目錄里,我們可以看到以下內容:

    • animate.py
    • buttons.py
    • image.py
    • shapes.py
    • stats.py

    這幾個文件我們可以直接運行,比如:

    $ python3 shapes.py
    

    這幾個文件運行的結果如下圖示:

    屏幕尺寸適配

    以上的幾個示例文件里,它們都默認你的屏幕尺寸是 128×32 ,但它們依然可以跑在 128×64 的屏幕上。如果我們想要看得更舒服一點,我們可以將尺寸進行適配。

    在每個 Python 文件里,都有下面這麼一段代碼:

    這裏也寫得很清楚了,上下兩行代碼分別代表 128×32 和 128×64 的屏幕,使用何種尺寸的屏幕,只需將對應的代碼前面的 # 去掉即可。

    公眾號:良許Linux

    有收穫?希望老鐵們來個三連擊,給更多的人看到這篇文章

    本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

    ※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

    ※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

    南投搬家公司費用需注意的眉眉角角,別等搬了再說!

    ※教你寫出一流的銷售文案?

    ※回頭車貨運收費標準

    ※別再煩惱如何寫文案,掌握八大原則!

  • 四、歸併排序 && 快速排序

    四、歸併排序 && 快速排序

    一、歸併排序 Merge Sort

    1.1、實現原理

    • 如果要排序一個數組,我們先把數組從中間分成前後兩部分,然後對前後兩部分分別排序,再將排好序的兩部分合併在一起,這樣整個數組就都有序了。
    • 歸併排序使用的就是分治思想。分治,顧名思義,就是分而治之,將一個大問題分解成小的子問題來解決。小的子問題解決了,大問題也就解決了。
    • 分治思想跟遞歸思想很像。分治算法一般都是用遞歸來實現的。 分治是一種解決問題的處理思想,遞歸是一種編程技巧,這兩者並不衝突。
    • 寫遞歸代碼的技巧就是,分析得出遞推公式,然後找到終止條件,最後將遞推公式翻譯成遞歸代碼。所以,要想寫出歸併排序的代碼,我們先寫出歸併排序的遞推公式。
    • 遞推公式:erge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
    • 終止條件:p >= r 不用再繼續分解
    • merge_sort(p…r)表示,給下標從 p 到 r 之間的數組排序。
    • 我們將這個排序問題轉化為了兩個子問題, merge_sort(p…q) 和 merge_sort(q+1…r),其中下標 q 等於 p 和 r 的中間位置,也就是 (p+r)/2。
    • 當下標從 p 到 q 和從 q+1 到 r 這兩個子數組都排好序之後,我們再將兩個有序的子數組合併在一起,這樣下標從 p 到 r 之間的數據就也排好序了。
    • 實現思路如下:
    /**
     * 歸併排序
     * @param arr 排序數據
     * @param n   數組大小
     */
    public static void merge_sort(int[] arr, int n) {
        merge_sort_c(arr, 0, n - 1);
    }
    
    // 遞歸調用函數
    public static void merge_sort_c(int[] arr, int p, int r) {
        // 遞歸終止條件
        if (p >= r) {
            return;
        }
        // 取p到r之間的中間位置q
        int q = (p + r) / 2;
    
        // 分治遞歸
        merge_sort_c(arr, p, q);
        merge_sort_c(arr, q + 1, r);
        // 將 arr[p...q] 和 arr[q+1...r] 合併為 arr[p...r]
        merge(arr[p...r],arr[p...q],arr[q + 1...r]);
    }
    
    • merge(arr[p…r], arr[p…q], arr[q + 1…r]) 這個函數的作用就是,將已經有序的 arr[p…q] 和 arr[q+1…r] 合併成一個有序的數組,並且放入 arr[p…r]。
    • 如下圖所示,我們申請一個臨時數組 tmp,大小與 arr[p…r] 相同。
    • 我們用兩個游標 i 和 j,分別指向 arr[p…q] 和 arr[q+1…r] 的第一個元素。
    • 比較這兩個元素 arr[i] 和 arr[j],如果 arr[i] <= arr[j],我們就把 arr[i] 放入到臨時數組 tmp,並且 i 后移一位,否則將 arr[j] 放入到數組 tmp,j 后移一位。
    • 繼續上述比較過程,直到其中一個子數組中的所有數據都放入臨時數組中,再把另一個數組中的數據依次加入到臨時數組的末尾,這個時候,臨時數組中存儲的就是兩個子數組合併之後的結果了。
    • 最後再把臨時數組 tmp 中的數據拷貝到原數組 arr[p…r] 中。
    /**
     * merge 合併函數
     * @param arr 數組
     * @param p   數組頭
     * @param q   數組中間位置
     * @param r   數組尾
     */
    public static void merge(int[] arr, int p, int q, int r) {
        if (r <= p) return;
    
        // 初始化變量i j k
        int i = p;
        int j = q + 1;
        int k = 0;
    
        // 申請一個大小跟A[p...r]一樣的臨時數組
        int[] tmp = new int[r - p + 1];
    
        // 比較排序移動到臨時數組
        while ((i <= q) && (j <= r)) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
    
        // 判斷哪個子數組中有剩餘的數據
        int start = i, end = q;
        if (j <= r) {
            start = j;
            end = r;
        }
    
        // 將剩餘的數據拷貝到臨時數組tmp
        while (start <= end) {
            tmp[k++] = arr[start++];
        }
    
        // 將tmp中的數組拷貝回 arr[p...r]
        for (int a = 0; a <= r - p; a++) {
            arr[p + a] = tmp[a];
        }
    }
    

    1.2、性能分析

    • 歸併排序穩不穩定關鍵要看 merge() 函數,也就是兩個有序子數組合併成一個有序數組的那部分代碼。
    • 在合併的過程中,如果 arr[p…q] 和 arr[q+1…r] 之間有值相同的元素,那我們可以像偽代碼中那樣,先把 arr[p…q] 中的元素放入 tmp 數組。
    • 這樣就保證了值相同的元素,在合併前後的先後順序不變。所以,歸併排序是一個穩定的排序算法
    • 其時間複雜度是非常穩定的,不管是最好情況、最壞情況,還是平均情況,時間複雜度都是 O(nlogn)
    • 歸併排序的合併函數,在合併兩個有序數組為一個有序數組時,需要藉助額外的存儲空間。
    • 儘管每次合併操作都需要申請額外的內存空間,但在合併完成之後,臨時開闢的內存空間就被釋放掉了。在任意時刻,CPU 只會有一個函數在執行,也就只會有一個臨時的內存空間在使用。
    • 臨時內存空間最大也不會超過 n 個數據的大小,所以空間複雜度是 O(n),不是原地排序算法。

    二、快速排序 Quicksort

    2.1、實現原理

    • 快排的思想是:如果要排序數組中下標從 p 到 r 之間的一組數據,可以選擇 p 到 r 之間的任意一個數據作為 pivot(分區點)。
    • 遍歷 p 到 r 之間的數據,將小於 pivot 的放到左邊,將大於 pivot 的放到右邊,將 pivot 放到中間。
    • 經過這一步驟之後,數組 p 到 r 之間的數據就被分成了三個部分,前面 p 到 q-1 之間都是小於 pivot 的,中間是 pivot,後面的 q+1 到 r 之間是大於 pivot 的。
    • 根據分治、遞歸的處理思想,可以用遞歸排序下標從 p 到 q-1 之間的數據和下標從 q+1 到 r 之間的數據,直到區間縮小為 1,就說明所有的數據都有序了。
    • 用遞推公式來將上面的過程寫出來的話,就是這樣:quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)。
    • 終止條件:p >= r
    /**
     * 快速排序
     * @param arr 排序數組
     * @param p 數組頭
     * @param r 數組尾
     */
    public static void quickSort(int[] arr, int p, int r) {
        if (p >= r) 
            return;
        // 獲取分區點 並移動數據
        int q = partition(arr, p, r);
        quickSort(arr, p, q - 1);
        quickSort(arr, q + 1, r);
    }
    

    partition() 分區函數:

    • 是隨機選擇一個元素作為 pivot(一般情況下,可以選擇 p 到 r 區間的最後一個元素),然後對 arr[p…r] 分區,並將小於 pivot 的放右邊,大於的放左邊,函數返回 pivot 的下標。

    partition() 的實現有兩種方式:

    • 一種是不考慮空間消耗,此時非常簡單。

      • 申請兩個臨時數組 X 和 Y,遍歷 arr[p…r],將小於 pivot 的元素都拷貝到臨時數組 X,將大於 pivot 的元素都拷貝到臨時數組 Y,最後再將數組 X 和數組 Y 中數據順序拷貝到arr[p…r]。
      /**
       * 分區函數方式一
       *
       * @param arr 數組
       * @param p   上標
       * @param r   下標
       * @return 函數返回 pivot 的下標
       */
      public static int partition1(int[] arr, int p, int r) {
          int[] xArr = new int[r - p + 1];
          int x = 0;
      
          int[] yArr = new int[r - p + 1];
          int y = 0;
      
          int pivot = arr[r];
      
          // 將小於 pivot 的元素都拷貝到臨時數組 X,將大於 pivot 的元素都拷貝到臨時數組 Y
          for (int i = p; i < r; i++) {
              // 小於 pivot 的存入 xArr 數組
              if (arr[i] < pivot) {
                  xArr[x++] = arr[i];
              }
              // 大於 pivot 的存入 yArr 數組
              if (arr[i] > pivot) {
                  yArr[y++] = arr[i];
              }
          }
      
          int q = x + p;
          // 再將數組 X 和數組 Y 中數據順序拷貝到 arr[p…r]
          for (int i = 0; i < x; i++) {
              arr[p + i] = xArr[i];
          }
          arr[q] = pivot;
          for (int i = 0; i < y; i++) {
              arr[q + 1 + i] = yArr[i];
          }
      
          return q;
      }
      
    • 另外一種有點類似選擇排序。

      • 我們通過游標 i 把 arr[p…r-1] 分成兩部分。arr[p…i-1] 的元素都是小於 pivot 的,我們暫且叫它“已處理區間”,arr[i…r-1] 是“未處理區間”。
      • 我們每次都從未處理的區間 arr[i…r-1] 中取一個元素 arr[j],與 pivot 對比,如果小於 pivot,則將其加入到已處理區間的尾部,也就是 arr[i]的位置。
      • 在數組某個位置插入元素,需要搬移數據,非常耗時。此時可以採用交換,在 O(1) 的時間複雜度內完成插入操作。需要將 arr[i] 與 arr[j] 交換,就可以在 O(1)時間複雜度內將 arr[j] 放到下標為 i 的位置。
      /**
       * 分區函數方式二
       * @param arr 數組
       * @param p   上標
       * @param r   下標
       * @return 函數返回pivot的下標
       */
      public static int partition2(int[] arr, int p, int r) {
          int pivot = arr[r];
          int i = p;
          for (int j = p; j < r; j++) {
              if (arr[j] < pivot) {
                  if (i == j) {
                      ++i;
                  } else {
                      int tmp = arr[i];
                      arr[i++] = arr[j];
                      arr[j] = tmp;
                  }
              }
          }
          int tmp = arr[i];
          arr[i] = arr[r];
          arr[r] = tmp;
          return i;
      }
      

    2.2、性能分析

    • 因為分區的過程涉及交換操作,如果數組中有兩個相同的元素,比如序列 6, 8, 7, 6, 3, 5, 9, 4,在經過第一次分區操作之後,兩個 6 的相對先後順序就會改變。所以,快速排序並不是穩定的排序算法
    • 按照上面的第二種分區方式,快速排序只涉及交換操作,所以空間複雜度為 Q(1),是原地排序算法
    • 時間複雜度為 Q(nlogn),最差為Q(n²)

    三、兩者對比

    歸併排序 快速排序
    排序思想 處理過程由下到上,先處理子問題,然後在合併 由上到下,先分區,在處理子問題
    穩定性
    空間複雜度 Q(n) Q(1) 原地排序算法
    時間複雜度 都為 O(nlogn) 平均為 O(nlogn),最差為 O(n²)
    • 歸併之所以是非原地排序算法,主要原因是合併函數無法在原地執行。快速排序通過設計巧妙的原地分區函數,可以實現原地排序,解決了歸併排序佔用太多內存的問題。
    • 歸併排序算法是一種在任何情況下時間複雜度都比較穩定的排序算法,這也使它存在致命的缺點,即歸併排序不是原地排序算法,空間複雜度比較高,是 O(n)。正因為此,它也沒有快排應用廣泛。

    本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

    【其他文章推薦】

    ※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

    網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

    ※想知道最厲害的網頁設計公司"嚨底家"!

    ※別再煩惱如何寫文案,掌握八大原則!

    ※產品缺大量曝光嗎?你需要的是一流包裝設計!

    ※回頭車貨運收費標準

    台中搬家公司費用怎麼算?