การตรวจจับพื้นผิวที่มองเห็นได้

เมื่อเราดูภาพที่มีวัตถุและพื้นผิวที่ไม่โปร่งใสเราจะมองไม่เห็นวัตถุเหล่านั้นจากมุมมองซึ่งอยู่ด้านหลังจากวัตถุที่อยู่ใกล้ตามากขึ้น เราต้องลบพื้นผิวที่ซ่อนอยู่เหล่านี้เพื่อให้ได้ภาพหน้าจอที่สมจริง การระบุและการกำจัดพื้นผิวเหล่านี้เรียกว่าHidden-surface problem.

มีสองวิธีในการขจัดปัญหาพื้นผิวที่ซ่อนอยู่ - Object-Space method และ Image-space method. เมธอด Object-space ถูกนำไปใช้ในระบบพิกัดทางกายภาพและใช้วิธีพื้นที่รูปภาพในระบบพิกัดหน้าจอ

เมื่อเราต้องการแสดงวัตถุ 3 มิติบนหน้าจอ 2 มิติเราจำเป็นต้องระบุส่วนต่างๆของหน้าจอที่มองเห็นได้จากตำแหน่งการรับชมที่เลือก

วิธีการบัฟเฟอร์ความลึก (Z-Buffer)

วิธีนี้พัฒนาโดย Cutmull เป็นแนวทางพื้นที่ภาพ แนวคิดพื้นฐานคือการทดสอบความลึก Z ของแต่ละพื้นผิวเพื่อกำหนดพื้นผิวที่ใกล้เคียงที่สุด (มองเห็นได้)

ในวิธีนี้แต่ละพื้นผิวจะถูกประมวลผลโดยแยกจากกันทีละตำแหน่งพิกเซลบนพื้นผิว ค่าความลึกของพิกเซลจะถูกเปรียบเทียบและพื้นผิว z ที่ใกล้ที่สุด (เล็กที่สุด) จะกำหนดสีที่จะแสดงในเฟรมบัฟเฟอร์

ใช้กับพื้นผิวของรูปหลายเหลี่ยมได้อย่างมีประสิทธิภาพ พื้นผิวสามารถประมวลผลตามลำดับใดก็ได้ หากต้องการลบล้างรูปหลายเหลี่ยมที่อยู่ใกล้กว่าจากรูปไกล ๆ ให้ตั้งชื่อบัฟเฟอร์สองตัวframe buffer และ depth buffer, ใช้

Depth buffer ใช้เพื่อเก็บค่าความลึกสำหรับตำแหน่ง (x, y) เนื่องจากพื้นผิวถูกประมวลผล (ความลึก 0 ≤≤ 1)

frame buffer ใช้เพื่อเก็บค่าความเข้มของค่าสีในแต่ละตำแหน่ง (x, y)

โดยปกติพิกัด z จะถูกทำให้เป็นมาตรฐานในช่วง [0, 1] ค่า 0 สำหรับพิกัด z ระบุบานหน้าต่างการตัดด้านหลังและ 1 ค่าสำหรับพิกัด z ระบุบานหน้าต่างการตัดด้านหน้า

อัลกอริทึม

Step-1 - ตั้งค่าบัฟเฟอร์ -

ความลึกบัฟเฟอร์ (x, y) = 0

Framebuffer (x, y) = สีพื้นหลัง

Step-2 - ประมวลผลรูปหลายเหลี่ยม (ทีละรูป)

สำหรับตำแหน่งพิกเซลที่ฉาย (x, y) แต่ละตำแหน่งของรูปหลายเหลี่ยมให้คำนวณความลึก z

ถ้า Z> ความลึกบัฟเฟอร์ (x, y)

คำนวณสีพื้นผิว

ตั้งค่าความลึกบัฟเฟอร์ (x, y) = z,

framebuffer (x, y) = สีพื้นผิว (x, y)

