WO2010121085A1 - Scalable particle interactive networks - Google Patents

Abstract

Scalable Particle Interactive Network (SPIN) graphics technologies are disclosed, which use a particle -based approach to represent, generate, model, encode, perform volumetric model recognition, and render volumetric models, among other unique improvements in the graphics field. The particle-based approach can preserve surface and volumetric information, in addition to other properties of volumetric models. The particle-based approach is suited for both static and evolving volumetric models, allows for adaptive reconstruction of the level-of-detail, and is appropriate for rendering in surface-based and volumetric-based systems.

Description

SCALABLE PARTICLE INTERACTIVE NETWORKS

Inventor: DR. IOAN ALEXANDRU SALOMIE, PH.D. Attorney Docket Number: IOAN000201

CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] Priority is claimed to United States Provisional Application 61/169,718, filed April 16, 2009, entitled "SCALABLE PARTICLE INTERACTIVE NETWORKS", which is incorporated by reference in its entirety.

TECHNICAL FIELD

[0002] This disclosure relates to the field of computer graphics.

BACKGROUND

[0003] Computer graphics technologies have become important to a wide range of industries. In the medical industry, sophisticated graphics are used for anatomical modeling for medical research, as well as for everyday patient diagnosis. In the entertainment industry, computer graphics are used intensively for special effects, animated films, and video games. Computer graphics also play an important role in scientific research, engineering, manufacturing, and many more of today's major industries.

[0004] Graphics technologies have evolved rapidly, at least in part due to evolution of computing devices which continue to become more powerful and diverse, and many of which are now small, portable, and equipped for wireless communications. New software applications in the aforementioned industries also drive improvements in graphics technologies. These software applications span a range of functions and purposes, including for example training, entertainment, monitoring, productivity, modeling, virtual reality and/or training simulations, three dimensional (3D) imaging, scientific data analysis, visualization of biological data and processes, real-time volumetric model reconstruction and recognition, computer aided design and manufacturing, and the reconstruction of 3D static or dynamic scenes from multiple camera views or other input data.

[0005] Recent developments in graphics technology, at the time of this writing, include surface representation methods such as the normal meshes disclosed in U.S. Pat. No. 7,129,947 to Schroeder et al., and the hybrid meshes disclosed in U.S. Pat. No. 7,006,088 to Guskov et al., both issued in 2006. Additionally, U.S. Pat. No. 6,982,710 to Salomie, also issued in 2006, discloses advantageous TriScan and MeshGrid techniques. However, there is an ongoing need for further development and improvement in the field of computer graphics. In particular, there is a need for graphics technologies that can effectively generate and manipulate unified volumetric model representations which provide both volumetric properties and surface descriptions in a scalable way, among a variety of other improvements needed in the art.

SUMMARY

[0006] Scalable Particle Interactive Network (SPIN) graphics technologies are disclosed herein. SPIN graphics technologies comprise a graphics model, data structures for representing graphics data according to the graphics model, and systems and methods for authoring, manipulating, encoding/decoding and displaying graphics implementing the graphics model. The SPIN graphics model generally uses particles as building blocks for volumetric models, and includes a variety of additional advances over the state of the art, as described in further detail herein. Data structures for representing graphics data according to the SPIN graphics model reflect the particles of the SPIN graphics model and can be used to represent an infinite range of objects or other scenes, designs or visual information, including for example multi-resolution three-dimensional (3D) objects. Systems and methods for authoring, manipulating, encoding/decoding and displaying graphics implementing the SPIN graphics model include a wide variety of methods, software, computing systems and computer readable media that implement the SPIN graphics model or portions thereof to realize the unique advantages associated with SPIN graphics technologies.

BRIEF DESCRIPTION OF THE DRAWINGS

[0007] The foregoing and other features of the present disclosure will become more fully apparent from the accompanying drawings. These drawings depict several embodiments in accordance with the disclosure and are not to be considered limiting of its scope. In the drawings:

[0008] FIG. 1 illustrates a virtual net populated with particles. The combination of particles represents a SPIN-based volumetric model.

[0009] FIG. 2 illustrates neighbor particles in a SPIN-based volumetric model that touch at shared vertex positions. [0010] FIG. 3 illustrates neighbor particles in a SPIN-based volumetric model that do not touch each other.

[0011] FIG. 4 illustrates a SPIN-based volumetric model in which particles share a plurality of vertices.

[0012] FIG. 5 illustrates the SPIN-based volumetric model of FIG. 4, where certain particle vertex coordinates have been further adjusted.

[0013] FIGS. 6A, 6B, and 6C illustrate increased resolution levels achieved by subdivision of particles into smaller particles.

[0014] FIG. 7 illustrates an example particle with auxiliary vertices as may be involved in a merge operation.

[0015] FIG. 8 illustrates a variety of example particle shapes.

[0016] FIG. 9 illustrates a particle centroid and wireframe views of two particle membranes.

[0017] FIG. 1OA illustrates particles in a virtual net in a hexa-packing mode.

[0018] FIG. 1OB illustrates virtual net points in a cubic-packing mode.

[0019] FIG. 1OC illustrates virtual net points in a hexa-packing mode.

[0020] FIG. 1OD illustrates virtual net points in a cubic-packing mode.

[0021] FIG. 1OE illustrates virtual net points in a hexa-packing mode.

[0022] FIG. 1OF illustrates a cross section of a hexa-packing mode virtual net along a Q axis.

[0023] FIG. 1OG illustrates a cross section of a hexa-packing mode virtual net along a R axis.

[0024] FIG. 1OH illustrates a cross section of a hexa-packing mode virtual net along a S axis.

[0025] FIG. 101 illustrates a cross section of a hexa-packing mode virtual net along a T axis.

[0026] FIG. HA illustrates particles that are neighbor along a single axis in a cubic packing mode.

[0027] FIG. 1 IB illustrates merged particles of FIG. 1 IA.

[0028] FIG. HC illustrates particles that are neighbor along a single axis in a hexa packing mode. [0029] FIG. HD illustrates merged particles of FIG. HC.

[0030] FIG. 12A illustrates particles that are neighbor along a combination of two axes in a cubic packing mode.

[0031] FIG. 12B illustrates merged particles of FIG. 12A.

[0032] FIG. 12C illustrates particles that are neighbor along a combination of two axes in a hexa packing mode.

[0033] FIG. 12D illustrates merged particles of FIG. 12C.

[0034] FIG. 13 A illustrates particles that are neighbor along a combination of three axes in a cubic packing mode.

[0035] FIG. 13B illustrates merged particles of FIG. 13 A.

[0036] FIG. 13C illustrates particles that are neighbor along a combination of three axes in a hexa packing mode.

[0037] FIG. 13D illustrates merged particles of FIG. 13C.

[0038] FIG. 14A illustrates a spherical shaped particle in a radial triangulation mode.

[0039] FIG. 14B illustrates a spherical shaped particle in a transversal triangulation mode.

[0040] FIG. 15A illustrates a cube shaped particle in a radial triangulation mode, as may be obtained by adjusting the coordinates of the particle of FIG. 14A.

[0041] FIG. 15B illustrates a cube shaped particle in a transversal triangulation mode, as may be obtained by adjusting the coordinates of the particle of FIG. 14B.

[0042] FIGS. 16A-16C illustrate vertices of a various types.

[0043] FIGS. 17A-17F illustrate connecting and merging of neighbor particles, and adjusting vertices.

[0044] FIG. 18A illustrates example operations modules for performing operations on particles.

[0045] FIG. 18B illustrates example region operations modules.

[0046] FIG. 19 illustrates a particle interconnection network, and may also be used to describe a region nesting network.

[0047] FIG. 20 illustrates a particle lineage network, and may also be used to describe a region lineage network.

[0048] FIGS. 21A-21E illustrate example intermediate steps of morphing from a 3D spherically shaped particle to a 2D planar membrane and then to a ID linear membrane. [0049] FIGS. 22A-22B illustrate non-planar particle cross sections as may be obtained by collapsing vertices toward the target cross section.

[0050] FIGS. 23A-23B illustrate non-planar particle cross sections as may be obtained by collapsing vertices toward the target cross section.

[0051] FIG. 24A illustrates a spherical shaped particle at a first precision level.

[0052] FIG. 24B illustrates a cube shaped particle at a first precision level.

[0053] FIG. 25A illustrates a spherical shaped particle at a second precision level, obtained by subdividing the particle membrane surface mesh illustrated in FIG. 24A.

[0054] FIG. 25B illustrates a cube shaped particle at a second precision level, obtained by subdividing the particle membrane surface mesh illustrated in FIG. 24B.

[0055] FIG. 26A illustrates a spherical shaped particle at a third precision level, obtained by subdividing the particle membrane surface mesh illustrated in FIG. 25A.

[0056] FIG. 26B illustrates a cube shaped particle at a third precision level, obtained by subdividing the particle membrane surface mesh illustrated in FIG. 25B.

[0057] FIGS. 27A-27B illustrate deformation of a spherically shaped particle in radial mode to a hyperoctahedron.

[0058] FIGS. 28A-28B illustrate deformation of a spherically shaped particle in transversal mode to a hyperoctahedron.

[0059] FIGS. 29A-29B illustrate subdivision of the particles illustrated in FIGS. 27A-27B, increasing resolution level in a cubic packing mode.

[0060] FIGS. 29C-29D illustrate subdivision of the particles illustrated in FIGS. 27A- 27B, increasing resolution level in a hexa packing mode.

[0061] FIGS. 30A-30B illustrate subdivision of the particles illustrated in FIGS. 28A-28B increasing resolution level in a cubic packing mode.

[0062] FIGS. 30C-30D illustrate subdivision of the particles illustrated in FIGS. 28A-28B increasing resolution level in a hexa packing mode.

[0063] FIG. 31 A illustrates a front view of the particles of FIGS. 29A or 3OA, in a uniformly distributed cubic packing mode virtual net.

[0064] FIG. 3 IB illustrates a front view of the particles of FIGS. 29B or 3OB, in a non- uniformly distributed cubic packing mode virtual net. [0065] FIG. 32A illustrates the uniformly distributed cubic packing mode virtual net from FIG. 31 A without the particles.

[0066] FIG. 32B illustrates the non-uniformly distributed cubic packing mode virtual net from FIG. 3 IB without the particles.

[0067] FIG. 33A illustrates a front view of the particles of FIGS. 29C or 3OC, in a uniformly distributed hexa packing mode virtual net.

[0068] FIG. 33B illustrates a front view of the particles of FIGS. 29D or 30D, in a non- uniformly distributed hexa packing mode virtual net.

[0069] FIG. 34A illustrates the uniformly distributed hexa packing mode virtual net from FIG. 33 A without the particles.

[0070] FIG. 34B illustrates the non-uniformly distributed hexa packing mode virtual net from FIG. 33B without the particles.

[0071] FIG. 35 illustrates transformation between a set of particles at a first resolution level and a set of particles at a second resolution level.

[0072] FIGS. 36A-36F illustrate 2D views of an example distribution of samples at 5 different resolution levels.

[0073] FIGS. 37A-37F illustrate views corresponding to FIGS. 36A-36F, wherein at least one of FIGS. 36A-36F is modified to produce a corresponding distribution in FIG. 37, triggering update of the remaining views of FIG. 37.

[0074] FIG. 38 illustrates an example multi-resolution data set.

[0075] FIG. 39 illustrates modification of the multi-resolution data set from FIG. 38 in a resolution-level isolation mode.

[0076] FIG. 40 illustrates modification of the multi-resolution data set from FIG. 38 in a downward update isolation mode.

[0077] FIG. 41 illustrates modification of the multi-resolution data set from FIG. 38 in a upward update isolation mode.

[0078] FIG. 42 illustrates modification of the multi-resolution data set from FIG. 38 in a default mode, followed by subsequent modification in which upward update is enabled and downward update is disabled.

[0079] FIG. 43 illustrates a cubical region of a 3D distribution of SPIN samples.

[0080] FIG. 44 illustrates an extension of FIG. 43 with a details component. [0081] FIGS. 45A-45B illustrate updated positions of ancestor samples from FIGS. 43-44.

[0082] FIG. 46 illustrates example operations of setup modules.

[0083] FIG. 47 illustrates example operations of reconstruction modules.

[0084] FIG. 48 illustrates example operations of multi-resolution upgrade modules.

[0085] FIG. 49 illustrates example operations of multi-resolution optimization modules.

[0086] FIG. 50 illustrates example operations of multi-resolution optimization modules to describe a SPIN-based volumetric model in a multi-resolution fashion using a multi-resolution optimized virtual net.

[0087] FIG. 51 illustrates example operations of multi-resolution optimization modules.

[0088] FIG. 52 illustrates example operations of multi-resolution upgrade modules.

[0089] FIG. 53 illustrates example operations of freeform modeling modules.

[0090] FIG. 54 illustrates an example computing system.

[0091] FIG. 55 illustrates example SPIN modules as may be recorded on a computer readable medium and/or implemented in a computing system.

[0092] FIG. 56 illustrates a technique for determining average particle size given a maximum reconstruction error of a volumetric model.

DETAILED DESCRIPTION

[0093] In the following detailed description, reference is made to the accompanying drawings, which form a part hereof. In the drawings, similar symbols typically identify similar components, unless context dictates otherwise. The illustrative embodiments described in the detailed description, drawings, and claims are not meant to be limiting. Other embodiments may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented here. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, and designed in a wide variety of different configurations, all of which are explicitly contemplated and made part of this disclosure.

[0094] A SPIN graphics model, also referred to as a particle -based graphics model, is described herein, along with a variety of systems, methods, operations, data structures, examples, and/or articles implementing or otherwise related to the SPIN graphics model. Computing technologies may implement aspects of the disclosed SPIN graphics model in a variety of ways as will be appreciated with the benefit of this disclosure. For example, in some embodiments, computer systems may be configured to allow authoring graphics according to a SPIN graphics model, and/or rendering (displaying) graphics that utilize the SPIN graphics model. In general, a computing device may be configured to process particle-based volumetric models, where processing comprises one or more of automatically or interactively creating, encoding, decoding, storing, loading, modifying, animating, and/or displaying particle-based volumetric models. An example computer is described with reference to FIG. 54. A computer may be equipped with a variety of software and/or hardware. For example, a computer may comprise a Graphics Processing Unit (GPU) or other processing unit configured to render a graphical image by loading and executing graphics processing modules that implement aspects of the SPIN graphics model, such as the various spin modules 4523 as illustrated in FIG. 55 and which are referenced throughout this specification.

[0095] In another example, the SPIN graphics model may be implemented in software which may be stored as computer executable instructions on a computer-readable medium. For example, software for use in health care industries may implement the SPIN graphics model to allow users of the software to create, view, and edit interactive anatomical images of organisms, including for example bones, organs, skin, and so on. Moreover, software used in scientific data manipulation, CAD, computer games and entertainment, 3D video, and virtual reality simulators may implement the SPIN graphics model.

[0096] In another example, the SPIN graphics model may be implemented in data structures stored on a computer readable medium. For example, data structures encoding data corresponding to graphical images that are authored and/or rendered according to the SPIN graphics model may be provided.

Overview of the SPIN Graphics Model

[0097] The following paragraphs provide an overview of the SPIN graphics model.

[0098] The SPIN graphics model generally uses particles as building blocks for SPIN- based volumetric models. Example particles may comprise elements such as, a particle centroid, particle vertices, and particle surfaces, also referred to as membranes. Locations of the particle elements can be defined with reference to a virtual net which may comprise for example a 3D grid. Particles can take an infinity of shapes and sizes. [0099] FIG. 1 illustrates a virtual net 131 comprising a plurality of virtual net points 132. A virtual net 131 may be populated with one or more particles 130. The combination of particles 130 forms a SPIN-based volumetric model. In some embodiments, a particle 130 may be inserted at any virtual net point 132. Also, in some embodiments, the centroid of the particle may overlap with a virtual net point, and also it may be attached to a virtual net point, such that when the virtual net point moves, the particle's centroid also moves with it, as described herein. While FIG. 1 and the description provided herein generally contemplates 3D volumetric models, it will be appreciated that the disclosed teachings are applicable to volumetric models in any number of dimensions ranging from 2 D and above.

[0100] FIG. 2 illustrates a SPIN-based volumetric model comprising a plurality of particles 130A, 130B, and 130C. Particles 130A, 130B, and 130C may comprise predefined numbers of vertices such as, for example vertices 134A, 134B, 135A, 135B, and 135C. Vertices are points on a surface of a particle, indicated by wireframe intersections in FIG. 2. Vertices may be shared as in the case of vertices 134, or vertices may not be shared as in the case of vertices 135. Particles 130A and 130B are neighbor particles touching at shared vertex 134A. Particles 130B and 130C are neighbor particles touching at shared vertex 134B.

[0101] FIG. 3 illustrates a SPIN-based volumetric model comprising a plurality of particles 130A, 130B, and 130C. Particles 130A and 130B are neighbor particles, however particles 130A and 130B do not touch at a shared vertex in the SPIN-based volumetric model of FIG. 3. Similarly, neighbor particles 130B and 130C do not touch at a shared vertex in FIG. 3. Neighbor particles need not necessarily touch each other.

[0102] FIG. 4 illustrates a SPIN-based volumetric model in which particles such as the various neighbor particles illustrated in FIGS. 1-3 share a plurality of vertices. Neighbor particles sharing vertices may be described herein as "merged" particles. By further adjusting coordinates of vertices in FIG. 4, the SPIN-based volumetric model in FIG. 5 may be obtained. FIG. 4 also illustrates that a SPIN-based volumetric model may be described using regions such as region 401 and region 402.

[0103] In some embodiments, neighbor particles may connect and merge through shared vertices. A vertex sharing configuration may specify which vertices are designated as shared vertices. Even when a vertex sharing configuration does not support connecting and/or merging of two or more particles, particles may still intersect arbitrarily, as necessary to provide the desired visual effects.

[0104] FIGS. 6 A, 6B, and 6C illustrate subdivision of particles into smaller particles, allowing for increased resolution levels. FIG. 6B comprises a similar SPIN-based volumetric model as FIG. 6A, however the SPIN-based volumetric model in FIG. 6B is constructed of smaller particles, thereby providing increased resolution. Similarly, FIG. 6C is constructed of smaller particles than FIG. 6B, providing increased resolution. FIGS. 6A, 6B, and 6C may comprise different resolution levels of a same volumetric model in some embodiments. Refer to the discussions of multi-resolution and particle subdivision herein for further teachings.

[0105] FIG. 7 illustrates an example particle from region 402, as illustrated in FIG. 4. The particle illustrated in FIG. 7 may be defined as a separate region if desired. A region boundary can slice through a SPIN-based volumetric model at any desired location. Here, the region includes for example the illustrated particle, but not a neighbor particle to which the illustrated particle would be joined in the complete SPIN-based volumetric model.

[0106] FIG. 7 illustrates example vertices 701, auxiliary vertices 711, and particle surface 721. One or more particle membranes comprising one or more properties for the particle membrane surface 721 may be associated with the particle, such that the particle membrane surface 721 may exhibit properties of a label assigned to the particle membrane surface721. The volume enclosed inside all of the illustrated vertices (including the auxiliary vertices 711) is referred to herein as a particle volume. FIG. 9 illustrates a particle comprising two membrane surfaces defined by wireframes 910 and 920 surrounding the centroid 900.

[0107] A variety of shapes can also represented by single particles, which have the ability to morph into an infinity of shapes and sizes. FIG. 8 illustrates a variety of example particle shapes. Furthermore, the precision level of a particle surface can be increased by inserting extra vertices and subdividing the surface mesh, as described herein in relation to FIGS. 24 - 26. In order to simplify the teachings herein, however, particles discussed herein are generally shaped as spheres, cubes, octahedrons, star tetrahedrons, cuboctahedrons, and several other more easily illustrated shapes. Nevertheless, all of the properties that these particular shapes exhibit may also be present within any arbitrarily shaped particle. Any of the properties that these illustrated particles exhibit may also present within any arbitrarily shaped particle. [0108] Multi-resolution examples illustrated in FIG. 6 show a constant level of detail across the entire shape. A SPIN-based volumetric model, however, can be displayed at an adaptive level of detail, by rendering particles at different resolution levels and/or precision levels, as discussed herein.

[0109] The virtual net employed FIG. 1 has the virtual net points uniformly distributed, and the particles are inserted at predefined {x, y, z} coordinates. In some embodiments, the virtual net points can be customized in non-uniform distributions, to support a desired particle-based volumetric model. Yet, in other embodiments, such as, in free form modeling or animation, a particle can be inserted at any {x, y, z} coordinate and the virtual net point closest to the particle insertion point may be moved such that it overlaps with the centroid of the particle.

[0110] Furthermore, a virtual net can be defined using several different approaches. In some embodiments, a virtual net may be defined in a mathematical form, by evaluating a mathematical function to determine particle position and neighbor relationships. In some embodiments, a virtual net may be defined for example by allocating an array of points in a computer memory.

[0111] In conclusion, a virtual net may provide a reference system for the particles allowing determining which particles are neighbor, and accordingly, which particles may be merged to form a larger entity.

Features and Advantages

[0112] In some embodiments, SPIN-based volumetric models can be defined at multiple resolution levels by one or several particles that may touch each other, and by the relationship between these particles, which can be described through particle interconnection and particle lineage networks. The description of a SPIN-based volumetric model can be encapsulated in a SPIN representation. A SPIN representation can comprise a multi-dimensional object representation containing a virtual net.

