Techniques for improved progressive mesh compression

An encoder includes a processor and a memory. The encoder generates a first plurality of levels of detail (LODs) and associated first type of vertex split records, each of the first type of vertex split records associated with an LOD of the first plurality of LODs is generated using a first type of collapse operator. The encoder initiates a switch from using the first type of collapse operator to a second type of collapse operator in response to a switching condition being satisfied. The encode further a second plurality of LODs and associated second type of vertex split records, each of the second type of vertex split records associated with a LOD of the second plurality of LODs is generated using the second type of collapse operator.

FIELD

This application relates, generally, to mesh compression, and specifically, to progressive mesh compression.

BACKGROUND

Progressive mesh compression is the encoding of mesh geometry in stages with each stage generating an improved precision related to mesh connectivity, positions, and other attributes. As each stage results in a better level of detail (LOD) of the compressed model, encoding of the next level takes advantage of the information already contained in the previous level. This is relevant for transmitting high resolution models via the Internet as the user on the receiving end (e.g., a client, a client device, or an application) does not have to wait until the entire model is received from the server. The client can quickly display lower resolution levels of the model before all the information is received at the client device.

SUMMARY

In one aspect, a method includes a computer-implemented method of progressive mesh compression. The method includes generating a first plurality of levels of detail (LODs) and associated first type of vertex split records, each of the first type of vertex split records associated with an LOD of the first plurality of LODs is generated using a first type of collapse operator, switching from using the first type of collapse operator to a second type of collapse operator in response to a switching condition being satisfied, and generating, based on the switching, a second plurality of LODs and associated second type of vertex split records, each of the second type of vertex split records associated with a LOD of the second plurality of LODs is generated using the second type of collapse operator.

In another aspect, an encoder includes a processor and a memory. The memory includes instructions configured to cause the processor to perform operations. The operations include to generate a first plurality of levels of detail (LODs) and associated first type of vertex split records, each of the first type of vertex split records associated with an LOD of the first plurality of LODs is generated using a first type of collapse operator, switch from using the first type of collapse operator to a second type of collapse operator in response to a switching condition being satisfied, and generate, based on the switching, a second plurality of LODs and associated second type of vertex split records, each of the second type of vertex split records associated with a LOD of the second plurality of LODs is generated using the second type of collapse operator.

In a further additional aspect, a non-transitory computer-readable storage medium having stored thereon computer executable program code which, when executed on a computer system, causes the computer system to perform operations. The operations include generating a first plurality of levels of detail (LODs) and associated first type of vertex split records, each of the first type of vertex split records associated with an LOD of the first plurality of LODs is generated using a first type of collapse operator, switching from using the first type of collapse operator to a second type of collapse operator in response to a switching condition being satisfied, and generating, based on the switching, a second plurality of LODs and associated second type of vertex split records, each of the second type of vertex split records associated with a LOD of the second plurality of LODs is generated using the second type of collapse operator.

It should be noted that these Figures are intended to illustrate the general characteristics of methods, structure, or materials utilized in certain example implementations and to supplement the written description provided below. These drawings are not, however, to scale and may not precisely reflect the precise structural or performance characteristics of any given implementation, and should not be interpreted as defining or limiting the range of values or properties encompassed by example implementation. The use of similar or identical reference numbers in the various drawings is intended to indicate the presence of a similar or identical element or feature.

DETAILED DESCRIPTION

An example improved (or enhanced) progressive mesh compression mechanism is described herein. In one implementation, an encoder (for example, at a server) may process an input mesh and generate a LOD and associated vertex split records. The processing of the input mesh includes processing a batch of edge collapse operators. The generating of the LOD includes generating a coarser mesh and associated vertex split records. The vertex split records are used by a decoder (e.g., a client, a user device, a browser application, etc.) for decoding and/or re-constructing the mesh, for example, for displaying at the client. In one implementation, the enhanced progressive mesh compression may include, for example, 60 LODs and 500,000 vertices (for the highest level LOD).

A batch of edge collapse operators may include either full-edge collapse operators or half-edge collapse operators. For example, a first batch of edge collapse operators may contain a plurality (e.g., 5,000) of full-edge collapse operators and a second batch of edge collapse operators may contain a plurality (e.g., 7,000 etc.) of half-edge collapse operators. The number of collapse operators in a batch, as described above, is just an example, and a batch may include any number of collapse operators for compressing an input mesh. Although the type of collapse operators in a batch may be full-edge or half-edge collapse operators, the proposed improved progressive mesh compression focuses on a batch of collapse operators containing either full-edge collapse operators or half-edge collapse operators. In a progressive mesh compression, different LODs may be created by collapsing (or decimating) a mesh (e.g., an input mesh) with successive batches of edge collapse operators until a very coarse mesh is generated. For each batch of edge collapse operators, an independent set of edges may be selected from a priority queue and collapsed.

