ODE/manual/衝突検出 - bambooflow Note

10. 衝突検出

ODEは2つの主要なコンポーネントを持っている：動力学シミュレーショ ン・エンジンおよび衝突検出エンジン。衝突エンジンは、各剛体の形に関する情報が与えられる。毎回のステップで、剛体がどれに互い触れるかを計算し、ユーザに生じる接触ポイント情報を渡す。次にユーザは、剛体間の接触ジョイント(contact joints)を作成する。

ODEの衝突検出の使用はオプションである。正しい接触情報を与えることができるならば、代替衝突検出システムは使用することができる。

10.1. 接触点

2つの剛体(body)が触れる場合、あるいは剛体がその環境で静止状態のものに触れる場合、接触は1つ以上の"接触点"で表わされる。各接触点は対応するdContactGeom構造体を持っている:

struct dContactGeom {
  dVector3 pos;       // contact position
  dVector3 normal;    // normal vector
  dReal depth;        // penetration depth  (侵入度)
  dGeomID g1,g2;      // the colliding geoms
};
 

posはグローバル座標に、接触位置を記録する。

depthは2つの剛体が互いに相互浸透する深さである。深さがそのとき0であるとき、2つの剛体はかすっている接触を持つ、つまり触れている。しかしながらこれはまれである。シミュレーションは完全に正確でなく、深さが非ゼロであって、しばしば極端に剛体に踏み込む。

normalは単位長さベクトル、概して言えば接触表面に垂直のベクトルである。

g1とg2は衝突したジオメトリオブジェクトである。

仕様は、剛体1が、深さ(depth)においてnormalベクトルに沿って移動される場合(または、剛体2が逆方向に同じ深さで移動される場合、等しい)、接触深さは0になる。これは剛体１のnormalベクトル点であることを意味する。

現実には、2つの剛体間の接触は複雑なものである。接触点によって接触を表すことは近似だけである。接触「patch(継ぎ当て)」あるいは「表面」はより物理的に正確かもしれない。しかし、高速シミュレーション・ソフトウェアの中でこれらのものを表すことは難問である。

シミュレーションに加えられた余分な接触点はさらに速度を遅くする。したがって、我々は速度のためにいくらか接触点を強引に無視することをする。例えば、2つのBoxの衝突はその状況のジオメトリを適切に表現するために多くの接触点が必要かもしれないが、最良の3点だけでを維持することができる。したがって、我々は近似の上に近似を重ねている。

10.2. Geoms

ジオメトリオブジェクト(あるいは略して"geoms")は衝突システムでの基本オブジェクトである。geomは1つの剛体の(球体もしくは箱のような)形を表すことができる、あるいは他のgeomsの1つのグループを表すことができる。―これは"space"と呼ばれる特殊なgeomの一種である。

どのgeomもゼロ以上の接触点を算出するために他のgeomに対して衝突させることができる。spaceは内部の接触点を算出するために、それらの含まれたgeomsをともに衝突させることができる拡張的な機能を持っている。

geomsは配置できたり(placeable)できなかったり(non-placeable)する。配置できるgeomはちょうど剛体のように位置ベクトルおよび3*3回転マトリックスを持っている。それはシミュレーション中に変更ができる。配置できないgeomの場合は、この機能を持っていない。例えば、これは移動できない環境のいくつかの静止状態のものに相当する。spaceは配置できないgeomsである。なぜならそれぞれ含まれるgeomがそれ自身の位置および方位を持つかもしれないが、space自体が位置および方位を持つことが意味をなさないためである。

剛体シミュレーションの中で衝突エンジンを使用するために、配置できるgeomsは剛体オブジェクトに関連付けさせる。これは、剛体から衝突エンジンがgeomsの位置および方位を得ることを可能にする。geomsは剛体とは 異なることに注意する。bodyの中のgeomはジオメトリ特性(サイズ、形、位置および方位)を持っているが、動力学特性(速度または質量のような)はない。bodyとgeomを合わせるとシミュレートされたオブジェクトの特性をすべて表す。

すべてのgeomは球体(sphere)、平面(plane)あるいは箱(box)のようなクラスの例である。以下には多くの内蔵クラスが記述されている。また、同様に自分自身のクラスを定義することができる。

