Thursday, July 12, 2012

And Now For Something Completely Different

Hey Readers,

I have something totally different for you this week. To give you some background, my other hobby is costuming, and on top of that it's mostly armor based costuming. I build things like, transformers, Iron man, that sort of thing. The piece of software I use to do this is called Pepakura. It allows a user to "unfold" a 3d model into 2 dimensions so that it can be printed out on cardstock and re-assembled. The problem is that it's been designed with building little papercraft model's not costuming. This results in a lot of little things I don't like about the software. Now rather than just accept those things I started planning out a better piece of software more designed for costuming in mind.

The problem with this though is that even if I built out this piece of software noone is going to use it because all of the existing content is built for pepakura. So I decided the number one thing I needed was in importer that could load pdo( the pepakura file format ) files into my software. The problem with doing this though is that pdo files are a closed format and besides one hacked together python script I found that could import parts of the 3d data there wasn't really any information about the format out there in the wild.

So I set about reverse engineering the format and started building up a spec of how it was layed out in memory. I've never done anything like this before and so it was a slippery slope trying to figure out where to begin. I've done lots of work with binary files though so I have a pretty solid grounding in how a lot of different formats are layed out so it gave me a bit of a base to start from. So I started with a simple box model and just started poking and prodding in a hex editor. Change a vertex, re-export see what changed. Change a color, re-export see what changed. Slowly but surely a picture started to emerge. Within a few days I had a clear picture of what the 3d data looked like in memory. One thing that really held me up was that I expected all of the floating point data to be stored as floats, but they decided to store them as doubles, I can't imagine why they would think they would really need that level of precision, were they thinking someone would be trying to unfold an earth sized object? Another thing that held me up a bit was that the strings are encoded. I saw patterns that looked like null terminated strings, a string length, a set of characters ending with a 0. When I looked at the data though the strings were jibberish. With a bit of fiddling around though I figured out that if I subtracted a constant from each element of the string I could decode it into the original string value. Turned out though that this constant changes from file to file. The good thing though was after a quick search of the header I found out one of the blocks of data I was unsure about stored the decoder value.

So that was about as far as I got a few months ago I got distracted by other things and there it lied dormant. A couple weeks ago though I got the itch again. So for the last couple weeks I've been poking and prodding at the data structures and finally have an almost complete picture of how everything is stored. I've also set up a pdo viewer option in my project for viewing pdo files. Now the next big question for me is do I go back to my voxel earth project or do I put some love into my costume designer project I planned out so many months ago.

Anyways, I've compiled how things are layed out in memory below. Everything that's important for rendering a pdo is there, there's a few odd and end flags that haven't been decoded yet. If anyone has any questions or feedback on what some of those unknown fields do please leave a comment.

Apologies if some of the formatting is messed up, seems to be a problem with blogger. Also comments for each piece of data are directly underneath the piece of data.
PDOData
    This is the main data structure. The pdo file is made up of a header,
    followed by all the object data, then a list of materials that are applied to
    those objects, the unfold patterns, then text and images that are placed in
    the document, and finally the settings.
    PDOHeader                header
    ObjectCollection         objectCollection
    MaterialCollection       materialCollection
    PatternCollection        patternCollection
    TextCollection           textCollection
    ImageCollection          imageCollection
    Settings                 settings

PDOHeader
    u8 version[9]
    version info, "version 3" for pdo 3 files.
     u8 moreData[13]
    unsure
    StringData applicationId
    I think this is an application id, in most files it seems to be "Pepakura
    Designer 3".
    u32 decoder
    This is stored as a u32 but is a char that when subtracted from each element
    in a string decodes the string.
    u32 unknown
    unsure
    u8 moreData[62]
    unsure

StringData
    u32 strLength
    number of characters contained in the string
    u8 nullTerminatedString[]
    array of characters
ObjectCollection
    double x
    x position of the collection of objects
    double y
    y position of the collection of objects
    double width
    width of the collection
    double height
    height of the collection
    u32 numObjects
    number of objects to read
    ObjectData dataArray[]
    array of the data objects
MaterialCollection
    u32 numMaterials
    number of materials
    MaterialData materialArray[]
    array of the material objects

PatternCollection
    u8 unknown
    unknown
    double unknown
    unknown, maybe a scale value
    u8 unknown
    unknown
    double x
    x position of the collection of patterns
    double y
    y position of the collection of patterns
    double width
    width of the collection of patterns
    double height
    height of the collection of patterns
    u32 numPatterns
    number of patterns stored in the array
    PatternData patternArray[]
    collection of pattern data