An encoder may process an input mesh and generate a plurality of LODs and associated vertex split records. In one example implementation, the encoder may process the input mesh using a batch of first type of collapse operators and generate a LOD and associated first type of vertex split records. For instance, the encoder may process an input mesh using a first batch of collapse operators and generate a LOD1and associated first type of vertex split records (VSR1). The encoder may continue with the progressive mesh compression and may process LOD1as input mesh using a second batch of first type of collapse operators. A LOD2and associated first type of vertex split records (VSR2) are generated. The generating of the LODs and associated first type of vertex split records may continue until a switching is triggered for switching the collapse operator from a first type of collapse operator to a second type of collapse operator or a coarsest LOD and associated first type of vertex records are generated.

The encoder may include a switching module which may trigger (or generate) a message (or some kind of indicator) to initiate a switch from the first type of collapse operator to a second type of collapse operator. That is, the switching module may trigger a message to initiate a switch so that a second type of edge collapse operator is used to collapse edges. In some implementations, the switching module may monitor the progressive mesh compression and may trigger the switching in response (or based on) a switching condition being satisfied. For example, the switching condition may be based on a user defined parameter, error threshold, or a combination thereof.

The encoder, after the switching, may continue with generating of a plurality of LODs and associated second type of vertex split records. In one implementation, the encoder may use a batch of second type of collapse operators and generate a LOD and associated second type of vertex split records. For example, the encoder may process the input mesh, which may be the mesh that was generated immediately preceding the mesh being currently generated (for example, LOD2), using a second batch of collapse operators and generate a LOD (e.g., LOD3) and associated second type of vertex split records (VSR3). After the generating of the LOD3and VSR3, the encoder may continue with the progressive mesh compression and continue with generating the LODs and associated second type of vertex split records. For example, the encoder may use LOD3as the input mesh and generate a LOD4and associated second type of vertex split records (VSR4), and continue with generating LOD5and VSR5using LOD4as the input mesh. The generating of the LODs and the associated second type of vertex split records may continue until a switching (e.g., to the first type of collapse operator) is triggered.

As described above in reference to the switching module initiating a switch from the first type of collapse operator to the second type of collapse operator, in one example implementation, the switching module may trigger a switch from the second type of collapse operator to the first type of collapse operator if a switching condition is satisfied. The switching condition for switching from the second type of collapse operator to the first type of collapse operator may be the same switching condition that is used to initiate a switch from the first type of collapse operator to the second type of collapse operator. However, in some example implementations, the switching conditions may be different, and may be user defined or based on different error thresholds.

The encoder may transmit a LOD and associated vertex split records to a decoder (e.g., decoder at a client). The transmission of a LOD and associated vertex split records may be based on a message received from the decoder. In one example implementation, the encoder may send the lowest resolution level LOD (e.g., LOD5) and associated vertex split records (e.g., VSR5) and vertex split records up until the highest requested LOD based on the message received from the decoder. The transmission of the associated vertex split records is incremental and does not have to be transmitted together (e.g., may be transmitted separately). The decoder may be interested in the next level LOD (e.g., LOD at a better resolution level) when the decoder needs the LOD for processing or displaying at the client (e.g., client device, browser application, etc.). In other words, the decoder may want the next level LOD and the encoder transmits the associated vertex split records associated with the next level LOD. In the improved progressive mesh compression being described herein, the LOD and associated vertex split records are transmitted in an order (from a resolution level perspective) that is opposite to the order they are generated. That is, the lowest resolution level LOD and associated vertex split records are transmitted first, depending on the message received from the decoder, and followed by vertex split records for higher level LODs and all the way up to the highest level LOD.

The improved progressive mesh compression described herein provides for progressive mesh compression by balancing quality (e.g., distortion) and cost (e.g., bit-rate or bits per vertex). That is, the improved progressive mesh compression balances distortion and bit-rate by switching between the first and second type of collapse operators (or vice versa). For example, in one example implementation, the improved progressive mesh compression may be performed by starting the progressive mesh compression with 30% of half-edge collapse operators followed by 70% of full-edge collapse operators. This may generate a progressively compressed mesh of same or similar quality with reduction in bit-rate (e.g., an estimated 18% reduction in bit-rate in one implementation). Thus, the improved progressive mesh compression provides for an efficient (e.g., faster) transmission of a LOD and associated vertex split records (from an encoder to a decoder) by allowing the decoder display the lower resolution level model quickly or display a model of higher resolution level at a given time that would otherwise would not be possible.