配置できるgeomsの参照ポイントはその位置ベクトルによってコントロールされるポイントである。標準クラスのための参照ポイントは、通常geomの質量の中心と一致する。この特徴は、標準クラスが動剛体に容易に接続されることを可能にする。参照の他のポイントが要求される場合、変形したオブジェクト(transformation object)はカプセル化したgeomとして使用することができる。

すべてのgeomsに当てはまる概念および関数は、様々なジオメトリクラスやそれらを操作する関数を以下に記述する。

10.3. space

spaceは他のgeomsを含むことができる配置できないgeomである。それは、動力学の代わりに衝突に当てはまる以外は、"world"の剛体の概念に似ている。

spaceオブジェクトは衝突検出をより速く生成するために存在する。spaceなしではすべてのgeomsシングルペアについての接触点を得るためにdCollideを呼ぶことにより、シミュレーション中の接触を生成しようとするだろう。N個のgeomsについてはO(Nの2乗)個のテストとなり、あなたの環境が多くのオブジェクトを持っている場合、それは計算コストがかかりすぎる。

よりよいアプローチは、space中にgeomを入れてdSpaceCollideを呼ぶことである。スペースはそのときに衝突の選択を行う。これはどのgeomsペアが潜在的に交差しているかをすばやく識別することを意味する。これらのペアはコールバック関数に渡されて、次にdCollideを呼ぶことができる。これは不要なdCollideのテストで起こっている多くを保存する。なぜならば、コールバック関数に渡したペアの数は、あらゆる物体と物体のペアの極少数だからである。

spaceは他のspaceを含むことができる。さらに衝突検出速度を最適化するために衝突環境をいくつかの階層に分割するのに役立つ。これについては下により詳細に記述されている。

10.4. 一般geom関数

geomに適用することができる関数を以下に示す。

void dGeomDestroy (dGeomID);

spaceから取り除いてgeomを破棄する。この関数はいくつかのタイプのgeomを破棄するが、geomの生成はそのタイプのための生成関数を呼ばなければならない。

spaceは破棄されたとき、cleanup modeが１(デフォルト)のとき、このspaceにあるすべてのgeomも同様に自動的に破棄する。

void dGeomSetData (dGeomID, void *);
void *dGeomGetData (dGeomID);

これらの関数は、geomに記憶したユーザ定義されたデータポインタを設定・取得する。

void dGeomSetBody (dGeomID, dBodyID);
dBodyID dGeomGetBody (dGeomID);

これらの関数は、配置できるgeomに関連したbodyの設定・取得をする。geomにbodyを設定すると、自動的にbodyとgeomの位置ベクトルおよび回転マトリックスを組み合わされる。そのため、1つの位置か四元数の設定は、両方のオブジェクトのために設定することになる。

ゼロのbody IDを設定することは、geomに自身に(どんなbodyからも独立している)位置と回転を与える。すでにgeomがbodyに接続しているならば、その新しい独立した位置/回転はbodyの現在の位置/回転に設定される。

配置できないgeomでこれらの関数を呼ぶとODEのデバッグにおいて実行時エラーとなる。

void dGeomSetPosition (dGeomID, dReal x, dReal y, dReal z);
void dGeomSetRotation (dGeomID, const dMatrix3 R);
void dGeomSetQuaternion (dGeomID, const dQuaternion);

配置できるgeomの位置ベクトル、回転マトリックスまたは方位の設定をする。これらの関数はdBodySetPosition、dBodySetRotation、dBodySetQuaternionと類似している。geomはbodyに取り付けられると、bodyの位置／回転／四元数もまた変更される。

配置できないgeomでこれらの関数を呼ぶとODEのデバッグにおいて実行時エラーとなる。

const dReal * dGeomGetPosition (dGeomID);
const dReal * dGeomGetRotation (dGeomID);
void dGeomGetQuaternion (dGeomID, dQuaternion result);

最初の2つは、geomの位置ベクトルと回転マトリックスのポインタを返す。返された値は内部のデータ構造へのポインタであるので、geomに変化がなされるまで、ベクトルは有効である。geomがbodyに取り付けられると、bodyの位置/回転ポインタは返される。すなわち、結果はdBodyGetPositionまたはdBodyGetRotationを呼ぶことと同一である。

