没有合适的资源？快使用搜索试试~ 我知道了~

首页游戏碰撞检测详解：高效算法与实战指南

游戏碰撞检测详解：高效算法与实战指南

1星需积分: 46 70 下载量 110 浏览量更新于2024-07-18 5 收藏 3.84MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

633页

"《实时碰撞检测：复杂环境中的精准与效率》是一本深度剖析游戏碰撞检测领域的权威指南，它针对当今高性能计算机游戏设计的核心需求提供了解决方案。在复杂的游戏中，碰撞检测是基础，但实现实时、准确且高效的碰撞检测却是一项挑战。书中详尽讲解了各种碰撞检测算法，包括但不限于多种几何形状的处理，如球体、盒子、圆环等，这些都是构建动态世界的关键。书中不仅深入解析了基础算法，而且强调了实际应用中的关键问题，例如几何和数值鲁棒性，以及如何优化算法以提高缓存效率。这些内容确保了读者能够应对不断增长的复杂环境对计算性能的要求。作者克里斯蒂·埃里克森不仅阐述了理论知识，还提供了丰富的实践经验，使得这本书成为互动应用开发者，尤其是游戏开发人员的必备参考书。两位业内专家，NVIDIA的高级软件开发者马特·帕尔夫和Valve的高级工程师杰伊·斯泰利，都对这本书给出了高度评价。他们认为这本书覆盖了碰撞检测的各个方面，无论你是初学者还是资深开发者，都能从中受益匪浅，获取实用的技术和策略，以便在设计和实现游戏物理系统时做出明智决策。《实时碰撞检测》以其全面性和实用性，成为了游戏开发者在解决碰撞检测难题时的重要工具，无论是对于基础概念的理解，还是对于技术细节的掌握，都能从中获得宝贵的知识和经验。对于追求高质量游戏体验和技术提升的专业人士来说，这无疑是一本不可或缺的参考资料。"

资源详情

资源推荐

Contents xv

6.6.4 Cache-friendlier Structures (Nonbinary Trees) 274

6.6.5 Tree Node and Primitive Ordering 275

6.6.6 On Recursion 276

6.6.7 Grouping Queries 278

6.7

Improved Queries Through Caching 280

6.7.1 Surface Caching: Caching Intersecting Primitives 280

6.7.2 Front Tracking 282

6.8

Summary 284

Chapter 7

Spatial Partitioning 285

7.1 Uniform Grids 285

7.1.1 Cell Size Issues 286

7.1.2 Grids as Arrays of Linked Lists 287

7.1.3 Hashed Storage and Inﬁnite Grids 288

7.1.4 Storing Static Data 290

7.1.5 Implicit Grids 291

7.1.6 Uniform Grid Object-Object Test 294

7.1.6.1 One Test at a Time 295

7.1.6.2 All Tests at a Time 297

7.1.7 Additional Grid Considerations 299

7.2

Hierarchical Grids 300

7.2.1 Basic Hgrid Implementation 302

7.2.2 Alternative Hierarchical Grid Representations 306

7.2.3 Other Hierarchical Grids 307

7.3

Trees 307

7.3.1 Octrees (and Quadtrees) 308

7.3.2 Octree Object Assignment 309

7.3.3 Locational Codes and Finding the Octant for a Point 313

7.3.4 Linear Octrees (Hash-based) 314

7.3.5 Computing the Morton Key 316

7.3.6 Loose Octrees 318

7.3.7 k-d Trees 319

7.3.8 Hybrid Schemes 321

7.4

Ray and Directed Line Segment Traversals 322

xvi Contents

7.4.1 k-d Tree Intersection Test 322

7.4.2 Uniform Grid Intersection Test 324

7.5

Sort and Sweep Methods 329

7.5.1 Sorted Linked-list Implementation 330

7.5.2 Array-based Sorting 336

7.6

Cells and Portals 338

7.7 Avoiding Retesting 341

7.7.1 Bit Flags 341

7.7.2 Time Stamping 342

7.7.3 Amortized Time Stamp Clearing 344

7.8

Summary 346

Chapter 8

BSP Tree Hierarchies 349

8.1 BSP Trees 349

8.2 Types of BSP Trees 351

8.2.1 Node-storing BSP Trees 351

8.2.2 Leaf-storing BSP Trees 352

8.2.3 Solid-leaf BSP Trees 354

8.3

Building the BSP Tree 355

8.3.1 Selecting Dividing Planes 358

8.3.2 Evaluating Dividing Planes 361

8.3.3

Classifying Polygons with Respect to a Plane 364

8.3.4 Splitting Polygons Against a Plane 367

8.3.5 More on Polygon Splitting Robustness 372

8.3.6 Tuning BSP Tree Performance 373

8.4

Using the BSP Tree 374

8.4.1 Testing a Point Against a Solid-leaf BSP Tree 374

8.4.2 Intersecting a Ray Against a Solid-leaf BSP Tree 376

8.4.3 Polytope Queries on Solid-leaf BSP Trees 378

8.5

Summary 381

Chapter 9

Convexity-based Methods 383

9.1 Boundary-based Collision Detection 383

Contents xvii

9.2

Closest-features Algorithms 385

9.2.1 The V-Clip Algorithm 386

9.3

Hierarchical Polyhedron Representations 388

9.3.1 The Dobkin–Kirkpatrick Hierarchy 389

9.4

Linear and Quadratic Programming 391

9.4.1 Linear Programming 391

