Triangle mesh compression

Abstract

A computer implemented method of processing elevation mesh data defining a polygon mesh surface to determine an alternative representation of the surface using fewer polygons than in the original representation is disclosed. Initially original elevation mesh data is sub-sampled to generate a low resolution representation of the polygon mesh surface where vertices of polygons correspond to points on a coarser X-Y grid than the original elevation mesh data. Error values indicative of the extent that portions of the surface defined by the low resolution elevation mesh data differ from corresponding portions of the surface defined by the original elevation mesh data are then determined. An alternative representation of the polygon mesh surface is then generated which includes: low resolution elevation mesh data for the portions of the polygon mesh surface associated with error values less than a threshold value; transition mesh data defining a polygon mesh surface immediately adjacent the perimeter of portions of the surface represented by the low resolution elevation mesh data; and higher resolution elevation mesh data for the remaining portions of the polygon mesh surface.

1 . A computer implemented method of processing elevation mesh data defining a polygon mesh surface to determine an alternative representation of the surface using fewer polygons than in the original representation, the method comprising:
 sub-sampling original elevation mesh data defining a polygon mesh surface where vertices of polygons correspond to points on an X-Y grid with a variable Z value at each grid point to generate low resolution elevation mesh data for a low resolution representation of the polygon mesh surface where vertices of polygons correspond to points on a coarser X-Y grid than the original elevation mesh data;   determining error values indicative of the extent that portions of the surface defined by the low resolution elevation mesh data differ from corresponding portions of the surface defined by the original elevation mesh data; and   generating an alternative representation of the polygon mesh surface comprising:   low resolution elevation mesh data for the portions of the polygon mesh surface associated with error values less than a threshold value;   transition mesh data defining a polygon mesh surface immediately adjacent the perimeter of portions of the surface represented by the low resolution elevation mesh data; and   higher resolution elevation mesh data for the remaining portions of the polygon mesh surface wherein the higher resolution elevation mesh data comprises data defining a polygon mesh surface where vertices of polygons correspond to points on finer regular X-Y grid than the low resolution elevation mesh data.   
     
     
         2 . The method of  claim 1  wherein sub-sampling original elevation mesh data comprises sampling the Z values at grid points for every nth entry in every nth line in the X-Y grid. 
     
     
         3 . The method of  claim 1  wherein determining error values comprises calculating error values based on the differences between Z values associated with grid points in the original elevation mesh data with corresponding Z values for the surface defined by portions of the surface defined by the low resolution elevation mesh data at corresponding X-Y grid points. 
     
     
         4 . The method of  claim 3  wherein the error value for a portion of a surface comprises the maximum difference between Z values associated with grid points in the original elevation mesh data with corresponding Z values for the surface defined by portions of the surface defined by the low resolution elevation mesh data for that portion of the surface. 
     
     
         5 . The method of  claim 3  wherein the error value for a portion of a surface comprises an average difference between Z values associated with grid points in the original elevation mesh data with corresponding Z values for the surface defined by portions of the surface defined by the low resolution elevation mesh data for that portion of the surface. 
     
     
         6 . The method of  claim 1  wherein determining error values comprises calculating a plurality of error values for each portion of the surface wherein generating an alternative representation of the polygon mesh surface comprises generating low resolution elevation mesh data for the portions of the polygon mesh surface associated for which all error values are less than a threshold value. 
     
     
         7 . The method of  claim 1  wherein generating an alternative representation of the polygon mesh surface comprises:
 determining higher resolution elevation mesh data for the portions of the polygon mesh surface associated with error values greater than the threshold value; 
 identifying portions of the higher resolution elevation mesh data corresponding to portions of the polygon mesh surface immediately adjacent portions of the polygon mesh surface represented by low resolution elevation mesh data; and 
 deleting the higher resolution elevation mesh data for the identified portions of the polygon surface immediately adjacent portions of the polygon mesh surface represented by low resolution elevation mesh data. 
 
     
     
         8 . The method of  claim 1  wherein generating an alternative representation of the polygon mesh surface comprises:
 identifying portions of a polygon mesh surface not represented by higher resolution or low resolution elevation mesh data; and 
 determining a Delaunay triangulation of the identified unrepresented portions of the polygon mesh surface connecting the vertices at the perimeters the of the surfaces represented by higher and low resolution elevation mesh data. 
 
     
     
         9 . The method of  claim 1  wherein the higher resolution elevation mesh data comprises original elevation mesh data for the portions of the polygon mesh surface which are not represented by the low resolution elevation mesh data or the transition mesh data. 
     
     
         10 . The method of  claim 1  wherein the higher resolution elevation mesh data comprises data defining a polygon mesh surface where vertices of polygons correspond to points on a plurality of finer resolution regular X-Y grids, the method further comprising:
 determining high resolution elevation mesh data for the portions of a polygon mesh surface not represented by transition mesh data or low level resolution elevation data comprising data defining a polygon mesh surface where vertices of polygons correspond to points on finer regular X-Y grid than the low resolution elevation mesh data; 
 determining error values indicative of the extent that portions of the surface defined by the high resolution elevation mesh data differ from corresponding portions of the surface defined by the original elevation mesh data; 
 utilizing the high resolution elevation mesh data as data to represent the portions of the polygon mesh surface associated with error values less than a threshold value; 
 generating further transition mesh data defining a polygon mesh surface immediately adjacent the perimeter of portions of the surface represented by the elevation mesh data; and 
 generating finer resolution elevation mesh data for the remaining portions of the polygon mesh surface wherein the finer resolution elevation mesh data comprises data defining a polygon mesh surface where vertices of polygons correspond to points on finer regular X-Y grid than the high resolution elevation mesh data. 
 
     
     
         11 . A computer readable medium storing computer interpretable instructions which when interpreted by a programmable computer cause the computer to process elevation mesh data defining a polygon mesh surface to determine an alternative representation of the surface using fewer polygons than in the original representation, by:
 sub-sampling original elevation mesh data defining a polygon mesh surface where vertices of polygons correspond to points on an X-Y grid with a variable Z value at each grid point to generate low resolution elevation mesh data for a low resolution representation of the polygon mesh surface where vertices of polygons correspond to points on a coarser X-Y grid than the original elevation mesh data;   determining error values indicative of the extent that portions of the surface defined by the low resolution elevation mesh data differ from corresponding portions of the surface defined by the original elevation mesh data; and   generating an alternative representation of the polygon mesh surface comprising:   low resolution elevation mesh data for the portions of the polygon mesh surface associated with error values less than a threshold value;   transition mesh data defining a polygon mesh surface immediately adjacent the perimeter of portions of the surface represented by the low resolution elevation mesh data; and   higher resolution elevation mesh data for the remaining portions of the polygon mesh surface wherein the higher resolution elevation mesh data comprises data defining a polygon mesh surface where vertices of polygons correspond to points on finer regular X-Y grid than the low resolution elevation mesh data.   
     
     
         12 . A processing apparatus for processing elevation mesh data defining a polygon mesh surface to determine an alternative representation of the surface using fewer polygons than in the original representation, the apparatus comprising:
 a mesh data store operable to store elevation mesh data defining a polygon mesh surface where vertices of polygons correspond to points on an X-Y grid with a variable Z value at each grid point; and   a re-gridding module operable to:
 sub-sample elevation mesh data stored in the mesh data store to generate low resolution elevation mesh data for a low resolution representation of the polygon mesh surface where vertices of polygons correspond to points on a coarser X-Y grid than the original elevation mesh data; 
 determine error values indicative of the extent that portions of the surface defined by the low resolution elevation mesh data differ from corresponding portions of the surface defined by the original elevation mesh data; and 
 output as data representing an alternative representation of the polygon mesh surface: 
 low resolution elevation mesh data for the portions of the polygon mesh surface associated with error values less than a threshold value; 
 transition mesh data defining a polygon mesh surface immediately adjacent the perimeter of portions of the surface represented by the low resolution elevation mesh data; and 
 higher resolution elevation mesh data for the remaining portions of the polygon mesh surface wherein the higher resolution elevation mesh data comprises data defining a polygon mesh surface where vertices of polygons correspond to points on finer regular X-Y grid than the low resolution elevation mesh data. 
   
     
     
         13 . The processing apparatus of  claim 12  wherein the re-gridding module is operable to sub-sample elevation mesh data stored in the mesh data store by sampling Z values at grid points for every nth entry in every nth line in the X-Y grid of a stored elevation mesh. 
     
     
         14 . The processing apparatus of  claim 12  wherein the re-gridding module is operable to determine error values by calculating error values based on the differences between Z values associated with grid points in the original elevation mesh data with corresponding Z values for the surface defined by portions of the surface defined by the low resolution elevation mesh data at corresponding grid points. 
     
     
         15 . The processing apparatus of  claim 12  wherein the re-gridding module is operable to:
 determine higher resolution elevation mesh data for the portions of the polygon mesh surface associated with error values greater than the threshold value; 
 identify portions of the higher resolution elevation mesh data corresponding to portions of the polygon mesh surface immediately adjacent portions of the polygon mesh surface represented by low resolution elevation mesh data; and 
 delete the higher resolution elevation mesh data for the identified portions of the polygon surface immediately adjacent portions of the polygon mesh surface represented by low resolution elevation mesh data. 
 
     
     
         16 . The processing apparatus of  claim 12  wherein the re-gridding module is operable to:
 identify portions of a polygon mesh surface not represented by higher resolution or low resolution elevation mesh data; and 
 determine a Delaunay triangulation of the identified unrepresented portions of the polygon mesh surface connecting the vertices at the perimeters the of the surfaces represented by higher and low resolution elevation mesh data.