Guided traversal in compression of triangular meshes

A computer program product comprising a non-transitory storage medium, the computer program product including code that, when executed by processing circuitry of a user device configured to encode data associated with a three-dimensional object, a plurality of vertices of a triangular mesh representing the three-dimensional object, causes the processing circuitry to perform a method, the method comprising:

• receiving the plurality of vertices of a triangular mesh representing the three-dimensional object, the triangular mesh including a plurality of faces, each of the plurality of faces including three vertices of the plurality of vertices;
• generating an initial traversal order specifying a sequence by which the plurality of faces are traversed according to an implicit, deterministic scheme, each step being one of a step to the left or a step to the right;
• for a step of the sequence specified by the initial traversal order:
• generating difference data representing (i) a first difference between a point predicted by the vertices of the face and a first vertex of the face, corresponding to a first step and (ii) a second difference between a point predicted by the vertices of the face and a second vertex of the face, corresponding to a second step, the first difference being smaller than the second difference;
• generating an indication in a traversal order of whether the first step deviates from the step of the sequence specified by the initial traversal order;
• and
• encoding traversal order to produce an encoded bitstream;
• and
• encoding first difference to produce encoded difference data, the encoded difference data producing the plurality of vertices of the triangular mesh in response to decoding.

An electronic apparatus configured to encode data associated with a three-dimensional object, a plurality of vertices of a triangular mesh representing the three-dimensional object, the electronic apparatus comprising:

• memory;
• and
• controlling circuitry coupled to the memory, the controlling circuitry being configured to:
• receive a plurality of vertices of a triangular mesh representing the three-dimensional object, the triangular mesh including a plurality of faces, each of the plurality of faces including three vertices of the plurality of vertices;
• generate an initial traversal order specifying a sequence by which the plurality of faces are traversed according to an implicit, deterministic scheme, each step being one of a step to the left or a step to the right;
• for a step of the sequence specified by the initial traversal order:
• generate difference data representing (i) a first difference between a point predicted by the vertices of the face and a first vertex of the face, corresponding to a first step and (ii) a second difference between a point predicted by the vertices of the face and a second vertex of the face, corresponding to a second step, the first difference being smaller than the second difference;
• generate an indication in a traversal order of whether the first step deviates from the step of the sequence specified by the initial traversal order;
• encoding traversal order to produce an encoded bitstream;
• and
• encoding first difference to produce encoded difference data, the encoded difference data producing the plurality of vertices of the triangular mesh in response to decoding.