[0113] In some embodiments, SPIN graphics provide a scalable particle-based approach that generates multi-resolution descriptions from a variety of input data in a view-independent fashion. SPIN graphics can support flexible ways for interconnecting neighbor particles according to the specifics of a particular design or set of input data. SPIN graphics can also represent volumetric models in a unified format preserving both the volumetric and surface properties of a volumetric model. SPIN graphics also can allow for adaptive level-of-detail (LOD), and can support dynamic shape and topology changes programmatically or through user interaction. In addition, implementations of SPIN graphics may be suited for modeling, animation (via software applications designed for use with SPIN and/or in connection with software applications such as Maya, CAD, and CAM), progressive compressed data transmission over digital or analog channels, and both static and evolving SPIN-based volumetric models.

[0114] While SPIN graphics have a number of advantages, some of the advantages that will be appreciated in connection with various of the below described embodiments include providing a particle -based representation method that embeds both the surface and volumetric description of a given shape; an authoring method allowing multi-resolution representations of a given shape; compact and progressive storage, streaming, adaptive level-of-detail (LOD), animation, modeling, special effects like morphing, and display; allowing specification of particle properties and real-time changes of particles' properties; memory efficiency and organization of particles according to regions of interest; and accurate shape representations which may be less dependent on particle tilting or distribution.

[0115] In particular, with regard to the above listed advantages, adaptive LOD may be an useful feature for a variety of graphics technologies, as it allows for rendering high complexity 3D scenes in real-time on a diverse range of devices. 3D graphics power varies by several orders of magnitude among existing consumer and professional devices with 3D graphics capabilities, which range from low power mobile devices, such as phones, to high-end graphics stations. Embodiments of SPIN graphics technologies disclosed herein can include powerful adaptive LOD support.

[0116] Additionally, in modeling applications, embodiments of SPIN graphics can provide improvements over existing graphics technologies that represent volumetric models as only a polygonal mesh, without additional volumetric information. Such existing graphics technologies can be limiting when the underlying polygonal mesh does not fully support a desired type of local deformation due to the size or orientation of the polygons. Moreover, when modeling implies topology changes, such as morphing a sphere into a torus or vice versa, such existing systems require the restructuring of the polygonal mesh, including the addition or removal of vertices. Embodiments of SPIN graphics technologies can provide more efficient modeling by altering the volumetric information, and locally regenerating the polygonal mesh description. Terms and Concepts

[0117] The following paragraphs introduce some of the terms and concepts employed by the SPIN graphics model.

[0118] "Virtual net" refers to a structure that may hold particles with their interconnection and lineage networks, and may hold global settings applicable to a SPIN-based volumetric model.

[0119] A "virtual net point" refers to a position within the virtual net on which a particle can be set or can exist. A virtual net point may be represented as a dot with zero size. Further, a virtual net point usually pertains to at least one data value representing a property of a volume, and may have coordinates {x, y, z} in the 3D space, and an index into the virtual net. The virtual net points may be distributed according to the cubic-packing or hexa-packing modes described herein.

[0120] The "main vertices" are a set of vertices defining the surface of a particle at the lowest precision level. The number of main vertices may depend on the vertex sharing configuration, as described herein.

[0121] A "shared vertex" is a vertex that may be used by more than one particle, allowing the particles to touch at the shared vertex. One or more vertex types may be designated as shared vertices, as described herein.

[0122] A "vertex sharing configuration" identifies which of the vertex types are sharable. Some embodiments may include 7 fixed vertex sharing configurations and a flexible vertex sharing configuration, as described herein.

[0123] A "membrane" describes the shape and properties of a surface boundary that a particle has at a given time and/or dimension. A particle having several membranes may be referred to as a multi-membrane particle. Membranes may also be referred to herein as a particle's surface.

[0124] "Surface triangulation" refers to a process of connecting vertices to define the surface mesh of a membrane.

[0125] A "centroid" is a point inside a particle's volume that is enclosed within all of the particle's membranes.

[0126] "Multi-resolution" refers to the ability to increase or decrease resolution level of a SPIN-based volumetric model, which may be achieved respectively by subdividing a particle into multiple particles, or by reuniting neighbor particles into one particle, as explained herein. [0127] "Precision level" refers to a number of vertices used to define a particle's surface mesh. At a lowest precision level, the main vertices form a base mesh. At higher precision levels, addition vertices may be added by subdividing the base mesh.

[0128] "Level of detail (LOD)" refers to an accuracy level of a volumetric model and may be adjusted by increasing or decreasing resolution level, precision level, or both.

[0129] A "particle" is a standalone multi-shape entity that is defined at least in part by positions of predefined numbers of vertices. A particle optionally exhibits one or several membranes, a centroid, and includes a volumetric description associated with each membrane. A particle can have an infinite number of shapes, as discussed herein.

[0130] "Particle interconnection network" refers to how particles connect and relate to each other at a given resolution level within a predefined region, which region may include an entire SPIN-based volumetric model or portion thereof. The particle interconnection network allows compact storage of the positioning of particles within a virtual net.

[0131] A "particle lineage network" has a hierarchical structure and deals with relationships between particles on a multi-resolution scale. A particle lineage network allows compact storage of relationship between particles at different resolution levels. Given a particle interconnection network at a specific resolution level, the particle lineage network allows derivation of particle interconnection networks at all the other resolution levels.

[0132] "Reconstructed surface" refers to a surface boundary of a SPIN-based volumetric model.

[0133] "SPIN-based volumetric model" refers to a particle-based representation of a volumetric model.

[0134] "SPIN-based surface reconstruction" refers to a procedure for generating a "SPIN- based volumetric model".

[0135] "Target surface" refers to a given surface of a volumetric model.

[0136] "Volumetric data" typically comprises data elements that may be arranged in a 3D matrix, and therefore may be thought of as a data grid.

[0137] A "volumetric description" may contain a volume measure of a space enclosed within a membrane, and its volumetric properties, such as density and/or any of a variety of other properties. [0138] The term "volumetric model" refers to a variety of input that has both a volumetric and surface component, such as, volumetric data, implicit surfaces, range data, cloud data, and several other types of acquisition data, synthetic or simulation data, and any other type of data that can be brought to a discrete form. Volumetric models described herein may be SPIN-based (also referred to as particle-based). A particle-based volumetric model is a volumetric model comprising one or more particles. Whether a particular volumetric model disclosed herein is particle-based will be appreciated from the context, description and figures associated with a disclosed volumetric model.

Virtual Net and Particles

[0139] In some embodiments, one or more virtual net calculation module(s) 4609 may provide a virtual net. The virtual net may provide a reference system for the particles for use in a variety of operations discussed herein. For example, in some embodiments a virtual net allows determinations of which particles are neighbor, and accordingly, which particles may be merged to form a larger entity.

[0140] In some embodiments, a virtual net may comprise an array of points distributed according to a certain strategy, as described herein, whereby a virtual net point may pertain to at least one data value representing a property of a volume, and may have coordinates {x, y, z} in the 3D space, and an index into the virtual net. In such embodiments, neighbor particles may be identified by their corresponding indices in the virtual net.

[0141] In other embodiments a virtual net may be defined under a mathematical formulation, which approach may eliminate a need for allocating virtual net points in a computer memory as an array of points. Such approach may save memory. Furthermore, neighbor particles may be identified by evaluating the neighborhood using the mathematical formulation. Evaluation criteria may comprise one or more of maximum/minimum distance between particles, angular orientation between particles, minimal particle size, and other parameters. The evaluation criteria may also determine when two particles are may be advantageously replaced by a larger particle, for example in response to a determination that two or more particles are too close to each other. Once neighbor particles identified, the evaluation criteria may also be used to determine the shared vertices that may be involved in the merging of the said particles. [0142] Both types of virtual net definitions can be used interchanged and for any of the purposes described herein, including, animation, modeling and authoring.

Particle Packing Modes

[0143] In some embodiments, SPIN graphics technologies can include particle distribution modules 4607 configured to implement a selected 2D, 3D, or higher N-dimensional particle distribution strategy. Two example particle distribution strategies are described herein, and are referred to herein as cubic-packing and the hexa-packing modes.

[0144] In the cubic-packing mode, the particles may be distributed along three axes, labeled for example as U, V and W. This mode can thus use a 3D matrix, which can be represented in the 3D Cartesian space {X, Y, Z}. For example, refer to the virtual net 131 illustrated in FIG. 1.

[0145] FIG. 1OA illustrates particles in a virtual net 1401 in a hexa-packing mode. In the hexa-packing mode the particles may be distributed along four axes, labeled as Q, R, S and T, thus, this mode may utilize a 4D matrix, which can also be represented in the 3D Cartesian space {X, Y, Z} . The 4D matrix can be contained in a 3D matrix that would correspond to a cubic-packing mode that would roughly contain twice the amount of the virtual net points of the 4D matrix. In other words, when a 4D matrix is mapped to a 3D matrix, one out of two of the virtual net points along each of the U, V and W directions of the 3D matrix are not present in the 4D matrix. Hence, in some embodiments, a point H(q, r, s, t) from a virtual net in a hexa-packing mode can be mapped to a point G (u, v, w) from a virtual net in a cubic-packing mode. Yet, not every point G (u¹, v' , w') from a virtual net in a cubic-packing mode has a corresponding point in a virtual net in a hexa-packing mode. Accordingly, the hexa-packing mode may use about 50% of the memory required for storing a SPIN representation compared to an "equivalent" cubic-packing mode.

[0146] FIG. 1OB and 1OD illustrate two identical virtual nets in a cubic-packing mode, with different set of highlighted virtual net points. FIG. 1OC and 1OE illustrate virtual nets in a hexa-packing mode. Larger hexa-packing mode virtual nets, such as illustrated in FIG. 1OA, may contain regions of virtual net points as shown in both FIG. 1OC and 1OE. The virtual net points such as 1200, 1201 and 1202, which are present in the hexa-packing mode illustrated in FIG. 1OC, are indicated in FIG. 1OB. The non-indicated virtual net points 1203 in FIG. 1OB have no corresponding virtual net point in FIG. 1OC. Similarly, virtual net points such as 1210, 1211 and 1212, which are present in the hexa-packing mode illustrated in FIG. 1OE, are indicated in FIG. 1OD. The non-indicated virtual net points 1213 in FIG. 1OD have no corresponding virtual net point in FIG. 1OE. In this example, the virtual nets from FIG. 1OC and 1OE have no common points, and the union of all points of virtual nets from FIG. 1OC and 1OE yields the points of the virtual net of either FIG. 1OB or 10D. In other embodiments, using FIG. 1OA as an example, virtual net regions, such as shown in FIG. 1OC and 1OE, may overlap and have common virtual net points. Moreover, virtual net regions are not limited to a certain number of points. A region can also comprise the entire volumetric model.

[0147] FIGS. 1OF, 1OG, 1OH and 101, illustrating a virtual net similar to the one in FIG. 1OC and 1OE, further elaborate on the four Q, R, S and T axes 1230. Each of the figures indicates one cross-section that is orthogonal to one of the four axes. The axis in question is displayed in white and labeled, while the other three axes are shown in grey color. FIG. 1OF shows cross section 1220 and axis Q 1230. FIG. 1OG shows cross section 1221 and axis R 1230. FIG. 1OH shows cross section 1222 and axis S 1230. FIG. 101 shows cross section 1223 and axis T 1230.

[0148] The index identifying a virtual net point within the virtual net may be defined as a three-dimensional value {u, v, w} along U, V and W axes of a 3D matrix in cubic-packing mode, respectively be defined by a as a four-dimensional value {q, r, s, t} along the Q, R, S, T axes of a 4D matrix in the hexa-packing mode..

[0149] FIGS. 14A and 14B illustrate spherical particles. The particles illustrated in FIG. 14 may connect with up to 26 neighbor particles in both cubic and hexa packing mode virtual nets. Accordingly, in some embodiments there may be up to 26 main vertices defining a single particle's surface. In some embodiments, a minimal number of main vertices may depend on the vertex sharing configuration that applies to a particle. The main vertices may define a particle's "base mesh" at the lowest precision level.

[0150] A volumetric model may be constructed in either the cubic or hexa-packing mode. The different packing modes may result in different surface triangulations of a volumetric model, and particle merge behaviors may be different in the different packing modes.

Particle Connectivity Modes

[0151] The particle packing modes may provide a framework for determining when two or more particles are neighbor. Accordingly, several connectivity modes can be established for particles, specifying the directions in which neighbor particles may connect with one another. FIGS. 11, 12, and 13 illustrate various connectivity modes. FIG. 11 illustrates particles in a 6-connectivity mode, in which neighbor particles may connect when they are neighbors on only one of the U, V or W directions. FIG. HA illustrates neighbor particles 2002A, 2002B in a cubic packing mode virtual net defined by virtual net points such as 2001 and U, V, W axes 2000. The particles 2002A, 2002B are neighbor along only one axis, namely, the V axis (in this example), and may therefore connect in the 6-connectivity mode. FIG. HB illustrates particles 2002A, 2002B after merging along the V axis. FIG. HC illustrates neighbor particles 2002C, 2002D in a hexa packing mode virtual net defined by virtual net points such as 2011 and Q, S, T, R axes 2010. The particles 2002C, 2002D are neighbor along only one axis in an equivalent cubic mode virtual net such as illustrated in FIGS. HA and HB, namely, the V axis (in this example), which may be constructed from some combination of the Q, S, T, and/or R axes 2010. The particles 2002C, 2002D may therefore connect in the 6-connectivity mode. FIG. HD illustrates particles 2002C, 2002D after merging along the V axis.

[0152] FIG. 12A illustrates neighbor particles 2004A, 2004B in a cubic packing mode virtual net defined by virtual net points such as 2001 and U, V, W axes 2000. The particles 2004 A, 2004B are neighbor along a direction that is a combination of only two axes, namely, the U, V axes (in this example), and may therefore connect in the 12-connectivity mode. FIG. 12B illustrates particles 2004A, 2004B after merging along the U, V axes. FIG. 12C illustrates neighbor particles 2004C, 2004D in a hexa packing mode virtual net defined by virtual net points such as 2011 and Q, S, T, R axes 2010. The particles 2004C, 2004D are neighbor along a direction that is a combination of only two axes in an equivalent cubic mode virtual net such as illustrated in FIGS. 12A and 12B, namely, the U, V axes (in this example), which may be constructed from some combination of the Q, S, T, and/or R axes 2010. The particles 2004C, 2004D may therefore connect in the 12- connectivity mode. FIG. 12D illustrates particles 2004C, 2004D after merging along the U, V axes.

[0153] FIG. 13A illustrates neighbor particles 2006A, 2006B in a cubic packing mode virtual net defined by virtual net points such as 2001 and U, V, W axes 2000. The particles 2006 A, 2006B are neighbor along a direction that is a combination of all three axes, namely, the U, V, and W axes, and may therefore connect in the 8-connectivity mode. FIG. 13B illustrates particles 2006A, 2006B after merging along the U, V, and W axes. FIG. 13C illustrates neighbor particles 2006C, 2006D in a hexa packing mode virtual net defined by virtual net points such as 2011 and Q, S, T, R axes 2010. The particles 2006C, 2006D are neighbor along a direction that is a combination of all three axes in an equivalent cubic mode virtual net such as illustrated in FIGS. 13A and 13B, namely, the U, V, and W axes, which may be constructed from some combination of the Q, S, T, and/or R axes 2010. The particles 2006C, 2006D may therefore connect in the 8-connectivity mode. FIG. 13D illustrates particles 2006C, 2006D after merging along the U, V, and W axes.

[0154] Combinations of the above connectivity modes are possible yielding the 18- connectivity, 14-connectivity, 20-connectivity, and 26-connectivity modes, with a total of 7 connectivity modes. Also, more than two particles may merge in any of the connectivity modes discussed herein, as will be seen in various of the illustrations provided herein.

Vertex Sharing Configurations

[0155] In some embodiments, SPIN graphics technologies can include vertex sharing modules 4610 configured to implement a vertex sharing configuration. Each vertex sharing configuration specifies which of the vertex types can be shared, and thus enables a particle to accept connections and merge with other particles through these shared vertices.

[0156] Given a connectivity mode between the particles, a vertex sharing configuration may enable or disable the merging of neighbor particles through a shared vertex. Accordingly embodiments may provide 7 fixed vertex sharing configurations, matching the 7 connectivity modes. Some embodiments may also support a flexible vertex sharing configuration, as described herein. Additionally, when particle neighbors beyond the nearby neighbors are considered, additional vertex sharing configurations may be employed to further expand particle connect and merge options in some embodiments.

[0157] To determine the connectivity properties of the 26 vertices illustrated in the particles of FIG. 14, the particles' surfaces may be further mapped from a sphere to a cube, as illustrated FIGS. 15A-15B. There are three categories of vertices, and so, these 26 vertices may be grouped into 6 of type V_A, as illustrated in FIG. 16 A, 12 vertices of type V_B, as illustrated in FIG. 16B, and 8 vertices type V_c, as illustrated in FIG. 16C. The vertices of type V_A are located within the boundary of each of the cube's faces in FIGS. 15A-15B, the vertices of type V_B are located along each of the cube's edges in FIGS. 15A-15B, and the vertices of type V_c are located at each of the cube's corners in FIGS. 15A-15B.

[0158] In a 6-shared configuration, any of the 6 vertices of type V_A may be shared. In a 12- shared configuration, any of the 12 vertices of type V_B may be shared, and in an 8-shared configuration, any of the 8 vertices of type V_c may be shared. Furthermore, any combination of the above three configurations is possible, yielding the 18-shared, 14-shared, 20-shared, and 26-shared configurations.

[0159] Besides the above "fixed" vertex sharing configurations, there may be also a "flexible" vertex sharing configuration, whereby the sharing status of each vertex, for single or groups of particles, can be enabled or disabled dynamically, independently of the rest of the vertices. Each of the fixed and flexible vertex sharing configurations allows emphasizing different topological variations in a reconstructed surface, to better match a target surface of a volumetric model.

[0160] In an example comprising two or more reconstructed surfaces in a same SPIN- based volumetric model, a first surface in the SPIN-based volumetric model may be obtained using a first sharing configuration, e.g., a 26-shared configuration, while a second surface, third or other additional surface in the SPIN-based volumetric model may be obtained using a different sharing configuration, e.g., a 14-shared configuration.

[0161] Especially when representing generic volumetric models, the 26-shared configuration may be optimal in the cubic packing mode, and the 18-shared configuration may be optimal in the hexa-packing mode, since the topology of the reconstructed surface (defined above) of the volumetric model may be the least sensitive to the orientation of the virtual net with respect to the axis of symmetry of the said volumetric model. Therefore, if not specified otherwise, the 26- shared configuration may be the default vertex sharing configuration for the cubic packing mode and the 18-shared configuration may be the default vertex sharing configuration for the hexa packing mode. Yet, any of the 7 fixed or any flexible vertex sharing configurations can be set as default in some embodiments. A choice of default sharing configuration may be dependent on which special effect or what topological variation a reconstructed surface is expected to have. In the cubic packing mode there are 26 immediate neighbors while in the hexa-packing mode there are only 18 immediate neighbors. Where an 18-shared vertex sharing configuration is selected, hexa-packing mode neighbor connections such as illustrated in FIG. 13D would not be allowed.

[0162] To illustrate the effect of a vertex sharing configuration selection, FIGS. 4 and 5 illustrate an example SPIN-based volumetric model in a cubic packing mode wherein the 26-shared vertex sharing configuration is employed. FIG. 1OA illustrates an example SPIN-based volumetric model in a hexa-packing mode wherein 12-shared vertex sharing configuration is employed. The volumetric model of FIG. 1OA would look very similar FIGS. 4 and 5 if the 18 vertex sharing configuration was used instead of the 12-shared vertex sharing configuration.

[0163] A default vertex sharing configuration can be set at different conceptual levels, such as, globally, when the vertex sharing configuration applies to the entire set of particles, per region of particles within a given resolution level or across the resolution levels, when the vertex sharing configuration applies to a subset of the particles, and per particle. In combination with the said conceptual levels a vertex sharing configuration can be set for all different membranes, or only for one or few of the membranes. To conclude, different regions, particles, or even membranes, may be allowed to have distinct vertex sharing configurations at any resolution level or across the resolution levels.

[0164] Each default vertex sharing configuration may be recorded as an attribute, either globally, or within one of the said networks, whichever applies. The priority of a vertex sharing configuration may increase from the global level towards the individual particle. Accordingly, the vertex sharing configuration that pertains specifically to a given vertex may be the one that has the highest priority.

[0165] In conclusion, some embodiments may allow particles to connect at a vertex if sharing is enabled for the vertex on all particles. Also, the vertex may be of the same type on all particles. Furthermore, in some embodiments, a particle may connect with several particles at different shared vertices, yet at any single shared vertex, there may be not more than two particles connecting.

Example: Shared Vertices