9.4.1.1 Fourier–Motzkin Elimination 394

9.4.1.2 Seidel’s Algorithm 396

9.4.2 Quadratic Programming 398

9.5

The Gilbert–Johnson–Keerthi Algorithm 399

9.5.1 The Gilbert–Johnson–Keerthi Algorithm 400

9.5.2 Finding the Point of Minimum Norm in a Simplex 403

9.5.3 GJK, Closest Points and Contact Manifolds 405

9.5.4 Hill Climbing for ExtremeVertices 405

9.5.5 Exploiting Coherence byVertex Caching 407

9.5.6 Rotated Objects Optimization 408

9.5.7 GJK for Moving Objects 408

9.6

The Chung–Wang Separating-vector Algorithm 410

9.7 Summary 412

Chapter 10

GPU-assisted Collision Detection 413

10.1 Interfacing with the GPU 414

10.1.1 Buffer Readbacks 414

10.1.2 Occlusion Queries 416

10.2

Testing Convex Objects 416

10.3 Testing Concave Objects 420

10.4 GPU-based Collision Filtering 423

10.5 Summary 426

Chapter 11

Numerical Robustness 427

11.1 Robustness Problem Types 427

11.2 Representing Real Numbers 429

11.2.1 The IEEE-754 Floating-point Formats 431

xviii Contents

11.2.2 Inﬁnity Arithmetic 435

11.2.3 Floating-point Error Sources 438

11.3

Robust Floating-point Usage 441

11.3.1 Tolerance Comparisons for Floating-point Values 441

11.3.2 Robustness Through Thick Planes 444

11.3.3 Robustness Through Sharing of Calculations 446

11.3.4 Robustness of Fat Objects 448

11.4

Interval Arithmetic 448

11.4.1 Interval Arithmetic Examples 450

11.4.2 Interval Arithmetic in Collision Detection 451

11.5

Exact and Semi-exact Computation 452

11.5.1 Exact Arithmetic Using Integers 453

11.5.2 Integer Division 457

11.5.3 Segment Intersection Using Integer Arithmetic 459

11.6

Further Suggestions for Improving Robustness 462

11.7 Summary 463

Chapter 12

Geometrical Robustness 465

12.1 Vertex Welding 466

12.2 Computing Adjacency Information 474

12.2.1 Computing a Vertex-to-Face Table 477

12.2.2 Computing an Edge-to-Face Table 479

12.2.3 Testing Connectedness 482

12.3

Holes, Cracks, Gaps and T-Junctions 484

12.4 Merging Co-planar Faces 487

12.4.1 Testing Co-planarity of Two Polygons 489

12.4.2 Testing Polygon Planarity 491

12.5

Triangulation and Convex Partitioning 495

12.5.1 Triangulation by Ear Cutting 496

12.5.1.1 Triangulating Polygons with Holes 499

12.5.2 Convex Decomposition of Polygons 500

12.5.3 Convex Decomposition of Polyhedra 502

12.5.4 Dealing with“Nondecomposable”Concave Geometry 506

Contents xix

12.6

Consistency Testing Using Euler’s Formula 507

12.7 Summary 510

Chapter 13

Optimization 511

13.1 CPU Caches 513

13.2 Instruction Cache Optimizations 515

13.3 Data Cache Optimizations 517

13.3.1 Structure Optimizations 518

13.3.2 Quantized and CompressedVertex Data 522

13.3.3 Prefetching and Preloading 523

13.4

Cache-aware Data Structures and Algorithms 525

13.4.1 A Compact Static k-d Tree 525

13.4.2 A Compact AABB Tree 529

13.4.3 Cache Obliviousness 530

13.5

Software Caching 531

13.5.1 Cached Linearization Example 532

13.5.2 Amortized Predictive Linearization Caching 535

13.6

Aliasing 536

13.6.1 Type-based Alias Analysis 538

13.6.2 Restricted Pointers 540

13.6.3 Avoiding Aliasing 542

13.7

Parallelism Through SIMD Optimizations 543

13.7.1 Four SpheresVersus Four Spheres SIMD Test 545

13.7.2 Four SpheresVersus Four AABBs SIMD Test 546

13.7.3 Four AABBsVersus Four AABBs SIMD Test 546

13.8

Branching 547

13.9 Summary 551

References 553

Index 577

About the CD ROM 591

剩余632页未读，继续阅读

粉丝: 26
资源: 8

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

游戏碰撞检测详解：高效算法与实战指南

Unity3d非物理引擎模拟碰撞效果

一种快速精确的连续碰撞检测算法 (2006年)

碰撞检测算法

游戏中的碰撞检测优化技术

游戏碰撞检测中的时间分辨率问题

深入理解Python游戏中的碰撞检测与响应

3D游戏中的简单碰撞碰撞检测算法

使用SpriteKit实现游戏中的精灵碰撞检测

Opcode碰撞检测

pygame碰撞游戏

基于untiy3d的赛车游戏设计与实现碰撞动画如何写

python制作打砖块游戏详细设计

java飞机大战后端的相关技术介绍，碰撞处理技术，详细说明该技术

unity射线检测碰撞

打飞机游戏 详细设计怎么描述

描述utils.containsPoint方法检测碰撞的设计，比较跟其它方法的优缺点

给我俄罗斯方块游戏的详细指导

python贪吃蛇游戏详细设计

Java后端飞机大战检测我方飞机与敌机的碰撞详细讲解

最新资源

打飞机游戏详细设计怎么描述