ข้อดี

  • ใช้งานง่าย
  • จะช่วยลดปัญหาความเร็วหากใช้ในฮาร์ดแวร์
  • มันประมวลผลทีละวัตถุ

ข้อเสีย

  • ต้องใช้หน่วยความจำขนาดใหญ่
  • เป็นกระบวนการที่ใช้เวลานาน

วิธีสแกนไลน์

เป็นวิธีการเว้นวรรคภาพเพื่อระบุพื้นผิวที่มองเห็นได้ วิธีนี้มีข้อมูลเชิงลึกสำหรับการสแกนบรรทัดเดียวเท่านั้น ในการกำหนดค่าความลึกของการสแกนเราต้องจัดกลุ่มและประมวลผลรูปหลายเหลี่ยมทั้งหมดที่ตัดกันเส้นสแกนที่กำหนดพร้อมกันก่อนที่จะประมวลผลบรรทัดการสแกนถัดไป ตารางสำคัญสองตารางedge table และ polygon table, ได้รับการบำรุงรักษาสำหรับสิ่งนี้

The Edge Table - ประกอบด้วยจุดสิ้นสุดพิกัดของแต่ละเส้นในฉากความชันผกผันของแต่ละเส้นและตัวชี้ในตารางรูปหลายเหลี่ยมเพื่อเชื่อมต่อขอบกับพื้นผิว

The Polygon Table - ประกอบด้วยค่าสัมประสิทธิ์ระนาบคุณสมบัติของวัสดุพื้นผิวข้อมูลพื้นผิวอื่น ๆ และอาจเป็นตัวชี้ไปยังตารางขอบ

เพื่ออำนวยความสะดวกในการค้นหาพื้นผิวที่ข้ามเส้นสแกนที่กำหนดจะมีการสร้างรายการขอบที่ใช้งานอยู่ รายการที่ใช้งานจะเก็บเฉพาะขอบที่ข้ามเส้นสแกนตามลำดับ x ที่เพิ่มขึ้น นอกจากนี้ยังมีการตั้งค่าสถานะสำหรับแต่ละพื้นผิวเพื่อระบุว่าตำแหน่งตามเส้นสแกนอยู่ภายในหรือภายนอกพื้นผิว

ตำแหน่งพิกเซลในแต่ละบรรทัดการสแกนจะถูกประมวลผลจากซ้ายไปขวา ที่จุดตัดด้านซ้ายที่มีพื้นผิวธงพื้นผิวจะเปิดอยู่และที่ด้านขวาธงจะปิด คุณจะต้องทำการคำนวณความลึกก็ต่อเมื่อมีการเปิดแฟล็กหลายพื้นผิวที่ตำแหน่งเส้นสแกนบางตำแหน่ง

วิธีการแบ่งพื้นที่

วิธีการแบ่งพื้นที่ใช้ประโยชน์โดยการค้นหาพื้นที่มุมมองที่แสดงถึงส่วนหนึ่งของพื้นผิวเดียว แบ่งพื้นที่การรับชมทั้งหมดออกเป็นรูปสี่เหลี่ยมขนาดเล็กและเล็กลงจนกระทั่งแต่ละพื้นที่เล็ก ๆ คือการฉายภาพของส่วนหนึ่งของพื้นผิวที่มองเห็นได้เพียงส่วนเดียวหรือไม่มีพื้นผิวเลย

ดำเนินการตามขั้นตอนนี้ต่อไปจนกว่าส่วนย่อยจะได้รับการวิเคราะห์อย่างง่ายดายว่าเป็นของพื้นผิวเดียวหรือจนกว่าจะลดขนาดลงเหลือเพียงพิกเซลเดียว วิธีง่ายๆในการทำเช่นนี้คือแบ่งพื้นที่ออกเป็นสี่ส่วนเท่า ๆ กันในแต่ละขั้นตอน มีความสัมพันธ์ที่เป็นไปได้สี่ประการที่พื้นผิวสามารถมีขอบเขตพื้นที่ที่ระบุได้

  • Surrounding surface - สิ่งที่ปิดล้อมพื้นที่อย่างสมบูรณ์

  • Overlapping surface - ส่วนที่อยู่ภายในและบางส่วนนอกพื้นที่

  • Inside surface - สิ่งที่อยู่ในพื้นที่อย่างสมบูรณ์

  • Outside surface - สิ่งที่อยู่นอกพื้นที่โดยสิ้นเชิง

