Patent Description:
Some aspects and examples disclosed herein are directed to complexity reduction via cavity removal by: (i) determining voxels on an initial exterior boundary of a first object in a voxel space, (ii) generating a distance field, outward from the initial exterior boundary of the first object, (iii) determining voxels having a local maximum of the distance field, (iv) determining a largest local maximum value from among the local maxima, (v) removing, from the distance field, voxels having a distance field value greater than the largest local maximum value, (vi) for a current distance field value, iterating downward from the largest local maximum value to: (A) remove, from the distance field, voxels having a distance field value equal to the current distance field value, (B) flag, as being in an interior region, voxels removed from the distance field that are contiguous, through other voxels removed from the distance field, with a voxel having a local maximum, and (C) flag, as being in an exterior region, voxels removed from the distance field that are contiguous, through other voxels removed from the distance field, with a voxel on an outer edge of the voxel space, (vii) determining whether a voxel is flagged as both in an interior region and in an exterior region, (viii) based at least on a first voxel being flagged as both in an interior region and in an exterior region, flagging the first voxel as an added boundary voxel, (ix) determining an adjusted exterior boundary as the initial exterior boundary of the first object and any added boundary voxels, and (x) generating a reduced-complexity object for processing by floodfilling voxels up through the adjusted exterior boundary.

References made throughout this disclosure relating to specific examples and implementations are provided solely for illustrative purposes but, unless indicated to the contrary, are not meant to limit all examples.

Some three-dimensional (3D) virtual objects (e.g., assets) intended for mixed reality (MR), virtual reality (VR), and augmented reality (AR) (collectively MR) displays have more complexity than is necessary for a satisfactory user experience. Some examples of 3D objects include a set of voxels indicated as being within the volume of the object, which can be rendered in an MR display. Some 3D objects include a set of meshes and a definition of a surface texture, such as a texel map or perhaps a material specification. Additionally, some MR display platforms, such as head mounted displays (HMDs) may impose constraints for storage and processing, making it difficult for render complex 3D objects.

Aspects of the disclosure reduce complexity of 3D objects by filling holes and/or removing cavities in an automated or semi-automated fashion (e.g., not manually). Exemplary candidates for complexity reduction include 3D scan data that is "noisy" or "busy", such as those including gaps, holes, and cavities. The disclosure operates to reduce the polycount of the 3D objects to optimize a balance between visual complexity of the 3D objects and rendering performance of those 3D objects. Polycount is reduced in a manner that does not adversely affect display quality as perceived by the user. Filling holes and/or removing cavities improves the frame rate and transfer speeds (e.g., reduces bandwidth usage) and reduces storage burdens, thereby improving the functionality of at least one computing device.

Systems and methods are disclosed for removing unnecessary details, such as cavities and holes, from 3D objects. In some examples, a 3D object is dilated and eroded, and undesirable webbing is removed to preserve a higher percentage of exterior detail. In some examples, distance fields internal and external to the object are removed in a layered manner, and new object surfaces are added wherever openings are narrower than the cavity's internal dimensions, to seal off the cavities. Holes and cavities, which are obscured in many viewing angles, are thus filled in (e.g., removed), thereby reducing the burden of storing and processing the hidden interior surfaces to improve rendering performance.

Different disclosed approaches leveraging distance fields may be combined. For example, aspects of the disclosure operate to fill one or more holes in 3D objects without removing cavities. In other examples, aspects of the disclosure operate to remove one or more cavities in 3D objects without filling holes. In still other examples, aspects of the disclosure operate to fill one or more holes in 3D objects while removing one or more cavities in those same 3D objects. As such, aspects of the disclosure operate to fill one or more holes and/or remove one or more cavities in 3D objects to reduce complexity of those 3D objects.

Although the examples use voxels (e.g., 3D pixels), it should be understood that the techniques disclosed herein may also be applied to two-dimensional (2D) pixels.

<FIG> illustrates a 2D cut plane <NUM> of an exemplary 3D object <NUM> in a 3D voxel space <NUM>. Voxel space <NUM> has an outer edge <NUM>. In this example, object <NUM> is the original received object (e.g., a first object) and has an exterior boundary <NUM> which includes the interior walls of a cavity <NUM>. Object <NUM> also has additional cavity <NUM> and holes <NUM> and <NUM>. Cavities <NUM> and <NUM> have openings that are narrower than the internal dimensions, whereas hole <NUM> has an opening that is wider than the dimensions further inside, and hole <NUM> has a constant width.

<FIG> illustrates an exemplary 2D cut plane of a reduced-complexity object <NUM> (e.g., 3D object) that was generated from original object <NUM> in accordance with a complexity reduction via hole filling operation. In some examples, the hole filling operation is represented by the operations described by flow charts <NUM> and <NUM> in <FIG> and <FIG>, respectively, with <FIG> illustrating intermediate stages.

