دانلود کتاب Efficient Collision Detection for Animation and Robotics

ترجمه فارسی توضیحات (ترجمه ماشینی)

تشخیص برخورد کارآمد برای انیمیشن و رباتیک

ما الگوریتم‌های کارآمدی را برای تشخیص برخورد و تعیین تماس بین مدل‌های هندسی ارائه می‌کنیم، که با مرزهای خطی یا منحنی توصیف می‌شوند و تحت حرکت صلب هستند. قلب الگوریتم تشخیص برخورد ما یک روش افزایشی ساده و سریع برای محاسبه فاصله بین دو چند وجهی محدب است. از تحدب برای ایجاد برخی معیارهای کاربردی محلی برای تأیید نزدیک‌ترین ویژگی‌ها استفاده می‌کند. یک روش پیش پردازش برای تقسیم کردن ویژگی های مجاور هر ویژگی به اندازه ثابت و در نتیجه تضمین زمان اجرای ثابت مورد انتظار برای هر آزمایش استفاده می شود. عملکرد زمان ثابت مورد انتظار یک ویژگی از بهره برداری از انسجام و موقعیت هندسی است. فرض کنید n تعداد کل ویژگی‌ها باشد، زمان اجرای مورد انتظار بسته به شکل، بین o(#) و 0(n) است، اگر مقداردهی اولیه خاصی انجام نشود. این تکنیک را می توان برای تشخیص برخورد دینامیکی، برنامه ریزی در فضای سه بعدی، شبیه سازی فیزیکی و سایر مشکلات رباتیک استفاده کرد. مجموعه‌ای از مدل‌هایی که در نظر می‌گیریم شامل چند وجهی و اشیایی با سطوحی است که با تکه‌های اسپلاین منطقی یا توابع جبری تکه‌ای توصیف شده‌اند. ما از الگوریتم محاسبه فاصله زمانی ثابت مورد انتظار برای تشخیص برخورد بین اشیاء چند وجهی محدب استفاده می‌کنیم و آن را با استفاده از یک نمایش سلسله مراتبی به اندازه‌گیری فاصله بین چند توپ غیر محدب گسترش می‌دهیم. در مرحله بعد، ما از روش های جبری جهانی برای حل معادلات چند جمله ای و توصیف سلسله مراتبی برای ابداع الگوریتم های کارآمد برای اشیاء منحنی دلخواه استفاده می کنیم. ما همچنین دو رویکرد متفاوت را برای کاهش فرکانس تشخیص برخورد از مقایسه‌های زوجی در محیطی با n جسم متحرک توصیف می‌کنیم. یکی از آنها استفاده از صف اولویت بندی شده با کران پایین در زمان برخورد است. دیگری از تست همپوشانی در جعبه های محدود استفاده می کند. در نهایت، ما یک الگوریتم برنامه‌ریز مسیر جهانی فرصت‌طلب را ارائه می‌کنیم که از الگوریتم محاسبه فاصله افزایشی برای ردیابی یک اسکلت تک بعدی به منظور برنامه‌ریزی حرکت ربات استفاده می‌کند. عملکرد محاسبات فاصله و الگوریتم‌های تشخیص برخورد قول آنها را برای شبیه‌سازی‌های دینامیکی بلادرنگ و همچنین برنامه‌های کاربردی در یک محیط مجازی تولید شده توسط رایانه تأیید می‌کند.

Efficient Collision Detection for Animation and Robotics

We present efficient algorithms for collision detection and contact determination between geometric models, described by linear or curved boundaries, undergoing rigid motion. The heart of our collision detection algorithm is a simple and fast incremental method to compute the distance between two convex polyhedra. It utilizes convexity to establish some local applicability criteria for verifying the closest features. A preprocessing procedure is used to subdivide each feature’s neighboring features to a constant size and thus guarantee expected constant running time for each test. The expected constant time performance is an attribute from exploiting the geometric coherence and locality. Let n be the total number of features, the expected run time is between o(#) and 0(n) depending on the shape, if no special initialization is done. This technique can be used for dynamic collision detection, planning in three-dimensional space, physical simulation, and other robotics problems. The set of models we consider includes polyhedra and objects with surfaces described by rational spline patches or piecewise algebraic functions. We use the expected constant time distance computation algorithm for collision detection between convex polyhedral objects and extend it using a hierarchical representation to distance measurement between non-convex polytopes. Next, we use global algebraic methods for solving polynomial equations and the hierarchical description to devise efficient algorithms for arbitrary curved objects. We also describe two different approaches to reduce the frequency of collision detection from pairwise comparisons in an environment with n moving objects. One of them is to use a priority queue sorted by a lower bound on time to collision; the other uses an overlap test on bounding boxes. Finally, we present an opportunistic global path planner algorithm which uses the incremental distance computation algorithm to trace out a one-dimensional skeleton for the purpose of robot motion planning. The performance of the distance computation and collision detection algorithms attests their promise for real-time dynamic simulations as well as applications in a computer generated virtual environment.