Subversion Repositories display

The NOD file holds information about roads and how they connect together.
First read John Mechalas' document at http://sourceforge.net/projects/garmin-img
(henceforth referred to as [JM])

- NOD 1 section updated Jan 2014.

Section NOD 2
=============

Offset | Size   | Description
-------+--------+--------------------------
00     | 1      | Road classification
01     | 3      | Pointer into NOD 1
04     | 1      | Number of bits from offset 0x06
05     | 1      | unknown
06     | varies | Little endian bit mask, with the number
       |        | of bits taken from 0x04

Some definitions of the road classification can be found in [JM].

The bit mask at 06 is read from the least significant bit of a byte
and the bytes are read in little endian order. Each bit corresponds
to a node in the road. If the bit is set to 1 then it is a routing
node, else it is a non-routing node (for example it could just be
used to mark an end of a house number range).

The first and last point of a road are implicitly nodes. Otherwise
a point of the road is a node if it has the so-called 'node-flag'
set (part of the RGN format).

Section NOD 1
=============

Consists of two kinds of area.  One contains records of variable length,
describing nodes in the road network. The other is a set of tables
related to the previous area of nodes. NOD 1 is made up of alternating
node and table areas.

The first byte of each node record provides a pointer to the associated
table area. The offset in NOD 1 of each table area is a multiple of
0x40, thus a node area is limited to a size of about 0x4000 bytes. In
practice, this first byte doesn't appear to exceed 0x60.
The 0x40 is not hardcoded, but is instead specified by the "node align"
field in the NOD header.

The table area starts with a header which specifies the number of
records in the tables, allowing to determine the offset of the next
node area, which follows the table area directly.

Using these facts it is possible to quickly start with the first byte,
find the tables, skip over them and find the next table and build up
a list. Any valid node must start with a byte that leads to its table.

Node area
---------
The first area consists of variable sized records.  There are pointers
from NOD 2 and NOD 3 to these records.  There is often more than one
pointer to the same record.  There are also nodes that are only
referenced by other nodes.

Each node record starts with a header.

Offset | Size   | Description
-------+--------+--------------------------
00     | 1      | Pointer to tables area
01     | 1      | Flags
02     | 3 or 4 | Coordinate offsets (see flags for size)

The following flags are known.

Flag   | Description
-------+----------------------------
0x40   | has arcs
0x20   | 2 byte coordinate offsets, instead of 12 bits
0x10   | Restrictions
0x08   | Boundary node
0x07   | Max destination class of arcs (?)

If the flag 0x10 is set, there are routing restrictions at this node. The
flag signifies the presence of restrictions data at the end of the record.

The flag 0x08 is set if the node is a boundary node, that is if it lies
on the boundary of the IMG tile. In that case, there will be a pointer
from NOD 3 to this record.

The flag 0x40 means that there are arcs for this node. An arc is
a link to another node that you can be routed to. They will start
just after the coordinate offsets. See the next section.

The coordinate offsets are relative to the base coordinates in the
header of the following tables area. If the flag 0x20 is set, each
coordinate offset is a two byte value, else both offsets are stored
in three bytes (12 bits each).

The final 3 bits contain the largest destination road-class of any
of the arcs from this node.

Arcs
-----
Following the coordinate offsets comes a sequence of variable length
records which describe links to other nodes which we call arcs. The
last of these records is marked by bit 0x80 in the second byte (Flags B below).

Size | Condition              | Description
-----+------------------------+----------------------------------
1    | Always                 | Arc flags
1,2  | Always                 | Target node
1    | first or (A & 0x80)    | Pointer into Table A
1,2,3| Always                 | Road length
1    | its complicated        | Initial bearing
1    | A & 0x20               | Curve data 

All links have flags, a pointer to another node and a length.
The other data present may include an initial bearing of the arc,
a link into Table A for the associated road and 'curve' data.
The data present depends on the flags. In some cases (road
data and direction) it may be taken from previous arcs.

Flag A
------
The first byte is always flags: note that the first arc in a node
is special and the flags vary in meaning for it. The first arc
always has a TableA link and a direction byte.

