Advanced Linux 3D graphics programming

Advanced Linux 3D graphics programming Chapter 1 Basic Linux 3D Graphics Concepts ..................1 2D Graphics Fundamentals ......................................1 3D Graphics Fundamentals ......................................3 3D Coordinate Systems and Vectors ...............................4 Perspective Projection.......................................5 Matrices ................................................6 Specific Matrix Transformations .................................6 Other Matrix Properties ......................................7 The l3d Library Classes........................................8 Sample l3d Program ........................................8 l3d Directory Structure ....................................12 The Five-Step Process of l3d Programs............................13 Overview of l3d Classes .....................................19 Applications and Events....................................19 2D Graphics ..........................................20 Concrete Factory Management ................................24 Specifying Geometry and Behavior..............................25 Fixed- and Floating-Point Math................................29 Summary of l3d Classes....................................31 Linux Programming Tools......................................32 Linux 3D Modeling .........................................32 Blender Interface and Commands ................................33 Exporting and Importing Blender Models............................36 Summary...............................................37 Chapter 2 Rendering and Animation Techniques for 3D Polygons ......39 Vertex Animation and 3D Morphing ................................39 Sample Program: morph3d....................................40 Lighting ...............................................48 Mathematical Models for Computing Light...........................49 Self Lighting..........................................49 Ambient Lighting .......................................50 Diffuse Reflection.......................................50 Specular Reflection ......................................55 Multiple Light Sources and Components...........................57 Radiosity and Ray Tracing ..................................58 Dynamic or Static Lighting Computations ..........................58 Fog...............................................59 Rendering Techniques for Drawing Light ............................60 Flat Shading ..........................................61 iv Contents Gouraud Shading .......................................61 Phong Shading ........................................63 Light Maps ..........................................63 Texture Mapping...........................................64 Step 1: Define a Texture .....................................65 Storing Texture Data .....................................66 Classes for Loading Textures from Disk ...........................68 Practical Issues in Dealing with Texture Image Files.....................73 Step 2: Define a Texture Space .................................74 Step 3: Map Between Texture Space and World Space .....................76 Calc: A Symbolic Algebra Package..............................79 Starting and Exiting Calc ...................................79 Stack-Based Computation...................................80 Entering and Editing Mathematical Entities .........................82 Solving Systems of Equations ................................85 Solving the Texture Mapping Equations with Calc......................86 Step 4: Reverse Project from Screen Coordinates into Texture Coordinates..........89 Step 5: Map Texture Coordinates to Integer Indices and Draw.................92 An Optimized Texture Mapping Strategy: u/z, v/z, 1/z .....................93 The Division Operation and Texture Mapping ........................95 Associating Textures with 3D Polygons.............................96 Rasterization Classes for 3D Polygons .............................98 An Abstract 3D Rasterizer: l3d_rasterizer_3d ........................98 A Software 3D Rasterizer Implementation: l3d_rasterizer_3d_sw_imp ..........101 A Mesa/OpenGL 3D Rasterizer Implementation: l3d_rasterizer_3d_mesa_imp......115 Sample Program: textest ....................................129 Light Mapping Revisited......................................135 Software Light Mapping ....................................136 Surfaces ...........................................136 Surface Cache ........................................141 Light Mapped Polygons ...................................142 Software Rasterization of Light Maps............................147 Hardware Light Mapping....................................147 Sample Program: lightmap ...................................151 Shadows and Light Maps....................................159 Summary ..............................................160 Chapter 3 3D Modeling with Blender.....................161 Tutorial: Creating and Exporting Compatible, Textured 3D Morph Targets ...........161 The Starting Morph Mesh....................................162 Inserting Two Morph Targets into Blender...........................163 Deforming the Mesh ......................................165 Applying a Texture and Assigning Texture Coordinates....................167 Testing the Morph in Blender..................................173 Exporting the Two Morph Targets ...............................173 Exporting the Texture Information ...............................174 Importing the Morph Targets into a Program .........................175 Tutorial:UsingInverseKinematicsandRoto-scopingtoModela WalkingHumanFigure.......................................180 Inverse Kinematics: Definition.................................181 Creating an Ika Chain in Blender................................183 Contents v Working with Ika Chains ....................................183 Creating the Arm Ikas......................................184 Creating the Main Body Ika ..................................185 Parenting the Ikas into a Hierarchy...............................185 Testing the Ika Chains .....................................187 Animating the Ika Chains....................................188 Connecting Ika Chains and Meshes ..............................189 Texturing and Exporting the Model ..............................190 Importing the Textured Ika Meshes ..............................192 Rotoscoping and Inverse Kinematics..............................197 Programming IK and FK ....................................200 Summary ..............................................201 Chapter 4 Visible Surface Determination I: General Techniques ......203 The Goals of VSD .........................................204 Back-Face Culling .........................................207 3D Convexity and Back-Face Culling .............................209 Sample Program: backface ...................................209 Class l3d_World_Backface .................................214 View Frustum Culling .......................................218 Defining a View Frustum....................................218 Computing the Frustum in World Coordinates .......................220 Class l3d_Viewing_Frustum.................................221 Using the Frustum Planes....................................223 Hierarchical View Frustum Culling ..............................223 Bounding Spheres and the View Frustum ..........................225 Computing Bounding Spheres................................227 Class l3d_bounding_sphere .................................228 Other Bounding Volumes ..................................231 Clipping Against the View Frustum ..............................233 Sample Program: frustum....................................233 Class l3d_World_Frustum ..................................236 The Painter’s Algorithm ......................................242 The Z Buffer Algorithm ......................................245 General Observations about the Z Buffer ...........................246 A Software Z Buffer: Class l3d_rasterizer_3d_zbuf_sw_imp.................248 Mesa/OpenGL Z Buffering ...................................257 Factory Manager for Z Buffered Rasterizers .........................261 Sample Program: texzbuf ...................................263 Z Buffer-like Algorithms....................................264 Summary ..............................................266 Chapter 5 Visible Surface Determination II: Space-partitioning Techniques ..................267 Binary Space Partitioning Trees, Octrees, and Regular Spatial Partitioning ...........267 Using a BSP Tree to Partially Pre-sort Polygons .......................271 Choosing a Splitting Plane..................................272 Back-to-Front Rendering (Painter’s Algorithm Revisited) .................274 Front-to-Back Rendering ..................................275 Combining BSP Trees and Bounding Volumes .......................275 Sample Program: bsp ......................................276 vi Contents Classes l3d_halfspace and l3d_bsptree ...........................277 Class l3d_world_bsptree...................................286 The Main Program......................................290 The World Database, Revisited ...............................293 Leafy BSP Trees: Automatic Convex Partitioning of Space..................293 Creating a Leafy BSP Tree .................................295 Methods for Leafy BSP Trees in Class l3d_bsptree.....................296 Sample Program: leafybsp..................................297 Axis-aligned BSP Trees and Mini BSP Trees .........................302 BSP Tree as a Multi-resolution Solid-Modeling Representation ...............303 BSP Trees and Dimension Independence ...........................306 Octrees..............................................306 Regular Spatial Partitioning ..................................308 Portals and Cells ..........................................308 The Main Ideas Behind the Portal Algorithm .........................308 Rendering a Portal World....................................310 Observations about the Portal Scheme .............................313 Portals as a Connectivity Graph ...............................313 Advantages and Disadvantages ...............................313 Back-Face Culling ......................................314 Clipping ...........................................314 Convexity or Non-Convexity ................................315 Moving the Camera and Objects Within a Portal Environment...............315 Portals and the Near Z Plane.................................316 Shadows ...........................................318 Mirrors ............................................320 Portals and Other Rendering Methods............................321 Classes for Portals and Sectors .................................322 Class l3d_polygon_3d_portal ................................322 Class l3d_sector .......................................323 Class l3d_world_portal_textured_lightmapped_obj.....................329 Class l3d_rasterizer_2d_sw_lighter_imp ..........................344 Class l3d_pipeline_world_lightmapped...........................351 Sample Program: porlotex ...................................353 Other VSD Algorithms.......................................356 Summary ..............................................357 Chapter 6 Blender and World Editing ....................359 World Editing............................................360 No World Editor.........................................360 Write Your Own World Editor .................................361 Adapt an Existing Editor ....................................362 Using Blender for Portal Worlds..................................363 Main Ideas of a Blender Portal World Editor .........................364 Step-by-Step Guide to World Design..............................367 Data Flow within the World Editing System..........................368 Creating Sectors and Portals ....................................369 Tutorial: Creating Aligned Portals via Extrusion and Separation ...............371 Tutorial: Aligning Portals from Separate Meshes .......................374 Tips for Working with Portals .................................382 Portalization: Generating Portal Connectivity...........................385 Contents vii Perl Scripts ...........................................387 Architecture of the Perl Portalization System .........................389 Structural Modules......................................390 Parsing and Generator Modules ...............................415 Controlling Scripts......................................429 Embedding Location, Orientation, Texture, Actor, and Other Information into Meshes.....430 Basic Ideas of Associating Attributes with Objects ......................431 Store an ID, Location, and Orientation in Overlapping Edges ...............431 The Tool Blend_at: Remote Control of Blender.......................433 Configuration and Testing of blend_at ...........................434 Specific Mesh Attributes Used by the Portalization System..................437 The Name Attribute .....................................437 The Type Attribute......................................437 Attributes for Sectors ....................................437 Attributes for Actors.....................................439 Parsing of Attributes by VidscParser.pm and vidinfo ....................440 Program Listings for blend_at .................................446 Class vertex .........................................447 Class blender_config.....................................447 Class blender_controller...................................448 Class blender_xcontroller ..................................449 Tutorial: Creating a Textured Room with Actors .......................463 Tips for Working with Attributes................................473 Summary of Blender and Portal Worlds..............................474 Other World Editing Ideas .....................................475 Portalized Regular Spatial Partitioning.............................475 BSP Tree and Octree ......................................476 Non-convex Sector-based Partitioning.............................476 Summary ..............................................478 Chapter 7 Additional Graphics Techniques..................479 Special Effects ...........................................479 Environment Mapping .....................................480 Billboards ............................................484 Lens Flare ............................................486 Particle Systems.........................................487 Physics and Particle Systems ................................488 Real-Time Update ......................................489 Sample Program: particle ..................................490 Comments on the Sample Program’s Physics ........................496 Some Ideas for You to Try..................................496 Natural Phenomena .......................................497 Bump Mapping .........................................499 Multi-pass Techniques .....................................500 Advanced Techniques .......................................501 Curved Surfaces.........................................501 Level of Detail .........................................505 Billboards ..........................................506 Edge Collapse ........................................506 BSPTree...........................................507 Texture LOD Techniques: MIP Mapping ..........................508 viii Contents Landscapes ...........................................509 Storing Landscapes as Height Fields ............................509 Generating Fractal Landscapes ...............................510 Rendering and LOD Techniques for Landscapes ......................511 Camera Tracking ........................................512 Summary ..............................................513 Chapter 8 Non-Graphical Techniques for Games and Interactive Environments .....................515 Sound ................................................515 Basics of Digital Sound.....................................516 The RPlay Server ........................................519 Using TCP/IP Networking to Communicate with the Server .................520 Class l3d_sound_client .....................................521 Class l3d_sound_server_rplay .................................522 TCP/IP Networking ........................................524 The Client ............................................524 The Server............................................526 Running the Sample Server and Client.............................529 Non-Blocking Operations....................................529 What Data to Send .......................................530 Collision Detection.........................................530 Intersection Testing and Bounding Volumes..........................531 Sphere-to-Sphere.......................................532 Ray-to-Polygon .......................................532 Ray-to-Sphere ........................................535 Sphere-to-Polygon ......................................536 Tunneling and Sweep Tests...................................538 Multiple Simultaneous Collisions and Collision Response ..................541 Allowing Penetration ....................................541 Avoiding Penetration with Temporal Search ........................542 Class l3d_collidable.......................................543 Class l3d_collidable_sphere ..................................544 Class l3d_polygon_3d_collidable ...............................548 Class l3d_polygon_3d_textured_lightmapped_collidable...................551 Class l3d_camera_collidable ..................................552 Class l3d_world_portal_textured_lightmapped_obj_colldet .................553 Plug-in Object Seeker, Class l3d_plugin_videoscape_mesh_seeker .............563 Sample Program: collide ....................................574 More Advanced Collision Detection and Response ......................576 Physics ...............................................577 Some Basic Concepts......................................577 Rigid Body Dynamics......................................578 Real-Time Update and Numerical Integration .........................579 Artificial Intelligence........................................580 Summary ..............................................582 Chapter 9 What Lies Ahead? .........................583 Content Development Systems...................................583 Game Blender/Blender 2.0 ...................................583 World Foundry .........................................590 Contents ix What Does This Mean for 3D Programmers? .........................598 The Future .............................................599 Summary ..............................................600 Perspective .............................................600 Appendix ...................................603 CD Installation ...........................................603 License .............................................603 Contents of the CD-ROM....................................603 Quick Start Guide........................................604 Directories ..........................................604 Installing the Sample Programs and Other Software ....................605 Troubleshooting the Sample Programs.............................607 Some Comments on the Sample Programs...........................607 Hardware Acceleration .....................................608 Porting the Code to Microsoft Windows..............................609 Tools Used to Prepare this Book..................................610 Resources..............................................611 3D Graphics Programming ...................................612 3D Modeling ..........................................612 3D Information and Applications................................613 General Programming......................................613 Other...............................................614 References .............................................614 Index ....................................617