[0166] In some embodiments, SPIN graphics technologies can include particle connection modules 4606 configured to support particle connecting and merging operations. For example, FIG. 17 illustrates for a 2D particle, or respectively, in a 2D cross-section through a 3D particle, example behavior of shared vertices. In some embodiments, neighbor particles within a particle interconnection network may be allowed to touch at specific predefined points located on the particles' surfaces. FIG. 17A illustrates neighbor particles 1010 and 1020. Particle 1010 comprises a centroid 1011 and a shared vertex 1012, and particle 1020 comprises a centroid 1021 and shared vertex 1022. FIG. 17B illustrates overlapping of shared vertices 1012 and 1022, connecting the particles 1010 and 1020. [0167] FIG. 17C illustrates the shared vertices splitting into auxiliary shared vertices 1031 and 1032, providing a doorway through which the neighbor particles 1010 and 1020 merge. A shared vertex may be automatically split into auxiliary vertices, thereby automatically generating auxiliary vertices to support a particle merge. In general, a shared vertex such as 1012 or 1022 may be located at an intersection point between a particle surface and a straight or curved line connecting particle centroids 1011, 1021. The auxiliary shared vertices 1031 and 1032 may be positioned in any direction with respect to the position of the initial position occupied by vertices 1012 and 1022 in FIG. 17B. For example, in some embodiments, auxiliary shared vertices 1031 and 1032 may be positioned in directions, such as 1050 and 1051, that are orthogonal to a straight or curved line connecting particle centroids 1011 and 1021. Further discussion of this subject is included elsewhere in this description, which also makes reference to the various additional identified elements of FIGS. 17C, 17D, 17E, and 17F.

[0168] In conclusion, in the 2D, 3D or other multi-dimensional space, once particles connect through a shared vertex, when they continue merging, the shared vertex may split into several auxiliary shared vertices such as 1031 and 1032. FIG. 7 illustrates auxiliary shared vertices positioned around the rim on the left-hand side of the illustrated 3D particle, while the neighbor particle sharing such vertices is omitted from FIG. 7 for the sake of clear illustration. An area defined by auxiliary shared vertices may be expandable.

Multi Membrane Particles

[0169] In some embodiments, SPIN graphics technologies can include membrane modules 4605 configured to support particle membranes. A particle with multiple membranes can be seen as several single membrane particles that overlap, and which share a same centroid. FIG. 9 illustrates a particle centroid 900. The centroid is a point inside the particle's volume that is enclosed within all of the particle's membranes, e.g., membranes defined by the wireframe views provided by 910 and 920.

[0170] Within the scope of a particle, every membrane such as 910 and/or 920 may be identified by one or more unique labels. A same label can be used to identify membranes in different particles within an interconnection or lineage network, at any resolution level. The union of the membranes with a same label belonging to different particles may describe a surface boundary of a SPIN based volumetric model that exhibits a particular property (skin, bones, etc). The label may comprises an identifier, an optional dimension parameter, and an optional feature set comprising one or more of surface attributes, such as, color, transparency, elasticity, etc., and/or visibility parameters.

Multi Membrane Volumetric Models

[0171] In some embodiments, SPIN graphics technologies can include multi-membrane connection modules 4613 configured to connect particles with multiple membranes. In a multi- membrane particle, every membrane may have its own vertices, for example, each membrane may comprise up to 26 vertices at the lowest precision level in both the cubic-packing mode and the hexa-packing mode when the 26 sharing configuration is used. The minimal number of vertices can be also less than 26, which is dependent upon the vertex sharing configuration that applies for the particle, namely, 6, 8, 12, 14, 18, and 20 vertices, corresponding to 6-sharing, 8-sharing, 12-sharing, 14-sharing, 18-sharing, and 20-sharing configuration respectively. Moreover other minimal numbers of vertices are possible when flexible vertex sharing configurations are used. The vertices of each membrane may be connected in radial, transversal or mixed mode to form a surface mesh, and they can be selectively enabled as shared or disabled using one of the said fixed or flexible vertex sharing configurations.

[0172] In some embodiments, whenever two multi-membrane particles connect, the shared vertices (it can be one or more) may lie on compatible membranes of both particles. Thus, in such embodiments two particles may connect and merge if both particles have at least one reciprocally compatible set of membranes. Moreover, several compatible membranes that belong to the same particle may connect through the same shared vertex. Membranes that are compatible may have either the same label or may be listed as compatible. A list of groups of compatible membranes can be recorded as an attribute, either globally for the entire set of particles, for a region of interest containing a subset of the particles, or for one or more individual particles. The priority of the list may increase from the global level towards the individual particle. Accordingly, the list of groups of compatible membranes that pertains specifically to a given particle may be the one that has the highest priority. Surface Triangulation Modes

[0173] In some embodiments, SPIN graphics technologies can include surface triangulation modules 4608 configured to connect vertices to form the particle's surface (or surfaces in the case of multiple membranes). Two example surface triangulation modes are described herein, referred to as the radial and transversal triangulation modes.

[0174] The below discussion considers connecting vertices of particles containing 26 shared vertices. However, it will be appreciated that variants of the disclosed techniques may be applied to particles with different numbers of shared vertices.

[0175] An example radial triangulation mode is illustrated for a spherical shaped particle in FIG. 14A. An example radial triangulation mode is illustrated for a cubical shaped particle in FIG. 15A.

[0176] An example transversal triangulation mode is illustrated for a spherical shaped particle in FIG. 14B. An example transversal triangulation mode is illustrated for a cubical shaped particle in FIG. 15B.

[0177] When considering the radial triangulation mode, each vertex may connect directly to vertices of a different type, but never connects directly to a vertex of the same type. For example, a vertex of type V_A may connect directly to 4 vertices of type V_B, and also to 4 vertices of type V_c. A vertex of type V_B may connect directly to 2 vertices of type V_A and also to 2 vertices of type V_c. A vertex of type V_c may connect to 3 vertices of type V_A, and also to 3 vertices of type V_B. Accordingly, in the radial triangulation mode, a vertex of type V_A may be connected to 8 vertices, a vertex of type V_B may be connected to 4 vertices, and a vertex of type V_c may be connected to 6 vertices.

[0178] In an example transversal triangulation mode, a vertex of type V_A may connect directly to 4 vertices of type V_B. A vertex of type V_B may connect directly to 4 vertices of type V_B and also to 2 vertices of type V_c. A vertex of type V_c may connect to 3 vertices of type V_B. Accordingly, in the transversal triangulation mode, a vertex of type V_A may be connected to 4 vertices, a vertex of type V_B may be connected to 6 vertices, and a vertex of type V_c may be connected to 3 vertices.

[0179] In some embodiments, a SPIN-based volumetric model may comprise particles in either or both of the radial and/or transversal triangulation modes. A single particle may also comprise a mixture of radial and transversal mode vertex connections, as desired to produce a surface mesh with a topology that best matches the target surface. The radial triangulation mode may be generally better suited for local convexities in the surface, while the transversal triangulation mode may be generally more appropriate for local concavities in the surface.

[0180] The connectivity of a mesh around a shared vertex may be modified to comprise auxiliary shared vertices as needed when particles are merged. Connectivity of a mesh may be modified by inserting new triangles and optionally replacing some existing triangles. Meanwhile, the connectivity between remaining vertices of a particle may remain unaffected by a merging operation.

[0181] Furthermore, as can be seen from FIGS. 14A-14B and 15A-15B, in some embodiments both the radial and the transversal triangulation modes may define a surface mesh of a single non connected particle at a lowest precision level with a same number of triangles, namely 48 triangles.

Operations with Particles

[0182] In some embodiments, SPIN graphics technologies can include operations modules 4611 configured to execute any of variety of operations with respect to a particle and/or SPIN-based volumetric model. FIG. 18A illustrates a detailed view of example operations modules 4611 stored on a computer readable medium 1500. Example operations modules may include, for example: (i) Particle Connection module(s) 4606, configured to connect and/or merge neighbor particles, or split connected particles, (ii) Remove/ Add module(s) 4636, configured to remove and/or add particles, (iii) Mesh Subdivision module(s) 4618, configured to augment and/or diminish the precision level of a particle, (iv) Vertex Sharing module(s) 4610, configured to change the vertex sharing configuration, (v) Divide/Join module(s) 4637, configured to divide and/or join particles, for example for the purpose of growing a volumetric model as discussed herein, and (vi) Subdivide and Reunite module(s) 4617, configured to subdivide and/or reunite particles. In some embodiments, the operations (i) to (iv) and corresponding modules may be implemented using a particle interconnection network, while operations (v) and (vi) and corresponding modules may be implemented using a particle lineage network. All the above operations can be used to implement dynamics of a SPIN-based volumetric model.

[0183] In some embodiments, operations of type (v), which may be implemented for example in a Divide/Join module 4637, may be used in simulating dynamics involved in growing a SPIN-based volumetric model, such as, a growing plant or anything else involving related growing behaviors. When a particle, referred to as an "ancestor particle", divides into several "descendant" particles, the descendant particles can yield sizes comparable to the ancestor particle. In this way, a SPIN-based volumetric model can grow with each particle division. The particle division step can be localized, and only affect one or a few of the particles, but it can also have a global impact that triggers division of all particles at once. The reverse operation of division is the joining of particles, which can shrink a SPIN-based volumetric model at each joining step. Furthermore, in the areas where "ancestor particles" divide into "descendant particles" the virtual net may be expanded and new virtual net points may be created to support the descendant particles. When particles join, the virtual net may be contracted in a reverse operation.

[0184] In some embodiments, the operations (vi) which may be implemented for example in a Subdivide and Reunite module 4617 may be used for increasing or decreasing the resolution level of a SPIN-based volumetric model, and these operations may be similar to (v). Yet, the main difference between operation (v) and (vi) may be that, when an ancestor particle subdivides into several descendant particles, the latter ones may remain smaller than the said ancestor particle.

[0185] During operations (v) and (vi), an ancestor particle may divide or subdivide into two or more descendant particles along any of the directions of the virtual net, for example in 3 directions for the cubic-packing mode, and 4 directions in the hexa-packing mode. These operations can happen in any of these directions simultaneously, and each operation can be repeated over and over again. Further, the descendant particles may preserve the surface and volumetric properties of the ancestor particle, but they can also change them, as it will be exemplified later on. A descendant particle may also become an ancestor particle once it divides or subdivides itself into other descendant particles. The procedure can be reversed through the joining or reuniting operations, which perform the reverse steps of the divide and subdivide operations.

[0186] Moreover, the operations (v) and (vi) can happen at the same time since they may be complementary.

Particle Regions

[0187] In some embodiments, SPIN graphics technologies can include region support modules 4604 configured to support particle regions. FIG. 4 illustrates a SPIN-based volumetric model comprising example regions 401 and 402. Embodiments of the SPIN graphics model can be configured to support multiple particle regions at each resolution level. A SPIN-based volumetric model can comprise at each resolution level either a single region containing all of its particles, or a plurality of regions. The regions can be any arbitrary shape. For example, a region may take a box shape or a sphere shape or any unordinary shape.

[0188] The regions can be adjacent or hierarchically nested inside one another. When the regions are nested, relationships between the regions can be expressed within any resolution level through a region nesting network. Relationships between the regions across resolution levels can be expressed through a region lineage network. In some embodiments, a region lineage network may have a hierarchical structure and encoding/decoding modules 4602 may encode how the regions subdivide when the resolution level is increased, and how the regions reunite when the resolution level is decreased, and/or subsequently decode such data.

[0189] Regions can be defined for a variety of useful purposes, such as localization and containment of groups of particles for faster retrieval access and memory efficiency; and grouping particles with similar or related features.

Operations with Regions

[0190] In some embodiments, SPIN graphics technologies can include region operations modules 4612 configured to execute any of variety of region operations. For example, at any resolution level, regions may be allowed to overlap, and so, one or more regions may occupy a space within the scope of another (optionally larger) region. This type of relationship between regions may be referred to as nesting. The region nesting may result in shared particles, when the particles within the intersection volume of the nested regions belong to more than one region, or the region nesting may be without shared particles in the opposite case. Further, regions may also relate across the different resolution levels, when the resolution level is increased, a region may split into several regions, and when the resolution level is decreased, several regions may combine into fewer regions.

[0191] FIG. 18B illustrates a computer readable medium 1800 comprising a detailed view of example region operations modules 4612 as may configure a computing device such as illustrated in FIG. 54 to perform operations on regions. The region operations modules 4612 that can be configured to perform operations on regions of particles may include: (i) Nesting module 4640, which may be configured to nest/un-nest regions using a region nesting network, and (ii) Subdivide/Reunite module 4641, which may be configured to subdivide and/or reunite regions using a hierarchical network.

[0192] As an example of operations involving regions, a complex SPIN-based volumetric model such as a model representing a building can be split at a given resolution level into several box like regions, each such region containing the particles involved in representing one of the rooms and its content items, such as the furniture and the human characters. Next, at a same resolution level, particles involved in defining the content items within the room region could further be grouped into regions, each such region being pertinent to one of the content items. Even further, the region containing the particles defining a person could be grouped into arbitrary nested regions, each such region corresponding to the organs within the body. Additionally, when the resolution is increased to the next higher level, each of the said regions may subdivide into several regions, and so, the region corresponding to an organ may split into several regions. This may be similar to the octree decomposition with the difference that a region can be arbitrary shaped, and that it can split into a number of regions that is different from 8.

[0193] The subdividing or reuniting of regions, and nesting into regions can continue until either an imposed minimal region size, or a certain resolution limit, is reached.

[0194] Box like regions can be described by the coordinates of their 8 corners, while the shape of arbitrary regions can be encoded by encoding/decoding modules 4602 using zero trees, binary maps, wavelet maps, and/or other similar data structures.

Storage: Particle Interconnection and Lineage Networks; Region Linage and Nesting Networks [0195] In some embodiments, SPIN graphics technologies can include storage modules 4625 configured to store and retrieve SPIN graphics data. In some embodiments of a particle based data representation, because the mesh connectivity may be predefined in a radial, transversal or mixed mode, there may be no need to store the entire mesh connectivity, neither for each particle apart, nor for the entire mesh. It may suffice in some embodiments to store globally, per regions and/or per particles a flag specifying one of the chosen triangulation modes. Further, it may be necessary in some embodiments to store each particle's geometry, namely, the coordinates of the vertices, and optionally the coordinates of the centroid points. Further, the interconnection particle network, and optionally the lineage particle network may be stored. Also optionally, region nesting and lineage networks may be stored. [0196] In some embodiments, SPIN graphics technologies can include particle interconnection network modules 4635 configured to create and/or manage particle interconnection networks. FIG. 19 illustrates a particle interconnection network. Particle interconnection network modules 4635 may be configured to store a particle interconnection network as a linked list of nodes, such as the linked list of nodes 1605, 1606, 1607, 1608, and 1609 illustrated in FIG. 19. Header or other metadata associated with the linked list may store parameters of a global nature such as membrane labels, total number of particles, or other data which applies to all of the nodes in a particle interconnection network. A node in the list may represent a particle description and may have up to 26 links toward other particle descriptions that are neighbor with the particle description. In some embodiments, an interconnection network may link particles of a volumetric model, or region thereof, with a same membrane, and may store the membrane's label.

[0197] A particle interconnection network particle description may comprise either the {u, v, w} index of the said particle into the virtual net, or the coordinates {x, y, z} of the particle's centroid, and one or more of (i) a description of a particle's membrane with a same label as the label of the list, and (ii) attributes related to volumetric properties. The description of the particle's membrane may comprise (i) the number of vertices, (ii) the coordinates of the vertices, (iii) whether the coordinates of the vertices are defined as absolute or relative values, (iv) the surface triangulation mode, (v) the vertex sharing configuration, and (vi) other surface related attributes. In some embodiments, particle description data need not include data that is redundant to any global metadata associated with a corresponding particle interconnection network.

[0198] Particle interconnection network data may be encoded and/or decoded using encoding/decoding modules 4602. The encoding/decoding modules 4602 may encode the said linked list in a compact form suited for storage on a medium. In some embodiments, the encoding/decoding modules 4602 may for example store a first node's particle description as absolute value, and store the contents of its links as relative values with respect to the first list node. As an example, the {u, v, w} indices for the first particle may be stored as absolute values, while for a second particle linked to the first, the difference index will be stored. The difference index may be computed as the difference between the {u, v, w} components of the second particle and of the first particle. Since linked particles are located on neighbor virtual net positions, the difference index may yield one of the -1, 0, or 1 value for each of the {u, v, w} components. The magnitude of the difference index may be much smaller than the absolute value of the index, and therefore can be encoded more efficiently. A further improvement may be achieved by only saving half of all possible links combinations, i.e., 26 combinations, by choosing 13 directions along which the links may be stored for every particle from the list.

[0199] In some embodiments, SPIN graphics technologies can include particle lineage network modules 4634 configured to create and/or manage particle lineage networks. FIG. 20 illustrates a particle lineage network. A particle lineage network may comprise a hierarchical multi- resolution structure comprising nodes illustrating the relationships between ancestor particles and descendant particles as a tree structure. For example, node 1700 corresponds to an ancestor particle, nodes 1701, 1702, and 1703 correspond to example descendant particles of 1700, and nodes 1704a, 1704b, 1704c, and 1704d correspond to descendant particles of 1703. Each node in the tree structure may contain a particle description, or may link to a particle description stored elsewhere, such as in a particle interconnection network node. In the cubic-packing mode each description of an ancestor particle may have up to 8 links towards descriptions of its descendant particles. In the hexa-packing mode, each description of an ancestor particle may have up to 4 links towards descriptions of its descendant particles. Nodes 1701 and 1704a-d are shaded in FIG. 20. The shading indicates that these nodes comprise particles with different properties from an ancestor particle. For example, a descendant particle may comprise a different label from an ancestor particle, and the descendant particle label data may be stored in the particle lineage network. In some embodiments, a node corresponding to an ancestor particle may comprise a union of the properties of its descendant particles. For example, node 1703 may correspond to a particle representing a limb of a biological organism, while nodes 1704c and 1704d correspond to particles representing bone within the limb, and nodes 1704a and 1704b correspond to particles representing flesh within the limb.

[0200] The encoding/decoding modules 4602 may encode the particle lineage network in a compact form suited for storage on a medium. The encoding/decoding modules 4602 may start with the description of an ancestor particle and encode for each of the links whether the descendant particles are of the same label, i.e., matter or void, or whether the descendant particles change their label. A descendant of a same label as its ancestor may be encoded with a value of "0", while a descendant of a different label as its ancestor may be encoded with a value of "1". Furthermore, different labels may be marked with the corresponding label. In addition, for each descendant, the coordinates of its vertices and/or other features may be defined relative to the coordinates of the ancestor particle. [0201] In some embodiments, SPIN graphics technologies can include region lineage network modules 4638 configured to create and/or manage particle region networks. FIG. 20 may be used to also describe a region lineage network. A region lineage network may comprise a hierarchical multi-resolution structure comprising nodes illustrating the relationships between ancestor regions and descendant regions as a tree structure. For example, node 1700 corresponds to an ancestor region, nodes 1701, 1702, and 1703 correspond to example descendant regions of 1700, and nodes 1704a, 1704b, 1704c, and 1704d correspond to descendant regions of 1703. Region lineage network data may be created and/or managed in the same manner as described above for particle lineage networks.

[0202] In some embodiments, SPIN graphics technologies can include region nesting network modules 4639 configured to create and/or manage region nesting networks. FIG. 19 may be used to also describe a region nesting network. A region nesting network may comprise a linked list of nodes, such as the linked list of nodes 1605, 1606, 1607, 1608, and 1609 illustrated in FIG. 19. Header or other metadata associated with the linked list may store parameters of a global nature such as area occupied by a region, parameters common to all particles within the region such as labels, volume properties, shared vertex configuration(s), and/or other data which applies to all of the nodes in a region nesting network. A node in the list may represent a region description and may have any number links toward regions nested within the node.

[0203] In some embodiments, region nesting modules 4639 may be configured to nest a first region inside a second region when the volume of the first region overlaps with the volume of the second region. For example, referring to FIG. 4, region 402 may not be nested in region 401. While region 401 surrounds region 402, the volume of region 402 does not overlap with the volume of region 401. However, embodiments may also be configured to consider any relationship between regions as cause for nesting a region inside another.

Controlling Particle Geometry

[0204] In some embodiments, SPIN graphics technologies can include particle geometry modules 4623 configured to control particle geometry. Particle geometry may be controlled by establishing and/or modifying particle centroid coordinates (or virtual net points corresponding to particle centroid coordinates) and/or particle vertex coordinates. Particle geometry modification may also account for geometry of connected and merged particles. Particle geometry modules 4623 may be configured to include and/or interact with modules for authoring volumetric models, producing animations, interactive modeling, and/or any other modules that directly or indirectly affect particle geometry.

[0205] In some embodiments, every membrane may have a variable geometry, which may be modified by adjusting the coordinates {x, y, z} of the vertices. In some embodiments, vertex adjustment may be done dynamically to support animation. Each of a particle's membranes can be described by a higher order degree function, and so, every membrane can morph into infinity of shapes. Simple volumetric models such as those illustrated in FIG. 8 can be represented precisely with one particle, while other volumetric models with a more complex shape, such as the hyperoctahedron illustrated in FIGS. 29B and 3OB, may be approximated by a SPIN-based volumetric model comprising several particles. However, no matter how complex a shape is, using several particles, increasing the precision level of the particles, and/or providing a multi-resolution description allows to representation of volumetric models of any shape at any desired precision. Additionally, triangulation mode selections may impact the precision and/or geometry of approximated shapes.

[0206] In some embodiments, particle geometry modules 4623 may be configured to adjust coordinates according to an approach used to define the coordinates. The coordinates of a vertex may be specified either as absolute values, or as relative values with respect to at least one reference point. Both absolute and relative values may comprise (i) {x, y, z} components, (ii) a description in a radial fashion (e.g., scalar offset with an optional direction), or (iii) can be defined by a function. Functions defining vertex coordinates as relative values may take as parameters at least one reference point and at least one relative value or vector to at least one reference point. The reference point can be the centroid of the particle or another point that may be interpolated between the centroid points of several neighbor particles. Hence, a reference point can be inside or outside a particle's volume.