<FIG> illustrates an intermediate stage <NUM> of complexity reduction via hole filling. After voxel space <NUM> containing original object <NUM> having an exterior boundary <NUM> has been received or accessed, and the voxels on exterior boundary <NUM> of original object <NUM> have been determined, a first maximum distance field value is selected. The first maximum distance field value may be specified by a human operator, may be determined based on the size and some complexity metric of original object <NUM>, or may be a trial value in an optimization loop. A first distance field <NUM> is generated outward from exterior boundary <NUM> of original object <NUM>, up through the maximum distance field value. In some examples, generating first distance field <NUM> may involve rastering through at least a portion of voxel space <NUM>. For each voxel exterior to original object <NUM>, a distance to a nearest exterior boundary voxel (e.g., a voxel on exterior boundary <NUM> of original object <NUM>) is determined. Based at least on the determined distance being less than or equal to the maximum distance field value, the determined distance is assigned to the voxel as a first distance field value. Distance field values may be quantized, to permit easier calculations of equality for distance field values of different voxels.

A floodfill boundary <NUM> (see <FIG>) is the set of outermost voxels of the first distance field having a distance value equal to the maximum distance field value. Floodfill boundary <NUM> is determined using only the outer-most voxels of first distance field <NUM>, even if multiple voxels may have the same distance field value, in some embodiments. For example, cavity <NUM> has an opening width <NUM>, which is fully closed off by distance field <NUM> only if distance field <NUM> has a depth <NUM> equal to at least half of opening width <NUM>. This permits filling in of cavity <NUM>. In another example, a maximum distance field value that is less than half of opening width <NUM> would not result in the closure of the opening of cavity <NUM> and thus would fail to fill in cavity <NUM>. If, initially, a maximum distance field value had been selected that was too small to close off cavity <NUM>, then by iterating with increasing maximum distance field values (e.g., additional maximum distance field values that are higher), then eventually, a maximum distance field value will be used that will close off cavity <NUM>. If, however, an initial maximum distance field value had been selected that was far in excess of what was necessary to close off cavity <NUM>, then by iterating with decreasing maximum distance field values (e.g., additional maximum distance field values that are smaller), then eventually, a maximum distance field value will be used that will not close off cavity <NUM>. Abrupt changes in the number of voxels included within the final resulting object may be detectable.

With the maximum distance field value set to exactly half of opening width <NUM> (within quantization tolerances), there is a line of voxels having the same distance field value, stretching from inside cavity <NUM> to outside of original object <NUM>. Only the outermost of these voxels are used for floodfill boundary <NUM> in this example. The voxels interior to floodfill boundary <NUM> are a floodfill region <NUM> that is floodfilled to generate intermediate stage <NUM>, as illustrated in <FIG>. In stage <NUM>, all holes and cavities of original object <NUM> have been filled, although surface detail (e.g., details of exterior boundary <NUM>) have been lost. Stage <NUM> is thus a dilated object, generated by dilating original object <NUM> by the maximum distance field value.

The next stages are used to recover at least some of the original surface detail. Part of the operation includes eroding the dilated object of stage <NUM> by the maximum distance field value to generate an eroded dilated object <NUM> (see <FIG>). Referring to <FIG>, showing stage <NUM>, a second distance field <NUM> is generated inwardly from floodfill boundary <NUM>, up through the maximum distance field value - the same maximum distance field that was used for the dilation procedure. In some examples, generating second distance field <NUM> may involve rastering through at least a portion of voxel space <NUM>. For each voxel interior to floodfill region <NUM>, a distance to a nearest floodfill boundary voxel (e.g., a voxel on floodfill boundary <NUM>) is determined. Based at least on the distance being less than or equal to the maximum distance field value, the determined distance is assigned to the voxel as a second distance field value.

The voxels in the second distance field are removed (e.g., eroded) from floodfill region <NUM> to generate eroded dilated object <NUM> as illustrated in <FIG>. In <FIG>, original object <NUM> is overlayed on the eroded results of stage <NUM>. An exterior boundary <NUM> shows at least some of the details of exterior boundary <NUM> of original object <NUM>. Voxels that have been added by the dilation, floodfill, and erosion processes (together called "closure" in some examples) are indicated as added voxel regions <NUM>. Added voxels may be determined by identifying voxels in eroded dilated object <NUM> that are not also in original object <NUM>.