Mask   | Name      | Description
-------+-----------|--------------------
0x80   | NEW_NET   | If first arc: Use compact directions
       |           | If not first: An index to table A is present (road segments)
0x40   | SIGN      | Sign - true if arc goes forward along the line
0x20   | CURVE     | Curve data present
0x18   | LEN       | Top bits of length
0x07   | DESTCLASS | Destination road class (0-4)

The destination road class is related to the max class of road that you
can get to by following this arc. It is not fully understood.

The next item is a pointer to the node, there are two flags at
the top that determine the length and how this is interpreted.

Target node
-----------
The top two bits of next byte determine how to get the link.

Mask   | Description
-------+--------------------
0x80   | Last link
0x40   | Inter-area link

Links may point to nodes in the same or another node area in NOD 1. We
call the latter inter-area links, the former intra-area links. A link
may point to a directly adjacent node in the road network (a "direct
link"), or to a node that may be reached by following a sequence of
direct links (an "indirect link"). For direct links, there is always
an opposite direct link from the destination node. This is not always
the case for indirect links. Indirect links appear to always point to
nodes on the same polyline.

If bit 0x40 is 0, then the node is contained in the same node area.
The low 6 bits are combined with the following byte 3, with byte 3
being the low bits of the combined value.
This value is added to the offset of the current node to arrive
at the location of the target node.

An inter-area link is signified by the presence of bit 0x40 in the
second byte. In that case, the low six bits of byte two are an index
into Table B in the following tables area, which holds a node
offset that can be anywhere in NOD 1.
If the six low bits are all 1s (ie 0x3f) then the next byte is read
and used instead. So it is possible to have more than 64 links, though
that is not particularly common.

The links from a node appear to be grouped according to the direction
in which they leave the node. The first link within such a group is a
direct link, while following links will be indirect (leading to nodes
further along the road than the one pointed at by the previous direct
link).

The first arc has some special features. Keep these in mind when
reading the explanations below.

1. There is always a NET offset
2. The flag A 0x80 signifies compact direction encoding.
3. There is always a direction byte.

The compact direction encoding means that there are two directions
of 4-bits each in a single byte.  See later.

Links: road
-----------
If bit NEW_NET in arc flags is set, or this is the first arc, then the next
thing will be a 1 byte pointer into Table A which contains some
information about the road associated with this arc.

When the bit is not set, then there is no Table A offset and the
arc refers to the road of the previous arc.

If the sign bit is set, then the arc goes in to forward direction
along the road. If not set then it goes in the backward direction.

Links: length
-------------
Next there is a byte that contains the length of the road between
the two nodes. The two bits 0x18 in the arc-flags form the top
two bits of the length giving a 10 bit quantity in all.
There are ways of getting a longer length [TO BE COMPLETED]

The length is in units of about 2.38m (ie it seems to be the length of
a Garmin unit at the equator). This distance is scaled by the
value in bits 5-7 of the 'flags' value at 0x1d in the header.
The length is multiplied by 1 shifted right by this value.

Links: direction
----------------
Next there may be a byte giving direction information. The first arc
always has such a byte.  There are two formats normal and compact. The
one in use is determined by the NEW_NET bit of the arc flags on the first
arc (since the first arc always has a Table A index, this bit is not
needed for its normal purpose).

If 1 the node uses the compact representation and if 0 then the normal 8
bit representation.  Each node can have a different representation, it is
not clear why though? If two bearings would be the same in the 4 bit
representation may be a reason to use the more accurate representation.

This is the bearing of the road as it leaves the node, not the straight
line direction between the nodes. Therefore there is only a direction for
the first arc in each group and sign, as the direction will be same for
other items in the group.  Typically a group will have one or more
arcs with NEW_NET=0 and SIGN=0 which will share the same direction as
the group leader, and then one or more with NEW_NET=0 and SIGN=1 which
will have a new direction.

Normal 8 bit direction:
This is simple, whenever you need a new direction, then read a byte and
use that.  0 is 0 degrees and 256 is 360 degrees, so multiply by 360/256
to get the direction.

Compact 4 bit direction:
When you first need a new direction read a byte, save it, and use the
bottom 4 bits as the direction.  You can shift up by 4 and then treat
the same way as an 8 bit direction.

When you next need a direction, do not read anything and return the
top 4 bits of the previous value.

Repeat as necessary.  Every other time you will read a byte.

Links: curve:
-------------
1 Byte Curve:
If the CURVE bit is set, then read 1 byte which contains the
direct bearing to the target node in the bottom 5 bits.

If the top three bits are not all zero:
Bits |
-----+-------------------------------
7-5  | Ratio of direct and path distance (3 bits)
4-0  | The direct bearing to the target node

The distance ratio is the ratio of the direct staight line
distance between the node and the target node, to the distance
obtained by following the road.

In this case there is a limited range available and it
is calculated approximately like this:
  (16 * direct-distance / road-distance) - 8

If this results in a number outside the range 1-7 then you
need to use the extended form, see the next sub-section.

The bearing is the direct straight line direction to the target
node.  It is 5 bits so can be convered to degrees by multiplying
by 360/0x1f.

2 Byte Curve:
If the top 3 bits are zero then another byte is read and this
is used as the direct bearing instead of the bottom 5 bits of
the first byte.
The bottom 5 bits of the first byte are then the distance ratio.

If top bits all zero:
Bits | Byte 1
-----+-------------------------------
7-5  | 0
4-0  | Ratio of direct to road distance

Bits | Byte 2
-----+-------------------------------
7-0  | The direct bearing to the target (8 bits)

In this case the distance ratio has its full range and is
calculated simply as:
  32 * direct-distance / road-distance

There seems to be a cap of 0x12 or so on the allowed value here.

The direct bearing is a full 8 bits in this case, so multiply
by 360/256 to get degrees.


Links: Restrictions:
-------------------

If node flag 0x10 was set, the links are followed by a variable length
sequence of offsets into Table C. The corresponding record in Table C
describes a restriction at the node.

Depending on the size of the largest Table C in NOD 1, these may be
bytes or little-endian shorts (or larger?). It is unknown whether
their size may be determined without reading the header of each tables
area.  The last offset has its highest bit set.

Tables area
-----------
The second kind of subsection in NOD 1 occurs once after each node
area. It always starts on a 0x40 boundary in the section and zero
padding bytes are used achieve this alignment.

The table area starts with a 9 byte header, and is followed by up to
three tables we call Table A, B and C.

There is a header area of 9 bytes.

Offset | Size   | Description
-------+--------+------------------------------
00     | 1      | flags, number of bytes for table C size
01     | 3      | base longitude
04     | 3      | base latitude
07     | 1      | number of records in Table A
08     | 1      | number of records in Table B

Table A contains fixed length records with the size given by the value
at 0x23 in the header. They represent
road segments (parts of roads between adjacent nodes) that meet nodes
in the preceding nodes area. These contain pointers into NET and
routing data (speed, oneway, road class, toll, what vehicle types are
allowed).

Table B contains offsets into NOD 1. These are the destinations of
inter-area links from the preceding nodes area.

Table B is followed by one or more bytes giving the size of Table C.
The number of bytes to be read are given by the bottom two bits of the
first flags field in the tables header. These two bytes form a little
endian integer that is the size of Table C.
If the bottom two bits are zero then the size of table C is zero,
although some files contain a single zero byte instead.

Table C contains data that is related to restrictions. In the common
case, it contains records of size 11 that are of the following form.

Offset | Size   | Description
-------+--------+---------------------------
00     | 3      | Header (05 40 00)
03     | 2      | Source node
05     | 2      | Restriction node
07     | 2      | Destination node
09     | 1      | Source segment
10     | 1      | Destination segment

Such a record describes a restriction at "Restriction node" coming
from "Source node" via "Source segment" headed for "Destination node"
along "Destination segment".

The segments are given by indices into the preceding Table B.

The nodes are given by little-endian unsigned shorts which are negative
offsets from the start of the tables area.

It is unclear what inter-section restrictions or restrictions at
boundary nodes look like, if they are possible.

Section NOD 3
=============

These are boundary nodes that are on the edge of the map, and connect to
other maps in the set.  They are described in [JM].