[0207] In some embodiments it may be more advantageous to define the vertices relatively to at least one reference point for several reasons, such as, (i) compact data structure, since relative values may have a lower magnitude as absolute values, and (ii) for easier modeling and animation. In the later case, when a reference point moves, the coordinates of a vertex can be immediately recomputed from the coordinates of the reference point and the related relative value. Defining the vertices relatively may be advantageous in animation and modeling applications. [0208] In some embodiments, particle geometry modules 4623 may be configured to produce 2-dimensional or 1 -dimensional cross sections from a 3D volumetric model. This may be accomplished at least in part by collapsing vertex locations towards the plane of a desired cross- section. For example, FIG. 21 illustrates example intermediate steps of morphing from a 3D spherically shaped particle, illustrated in FIG. 2 IA, to a 2D planar membrane, illustrated in FIG. 21D, to a ID linear membrane, illustrated in FIG. 21E. Also, as illustrated in FIGS. 22A and 22B and FIGS. 23A and 23B, cross-sections obtainable by collapsing particle vertices can also be non planar. Yet, each membrane may be constrained to surround/envelop the particle's centroid point.

[0209] In addition, the centroid may also have a {x, y, z} coordinate that can be variable and changed to reposition the particle within the 3D space. In some embodiments, when the centroid of a particle overlaps and is attached to a point in the virtual net, moving the virtual net points or deforming the virtual net may also reposition the particle in the 3D space.

[0210] In some embodiments, particle geometry modules 4623 may be configured to adjust geometry of merged particles. In general, referring to FIGS. 17C, 17D, 17E, and 17F, vertices of merged particles may be adjusted in any manner that avoids self-intersection of merged particle surfaces. A variety of different approaches may avoid self intersection, and several examples are provided herein.

Example: Adjusting Particle 's Geometry

[0211] In FIG. 17C, auxiliary shared vertices 1031 and 1032 are positioned in directions 1050 and 1051. Direction 1051 is defined by starting point 1046 and endpoint 1045. Direction 1050 is defined by starting point 1046 and endpoint 1042. Reference point 1046 is a point (optionally, a midpoint) on a straight or curved line connecting particle centroids 1011 and 1021. Reference point 1045 is a point (optionally, a midpoint) on a straight or curved line connecting virtual net points 1043 and 1044. Reference point 1042 is a point (optionally, a midpoint) on a straight or curved line connecting virtual net points 1040 and 1041. Points 1040, 1041, 1043, and 1044 are all points in directions orthogonal to the line between the centroids 1011 and 1021. Points 1040 and 1041 are on the same side of the line as auxiliary vertex 1031 while points 1043 and 1044 are on the same side of the line as auxiliary vertex 1032. Therefore, an example algorithm for adjusting an auxiliary vertex may be as follows: [0212] Step 1 : Select an internal reference point (such as a midpoint) on a line between particle centroids (centroid bisection line).

[0213] Step 2: Identify first virtual net point neighbor to first centroid, on a line passing through the first centroid and orthogonal to the centroid bisection line and on same side of centroid bisection line as a first auxiliary vertex.

[0214] Step 3: Identify second virtual net point neighbor to second centroid, on a line passing through the second centroid and orthogonal to the centroid bisection line and on same side of centroid bisection line as a first auxiliary vertex.

[0215] Step 3: select an external reference point (such as a midpoint) on line between the first and second identified virtual net points.

[0216] Step 4: Adjust coordinates of auxiliary vertex along a line between the internal and external reference points.

[0217] FIG. 17D illustrates adjusting vertices 1060, 1061, and 1062 other than the auxiliary vertices, which may for example be done along with adjusting auxiliary vertices 1031 and 1032. In FIG. 17D, the non-auxiliary vertices are moved in radial directions, defined individually for each non-auxiliary vertex, using a particle centroid as a starting reference point and a neighbor virtual net point in a same direction as the non-auxiliary vertex as an end reference point. Directions for moving a non-auxiliary vertex may include, for example, a direction defined by one or more of the U, V, and W axes. In the example of FIG. 17D, vertex 1060 and 1061 are adjusted in directions 1052 and 1053 which may be any one of the U, V, or W directions. Vertex 1052 is adjusted in directions 1054 which may be a combination of two of the U, V, and W directions. Direction 1054 is defined by the centroid 1011 and virtual net point 1047. In the case of 3D particles, vertices of type Vc may be adjusted in directions that are combinations of all three axes U, V, and W. Also, other vertices, such as auxiliary vertices, or vertices of types V_A and/or V_B, may be adjusted in directions that are combinations of all three axes.

[0218] FIG. 17E illustrates adjusting vertices 1080, 1081 other than the auxiliary vertices and which are neighbor to the auxiliary vertices, and which may for example be done along with adjusting auxiliary vertices 1031 and 1032. In FIG. 17E, vertices 1080 and 1081 are adjusted in the same manner as described in FIG. 17D. It can be seen that this method limits vertex adjustment to the intersection of the lines defined by 1070 and 1071. While adjusting beyond this limit may be possible in some embodiments, it would produce a self-intersecting surface and is therefore not appropriate for many embodiments, and may be prohibited in some embodiments.

[0219] FIG. 17F illustrates another embodiment of adjusting vertices 1080, 1081 other than the auxiliary vertices and which are neighbor to the auxiliary vertices, and which may for example be adjusted along with adjusting the auxiliary vertices 1031 and 1032. In FIG. 17F, vertices 1080 and 1081 may be adjusted along a curved line starting at a particle centroid 1011 or 1021 and ending at a point 1048 or 1049 along a line between virtual net points 1040 and 1041. Point 1048 may be between 1040 and 1042, and point 1049 may be between 1041 and 1042. The positions of 1040 and 1041 may be selected as described herein. In some embodiments, the shape of the curve of 1072 and 1073 may be selected to maximize the homogeneity of the surface triangles as the surface changes in shape.

Scales of resolution with SPIN

[0220] In some embodiments, SPIN graphics technologies can include LOD control modules 4624 configured to control LOD with which a SPIN-based volumetric model is displayed. Some embodiments may be configured to increase accuracy with which a SPIN-based volumetric model represents a corresponding object or image using any of several example techniques. Techniques for increasing accuracy include (i) augmenting the precision level of one or several of the particles defining a SPIN-based volumetric model, (ii) inserting more particles, (iii) dividing the particles for growing a SPIN-based volumetric model, (iv) augmenting the precision level of portions of one or several of the particles defining a SPIN-based volumetric model, and/or (v) subdividing one or more of the particles defining the SPIN-based volumetric model in order to increase the resolution level with which a SPIN-based volumetric model is represented.

[0221] In some embodiments, LOD control modules 4624 may include multi-resolution display control module(s) 4621 configured to simultaneously display multi-resolution SPIN-based models at different resolution levels. Accordingly, different particles or regions within a multi- resolution volumetric model can be simultaneously displayed at different resolution levels.

Multi-Resolution Aspects and Design

[0222] In some embodiments, SPIN graphics technologies can include multi-resolution modules 4616 configured to support multi-resolution aspects of a volumetric model. For example, multi-resolution modules 4616 may configure a device to allow for design or display of SPIN-based volumetric models comprising a plurality of resolution levels, ranging from low-resolution to high- resolution. Multi-resolution modules 4616 may encode multi-resolution data for a SPIN-based volumetric model, allowing the SPIN-based volumetric model to be rendered at any of a plurality of resolution levels.

[0223] In some embodiments, multi-resolution techniques employed in a particle-based graphics model may be based on an approximation scheme. Within a multi-resolution SPIN-based volumetric model, there may be a relationship between virtual net positions and a particle's vertices at the different resolution levels. A lower resolution version of a SPIN-based volumetric model may be obtained by smoothly approximating a higher resolution version of the same model.

[0224] Virtual net positions and vertices defining the particles of a lower resolution version of a SPIN-based volumetric model may be differently distributed, and also have different coordinates than the virtual net positions and the vertices defining the particles of a higher resolution version. The higher resolution version may have more virtual net positions and vertices than the lower resolution version. According to the specifics of the particle subdivision, a set of wavelet filters that allows for a multi-resolution decomposition of a SPIN-based volumetric model, and respectively reconstruction, are further designed as explained below.

[0225] Complex high resolution models can comprise of hundreds of millions of polygons or more, but the technology for real-time display of such complex models still lags behind, due to limited resolution of display devices and limited computation power. Therefore, multi-resolution 3D approaches provided herein, which may optionally work on a region-of-interest (ROI) basis, may provide a practical solution for real-time rendering at a selected resolution level. Since processing power varies by a few orders of magnitude from low power devices with 3D graphics capabilities, like smart phones, to high-end 3D graphics stations, multi-resolution 3D models provided herein may allow for lossless reconstruction at a resolution level or within a ROI selected based on device capabilities.

[0226] Some implementations of the SPIN graphics model may include support for multi- resolution representations that can work on a region-of-interest basis. Embodiments may furthermore implement smooth transformations to allow (i) the decomposition of a SPIN based volumetric model into a hierarchy of lower resolution models while preserving the original shape as accurately as possible, (ii) for animation, morphing, deformation, or special effects, (iii) for representing or encoding of dynamic models, and for any other operations performed on the surface or the volume of the SPIN based volumetric model.

[0227] The following sections describe how to derive a set of wavelet filters to support multi-resolution technologies described herein, and provides an example solution that may be appropriate for some embodiments. The filters described herein may be used to transform a high- resolution model into a hierarchy of gradually lower and lower resolution models, and also for reversing the transformation in order to retrieve the initial high-resolution model. These filters may also allow be utilized to implement hierarchical modeling and animation in some embodiments.

Example: Precision Levels of a Particle

[0228] In some embodiments, SPIN graphics technologies can include mesh subdivision modules 4618 configured to support increasing or decreasing the mesh precision level of a particle. For example, mesh subdivision modules 4618 may configure a device to allow for design or display of SPIN-based volumetric models comprising a plurality of mesh precision levels, ranging from a base precision level to higher precision levels. Mesh subdivision modules 4618 may encode mesh precision data for a SPIN-based volumetric model, allowing the SPIN-based volumetric model to be rendered at any of a plurality of mesh precision levels.

[0229] In some embodiments, augmenting the precision level of one or several of the particles defining a SPIN-based volumetric model may be accomplished by inserting extra vertices to the base mesh at said precision level by subdividing the base mesh using an approach similar to that described in the context of subdivision surfaces, such as, the Catmull-Clark mesh and vertex refinement scheme. The coordinates of these extra vertices may be interpolated from the coordinates of existing particle vertices, and or adjusted to match the target surface of the volumetric model.

[0230] Particles at different precision levels are illustrated in FIGS. 24-26. FIG. 24A illustrates the base mesh of a spherical particle, which is further mapped to a cube in FIG. 24B. In FIG. 24 vertices 2023 are of type V_A, vertices 2021 and 2022 are of type V_B, and vertices 2020 are of type V_c. The base mesh of the particle from FIG. 24 A and 24B may be subdivided through the insertion of extra vertices, such as, 2024 and 2025, yielding the result shown in FIGS. 25A and 25B respectively. In other words, FIGS. 25 A and 25B may illustrate the surface mesh of the particle from FIGS. 24A and 24B at an increased precision level. To provide the increased precision level, the coordinates of the extra vertices may need to be adjusted accordingly. Repeating the process of inserting extra vertices and subdividing the mesh of particle from FIGS. 25 A and 25B may yield the results shown in FIGS. 26A and 26B, respectively. The particle from FIGS. 26A and 26B may yield an even higher precision level compared to the particle of FIGS. 25A and 25B, respectively.

[0231] In the examples from FIGS. 24-26, the base mesh has been designed by connecting the main vertices in radial mode. Nevertheless, the principle described herein may also be applied when the base mesh, or subsequent higher precision level meshes, are designed in transversal mode, or mixed mode. Moreover, a mesh at a higher precision level may be in a different triangulation mode than the base mesh.

[0232] Moreover, in the examples from FIGS. 24-26, the base mesh contains all 26 vertices, which include vertices of type V_A, V_B or V_c. In some embodiments, whereby different vertex sharing configurations are used, the base mesh may comprise less than 26 vertices, as described herein.

Adaptive Precision and Resolution

[0233] In the examples from FIGS. 24-26 the particle's mesh has uniformly been subdivided over the entire particle's surface to increase the precision level. Nevertheless, in some embodiments LOD control modules 4624 may be configured to subdivide a particle's mesh in some areas only, yielding an adaptive precision level of portions of a particle's surface. There are several embodiments where adaptive precision levels are useful, such as: (i) for increasing the density of the mesh only in chosen areas, e.g. in visible parts of the particles for reducing the rendering overhead, and (ii) when displaying the volumetric model at adaptive resolution levels, when merging particles belonging at different resolution levels, the side of a particle that is facing neighbor particles at a higher resolution level may be subdivided to provide a higher number of shared vertices that would match the number of neighbor particles with whom the said particle would need to merge. In such case, some of the extra vertices may become shared vertices.

Example: Particle 's Geometry In Multi-Resolution

[0234] Considering the multi-resolution hyperoctahedron related example, FIG. 27A illustrates a spherically shaped particle that is triangulated in the radial mode and which is shown at the lowest precision level. To approximate the surface of a hyperoctahedron, the particle of FIG. 27A may be deformed into FIG. 27B. Further, another spherically shaped particle illustrated in FIG. 28A, which is also shown at the lowest precision level, yet this time is triangulated in the transversal mode, may be deformed into FIG. 28B, to approximate the surface of the said hyperoctahedron. Any of the particles illustrated in FIGS. 27A, 27B, 28 A, and 28B may be inserted in either the cubic-packing mode virtual net of FIG. 1OB or 1OD, or the hexa-packing mode virtual net of FIG. 1OC or 1OE. For example, particles may be inserted such that the center of a particle overlaps with a center point of a virtual net.

[0235] When the resolution level is increased in the cubic-packing mode, the particles of FIGS. 27A and 28A may be subdivided into 8 particles as shown in FIGS. 29A, 3OA, and 3 IA, respectively. FIG. 29A illustrates 8 particles triangulated in the same radial mode as the particle of FIG. 27A. Similarly, FIG. 3OA illustrates 8 particles which are triangulated in the same transversal mode as FIG. 28A. Further, in order to approximate the surface of a hyperoctahedron, particles of FIG. 29A and FIG. 3OA may be deformed into the particles of FIG. 29B and FIG. 3OB, respectively. FIG. 31 A illustrates the 8 particles of FIG. 29A or 3OA inserted in a higher-resolution virtual net (higher resolution than FIG. 1OB, for example) which may accommodate particles such as those of FIG. 29A and FIG. 3OA. FIG. 31 A provides a front view in which only 4 of the 8 particles of FIG. 29A and FIG. 3OA are visible.

[0236] FIG. 32A illustrates an empty virtual net or a region of a larger virtual net corresponding to FIG. 3 IA. In FIG. 32B, the virtual net of FIG. 32 A is deformed to distribute the virtual net points non-uniformly. The virtual net may be optimized to accommodate a volumetric model. For example, the virtual net illustrated in FIG. 32B may be optimized for the hyperoctahedron illustrated in FIG. 3 IB. FIG. 3 IB illustrates the particles of FIG. 31 A inserted in the virtual net of FIB. 32B, where coordinates of the particle vertices are adjusted to produce the hyperoctahedron shape illustrated in FIGS. 29B and 3OB.

[0237] When the resolution level is increased in the hexa-packing mode, the particles of FIGS. 27A and 28A may be subdivided into 4 particles as shown in FIGS. 29C and 3OC, respectively. FIG. 29C illustrates 4 particles triangulated in the same radial mode as the particle of FIG. 27A. Similarly, FIG. 3OC illustrates 4 particles which are triangulated in the same transversal mode as FIG. 28A. Further, in order to approximate the surface of a hyperoctahedron, particles of FIG. 29C and FIG. 3OC may be deformed into the particles of FIG. 29D and FIG. 3OD, respectively. FIG. 33 A illustrates the 4 particles of FIG. 29C or 3OC inserted in a higher-resolution virtual net (higher resolution than FIG. 1OC, for example) which may accommodate particles such as those of FIG. 29C and FIG. 3OC. FIG. 33 A provides a frontal view of the 4 particles of FIG. 29C and FIG. 3OC.

[0238] FIG. 34A illustrates an empty virtual net or a region of a larger virtual net corresponding to FIG. 33 A. In FIG. 34B, the virtual net of FIG. 34A is deformed to distribute the virtual net points non-uniformly. The virtual net may be optimized to accommodate a volumetric model. For example, the virtual net illustrated in FIG. 34B may be optimized for the hyperoctahedron illustrated in FIG. 33B. FIG. 33B illustrates the particles of FIG. 33 A inserted in the virtual net of FIB. 34B, where coordinates of the particle vertices are adjusted to produce the hyperoctahedron shape illustrated in FIGS. 29D and 3OD.

[0239] Furthermore, when resolution level may be increased again, for example by subdividing the 8 particles of FIG. 29A or FIG. 3OA into 64 particles, in the cubic-packing mode, or by subdividing the 4 particles of FIG. 29C or FIG. 3OC into 16 particles, in the hexa-packing mode. The accuracy of the approximation of the surface of the hyperoctahedron may increase with the resolution level or respectively with the number of particles used in the representation.

Subdivide & Reunite Operations on Particles

[0240] In some embodiments, SPIN graphics technologies can include subdivide and reunite modules 4617 configured to support subdivide and reunite operations. FIG. 35 illustrates transformation between a set of particles at a first resolution level and a set of particles at a second resolution level. For simplicity FIG. 35 may be considered a one dimensional set of particles. Embodiments may be configured to subdivide a first set of particles 254 (bottom row) at a first resolution level (RL), when the RL increases, into a larger set of particles 250 (top row) to provide a second, higher RL. Conversely, when the RL decreases, embodiments may be configured to reunite the set of particles 250 into the smaller set of particles 254. The arrows 251 and 252 show the correspondence between an ancestor particle "M" from the first set of particles 254 from the lower RL and its descendant particles "S" and "C" from the second set of particles 250 from the higher RL. Each dot such as 255 denotes the centroid of a particle. As previously described, every centroid overlaps with a position within the virtual net.

[0241] To simplify the explanation herein, the particles are shown as boxes in FIG. 35, such as particle 249, while in general a particle may have any arbitrary shape, as described herein. [0242] Please note that the two-dimensional (2D) and three-dimensional (3D) cases may be generalized from the one-dimensional case. In the 2D and/or 3D cases, the same operations can be performed for each direction, either simultaneously or selectively.

[0243] In some embodiments, an ancestor particle from 254 may subdivide into "n" descendant particles when the RL increases, while "n" descendant particles from 250 may reunite into 1 ancestor particle from 245 when the RL decreases, where "n" is at least 2. The examples and the wavelet filters described below consider that "n" equals to 2, for efficiency of the teachings herein.

[0244] At the limits of the interval, i.e. the first and last particles from 250, referred to as limit particles, some embodiments may preserve only a single particle when increasing the RL, i.e. there may be no subdivision into 2 (subdivision into "n" in general case) and there may be no reuniting either, but only repositioning. The reason why one would consider treating the limit particles differently in some embodiments is because, the limit particles may be considered to be outside the object (at least when the object is closed), hence they may be considered to be void particles, and so, there may be no benefit from increasing the number of the outside (void) particles since they do not contribute to the shape of the object, while they may take up some storage memory.

[0245] To give an example, let's consider a model that comprises of "c" particles 254 at the lowest RL (I = 0), whereby 2 of them are limit particles (and lying outside of the object). The number of particles at an arbitrary RL (I = k) is n = c X 2^l, whereby m = 2^l+1 are outside particles located at the limit of the object. If the limit particles would not subdivide, then at the said RL (I = k) there will be n = (c — 2) X 2^l + 2 particles, whereby only 2 of them are outside particles. This way one avoid allocating a number of 2^l+1 — 2 particles, which is a quite significant number.

[0246] Let's insert some numbers into these equations: if c = 5 and I = 7, then, when all particles subdivide there will be n = 5 x 27 = 640 particles with m = 256 outside particles, while, when the limit particles do not subdivide there will be n = 3 x 27 + 2 = 386 particles whereby only 2 of them are limit particles. This example shows that during the subdivision almost 2 / 3 of the particles would get wasted as outside (void) particles.

[0247] It may be not necessary to handle the subdivision of the limit particles differently from the others, yet, to optimize memory usage it may be desirable to avoid subdividing the limit particles when the RL increases, while repositioning them instead. Designing the Wavelet Filters for SPIN

[0248] Furthermore, with reference to the subdivide and reunite modules 4617, in selecting formulas used to derive the wavelet filter coefficients that establish the relationship between the centroids of the ancestor and descendant particles, respectively the relationship between the virtual net positions at consecutive RLs, embodiments may account for how the subdivide or reunite operations may be performed on and with the particles. Namely, during the subdivide operations, which may be carried out when the RL increases, the new descendant particles may to be repositioned with respect to the positions of the ancestor particles in such a way such that the shape of the underlying volumetric object is refined while preserving the features of the lower RL. Reversely, when the RL decreases the detail decreases while the overall shape is preserved.

[0249] The formulas and wavelet filters that support the said subdivide and reunite operations can be grouped into two groups:

• The "analysis filters" which define/describe the reunite operations between particles, which lead to a coarser definition RL of a SPIN-based volumetric model.

• The "synthesis filters" that define/describe the subdivide operations and which allow to reconstruct the high definition RL of a SPIN-based volumetric model.

[0250] Let's label the particles at the higher RL as "A" to "/", and those belonging to the particles at the lower RL as "AT" to "5", as illustrated in FIG. 35.