Eroded dilated object <NUM> contains webbing, which may be undesirable in some examples, as it blurs exterior boundary details (see the magnified view of <FIG>). Four regions of webbing <NUM>, <NUM>, <NUM>, and <NUM> are indicated in this example. In some examples, a procedure is implemented to remove regions of webbing <NUM>, <NUM>, <NUM>, and <NUM>, without clearing out cavities and holes that have been filled in. The result is the reduced-complexity object <NUM> of <FIG>. The procedure is described in more detail for <FIG>, and involves determining, for each of one or more added regions, a ratio of the number of internal surface voxels to the number of external. In some examples, the number of internal surface voxels is divided by the number of external surface voxels to obtain the ratio. Higher ratios are associated with filling deep holes and cavities, whereas lower ratios are associated with filling of shallow surface depressions and webbing (such as regions of webbing <NUM>, <NUM>, <NUM>, and <NUM>). Webbing having a ratio of internal surface voxels to external surface voxels that is below a first ratio threshold are removed from eroded dilated object <NUM>. In some examples, the threshold ratio may be approximately <NUM> to <NUM>.

Of the added voxels, a surface voxel is one that is adjacent to a voxel that is not an added voxel. Of the added surface voxels, an added surface voxel that is adjacent to an empty voxel (a voxel that is not in original object <NUM>) is flagged, or otherwise labeled, as an external surface voxel. A set of external surface voxels <NUM> is indicated in <FIG>. Of the added surface voxels, an added surface voxel that is adjacent to original object <NUM> is flagged as an internal surface voxel. A set of internal surface voxels <NUM> is also indicated in <FIG>. Internal surface voxels are surface voxels that are not external surface voxels. That is, they are surface voxels and they are not adjacent to a voxel that is not in original object <NUM>.

<FIG> illustrates a further magnified view of a portion of <FIG>. Specifically, <FIG> illustrates region of webbing <NUM> in greater detail, with the external surface voxels annotated with horizontal lines and the internal surface voxels annotated with vertical lines.

With the webbing removed, a reduced complexity object has been generated that may be easier to render, store, and transfer, and yet may preserve at least some of the surface detail of the original object.

<FIG> is a flow chart <NUM> illustrating exemplary operations involved in complexity reduction via hole filling. The operations illustrated in <FIG> may be performed by any processing unit, such as a computing node. Operation <NUM> includes receiving a voxel space containing an original object having an exterior boundary. Operation <NUM> includes determining voxels on the exterior boundary of the original object. Operation <NUM> includes selecting a first maximum distance field value. Operation <NUM> includes dilating the original object by the maximum distance field value to generate a dilated object. Operation <NUM> includes eroding the dilated object by the maximum distance field value to generate an eroded dilated object.

<FIG> is a flow chart <NUM> illustrating exemplary operations involved in complexity reduction via hole filling. The operations illustrated in <FIG> may be performed by any processing unit, such as a computing node. Operation <NUM> includes receiving a voxel space containing an original object having an exterior boundary, and operation <NUM> includes determining voxels on the exterior boundary of the original object. Operation <NUM> includes selecting a first maximum distance field value, which may be input by a user, selected based on historical values, or selected by an automated operation that iterates with multiple different values, in order to find an optimum value.

Operation <NUM> involves dilating the original object by the maximum distance field value to generate a dilated object, and is comprised of operations <NUM>-<NUM>. Operation <NUM> generates a first distance field, outward from the exterior boundary of the original object, up through the maximum distance field value. Operation <NUM> comprises operations <NUM> and <NUM>. In some examples, operation <NUM> rasters through at least a portion of the voxel space and, for each voxel exterior to the original object, determines a distance to a nearest exterior boundary voxel of the original object. In operation <NUM>, based at least on the determined distance being less than or equal to the maximum distance field value, the determined distance is assigned to the voxel as a first distance field value. Distance field values may be quantized, to permit easier calculations of equality for distance field values of different voxels.

In operation <NUM>, a floodfill boundary is determined. The floodfill boundary is a set of outermost voxels of the first distance field having a distance value equal to the maximum distance field value. Operation <NUM> floodfills a floodfill region comprising voxels interior to the floodfill boundary. The resulting dilated object includes the voxels in the floodfill region. Operation <NUM> erodes the dilated object by the maximum distance field value to generate an eroded dilated object, and comprises operations <NUM>-<NUM>. Operation <NUM> generates a second distance field, inward from the floodfill boundary, up through the maximum distance field value. Operation <NUM> may include rastering through at least a portion of the voxel space, and for each voxel interior to the floodfill region, determining a distance to a nearest floodfill boundary voxel in operation <NUM>. Operation <NUM> includes, based at least on the distance being less than or equal to the maximum distance field value, assigning the determined distance to the voxel as a second distance field value. Operation <NUM> then removes, from the floodfill region, voxels in the second distance field, wherein the eroded dilated object comprises voxels remaining in the floodfill region. This generates an eroded dilated object. The process of dilating and eroding (e.g., operation <NUM> and <NUM>) may be referred to as closure.

