การปรับปรุงการจำลองและประสิทธิภาพด้วยตัวแก้ปัญหาฟิสิกส์ขั้นสูง

ในปี 2016 เราได้เพิ่มการรองรับข้อจำกัดทางฟิสิกส์ที่หลากหลาย ซึ่งกระตุ้นให้นักพัฒนาเปลี่ยนไปใช้ตัวแก้ปัญหาใหม่และขยายขีดความสามารถในการสร้างสรรค์ของเอนจินฟิสิกส์ สถานที่ใหม่ทั้งหมดจะใช้ตัวแก้ปัญหา PGS เป็นค่าเริ่มต้น โดยมีตัวเลือกในการย้อนกลับไปใช้ตัวแก้ปัญหาแบบคลาสสิก

เราได้แก้ไขปัญหาความเสถียรที่เกี่ยวข้องกับค่าความแตกต่างของมวลสูงและกลไกที่ซับซ้อนโดยการแนะนำตัวแก้สมการแบบไฮบริด LDL-PGS ในช่วงกลางปี 2018 ซึ่งทำให้ตัวแก้สมการเก่าล้าสมัย และถูกปิดการใช้งานอย่างสมบูรณ์ในปี 2019 โดยอัตโนมัติทุกที่ไปยัง PGS

ในปี 2019 ประสิทธิภาพได้รับการปรับปรุงเพิ่มเติมโดยใช้การประมวลผลแบบมัลติเธรด ซึ่งแบ่งการจำลองออกเป็นงานย่อยที่ประกอบด้วยกลุ่มของชิ้นส่วนจำลองที่เชื่อมต่อกัน เรายังคงประสบปัญหาด้านประสิทธิภาพที่เกี่ยวข้องกับ LDL ซึ่งในที่สุดเราได้แก้ไขในช่วงต้นปี 2020

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

การนำกฎของฟิสิกส์ไปปฏิบัติ

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

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

การเคลื่อนที่เป็นผลมาจากการที่ตัวแก้ปัญหาตีความกฎของฟิสิกส์ เช่น การอนุรักษ์พลังงานและโมเมนตัม แต่การทำสิ่งนี้ให้ถูกต้อง 100% นั้นมีค่าใช้จ่ายสูงเกินไป และเคล็ดลับในการจำลองแบบเรียลไทม์คือการประมาณค่าเพื่อเพิ่มประสิทธิภาพ ตราบใดที่ผลลัพธ์ยังคงสมจริงทางกายภาพ ตราบใดที่กฎพื้นฐานของการเคลื่อนที่ยังคงอยู่ภายในขอบเขตที่ยอมรับได้ การแลกเปลี่ยนนี้ถือว่ายอมรับได้อย่างสมบูรณ์สำหรับการจำลองเกมคอมพิวเตอร์

ก้าวไปทีละเล็กทีละน้อย

แนวคิดหลักของเครื่องยนต์ฟิสิกส์คือการทำให้การเคลื่อนไหวเป็นแบบไม่ต่อเนื่องโดยใช้การก้าวเวลา (time-stepping) สมการการเคลื่อนไหวของวัตถุแข็งที่มีข้อจำกัดและไม่มีข้อจำกัดนั้นยากมากที่จะรวมเข้าด้วยกันโดยตรงและแม่นยำ การทำให้เป็นแบบไม่ต่อเนื่องจะแบ่งการเคลื่อนไหวออกเป็นส่วนย่อยๆ ของช่วงเวลาเล็กๆ ซึ่งสมการจะถูกทำให้ง่ายขึ้นและทำให้เป็นเชิงเส้น ทำให้สามารถแก้สมการได้ใกล้เคียงกับความจริงมากขึ้น ซึ่งหมายความว่าในแต่ละช่วงเวลาของการก้าวเวลา การเคลื่อนไหวของส่วนที่เกี่ยวข้องของวัตถุแข็งที่มีข้อจำกัดจะถูกประมาณค่าเป็นเชิงเส้น

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

การแก้ปัญหา