การทดสอบเพื่อระบุการมองเห็นพื้นผิวภายในพื้นที่สามารถระบุได้ในรูปแบบของการจำแนกทั้งสี่นี้ ไม่จำเป็นต้องมีการแบ่งย่อยของพื้นที่ที่ระบุอีกต่อไปหากเงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง -

  • พื้นผิวทั้งหมดเป็นพื้นผิวภายนอกที่เกี่ยวกับพื้นที่
  • มีพื้นผิวด้านในซ้อนทับหรือโดยรอบเพียงด้านเดียวเท่านั้นที่อยู่ในพื้นที่
  • พื้นผิวโดยรอบบดบังพื้นผิวอื่น ๆ ทั้งหมดภายในขอบเขตพื้นที่

การตรวจจับใบหน้าด้านหลัง

วิธีการเว้นวรรควัตถุที่ง่ายและรวดเร็วในการระบุใบหน้าด้านหลังของรูปทรงหลายเหลี่ยมนั้นขึ้นอยู่กับการทดสอบ "ภายใน - ภายนอก" จุด (x, y, z) คือ "ภายใน" พื้นผิวรูปหลายเหลี่ยมที่มีพารามิเตอร์ระนาบ A, B, C และ D ถ้าเมื่อจุดภายในอยู่ตามแนวสายตาไปยังพื้นผิวรูปหลายเหลี่ยมจะต้องเป็นใบหน้าด้านหลัง ( เราอยู่ข้างในใบหน้านั้นและไม่สามารถมองเห็นด้านหน้าได้จากตำแหน่งการมองของเรา)

เราสามารถทำให้การทดสอบนี้ง่ายขึ้นโดยพิจารณาเวกเตอร์ปกติ N ไปยังพื้นผิวรูปหลายเหลี่ยมซึ่งมีส่วนประกอบของคาร์ทีเซียน (A, B, C)

โดยทั่วไปถ้า V เป็นเวกเตอร์ในทิศทางการมองจากตา (หรือตำแหน่ง "กล้อง") รูปหลายเหลี่ยมนี้จะเป็นหน้าหลังถ้า

V.N > 0

นอกจากนี้หากคำอธิบายวัตถุถูกแปลงเป็นพิกัดการฉายและทิศทางการรับชมของคุณขนานกับแกน z ที่ดูแล้ว -

V = (0, 0, V z ) และ V.N = V Z C

ดังนั้นเราต้องพิจารณาเฉพาะเครื่องหมายของ C ซึ่งเป็นส่วนประกอบของเวกเตอร์ปกติ N.

ในระบบการมองด้วยมือขวาที่มีทิศทางการมองตามแกน $ Z_ {V} $ เชิงลบรูปหลายเหลี่ยมจะเป็นหน้าหลังถ้า C <0 นอกจากนี้เราไม่สามารถมองเห็นใบหน้าใด ๆ ที่ปกติมีองค์ประกอบ z C = 0 เนื่องจากคุณ ทิศทางการดูจะไปทางรูปหลายเหลี่ยมนั้น ดังนั้นโดยทั่วไปเราสามารถระบุรูปหลายเหลี่ยมเป็นหน้าหลังได้หากเวกเตอร์ปกติมีค่าส่วนประกอบ az -

C <= 0

