• Create Account

# grhodes_at_work

Member Since 31 May 2000
Offline Last Active Jun 04 2013 12:37 PM

### #5067401OBB calculating extents

Posted by on 04 June 2013 - 11:46 AM

Thank you for the additional background information. I now understand better what you are doing, and what your references are.

With respect to the separate transform object, I agree that you wouldn't want to create a new transform class. And, certainly, it does not necessarily make sense for OBB to inherit from transform. The OBB could have a property that is a transform object, and I wonder if it might still make sense to take advantage of the existing scene graph transform class. If you do something like this in your collision detection engine, then it might make it easier to sync your collision detection with the scene graph to be rendered. Or, the OBB shape could be a child of a transform object...making it easier to support compound shapes or different types of collision shapes. Many physics engines are set up sort of like this. I realize that rendering engines and collision detection/physics engines often have separate representations of the scene, but the collision/physics engines usually provide helpful built-in mechanisms to point back to a rendered scene graph.

I can think of another OBB reference, which might be useful if you can find a copy online. It is the OBBTree paper written by researchers at UNC Chapel Hill many years ago. Yes, its really old now, but is one of the early presentations of OBB for collision detection, and still useful. Here is a link to the paper. (I admit that I haven't ready it in a long, long time.)

http://www.cs.unc.edu/~walk/papers/gottscha/sig96.pdf

Pierre Terdiman also has done some work that you might find useful:

http://www.codercorner.com/Coder.htm - see OPCODE for example

http://www.codercorner.com/RAPID_Hack.htm

Graham

### #5067211OBB calculating extents

Posted by on 03 June 2013 - 03:50 PM

There are some things about your presentation that are worrisome to me, in terms of language use, variable names, and coding style. I offer some suggestions, which you can use if you find them useful.

First, you say that your OBB's having "3 perpendicular normals," but I wonder why you call them normals. Is it because the faces of the OBB are perpendicular to these vectors that you called them "normals?" Why not call them just local coordinate frame axes, or basis vectors, or basis directions, all of which are more general and more appropriate for vectors that define the rotation of a generalized shape? I would also suggest that you completely separate the dimensions of the OBB from the basis vectors in the constructor, for clarity. Embedding the size of the OBB inside the incoming basis vectors...is confusing. There is nothing in the variable names of the OBB constructor parameters that indicates the length of the edges is equal to the length of those vectors.

If I were to write a simple OBB class, it'd look something like this. This is just quickly written code, incomplete, not really designed, not tested, and not exactly what I'd use for a project. This code illustrates an idea. The idea is to suggest building your transformation (location and orientation) as a separate object and just include it in the OBB class. By building the transformation separately, you can re-use it to represent other things in the scene, too. Not just OBB's.

/// simple 3x3 matrix class, to be used to store orientation as a 3x3
/// rotation matrix
class RotationMatrix3x3
{
public:
RotationMatrix3x3(const vec3 &xDir, const vec3 &yDir, const vec3 &zDir)
{
m_basisVectors[0] = xDir;
m_basisVectors[1] = yDir;
m_basisVectors[2] = zDir;
}

protected:
vec3 m_basisVectors[3]; ///< x, y, and z direction basis vectors
};

/// transformation class to be used to store translation and rotation
/// relative to a parent or world Cartesian coordinate frame
class Transform
{
public:
Transform(const vec3 &translation, const vec3 &xDir, const vec3 &yDir,
const vec3 &zDir):
m_translation(translation), m_orientation(xDir, yDir, zDir)
{
}

protected:
/// translation vector, represented in a parent or world coordinate frame
vec3 m_translation;

/// orientation as a 3x3 rotation matrix, represented in a parent or world
/// coordinate frame
RotationMatrix3x3 m_orientation;
};

/// Oriented Bounding Box class, which inherits its location and orientation
/// relative to a parent or world coordinate frame via the Transform class
class OBB : public Transform
{
OBB(const vec3 &translation, const vec3 &xDir, const vec3 &yDir,
const vec3 &zDir, const vec3 &extent) :
Transform(translation, xDir, yDir, zDir), m_extent(extent)
{
}

protected:
/// extent along local object basis directions
vec3 m_extent;
};



I hope this is somehow useful.

grhodes_at_work

### #5062678normals in tangent space question

Posted by on 17 May 2013 - 04:34 PM

There is some very good discussion here, and I appreciate all of the contributions. There are a couple of points that I think are worth restating, or clarifying, so that people might understand more deeply.

With regard to which aspect of geometry the TBN is associated, the TBN exists for any point on the surface, not only at each face, and also not only at each vertex. It may be computed at each vertex, or each pixel, or once per face for that matter, depending on how it is to be used (vertex or fragment shader or just asset calculations on the CPU) or what is convenient, but strictly speaking it exists continuously across the surface.

With regard to the tangent direction, it is not in general true that it is defined to point in the direction of change of the u coordinate. A tangent vector can be any vector that is located in the tangent plane at a point on the surface (the tangent plane being the plane that is orthogonal to the local surface normal at that point, er, for a surface that is continuously differentiable). So, as Bacterius noted, it is true that there are infinitely many possible tangent space choices at any point on the surface.

It happens that computing the tangent along the curve of the u direction is quite convenient, and, since it aligns with texture coordinates, this choice fits very nicely with computer rendering use cases. Also, on a mesh, standardizing on this choice enables continuity of the tangent spaces across the entire mesh surface.

As for the bitangent (which is a more appropriate term than binormal, when dealing with surfaces), it is in fact just like the tangent in that it lies in the tangent plane. It is a tangent vector, just a different one than the T in TBN. In computer graphics the bitangent is often computed along the v direction, again in order to align with texture coordinate directions and provide for TBN continuity, but there is that issue of the u and v directions being nonorthogonal in model/world space (vs. tangent space), as discussed in prior posts. The terathon page linked above discusses this orthogonality issue with a workable solution, concisely.

I know many resources out there explicitly define the tangent to be computed along the u direction and bitangent to be computed along the v direction, but to understand deeply you should recognize that these choices are made merely to achieve the alignment with the texture directions with the happy bonus of TBN continuity. I hope this reply helps someone understand more deeply, if only a little.

Graham

### #5058110My approach to physics

Posted by on 30 April 2013 - 11:13 AM

I am surprised that you were unable to find satisfactory discussions of handling multiple simultaneous collisions with multiple collision points. In my view, there is quite a lot of discussions and documentation freely available about how the constraint solvers in modern game physics engines work, and address exactly these problems. This has been continuously worked and improved in the games industry for more than a decade.

For example, here's an intermediate level presentation from an annual tutorial series on physics simulation, from the Game Developer's Conference in 2012, discussing the implementation of a multi-body, multi-contact rigid body contact/constraint solver. The first half focuses on a single contact, but the last half delves into multiple bodies and multiple contacts. There are many such presentations and technical documents out there. The GDC tutorials on math and physics for games have been going on for nearly a decade:

http://www.essentialmath.com/GDC2012/Richard_Tonge_solvingRigidBodyContacts.pdf

And here is one of Erwin Coumans' presentations on rigid body dynamics simulation. The last 25% of this talk discusses using the GPU to accelerate constraint solving. (He presented a new one this year at GDC, back in March, describing new advances in GPU-accelerated rigid body dynamics).

I bet there are some excellent presentations available at the following link. These are presentations from Erin Catto's physics tutorial at GDC back in March:

You would be wise to look at some of these materials, because there are a lot of lessons learned, and practical implementation experience (LOTS of this) in those presentations. Many of these folks have worked on real time physics simulation as their full time job, for years.

The conservation of energy problem is also discussed in the game physics literature, though from a games perspective (fast, stable with large time steps and over long simulation times and for very diverse scenarios, realistic-looking), and not a perfect math/engineering/simulation perspective. For practical problems, even the engineering solutions don't have perfect solutions that satisfy conservation of energy. (In simulating fluid dynamics, there is a class of theoretical problems that can be solved with "perfect shift," numerical solutions of wave-like equations that generate prefectly zero error...but these are only contrived theortical problems...not in practice.) As others have written, physics is hard. But, you knew that!

Graham

### #5057779basic collisions

Posted by on 29 April 2013 - 09:52 AM

Perhaps you could ask a specific technical question? Also, it is unclear what we are meant to be paying attention to in your video. If you want to illustrate a specific problem with your collision detection, it would be better to show one simple collision example that shows the problem you're concerned about.

Graham

### #5057773Fluid Dynamics Books

Posted by on 29 April 2013 - 09:11 AM

I will post a couple of recommendations of fluid dynamics books that I like, although I doubt you would choose them because they focused more on engineering that animation and games, are more classics than very current, and because they are uber pricey. (You may get lucky at a used college bookstore and find a cheap used copy.) But they are very good if you have any desire to understand the nature of fluids and the equations used to simulate them. I personally think it is better to have a good understanding of the physics you are trying to simulate, than just have a loose understanding. Harder to fix problems in the code if you don't understand the physics.

The first one is an excellent book for learning about the nature of fluid flow as it appears in the equations we use to model fluids. It is an undergraduate level CFD book. Highly recommended for those who are good at math and want to understand the physics deeply. I had not realized how pricey these books had gotten. I bought a copy new for US$50 ten years ago. Now it is US$200? Crazy.

http://www.amazon.com/Computational-Fluid-Dynamics-John-Anderson/dp/0070016852/ref=sr_1_1?s=books&ie=UTF8&qid=1367247111&sr=1-1&keywords=computational+fluid+dynamics

The other one is similar, but is more in depth. Graduate school level. This one does get into some semi-modern techniques, such as artificial compressibility (to accelerate solutions for incompressible/elliptic flows), and things like essentially non-oscillatory (ENO) techniques with flux limiters for transonic and supersonic fluids. It is a bit less expensive. Plus, you can rent it for US\$40. (WTF? Rent a book from amazon. Crazy.)

http://www.amazon.com/Computational-Mechanics-Transfer-Physical-Processes/dp/1591690374/ref=sr_1_1?s=books&ie=UTF8&qid=1367247513&sr=1-1&keywords=computational+fluid+mechanics

Here is one reason why those books might not be so interesting from the point-of-view of implementing fluids for games. Those books do focus more on the Eulerian approach to fluids, in which you have a fixed volume tracking fluid properties at fixed points or cells within the volume, which is good for designing machines, pipes, airplanes in normal operating conditions...sometimes games. But these days many games solve fluids using the Lagrangian approach, which tracks the motion of individual fluid particles. This enables modeling of, for example, splashes, water collecting into an emergent pool after dynamic changes to the environment, puffs of smoke, etc. More interesting fluid motion for interactive applications and games. For example, the smoothed particle hydrodynamics (SPH) technique implemented in some game physics engines is a Lagrangian fluid solver. But they are very good if you want to understand the nature of fluids and have a deeper understanding of what the terms in the governing equations mean.

http://en.wikipedia.org/wiki/Lagrangian_and_Eulerian_specification_of_the_flow_field

Graham

### #4772502Primitive physics class question

Posted by on 10 February 2011 - 01:29 PM

nullsquared, actually I am glad that you refuse to just take what your teacher says to be always true. It isn't. Frankly, any good teacher should welcome a good student's challenge and be open to themselves learning from the students. The classroom should be a collaboration, an interaction. The teacher is the master, but the master must also learn from the student.

### #4764847Invaluable paper for ANY game programmer

Posted by on 25 January 2011 - 08:27 PM

I don't know if the OP intended this as a troll or a joke, but it is clearly so incredibly obscure and advanced that it is off topic. I'm closing the thread, or hiding it, depending on what I can do with the new forums, and have asked the OP to not do this again.

grhodes_at_work
moderator, Math & Physics

### #4446065Good tuts on procedural planet generation?

Posted by on 26 April 2009 - 04:54 PM

There actually is a tutorial here on gamedev that you may find useful:

Procedural Planets Part 1 - Structure

Looks like it didn't go to a part 2, though, and the author's site seems to be down.

You might find something useful at vterrain.org

Apart from that, I don't have any links to specific presentations, but Ken Musgrave in the past has given good overview tutorials @ the annual SIGGRAPH conference. I can personally recommend that. You might find one of those with a Google search. His company, Pandromeda, (which seems to have gone silent but still with an available webpage) sells an artist application for generating procedural planets, called Mojoworld. It can be consider to be in the same class as things like Bryce and TerraGen, but I like the control that Mojoworld provides for customizing the fractal equations.

### #4369767Physical Collision Response

Posted by on 23 December 2008 - 02:58 AM

I don't really have time to give a tutorial here, but I can point you to some very good introductory reference material, which you can use for self-study. Please go to the sticky thread list of physics engines and reference material, at the top of the thread list for this forum and visit the "Essential Math" presentation materials link. The presentations at that link are a very good introduction to game physics, and include a very good introduction to collisions. It probably won't answer all your questions, but its a better introduction than I can possible give here. Here is the link to the sticky thread (but you can also see it at the top of the forum's thread list):

List of Physics Engines and Reference Material

Again, look for "Essential Math"

Hope that helps!

### #563153LaTeX - based equations in gamedev.net forums

Posted by on 23 February 2010 - 11:55 AM

Folks, There is a sticky thread in another forum that shows how you can embed fancy LaTeX-based equations in your forum posts. That functionality seems really beneficial to the math & physics forum so I'm linking to the other thread here. Here is a link to that thread: LaTeX - math equations support? There is another service available that can also do this. Here is an example using the other service: $\int_{-\infty }^{\infty }e^{-x^{2}}\;dx=\sqrt{\pi }$ And the HTML code to put in your post for that example is:
<img src="http://www.forkosh.dreamhost.com/mimetex.cgi?\int_{-\infty }^{\infty }e^{-x^{2}}\;dx=\sqrt{\pi }"/>


(Personally I find the image generated by the service mentioned in the other thread to be a bit prettier.]

### #475753List of physics engines and reference material (updated 7 March 2011)

Posted by on 12 December 2007 - 04:56 AM

Someone suggested that it might be useful to have a sticky list of physics engines and reference material available here (for convenience...the info is all available elsewhere). So, I am giving it a try.This thread is not for discussions. It is simply meant to contain links to commonly-requested information. I'll leave the thread open for contributions, but I will remove anything that is remotely off topic or tangential. Add links, but do not discuss!
-------------------------------------------------Commercial Physics Engines (usually written in C++)-------------------------------------------------
Note that most of these have license options that are attractively priced for indie and hobby developers.

Havok (3D, free for non-commercial and inexpensive commercial PC games, fee-based for games above a price limit, non-game applications, and consoles. Download available from Try Havok.)
NovodeX (see Ageia PhysX)
Ageia PhysX (previously NovodeX, now NVIDIA PhysX)
NVIDIA PhysX (previously Ageia PhysX) (3D, free for PC-based games, free for PS3 through Sony pre-purchase, fee-based for other consoles)Oxford Dynamics (3D, vehicle sim - appears to be dead...)
Digital Molecular Matter (DMM) from Pixelux Entertainment (3D, fee-based licensing)
SPE Simple Physics Engine (3D, free for noncommercial, fee-based for commercial)
Chrono::Engine (3D, free for noncommercial use, fee-based for commercial)
True Axis (3D, free for noncommercial, fee-based for commercial with a reasonable indie license option)
Gino van den Bergen's SOLID collision detection library (3D, fee-based for commercial, open sourced for GPL/QPL projects)
SimVex - (previously simul-X) Addon library for Havok enabling game-quality vehicle creation of any configuration, cars, motorcycles, aircraft, etc.
CarX - CarX is a car physics engine for AAA racing games. (3D,C++,fee-based licensing)

-------------------------------------------------Open Source and Freeware Physics Engines-------------------------------------------------
Bullet (3D, open source Zlib license)
Open Dynamics Engine (3D, open source BSD license)
Box2D (2D, open source permissive Zlib license)
Newton Game Dynamics (3D, custom free-use license)
JigLib (3D, open source Zlib license)
Chipmunk (2D, open source unrestrictive MIT license)
Open Tissue (various, open source Zlib license)

------------------------------------------------------------XNA-Compatible ports------------------------------------------------------------
JigLibX - XNA port of JigLib (previously JiggleX)
Bullet for XNA

------------------------------------------------------------Other ports------------------------------------------------------------
JigLibFlash - port of JigLib to Flash via ActionScript 3

------------------------------------------------------------"Abstraction Layers" that support multiple physics engines------------------------------------------------------------
Open Physics Abstraction Layer - OPAL (is this dead?)
pal

-------------------------------------------------Technical References (most are quite advanced)-------------------------------------------------
Tutorial presentation materials on game physics from GDC (Essential Math) A good starting point for beginners
Kenny Erleben's Ph.D Thesis on Multibody Dynamics Simulation
Article on Sweep-and-Prune collision detection by Pierre Terdiman
Dr. Jan Bender's page on impulse-based dynamics, with papers and a downloadable library
Claude Lacoursière's Ph.D Thesis on multibody dynamics simulation
Advanced Character Physics - Thomas Jakobsen (often referenced)
Position-Based Dynamics by Muller et al
Links to various papers by David Baraff et al

-----------------------------------------------------------Links to other physics directory/resource/wiki/blog sites-----------------------------------------------------------
Hardwire's Game Physics Resources
Erin Catto's Physics Weblog
Christer Ericson's Real-Time Collision Detection website (companion to his book)
David Eberly's Geometric Tools website - home of the Wild Magic game engine as well as numerous technical articles and useful code

PARTNERS