แอนิเมชันนี้แสดงวิธีที่ตัวแก้ PGS เปลี่ยนตำแหน่งของวัตถุแต่ละตัวในแต่ละขั้นตอนของกระบวนการวนซ้ำ โดยมีวัตถุประสงค์เพื่อหาตำแหน่งที่เคารพข้อจำกัดของลูกบอลและเบ้าในขณะที่รักษาจุดศูนย์กลางมวลไว้ในแต่ละขั้นตอน (นี่เป็นประเภทของตัวแก้ตำแหน่งที่ใช้โดย IK dragger) แม้ว่าตัวอย่างนี้จะมีวิธีแก้ปัญหาเชิงวิเคราะห์ที่ง่าย แต่ก็เป็นการสาธิตแนวคิดเบื้องหลัง PGS ได้เป็นอย่างดี ในแต่ละขั้นตอน ตัวแก้ปัญหาจะแก้ไขข้อจำกัดหนึ่งข้อและปล่อยให้อีกข้อหนึ่งถูกละเมิด หลังจากทำซ้ำหลายครั้ง ร่างกายจะเข้าใกล้ตำแหน่งที่ถูกต้องมากขึ้น ลักษณะเฉพาะของวิธีนี้คือวิธีที่ร่างกายแข็งบางชนิดดูเหมือนจะสั่นรอบตำแหน่งสุดท้าย โดยเฉพาะอย่างยิ่งเมื่อมีการจับคู่ปฏิสัมพันธ์กับร่างกายที่มีน้ำหนักมากกว่า หากเราไม่ทำซ้ำมากพอ ส่วนที่เป็นสีเหลืองอาจเหลืออยู่ในสถานะที่ไม่ถูกต้องอย่างเห็นได้ชัด โดยที่หนึ่งในข้อจำกัดสองข้อของมันถูกละเมิดอย่างรุนแรง สิ่งนี้เรียกว่าปัญหาอัตราส่วนมวลสูง และเป็นปัญหาที่กวนใจของเครื่องมือฟิสิกส์เนื่องจากทำให้เกิดความไม่เสถียรและการระเบิด หากเราทำซ้ำมากเกินไป ตัวแก้ปัญหาจะช้าเกินไป หากเราไม่ทำซ้ำมากพอ มันจะกลายเป็นไม่เสถียร การปรับสมดุลระหว่างทั้งสองด้านเป็นกระบวนการที่ยากลำบากและยาวนาน

กลยุทธ์การบรรเทาผลกระทบ

ตัวแก้ปัญหามีแหล่งที่มาของความไม่แม่นยำหลักสองประการ: การก้าวเวลา (time-stepping) และการแก้ปัญหาแบบวนซ้ำ (iterative solving) (นอกจากนี้ยังมีการคลาดเคลื่อนของจุดทศนิยม (floating point drift) แต่มีน้อยมากเมื่อเทียบกับสองประการแรก) ความไม่แม่นยำเหล่านี้ทำให้เกิดข้อผิดพลาดในการจำลอง ทำให้การจำลองเบี่ยงเบนจากเส้นทางที่ถูกต้อง บางส่วนของการเบี่ยงเบนนี้สามารถยอมรับได้ เช่น ความเร็วที่แตกต่างกันเล็กน้อยหรือการสูญเสียพลังงาน แต่บางส่วนไม่สามารถยอมรับได้ เช่น ความไม่เสถียร การเพิ่มพลังงานอย่างมาก หรือการเคลื่อนที่ผิดตำแหน่งของข้อจำกัด

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

1. การเริ่มต้นแบบอุ่น: เริ่มต้นด้วยคำตอบจากขั้นตอนเวลาครั้งก่อนเพื่อเพิ่มอัตราการลู่เข้าของตัวแก้แบบวนซ้ำ
2. หลังการทำให้เสถียร: การฉายระบบกลับไปยังปริภูมิข้อจำกัดเพื่อป้องกันการเบี่ยงเบนของข้อจำกัด
3. การทำให้เป็นไปตามข้อกำหนด: การเพิ่มการปฏิบัติตามข้อกำหนดเข้าไปในข้อจำกัดเพื่อให้แน่ใจว่ามีวิธีแก้ปัญหาและวิธีแก้ปัญหาดังกล่าวเป็นวิธีเดียว
4. การปรับสภาพล่วงหน้า: การใช้สารละลายที่แน่นอนสำหรับระบบย่อยเชิงเส้น เพื่อปรับปรุงเสถียรภาพของกลไกที่ซับซ้อน