[0251] To simulate the natural behavior of the particles during the subdivision, some embodiments may impose that whenever two adjacent particles "N" and "P" subdivide, i.e. into (D, F} and (F, G}, the centroids of the descendant particles "F" and "F" will be distributed such that the distance between the centroids of "F and F" is 1/2 of the distance between the centroids of "N and P". This further implies that each of the distances between the centroids of "N and F" and of "F and P" are 1/4 of the distance between the centroids of "N and P". This also implies that the distances between the centroids of "N and F" and of "F and P" are 1/2 of the distance between "F and F", as illustrated in FIG. 35.

[0252] Considering the above constraints, some embodiments may utilize the following formulas for deriving the centroid positions of the particles "C", "D", "F" and "F" from "M", "N" and "P". Please note that in the equations that follow the letters "C", "D", "F", "F", "M", "N" and "P" denote the position of the centroids of the particles with the same label. {Low Pass Synthesis Left) {Low Pass Synthesis Right)

(3N + P) . _J7 _ {N + 3P) _ 4 4

[0253] The inverse formula, deriving the centroid positions of the lower RL particle "N" from the higher RL particles "C" and "D" or "£"' and "F" can be obtained by solving the above equations, which is:

{Low Pass Analysis)

N = 4C-3M; _{N =} (^{4D ~ M}) _{; OV}M = 4D -3N; (0.2)