วิธีการที่คล้ายกันนี้สามารถใช้ได้ในแพ็กเกจที่ใช้ระบบการดูด้วยมือซ้าย ในแพ็กเกจเหล่านี้พารามิเตอร์ระนาบ A, B, C และ D สามารถคำนวณได้จากพิกัดจุดยอดรูปหลายเหลี่ยมที่ระบุในทิศทางตามเข็มนาฬิกา (ต่างจากทิศทางทวนเข็มนาฬิกาที่ใช้ในระบบมือขวา)

นอกจากนี้ใบหน้าด้านหลังยังมีเวกเตอร์ปกติที่ชี้อยู่ห่างจากตำแหน่งการมองเห็นและระบุโดย C> = 0 เมื่อทิศทางการรับชมอยู่ตามแกน $ Z_ {v} $ ที่เป็นบวก ด้วยการตรวจสอบพารามิเตอร์ C สำหรับระนาบต่างๆที่กำหนดวัตถุเราสามารถระบุใบหน้าด้านหลังทั้งหมดได้ทันที

วิธี A-Buffer

เมธอด A-buffer เป็นส่วนขยายของเมธอด deep-buffer วิธี A-buffer เป็นวิธีการตรวจจับการมองเห็นที่พัฒนาขึ้นที่ Lucas film Studios สำหรับระบบการเรนเดอร์แสดงทุกสิ่งที่คุณเคยเห็น (REYES)

A-buffer จะขยายในวิธีการบัฟเฟอร์ความลึกเพื่อให้แผ่นใส โครงสร้างข้อมูลหลักใน A-buffer คือบัฟเฟอร์การสะสม

แต่ละตำแหน่งใน A-buffer มีสองฟิลด์ -

  • Depth field - เก็บจำนวนจริงที่เป็นบวกหรือลบ

  • Intensity field - เก็บข้อมูลความเข้มของพื้นผิวหรือค่าตัวชี้

ถ้าความลึก> = 0 ตัวเลขที่เก็บไว้ที่ตำแหน่งนั้นคือความลึกของพื้นผิวเดียวที่ทับซ้อนกันในพื้นที่พิกเซลที่เกี่ยวข้อง จากนั้นฟิลด์ความเข้มจะเก็บส่วนประกอบ RGB ของสีพื้นผิว ณ จุดนั้นและเปอร์เซ็นต์ของการครอบคลุมพิกเซล

หากความลึก <0 แสดงว่ามีการสนับสนุนหลายพื้นผิวต่อความเข้มของพิกเซล จากนั้นฟิลด์ความเข้มจะจัดเก็บตัวชี้ไปยังรายการข้อมูลพื้นผิวที่เชื่อมโยงกัน บัฟเฟอร์พื้นผิวใน A-buffer ประกอบด้วย -

  • ส่วนประกอบความเข้ม RGB
  • พารามิเตอร์ความทึบ
  • Depth
  • เปอร์เซ็นต์ของพื้นที่ครอบคลุม
  • ตัวระบุพื้นผิว

อัลกอริทึมดำเนินการเช่นเดียวกับอัลกอริทึมบัฟเฟอร์ความลึก ค่าความลึกและความทึบใช้เพื่อกำหนดสีสุดท้ายของพิกเซล

วิธีการเรียงลำดับความลึก

วิธีการเรียงลำดับความลึกใช้ทั้งการดำเนินการพื้นที่ภาพและพื้นที่วัตถุ วิธีการเรียงลำดับความลึกทำหน้าที่พื้นฐานสองอย่าง -

  • ขั้นแรกพื้นผิวจะถูกจัดเรียงตามลำดับความลึกที่ลดลง

  • ประการที่สองพื้นผิวจะถูกแปลงตามลำดับโดยเริ่มจากพื้นผิวที่มีความลึกมากที่สุด

การแปลงการสแกนของพื้นผิวรูปหลายเหลี่ยมจะดำเนินการในพื้นที่ภาพ วิธีการแก้ปัญหาพื้นผิวที่ซ่อนอยู่นี้มักเรียกว่าpainter's algorithm. รูปต่อไปนี้แสดงผลของการเรียงลำดับความลึก -

