# US 12,223,615 B2 · Apparatus and method for approximate trilinear interpolation for scene reconstruction > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,223,615 B2 - Document ID: US12223615B2 - Status: Granted - Kind: B2 - Application number: 16/917,791 - Filed: 2020-06-30 - Published: 2021-12-30 - Granted: 2025-02-11 - Earliest claimed: 2020-06-30 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: Vivek De; Ram Krishnamurthy; Amit Agarwal; Steven Hsu; Monodeep Kar - Web page: https://patentgrep.com/patent/US12223615B2 ## CPC - G06T 3/4007: based on interpolation, e.g. bilinear interpolation (image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403) - G06T 7/70: Determining position or orientation of objects or cameras (camera calibration G06T7/80) - G06T 15/06: Ray-tracing - G06T 17/205: {Re-meshing} - G06T 2207/20021: Dividing image into blocks, subimages or windows - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract A method comprising: dividing a 3D space into a voxel grid comprising a plurality of voxels; associating a plurality of distance values with the plurality of voxels, each distance value based on a distance to a boundary of an object; selecting an approximate interpolation mode for stepping a ray through a first one or more voxels of the 3D space responsive to the first one or more voxels having distance values greater than a threshold; and detecting the ray reaching a second one or more voxels having distance values less than the first threshold; and responsively selecting a precise interpolation mode for stepping the ray through the second one or more voxels. ## Claims ### Claim 1 A method comprising: dividing a three-dimensional (3D) space into a voxel grid comprising a plurality of voxels; associating a plurality of distance values with the plurality of voxels, each distance value based on a distance to a boundary of an object; selecting a first interpolation mode for stepping a ray through a first one or more voxels of the 3D space responsive to the first one or more voxels having distance values greater than a threshold, wherein stepping the ray through the first one or more voxels in the first interpolation mode comprises performing interpolation of the ray through the first one or more voxels by passing distance values associated with the first one or more voxels through a sign-preserving shift circuit, the sign-preserving shift circuit performs incrementally bit shifting on the distance values, wherein a number of bits in the bit shifting performed on a distance value of the distance values corresponding to a voxel of the first one or more voxels is selected based on a plurality of voxel address fractions of the voxel; detecting the ray reaching a second one or more voxels having distance values less than the threshold; and responsively selecting a second interpolation mode that is more precise than the first interpolation mode for stepping the ray through the second one or more voxels. ### Claim 2 (depends on 1) The method of claim 1 wherein the threshold comprises a value of 0, wherein the ray is traversed in accordance with the first interpolation mode for voxels having positive distance values, and wherein the ray is traversed in accordance with the second interpolation mode for voxels having negative distance values. ### Claim 3 (depends on 1) The method of claim 1 wherein the distance values comprise truncated signed distance function (TSDF) values. ### Claim 4 (depends on 3) The method of claim 3 further comprising: determining the boundary of the object based on sign values of the TSDF values associated with voxels on different sides of the boundary. ### Claim 5 (depends on 4) The method of claim 4 wherein voxels external to the object are associated with positive TSDF values and voxels inside the object are associated with negative TSDF values. ### Claim 6 (depends on 1) The method of claim 1 further comprising: determining a maximum possible negative TSDF value of a first voxel using a magnitude of address values associated with the first voxel in combination with a sign of a first TSDF value associated with the first voxel; and using the maximum possible negative TSDF value as the distance value. ### Claim 7 (depends on 1) The method of claim 1 further comprising: performing a plurality of multiplications when in the second interpolation mode to multiply a plurality of distance values by a corresponding plurality of address fractions of a voxel to generate a plurality of intermediate products; and adding the plurality of intermediate products to generate a final interpolated result. ### Claim 8 An apparatus comprising: a first circuit to perform a first interpolation of a ray through a first set of voxels in a voxel grid based on coarse grain magnitudes of a first set of voxel address values and first distance values associated with the first set of voxels, wherein the first circuit is operable responsive to the first distance values indicating that the first set of voxels being traversed by the ray are external to an object, wherein performing the first circuit of the ray through the first set of voxels comprises passing the first distance values associated with the first set of voxels through a sign-preserving shift circuit, the sign-preserving shift circuit to perform bit shifting on the first distance values, wherein a number of bits in the bit shifting performed on a distance value of the first distance values corresponding to a voxel of the first set of voxels is selected based on a plurality of voxel address fractions of the voxel; and a second circuit to perform a second interpolation of the ray that is more precise than the first interpolation through a second set of voxels in the voxel grid responsive to detecting that second distance values associated with the second set of voxels indicate that the second set of voxels are not external to the object. ### Claim 9 (depends on 8) The apparatus of claim 8 further comprising: a third circuit to determine that the first distance values are above a specified threshold and to responsively indicate that the first set of voxels are external to the object, the third circuit to determine that one or more of the second distance values are below the specified threshold and to responsively indicate that the second set of voxels are not external to the object. ### Claim 10 (depends on 9) The apparatus of claim 9 wherein the specified threshold comprises a value of 0. ### Claim 11 (depends on 9) The apparatus of claim 9 wherein the first and second distance values comprise truncated signed distance function (TSDF) values. ### Claim 12 (depends on 8) The apparatus of claim 8 wherein the first circuit is configured to: generate a control signal based on a set of voxel address values and a current distance value; and select an output distance value from a set of input values responsive to the control signal, the set of input values comprising a 0 value, the current distance value, and one or more fractions of the current distance value, wherein the first circuit is to generate an interpolated value based on the output distance value and the set of voxel address values. ### Claim 13 (depends on 12) The apparatus of claim 12 wherein the one or more fractions of the current distance value comprise half the current distance value, a quarter of the current distance value, and an eighth of the current distance value. ### Claim 14 (depends on 12) The apparatus of claim 12, wherein generating the one or more fractions of the current distance value comprises shifting the current distance value. ### Claim 15 (depends on 8) The apparatus of claim 8 wherein the second circuit is configured to: multiply a plurality of distance values with a plurality of address values or values derived from one or more of the plurality of address values to generate a plurality of intermediate products; and generate a sum of the plurality of intermediate products to generate an interpolated distance value. ### Claim 16 (depends on 10) The apparatus of claim 10 wherein a boundary of the object is identified based on different signs of the first and second distance values associated with voxels on different sides of the boundary. ### Claim 17 (depends on 9) The apparatus of claim 9 wherein a maximum possible negative distance value of a voxel associated with the first set of distance values is determined and used to determine that the voxel is external to the object. ### Claim 18 A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform: dividing a three-dimensional (3D) space into a voxel grid comprising a plurality of voxels; associating a plurality of distance values with the plurality of voxels, each distance value based on a distance to a boundary of an object; selecting a first interpolation mode for stepping a ray through a first one or more voxels of the 3D space responsive to the first one or more voxels having distance values greater than a threshold, wherein stepping the ray through the first one or more voxels in the first interpolation mode comprises performing interpolation of the ray through the first one or more voxels by passing distance values associated with the first one or more voxels through a sign-preserving shift circuit, the sign-preserving shift circuit performing bit shifting on the distance values, wherein a number of bits in the bit shifting performed on a distance value of the distance values corresponding to a voxel of the first one or more voxels is selected based on a plurality of voxel address fractions of the voxel; detecting the ray reaching a second one or more voxels having distance values less than the threshold; and responsively selecting a second interpolation mode that is more precise than the first interpolation mode for stepping the ray through the second one or more voxels. ### Claim 19 (depends on 18) The non-transitory machine-readable medium of claim 18 wherein the threshold comprises a value of 0, wherein the ray is traversed in accordance with the first interpolation mode for voxels having positive distance values, and wherein the ray is traversed in accordance with the second interpolation mode for voxels having negative distance values. ### Claim 20 (depends on 18) The non-transitory machine-readable medium of claim 18 wherein the distance values comprise truncated signed distance function (TSDF) values. ### Claim 21 (depends on 20) The non-transitory machine-readable medium of claim 20 further comprising program code to cause the machine to perform the operations of: determining the boundary of the object based on sign values of the TSDF values associated with voxels on different sides of the boundary. ### Claim 22 (depends on 21) The non-transitory machine-readable medium of claim 21 wherein voxels external to the object are associated with positive TSDF values and voxels inside the object are associated with negative TSDF values. ### Claim 23 (depends on 18) The non-transitory machine-readable medium of claim 18 further comprising program code to cause the machine to perform: determining a maximum possible negative TSDF value of a first voxel using a magnitude of address values associated with the first voxel in combination with a sign of a first TSDF value associated with the first voxel; and using the maximum possible negative TSDF value as the distance value. ### Claim 24 (depends on 18) The non-transitory machine-readable medium of claim 18 further comprising program code to cause the machine to perform: performing a plurality of multiplications when in the second interpolation mode to multiply a plurality of distance values by a corresponding plurality of address fractions of a voxel to generate a plurality of intermediate products; and adding the plurality of intermediate products to generate a final interpolated result.