TextCollection
    u32 numTextData
    number of text objects
    TextData textArray[]
    collection of text objects


ImageCollection
    u32 numImages
    number of image objects
    ImageData imageArray[]
    collection of image objects
ImageData
    double x
    x position of the collection of bitmap
    double y
    y position of the collection of bitmap
    double width
    width of the collection of bitmap
    double height
    height of the collection of bitmap
    BitmapData bmpData
    stores the actual texture data
Settings
    These are all of the common settings for the application. Oddly it seems to
    be a mish-mash of what options save and which ones don't. Any that I haven't
    decoded yet are marked as unknown.
    u32 unknown
    Unknown
    u8 showFlaps
    Whether or not all flaps are visible
    u8 showEdgeId
    Turn on/off viewing of the edge id's
    u8 unknown
    Unknown flag.
    u8 isTextureOn
    Turn textures on/off
    u8 useAngleThreshold
    Use the angle threshold to hide edges that angles are below a given
    threshold.
    u8 angleThreshold
    The angle threshold for hiding edges, goes from 0 to 180
    u8 unknown
    Unknown flag
    u8 unknown
    Unknown flag
    u8 unknown
    Unknown flag
    u8 doDrawWhiteLine
    If it's set then option says draw a white line under the folds.
    u32 mountainMode
    0 if it's solid, 1 if it's off, and I think 2 if it's a pattern.
    u32 valleyMode
    0 if it's solid, 1 if it's off, and I think 2 if it's a pattern.
    u32 cutLineMode
    0 if it's solid, 1 if it's off
    u32 unknown
    unknown flag
    u32 pageType
    The paper type, it's an enum, I haven't mapped it out yet, but matches up to
    how it's listed in the combo box in the print options.
    u32 isLandscape
    Should it print out landscape.
    u32 sideMargin
    Sets how big the side margins are.
    u32 topMargin
    Sets how big the top/bottom margins are.
    double mountainPattern[6]
    If the mountain mode has been set to 2 each number dictates how far to
    draw/skip the pattern in the lines.
    double valleyPattern[6]
    If the valley mode has been set to 2 each number dictates how far to
    draw/skip the pattern in the lines.
    u8 addOutlinePadding
    Add padding to how the texture is layed out across the folds.
    double globalScale
    The global scale for the file.
    StringData comment
    The comment string set in the options.
    StringData author
    The author string set in the options.
    u32 unknown
    Unknown flag.
    

ObjectData
    This is a collection of data that describes the 3d object.
    StringData name
    Name of the object
    VertexCollection vertices
    Collection of vertices that make up the object
    FaceCollection faces
    Collection of faces that make up the object
    EdgeCollection edges
    Collection of edges that make up the object
   
VertexCollection
    u8 unknown
    Unknown
    u32 numVertices
    Number of vertices in data array
    VertexData vertexArray[]
    Array of the vertex data.

FaceCollection
    u32 numFaces
    Number of faces in data array.
    FaceData faceArray[]
    Array of the face data
EdgeCollection
    u32 numEdges
    The number of edges in data array
    EdgeData edgeArray[]
    Array of the edge data.
VertexData
    The vertex data stores the 3d position for the original 3d model. Surprised
    they didn't stick more in here like normals or uvs. I guess it keeps things
    simple for the data format.
    double x
    x position in 3d space
    double y
    y position in 3d space
    double z
    z position in 3d space
   

FaceData
    Face data, these are the faces that make up the poly's of the 3d model and
    provide information for drawing the 2d unfolds. They allow for an arbitrary
    number of indices so the poly can have any number of points. I've only seen
    in practice 3 and 4 though, tris and quads.
    u32 materialId
    The index into the material collection which represents what material this
    face has on it.
    u32 unknown
    Unknown
    double normal.x
    The x component of the normal vector for this face
    double normal.y
    The y component of the normal vector for this face
    double normal.z
    The z component of the normal vector for this face
    double unknown
    Unknown
    u32 numIndices
    The number of indices this face has which tells how many points in poly.
    FaceIndexData indexArray[]
    The array of index information.
EdgeData
    Edge data, not really sure what this is useful for. All the data is better
    represented in the 2d unfold edge data. I guess one useful piece of info is
    the fact that there is one individual edgeData for each edge in the 3d model.
    Since an edge is always shared by 2 faces the 2 faces are indexed in the data
    structure. I guess this chunk of data is actually kind of useful for quickly
    calculating what the angle of an edge is for calculating the angle between
    two faces.
    u32 faceIndex0
    The face index for this edge.
    u32 vertIndex0
    The vertex index inside the face for this edge.
    u32 faceIndex1
    The second face index for this edge.
    u32 vertIndex1
    The vertex index inside the second face for this edge.
    u16 isEdgeShared
    This is either 1 or 0 it's the same value as in the unfolded edge data
    structure.
    u16 unknown
    Unknown.
    u16 unknown
    Unknown.