อัลกอริทึมเริ่มต้นด้วยการจัดเรียงตามความลึก ตัวอย่างเช่นค่าประมาณ "ความลึก" เริ่มต้นของรูปหลายเหลี่ยมอาจถูกนำไปใช้เป็นค่า z ที่ใกล้เคียงที่สุดของจุดยอดใด ๆ ของรูปหลายเหลี่ยม

ให้เรานำรูปหลายเหลี่ยม P ที่ท้ายรายการ พิจารณารูปหลายเหลี่ยมทั้งหมด Q ที่มีส่วนขยาย z ทับซ้อนกันของ P ก่อนวาด P เราทำการทดสอบต่อไปนี้ หากการทดสอบใด ๆ ต่อไปนี้เป็นผลบวกเราก็ถือว่า P สามารถวาดได้ก่อน Q

  • x-extents ไม่ทับซ้อนกันหรือไม่?
  • ส่วนขยาย y ไม่ทับซ้อนกันหรือไม่?
  • P อยู่ฝั่งตรงข้ามของเครื่องบินของ Q จากมุมมองหรือไม่?
  • Q ทั้งหมดอยู่ด้านเดียวกับระนาบของ P กับมุมมองหรือไม่?
  • เส้นโครงของรูปหลายเหลี่ยมไม่ทับซ้อนกันหรือไม่?

หากการทดสอบทั้งหมดล้มเหลวเราจะแยก P หรือ Q โดยใช้ระนาบของอีกชุดหนึ่ง รูปหลายเหลี่ยมที่ตัดใหม่จะแทรกลงในลำดับความลึกและกระบวนการจะดำเนินต่อไป ในทางทฤษฎีการแบ่งพาร์ติชันนี้สามารถสร้าง O (n 2 ) รูปหลายเหลี่ยมแต่ละรูปได้ แต่ในทางปฏิบัติจำนวนรูปหลายเหลี่ยมจะน้อยกว่ามาก

ต้นไม้ Binary Space Partition (BSP)

การแบ่งพื้นที่ไบนารีใช้เพื่อคำนวณการมองเห็น ในการสร้างต้นไม้ BSP ควรเริ่มต้นด้วยรูปหลายเหลี่ยมและติดป้ายกำกับขอบทั้งหมด การจัดการกับขอบเพียงครั้งเดียวให้ขยายขอบแต่ละด้านเพื่อให้ระนาบแยกเป็นสองส่วน วางขอบแรกในต้นไม้เป็นราก เพิ่มขอบตามมาโดยขึ้นอยู่กับว่าอยู่ด้านในหรือด้านนอก ขอบที่ขยายส่วนขยายของขอบที่มีอยู่แล้วในต้นไม้จะถูกแบ่งออกเป็นสองส่วนและทั้งสองจะถูกเพิ่มเข้าไปในต้นไม้

  • จากรูปด้านบนก่อนอื่น A เป็นราก

  • ทำรายการโหนดทั้งหมดในรูป (a)

  • ใส่โหนดทั้งหมดที่อยู่หน้ารูท A ทางด้านซ้ายของโหนด A และใส่โหนดทั้งหมดที่อยู่หลังรูท A ไปทางด้านขวาดังแสดงในรูป (b)

  • ประมวลผลโหนดด้านหน้าทั้งหมดก่อนแล้วจึงดำเนินการกับโหนดด้านหลัง

  • ดังแสดงในรูป (c) เราจะประมวลผลโหนดก่อน B. เนื่องจากไม่มีอะไรอยู่ด้านหน้าโหนดBเราได้ใส่ NIL อย่างไรก็ตามเรามีโหนดC ที่ด้านหลังของโหนด Bดังนั้นโหนด C จะไปทางด้านขวาของโหนด B.

  • ทำซ้ำขั้นตอนเดียวกันสำหรับโหนด D.