|
Mathematics: All Articles
Implementing High-Quality PRNG on GPUs |
Collision Detection Shader Using Cube-Maps |
Solving Systems of Linear Equations Using the Cross Product |
Efficient Sequence Indexing for Game Development |
Sphere Trees for Speedy BSPs |
CSG Construction Using BSP Trees |
Using Geometric Algebra for Computer Graphics |
Minimax Numerical Approximation |
Oblique View Frustums for Mirrors and Portals |
Faster Quaternion Interpolation Using Approximations |
Safe Random Number Systems |
Minimal Acceleration Hermite Curves |
Spline-Based Time Control for Animation |
Implementing Improved Perlin Noise |
Using the Covariance Matrix for Better-Fitting Bounding Objects |
Fast Contact Reduction for Dynamics Simulation |
Fast Collision Detection for 3D Bones-Based Articulated Characters |
Solving Accuracy Problems in Large World Coordinates |
The Jacobian Transpose Method for Inverse Kinematics |
Critically Damped Ease-In/Ease-Out Smoothing |
Extracting Frustum and Camera Information |
Hardware Skinning with Quaternions |
Hardware Skinning with Quaternions |
Implementing Improved Perlin Noise |
The Statistics of Random Numbers |
Abstract: Random numbers are used most heavily by Artificial Intelligence and games in general. To ignore their potential is to make the game predictable and boring. Using them incorrectly can be just as bad as ignoring them outright. Understanding how random numbers are generated, their limitations and their capabilities, can remove many difficulties of using them in your game. This article offers insight into random numbers, their generation, and methods to separate good ones from bad.
Filtered Randomness for AI Decisions and Game Logic |
Abstract: Conventional wisdom suggests that the better the random number generator, the more unpredictable your game will be. However, according to psychology studies, true randomness over the short term often looks decidedly unrandom to humans. This article shows how to make random AI decisions and game logic look more random to players, while still maintaining strong statistical randomness. Full source code, ready to drop into your game, is supplied on the book's CD-ROM.
Floating-Point Exception Handling |
Using Vector Fractions for Exact Geometry |
T-Junction Elimination and Retriangulation |
Abstract: This article describes how to detect possible sources of these seams in complex 3D scenes and how to modify static geometry so that visible artifacts are avoided. Since T-junction elimination adds verticies to existing polygons (that are not necessarily convex), we also discuss a method for triangulating arbitrary concave polygons.
Constrained Inverse Kinematics |
Fast Base-2 Functions for Logarithms and Random Number Generation |
More Approximations to Trigonometric Functions |
Considerations for Movement and Physics in MMP Games |
Collision Detection of Deformable Volumetric Meshes |
Automatic Parameterizations on the Cube |
k-D Tree Face Portals with Solid Geometry |
Resolution of the Inverse Kinematic of an Articulated Structure Using the Jacobian Pseudo-Inverse |
A Fast All-Interger Ellipse Discretization Algorithm |
 |  |
Tony Barrera (Barrera Kristiansen AB), Anders Hast (Creative Media Lab, University of G�vle), and Ewert Bengtsson (Center for Image Analysis, Uppsala University)
Graphics Programming Methods, 2003. |
A Fast and Simple All-Interger Parametric Line |
| |
Tony Barrera (Barrera Kristiansen AB), Anders Hast (Creative Media Lab, University of G�vle), and Ewert Bengtsson (Center for Image Analysis, Uppsala University)
Graphics Programming Methods, 2003. |
Recursive Dimensional Clustering: A Fast Algorithm for Collison Detection |
Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching |
Abstract: The article presents an algorithm and demonstration application that manages thousands of objects in motion that are continuously maintained as a collection of hierarchical bounding spheres in a SphereTree. The design goal for this algorithm has been to make the 99-percentile case spend almost no CPU time updating an object in motion within the tree structure. Queries against the SphereTree perform more tests than other data structures, but this is mitigated by the fact that the tree can be maintained using very little CPU time. This data structure is ideally suited for gross culling of massive numbers of moving objects in a large world space. It doesn't matter if the objects are moving at widely disparate speeds, or even if many of them are not in motion at all. It also has a very low cost when objects are inserted and removed from the tree with great frequency.
Compressed Axis-Aligned Bounding Box Trees |
Abstract: The axis-aligned bounding box (AABB) tree structure has proven to be very useful for accelerating intersection queries on sets of geometry. The data structure is easy to implement, the built structure is numerically well conditioned, and like all binary trees, they have O(log n) search time. This article explains several techniques that can be used to lower the overall memory footprint of an AABB tree to 11 bytes per triangle.
Direct Access Quadtree Lookup |
Abstract: This article presents a general-purpose optimization for quadtree access that improves performance in three ways over the traditional implementations: 1) by eliminating node traversal and the unnecessary cache-misses it causes, 2) by requiring fewer instructions and CPU cycles overall vs. a best case traditional approach, and 3) by doing so in a compact amount of time and with minimal memory accesses regardless of what depth in the tree the target node resides in.
Floating-Point Tricks: Improving Performance with IEEE Floating-Point |
Using Bloom Filters to Improve Computational Performance |
Fast, Robust Intersection of 3D Line Segments |
Inverse Trajectory Determination |
The Parallel Transport Frame |
Genuine Random Number Generation |
Smooth C2 Quaternion-based Flythrough Paths |
Abstract: This article will help lay the groundwork for building an accurate physics simulation by starting with one of the most crucial parts of a real-time physics engine: 3D collision detection. The two basic algorithms this article covers are: Bounding Sphere Collision Detection and Triangle-to-Triangle Collision Detection.
Multi-Resolution Maps for Interaction Detection (Collision Detection) |
Abstract: This article describes a method for reducing the number of proximity tests that must be performed for games with large numbers of game objects of varying sizes.
Computing the Distance into a Sector |
Abstract: This article describes a simple and fast algorithm for determining where a point is between the edges of a 2D quad (or sector). The result is a unit floating point number, where 0 indicates that the point lies on the leading edge, and where 1 indicates that the point lies on the opposite edge. The sector may be any four-sided, 2D convex shape.
Integrating the Equations of Rigid Body Motion |
Implicit Euler Integration for Numerical Stability |
Fast Math Using Template Metaprogramming |
Polynomial Approximations to Trigonometric Functions |
Wavelets: Theory and Compression |
A Fast Cylinder-Frustrum Intersection Test |
Abstract: This article presents a quick algorithm for determining whether an arbitrary cylinder potentially intersects the view frustum (and thus whether the object is visible).
Quaternions for Game Programming |
Matrix-Quaternion Conversions |
Interpolating Quaternions |
The Shortest Arc Quaternion |
Predictable Random Numbers |
|