A first ratio threshold is selected in operation <NUM>. The first ratio threshold may be input by a user, selected based on historical values, or selected by an automated operation that iterates with multiple different values, to find an optimum value. In some examples, a threshold ratio is approximately <NUM> to <NUM>. A higher threshold retains more of the original surface resulting in higher rendering quality, but at a cost of lower compression potential. This is an example of a quality versus performance trade-off. Different threshold ratios may be used, based on factors of connection speed, storage capacity, and frame rate performance. Operation <NUM> includes determining one or more added voxels as voxels in the eroded dilated object and not in the original object, such as by rastering through at least a portion of the voxel space. Operation <NUM> includes determining one or more added regions as sets of contiguous regions of added voxels.

Operation <NUM> removes webbing from the eroded dilated object, and comprises operations <NUM>-<NUM>. Operation <NUM> removes webbing having a ratio of internal surface voxels to external surface voxels below the first ratio threshold. Operation <NUM> sets up an iteration process for each added region. Operation <NUM> determines surface voxels of the added region, and operation <NUM> sets up an iteration process for each surface voxel of the added region. Operation <NUM> determines whether the surface voxel of the added region is adjacent to a voxel not in the original object (e.g., an empty voxel). Operations <NUM> and <NUM> flag the surface voxels as either external surface voxels or internal surface voxels. Operation <NUM> includes, based at least on the surface voxel of the added region being adjacent to a voxel not in the original object, flagging the voxel as an external surface voxel. Operation <NUM> includes, based at least on the surface voxel of the added region not being adjacent to a voxel not in the original object, flagging the voxel as an internal surface voxel. External surface voxels are those voxels that had been added and which are adjacent to empty voxels, and internal surface voxels are those voxels that had been added and which are not adjacent to empty voxels, but instead are adjacent to the original object. Added voxels that are adjacent to both empty voxels and the original object are external surface voxels.

Operation <NUM> determines, for the added region, a ratio of a number of internal surface voxels to a number of external surface voxels. The number of internal surface voxels is divided by the number of external surface voxels to obtain the ratio. Decision operation <NUM> determines whether the ratio is below the threshold. If it is, then operation <NUM> includes, based at least on the ratio for the added region being below the first ratio threshold, removing the added region from the eroded dilated object.

In some examples, a complexity metric may be computed to ascertain the complexity of the object in operation <NUM>. This complexity metric is used in operation <NUM> to adjust the maximum distance field value or the ratio threshold, as part of an optimization process in some examples. In some examples, a count of the outside voxels of the final object is used to determine whether to increase or decrease the distance field maximum distance field value or the ratio threshold. That is, operation <NUM> includes, based at least on computing a complexity metric, adjusting at least one of the ratio threshold and the maximum distance field value. Operation <NUM> iterates, with at least one additional (e.g., new) ratio threshold, removing of webbing to generate a plurality of eroded dilated objects. Operation <NUM> iterates, with at least one additional (e.g., new) maximum distance field value, dilating the original object and eroding the dilated object to generate a plurality of eroded dilated objects. In some examples, operation <NUM> includes selecting, from the plurality of eroded dilated objects, a reduced-complexity object as the final object for some action. In some examples of operation <NUM>, that action may include displaying the final object, for example on presentation components <NUM> (of <FIG>) that may include an HMD. In some examples of operation <NUM>, that action may include rendering the final object for display, for example using computing device <NUM> and presentation components <NUM> (See <FIG>), which may include an HMD. In some examples of operation <NUM>, that action may include storing the final object for a later rendering operation in memory <NUM> of computing device <NUM>. In some examples of operation <NUM>, that action may include transmitting the final object to a remote node (e.g., a remote version of computing device <NUM>), using network component <NUM> of computing device <NUM>.

Cavity removal from 3D objects is next discussed.

<FIG> illustrates a 2D cut plane <NUM> of an exemplary 3D object <NUM> in a 3D voxel space <NUM>. Voxel space <NUM> has an outer edge <NUM>. In this example, object <NUM> is the original received or accessed object and has an initial exterior boundary <NUM> and a cavity <NUM>. <FIG> illustrates an exemplary 2D cut plane of a reduced-complexity object <NUM> (3D object) that was generated from original object <NUM> in accordance with a complexity reduction via cavity removal operation. For example, cavity <NUM> has been removed. In some examples, the operations are described by flow charts <NUM> and <NUM> in <FIG> and <FIG>, respectively, with <FIG> illustrating intermediate stages.