dGeomGetQuaternionは、提供されるspaceに、geomの四元数をコピーする。geomがbodyに取り付けられると、bodyの四元数は返される。すなわち、もたらされる四元数の結果はdBodyGetQuaternionを呼ぶ結果と同じである。

配置できないgeomでこれらの関数を呼ぶとODEのデバッグにおいて実行時エラーとなる。

void dGeomGetAABB (dGeomID, dReal aabb[6]);

Return in aabb an axis aligned bounding box that surrounds the given geom. The aabb array has elements (minx,maxx,miny,maxy,minz,maxz). If the geom is a space, a bounding box that surrounds all contained geoms is returned.
aabbに、与えられたgeomを囲むbounding boxを並べた軸をaabbとして返す。aabb配列には、要素（minx,maxx,miny,maxy,minz,maxz）がある。geomがspaceであるならば、すべての含まれたgeomsを囲むbounding boxは返さる。

それがgeomがbounding boxは計算された最後の時から動かなかったと確定することができるならば、この関数は予め計算されキャッシュされたbounding boxを返すかもしれない。

int dGeomIsSpace (dGeomID);

与えられたgeomがspaceのとき1を返す。そうでなければ0を返す。

dSpaceID dGeomGetSpace (dGeomID);

与えられたジオメトリを含むspaceを返す。spaceに含まれていないとき0を返す。

int dGeomGetClass (dGeomID);

与えられたgeomによりクラス番号を返す。
標準クラス番号は次のとおり、

dSphereClass	Sphere
dBoxClass	Box
dCCylinderClass	Capped cylinder
dCylinderClass	Regular flat-ended cylinder
dPlaneClass	Infinite plane (non-placeable)
dGeomTransformClass	Geometry transform
dRayClass	Ray
dTriMeshClass	Triangle mesh
dSimpleSpaceClass	Simple space
dHashSpaceClass	Hash table based space

ユーザ定義されたクラスはそれら自身の番号を返す。

void dGeomSetCategoryBits (dGeomID, unsigned long bits);
void dGeomSetCollideBits (dGeomID, unsigned long bits);
unsigned long dGeomGetCategoryBits (dGeomID);
unsigned long dGeomGetCollideBits (dGeomID);

与えられたgeomのために”category”と”collide”のビットフィールドを設定・取得する。これらのビットフィールドは支配するspaceにより使われ、それぞれのgeomが相互作用する。ビットフィールドは少なくとも32ビット長であることが保証される。新区生成されたgeomのcategoryとcollideのデフォルト値はすべてのビットを設定する。

void dGeomEnable (dGeomID);
void dGeomDisable (dGeomID);
int dGeomIsEnabled (dGeomID);

geomを有効/無効を設定する。無効geomはdSpaceCollideとdSpaceCollide2に完全に無視される。けれどもspaceのメンバのままである。

dGeomIsEnabled関数はgeomが有効のとき1を返し、無効のとき0を返す。新しいgeomは有効状態のとき生成される。

10.5. 衝突検出

"world"の衝突検出はspaceを作ったときとspaceにgeomを追加したときに生成される。毎時間ステップで互いに交わった全てのgeomについて接触リストを生成することが必要となる。次の3つの関数はこのために使われる：

• dCollideは2つのgeomが交差したら接触ポイントを生成する。
• dSpaceCollideはスペース内の潜在的に交わったgeomペアのいずれかを決定して、候補ペアと一緒にコールバック関数を呼ぶ。これは接触ポイントを直接生成しない。それはユーザがいくつかのペアを特別に扱うかもしれないからである。例えば衝突を無視したり、異なった接触生成方法を使うなどである。そのような各ペアに対し要求するべきかどうかといった決定はコールバック関数の中で下される。
• dSpaceCollide2は、1つのspaceのいずれかのgeomsが別のspaceのいずれかのgeomsと潜在的に交わるかを決定して、各候補ペアを備えたコールバック関数を呼ぶ。またそれはspaceに対する非spaceであるgeomもテストすることができる。衝突階層がある場合、つまり、他のspaceを含むspaceがある場合にこの関数は有用である。

The collision system has been designed to give the user maximum flexibility to decide which objects will be tested against each other. This is why are there are three collision functions instead of, for example, one function that just generates all the contact points.