กลยุทธ์ที่ 1, 2 และ 3 ค่อนข้างเป็นแบบดั้งเดิม แต่กลยุทธ์ที่ 3 ได้รับการปรับปรุงและพัฒนาให้สมบูรณ์แบบโดยเรา นอกจากนี้ แม้ว่ากลยุทธ์ที่ 4 จะไม่ใช่เรื่องที่ไม่เคยได้ยินมาก่อน แต่เรายังไม่เคยเห็นการนำไปใช้ในทางปฏิบัติ เราใช้วิธีการแยกปัจจัยแบบดั้งเดิมสำหรับเมทริกซ์ข้อจำกัดที่เบาบางขนาดใหญ่ และวิธีที่มีประสิทธิภาพใหม่ในการรวมเข้ากับ PGS การใช้งานที่ได้มีความช้ากว่า PGS เพียงเล็กน้อยเท่านั้น แต่รับประกันว่าระบบเชิงเส้นที่มาจากข้อจำกัดความเท่าเทียมกันจะถูกแก้ไขอย่างถูกต้อง ส่งผลให้ข้อจำกัดความเท่าเทียมกันได้รับผลกระทบเพียงจากการกระจายเวลาเท่านั้น รายละเอียดเกี่ยวกับวิธีการของเราอยู่ในงานนำเสนอ GDC 2020 ของฉัน ขณะนี้เรากำลังศึกษาวิธีการโดยตรงที่นำไปใช้กับข้อจำกัดที่ไม่เท่าเทียมกันและการชนกัน

รับรายละเอียดเพิ่มเติม

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

เราใช้สูตรที่สองเนื่องจากมีข้อจำกัดน้อยกว่าและต้องการคณิตศาสตร์และการนำไปใช้ที่ง่ายกว่ามาก

เครื่องยนต์ Roblox ใช้การวิเคราะห์เชิงคำนวณเพื่อคำนวณการตอบสนองแบบไดนามิกของข้อจำกัด ซึ่งแตกต่างจากวิธีการลงโทษที่เคยใช้มาก่อน วิธีการวิเคราะห์เชิงคำนวณถูกนำเสนอครั้งแรกในงานของ Baraff ในปี 1989 ซึ่งใช้วิธีนี้ในการจัดการกับข้อจำกัดทั้งแบบเท่ากันและไม่เท่ากันในลักษณะที่สอดคล้องกัน Baraff สังเกตว่าแบบจำลองการสัมผัสสามารถถูกกำหนดโดยใช้การโปรแกรมเชิงเส้นกำลังสอง และเขาได้เสนอวิธีการแก้ปัญหาแบบฮิวริสติก (ซึ่งไม่ใช่วิธีที่เราใช้ในตัวแก้ปัญหาของเรา)

แทนที่จะใช้การคำนวณแบบใช้แรง (force-based formulation) เราใช้การคำนวณแบบใช้แรงกระตุ้น (impulse-based formulation) ในพื้นที่ความเร็ว (velocity space) ซึ่งได้รับการแนะนำครั้งแรกโดย Mirtich-Canny ในปี 1995 และได้รับการปรับปรุงเพิ่มเติมโดย Stewart-Trinkle ในปี 1996 ซึ่งทำให้การจัดการกับประเภทการสัมผัสต่าง ๆ เป็นหนึ่งเดียว และรับประกันการมีอยู่ของคำตอบสำหรับการสัมผัสที่มีแรงเสียดทาน ในแต่ละช่วงเวลาที่กำหนด ข้อจำกัดและการชนจะถูกดูแลรักษาโดยการเปลี่ยนแปลงความเร็วในทันทีอันเนื่องมาจากแรงกระตุ้นของข้อจำกัด คำอธิบายที่ยอดเยี่ยมเกี่ยวกับเหตุผลที่การจำลองแบบใช้แรงกระตุ้นนั้นเหนือกว่าสามารถพบได้ในงานนำเสนอของ GDC โดย Catto ปี 2014

การสัมผัสที่ไร้แรงเสียดทานถูกจำลองโดยใช้ปัญหาการเสริมเชิงเส้น (Linear Complementarity Problem: LCP) ตามที่อธิบายไว้ใน Baraff 1994 แรงเสียดทานถูกเพิ่มเข้ามาโดยการฉายแบบไม่เชิงเส้นลงบนกรวยแรงเสียดทาน สลับกับการทำซ้ำของวิธี Projected Gauss-Seidel