<FIG> illustrates a stage <NUM> in which a distance field <NUM> has been generated outwardly from initial exterior boundary <NUM> of original object <NUM>. Initially, distance field <NUM> may have been generated for all voxels in voxel space <NUM> and not in original object <NUM>. In some examples, generating a distance field involves, for each voxel exterior to original object <NUM>, determining a distance to a nearest initial exterior boundary voxel (a voxel on exterior boundary <NUM> of original object <NUM>) and assigning the determined distance to the voxel as a distance field value. Distance field values may be quantized, to permit easier calculations of equality for distance field values of different voxels. Voxels having a local maximum distance field value may be found, and the largest local maximum value determined from among the local maxima. The determination of local maxima excludes voxels on outer edge <NUM>. Voxels having a distance field value greater than the largest local maximum value are removed from the distance field. The resulting distance field now extends only as far outward from original object <NUM> as the maximum depth of cavity <NUM>. This is stage <NUM> illustrated in <FIG>, with a single local maximum at point <NUM> in the center (e.g., the maximum distance from all points of original object <NUM>).

An iterative loop draws down distance field <NUM>, one layer at a time. A layer in distance field <NUM> is all voxels having the same distance field value. Starting with the largest local maximum value, all voxels having the same distance field value as the current distance field value are removed. Voxels that are removed from distance field <NUM> are flagged as being in an interior region, flagged as being in an exterior region, or both. An interior region voxel is a voxel removed from the distance field that is contiguous (e.g., through one or more other voxels removed from the distance field) with a voxel having a local maximum. For example, an interior region voxel is a voxel that is immediately adjacent to a voxel having a local maximum, or contiguous to the voxel having a local maximum via one or more other voxels removed from the distance field.

In the illustrated example of <FIG>, at stage <NUM>, an interior region <NUM> is a set of voxels that had been removed from distance field <NUM> and are contiguous with the local maximum at point <NUM> (see <FIG>). Removed voxels that are not interior region voxels are flagged as exterior region voxels. The exterior region encircles the outside of distance field <NUM>. A set of exterior region voxels <NUM> is indicated, which contains local maximum at point <NUM> and other voxels contiguous with it, that are not within distance field <NUM>. Another process of determining exterior region voxels determines that voxels removed from distance field <NUM> that are contiguous, through one or more other voxels removed from distance field <NUM>, with a voxel on outer edge <NUM> of voxel space <NUM> are exterior region voxels. Thus, exterior region voxels may be determined directly, or by determining that they are not interior region voxels.

<FIG> illustrate an exemplary progression of the iterative process as distance field <NUM> is reduced. A spike <NUM> appears in interior region <NUM> and another spike <NUM> appears in the exterior region outside distance field <NUM>. Interior region <NUM> grows as distance field <NUM> shrinks. If there are multiple local maxima, the interior region surrounding the largest local maximum grows first, and the interior regions surrounding the other local maxima start growing when the distance field has shrunk to include only lower values comparable to the other local maxima.

The spikes <NUM> and <NUM> start off small in stage <NUM> of <FIG>, and grow by stage <NUM> of <FIG>. When spikes <NUM> and <NUM> touch, the voxels at the center of the intersection are flagged as both in an interior region and in an exterior region. When this occurs, based at least on a voxel being flagged as both in an interior region and in an exterior region, those voxel are flagged as added boundary voxels. In some situations, removing a layer of distance field <NUM> removes multiple voxels in a line between spikes <NUM> and <NUM>. Rather than adding the entire set of newly-removes voxels added boundary voxels, only the center voxel is added as a boundary voxel. This is illustrated in <FIG>, showing stage <NUM>. A new added boundary <NUM> is generated at the intersection area, in the center. By the time distance field <NUM> is fully depleted in stage <NUM> (see <FIG>), added boundary <NUM> closes up original object <NUM>. Interior region <NUM> fully occupies the interior of an adjusted exterior boundary, defined by combination of initial exterior boundary <NUM> of original object <NUM> and added boundary <NUM>. Any "leaks" of original object <NUM> are sealed because the voxels in any openings are flagged as both in an interior region and in an exterior region and therefore be flagged as added boundary voxels. Floodfilling voxels up through the adjusted exterior boundary generates reduced-complexity object <NUM> of <FIG>.

<FIG> is a flow chart <NUM> illustrating exemplary operations involved in complexity reduction via cavity removal. The operations illustrated in <FIG> may be performed by any processing unit, such as a computing node. Operation <NUM> includes receiving a voxel space containing an original object having an initial exterior boundary. Operation <NUM> includes determining voxels on the initial exterior boundary of the original object. Operation <NUM> includes generating a distance field, outward from the initial exterior boundary of the original object. Operation <NUM> includes determining voxels having a local maximum of the distance field. Operation <NUM> includes determining a largest local maximum value from among the local maxima. Operation <NUM> includes removing, from the distance field, voxels having a distance field value greater than the largest local maximum value.