FIG. 1Aillustrates a portion of a geometric model100being compressed using a first type of edge collapse operators.

InFIG. 1A, area102of the geometric model100represents an area which may be compressed using an improved progressive mesh compression. In one example implementation, the area102may be compressed using a first type of collapse operator. The first type of collapse operator may be a half-edge collapse operator (described in detail in reference toFIG. 2A) or a full-edge collapse operator (described in detail in reference toFIG. 2B). As described above, the progressive mesh compression may generate a LOD and associated first type of vertex split records. The LOD and the associated first type of vertex split records may be generated by collapsing an input mesh with successive batches (e.g. one or more batches) of first type of edge collapse operators until reaching a very coarse mesh. During the improved progressive mesh compression, for each batch of the first type of edge collapse operators, an independent set of edges may be selected from a priority queue and collapsed. In one implementation, based on a specific error metric, each candidate edge in the priority queue may be associated with a weight corresponding to the increase of the error induced by its collapse.

The LODs and associated vertex split records may be generated using one type of edge collapse operators throughout the whole edge collapse process. However, such generation using one type of edge collapse operators may not be efficient or meet quality expectations. For instance, the use of the full-edge collapse operator throughout the whole edge collapse process may generate, upon decoding by a decoder on the receiving end, a higher-quality geometric model. But, a higher amount of data has to be transmitted, for example, from the encoder to the decoder. The proposed improved progressive mesh compression uses at least two types of edge collapse operators for generating LODs and associated vertex split records. The two types of edge collapse operators may be full-edge and half-edge collapse operators.

FIG. 1Billustrates a portion of a geometric model150being compressed using a second type of edge collapse operator.

InFIG. 1B, area152of the geometric model150represents an area which may be compressed using an improved progressive mesh compression. In one example implementation, the area152may be compressed using a second type of edge collapse operator. The second type of edge collapse operator may be a full-edge collapse operator (described in detail in reference toFIG. 2A) or a half-edge collapse operator (described in detail in reference toFIG. 2B). That is, the first and second types of edge collapse operators are different (not the same type of edge collapse operators).

The LODs and the associated second type of vertex split records may be generated by collapsing an immediately preceding mesh with successive batches (e.g. one or more batches) of second type of edge collapse operators until reaching a very coarse mesh. During the improved progressive mesh compression, for each batch of the second type of edge collapse operators, an independent set of edges may be selected from a priority queue and collapsed. In one implementation, based on a specific error metric, each candidate edge in the priority queue may be associated with a weight corresponding to the increase of the error induced by its collapse.

FIG. 2Aillustrates an example collapsing of edges200using a full-edge collapse operator, according to at least one example implementation.

InFIG. 2A, two vertices (202and210) connected by an edge (206) are collapsed using a full-edge collapse operator. In such a full-edge collapse operation, the two vertices (202and210) are merged and a new vertex218is generated. The location of the new vertex218is determined by minimizing the local error. However, this may result in requiring higher number of bits for encoding the two residuals between the merged vertex and its two ancestors to reverse the full-edge collapse operator during the decoding. As the newly merged vertex218is being generated, edges204and208are collapsed into edge216and edges222and224are collapsed into edge226. As illustrated inFIG. 2A, new edge216is generated by merging edges204and208and new edge226is generated by merging edges222and226. The merging of two vertices and the collapsing of edges generates a LOD and associated vertex split records. The vertex split records are used by the decoder to decode or re-construct the model.

FIG. 2Billustrates an example collapsing of edges250using a half-edge collapse operator, according to at least one example implementation.

InFIG. 2B, two vertices (252and256) connected by an edge (254) are collapsed using a half-edge collapse operator. In such a collapse operation, one of the vertices, for example, vertex256, is moved/merged into the vertex252. This will result in generating data related to the vertex256as the position of the other vertex252has not changed. In other words, in the half-edge collapse operator operation, the merged vertex is restricted to be located at one of its two ancestors. While the local error may be larger than in the full-edge collapse operator operation, only one residual vector has to be decoded to reverse the operator during decoding (e.g., by subsampling the mesh vertices instead of resampling). This may result in requiring lower number of bits for representing the information but the distortion rate may be higher (e.g., more distorted lower LODs).

FIG. 3illustrates a block diagram of an encoder300for an improved progressive mesh compression.