Spaces may contain other spaces. These sub-spaces will typically represent a collection of geoms (or other spaces) that are located near each other. This is useful for gaining extra collision performance by dividing the collision world into hierarchies. Here is an example of where this is useful:

Suppose you have two cars driving over some terrain. Each car is made up of many geoms. If all these geoms were inserted into the same space, the collision computation time between the two cars would always be proportional to the total number of geoms (or even to the square of this number, depending on which space type is used).

To speed up collision a separate space is created to represent each car. The car geoms are inserted into the car-spaces, and the car-spaces are inserted into the top level space. At each time step dSpaceCollide is called for the top level space. This will do a single intersection test between the car-spaces (actually between their bounding boxes) and call the callback if they touch. The callback can then test the geoms in the car-spaces against each other using dSpaceCollide2. If the cars are not near each other then the callback is not called and no time is wasted performing unnecessary tests.

If space hierarchies are being used then the callback function may be called recursively, e.g. if dSpaceCollide calls the callback which in turn calls dSpaceCollide with the same callback function. In this case the user must make sure that the callback function is properly reentrant.

Here is a sample callback function that traverses through all spaces and sub-spaces, generating all possible contact points for all intersecting geoms:

void nearCallback (void *data, dGeomID o1, dGeomID o2)
  {
    if (dGeomIsSpace (o1) || dGeomIsSpace (o2)) {
      // colliding a space with something
      dSpaceCollide2 (o1,o2,data,&nearCallback);
      // collide all geoms internal to the space(s)
      if (dGeomIsSpace (o1)) dSpaceCollide (o1,data,&nearCallback);
      if (dGeomIsSpace (o2)) dSpaceCollide (o2,data,&nearCallback);
    }
    else {
      // colliding two non-space geoms, so generate contact
      // points between o1 and o2
      int num_contact = dCollide (o1,o2,max_contacts,contact_array,skip);
      // add these contact points to the simulation
      ...
    }
  }
 
  ...
 
  // collide all objects together
  dSpaceCollide (top_level_space,0,&nearCallback);
 

A space callback function is not allowed to modify a space while that space is being processed with dSpaceCollide or dSpaceCollide2. For example, you can not add or remove geoms from a space, and you can not reposition the geoms within a space. Doing so will trigger a runtime error in the debug build of ODE.
スペース・コールバック関数は、そのスペースが dSpaceCollideまたはdSpaceCollide2で処理されている一方、スペースを修正することを許されていない。例えば、スペースからの geomsを追加もしくは削除することができない。そして、スペース内のgeomsの位置を変えることができない。そうすることで、ODEのdebug構 造におけるランタイム・エラーが引き起こされる。

10.5.1. CategoryとCollideビットフィールド

Each geom has a ``category'' and ``collide'' bitfield that can be used to assist the space algorithms in determining which geoms should interact and which should not. Use of this feature is optional - by default geoms are considered to be capable of colliding with any other geom.

Each bit position in the bitfield represents a different category of object. The actual meaning of these categories (if any) is user defined. The category bitfield indicates which categories a geom is a member of. The collide bitfield indicates which categories the geom will collide with during collision detection.

A pair of geoms will be considered by dSpaceCollide and dSpaceCollide2 for passing to the callback only if one of them has a collide bit set that corresponds to a category bit in the other. The exact test is as follows:

// test if geom o1 and geom o2 can collide
  cat1 = dGeomGetCategoryBits (o1);
  cat2 = dGeomGetCategoryBits (o2);
  col1 = dGeomGetCollideBits (o1);
  col2 = dGeomGetCollideBits (o2);
  if ((cat1 & col2) || (cat2 & col1)) {
    // call the callback with o1 and o2
  }
  else {
    // do nothing, o1 and o2 do not collide
  }
 

Note that only dSpaceCollide and dSpaceCollide2 use these bitfields, they are ignored by dCollide.

Typically a geom will belong only to a single category, so only one bit will be set in the category bitfield. The bitfields are guaranteed to be at least 32 bits wide, so the user is able to specify an arbitrary pattern of interactions for up to 32 objects. If there are more than 32 objects then some of them will obviously have to have the same category.

Sometimes the category field will contain multiple bits set, e.g. if the geom is a space them you may want to set the category to the union of all the geom categories that are contained.