Operation <NUM> includes setting up an iteration for a current distance field value iterating downward from the largest local maximum value (e.g., reducing the value with each iteration). Operation <NUM> includes removing, from the distance field, voxels having a distance field value equal to the current distance field. Operation <NUM> includes flagging, as being in an interior region, voxels removed from the distance field that are contiguous, through one or more other voxels removed from the distance field, with a voxel having a local maximum. Operation <NUM> includes flagging, as being in an exterior region, voxels removed from the distance field that are not interior region voxels. Operation <NUM> includes determining whether a voxel is flagged as both in an interior region and in an exterior region. Operation <NUM> includes, based at least on a voxel being flagged as both in an interior region and in an exterior region, flagging the voxel as an added boundary voxel. Operation <NUM> includes determining an adjusted exterior boundary as the initial exterior boundary of the object and any added boundary voxels. Operation <NUM> includes generating a first reduced-complexity object by floodfilling voxels up through the adjusted exterior boundary.

<FIG> is another flow chart illustrating exemplary operations involved in complexity reduction via cavity removal. The operations illustrated in <FIG> may be performed by any processing unit, such as a computing node. A voxel space containing an original object having an initial exterior boundary is received in operation <NUM>, and operation <NUM> determines voxels on the initial exterior boundary of the original object. Operation <NUM> generates a distance field, outward from the initial exterior boundary of the original object, using operations <NUM> and <NUM>. In some examples, generating a distance field comprises generating a distance field for all voxels in the voxel space and not in the original object (the empty voxels) all the way out to the outer edge of the voxel space. Operation <NUM> rasters through at least a portion of the voxel space and, for each voxel exterior to the original object, determines a distance to a nearest initial exterior boundary voxel of the original object. Operation <NUM> assigns the determined distance to the voxel as a distance field value.

Operation <NUM> determines voxels having a local maximum of the distance field, and includes operations <NUM> and <NUM>. Operation <NUM> rasters through at least a portion of the voxel space and, for each voxel in the distance field and not on an outer edge of the voxel space, determines whether any neighboring voxel has a greater a distance field value. In operation <NUM>, based at least on no neighboring voxel having a greater a distance field value, a voxel is flagged as a local maximum. Operation <NUM> then determines the largest local maximum value from among the local maxima, and operation <NUM> removes, from the distance field, voxels having a distance field value greater than the largest local maximum value. These removed voxels are outside the object, and out toward the outer edge of the voxel space.

An iterative operation <NUM> draws down the distance field one layer at a time, and comprises operations <NUM>-<NUM>. A layer is all voxels having the same distance field value. Operation <NUM> sets up an iteration of a current distance field value, iterating downward from the largest local maximum value. Operation <NUM> removes, from the distance field, voxels having a distance field value equal to the current distance field value. Operation <NUM> flags, as being in an interior region, voxels removed from the distance field that are contiguous, through one or more other voxels removed from the distance field, with a voxel having a local maximum. The result is an interior region growing around a local maximum. If there are multiple local maxima, the interior region surrounding the largest local maximum grows first, and the interior regions surrounding the other local maxima start growing when the distance field has shrunk to include only lower values comparable to the other local maxima.

Operation <NUM> flags, as being in an exterior region, voxels removed from the distance field that are contiguous, through other voxels removed from the distance field, with a voxel on an outer edge of the voxel space. In some situations, removing a layer of the distance field removes multiple voxels in a line between an interior region and an exterior region. Rather than flagging the entire set of newly-removed voxels, only the center voxel is flagged as being both in an interior region and in an exterior region. Decision operation <NUM> determines whether a voxel is flagged as both in an interior region and in an exterior region. If so, then operation <NUM> includes, based at least on a voxel being flagged as both in an interior region and in an exterior region, flagging the voxel as an added boundary voxel. In some examples of operation <NUM>, flagging the voxel as an added boundary voxel comprises flagging a center voxel of a set of voxels removed in a same layer. Operation <NUM> determines an adjusted exterior boundary as the initial exterior boundary of the original object and any added boundary voxels, and operation <NUM> generates a first reduced-complexity object by floodfilling voxels up through the adjusted exterior boundary.

Operation <NUM> moves to flow chart <NUM> or flow chart <NUM> (see <FIG> and <FIG>) to generate a second reduced-complexity object. In some examples, operation <NUM> may include selecting a first maximum distance field value; dilating the first reduced-complexity object by the maximum distance field value to generate a dilated object; and eroding the dilated object by the maximum distance field value to generate an eroded dilated object. In some examples, operation <NUM> may include selecting a first ratio threshold; determining one or more added voxels as voxels in the eroded dilated object and not in the original object; determining one or more added regions as sets of contiguous regions of added voxels; and removing, from the eroded dilated object, webbing having a ratio of internal surface voxels to external surface voxels below the first ratio threshold, to generate a second reduced-complexity object.