As shown inFIG. 3, the example processing system300may include at least one processor342, at least one memory344, a controller346, and/or an encoder302. The at least one processor342, the at least one memory344, the controller346, and/or the encoder302may be communicatively coupled via bus348.

The processor342may be utilized to execute instructions stored in the memory344, so as to thereby implement the various features and functions described herein, or additional or alternative features and functions. The processor342and the memory344may be utilized for various other purposes. For example, the memory344may represent an example of various types of memory and related hardware and software, or a combination thereof, which may be used to implement any one of the components or modules described herein.

The memory344may be configured to store data or information associated with the processing system300. For example, the memory344may be configured to store codecs (e.g., encoder302), meshes or information related to meshes (e.g., input mesh304, LODs, vertex split records), and any other associated or related data for enhancing the progressive mesh compression. The memory344may be a shared resource. For example, the processing system300may be an element of a larger system (e.g., a server, a personal computer, a mobile device, and the like). Therefore, the memory344may be configured to store data or information associated with other elements (e.g., image/video serving, web browsing, or wired/wireless communications) within the larger system.

The controller346may be configured to generate various control signals and communicate the control signals to various blocks of the processing system300. The controller346may be configured to generate the control signals to implement the techniques (e.g., mechanisms, procedures, etc.) described herein. The controller346may be configured to control the encoder302to a mesh (e.g., input mesh304), and the like according to example implementations or aspects. For example, the controller346may generate control signals corresponding to parameters to implement an encoding mechanism (e.g., improved progressive mesh compression).

In one implementation, the encoder302may include a first collapsing module310and a second collapsing module320for performing an improved progressive mesh compression. For example, the first collapsing module310may be configured to receive (e.g., read) an input mesh (e.g., input mesh304) and process the input mesh304using a first type of edge collapse operator312. That is, the first collapsing module310runs (or executes) a batch of first type of collapse operators and generates a LOD314(of a first plurality of LODs) and associated first type of vertex split records316. The LOD314and first type of vertex split records316may be stored in the memory344. As shown inFIG. 3, the first collapsing module310may process a plurality of batches and generate a first plurality of LODs and associated first type of vertex split records (each LOD has its own associated vertex split records).

The generating of the first plurality of LODs and the associated first type of vertex split records may continue until a switching is initiated by the switching module330. The switching module330may initiate a switching, from one type of collapse operator to another type of collapse operator, when a switching condition is satisfied. The switching condition may be based at least on one of a user-defined parameter, error threshold (during collapsing), or based at least on identifying a branching point. In one implementation, for example, the encoder, to identify the branching point (or the optimum point for switching) may offload the processing of the batches to other servers to determine the optimal switching point. For instance, all possible switching scenarios are evaluated by other servers offline in a distributed environment (e.g., cloud) and the optimal switching location notified to the switching module330.

The second collapsing module320, upon switching to the second type of collapse operators, may process the immediately preceding LOD and generate a LOD (of the second plurality of LODs324) and associated second type of vertex split records326. The second collapsing module320may retrieve the input mesh from the memory344. The input mesh for the second collapsing module320may be the immediately preceding mesh (e.g., LOD2) that has been generated and stored in the memory344. The LOD and the second type of vertex split records are then stored in the memory344.

FIG. 4illustrates a flowchart400of a method of an improved progressive mesh compression according to least one example implementation.

At block410, the encoder302and/or the first collapsing module310may generate a first plurality of levels of detail (LODs) and associated first type of vertex split records, each of the first type of vertex split records associated with an LOD of the first plurality of LODs is generated using a first type of collapse operator. For example, in one implementation, the encoder302and/or or the first collapsing module310may generate a first plurality of LODs and associated first type of vertex split records, e.g., LOD1(314) and VSR1(316); and LOD2(315) and VSR2(317). The vertex split records VSR1(316) and VSR2(317) are generated using the first type of collapse operator312. In one implementation, the first type of collapse operator312may be a half-edge collapse operator or a full-edge operator.

At block410, the encoder302and/or the switching module330may switch from using the first type of collapse operator to a second type of collapse operator in response to a switching condition being satisfied. For example, in one implementation, the encoder302and/or or the switching module330may, in response to a switching condition being satisfied, switch from using a first type of collapse operator to a second type of collapse operator. In one example, implementation, the switching may be from the first to the second type of edge collapse operator or from the second to the first type of edge collapse operator.