Design note: Why don't we just have a single category bitfield and use the test (cat1 & cat2) ? This is simpler, but a single field requires more bits to represent some patterns of interaction. For example, if 32 geoms have an interaction pattern that is a 5 dimensional hypercube, 80 bit are required in the simpler scheme. The simpler scheme also makes it harder to determine what the categories should be for some situations.

10.5.2. 衝突検出関数

int dCollide (dGeomID o1, dGeomID o2, int flags, dContactGeom *contact, int skip);

Given two geoms o1 and o2 that potentially intersect, generate contact information for them. Internally, this just calls the correct class-specific collision functions for o1 and o2.
潜在的に交差する2の与えられたgeoms o1およびo2は、それらのための連絡情報を生成する。内部では、o1とo2のための正確なクラス特有の衝突関数を呼ぶ。

flags specifies how contacts should be generated if the geoms touch. The lower 16 bits of flags is an integer that specifies the maximum number of contact points to generate. Note that if this number is zero, this function just pretends that it is one - in other words you can not ask for zero contacts. All other bits in flags must be zero. In the future the other bits may be used to select from different contact generation strategies.
geomsが触れる場合どのように接触を生成しなければならないか指定する。低16ビットフラグは生成する接触ポイントの最大数を指定する整数である。こ の数が0である場合、これが1として振る舞われることに注意する。言いかえれば、0 個の接触を求めることはできない。flagsの他のすべてのビットは0である。今後、他のビットは異なる接触生成方法から選択するために使用されてもかま わない。

contact points to an array of dContactGeom structures. The array must be able to hold at least the maximum number of contacts. These dContactGeom structures may be embedded within larger structures in the array - the skip parameter is the byte offset from one dContactGeom to the next in the array. If skip is sizeof(dContactGeom) then contact points to a normal (C-style) array. It is an error for skip to be smaller than sizeof(dContactGeom).
dContactGeom構造体の1つの配列へのポインタ。配列は、少なくとも接触の最大数を保持することができる。このdContactGeom構造体は配列中のより大きな構造体内に埋め込まれるかもしれない。skipパラ メータはdContactGeomを次の配列へオフセットするバイト数である。skipがsizeof(dContactGeom)である場合、 contactは通常(C-スタイル)の配列を指す。skipがsizeof(dContactGeom)より小さいときはエラーである。

If the geoms intersect, this function returns the number of contact points generated (and updates the contact array), otherwise it returns 0 (and the contact array is not touched).
geomsが交差する時に、この関数は生成された接触ポイントの数を返 す(contactの配列を更新する)、そうでないときは、0を返す(contactの配列は更新されない)。