<FIG> illustrates how complexity reduction via hole filling and complexity reduction via cavity removal may produce different results, showing an intermediate stage <NUM>. Original object <NUM>, used in the example for complexity reduction via hole filling process, explained with <FIG>, has been subjected to the complexity reduction via cavity removal processes, explained with <FIG>. As illustrated in <FIG>, cavity <NUM> has been capped off with added boundaries <NUM> and <NUM>, and cavity <NUM> has been sealed with added boundary <NUM>. This is because the openings of cavities <NUM> and <NUM> are narrower than each cavity's internal dimensions.

In contrast, hole <NUM> opens such that the mouth is the widest dimension, and hole <NUM> has parallel sides. Thus, holes <NUM> and <NUM> are not sealed off by complexity reduction via cavity removal. A floodfilling operation generates reduced-complexity object <NUM>, as shown in <FIG>.

<FIG> is a block diagram of an example computing device <NUM> or node for implementing aspects disclosed herein, and is designated generally as computing device <NUM>. Computing device <NUM> is one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing device <NUM> be interpreted as having any dependency or requirement relating to any one or combination of components/modules illustrated.

The examples and embodiments disclosed herein may be described in the general context of computer code or machine-useable instructions, including computer-executable instructions such as program components, being executed by a computer or other machine, such as a personal data assistant or other handheld device. Generally, program components including routines, programs, objects, components, data structures, and the like, refer to code that performs particular tasks, or implement particular abstract data types. The disclosed examples may be practiced in a variety of system configurations, including personal computers, laptops, smart phones, mobile tablets, hand-held devices, consumer electronics, specialty computing devices, etc. The disclosed examples may also be practiced in distributed computing environments, where tasks are performed by remote-processing devices that are linked through a communications network. For example, a distributed computing environment may host cloud synthetics services. Some embodiments of synthetics services may provide synthetic 3D environments as well as rendering a surface in a synthetic scene.

Computing device <NUM> includes a bus <NUM> that directly or indirectly couples the following devices: memory <NUM>, one or more processors <NUM>, one or more presentation components <NUM>, input/output (I/O) ports <NUM>, I/O components <NUM>, a power supply <NUM>, and a network component <NUM>. Computing device <NUM> should not be interpreted as having any dependency or requirement related to any single component or combination of components illustrated therein. While computing device <NUM> is depicted as a seemingly single device, multiple computing devices <NUM> may work together and share the depicted device resources. For example, memory <NUM> may be distributed across multiple devices, processor(s) <NUM> may provide housed on different devices, and so on.

Bus <NUM> represents what may be one or more busses (such as an address bus, data bus, or a combination thereof). Although the various blocks of <FIG> are shown with lines for the sake of clarity, in reality, delineating various components is not so clear, and metaphorically, the lines would more accurately be grey and fuzzy. For example, one may consider a presentation component such as a display device to be an I/O component. Also, processors have memory. Such is the nature of the art, and the diagram of <FIG> is merely illustrative of an exemplary computing device that can be used in connection with one or more embodiments of the present invention. Distinction is not made between such categories as "workstation," "server," "laptop," "hand-held device," etc., as all are contemplated within the scope of <FIG> and the references herein to a "computing device.

Memory <NUM> may include any of the computer-readable media discussed herein. Memory <NUM> may be used to store and access instructions configured to carry out the various operations disclosed herein. In some examples, memory <NUM> includes computer storage media in the form of volatile and/or nonvolatile memory, removable or non-removable memory, data disks in virtual environments, or a combination thereof.

Processor(s) <NUM> may include any quantity of processing units that read data from various entities, such as memory <NUM> or I/O components <NUM>. Specifically, processor(s) <NUM> are programmed to execute computer-executable instructions for implementing aspects of the disclosure. The instructions may be performed by the processor, by multiple processors within the computing device <NUM>, or by a processor external to the client computing device <NUM>. In some examples, the processor(s) <NUM> are programmed to execute instructions such as those illustrated in the flowcharts discussed below and depicted in the accompanying drawings. Moreover, in some examples, the processor(s) <NUM> represent an implementation of analog techniques to perform the operations described herein. For example, the operations may be performed by an analog client computing device <NUM> and/or a digital client computing device <NUM>.

Presentation component(s) <NUM> present data indications to a user or other device. Exemplary presentation components include a display device, speaker, printing component, vibrating component, etc. One skilled in the art will understand and appreciate that computer data may be presented in a number of ways, such as visually in a graphical user interface (GUI), audibly through speakers, wirelessly between computing devices <NUM>, across a wired connection, or in other ways.

Ports <NUM> allow computing device <NUM> to be logically coupled to other devices including I/O components <NUM>, some of which may be built in. Example I/O components <NUM> include, for example but without limitation, a microphone, keyboard, mouse, joystick, game pad, satellite dish, scanner, printer, wireless device, etc..

