Generation of triangle mesh for a three dimensional image

A method of generating a triangle mesh for a three dimensional image, the method comprising:

• providing a depth map;
• generating a k-D tree for the depth map, the k-D tree representing a hierarchical arrangement of the regions, wherein the hierarchical arrangement of regions satisfies a requirement that a depth variation measure for regions is below a threshold;
• positioning an internal vertex within each region of the k-D tree;
• and
• generating the triangle mesh by forming sides of triangles of the triangle mesh as lines between internal vertices of neighboring regions.

An apparatus for generating a triangle mesh, the apparatus comprising:

• a receiver circuit arranged to receive a video signal, the video signal comprising image data,
• wherein the image data comprises a representation of a three dimensional image and a k-D tree for a depth map of the three dimensional image,
• wherein the depth map comprises regions,
• wherein the k-D tree represents a hierarchical arrangement of the regions, wherein the hierarchical arrangement of the regions satisfies a requirement that a depth variation measure for regions is below a threshold;
• and
• a triangle mesh generator circuit arranged to position an internal vertex within each of the regions of the k-D tree, wherein the triangle mesh generator circuit is arranged to generate the tringle mesh by forming sides of triangles of the triangle mesh as lines between internal vertices of neighboring regions.