At block430, the encoder302and/or the second collapsing module320may generate, based on the switching, a second plurality of LODs and associated second type of vertex split records, each of the second type of vertex split records associated with a LOD of the second plurality of LODs is generated using the second type of collapse operator. For example, in one implementation, the encoder302and/or or the second collapsing module320may generate a second plurality of LODs and associated second type of vertex split records, e.g., LOD3(324) and VSR3(326); LOD4(325) and VSR4(327); LOD5(328) and VSR5(329). The vertex split records (VSR3, VSR4, and VSR5) are generated using the second type of collapse operator322. In one implementation, the second type of collapse operator322may be a full-edge operator or a half-edge collapse operator. In other words, the first type of collapse operator is different from the second type of collapse operator.

Alternatively, at block440, the encoder302may, in response to a message received from a decoder, transmit a LOD of the first plurality of LODs and associated first type of vertex split records or a LOD of the second plurality of LODs and associated second type of vertex split records. For example, in one implementation, the encoder302may transmit LOD5(328) and VSR5(329) in response to a message received from a decoder. In another example implementation, the encoder302may transmit LOD5(328) and VSR4(327) in response to a message received from a decoder. In some other example implementations, the LOD may be a lowest LOD being requested from the decoder, and the vertex split records include vertex split records associated with the lowest LOD and vertex split records associated with LODs up to a highest LOD. In other words, the client may request the next LOD, but the encoder may send the vertex split records associated with the next LOD. In some more example implementations, the encoder may send vertex split records associated with LODs up to the highest LOD.

The improved progressive mesh compression mechanism provides for progressive mesh compression by balancing quality (e.g., distortion) and cost (e.g., bit-rate or bits per vertex). That is, the improved progressive mesh compression mechanism balances distortion and bit-rate by switching between the first and second type of collapse operators (or vice versa). For example, in one example implementation, improved progressive mesh compression may be performed by starting the progressive compression mechanism with 30% of half-edge collapse operator followed by 70% of full-edge collapse operators. This may provide for a compressed mesh of same or similar quality with an estimated 18% reduction in bit-rate. Thus, the improved progressive mesh compression provided for an efficient (e.g., faster) transmission of LODs and associated vertex split records (from an encoder to a decoder) by enabling the decoder display the lower resolution level model quickly or display a model of higher resolution level that would otherwise would not be possible.

FIG. 5shows an example of a computer device500and a mobile computer device550, which may be used with the techniques described here. Computing device500is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. Computing device550is intended to represent various forms of mobile devices, such as personal digital assistants, cellular telephones, smart phones, and other similar computing devices. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

The processor552can execute instructions within the computing device550, including instructions stored in the memory564. The processor may be implemented as a chipset of chips that include separate and multiple analog and digital processors. The processor may provide, for example, for coordination of the other components of the device550, such as control of user interfaces, applications run by device550, and wireless communication by device550.

The computing device550may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a cellular telephone580. It may also be implemented as part of a smart phone582, personal digital assistant, or other similar mobile device.

Various implementations of the systems and techniques described here can be realized in digital electronic circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which may be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device. Various implementations of the systems and techniques described here can be realized as and/or generally be referred to herein as a circuit, a module, a block, or a system that can combine software and hardware aspects. For example, a module may include the functions/acts/computer program instructions executing on a processor (e.g., a processor formed on a silicon substrate, a GaAs substrate, and the like) or some other programmable data processing apparatus.

Methods discussed above, some of which are illustrated by the flow charts, may be implemented by hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine or computer readable medium such as a storage medium. A processor(s) may perform the necessary tasks.

Specific structural and functional details disclosed herein are merely representative for purposes of describing example embodiments. Example embodiments, however, be embodied in many alternate forms and should not be construed as limited to only the embodiments set forth herein.

It will be understood that when an element is referred to as being connected or coupled to another element, it can be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being directly connected or directly coupled to another element, there are no intervening elements present. Other words used to describe the relationship between elements should be interpreted in a like fashion (e.g., between versus directly between, adjacent versus directly adjacent, etc.).

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments. As used herein, the singular forms a, an, and the are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms comprises, comprising, includes and/or including, when used herein, specify the presence of stated features, integers, steps, operations, elements and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components and/or groups thereof

In the above illustrative implementations, reference to acts and symbolic representations of operations (e.g., in the form of flowcharts) that may be implemented as program modules or functional processes include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types and may be described and/or implemented using existing hardware at existing structural elements. Such existing hardware may include one or more Central Processing Units (CPUs), digital signal processors (DSPs), application-specific-integrated-circuits, field programmable gate arrays (FPGAs) computers or the like.

While example implementations may include various modifications and alternative forms, implementations thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit example implementations to the particular forms disclosed, but on the contrary, example implementations are to cover all modifications, equivalents, and alternatives falling within the scope of the claims. Like numbers refer to like elements throughout the description of the figures.