If a space is passed as o1 or o2 then this function will collide all objects contained in o1 with all objects contained in o2, and return the resulting contact points. This method for colliding spaces with geoms (or spaces with spaces) provides no user control over the individual collisions. To get that control, use dSpaceCollide or dSpaceCollide2 instead.
スペースがo1またはo2として通過される場合、この関数は、o2のす べてのオブジェクトをo1のすべてのオブジェクトに衝突させて、生じる接触ポイントを返すだろう。geomとスペース(またはスペースとスペース）を衝突 させるこの方法は、個々の衝突に対するユーザコントロールは備えていない。そのコントロールを得るためには、dSpaceCollideまたは dSpaceCollide2を代わりに使用してください。

If o1 and o2 are the same geom then this function will do nothing and return 0. Technically speaking an object intersects with itself, but it is not useful to find contact points in this case.
o1とo2が同じgeomである場合、この関数は何もせずに0を返す。 技術的に話すと、1つのオブジェクト自身の交差であるが、この場合に接触ポイントを見つけることは有用ではない。

This function does not care if o1 and o2 are in the same space or not (or indeed if they are in any space at all).
この関数はo1とo2が同じスペースであるかどうか(または、すべてで の任意のスペースである場合)は配慮しない。

void dSpaceCollide (dSpaceID space, void *data, dNearCallback *callback);

This determines which pairs of geoms in a space may potentially intersect, and calls the callback function with each candidate pair. The callback function is of type dNearCallback, which is defined as:
これは、スペース中のgeomsペアのどれが交わるか決定し、各候補ペ アを備えたコールバック関数を呼ぶ。
callback関数はタイプdNearCallbackであり、それは次のように定義されている:

typedef void dNearCallback (void *data, dGeomID o1, dGeomID o2);

The data argument is passed from dSpaceCollide directly to the callback function. Its meaning is user defined. The o1 and o2 arguments are the geoms that may be near each other.
data引数は、dSpaceCollideからコールバック関数に直 接渡される。その意味はユーザ定義されている。o1とo2の引数は互い近距離にあるgeomsである。

The callback function can call dCollide on o1 and o2 to generate contact points between each pair. Then these contact points may be added to the simulation as contact joints. The user's callback function can of course chose not to call dCollide for any pair, e.g. if the user decides that those pairs should not interact.

Other spaces that are contained within the colliding space are not treated specially, i.e. they are not recursed into. The callback function may be passed these contained spaces as one or both geom arguments.

dSpaceCollide() is guaranteed to pass all intersecting geom pairs to the callback function, but it may also make mistakes and pass non-intersecting pairs. The number of mistaken calls depends on the internal algorithms used by the space. Thus you should not expect that dCollide will return contacts for every pair passed to the callback.

void dSpaceCollide2 (dGeomID o1, dGeomID o2, void *data, dNearCallback *callback);

This function is similar to dSpaceCollide, except that it is passed two geoms (or spaces) as arguments. It calls the callback for all potentially intersecting pairs that contain one geom from o1 and one geom from o2.

The exact behavior depends on the types of o1 and o2:

• If one argument is a non-space geom and the other is a space, the callback is called with all potential intersections between the geom and the objects in the space.
• If both o1 and o2 are spaces then this calls the callback for all potentially intersecting pairs that contain one geom from o1 and one geom from o2. The algorithm that is used depends on what kinds of spaces are being collided. If no optimized algorithm can be selected then this function will resort to one of the following two strategies:

1. All the geoms in o1 are tested one-by-one against o2.
2. All the geoms in o2 are tested one-by-one against o1.

The strategy used may depends on a number of rules, but in general the space with less objects has its geoms examined one-by-one.

• If both arguments are the same space, this is equivalent to calling dSpaceCollide on that space.
• If both arguments are non-space geoms, this simply calls the callback once with these arguments.

If this function is given a space and an geom X in that same space, this case is not treated specially. In this case the callback will always be called with the pair (X,X), because an objects always intersects with itself. The user may either test for this case and ignore it, or just pass the pair (X,X) to dCollide (which will be guaranteed to return 0).

10.6. space関数

There are several kinds of spaces. Each kind uses different internal data structures to store the geoms, and different algorithms to perform the collision culling:
スペースはいくつか種類がある。それぞれの種類はgeomsを格納する ために違う内部のデータ構造体を使用し、そして衝突の選択を行うのは異なるアルゴリズムを使用する：

• Simple space. This does not do any collision culling - it simply checks every possible pair of geoms for intersection, and reports the pairs whose AABBs overlap. The time required to do intersection testing for n objects is O(n2). This should not be used for large numbers of objects, but it can be the preferred algorithm for a small number of objects. This is also useful for debugging potential problems with the collision system.

単純なスペース。これは、衝突選択を行わない。それは、単に交 差におけるすべての可能性のあるgeomsペアをチェックし、AABBが重なり合うそのペアを報告する。n個のオブジェクトにおいて、交差試験を行うのに 必要な時間はO(nの2乗)である。これは多くのオブジェクトのために使用されてはならない。しかし、少数のオブジェクト用の好ましいアルゴリズムであ る。さらに、これは、衝突システムに関する潜在的な問題をデバッグするのに役立つ。

• Multi-resolution hash table space. This uses an internal data structure that records how each geom overlaps cells in one of several three dimensional grids. Each grid has cubical cells of side lengths 2i, where i is an integer that ranges from a minimum to a maximum value. The time required to do intersection testing for n objects is O(n) (as long as those objects are not clustered together too closely), as each object can be quickly paired with the objects around it.

多分割ハッシュテーブルのスペース。これは、各geomがいく つかの3次元のグリッドのうち1つの中のセルをどのように重ねるかを記録するための、内部のデータ構造体を使用する。iが最小から最大の値まで及ぶ整数で ある場合、各グリッドは側面の長さ2のi乗の立方体のセルを持つ。各オブジェクトがそのまわりのオブジェクトと速くペアになることができるので、nオブ ジェクトのために交差試験を行うのに必要な時間は(それらのオブジェクトがともにあまり緊密にクラスターにされない限り)O(n)である。

• Quadtree space. This uses a pre-allocated hierarchical grid-based AABB tree to quickly cull collision checks. It's exceptionally quick for large amounts of objects in landscape-shaped worlds. The amount of memory used is 4^depth * 32 bytes. Currently dSpaceGetGeom is not implemented for the quadtree space.

Quadtreeスペース。これは、速く衝突チェックを選択さ せるために、あらかじめ割り付けられた階層的なグリッドベースのAABBツリーを使用する。それは、景観がある世界の大量のオブジェクトに対し非常に高速 になる。使用されるメモリ量は、4＾depth * 32バイトです。現在、dSpaceGetGeomはquadtreeスペースのために導入されない。

Here are the functions used for spaces:
ここに、スペースのために使用された関数がある：

dSpaceID dSimpleSpaceCreate (dSpaceID space);
dSpaceID dHashSpaceCreate (dSpaceID space);

Create a space, either of the simple or multi-resolution hash table kind. If space is nonzero, insert the new space into that space.
スペースを作成する。各々シンプルか、多分割のハッシュテーブルのどち らか。spaceがゼロでない場合、スペースの中に新しいスペースを挿入する。

dSpaceID dQuadTreeSpaceCreate (dSpaceID space, dVector3 Center, dVector3 Extents, int Depth);

Creates a quadtree space. center and extents define the size of the root block. depth sets the depth of the tree - the number of blocks that are created is 4^depth.

void dSpaceDestroy (dSpaceID);

This destroys a space. It functions exactly like dGeomDestroy except that it takes a dSpaceID argument. When a space is destroyed, if its cleanup mode is 1 (the default) then all the geoms in that space are automatically destroyed as well.

void dHashSpaceSetLevels (dSpaceID space, int minlevel, int maxlevel);
void dHashSpaceGetLevels (dSpaceID space, int *minlevel, int *maxlevel);

Sets and get some parameters for a multi-resolution hash table space. The smallest and largest cell sizes used in the hash table will be 2^minlevel and 2^maxlevel respectively. minlevel must be less than or equal to maxlevel.

In dHashSpaceGetLevels the minimum and maximum levels are returned through pointers. If a pointer is zero then it is ignored and no argument is returned.

void dSpaceSetCleanup (dSpaceID space, int mode);
int dSpaceGetCleanup (dSpaceID space);

Set and get the clean-up mode of the space. If the clean-up mode is 1, then the contained geoms will be destroyed when the space is destroyed. If the clean-up mode is 0 this does not happen. The default clean-up mode for new spaces is 1.
スペースのクリーンアップモードをセット、ゲットをする。クリーンアッ プモードが1である場合、スペースが破棄される時、そこに含まれるgeomsが破壊される。クリーンアップモードが0である場合、これは起こらない。新し いスペース用のデフォルトクリーンアップモードは1である。

void dSpaceAdd (dSpaceID, dGeomID);

Add a geom to a space. This does nothing if the geom is already in the space. This function can be called automatically if a space argument is given to a geom creation function.
スペースへgeomを加える。geomが既にスペースである場合、これ は何もしない。space引数がgeom生成関数に与えられる場合、この関数は自動的に呼ぶことができる。

void dSpaceRemove (dSpaceID, dGeomID);

Remove a geom from a space. This does nothing if the geom is not actually in the space. This function is called automatically by dGeomDestroy if the geom is in a space.

int dSpaceQuery (dSpaceID, dGeomID);

Return 1 if the given geom is in the given space, or return 0 if it is not.

int dSpaceGetNumGeoms (dSpaceID);

Return the number of geoms contained within a space.

dGeomID dSpaceGetGeom (dSpaceID, int i);

Return the i'th geom contained within the space. i must range from 0 to dSpaceGetNumGeoms()-1.

If any change is made to the space (including adding and deleting geoms) then no guarantee can be made about how the index number of any particular geom will change. Thus no space changes should be made while enumerating the geoms.

This function is guaranteed to be fastest when the geoms are accessed in the order 0,1,2,etc. Other non-sequential orders may result in slower access, depending on the internal implementation.