FaceIndexData
    Faces are usually made up of 3 or 4 of these FaceIndexData objects. They
    store data for the 2d description of the unfolded face as well as store the
    vertex index to the 3d data for rendering the 3d model.
    u32 vertexIndex
    The index into the 3d vertex data.
    double x
    The x position of the face index in the 2d view.
    double y
    The y position of the face index in the 2d view.
    double u
    The u texture coordinate for mapping the diffuse texture to the object.
    double v
    The v texture coordinate for mapping the diffuse texture to the object.
    u8 unknown
    Unknown.
    double edgeSize
    I believe this is the distance of the edge made up of this face index to the
    following face index.
    double leftEdgeAngle
    The left angle of the fold for the edge made up of this face index to the
    next face index.
    double rightEdgeAngle
    The right angle of the fold for the edge made up of this face index to the
    next face index.
    u32 outerColor[3]
    The outer color of this edge if an edge color has been set.
    u32 innerColor[3]
    The inner color of this edge if an edge color has been set.
MaterialData
    Materials can be applied on a per object basis. They store information for
    describing the color, texture, and I believe but haven't fully tested,
    ambient and specular color values.
    
    StringData name
    The name of the material
    float colorData[20]
    A collection of color values stored as floats. Interesting side note this is
    the only floating point value in the file that is actually stored as a float
    as opposed to double which seems to be the pdo standard for floating point
    numbers. I didn't spend much time investigating these values but I believe
    they're the diffuse/ambient/specular color values probably stored as 4
    floats, rgba.
    u8 hasBitmap
    If this value is set to 1 then the material also has a diffuse texture stored
    as a bitmap
    BitmapData bmpData
    optional piece of data, if the previous value is 1 then this will be a bitmap
    representing the diffuse texture for the material

BitmapData
    Images in a pdo document have their data embedded in the file. These bitmaps
    are used in materials and also in images which can be placed around the
    document. The actual raw data is rgba and stored as a compressed chunk of    
    data, the compression method is zlib.

    u32 width
    The width of the bitmap in pixels.
    u32 height
    The height of the bitmap in pixels.
    u32 compressedDataLength
    The length of the stored compressed image data.
    u8 compressedDataArray[]
    The image data is compressed using zlib.
PatternData
    Every unfolded object in the 2d window is contained in the file as a pattern.
    It's stored as a collection of edges that make up the structure of the
    pattern.
   
    u32 objectData
    This is the index of the object that the pattern belongs to. This can be
    referenced from the object collection
    double x
    x position of the pattern
    double y
    y position of the pattern
        double width
    width of the pattern
        double height
        height of the pattern
        StringData name
        Name of the pattern assigned in the editor
        u32 numEdges
        Number of unfolded edges in the unfold pattern   
    UnfoldEdge edgeArray
    The array of edges

UnfoldEdge
    These objects represent an unfolded edge on the 2d area.
   
    u8 unknown
        unknown
        u8 unknown
        unknown
        u32 faceId0
        The edge data is strangely stored as an index into the 3d faces and then the
    index into vertex in that face, the following point of the edge is the next
    vertex in that face.
    u32 vertexId0
        The vertex index into the face that represents the starting point of the edge
        u8 isSharedEdge
        This is a boolean representing whether or not this edge is shared. AKA, the
    edge is not an      outer edge on the pattern but an inner edge.
        u32 faceId1
        Optional, if isSharedEdge is 1, then the face that the shared edge belongs to
        u32 vertexId1
        Optional, if isSharedEdge is 1, then the vertex index into the shared edges
    face that  represents the starting point of the edge
TextData
    These are the text objects that can be placed within the 2d area of the pdo
    document.
   
    double x
    x position of the text
    double y
    y position of the text
    double width
    width of the text
    double height
    height of the text
    double unknown   
    unknown
    u8 color[4]
    color of the text, stored as 4 u8's rgba
    u32 fontSize
    the size of the font, aka point size
    StringData fontName
    name of the font
    u32 numStrings
    number of strings
    StringData stringArray[]
    This is a collection of strings which are stored in this text object

Model almost decoded.

There we go model decoded

Hmm those unfolds don`t quite look right

Hmm the bounding boxes are looking right

Hey there we go, unfolds rendering correctly

Found the normals for them model!

FIgured out which edges were the internal edges.