In some examples, the network component <NUM> includes a network interface card and/or computer-executable instructions (e.g., a driver) for operating the network interface card. Communication between the computing device <NUM> and other devices may occur using any protocol or mechanism over any wired or wireless connection. In some examples, the network component <NUM> is operable to communicate data over public, private, or hybrid (public and private) using a transfer protocol, between devices wirelessly using short range communication technologies (e.g., near-field communication (NFC), BLUETOOTH® branded communications, or the like), or a combination thereof.

Although described in connection with an example computing device <NUM>, examples of the disclosure are capable of implementation with numerous other general-purpose or special-purpose computing system environments, configurations, or devices. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with aspects of the disclosure include, but are not limited to, smart phones, mobile tablets, mobile computing devices, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, gaming consoles, microprocessor-based systems, set top boxes, programmable consumer electronics, mobile telephones, mobile computing and/or communication devices in wearable or accessory form factors (e.g., watches, glasses, headsets, or earphones), network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, virtual reality (VR) devices, holographic device, and the like. Such systems or devices may accept input from the user in any way, including from input devices such as a keyboard or pointing device, via gesture input, proximity input (such as by hovering), and/or via voice input.

By way of example and not limitation, computer readable media comprise computer storage media and communication media. Computer storage media include volatile and nonvolatile, removable and non-removable memory implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or the like. Computer storage media are tangible and mutually exclusive to communication media. Computer storage media are implemented in hardware and exclude carrier waves and propagated signals. Computer storage media for purposes of this disclosure are not signals per se. Exemplary computer storage media include hard disks, flash drives, solid-state memory, phase change random-access memory (PRAM), static random-access memory (SRAM), dynamic random-access memory (DRAM), other types of random-access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disk read-only memory (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device. In contrast, communication media typically embody computer readable instructions, data structures, program modules, or the like in a modulated data signal such as a carrier wave or other transport mechanism and include any information delivery media.

Some examples herein are described as performing certain operations via "iteration," "iterative computing," and other variations of such language. Iteration refers to repeatedly performing the same operation or set of operations upon each object in a set of objects until the operation or set of operations has been performed upon every object in the set of objects. It should be understood that, unless explicitly stated otherwise, iteration over a set of objects can be done either sequentially (e.g.: operate on A; then B; then C; then D) or concurrently (e.g.: operate on A and B simultaneously; then operate on C and D simultaneously). Concurrent iteration can process as many objects at once as an example operating environment practicably allows.

Sequential iteration is most suitable to examples where only a single processor is available to perform operations and/or the computing environment does not support multi-threaded computation. Concurrent iteration is most suitable to examples where more than one processor is available to perform operations and/or the computing environment does support multi-threaded (also referred to as parallel) computation. Concurrent iteration exhibits considerable performance advantages over sequential iteration, especially when working with large data sets.

Examples are given herein, in both this Detailed Description and the Drawings, utilizing sequential iteration so that the Detailed Description and Drawings facilitate both full understanding of the disclosure and the greatest possible clarity. No portion of this disclosure expresses, nor is any portion of this disclosure intended to express, that only sequential iteration or concurrent iteration is usable for any particular instance of iteration herein. The use of sequential iteration in the Drawings does not express a preference for sequential iteration over concurrent iteration. No such preference exists-examples of the disclosure should implement whatever type of iteration is most suited to the example's intended application.

Claim 1:
A system for complexity reduction of object via cavity removal, the system comprising:
a processor (<NUM>); and
a computer-readable medium (<NUM>) storing instructions that are operative when executed by the processor to:
determine voxels on an initial exterior boundary of a first object in a voxel space (<NUM>);
generate a distance field, outward from the initial exterior boundary of the first object (<NUM>);
determine voxels having a local maximum of the distance field (<NUM>);
determine a largest local maximum value from among the local maxima (<NUM>), wherein the determination of local maxima excludes voxels on an outer edge of the voxel space (<NUM>);
remove, from the distance field, voxels having a distance field value greater than the largest local maximum value (<NUM>);
for a current distance field value, iterate downward from the largest local maximum value (<NUM>) to:
remove, from the distance field, voxels having a distance field value equal to the current distance field value (<NUM>);
flag, as being in an interior region, voxels removed from the distance field that are contiguous, through other voxels removed from the distance field, with a voxel having a local maximum (<NUM>); and
flag, as being in an exterior region, voxels removed from the distance field that are contiguous, through other voxels removed from the distance field, with a voxel on an outer edge of the voxel space (<NUM>);
determine whether a voxel is flagged as both in an interior region and in an exterior region (<NUM>);
based at least on a voxel being flagged as both in an interior region and in an exterior region, flag the voxel as an added boundary voxel (<NUM>);
determine an adjusted exterior boundary as the initial exterior boundary of the first object and any added boundary voxels (<NUM>); and
generate a reduced-complexity object for processing by floodfilling voxels up through the adjusted exterior boundary (<NUM>).