Difference between revisions of "KCL (File Format)"
m (More documentation and typo fix) |
|||
(34 intermediate revisions by 14 users not shown) | |||
Line 1: | Line 1: | ||
− | '''KCL Files''' are collision files used in [[Mario Kart Wii]] and many other games. They have been used since at least [[Mario Kart DS]]. The documentation here is specifically for the | + | '''KCL Files''' are collision files used in [[Mario Kart Wii]] and many other games. They have been used since at least [[Mario Kart DS]]. The documentation here is specifically for the Mario Kart Wii implementation, although other implementations are likely to be similar.<br /> |
The KCL files contain simplified versions of model files in order to allow rapid collision detection. They use an octree for efficient spatial indexing, as well as storing the actual triangles of the models in a more rapidly accessible format. | The KCL files contain simplified versions of model files in order to allow rapid collision detection. They use an octree for efficient spatial indexing, as well as storing the actual triangles of the models in a more rapidly accessible format. | ||
− | |||
− | |||
− | |||
== File Format == | == File Format == | ||
The basic file format consists of a header, and four data sections. | The basic file format consists of a header, and four data sections. | ||
+ | |||
=== Header === | === Header === | ||
− | The header is a 0x3c byte structure as follows. | + | The header is a 0x38 or 0x3c byte structure as follows. |
{| class="wikitable" | {| class="wikitable" | ||
− | ! Offset !! Type !! Description | + | ! Offset !! Type !! Name !! Description |
|- | |- | ||
− | | 0x00 || u32 || | + | | 0x00 || u32 || pos_data_offset || 0-indexed offset to array of position vectors. |
|- | |- | ||
− | | 0x04 || u32 || | + | | 0x04 || u32 || nrm_data_offset || 0-indexed offset to array of normal vectors. |
|- | |- | ||
− | | 0x08 || u32 || | + | | 0x08 || u32 || prism_data_offset || 1-indexed offset to array of triangular prisms. |
|- | |- | ||
− | | 0x0c || u32 || Offset to | + | | 0x0c || u32 || block_data_offset || Offset to collision octree blocks. |
|- | |- | ||
− | | 0x10 || | + | | 0x10 || f32 || prism_thickness || Depth of a triangular prism along its normal vector. |
|- | |- | ||
− | | 0x14 || | + | | 0x14 || Vec3 || area_min_pos || Smallest possible coordinate in the model |
|- | |- | ||
− | | 0x20 || u32 || X mask | + | | 0x20 || u32 || area_x_width_mask || X mask. X coordinates with bits outside this mask are outside the model (See section 4) |
|- | |- | ||
− | | 0x24 || u32 || Y mask | + | | 0x24 || u32 || area_y_width_mask || Y mask. Y coordinates with bits outside this mask are outside the model (See section 4) |
|- | |- | ||
− | | 0x28 || u32 || Z mask | + | | 0x28 || u32 || area_z_width_mask || Z mask. Z coordinates with bits outside this mask are outside the model (See section 4) |
|- | |- | ||
− | | 0x2c || u32 || | + | | 0x2c || u32 || block_width_shift || Octree leaf block size shift (size = 2^block_width_shift = 1 << block_width_shift) |
|- | |- | ||
− | | 0x30 || u32 || Y shift | + | | 0x30 || u32 || area_x_blocks_shift || Y shift. Used to form the index of the root block's children (See section 4 algorithm) |
|- | |- | ||
− | | 0x34 || u32 || Z shift | + | | 0x34 || u32 || area_xy_blocks_shift || Z shift. Used to form the index of the root block's children (See section 4 algorithm) |
− | |||
− | |||
|- | |- | ||
+ | | 0x38 || f32 || OPTIONAL[ sphere_radius ] || Maximum radius of a sphere that can be collided with this file. This field must be used when computing the octree; e.g., to consider which triangles are inside an octree 32x32 block, it is insufficient to just consider a 32x32 cube since it would miss prisms a player could hit while being on the edge of the box. Therefore, it is necessary to consider a distance field with constant distance of sphere_radius. From analysis of official files, this is not just a larger cube, but actually a curvy, beveled figure (especially noticeable with small cubes where sphere_radius > width). Official tools will only include prisms that are actually reachable in leaf nodes which produces more efficient files than homebrew. This field is not provided by KCL files from [[Super Mario Galaxy]]/other platformers. Therefore, using those tools for KCL may be problematic as [[Mario Kart Wii]] expects this value. | ||
|} | |} | ||
All offsets are relative to the start of the file. <br/> | All offsets are relative to the start of the file. <br/> | ||
− | The meaning of the shift and mask values is explained in section 4. | + | The meaning of the shift and mask values is explained in section 4. |
− | === Section 1 - | + | |
− | Section 1 is simply a large array of | + | An official KCL generation algorithm can be observed in Super Mario Galaxy's <code>DynamicCollisionObj::updateCollisionHeader()</code>. A decompilation is provided below: |
+ | <pre> | ||
+ | void DynamicCollisionObj::updateCollisionHeader() | ||
+ | { | ||
+ | Vec min, max, extent; | ||
+ | int masks[3]; | ||
+ | int extent_int_x, extent_int_y, extent_int_z; | ||
+ | int max_entropy = 0, component = 0, component_ = 0, bits_sel, mask_sel, i, v8, bit_shift, area_y_width_mask, area_z_width_mask; | ||
+ | |||
+ | // Compute bounding box and extent | ||
+ | MR::createBoundingBox(this->mVertices, this->mNumVertices, &min, &max); | ||
+ | JGeometry::TVec3<f>::TVec3<f>(&extent, &max); | ||
+ | JGeometry::TVec3<f>::__ami(&extent, &min); | ||
+ | |||
+ | // Initialize masks with extent | ||
+ | extent_int_x = (int)extent.x; | ||
+ | extent_int_y = (int)extent.y; | ||
+ | extent_int_z = (int)extent.z; | ||
+ | masks[0] = extent_int_x; | ||
+ | masks[1] = extent_int_y; | ||
+ | masks[2] = extent_int_z; | ||
+ | if ( !extent_int_x ) masks[0] = 1; | ||
+ | if ( !masks[1] ) masks[1] = 1; | ||
+ | if ( !masks[2] ) masks[2] = 1; | ||
+ | |||
+ | // Find highest number of bits to shift | ||
+ | for (component = 0; component < 3; ++component) | ||
+ | { | ||
+ | bits_sel = 0x80000000; | ||
+ | mask_sel = 0xFFFFFFFF; | ||
+ | i = 0; | ||
+ | v8 = 32; | ||
+ | while ( (masks[component] & bits_sel) == 0 ) | ||
+ | { | ||
+ | bits_sel >>= 1; | ||
+ | mask_sel >>= 1; | ||
+ | ++i; | ||
+ | if ( !--v8 ) | ||
+ | goto CONTINUE; | ||
+ | } | ||
+ | masks[component] = ~mask_sel; | ||
+ | if ( max_entropy < i ) | ||
+ | max_entropy = i; | ||
+ | CONTINUE:; | ||
+ | } | ||
+ | |||
+ | // Update header fields | ||
+ | bit_shift = 33 - max_entropy; | ||
+ | area_y_width_mask = masks[1]; | ||
+ | this->mpHeader->area_x_width_mask = masks[0]; | ||
+ | area_z_width_mask = masks[2]; | ||
+ | this->mpHeader->area_y_width_mask = area_y_width_mask; | ||
+ | this->mpHeader->area_z_width_mask = area_z_width_mask; | ||
+ | this->mpHeader->block_width_shift = bit_shift; | ||
+ | JGeometry::TVec3<f>::__as(&this->mpHeader->area_min_pos, &min); | ||
+ | } | ||
+ | </pre> | ||
+ | |||
+ | === Section 1 - Position Vectors === | ||
+ | Section 1 is simply a large array of position vectors, stored as 3 successive floats for X, Y and Z. The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 2 from the start of Section 1; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the prisms list and keep track of the highest position index. | ||
+ | |||
=== Section 2 - Normals === | === Section 2 - Normals === | ||
− | Section 2 is much the same as section 1, in that it is a large array of | + | Section 2 is much the same as section 1, in that it is a large array of normal vectors. Again the values are stored as 3 successive floats for X, Y and Z. The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 3 from the start of Section 2; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the prisms list and keep track of the highest normal index across every field (face normals + edge normals). |
+ | |||
+ | === Section 3 - Triangular Prisms === | ||
+ | The third section is a pool of triangular prisms encoded as face normal vectors and a height. The offset to this section is stored as 0x10 less than the actual location of the data because this section is one indexed in section 4. The structure of each entry in this section is a 0x10 byte structure given below. | ||
+ | |||
+ | The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 4 from the start of Section 3; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the '''octree''' and keep track of the highest prism index. | ||
− | |||
− | |||
{| class="wikitable" | {| class="wikitable" | ||
− | ! Offset !! Type !! Description | + | ! Offset !! Type !! name !! Description |
− | |||
− | |||
|- | |- | ||
− | | | + | | 0x00 || f32 || height || Triangle altitude from Vertex 1 to the opposite side. |
|- | |- | ||
− | | | + | | 0x04 || u16 || pos_i || Vertex 1 position index (0 based index into section 1). |
|- | |- | ||
− | | | + | | 0x06 || u16 || fnrm_i || Face normal vector index (0 based index into section 2). |
|- | |- | ||
− | | | + | | 0x08 || u16 || enrm1_i || First edge normal vector (in counterclockwise order) -- Normal A index (0 based index into section 2). |
|- | |- | ||
− | | | + | | 0x0a || u16 || enrm2_i || Second edge normal vector (in counterclockwise order) -- Normal B index (0 based index into section 2). |
|- | |- | ||
− | | | + | | 0x0c || u16 || enrm3_i || Third edge normal vector (in counterclockwise order) -- Normal C index (0 based index into section 2). |
|- | |- | ||
+ | | 0x0e || u16 || attribute || [[KCL flag|Collision attribute]]. In Super Mario Galaxy, this is an attribute *index* into an Attribute Lookup Table. In Mario Kart Wii, the attribute is stored directly in prisms. | ||
|} | |} | ||
− | All | + | |
+ | All indices in this section are 0 indexed. The position index is an index for section 1, and the others are indices to section 2. The coordinate system is right handed. | ||
+ | |||
+ | The decoding algorithm can be seen in [[Mario Kart 7]]'s <code>KDGndCol::PolygonMesh::parseModel(const KDGndCol::KColData&, bool)</code>. It is described below: | ||
<pre> | <pre> | ||
− | Vertex1 = | + | CrossA = cross(enrm1, fnrm) |
− | Vertex2 = | + | CrossB = cross(enrm2, fnrm) |
− | Vertex3 = | + | Vertex1 = pos |
+ | Vertex2 = pos + CrossB * (height / dot(CrossB, enrm3)) | ||
+ | Vertex3 = pos + CrossA * (height / dot(CrossA, enrm3)) | ||
</pre> | </pre> | ||
− | A method for converting three | + | An encoding algorithm can be seen in Super Mario Galaxy's <code>DynamicCollisionObj::updateTriangle()</code>. A method for converting three vertices into the KCL form is given below. |
+ | One approach is described below: (this assumes vertices are arranged counter-clockwise when viewed from their front side) | ||
<pre> | <pre> | ||
− | + | pos = Vertex1 | |
− | + | fnrm = normalize(cross( Vertex2 - Vertex1, Vertex3 - Vertex1 )) | |
− | + | enrm1 = normalize(cross(fnrm, Vertex3 - Vertex1)) | |
− | + | enrm2 = normalize(-cross(fnrm, Vertex2 - Vertex1)) | |
− | + | enrm3 = normalize(cross(fnrm, Vertex2 - Vertex3)) | |
− | + | Length = dot(Vertex2 - Vertex1, enrm3) | |
</pre> | </pre> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | === | + | === Section 4 - Spatial Index === |
− | + | Offsets in this section are interpreted differently depending on if that offset represents a non-leaf or a leaf block. The first entry represents the root block which is not a leaf block and contains the entire model. Subsequent blocks are subdivisions of the root block until the leaf blocks are reached. | |
− | + | * In non-leaf blocks, the offset points to an array of 8 u32 offsets, which are the offsets of the block's children. | |
+ | * In leaf blocks, the offset points to an array of u16 prism indices. Each of these is a 1-based index to section 3, which is a triangle that must be checked by an object at the original location. The first entry of a list is always 0, which serves as a 0 termination for the previous list. | ||
+ | |||
+ | As an example, MKW's algorithm for finding the leaf block that contains a point is as follows | ||
+ | <pre> | ||
+ | u16* KCollisionOctree::searchBlock(const EGG::Vector3f& point) { | ||
+ | // Calculate the x, y, and z offsets of the point from the minimum | ||
+ | // corner of the tree's bounding box. | ||
+ | const int x = point.x - this->area_min_pos.x; | ||
− | + | // Check if the point is outside the tree's bounding box in the x, y, | |
− | + | // or z dimensions. If it is, return 0. | |
− | + | if ((x & this->area_x_width_mask) != 0) { | |
− | + | return 0; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | const int y = point.y - this->area_min_pos.y; | |
− | + | if ((y & this->area_y_width_mask) != 0) { | |
− | + | return 0; | |
+ | } | ||
− | = | + | const int z = point.z - this->area_min_pos.z; |
− | { | + | if ((z & this->area_z_width_mask) != 0) |
− | + | { | |
− | + | return 0; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | // Initialize the current tree node to the root node of the tree. | |
− | + | u32 shift = this->block_width_shift; | |
− | + | u8* curBlock = this->block_data; | |
+ | s32 offset; | ||
− | = | + | // Traverse the tree to find the leaf node containing the input point. |
− | + | u32 index = 4 * (((u32)z >> shift) << this->area_xy_blocks_shift | |
− | + | | ((u32)y >> shift) << this->area_x_blocks_shift | |
− | + | | (u32)x >> shift); | |
− | |||
− | |- | ||
− | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | ' | + | while (true) { |
− | + | // Get the offset of the current node's child node. | |
− | + | offset = *(u32*)(curBlock + index); | |
− | + | // If the offset is negative, the current node is a leaf node. | |
+ | if ((offset & 0x80000000) != 0) { | ||
+ | break; | ||
+ | } | ||
− | + | // If the offset is non-negative, update the current node to be | |
− | + | // the child node and continue traversing the tree. | |
− | + | shift--; | |
− | + | curBlock += offset; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | = | + | index = 4 * ((4 * ((u32)z >> shift)) & 4 |
− | + | | (2 * ((u32)y >> shift)) & 2 | |
− | | | + | | (1 * ((u32)x >> shift)) & 1); |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | // Return the address of the leaf node containing the input point. | |
− | + | return reinterpret_cast<u16*>(curBlock + (offset & 0x7FFFFFFF)); | |
− | + | } | |
− | + | </pre> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == | + | == Tools == |
− | + | The following tools can handle KCL files: | |
− | + | * [[Collision Tools]], by Blank: object exporter and importer, designed for [[Super Mario Galaxy]], but usable for [[Mario Kart Wii]] | |
− | + | * [[CTools]], by [[Chadderz]]: editor | |
− | + | * [[SZS Modifier]], by [[Chadderz]]: editor | |
− | + | * [[un-beancorner]], by [[Atlas]]: allows lowering wall collision to prevent clipping over road with walls around them | |
− | + | * [[Wexos's Toolbox]], by [[Wexos]] | |
− | + | * [[Wiimms SZS Tools]], by [[Wiimm]]: [[3D Tool]]-compatible exporter and importer (may [[Creating a KCL with Wiimms Tools|create a KCL]] directly from an OBJ file). Wiimms SZS Tools are recommended for KCL creation; see [[Creating a KCL with Wiimms Tools]] for details. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | [[ | + | [[Category:File Format/MKW]] |
Latest revision as of 23:01, 13 December 2023
KCL Files are collision files used in Mario Kart Wii and many other games. They have been used since at least Mario Kart DS. The documentation here is specifically for the Mario Kart Wii implementation, although other implementations are likely to be similar.
The KCL files contain simplified versions of model files in order to allow rapid collision detection. They use an octree for efficient spatial indexing, as well as storing the actual triangles of the models in a more rapidly accessible format.
File Format
The basic file format consists of a header, and four data sections.
Header
The header is a 0x38 or 0x3c byte structure as follows.
Offset | Type | Name | Description |
---|---|---|---|
0x00 | u32 | pos_data_offset | 0-indexed offset to array of position vectors. |
0x04 | u32 | nrm_data_offset | 0-indexed offset to array of normal vectors. |
0x08 | u32 | prism_data_offset | 1-indexed offset to array of triangular prisms. |
0x0c | u32 | block_data_offset | Offset to collision octree blocks. |
0x10 | f32 | prism_thickness | Depth of a triangular prism along its normal vector. |
0x14 | Vec3 | area_min_pos | Smallest possible coordinate in the model |
0x20 | u32 | area_x_width_mask | X mask. X coordinates with bits outside this mask are outside the model (See section 4) |
0x24 | u32 | area_y_width_mask | Y mask. Y coordinates with bits outside this mask are outside the model (See section 4) |
0x28 | u32 | area_z_width_mask | Z mask. Z coordinates with bits outside this mask are outside the model (See section 4) |
0x2c | u32 | block_width_shift | Octree leaf block size shift (size = 2^block_width_shift = 1 << block_width_shift) |
0x30 | u32 | area_x_blocks_shift | Y shift. Used to form the index of the root block's children (See section 4 algorithm) |
0x34 | u32 | area_xy_blocks_shift | Z shift. Used to form the index of the root block's children (See section 4 algorithm) |
0x38 | f32 | OPTIONAL[ sphere_radius ] | Maximum radius of a sphere that can be collided with this file. This field must be used when computing the octree; e.g., to consider which triangles are inside an octree 32x32 block, it is insufficient to just consider a 32x32 cube since it would miss prisms a player could hit while being on the edge of the box. Therefore, it is necessary to consider a distance field with constant distance of sphere_radius. From analysis of official files, this is not just a larger cube, but actually a curvy, beveled figure (especially noticeable with small cubes where sphere_radius > width). Official tools will only include prisms that are actually reachable in leaf nodes which produces more efficient files than homebrew. This field is not provided by KCL files from Super Mario Galaxy/other platformers. Therefore, using those tools for KCL may be problematic as Mario Kart Wii expects this value. |
All offsets are relative to the start of the file.
The meaning of the shift and mask values is explained in section 4.
An official KCL generation algorithm can be observed in Super Mario Galaxy's DynamicCollisionObj::updateCollisionHeader()
. A decompilation is provided below:
void DynamicCollisionObj::updateCollisionHeader() { Vec min, max, extent; int masks[3]; int extent_int_x, extent_int_y, extent_int_z; int max_entropy = 0, component = 0, component_ = 0, bits_sel, mask_sel, i, v8, bit_shift, area_y_width_mask, area_z_width_mask; // Compute bounding box and extent MR::createBoundingBox(this->mVertices, this->mNumVertices, &min, &max); JGeometry::TVec3<f>::TVec3<f>(&extent, &max); JGeometry::TVec3<f>::__ami(&extent, &min); // Initialize masks with extent extent_int_x = (int)extent.x; extent_int_y = (int)extent.y; extent_int_z = (int)extent.z; masks[0] = extent_int_x; masks[1] = extent_int_y; masks[2] = extent_int_z; if ( !extent_int_x ) masks[0] = 1; if ( !masks[1] ) masks[1] = 1; if ( !masks[2] ) masks[2] = 1; // Find highest number of bits to shift for (component = 0; component < 3; ++component) { bits_sel = 0x80000000; mask_sel = 0xFFFFFFFF; i = 0; v8 = 32; while ( (masks[component] & bits_sel) == 0 ) { bits_sel >>= 1; mask_sel >>= 1; ++i; if ( !--v8 ) goto CONTINUE; } masks[component] = ~mask_sel; if ( max_entropy < i ) max_entropy = i; CONTINUE:; } // Update header fields bit_shift = 33 - max_entropy; area_y_width_mask = masks[1]; this->mpHeader->area_x_width_mask = masks[0]; area_z_width_mask = masks[2]; this->mpHeader->area_y_width_mask = area_y_width_mask; this->mpHeader->area_z_width_mask = area_z_width_mask; this->mpHeader->block_width_shift = bit_shift; JGeometry::TVec3<f>::__as(&this->mpHeader->area_min_pos, &min); }
Section 1 - Position Vectors
Section 1 is simply a large array of position vectors, stored as 3 successive floats for X, Y and Z. The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 2 from the start of Section 1; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the prisms list and keep track of the highest position index.
Section 2 - Normals
Section 2 is much the same as section 1, in that it is a large array of normal vectors. Again the values are stored as 3 successive floats for X, Y and Z. The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 3 from the start of Section 2; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the prisms list and keep track of the highest normal index across every field (face normals + edge normals).
Section 3 - Triangular Prisms
The third section is a pool of triangular prisms encoded as face normal vectors and a height. The offset to this section is stored as 0x10 less than the actual location of the data because this section is one indexed in section 4. The structure of each entry in this section is a 0x10 byte structure given below.
The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 4 from the start of Section 3; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the octree and keep track of the highest prism index.
Offset | Type | name | Description |
---|---|---|---|
0x00 | f32 | height | Triangle altitude from Vertex 1 to the opposite side. |
0x04 | u16 | pos_i | Vertex 1 position index (0 based index into section 1). |
0x06 | u16 | fnrm_i | Face normal vector index (0 based index into section 2). |
0x08 | u16 | enrm1_i | First edge normal vector (in counterclockwise order) -- Normal A index (0 based index into section 2). |
0x0a | u16 | enrm2_i | Second edge normal vector (in counterclockwise order) -- Normal B index (0 based index into section 2). |
0x0c | u16 | enrm3_i | Third edge normal vector (in counterclockwise order) -- Normal C index (0 based index into section 2). |
0x0e | u16 | attribute | Collision attribute. In Super Mario Galaxy, this is an attribute *index* into an Attribute Lookup Table. In Mario Kart Wii, the attribute is stored directly in prisms. |
All indices in this section are 0 indexed. The position index is an index for section 1, and the others are indices to section 2. The coordinate system is right handed.
The decoding algorithm can be seen in Mario Kart 7's KDGndCol::PolygonMesh::parseModel(const KDGndCol::KColData&, bool)
. It is described below:
CrossA = cross(enrm1, fnrm) CrossB = cross(enrm2, fnrm) Vertex1 = pos Vertex2 = pos + CrossB * (height / dot(CrossB, enrm3)) Vertex3 = pos + CrossA * (height / dot(CrossA, enrm3))
An encoding algorithm can be seen in Super Mario Galaxy's DynamicCollisionObj::updateTriangle()
. A method for converting three vertices into the KCL form is given below.
One approach is described below: (this assumes vertices are arranged counter-clockwise when viewed from their front side)
pos = Vertex1 fnrm = normalize(cross( Vertex2 - Vertex1, Vertex3 - Vertex1 )) enrm1 = normalize(cross(fnrm, Vertex3 - Vertex1)) enrm2 = normalize(-cross(fnrm, Vertex2 - Vertex1)) enrm3 = normalize(cross(fnrm, Vertex2 - Vertex3)) Length = dot(Vertex2 - Vertex1, enrm3)
Section 4 - Spatial Index
Offsets in this section are interpreted differently depending on if that offset represents a non-leaf or a leaf block. The first entry represents the root block which is not a leaf block and contains the entire model. Subsequent blocks are subdivisions of the root block until the leaf blocks are reached.
- In non-leaf blocks, the offset points to an array of 8 u32 offsets, which are the offsets of the block's children.
- In leaf blocks, the offset points to an array of u16 prism indices. Each of these is a 1-based index to section 3, which is a triangle that must be checked by an object at the original location. The first entry of a list is always 0, which serves as a 0 termination for the previous list.
As an example, MKW's algorithm for finding the leaf block that contains a point is as follows
u16* KCollisionOctree::searchBlock(const EGG::Vector3f& point) { // Calculate the x, y, and z offsets of the point from the minimum // corner of the tree's bounding box. const int x = point.x - this->area_min_pos.x; // Check if the point is outside the tree's bounding box in the x, y, // or z dimensions. If it is, return 0. if ((x & this->area_x_width_mask) != 0) { return 0; } const int y = point.y - this->area_min_pos.y; if ((y & this->area_y_width_mask) != 0) { return 0; } const int z = point.z - this->area_min_pos.z; if ((z & this->area_z_width_mask) != 0) { return 0; } // Initialize the current tree node to the root node of the tree. u32 shift = this->block_width_shift; u8* curBlock = this->block_data; s32 offset; // Traverse the tree to find the leaf node containing the input point. u32 index = 4 * (((u32)z >> shift) << this->area_xy_blocks_shift | ((u32)y >> shift) << this->area_x_blocks_shift | (u32)x >> shift); while (true) { // Get the offset of the current node's child node. offset = *(u32*)(curBlock + index); // If the offset is negative, the current node is a leaf node. if ((offset & 0x80000000) != 0) { break; } // If the offset is non-negative, update the current node to be // the child node and continue traversing the tree. shift--; curBlock += offset; index = 4 * ((4 * ((u32)z >> shift)) & 4 | (2 * ((u32)y >> shift)) & 2 | (1 * ((u32)x >> shift)) & 1); } // Return the address of the leaf node containing the input point. return reinterpret_cast<u16*>(curBlock + (offset & 0x7FFFFFFF)); }
Tools
The following tools can handle KCL files:
- Collision Tools, by Blank: object exporter and importer, designed for Super Mario Galaxy, but usable for Mario Kart Wii
- CTools, by Chadderz: editor
- SZS Modifier, by Chadderz: editor
- un-beancorner, by Atlas: allows lowering wall collision to prevent clipping over road with walls around them
- Wexos's Toolbox, by Wexos
- Wiimms SZS Tools, by Wiimm: 3D Tool-compatible exporter and importer (may create a KCL directly from an OBJ file). Wiimms SZS Tools are recommended for KCL creation; see Creating a KCL with Wiimms Tools for details.