(A F - P\

N = ± ^J-; ov P = 4E-3N; N = 4F -3P;

[0254] Further, by replacing "M" in the first equation on the left with M = 4D — 3N and "P" in the second equation on the right with P = 4E — 3 N, one obtains:

{Low Pass Analysis Left) {Low Pass Analysis Right)

8N = 12E -4F; 8N = 12D -4C; (0.3)

_{N =} M-_{L N}J-Rz£.

2 2

[0255] In the following we define the term sample as the particle's centroid position, respectively a position in the virtual net.

[0256] According to formula (0.3) the position of sample "N" can be estimated both from the samples on the left ("C" and "D") and from those on the right ("F" and "F"). This may suggest that one can derive a more general formula by combining the above "Left" and "Right" equations into equation (0.3):

{Low Pass Analysis) : N = ; (0.4)

[0257] From equation (0.4) one can derive the following filter coefficients:

{Low Pass Analysis) : I --,-,-,-- [, or (-0.25,0.75,0.75,-0.25) (0.5)

[ 4 4 4 4j ^l '

[0258] If one makes the analogy with the format of the bi-orthogonal wavelet filters, which is shown in equation (0.6), one may be tempted to assign "α = 0.25" and "/? = 0.75", and so to obtain the filter coefficients for the direct and inverse wavelet transform that would satisfy the constraints imposed for the SPIN method. Please note that the bi-orthogonal wavelets are smooth reversible transformations, as shown below:

(Low Pass Analysis Filter): {—a, β, β, —a] c (aa β β β β a cη) (High Pass Analysis Filter) : J-, -7, _T, ~ τ}

(a β β a_} <⁰-⁶>

(Low Pass Synthesis Filter) : j- , - , - , - 1

(High Pass Synthesis Filter): {a,β, —β, —a}

[0259] Further, we may need to verify whether the above filter coefficients guarantee a lossless reconstruction of the signal, which in our case is the distribution of the particles. It will be demonstrated below that embodiments may utilize either of two solutions, either to scale up both "α = 0.25" and "β = 0.75" or to slightly modify formula (0.6).

Matching the constraints imposed on bi-orthogonal filters with the ones imposed for SPIN

[0260] Equation (0.7) gives the values of the samples "M" to "R" as derived using the "Low Pass Analysis Filter" from equation (0.6):

[0261] Similarly, by applying the "High Pass Analysis Filter" on the same samples embodiments may obtain the detail data "Δ" (see equation (0.8)) that may be used when reconstructing the higher RL samples from the lower RL samples.

. ( a . β _n β _, a _ Δ_Br = \ —x A - — x B + — x C x D

[0262] As illustrated by equation (0.7), a sample "M" from a lower RL may be derived using the low pass analysis filter as a weighted average of its neighbor samples "A, B, C, D" at the higher RL. In addition, the detail Δ_βC at sample "M" may be computed using the high pass analysis filter, from equation (0.8), as a weighted difference of its neighbor samples "A, B, C, D" at the higher RL. Moreover, as result of this transformation, both samples "S" and "C" are symmetrically positioned with respect to sample "M" and so the details of both samples "S" and "C" have the same magnitude Δ_βC but different signs. Accordingly, these formulas enforce a downward dependency between the distributions of the samples at lower RLs with respect to the samples at the higher RLs.

[0263] Further, to reconstruct the higher RL samples "A" to "/" from the lower RL samples embodiments may apply the inverse operation, that is, to apply the filtering with the "Low Pass Synthesis Filters" on the lower RL samples and sum this result with the output of the filtering on the detail data with the "High Pass Synthesis Filters". Accordingly, these formulas enforce an upward dependency between the distributions of the samples at higher RLs with respect to the samples at the lower RLs. This procedure is elaborated in more detail below. (Low Pass Synthesis) :

(Low Pass Synthesis Left) (Low Pass Synthesis Right)

(β a) (a β_

\l ' 2) Xl ' 2. (0.9) (High Pass Synthesis): {a, β, -β, -a}

(High Pass Synthesis Left) (High Pass Synthesis Right) {β, -a} {a, -β}

[0264] Please note that, the notations "Left" and "Right" used for the "Analysis and Synthesis" filters are not standard scientific language. They have been used in this text since they describe in a more intuitive way whether it is the "Left" or "Right" sample that is transformed during the filtering. Typically, the literature uses "Even" and "Odd" samples instead, which in our case could be misleading because the sample that is treated as even sample has an odd position due to the fact that the first sample is treated differently from the rest. The filter coefficients for the "Left" and "Right" samples are usually different, as shown by equation (0.9).

[0265] So, embodiments may apply the "Synthesis Filtering" on the low resolution samples "N" and "P" and on the detail data "Δ_DE" and "Δ_FG" (see equations (0.10)) using the filters from equation (0.9) to obtain the result from equation (0.11) when employing the "Left" filters, and to obtain the result from equation (0.12) when employing the "Right" filters.

(Analysis)

P = {-aχE + βχF + βχG-aχH) (0.10)

Λ *FG - -_xE-^xF + ^xG--xH

(Synthesis Left)

+ βχD + βχE-aχF) + — χ(-aχE + βχF + βχG-aχH) +

βx(-xC-^-xD + ^-xE--xF}-ax(-xE-^-xF + ^-xG--xH}= (0.11)

{2 2 2 2 J {2 2 2 2 ) +

(β²-a²)xE;

(Synthesis Right)

^_{xN +} £χPy(aχA_DE-βχA_PG) =

— χ(-aχC + βχD + βχE-aχF)+-t-χ(-aχE + βχF + βχG-aχH) +

[0266] According to equations (0.11) and (0.12), in order to have perfect reconstruction of the higher RL samples from the lower RL samples and the detail data, {a, /?} may satisfy following relation:

[β² -a²) = \ (0.13)

[0267] The values that we found were "α = 0.25" and "β = 0.75" (see equation (0.5)). In order to have these values satisfy equation (0.13) they may be scaled up, because:

(0.75² - 0.25²) = 0.5 ≠ 1 (0.14)

[0268] To find the appropriate scaling factors, embodiments may to solve the following equations:

(/?² - a²) = 1 and β = 3 x a, which implies that:

1 3 a' = — = 0.35355339 ... and /?' = — = 1.06066017 ...

V8 V8 ₍0.i5) a' β' ,- scale = — = — = V2 = 1.41421356 ... a β

[0269] As shown by equation (0.15), in order to achieve a perfect reconstruction, {α', β'} should be used instead of {a, /?}. Nevertheless, because {a, β] would be the filter coefficients that properly describe the subdivision operation and the distribution of the samples, after applying the wavelet analysis, the lower RL samples may be scaled down by Λ/2. Reciprocally, before reconstructing the higher RL samples the lower RL samples may be scaled up with Λ/2.

[0270] One may notice that the wavelet filter coefficients obtained by equation (0.15) are the coefficients of the bi-orthogonal wavelet filter known in literature as "bior31", which has a smooth behavior.

[0271] The "bior31" wavelet filter could be one of the appropriate filter to be used for the multi-resolution analysis and reconstruction of 3D models encoded with SPIN, but one has to consider that the samples need to be scaled down or up with Λ/2 after and before applying the wavelet transform.

[0272] Nevertheless, there is another solution that may be appropriate in some embodiments, and which produces the same smooth distribution as the "bior31" filter. These filters are shown below: (Low Pass Analysis Filter): {—a, β, β, —a} (High Pass Analysis Filter): {a, —β,β, —a}

(Low Pass Synthesis Filter) : {a, β, β, a} (High Pass Synthesis Filter): {a,β, -β, -a}

[0273] If one rewrites the generic "Analysis" and "Synthesis" filters equations from (0.6) as in (0.16), than the condition for perfect reconstruction of the higher RL samples from the lower RL becomes:

2x (β² - a² ) = l (0.17)

[0274] This time, when replacing "α = 0.25" and "β = 0.75" one obtains a perfect reconstruction:

2x (0.75² - 0,25²) = 2 x 0.5 = l (0.18)

[0275] Let's call the filter described by equation (0.16) the "SPIN" filter (see equation (0.19)).

(Low Pass Analysis Filter): {-0.25, 0.75, 0.75, -0.25} (High Pass Analysis Filter): {0.25, -0.75, 0.75, -0.25}

(Low Pass Synthesis Filter): {0.25, 0.75, 0.75, 0.25} (High Pass Synthesis Filter): {0.25, 0.75, -0.75, -0.25}

[0276] The difference that appears when employing the "SPIN" filter instead of the "bior31" filter may be in the magnitude of the lower RL samples (as explained above) and detail data. The detail data obtained with the "SPIN" filters may be scaled up with a factor of Λ/2. But since all the detail coefficients may be scaled with the same factor, it may be just a matter of dividing by Λ[2 in order to yield the same detail data as with the "bior31". Still, the fact that the detail data might be scaled up or down with respect to a reference need not affect the behavior of the distribution of the particles.

[0277] Both the "SPIN" and "bior31" filters may be appropriate in some embodiments. When employing the "SPIN" filter, embodiments need not scale down the lower RL samples after the decomposition, and need not scale them up before reconstructing the higher RLs from lower RLs. [0278] In addition, the "SPIN" filter (see equation (0.19)) may be more appropriate than the "bior31" filter (see equation (0.20)) for some embodiments, because the "SPIN" filter may guarantee a mathematically lossless reconstruction. The "SPIN" filter coefficients a = 0.25 and β = 0.75 are bounded, while for the "bior31" filter a' = 0.35355339 and /?' = 1.06066017 (shown below) are not bounded (a' and β' have an infinite number of digits after the decimal point). (Low Pass Analysis Filter): {-0.3535 ... , 1.0606 ... , 1.0606, -0.3535 ... } fθ.3535 ... 1.0606 ... 1.0606 ... 0.3535 ..Λ

(High Pass Analysis Filter) : j-

2 2 2 2 rθ.3535 ... 1.0606 ... 1.0606 ... 0.3535 ..Λ ^°²⁰^

(Low Pass Synthesis Filter) : j , , , 1

(High Pass Synthesis Filter): {0.3535 ... , 1.0606 ... , -1.0606 ... , -0.3535 ... }

Reconstructing, the particle 's centroid positions at the limits

[0279] As mentioned above, although not mandatory, embodiments may treat the first and last particles in a particular way during the subdivision, in order to save memory. These particles may be not subdivided when increasing the RL, and so, there may be no need to reunite them when decreasing the RL. Instead, particles at the limits may be repositioned during the subdivision. (Low Pass Analysis Left) (Low Pass Analysis Right)

{2xβ,-2x a} {-2x a,2xβ}

(Low Pass Synthesis Left) (Low Pass Synthesis Right)

{#«} {">β) _{(1 1)}

(High Pass Synthesis Left) (High Pass Synthesis Right)

{θ,-2α} {2α,0} with α = 0.25 and β = 3a = 0.75

[0280] As illustrated in equation (1.1), for the limit samples only the "Low Pass Analysis Filters" may be employed in order to obtain the RL limit samples, e.g. sample "K-" may be derived from samples "A" and "S" - the detail data for the limit samples is "0". For the first sample we may employ the filters with the labels "Left", while for the last sample we need to employ the filters with the labels "Right".

[0281] Please notice that, since only half of the filter coefficients are used, they are scaled by "2" with respect to the filters from (0.19). [0282] The proof that the filters from equation (1.1) allow a perfect reconstruction of the higher RLs samples from lower RLs samples, may be given in equation (1.2) for the limit sample on the left (first sample), and in equation (1.3) for the limit sample on the right (last sample).

(Analysis Left)

K = (2βxA-2axB)

Δ,=0

(Synthesis Left) (1.2)

A = βχK + aχM + 0χA_Λ-2aχA_BC = = 2β² x A-2aβχB -a²x A + aβxB + aβxC -a²χD - -cc²χA + aβχB-aβχC + a²χD = (2β² -2cc²)χA replacing a = 0.25 and β = 0.75

(2β²-2a²)xA = 2\—- — )xA = A 1 ^; U6 16 J

(Analysis Right)

A_j =O

(Synthesis Righ) (1.3)

J = ccxR + βxS + 2ccxA_HI =

= -cc²χG + aβχH + aβχI-a²χJ-2aβχI + 2β²χJ + cc²χG-ccβχH + aβχI-a²χJ = {2β²-2a²)χJ replacing a = 0.25 and β = 0.75

[0283] Please note that besides the SPIN filters, other filters that are compatible with the subdivision approach described above can be used in some embodiments for the analysis and synthesis of a multi-resolution SPIN-based volumetric model. Multi-Resolution Distribution of Particles

[0284] FIG. 36 provides 2D views of an example distribution of samples at 5 different resolution levels, as may for example be implemented in some embodiments. The dots displayed in each image represent the samples. The lines connecting these dots are there for guidance only, and they illustrate how the samples relate to each other. As mentioned previously, a sample may be a generic term for a virtual net position for a particle's centroid. In the examples from FIG.36 the samples at the limit are not subdivided when the resolution increases, however they are repositioned.

[0285] FIG. 36A illustrates the samples of the lowest RL (λ = 1) distributed uniformly. Further, FIG. 36B shows in addition the samples of the following higher RL (λ = 2). FIG. 36C illustrates just the samples of the said RL (λ = 2). Furthermore, FIG. 36D exemplifies the samples of said RL (λ = 2) and of the following higher RL (λ = 3). Next, FIG. 36E illustrates only the samples of said RL (λ = 3). Finally, FIG. 36F illustrates the samples of the lowest RL (λ = 1) and the ones of the highest RL (λ = 5).

[0286] Please note that there may be a hierarchical dependency between the distributions of the samples of different RLs, for example according to the formulas expressed through the "SPIN" filters described herein. In FIGS. 36A-36F, the samples at each RL are uniformly distributed, however other embodiments may be non-uniform.

[0287] In some embodiments, a change in distribution of the samples at a certain RL may affect the distribution of the samples both at the lower and higher RLs, such that the topology of the shape may be consistently preserved across the RLs. For example, FIGS. 37A-37F correspond to FIGS. 36A-36F, wherein at least one of FIGS. 36A-36F is modified to produce a corresponding distribution in FIG. 37, which triggered the hierarchical update of the particles of the lower and/or higher RLs represented by the remaining distributions illustrated in FIG. 37.

[0288] Furthermore, at any given moment when displaying a SPIN based model at a constant RL (A = /c), i.e. a same RL over the entire model, then in some embodiments only the particles of the said RL (1 = k) may be visible, as shown in FIGS. 36A, 36C, 36E, 37A, 37C, and 37E. Nevertheless, when the model may be displayed with an adaptive RL, in which some regions may have a higher RL (higher resolution) while other regions may have a lower RL (lower resolution), then particles belonging to different RLs may be displayed at the same time, for example by simultaneously displaying two or more regions side-by-side and at different levels of detail. Extending the SPIN Filters for Modeling and Animation

[0289] In some embodiments, SPIN graphics technologies can include modeling and animation modules 4619 configured to support modeling and animation using particle-based graphics technologies. Applying the wavelet analysis in the classical way on a ID data set comprising n = 2k samples, using the SPIN filter (or other said compatible filters), it produces k approximation samples, which represent the lower resolution level (RL) samples, and it also produces k detail samples. Accordingly, in some embodiments, the distribution of the said k approximation and detail samples may be dependent on the distribution of the said 2k samples from the higher RL, and so there may be a downward dependency. In some embodiments, there may be also an upward dependency since the distribution of the said original ID data set can be reconstructed by applying the wavelet synthesis on the k approximation samples and k detail samples. Some embodiments may be configured to repeat the wavelet analysis over and over again on the approximation samples obtained at each step, and so yielding a multi-resolution decomposition of the distribution of the samples defining a SPIN-based volumetric model, which may be referred to as multi-resolution decomposition of the SPIN samples.

[0290] The said downwards dependency may be a factor in obtaining a multi-resolution decomposition of the SPIN samples, whereby the distribution of the samples at each RL may preserve as faithfully as possible the distribution of the samples at the highest RL. Logically, the lower the RL the coarser the approximation may be.

[0291] Since the detail values derived at each RL may usually be lower in magnitude than the coordinates of the positions of the SPIN samples at the highest RL, some embodiments may save the multi-resolution decomposition of the SPIN samples rather than storing the SPIN samples at the highest RL. This approach may be more memory-efficient. A multi-resolution decomposition of the SPIN samples may comprise the approximation samples at the lowest RL, the detail samples at the lowest RL, and the detail samples at all the higher RLs up to the highest RL minus 1.

[0292] The said upward dependency may be utilized in some embodiments when reconstructing the SPIN samples at the highest RL, from the multi-resolution decomposition of the SPIN samples.

[0293] The downward dependency and especially the upward dependency may be utilized in some embodiments when performing hierarchical modeling and animation. In those situations embodiments may be configured such that whenever the position of a sample at one of the lower RLs is altered it may be reflected at all the higher RLs.

[0294] Still there may be situations when one desires that any changes to the position of a sample may be kept contained within the RL the sample belongs to, or it may be passed to a limited set of neighbor RLs but not to the entire hierarchy of RLs.

[0295] Referring back to the ID example, let's consider an extended wavelet transform whereby the wavelet analysis may be modified in such a way that when applied to the ID data set comprising n = 2k samples at the highest RL (λ), using the SPIN filters (or other said compatible filters), it produces k approximation samples, which represent the samples of the lower resolution RL (λ — 1), and it also produces 2k detail samples. In this case embodiments may have extra flexibility to modify the distribution of the samples at any RL without affecting the distribution of the samples of the other RLs. Nevertheless, some of the details may have to change in order to allow reconstructing one RL (lower or higher) from another RL (higher or lower) accurately.

[0296] Finally, a positive implication of producing 2k detail samples when generating the lower RL (λ — 1) may be that every of the 2k samples from the higher RL (λ) has a detail value associated with it, and so the position of any sample can be modified without requiring to update the distribution of other samples, from the same or different RLs, it would only require to update the value of the detail associated with the said sample.

[0297] FIG. 38 illustrates an example multi-resolution data set. In some embodiments, data structures including samples that correspond to one or more RLs may be stored on a computer- readable medium. The data structures may include for example particle centroid and/or vertex locations (stored for example as coordinates in a virtual net) at each RL. Modules for authoring, displaying, and navigating between the various RLs may be included in some embodiments.

[0298] To illustrate the different hierarchical modeling possibilities, consider an example of a multi-resolution decomposition of a 2D distribution of SPIN samples. FIG. 38 shows 3 consecutive RLs of samples overlaid on top of each other, whereby the samples at each RL are distributed according to the SPIN filters described herein. In the case shown in FIG. 38 all the samples at each RL are uniformly distributed. The samples such as 258 belong to the lowest RL (λ = 1), the samples such as 257 belong to intermediate RL (λ = 2), and the samples such as 256 belong to the highest RL (λ = 3). Samples similar to 258, 257, and 256 and similar distributions are illustrated separately in FIGS. 36A, 36C, and 36E, respectively. [0299] When sample "J4" from RL (λ = 2) may be repositioned, for example by user interaction with an authoring module 4601 configured to create and/or modify a multi-resolution SPIN-based volumetric model, depending on the modeling mode, embodiments may be configured to trigger any of a variety of updates, as follows:

[0300] 1. In the default mode, the authoring module 4601 may be configured to update the distribution of the lower and higher RLs according to the analysis and synthesis wavelet filters. In this mode, the repositioning of sample "A" may trigger the update, according to the analysis filter, of the positions of the ancestor samples "R, S, T and U" from RL (Λ = 1), with which sample "A" has a downward dependency. Further, the update of the said ancestor samples may trigger update of the detail values for the samples from RL (Λ = 2), including samples "X, Y and Z", which have an upward dependency with the said ancestor samples. Furthermore, all the samples from RL (Λ = 3), namely the following 16 samples "S, C, .. . , P and Q", which are upward dependent on sample "A" may be repositioned according to the synthesis filters.

[0301] 2. In a resolution-level isolation mode, as illustrated in FIG. 39, the authoring module 4601 may be configured to isolate a RL by not performing the downward and upward updates of the positions of the samples. For example, repositioning sample "A" may involve the update of its detail value towards the samples "R, S, T and U" from the lower RL (Λ = 1), and in some embodiments may further involve the update of the detail values (but not positions) of one or more additional RL 's, for example, detail values for samples from RL (Λ = 3), namely the following 16 samples "S, C, .. . , P and Q", which are upward dependent on sample "A" may be updated.

[0302] 3. In a downward update isolation mode, as illustrated in FIG. 40, the authoring module 4601 may be configured to isolate RLs that are downward of an updated RL by not performing the downward updates of the positions of the samples. This mode may be used for example when the downward update of the positions of the samples is temporarily not desired. Referring to FIG. 40, repositioning sample "A" may involve the update of its detail value towards the samples from the lower RL (Λ = 1) with which sample "A" has a downward dependency, and may further involve the update of the positions of samples from RL (Λ = 3), namely the following 16 samples "S, C, .. . , P and Q", which are upward dependent on sample "A".

[0303] 4. In an upward update isolation mode, as illustrated in FIG. 41, the authoring module 4601 may be configured to isolate RLs that are upward of an updated RL by not performing the upward updates of the positions of the samples. This mode may be used for example when the upward update of the positions of the samples may be temporarily not desired. Referring to FIG. 41, repositioning sample "A" may involve the update of the positions of the ancestor samples "β, S, T and U" from RL (λ = 1) with which sample "A" has a downward dependency, and the update of the detail values (but not positions) of samples from RL (λ = 3), namely detail values of the samples "S, C, . .. , P and Q", which are upward dependent on sample "A" may be updated.

[0304] Please note that since each sample has a detail value associated with it, any combination of the scenarios presented above may be possible, since there may be always the choice between updating the position of a sample, updating its associated detail value, or both of them.

[0305] FIG. 42 continues the example from the default mode embodiment discussed above, by repositioning the sample "A" back to its initial position from FIG. 38, while having the upward update of the positions of the samples from RL (Λ = 3) enabled and the downward update of the positions of the samples from RL (Λ = 1) disabled. Accordingly, the positions of the samples "R, S, T and U" from the lower RL (Λ = 1) are not changed only their corresponding detail values are updated, and the positions of the samples from RL (Λ = 3) are updated consistent with the changes in the position of sample "A".

Applying the Flexible Approach to 3D

[0306] Furthermore, with respect to modeling and animation modules 4619, FIG. 43 illustrates a cubical region of a 3D distribution of SPIN samples. Sample P belongs to RL (Λ = k), while samples "A, B, C, D, E, F, G and H" belong to the lower RL (Λ = k — 1). The other points "/,/, K, L, M and N" are intermediate values, which embodiments may be configured to compute using formula (1.4).

3A + B 3C + D 3E + F 3G + H

1 —

4 '

31 + K 9A + 3B + 3E + F

M =

4 16

(1.4)

3J + L 9C + 3D + 3G +H

N =

4 16

3M + N 27A + 9B + 9C + 9E + 3D + 3G + 3F + H

P - 4 64

[0307] Considering a modeling scenario when the position of one of the samples

"A, B, C, D, E, F , G and H" from RL (Λ = k — 1) may be altered, for example by a user interaction with a User Interface (UI) exposed by authoring module(s) 4601 and/or User Interface modules 4603, an authoring module 4601 may be configured to use the formula (1.4), which is the "Low Pass Synthesis" generalized to 3D, to calculate the position of sample P of RL (λ = k) based on the position of the said 8 samples of the lower RL (λ = k — 1).

[0308] Formula (1.4) can be extended in some embodiments to allow more flexibility by introducing the details component "Δ", as illustrated in FIG. 44. If P is the actual position of the predicted sample P, then the detail component "Δ" is the vector pointing from P to P. Considering that sample A was repositioned, an authoring module 4601 may be configured to change the prediction of the positions of the descendant samples at RL (λ = k), and so, for each of the descendant particles either their position or their detail value "Δ" may be updated in a similar way as exemplified for sample P ^'.

[0309] Hence formula (1.4) can be generalized as:

27A + 9B + 9C + 9E + 3D + 3G + 3F + H , ₄

P' = Δ + P = Δ + (1.5)

64

[0310] Furthermore, considering the modeling scenario when sample P' at RL (λ=k) is repositioned, given the samples "A, B, C, D, E, F, G and H" from the lower RL (Λ = k — 1), an authoring module 4601 may be configured to find a detail component "Δ" by reversing formula (1.5) as:

27A + 9B + 9C + 9E + 3D + 3G + 3F + H

A= P' - P = P' (1.6)

64

[0311] Alternatively, when sample P' at RL (Λ = k) is repositioned (for example by a user via an authoring module 4601 UI), instead of updating the detail component "Δ" an authoring module 4601 may update the position of the said ancestor samples at RL (λ = k — 1), as illustrated in FIGS. 45A and 45B. To be noted that, FIGS. 45A and 45B represent the same cubical region of a 3D distribution of SPIN samples, whereby for readability purposes the samples have been split among these two figures.

[0312] Using formula (1.7), which may be the "Low Pass Analysis" generalized to 3D, an authoring module 4601 may predict the position of sample A of RL (λ = k — 1) based on the position of the samples "P', Q', R', S', T', U', V and W" belonging to the higher RL (λ = k). In formula (1.7), and also in FIGS. 45A and 45B, the points "P, Q, R, S, T, U, V and W" may be the positions of the samples "P', Q', R', S', T', U', V' and W" minus their corresponding detail vectors

"Δ". 3P - Q U 3R - S 3V - W

B -- r — 3T -

—, D F —

2 ' 2 2 ' )

2

3B - D 9P - - 3Q - - 3R + S

F =

2 4 r - 3C - E 9T - - 3U - - 3V + W

2 4 (1.7)

3F - G 27 P - 9Q - 9R - - 9T + 3S + 3U + 3V - W

A -

2 8 with P = P' - A_P; Q = Q' - A_Q; R = R' - Δ_R; S = S' - A₅;

T = T' - A_T; U = U' - A_υ; V = V' - A_V; W = W' - A_W; Extra Features

[0313] Various embodiments may also provide one or more module(s) such as: (i) cross section modules 4631 configured to display cross-sections through the SPIN-based volumetric model, (ii) region selection modules 4633 configured to display only selected regions of particles, (iii) membrane selection modules 4622 configured to choose which of the membranes to display, and (iv) volume/surface are computation modules 4614 configured to compute a SPIN-based volumetric model's surface area and volume in totality, for regions of interest or individual particles, and for selected membranes. Lastly, but not exclusively, embodiments may provide dynamics modules 4627 configured to observe and encode the dynamics of a given SPIN-based volumetric model.

Authoring Applications: Setup of the particle network & virtual net

[0314] In some embodiments, SPIN graphics technologies can include setup modules 4626 configured to set up a SPIN representation. At any given resolution level the setup of a SPIN representation may comprise (i) deciding upon a packing mode, (ii) choosing one or more vertex sharing configuration, and optionally specifying them at different conceptual levels, (iii) setting a triangulation mode for the surface mesh, i.e., radial, transversal or mixed, and optionally specifying the triangulation mode at different conceptual levels, and/or (iv) specifying the average particle size, respectively the average distance between two particles, or the maximum allowed reconstruction error, respectively the desired reconstruction accuracy. Optionally, the boundary of regions for particles can also be defined. However, particles can be grouped into regions at a later stage in some embodiments. Setup modules 4626 may be configured to implement each of the setup operations described herein, optionally in cooperation with various of the other modules disclosed herein. [0315] Setup operations (i) and (iv) allow embodiments to design a virtual net for a SPIN representation, whereby the virtual net comprises of a set of points that can be occupied by particles, and the distribution of these points within the said SPIN representation. Thus the word "virtual" in "virtual net" relates to the fact that the virtual net acts as a placeholder, and that points in the virtual net need not physically exist when particles are not occupying them. Once particles are inserted at virtual net points, they may form a particle interconnection network. Moreover, if a SPIN representation is multi-resolution, the particles may in addition form a lineage network. Further, in some embodiments the design of the virtual net may guarantee that neighbor particles are related to each other according to the chosen packing mode.

Particle size versus reconstruction error

[0316] In some embodiments, SPIN graphics technologies can include particle size determination modules 4615 configured to determine particle sizes in a SPIN-based volumetric model. FIG. 56 illustrates an example technique in which a particle size determination module 4615 may be configured to determine an average size of a particle, given an absolute error δ_D along each of the directions D of a virtual net, as follows. Considering that a particle 5601 is inscribed within a multi-dimensional ellipsoid 5600 such that all of the particle's vertices 5602 lie on the surface of the said ellipsoid 5600, then, the error δ_D 5605 represents the maximum distance measured in a normal direction from the surface of the said ellipsoid 5600 to the surface of the particle 5601 along each of the directions D of the virtual net. A two-dimensional cross section may be made through a multidimensional ellipsoid circumscribing a particle, as illustrated in FIG. 56. The absolute error δ_D 5605 and the radii r_D 5606 may be measured along two of the ellipsoid's directions 5603 and 5604, as may the angle oc which may be averaged to 45°, a value that is precise when the ellipsoid is a sphere. In such a scenario the formula to compute the radii may comprise the following:

[0317] Further, given the linear or curvilinear size L_D that a SPIN-based volumetric model has along each of the directions D of the virtual net and the size of a particle defined by the radii r_D of the said ellipsoid circumscribing the said particle, one can compute the number of virtual net points g_D along each of the directions D of the virtual net as:

L_D 9D = —

^TD [0318] Accordingly, given any particle P₁ that is inserted at certain point within the virtual net VN₁, the size of particle P₁ may be bounded by its neighbor virtual net points, namely 26 neighbor points when considering the 26 vertex sharing configuration. Thus, if particle P₁ would need to be expanded beyond the coordinates of one of the neighbor virtual net point VN₂, then either the virtual net point VN₂ may be repositioned such that the particle P₁ remains bounded by all its neighbor virtual net points, or an additional particle P₂ may be inserted at virtual net point VN₂ and may be merged with particle P₁ according to the vertex sharing configuration. The latter assumes that no other particle already existed at point VN₂.

Particle Distribution

[0319] In some embodiments, SPIN graphics technologies can include virtual net distribution module(s) 4630 configured to calculate a distribution of virtual net points for a SPIN- based volumetric model. Besides determining the average size of a particle and the number of virtual net points along each of the directions of the virtual net, as described above, embodiments may determine how to distribute virtual net points to yield the best accuracy. Some embodiments may be configured to distribute virtual net points uniformly, for example as illustrated in FIGS. 1OA, 3 IA, 32A, 33A, and 34A, which may have the advantages that the virtual net may be simple to design and that it may be straightforward to store. Yet, when reconstructing arbitrary shaped volumetric models, having the virtual net points distributed uniformly, which implies that all the particles have the same average size, has the disadvantage that the reconstruction accuracy may be low in narrow or high curvature boundary areas, while it may be much higher in larger or low curvature boundary areas, and so, the accuracy of the reconstructed areas may vary. A better solution in some embodiments may be to configure virtual net distribution module(s) to distribute the virtual net's points non- uniformly, for example, as illustrated in FIGS. 31B, 32B, 33B, and 34B, which implies that particles can have different average sizes, and so, smaller and denser distributed particles may better reconstruct narrow or high curvature boundary areas, while larger and sparser distributed particles may better fill the space within the volume and also at boundary areas with larger curvature. Accordingly, the non-uniform distribution of the virtual net points may be configured to provide more uniform reconstruction accuracy. Steps for Optimal Particle Distribution & Size

[0320] In some embodiments, distribution modules 4630 may be configured to carry out operations to optimally distribute virtual net points, which operations may comprise one or more of the following, as illustrated in FIG. 46. The operations/modules of FIG. 46 may be recorded on a computer readable medium 3700, as illustrated:

[0321] (i) Estimate the average particle size and the number of virtual net points g_D 3701 along each of the directions D of the virtual net, as previously described. Optionally, increment the number of virtual net points g_D along each of the directions D of the virtual net with a certain amount, i.e. 2 or more, to reserve space for void particles.

[0322] (ii) Deform the virtual net 3702 such that most of the virtual net points are inside (overlapping with) the volumetric model. Optimally, at least one row or one column of virtual net points along each of the directions D of the virtual net are in the exterior of the volumetric model, such that the target surface lies between matter and void virtual net points.

[0323] (iii) Mark virtual net points 3703, for example mark as "matter" virtual net points positioned inside the volumetric model, and similarly, mark as void virtual net points that don't overlap with (are in the exterior of) a volumetric model. In some embodiments where the volumetric model contains mixed properties, the matter virtual net points may yield different labels corresponding to different properties of the volumetric model. Thus there may be two or more different labels in some embodiments. Marking the virtual net points 3703 may include marking particles as matter or void particles as well as marking other particle properties such as membrane labels.

[0324] (iv) Distribute virtual net points 3704. To optimally distribute the virtual net points, assume that each virtual net point is connected through springs to neighbor virtual net points, independent of which label they have, and thus yielding a virtual spring net. Recalling the explanations related to deriving the different vertex sharing configurations, and using a similar reasoning, one virtual net point VN₁ can selectively connect to one of its neighbor virtual net points VNi through a spring. Accordingly, there are 7 fixed spring configurations and a flexible spring configuration, matching the 7 fixed and flexible vertex sharing configurations discussed herein in the context of particles. The flexible spring configuration may allow a user to manually choose to which of the said neighbors VN_t to connect the virtual net point VN₁. [0325] (v) Define spring constants 3705. For each spring, define an appropriate spring constant k, which is defined by the ratio between the force F applied to the spring and the elastic deformation Al it produces to the spring, as shown in the following equation:

[0326] (vi) For springs connecting boundary virtual net points, i.e., virtual net points that are next to the boundary of the volumetric model, define the spring constant k inverse proportional to the curvature of the boundary, namely, the higher the curvature, the smaller the value of the constant k, and thus, the easier it is to compress or stretch the spring. Accordingly, the smaller the curvature, the higher the value of the constant k, and thus, the harder it is to compress or stretch the spring. Accordingly, the virtual net points in the neighborhood of areas of high curvature will be denser, and may be populated by particles of a smaller size, finally yielding a denser triangulation that better approximates the those areas with a higher curvature.

[0327] (vii) For springs connecting non boundary virtual net points, define the spring constant proportional with the distance from the boundary to the spring location measured along the spring's axis. The spring's axis is oriented either along one of the directions D of the virtual net, or in a diagonal direction defined by combinations of two or more directions. The closer to the boundary a spring is, the smaller the value of its constant k, thus the easier it is to compress or stretch the spring. Accordingly, the further from the boundary a spring is, the larger the value of its constant k, and thus, the harder it is to compress or stretch the spring.

[0328] (viii) Error correction 3706. Once the forces within the virtual spring net are in equilibrium, if the distance between two virtual net points Ci(VN₁, VW₂₎ is too small, respectively, when the particle that would be inserted in those locations would become smaller than desired, distribution modules 4630 may be configured to either (1) increase the value of the constant k of the spring connecting the said two virtual net points VN₁ and VN₂ and/or decrease the value of the constant k of neighbor springs, or (2) reposition some boundary matter virtual net points to the exterior of the volumetric model and label those virtual net points as void. Accordingly, the surface boundary of the volumetric model may stay always between void and matter boundary virtual net points, and may never pass between two virtual net points of the same kind, i.e. matter or void.

[0329] (ix) Calculate distances between virtual net points 3707. Once the equilibrium of forces within the deformed virtual spring and particle net is achieved, distribution modules 4630 can be configured to estimate at each virtual net point the force that is applied along each such spring. Thus, given the force F along a spring s(i,j), where i andy are the indices of the virtual net points V_t and V_j connected through spring s(i,j), and the spring's constant k, distribution modules 4630 can be configured to compute the deformation Δ/ of the spring, and thus determine the length I (equal to the initial spring's length minus the deformation) of the spring under the given force F. In other words, the distance between two neighbor virtual net points V_t and V_j may be equal to the spring's length I. Accordingly, the smaller the spring constant k is, the closer to each other the virtual net points are, and the smaller the particles inserted in those positions may be. Reciprocally, the larger the spring constant k is, the sparser the distribution of the virtual net points is, and the larger the particles inserted in those positions may be. Nevertheless, the spring constant k can also be defined with a fixed value for the entire virtual net, in which case the distance between the virtual net points is more homogeneous, or in particular cases even constant.

[0330] Remark: Embodiments may be configured to reposition the virtual net points (either by rearranging or relocating) anytime during a reconstruction or modeling procedure, or even once the procedures are completed, thus allowing for dynamic shape morphing and animation, as explained herein.

Operations for Reconstructing Single Resolution Volumetric Models

[0331] In some embodiments, SPIN graphics technologies can include reconstruction module(s) 4628 configured to reconstruct a volumetric model. Reconstruction module(s) 4628 may be configured to carry out one or more of the following operations as illustrated in FIG. 47. The operations/modules of FIG. 47 may be recorded on a computer readable medium 3800, as illustrated.

[0332] (i) Complete the setup 3801 of the SPIN representation according to the particularities of the said volumetric model and the desired reconstruction accuracy, as described above. Optionally, this operation may increment the number of virtual net points g_D along each of the directions D of the virtual net with a certain amount, i.e. 2 or more, to reserve space for void particles.

[0333] (ii) Insert a so-called matter particle 3802 at each virtual net point that is inside the volumetric model description and mark each particle with the label of the corresponding virtual net point. Membrane labels may also be marked. There may be no need to insert particles at virtual net points that are in the exterior of the volumetric model, yet, for the sake of simplifying the explanation we consider that in those said points void particles may be inserted. All void particles may have the same label. Furthermore, the centroid of every particle, matter and void, may overlap with the corresponding virtual net point.

[0334] (iii) Connect and merge neighbor matter particles 3803 that optionally have the same label, and which are chosen according to the vertex sharing configuration with the highest priority that applies to each of these particles.

[0335] (iv) Adjust the vertex coordinates 3804 of matter particles to fit a target surface.

[0336] (v) Defining particle surface meshes 3805 based on the radial, transversal or mixed triangulation mode(s). The reconstructed surface mesh of the entire volumetric model is the union of the surface meshes of each matter particle, and it can be based on either the radial, transversal or mixed triangulation mode.

[0337] In some embodiments, the above operations, namely, inserting a matter particle, connecting or merging the said matter particle with neighbor matter particles, optionally marked with the same label, which may be chosen according to the vertex sharing configuration, adjusting the vertices' coordinates of the said matter particle and also the coordinates of the vertices affected by the merging operation, and defining the said matter particle's surface mesh based on the radial, transversal or mixed triangulation mode, can also be done consecutively as part of one iteration, then repeated in additional iterations for additional matter particles. Accordingly, a surface reconstruction procedure may comprise a plurality of iterations, whereby the total number of iterations may be equal to the amount of matter particles that are inserted.

[0338] The insertion of void particles does not contribute to the surface of the SPIN-based volumetric model. Nevertheless, applying the above steps to the void particles instead of the matter particles yields a surface that may be the reverse of the surface reconstructed with the matter particles. Some embodiments may be configured to construct surfaces in this "reverse" approach.

Operations for Reconstructing Multi- Resolution Volumetric Models Using the Detail Reduction Approach

[0339] In some embodiments, SPIN graphics technologies can include multi-resolution upgrade module(s) 4629 configured obtain a multi-resolution SPIN-based volumetric model description from a single resolution volumetric model. Multi-resolution module(s) may employ so- called detail reduction and/or detail restoring approaches. [0340] A detail reduction approach may be accomplished by performing one or more of the operations illustrated in FIG. 48. The operations/modules of FIG. 48 may be recorded on a computer readable medium 3900, as illustrated.

[0341] Some embodiments may be configured to convert a single resolution volumetric model into a multi-resolution description by applying 3D wavelet-based multi-resolution decomposition (analysis) techniques to a single resolution volumetric model. In such a detail reduction approach the operations for reconstructing a multi-resolution SPIN-based volumetric model may comprise the following:

[0342] (i) Reconstruct the SPIN-based volumetric model at the highest resolution level L 3901, for example using a setup of the SPIN representation that allows obtaining the desired accuracy at each resolution level. In general, the lower the resolution level, the lower the accuracy is.

[0343] (ii) Update the SPIN-based volumetric model 3902 for reconstructing the volumetric model at resolution level L — 1, for example by reuniting void and matter neighbor particles (referred to as descendant particles), and their corresponding virtual net points, from resolution level L into larger particles, namely, the ancestor particles. The reunite operation can happen between particles of the same or different kind, namely matter or void, and also between particles with the same or different labels. As a result of the reunite operations, the SPIN representation at resolution level L - I may contain a virtual net with fewer number of points, which corresponds to a lower resolution and accuracy version of the volumetric model, and which may be populated by larger void and matter particles whose centroids may overlap the level L - I virtual net points.

[0344] (iii) Determine the ancestor particle's label and thus its properties 3903, for example either by using an overlap approach or by employing a prediction (empiric) formula. The overlap approach checks how the said particle's location within the virtual net overlaps with the volumetric model (which may be preferably defined at the same said resolution level L — 1). If there is no overlap between them, the said ancestor particle becomes a void particle and yields the corresponding label. Otherwise, the label reflects the properties that the volumetric model exhibits at the overlap area with the said ancestor particle. When using the prediction formula, the label of an ancestor particle may be determined based on the number of descendant matter particles and their labels. Accordingly, an ancestor particle may be of type matter if within its descendant particles the number of ones that are of type matter may be larger or equal to a minimum number that may be user configurable. In conclusion, an ancestor particle may yield a label, and thus properties, that can be different from those of its descendant particles. The properties of the matter ancestor particle may be a superset (the union and possibly more) of the properties of its descendant particles.

[0345] (iv) Connect or merge each ancestor matter particle 3904 with neighbor ancestor matter particles that optionally have the same label, and which are chosen according to the highest priority vertex sharing configuration that applies to each particle.

[0346] (v) Adjust coordinates 3905, for example by adjusting the vertex coordinates of each ancestor matter particle and also the coordinates of the vertices affected by the merging operation, such that vertices either match the coordinates of corresponding vertices of descendant particles, or they fit (are positioned on) a target surface. In the latter case, the target surface may correspond either to the volumetric model description at the highest resolution level, or to the volumetric model description at a same resolution level (e.g., L — 1).

[0347] (vi) Define particle surfaces 3906, for example by defining each ancestor matter particle's surface mesh based on the radial, transversal or mixed triangulation mode.

[0348] (vii) Repeat the above operations, starting with step (ii), and at each step substitute level L with level L - I [L becomes L - I, and L - I becomes L — 2), until the lowest desirable resolution level is reached L - I = O.

[0349] The relationship between the coordinates of the centroid of any ancestor particles at level L-I and the coordinates of the centroids of related particles at level L, comprising the said descendant particles and optionally particles neighbor with the said descendant particles, may be expressed using wavelet filters. Moreover, the hierarchy of particles with the coordinates of their centroids obtained for all resolution levels or a consecutive set of resolution levels may be described by a multi-dimensional wavelet-based decomposition, which can be obtained using the SPIN filters or compatible, as described herein.

Optimizing, the Distribution and Number of Virtual Net Points for Multi-Resolution

[0350] In some embodiments, SPIN graphics technologies can include multi-resolution optimization module(s) 4620 configured to obtain a multi-resolution SPIN-based volumetric model description from a single resolution volumetric model. For example, multi-resolution optimization module(s) 4620 may be configured to derive a virtual net for representing a volumetric model in a multi-resolution way, by performing one or more of the operations illustrated in FIG. 49. The operations/modules of FIG. 49 may be recorded on a computer readable medium 4000, as illustrated.

[0351] For the following description, it may be assumed that the number of particles that reunite along each of the directions D of a virtual net is equal to 2. Accordingly, when distributing the virtual net points according to the cubic-packing mode, 8 descendant particles reunite to form one ancestor particle, while, when distributing the virtual net points according to the hexa-packing mode, 4 descendant particles reunite to form one ancestor particle. Nevertheless, the explanation below can be extrapolated for any other configuration.

[0352] (i) Estimate the average particle size and the number of virtual net point g_D 4001 along each of the directions D of the virtual net, according to the desired accuracy, as previously explained.

[0353] (ii) Estimate the maximum number of resolution levels L"^ax 4002 along each of the directions D of the virtual net, for example using the following formula, whereby operator [xj returns the closest integer value that is less than or equal to x:

[0354] (iii) Select the desired number of resolution levels L_D 4003, for example as a value between 1 and L™^ax , and determine a number of virtual net points g% at a lowest RL I = 0, for example with the following formula, whereby operator [x] returns the closest integer value that is larger than or equal to x: choose either

[0355] (iv) Compute the number of virtual net points g_D at a highest RL I = L_D — 1 4004, for example as: g_D = g_D° x Z^-¹

[0356] (v) Optionally, reserve space for void particles 4005, for example by incrementing the number of virtual net points g_D 4005 along each of the directions D of the virtual net by a certain amount, e.g. two (2) or more, to reserve space for void particles.

[0357] (vi) Deform the virtual net 4006, for example such that all of the virtual net points, except the optional ones that were reserved for the void particles, are inside (overlapping with) the volumetric model. The virtual net points reserved for the void particles may be positioned at the exterior of the volumetric model.

[0358] (vii) Mark particles 4007, for example by marking as matter each of the virtual net points that is positioned inside the volumetric model, and similarly, marking as void each virtual net point that doesn't overlap with (is in the exterior of) the volumetric model.

[0359] (viii) Distribute the virtual net points 4008, for example using the spring model to produce an optimized distribution as explained herein. If necessary, fine tune the spring's constants k to obtain the desired results, yet, some embodiments may avoid moving any of the matter virtual net points outside the volumetric model, since their number may be utilized for the following steps.

[0360] (ix) Derive the virtual net points 4009 (ancestor) for the immediate lower resolution level L — 1, for example by reuniting virtual net points (descendants) of the same kind only, namely void with void and matter with matter.

[0361] (x) Compute the coordinates of the ancestor virtual net points 4010, for example at level L - I from the coordinates of related virtual net points at level L, comprising the corresponding descendant virtual net points and optionally virtual net points neighbor with the said descendant virtual net points. The said computation may be preferably expressed using wavelet filters.

[0362] (xi) Mark ancestor virtual net points 4011, for example by marking ancestor virtual net point with the same label, matter or void, as its descendant virtual net points. Matter labels may comprise membrane labels in some embodiments.

[0363] (xii) Repeat step (ix) to (xi), and at each step substitute level L with level L — 1 (L becomes L - I, and L - I becomes L — 2), until the lowest desirable resolution level is reached L - I = O.

[0364] Further, some embodiments may include one or more modules configured to describe the volumetric model in a multi-resolution fashion using the multi-resolution optimized virtual net, by performing one or more of the operations illustrated in FIG. 50. The operations/modules of FIG. 50 may be recorded on a computer readable medium 4100, as illustrated.

[0365] (i) Insert particles 4101, for example by selecting the virtual net points that correspond to the highest resolution level, and inserting matter particles in each matter virtual net point, and optionally, inserting void particles in each void virtual net point. [0366] (ii) Connect particles 4102, for example by connecting and merging neighbor matter particles, or keeping them disconnected, according to the vertex sharing configuration (with the highest priority) that applies to each of these particles.

[0367] (iii) Repeat steps (i) and (ii) for every lower resolution level.

[0368] (iv) Adjust highest resolution level vertex coordinates 4103, for example, at the highest resolution level, adjust the vertex coordinates of the matter particles to fit the target surface of the volumetric model.

[0369] (v) Adjust lower resolution level vertex coordinates 4104, for example, at each lower resolution level L - I, starting from high to low, adjust the vertices' coordinates of the matter particles to match the vertices of corresponding descendant matter particles from the immediate higher resolution level L.

[0370] (vi) Define particle surfaces 4105, for example, for every resolution level, including the highest, define every matter particle's surface mesh based on the radial, transversal or mixed triangulation mode.

[0371] The above operations may be used to complete the automatic multi-resolution reconstruction of a volumetric model. The said multi-resolution description can further be used for display, storage, data transmission, and so forth, but it can also be used as input for another particle based reconstruction of the same volumetric model. The relationship between the ancestor particles and their corresponding descendant particles (in terms of their labeling), may be stored as a lineage network that can be encoded using zero trees.

[0372] In conclusion, operations for optimally reconstructing a multi-resolution volumetric model using SPIN may comprise the following, illustrated in FIG. 51, and for which operations/modules may be stored on a computer readable medium 4200:

[0373] (i) Create the multi-resolution virtual net 4201, for example such that it provides the desired accuracy and optimize its virtual net points according to the multi-resolution guidelines.

[0374] (ii) Insert particles 4202, for example, at each resolution level, insert matter particles in every virtual net point that overlaps with the volumetric model, and optionally insert void particles at virtual net points that are in the exterior of the volumetric model. Inserting the particles also forms the lineage network, and thus each ancestor particle knows its corresponding descendant particles, and vice versa. [0375] (iii) Connect particles 4203, for example, at each resolution level, connect and merge neighbor matter particles, or keep them disconnected, according to the vertex sharing configuration (with the highest priority) that applies to each of these particles.

[0376] (iv) Adjust coordinates 4204, for example, at the highest resolution level, adjust the vertices' coordinates of the matter particles to fit the target surface of the volumetric model. Further, at every lower resolution level L - I adjust the vertices' coordinates of the matter particles either to fit the target surface of the volumetric model, which may be defined at the same resolution level L — 1, or to match the vertices of corresponding descendant matter particles from the immediate higher resolution level L.

[0377] (v) Define particle surfaces 4205, for example, at each resolution level, define each matter particle's surface mesh based on the radial, transversal or mixed triangulation mode.

Reconstructing Multi-Resolution Volumetric Models from Low to High

[0378] In some embodiments, multi-resolution upgrade module(s) 4629 may be configured to perform multi-resolution reconstruction of a volumetric model using the detail restoring approach, by performing one or more of the operations illustrated in FIG. 52. The operations/modules of FIG. 52 may be recorded on a computer readable medium 4300, as illustrated.

[0379] An example detail restoring approach may start from the lowest resolution level and incrementally build up each of the following higher resolution level SPIN-based versions of the volumetric model. Preferably, the volumetric model may be also described in a multi-resolution fashion. Otherwise, if this isn't the case, the volumetric model can be first reconstructed using the optimal detail reduction approach, and further, the SPIN-based multi-resolution reconstruction may be used as the input for the detail restoring approach. The following steps explain an example detail restoring approach.

[0380] (i) Create a virtual net 4301, for example by designing the virtual net points at the lowest resolution level I = 0, for example, such that at least one virtual net point may overlap with each disjoint part of the volumetric model, preferably defined at the same resolution level Z = O. Optionally, set at least one row or column of virtual net points along each of the directions D of the virtual net in the exterior of the volumetric model, such that the target surface lies between matter and void virtual net points. [0381] (ii) Insert particles 4302, for example by inserting matter particles in every virtual net point that overlaps with the volumetric model, and optionally inserting void particles at virtual net points that are in the exterior of the volumetric model. This operation may define the particle interconnection network.

[0382] (iii) Connect particles 4303, for example by connecting and merging neighbor matter particles, or keep them disconnected, according to the vertex sharing configuration (with the highest priority) that applies to each of these particles.

[0383] (iv) Adjust vertices 4304, for example by adjusting the vertex coordinates of the matter particles to fit the target surface of the volumetric model, which may be preferably defined at the same resolution level Z = O.

[0384] (v) Reconstruct volumetric model at higher resolution level 4305, for example by reconstructing the volumetric model at an immediate higher resolution level I + 1, subdividing each particle along at least one of the directions D of the virtual net, and also increasing the virtual net points to accommodate the increased number of particles.

[0385] (vi) Position descendant particles 4306, for example by positioning the centroids of each of the descendant particles from level I + 1 (and the corresponding virtual net points) in between the position of the centroid and a vertex that belong to the corresponding ancestor particle. Accordingly, the centroids of every descendant particle may lie within the volumetric space of its ancestor particle, and so, ancestor particles may subdivide into descendant particles of the same type, i.e., matter particles into matter particles and void particles into void particles. Nevertheless, in case the size of a boundary descendant matter particle may be smaller than it is required by the imposed reconstruction accuracy, it may be desirable to position the said descendant particle outside its ancestor's volumetric space at the exterior of the volumetric model. This way, the said descendant particle becomes a void particle.

[0386] (vii) Adjust descendant particle vertices 4307, for example by adjusting the vertex coordinates of the descendant matter particles to fit the target surface of the volumetric model, which may be preferably defined at the same resolution level I + 1. Optionally, the vertices of the ancestor particles can be used as a boundary definition. Accordingly, some of the descendant particles' vertices may match the coordinates of their corresponding ancestor particles' vertices, while the remaining non-adjusted vertices of the descendant particles may be interpolated between the coordinates of the adjusted descendant particles' vertices. [0387] (viii) Increment resolution level and repeat 4308, for example by incrementing the resolution level by substituting / with I + 1, and repeating operations (v) to (vii) to reconstruct the volumetric model at the following higher resolution level.

[0388] (ix) Repeat step (viii) until the highest resolution level I = L — 1 is reconstructed.

Freeform Modeling & Animation Applications

[0389] In some embodiments, SPIN graphics technologies can include freeform modeling module(s) 4632 configured to implement interactive and/or programmatic freeform modeling applications for designing single resolution and/or multi-resolution models, and also animation and special effects like morphing. For example, freeform modeling module(s) 4632 may implement operations illustrated in FIG. 53. The operations/modules of FIG. 53 may be recorded on a computer readable medium 4400, as illustrated.

[0390] (i) Setup a volumetric model 4401, for example in a similar way as for authoring applications, namely: deciding upon the packing mode, choosing one or more vertex sharing configuration, setting the surface mesh triangulation mode, specifying the number of virtual net points, and optionally the distance between them or the average particle size. The virtual net can be extended or shrunk any time in order to accommodate more or, respectively, fewer particles.

[0391] (ii) Adjust virtual net 4402. The virtual net can be kept with its virtual net points uniformly distributed, or optionally, the virtual net can be adjusted to provide a variable density of virtual net points. For example, virtual nets such as illustrated in FIGS. 32A and 34A may be adjusted to provide variable density virtual nets such as illustrated in FIGS. 32B and 34B.

[0392] (iii) Add particles 4403. A particle may be added to the virtual net in two example ways, namely, by specifying a place in the virtual net where the particle should be inserted, or by dragging the particle within the virtual net until the appropriate place is found. Since a particle may be positioned on a virtual net point in order to determine who its neighbors are, two particle positioning modes may be available, namely, particle snap to virtual net point (abbreviated as PSVNL) or virtual net point snap to particle (abbreviated as VNLSP). In the PSVNL mode, when the particle is inserted or while it is dragged, the said particle snaps to the closest virtual net point such that its centroid overlaps with the said virtual net point. When considering the VNLSP mode, each time a particle is inserted or while it is dragged, the closest virtual net point may be repositioned to overlap with the particle's centroid. When dragging a particle in the PSVNL mode, the motion of the particle may be in zigzag while the virtual net points are static. Conversely, when dragging a particle in the VNLSP mode, the motion of the particle is smooth, and each time another virtual net point is closer to the particle it may be repositioned to overlap with the particle's centroid, while the virtual net point that was previously overlapping is moved back to its original position.

[0393] (iv) Connect Particles 4404. After inserting, a said particle may connect and merge with particles on neighbor virtual net points, if the vertex sharing configuration allows for that. Moreover, while dragging the said particle, in either PSVNL or VNLSP mode, each time another virtual net point is attached to the said particle, the said particle may (a) disconnect from particles that are not located on neighbor virtual net points anymore, (b) update the connection and the way it merges with particles that continue to remain on neighbor virtual net points, and (c) connect and merges with new particles from neighbor virtual net points. The way neighbor particles connect and merge, or disconnect, may be always according to the vertex sharing configuration that applies.

[0394] While inserting or dragging any particle P_A, when P₄ is in the vicinity of another particle P_B, the snap to particle feature may allow to position particle P_A such that it touches particle

PB -

[0395] (v) Adjust particles 4405. Inserted particles can further be adjusted through, resizing, reshaping (which may be done by adjusting the particle's vertices independently), dragging or repositioning. Yet, particles can also be removed. The snap to particle mode can also be useful while resizing or reshaping particles to allow the adjustment of the said particle such that it touches the neighbor particles. Further, as previously explained, the size of any particle P₁, which may be inserted at any virtual net point VN₁, may be bounded by its 26 neighbor virtual net points. Accordingly, when resizing or reshaping the particle P₁ beyond the coordinates of one of the neighbor virtual net point VN₂ , then the said virtual net point VN₂ may be repositioned such that the particle P₁ remains bounded by all its neighbor virtual net points. For similar reasons, the repositioning of the said virtual net point VN₂ may require the repositioning of other virtual net point.

[0396] (vi) Multi-resolution adjustments 4406. The above modeling steps can also be done in a multi-resolution fashion. Modeling a particle at any resolution level may impact the entire hierarchy of both its descendant and ancestor particles, which is due to the relationship that exists between the centroids of the descendants and ancestor particles, as previously explained. Accordingly, applying transformations at the lower resolution levels may have a more global impact, while applying the same transformations at higher resolution levels may have a more local impact, and so, the higher the resolution level the localized the hierarchical modeling is. Further, each time a particle is inserted at any resolution level /, an entire hierarchy of descendant particles up to the highest resolution level may be added. Conversely, when any particle from any resolution level / is deleted, than optionally, the entire hierarchy of its descendant particles may be deleted. Also, when any particle P_A is deleted, if it has an ancestor particle at the immediate lower resolution level Z - I, the said ancestor particle may consider that the descendant particle P_A is of type void.

[0397] (vii) Modify particle interconnection network 4407. The particle interconnection network may expand with each particle that is inserted, and while dragging a particle, the particle interconnection network may be modified each time another virtual net point is attached to a particle.

[0398] (viii) Modify particle lineage network 4408. Similarly the particle lineage network may be created and updated each time a multi-resolution modeling is performed.

[0399] In some embodiments, modeling with particles as described herein allows for interactively and/or programmatically describing dynamics of living systems (growing and/or changing properties), fluid mechanics (dragging or relative movement between particles), cellular automata (growing and/or changing properties), and many other complex systems. Additionally, modeling and animation modalities described above can involve regions of particles instead of individual particles.

[0400] In conclusion, authoring, modeling and animation can be combined in any order to achieve a desired shape of a SPIN-based volumetric model.

Example Computing Device

[0401] With reference to FIG. 54, an exemplary computing system 4500 is depicted for implementing embodiments. Computing system 4500 may include for example a processor 4510, memory 4520, system bus 4530, one or more drives 4540, user input interface 4550, output peripheral interface 4560, and network interface 4570.

[0402] Drives 4540 may include, for example, a compact disk drive 4541 which accepts an optical disk 4541 A, a so-called hard drive 4542, which may employ any of a diverse range of computer readable media, and a flash drive 4543 which may employ for example a Universal Serial Bus (USB) type interface to access a flash memory 4543A. Drives may further include network drives and virtual drives (not shown) accessed via the network interface 4570.

[0403] The drives 4540 and their associated computer storage media provide storage of computer readable instructions, data structures, program modules and other data for the computer system 4500. For example, a hard drive 4542 may include an operating system 4544, application programs 4545, program modules 4546, and database 4547. SPIN modules 4523 may be stored among program modules 4546, and may be loaded into RAM 4521 along with associated data and instructions to carry out the various operations discussed herein.

[0404] Computer system 4500 may further include a wired or wireless input interface 4550 through which selection devices 4551 and input devices 4552 may interact with the other elements of the system 4500. Selection devices 4551 and input devices 4552 can be connected to the input interface 4550 which is in turn coupled to the system bus 4530, allowing devices 4551 and 4552 to interact with processor 4510 and the other elements of the system 4500. Interface and bus structures that may be utilized to implement 4550 may include for example a Peripheral Component Interconnect (PCI) type interface, parallel port, game port and a wired or wireless Universal Serial Bus (USB) interface.

[0405] Selection devices 4551 such as a mouse, trackball, touch screen, or touch pad allow a user to select among desired options that may be output by the system 4500, for example via the display 4562. Input devices 4552 can include any devices through which commands and data may be introduced to the system 4500. Exemplary input devices 4552 include a keyboard, an electronic digitizer, a microphone, a joystick, game pad, satellite dish, scanner, media player, mobile device, or the like.

[0406] Computer system 4500 may also include an output peripheral interface 4560 which allows the processor 4510 and other devices coupled to bus 4530 to interact with peripheral output devices such as printer 4561, display 4562, and speakers 4563. Interface and bus structures that may be utilized to implement 4560 include those structures that can be used to implement the input interface 4550. It should also be understood that many devices are capable of supplying input as well as receiving output, and input interface 4550 and output interface 4560 may be dual purpose or support two-way communication between components connected to the bus 4530 as necessary.

[0407] Computing system 4500 may operate in a networked environment using logical connections to one or more computers. By way of example, FIG. 54 shows a LAN 4571 connection to a network 4572. A remote computer may also be connected to network 4571. The remote computer may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and can include many or all of the elements described above relative to computing system 4500.

[0408] Networking environments are commonplace in offices, enterprise-wide area networks (WAN), local area networks (LAN), intranets and the Internet. For example, in the subject matter of the present application, computing system 4500 may comprise the source machine from which data is being migrated, and the remote computer may comprise the destination machine, or vice versa. Note however, that source and destination machines need not be connected through a network 4572, but instead, data may be migrated via any media capable of being written by the source platform and read by the destination platform or platforms.

[0409] When used in a LAN or WLAN networking environment, computing system 4500 is connected to the LAN through a network interface 4570 or an adapter. When used in a WAN networking environment, computing system 4500 typically includes a modem or other means for establishing communications over the WAN, such as the Internet or network 4572. It will be appreciated that other means of establishing a communications link between computers may be used.

[0410] According to one embodiment, computing system 4500 is connected in a networking environment such that the processor 4510 and/or program modules 4546 can perform in accordance with embodiments herein.

[0411] FIG. 55 illustrates a variety of SPIN modules 4523 introduced with reference to FIG. 54, and which are described throughout this specification. In some embodiments, the various illustrated modules, or aspects thereof, may be stored on a computer readable medium, and may be executable by a computing device to configure such computing device according to the technologies described herein. Furthermore, execution of any aspect of the illustrated modules or combinations thereof by a computing device comprises performance methods according to the teachings set forth herein. Finally, in some embodiments, any of the various aspects of the illustrated modules may be controlled by a user interaction with user interface modules 4603 as will be appreciated. Conclusion

[0412] Among the various teachings herein are: A data structure stored on a computer readable medium, said data structure comprising: data representing a n-dimensional object, said n- dimensional object having an object volume formed from one or more particles, said data comprising: first coordinates for a first particle centroid in a virtual net, said first particle centroid defining a position of said first particle in said virtual net; second coordinates for a plurality of vertices for said first particle, said first particle having a first particle volume defined by said plurality of vertices, and said first particle volume forming at least a portion of said object volume.

[0413] Said virtual net may be m-dimensional. Said plurality of vertices for said first particle may comprise up to 26 vertices at the lowest precision level. Said second coordinates may comprise one or more of: X, Y, and Z coordinate information as absolute values or relative to said virtual net; X, Y, and Z coordinate information relative to said particle centroid; angle and offset coordinate information relative to said virtual net; and angle and offset coordinate information relative to said particle centroid. Said data may further comprise information indicating whether at least one of said plurality of vertices is a shared vertex, wherein a shared vertex is a vertex that is shared between said first particle and a second particle that is a neighbor of said first particle. The data structure may further comprise vertex type information associated with one or more of said plurality of vertices. The data structure may further comprise information identifying one or more vertex sharing configurations for said first particle. Said plurality of vertices may comprise vertices of type V_A, V_B, or Vc, and said one or more vertex sharing configurations may comprise one or more of: a vertex sharing configuration that enables all vertices of type V_A to be shared; a vertex sharing configuration that enables all vertices of type V_B to be shared; a vertex sharing configuration that enables all vertices of type Vc to be shared; a vertex sharing configuration that enables all vertices of type V_A and V_B to be shared; a vertex sharing configuration that enables all vertices of type V_A and Vc to be shared; a vertex sharing configuration that enables all vertices of type V_B and Vc to be shared; a vertex sharing configuration that enables all vertices of type V_A, V_B, and Vc to be shared; and a vertex sharing configuration that enables user selection of shared vertices. The data structure may further comprise information identifying one or more triangulation modes for said first particle. Said one or more triangulation modes comprise one or more of a radial and a transversal triangulation mode. Said plurality of vertices may define a surface of a membrane associated with said first particle. The data structure of claim may further comprise a surface attribute associated with said membrane. Said membrane may be identified by a label. The data structure may further comprise a feature vector that comprises said label. Said label may identify a feature set comprising surface attributes. The data structure may further comprise third coordinates for a second plurality of vertices for said first particle, said first particle having a second particle volume defined by said second plurality of vertices. The data structure may further comprise a label identifying a second membrane, wherein said second membrane is associated with said second particle volume. Said first particle may be associated with at least one region. Said at least one region may be associated with a label identifying a membrane for said first particle. The data structure may further comprise information identifying a resolution level at which said first particle subdivides into two or more child particles. The data structure may further comprise information identifying a resolution level at which said first particle reunites into a parent particle.

[0414] Furthermore, some embodiments may provide a data structure stored on a computer readable medium, said data structure comprising: data representing a three-dimensional object, said three-dimensional object having an object volume formed from one or more particles, said data comprising: coordinates for a plurality of vertices for a first particle, said first particle having a first particle volume defined by said plurality of vertices, and said first particle volume forming at least a portion of said object volume.

[0415] Furthermore, some embodiments may provide a data structure stored on a computer readable medium, said data structure comprising: data representing a n-dimensional object, said n- dimensional object having an object surface and/or volume, said data comprising: a plurality of first coordinates, said first coordinates defining at least one centroid virtual net point for at least one particle, said at least one particle having a first particle surface and/or volume defined by vertices, and said first particle surface and/or volume forming at least a portion of said object surface and/or volume.

[0416] Furthermore, some embodiments may provide a system comprising data representing a n-dimensional object, said n-dimensional object having an object surface and/or volume that is formed from a plurality of particles with particle surfaces and/or volumes defined by a plurality of particle vertices, and a computer readable medium comprising instructions executable by a processor, said instructions and corresponding methods performed in such a system comprising: connecting first particle vertices corresponding to a first particle with second particle vertices corresponding to a second particle to form a surface mesh for said three-dimensional object, wherein said connecting is carried out in one or more triangulation modes; wherein one or more of said first particle vertices and one or more of said second particle vertices have a vertex type V_A, V_B, or Vc; wherein said one or more triangulation modes comprise: a radial triangulation mode in which one or more first particle vertices of type V_A can connect to one or more second particle vertices of types V_B and Vc, one or more first particle vertices of type V_B can connect to one or more second particle vertices of types V_A and Vc, and one or more first particle vertices of type Vc can connect to one or more second particle vertices of type V_A and V_B; and a transversal triangulation mode in which one or more first particle vertices of type V_A can connect to one or more second particle vertices of types V_B, one or more first particle vertices of type V_B can connect to one or more second particle vertices of types V_B and Vc, and one or more first particle vertices of type Vc can connect to one or more second particle vertices of type V_B. The methods may further comprise determining a triangulation mode that is defined for said first particle. Said first particle may define a radial triangulation mode for use with a first plurality of vertices of said first particle and said transversal triangulation mode for use with a second plurality of vertices of said first particle. At least two triangles of said first particle may be triangulated in a same triangulation mode. The methods may further comprise specifying a triangulation mode for one or more new vertices added to said first particle in a merge operation. The methods may further comprise switching one or more vertices of said first particle from a radial to a transversal triangulation mode or vice-versa in response to addition of one or more new vertices to said first particle in a merge operation.

[0417] Furthermore, some embodiments may provide a system comprising data representing a n-dimensional object, said n-dimensional object having an object surface and/or volume that is formed from a plurality of particles with particle surfaces and/or volumes defined by a plurality of particle vertices, and a computer readable medium comprising instructions executable by a processor, said instructions and corresponding methods performed in such a system comprising: calculating a virtual net, where virtual net points in said virtual net are defined by virtual net coordinates; for a first resolution level, calculating virtual net coordinates for a first particle centroid; for a second resolution level, subdividing said first particle into a plurality of child particles; and calculating virtual net coordinates for particle centroids for said plurality of child particles according to a particle division operation defined for said first particle. Said first particle may be subdivided into eight child particles in the cubic-packing mode, and may be subdivided into four child particles in the hexa-packing mode. Said particle division operation may preserve a membrane property of said first particle when calculating said plurality of child particles. Said particle division operation may preserve a volumetric property of said first particle when calculating said plurality of child particles. The methods may further comprise displaying said n-dimensional object at said first and second resolution levels.

[0418] Furthermore, some embodiments may provide a system for modeling a n- dimensional object, said n-dimensional object having an object surface and/or volume that is formed from a plurality of particles with particle surfaces and/or volumes defined by a plurality of particle vertices, and a computer readable medium comprising instructions executable by a processor, said instructions and corresponding methods performed in such a system comprising: instructions enabling selection of a number of axes for a virtual net in which said particles may be distributed; instructions enabling selection of a vertex sharing configuration for said plurality of vertices; instructions enabling selection of a mode for connecting said vertices to form a surface mesh; instructions enabling selection of an average particle size; and instructions enabling modeling of said three-dimensional object by placing particles with properties comprising a selected vertex sharing configuration, mode for connecting vertices, and average size, in a virtual net comprising a selected number of axes. At least one of said instructions enabling selection of a number of axes, instructions enabling selection of a vertex sharing configuration, instructions enabling selection of a mode for connecting said vertices, and instructions enabling selection of an average particle size may perform a default selection. Said instructions enabling selection of a number of axes may comprise instructions enabling selection between at least a hexa-packing mode in which particles are distributed along four axes, and a quad-packing mode the particles are distributed along three axes. Said instructions enabling selection of a vertex sharing configuration may comprise instructions enabling selection of a twenty-six shared vertices configuration, an eighteen shared vertices configuration, or any other vertex sharing configuration. Said instructions enabling selection of a mode for connecting said vertices may comprise instructions enabling selection between at least a radial and transversal triangulation mode. The computer readable medium may further comprise instructions enabling selection of a distribution mode for said virtual net. Said instructions enabling selection of a distribution mode may comprise instructions enabling selection between at least uniform and non-uniform distribution mode.

[0419] Furthermore, some embodiments may provide a system comprising data representing a n-dimensional object, said n-dimensional object having an object surface and/or volume that is formed from a plurality of particles with particle surfaces and/or volumes defined by a plurality of particle vertices, wherein each of said particle vertices has a vertex type V_A, V_B, or Vc, and a computer readable medium comprising instructions executable by a processor, said instructions and corresponding methods performed in such a system comprising: setting a vertex sharing configuration to at least one of a plurality of vertex sharing configurations that specify which of the vertex types can be shared, said vertex sharing configurations comprising: a vertex sharing configuration that enables all vertices of type V_A to be shared; a vertex sharing configuration that enables all vertices of type V_B to be shared; a vertex sharing configuration that enables all vertices of type Vc to be shared; a vertex sharing configuration that enables all vertices of type V_A and V_B to be shared; a vertex sharing configuration that enables all vertices of type V_A and Vc to be shared; a vertex sharing configuration that enables all vertices of type V_B and Vc to be shared; a vertex sharing configuration that enables all vertices of type V_A, V_B, and Vc to be shared; and a vertex sharing configuration that enables user selection of shared vertices. The methods may further comprise using said seventh sharing configuration as a default vertex sharing configuration. Said plurality of particle vertices may comprise up to 26 vertices at the lowest precision level.

[0420] Furthermore, some embodiments may provide a computer system configured to process graphics according to a particle-based graphics model, comprising a processor (4510) and memory (4520) configured to process particle-based volumetric models, a particle-based volumetric model comprising: one or more particles (130) that collectively form the volumetric model (FIG. 1), wherein each particle (130) is defined at least in part by positions of predefined numbers of vertices (701), wherein each vertex is defined by vertex coordinates, wherein each vertex has a vertex type (FIG. 16), wherein each vertex is connected to other vertices of a same particle according to a particle triangulation mode (FIG. 14), and wherein the connected vertices define a surface (721) of a particle's membrane; wherein one or more of the vertices are shared vertices (134A, 134B), the shared vertices comprising vertices at which a particle (130A) permits connecting with a neighbor particle (130B); and wherein shared vertices of are configured to split into a plurality of auxiliary vertices (711) to allow merging of neighbor particles. The system may be configured to position particles and vertices based on a virtual net structure comprising virtual net point definitions, the virtual net point definitions may allow for uniform and non-uniform virtual net point distributions. The system may be configured to adjust vertex coordinates to modify a shape of a particle surface mesh. The system may be configured to dynamically adjust vertex coordinates to produce an animation with the volumetric model. The system may be configured to associate multiple membranes with a particle, each membrane may comprise: vertices defining the shape of the membrane; and one or more labels that define a property of the membrane; and wherein neighbor particles that have membranes with a same property may permit connecting and merging of the membranes with the same property. The system may be configured to associate the one or more particles with one or more regions, and the one or more regions may collectively form the volumetric model. The system may be configured to perform operations with regions, the operations comprising one or more of: nesting regions in a region nesting network; subdividing a region according to a region lineage network; and reuniting regions according to a region lineage network. The system may be configured to subdivide and reunite one or more of the particles of the volumetric model to modify a resolution level of the volumetric model. The system may be configured to subdivide at least a portion of a particle membrane to increase a precision level of the membrane. The system may be configured to subdivide one or more particles into descendant particles, and the descendant particles may be sized such that the volumetric model grows by particle subdivision. The system may be configured to select one or more of: a virtual net configuration comprising a particle density and a particle distribution for the volumetric model; a packing mode selectable from a group comprising a cubic packing mode and a hexa packing mode; a vertex sharing configuration selectable from a group comprising two or more vertex types that may be designated as shared vertices; a triangulation mode selectable from a group comprising a radial triangulation mode and a transversal triangulation mode; and an average particle size. A particle of the one or more particles may comprise a number and distribution of shared vertices according to a vertex sharing configuration selected for one or more of the particle, a region comprising the particle, and the volumetric model. The system may be configured to store data corresponding to the particle-based volumetric model as one or more particle interconnection networks, each particle interconnection network encoding connections between particles within a predefined region of the volumetric model. The system may be configured to store data corresponding to the particle-based volumetric model as one or more particle lineage network encoding relationships between particles at different resolution levels. The system may be configured to connect particles via shared vertices only, and to merge neighbor particles by automatically generating one or more auxiliary vertices. [0421] There is little distinction left between hardware and software implementations of aspects of systems; the use of hardware or software is generally (but not always, in that in certain contexts the choice between hardware and software can become significant) a design choice representing cost vs. efficiency tradeoffs. There are various vehicles by which processes and/or systems and/or other technologies described herein can be effected (e.g., hardware, software, and/or firmware), and that the preferred vehicle may vary with the context in which the processes and/or systems and/or other technologies are deployed. For example, if an implementer determines that speed and accuracy are paramount, the implementer may opt for a mainly hardware and/or firmware vehicle; if flexibility is paramount, the implementer may opt for a mainly software implementation; or, yet again alternatively, the implementer may opt for some combination of hardware, software, and/or firmware.

[0422] The foregoing detailed description has set forth various embodiments of the devices and/or processes via the use of block diagrams, flowcharts, and/or examples. Insofar as such block diagrams, flowcharts, and/or examples contain one or more functions and/or operations, it will be understood by those within the art that each function and/or operation within such block diagrams, flowcharts, or examples can be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or virtually any combination thereof. In one embodiment, several portions of the subject matter described herein may be implemented via Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs), digital signal processors (DSPs), or other integrated formats. However, those skilled in the art will recognize that some aspects of the embodiments disclosed herein, in whole or in part, can be equivalently implemented in integrated circuits, as one or more computer programs running on one or more computers (e.g., as one or more programs running on one or more computer systems), as one or more programs running on one or more processors (e.g., as one or more programs running on one or more microprocessors), as firmware, or as virtually any combination thereof, and that designing the circuitry and/or writing the code for the software and or firmware would be well within the skill of one of skill in the art in light of this disclosure. In addition, those skilled in the art will appreciate that the mechanisms of the subject matter described herein are capable of being distributed as a program product in a variety of forms, and that an illustrative embodiment of the subject matter described herein applies regardless of the particular type of signal bearing medium used to actually carry out the distribution. Examples of a signal bearing medium include, but are not limited to, the following: a recordable type medium such as a floppy disk, a hard disk drive, a Compact Disc (CD), a Digital Video Disk (DVD), a digital tape, a computer memory, etc.; and a transmission type medium such as a digital and/or an analog communication medium (e.g., a fiber optic cable, a waveguide, a wired communications link, a wireless communication link, etc.).

[0423] Those skilled in the art will recognize that it is common within the art to describe devices and/or processes in the fashion set forth herein, and thereafter use engineering practices to integrate such described devices and/or processes into data processing systems. That is, at least a portion of the devices and/or processes described herein can be integrated into a data processing system via a reasonable amount of experimentation. Those having skill in the art will recognize that a typical data processing system generally includes one or more of a system unit housing, a video display device, a memory such as volatile and non-volatile memory, processors such as microprocessors and digital signal processors, computational entities such as operating systems, drivers, graphical user interfaces, and applications programs, one or more interaction devices, such as a touch pad or screen, and/or control systems including feedback loops and control motors (e.g., feedback for sensing position and/or velocity; control motors for moving and/or adjusting components and/or quantities). A typical data processing system may be implemented utilizing any suitable commercially available components, such as those typically found in data computing/communication and/or network computing/communication systems. The herein described subject matter sometimes illustrates different components contained within, or connected with, different other components. It is to be understood that such depicted architectures are merely exemplary, and that in fact many other architectures can be implemented which achieve the same functionality. In a conceptual sense, any arrangement of components to achieve the same functionality is effectively "associated" such that the desired functionality is achieved. Hence, any two components herein combined to achieve a particular functionality can be seen as "associated with" each other such that the desired functionality is achieved, irrespective of architectures or intermediate components. Likewise, any two components so associated can also be viewed as being "operably connected", or "operably coupled", to each other to achieve the desired functionality, and any two components capable of being so associated can also be viewed as being "operably couplable", to each other to achieve the desired functionality. Specific examples of operably couplable include but are not limited to physically mateable and/or physically interacting components and/or wirelessly interactable and/or wirelessly interacting components and/or logically interacting and/or logically interactable components.

[0424] With respect to the use of substantially any plural and/or singular terms herein, those having skill in the art can translate from the plural to the singular and/or from the singular to the plural as is appropriate to the context and/or application. The various singular/plural permutations may be expressly set forth herein for sake of clarity.

[0425] It will be understood by those within the art that, in general, terms used herein, and especially in the appended claims (e.g., bodies of the appended claims) are generally intended as "open" terms (e.g., the term "including" should be interpreted as "including but not limited to," the term "having" should be interpreted as "having at least," the term "includes" should be interpreted as "includes but is not limited to," etc.). It will be further understood by those within the art that if a specific number of an introduced claim recitation is intended, such an intent will be explicitly recited in the claim, and in the absence of such recitation no such intent is present. For example, as an aid to understanding, the following appended claims may contain usage of the introductory phrases "at least one" and "one or more" to introduce claim recitations. However, the use of such phrases should not be construed to imply that the introduction of a claim recitation by the indefinite articles "a" or "an" limits any particular claim containing such introduced claim recitation to inventions containing only one such recitation, even when the same claim includes the introductory phrases "one or more" or "at least one" and indefinite articles such as "a" or "an" (e.g., "a" and/or "an" should typically be interpreted to mean "at least one" or "one or more"); the same holds true for the use of definite articles used to introduce claim recitations. In addition, even if a specific number of an introduced claim recitation is explicitly recited, those skilled in the art will recognize that such recitation should typically be interpreted to mean at least the recited number (e.g., the bare recitation of "two recitations," without other modifiers, typically means at least two recitations, or two or more recitations). Furthermore, in those instances where a convention analogous to "at least one of A, B, and C, etc." is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., "a system having at least one of A, B, and C" would include but not be limited to systems that have A alone, B alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C together, etc.). In those instances where a convention analogous to "at least one of A, B, or C, etc." is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., "a system having at least one of A, B, or C" would include but not be limited to systems that have A alone, B alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C together, etc.). It will be further understood by those within the art that virtually any disjunctive word and/or phrase presenting two or more alternative terms, whether in the description, claims, or drawings, should be understood to contemplate the possibilities of including one of the terms, either of the terms, or both terms. For example, the phrase "A or B" will be understood to include the possibilities of "A" or "B" or "A and B."

[0426] While various embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in art.

Claims

CLAIMS:

1. A computer system configured to process graphics according to a particle-based graphics model, comprising: a processor (4510) and memory (4520) configured to process particle-based volumetric models, a particle-based volumetric model comprising: one or more particles (130) that collectively form the volumetric model (FIG. 1), wherein each particle (130) is defined at least in part by positions of predefined numbers of vertices (701), wherein each vertex is defined by vertex coordinates, wherein each vertex has a vertex type (FIG. 16), wherein each vertex is connected to other vertices of a same particle according to a particle triangulation mode (FIG. 14), and wherein the connected vertices define a surface (721) of a particle's membrane; wherein one or more of the vertices are shared vertices (134A, 134B), the shared vertices comprising vertices at which a particle (130A) permits connecting with a neighbor particle (130B); and wherein shared vertices of are configured to split into a plurality of auxiliary vertices (711) to allow merging of neighbor particles.

2. A computer system according to claim 1, wherein the system is configured to position particles and vertices based on a virtual net structure comprising virtual net point definitions, and wherein the virtual net point definitions allow for uniform and non-uniform virtual net point distributions.

3. A computer system according to claim 1, wherein the system is configured to adjust vertex coordinates to modify a shape of a particle surface mesh.

4. A computer system according to claim 1, wherein the system is configured to dynamically adjust vertex coordinates to produce an animation with the volumetric model.

5. A computer system according to claim 1, wherein the system is configured to associate multiple membranes with a particle, and wherein each membrane comprises: vertices defining the shape of the membrane; and one or more labels that define a property of the membrane; and wherein neighbor particles that have membranes with a same property permit connecting and merging of the membranes with the same property.

6. A computer system according to claim 1, wherein the system is configured to associate the one or more particles with one or more regions, and wherein the one or more regions collectively form the volumetric model.

7. A computer system according to claim 6, wherein the system is configured to perform operations with regions, the operations comprising one or more of: nesting regions in a region nesting network; subdividing a region according to a region lineage network; and reuniting regions according to a region lineage network.

8. A computer system according to claim 1, wherein the system is configured to subdivide and reunite one or more of the particles of the volumetric model to modify a resolution level of the volumetric model.

9. A computer system according to claim 1, wherein the system is configured to subdivide at least a portion of a particle membrane to increase a precision level of the membrane.

10. A computer system according to claim 1, wherein the system is configured to subdivide one or more particles into descendant particles, and wherein the descendant particles are sized such that the volumetric model grows by particle subdivision.

11. A computer system according to claim 1 , wherein the system is configured to select one or more of: a virtual net configuration comprising a particle density and a particle distribution for the volumetric model; a packing mode selectable from a group comprising a cubic packing mode and a hexa packing mode; a vertex sharing configuration selectable from a group comprising two or more vertex types that may be designated as shared vertices; a triangulation mode selectable from a group comprising a radial triangulation mode and a transversal triangulation mode; and an average particle size.

12. A computer system according to claim 1, wherein a particle of the one or more particles comprises a number and distribution of shared vertices according to a vertex sharing configuration selected for one or more of the particle, a region comprising the particle, and the volumetric model.

13. A computer system according to claim 1, wherein the system is configured to store data corresponding to the particle-based volumetric model as one or more particle interconnection networks, each particle interconnection network encoding connections between particles within a predefined region of the volumetric model.

14. A computer system according to claim 1, wherein the system is configured to store data corresponding to the particle-based volumetric model as one or more particle lineage network encoding relationships between particles at different resolution levels.

15. A computer system according to claim 1, wherein the system is configured to connect particles via shared vertices only, and to merge neighbor particles by automatically generating one or more auxiliary vertices.