View source for KCL (File Format)/Wii U

'''KCL''' files are collision files, which is the model the game runs collision against. KCL files has been used since at least [[Mario Kart DS]], but this documentation is about the format used in [[Wii U]] and [[Nintendo Switch]]. For other formats, see [[KCL (File Format)]].

KCL stores prisms, a triangle with a depth, in a format which allows fast access and collision calculation, and has an octree which splits the world space into many sub spaces, to make the game test collision on less prisms, which allows for much faster collision detection.

= File Format =
== Header ==
The file begins with the following header:

{| class="wikitable"
! Offset !! Type !! Description
|-
| 0x00 || Byte[4] || '''Version number'''. Always 2.2.0.0.
|-
| 0x04 || UInt32 || '''[[#Division Info|Division info]] offset'''.
|-
| 0x08 || UInt32 || '''[[#Model|Model]] offset table offset'''.
|-
| 0x0C || UInt32 || '''Number of [[#Model|models]]'''.
|-
| 0x10 || Float[3] || '''Minimal coordinate''' for all [[#Model|models]].
|-
| 0x1C || Float[3] || '''Maximal coordinate''' for all [[#Model|models]].
|-
| 0x28 || Int32[3] || '''Area width shift'''. Defines the size of the space where collision data is stored.
|-
| 0x34 || UInt32 || '''Total number of [[#Prism|prisms]]'''.
|}

=== Division Info ===
The collision files of [[Mario Kart 8]] actually hold multiple [[#Model|models]] in the format of those found in [[Mario Kart Wii]]. This was required because one of such models can only hold a maximum of 16384 prisms, because each prism requires four normal vectors, and it can only link to 65536 normals.

Instead of increasing the size used to store a prism index, multiple such models are stored, of which each represents the prisms available in one, or multiple, cubes of the whole course space. To divide the course space into such cubes referencing the models, a new global division follows the header. It works similar to the [[#Octree|octree]] of one of such models, but instead of looking up prisms, models are looked up with it.

The division info consists of at least 8 integers, representing the division keys of the 8 cubes the course space is initially divided into. Depending on the flags set in the upper two bits of the key, either the remainder points to an index of a model in the model array which data will be used for this cube, divides the cube further into 8 subcubes, or denotes no data being available in this cube.

{| class="wikitable"
! Set Flags (0-based) !! Remaining Data !! Description
|-
| 31 || Model Index || [[#Model|Model]] index which is part of this space.
|-
| 31 & 30 || Unused (being 0) || No model is used for this cube, as no data is present in this part of space.
|-
| else || Child Nodes Offset || Divides this cube into 8 more subcubes. The value is an offset, which is multiplied by 4 to get the actual offset, relative to the start of the current node.
|}

== Model ==
Each model in the file has a format almost identical to KCL files in [[Mario Kart Wii]]. The model consists of a header, and four data sections. The header is a 0x3C byte structure as follows:

{| class="wikitable"
! Offset !! Type !! Description
|-
| 0x00 || UInt32 || '''[[#Vertex Position|Vertex position]] offset''', relative to the start of this structure.
|-
| 0x04 || UInt32 || '''[[#Normals|Normal]] offset''', relative to the start of this structure.
|-
| 0x08 || UInt32 || '''[[#Prisms|Prism]] offset''', relative to the start of this structure.
|-
| 0x0C || UInt32 || '''[[#Octree|Octree]] offset''', relative to the start of this structure.
|-
| 0x10 || Float || '''Prism thickness'''. Defines the depth of the prisms created by the triangles.
|-
| 0x14 || Float[3] || '''Minimum coordinates of this model''', which also is the [[#Octree|octree]] origin'''.
|-
| 0x20 || UInt32 || '''X width mask'''.
|-
| 0x24 || UInt32 || '''Y width mask'''.
|-
| 0x28 || UInt32 || '''Z width mask'''.
|-
| 0x2C || UInt32 || '''Block width shift'''.
|-
| 0x30 || UInt32 || '''Blocks X shift'''.
|-
| 0x34 || UInt32 || '''Blocks XY shift'''.
|-
| 0x38 || Float|| {{Unknown-left|'''Sphere radius'''. Unknown usage.}}
|}

=== Vertex Position ===
This section is an array of vertex positions, each represents as three floats, X, Y and Z. The number of elements is not stored.

=== Normals ===
This section is an array of normals, each represents as three floats, X, Y and Z. The number of elements is not stored.

=== Prisms ===
The third section is the section containing the actual model information. The structure of each entry in this section is a 0x14 byte structure given below.

{| class="wikitable"
! Offset !! Type !! Description
|-
| 0x00 || Float || '''Triangle height'''.
|-
| 0x04 || UInt16 || The index of the '''base vertex position''' into the [[#Vertex Positions|vertex array]].
|-
| 0x06 || UInt16 || The index of the '''triangle normal''' into the [[#Normals|normal array]].
|-
| 0x08 || UInt16 || The index of the '''prism side A normal''' into the [[#Normals|normal array]].
|-
| 0x0A || UInt16 || The index of the '''prism side B normal''' into the [[#Normals|normal array]].
|-
| 0x0C || UInt16 || The index of the '''prism side C normal''' into the [[#Normals|normal array]].
|-
| 0x0E || UInt16 || '''Collision attribute'''.
|-
| 0x10 || UInt32 || '''Global prism index'''.
|}

[[File:Kcl-prism-description.png|400px|thumb|left|A collision prism.]]
<br clear="all">

Below contains the calculation needed to convert three vertices into the needed values. This method assumes the vertices are arranged anti-clockwise when viewed from the collidable side.

<pre>
Position = Vertex1
Direction = Normalize(Cross(Vertex2 - Vertex1, Vertex3 - Vertex1 ))
DirectionA = Normalize(Cross(Normal, Vertex3 - Vertex1 ))
DirectionB = Normalize(-Cross(Normal, Vertex2 - Vertex1 ))
DirectionC = Normalize(Cross(Normal, Vertex2 - Vertex3 ))
Length = Dot(Vertex2 - Vertex1, DirectionC )
</pre>

=== Octree ===
The octree subdivides the world space into cubes, to allow much faster prism collision detection. The number of root [[#Node|nodes]] can be calculated by the following algorithm:
<pre>
NrRootNodes = (MaskWidthX >> BlockWidthShift + 1) * (~MaskWidthY >> BlockWidthShift + 1) * (~MaskWidthZ >> BlockWidthShift + 1)
</pre>

Then the number of root nodes are written to the file. These nodes link to more nodes or prism lists.

==== Node ====
Each node has the following structure:

{| class="wikitable"
! Offset !! Type !! Description
|-
| 0x00 || UInt32 || '''Flag''': '''ABBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB'''
'''A''': 1 means it's a leaf. See below.<br>
'''B''': Offset to next structure, relative to the parent node, or start of octree data if the node is a root node.
|}

If the node is a leaf, then it means it isn't subdivided anymore and it contains a prism list. This prism  list is terminated by 0xFFFF, and contains indices of the [[#Prisms|prisms]] that are present in this subspace. If it's not a leaf, then this node is subdivided into 8 more nodes, which the offset into the structure links to.

= Tools =
The following tools can handle KCL files:
* [[Wexos's Toolbox]], by [[Wexos]]

[[Category:Switch File Formats]]
[[Category:Wii U File Formats]]