การเลื่อนค่าตัวเลขที่ก่อให้เกิดข้อผิดพลาดในตำแหน่งของข้อจำกัดนั้นได้รับการแก้ไขโดยใช้เทคนิคหลังการเสถียรภาพซึ่งใช้ความเร็วเทียมที่แนะนำโดย Cline-Pai ในปี 2003 ซึ่งเกี่ยวข้องกับการแก้สมการ LCP ครั้งที่สองในพื้นที่ตำแหน่ง ซึ่งจะฉายระบบกลับไปยังปริภูมิข้อจำกัด

LCPs ถูกแก้ไขโดยใช้ PGS / Impulse Solver ที่ได้รับความนิยมจากงานของ Catto 2005 (ดูเพิ่มเติมที่ Catto 2009) วิธีนี้เป็นแบบวนซ้ำและพิจารณาข้อจำกัดแต่ละข้อตามลำดับและแก้ไขอย่างอิสระ ในหลายรอบการวนซ้ำ และในสภาวะที่เหมาะสม ระบบจะบรรจบกับคำตอบที่เป็นคำตอบรวม

นอกจากนี้ ปัญหาอัตราส่วนมวลสูงในข้อจำกัดความเท่าเทียมกันจะถูกแก้ไขโดยการเตรียมเงื่อนไขล่วงหน้าของ PGS โดยใช้การแยกย่อย LDL แบบบางของเมทริกซ์ข้อจำกัดที่เป็นความเท่าเทียมกัน เมทริกซ์ย่อยที่มีความหนาแน่นสูงของเมทริกซ์ข้อจำกัดจะถูกทำให้บางลงโดยใช้วิธีที่เราเรียกว่า Body Splitting ซึ่งคล้ายกับการแยกย่อย LDL ที่ใช้ในงานของ Baraff 1996 แต่รองรับระบบกลไกทั่วไปได้มากขึ้น และแก้ปัญหาในระบบพื้นที่ข้อจำกัด สำหรับข้อมูลเพิ่มเติม คุณสามารถดูการนำเสนอของฉันที่ GDC 2020

สถาปัตยกรรมของตัวแก้ของเราเป็นไปตามแนวคิดของ Guendelman-Bridson-Fedkiw ซึ่งการก้าวความเร็วและตำแหน่งถูกแยกออกโดยการแก้ปัญหาข้อจำกัด ลำดับเวลาของเราคือ:

1. ความเร็วล่วงหน้า
2. การแก้ไขข้อจำกัดในปริภูมิความเร็วและปริภูมิตำแหน่ง
3. ตำแหน่งก้าวหน้า

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

หนังสือ Erleben 2005 เป็นแหล่งข้อมูลที่ยอดเยี่ยมสำหรับการจำลองวัตถุแข็ง ซึ่งเพิ่งเปิดให้เข้าถึงได้ฟรีเมื่อไม่นานมานี้ คุณสามารถหาการบรรยายออนไลน์เกี่ยวกับแอนิเมชันที่ใช้ฟิสิกส์เป็นพื้นฐาน บล็อกของ Nilson Souto เกี่ยวกับการสร้างเอนจินฟิสิกส์ และการนำเสนอที่ยอดเยี่ยมในงาน GDC โดย Erin Catto เกี่ยวกับวิธีการแก้ปัญหาสมัยใหม่ นอกจากนี้ยังมีฟอรัมอย่าง Bullet Physics Forum และ GameDev ซึ่งเป็นแหล่งที่ดีเยี่ยมสำหรับการถามคำถาม

สรุป

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

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

ทั้งบริษัท Roblox Corporation และบล็อกนี้ไม่ได้รับรองหรือสนับสนุนบริษัทหรือบริการใด ๆ ทั้งสิ้น นอกจากนี้ ไม่มีการรับประกันหรือคำมั่นสัญญาใด ๆ เกี่ยวกับความถูกต้อง ความน่าเชื่อถือ หรือความสมบูรณ์ของข้อมูลที่ปรากฏในบล็อกนี้

บทความบล็อกนี้ได้รับการเผยแพร่ครั้งแรกบนบล็อกเทคโนโลยีของ Roblox