this disclosure pertains to systems , methods , and computer readable media to decompose arbitrarily complex shapes into two or more simple convex shapes . such shapes may represent easily computable objects suitable for use by all manner of simulation engines ( or simulators ). in general , techniques are disclosed for determining which of multiple operations are best suited to decompose a given object based on various characteristics of the object . if the approach selected is convex decomposition , a new approach which may be either approximate ( acd ) or exact ( ecd ) is disclosed . more particularly , it has been unexpectedly found that by taking into consideration just a few easily determined characteristics of an object , a near optimal selection of a decomposition strategy may be made . a novel approach to one of these strategies , convex decomposition , considers an object &# 39 ; s number of reflex points and has been shown to be efficient in both the amount of time taken to decompose a given object or shape and the amount of memory needed to do so . in the following description , for purposes of explanation , numerous specific details are set forth in order to provide a thorough understanding of the disclosed concepts . as part of this description , some of this disclosure &# 39 ; s drawings represent structures and devices in block diagram form in order to avoid obscuring the novel aspects of the disclosed concepts . in the interest of clarity , not all features of an actual implementation are described . moreover , the language used in this disclosure has been principally selected for readability and instructional purposes , and may not have been selected to delineate or circumscribe the inventive subject matter , resort to the claims being necessary to determine such inventive subject matter . reference in this disclosure to “ one embodiment ” or to “ an embodiment ” means that a particular feature , structure , or characteristic described in connection with the embodiment is included in at least one embodiment of the invention , and multiple references to “ one embodiment ” or “ an embodiment ” should not be understood as necessarily all referring to the same embodiment . it will be appreciated that in the development of any actual implementation ( as in any software and / or hardware development project ), numerous decisions must be made to achieve the developers &# 39 ; specific goals ( e . g ., compliance with system - and business - related constraints ), and that these goals may vary from one implementation to another . it will also be appreciated that such development efforts might be complex and time - consuming , but would nevertheless be a routine undertaking for those of ordinary skill in the design an implementation of graphics processing systems having the benefit of this disclosure . referring to fig2 , decomposition selection operation 200 in accordance with one embodiment begins by taking a given object o 202 and simplifying it to generate simplified - object o s 204 ( block 220 ). ( in another embodiment , object o 202 need not be simplified .) if simplified - object o s 204 is dynamic ( the “ yes ” prong of block 225 ), a further test may be made to determine if simplified - dynamic - object o sd 206 has holes . as used herein , a “ dynamic object ” or “ dynamic shape ” refers to an object that is generated by an application in response to program input ( such as , for example , from a user ). that is to say , a dynamic object is an object whose shape is not known by an application a priori . if simplified - dynamic - object o sd 206 has lots of holes ( the “ yes ” prong of block 230 ), simplified - dynamic - hole - object o sdh 208 may be decomposed in accordance with distance field decomposition methodologies 235 . as used herein , an object has “ lots of holes ” if it has one or more holes where the retention of the hole is required for its dynamic characteristics to be manifest . for example , a block may have an interior hole , joined by a pipe to another interior hole . if a marble put into one hole would be expected to roll into the other hole via the pipe , it would be considered essential to retain a representation of the hole . if simplified - dynamic - object o sd 206 does not have lots of holes ( the “ no ” prong of block 230 ), it may be decomposed in accordance with convex decomposition methodologies ( block 240 ). if simplified - object os 204 is not dynamic , that is , static ( the “ no ” prong of block 225 ), another check may be made to determine if it has lots of holes ( block 245 ). if simplified - object o s 204 has lots of holes ( the “ yes ” prong of block 245 ), simplified - hole - object o sh 210 may be checked for complexity ( block 250 ). as used in this context , an object is complex , if its density of details approaches its sampling resolution . for example , a banana has low complexity at a given resolution , meaning that any two samples of the banana &# 39 ; s shape at adjacent pixel locations are likely to result in the same value . a cactus , on the other hand , would have high complexity at a given resolution because any two samples might be greatly different because they might hit either side of a needle on the cactus , or the surface of the cactus ; any given sample point has a chance of having three different orientations . another known approach applies a simplification algorithm ( e . g ., the ramer - douglas - peucker algorithm ; see discussion below ). if the reduced or simplified shape is approximately the same as the unreduced shape , the object is not complex . one of ordinary skill in the art will understand that what constitutes “ approximately the same ” may be specific to the implementation , with the mathematical concept of “ similar ” well - known to those of ordinary skill in the art . if simplified - hole - object o sh 210 is complex ( the “ yes ” prong of block 250 ), simplified - hole - complex - object o shc 212 may be decomposed with difference field methodologies ( block 235 ). if simplified - hole - object o sh 210 is not complex ( the “ no ” prong of block 250 ), it may be decomposed in accordance with spatial partition methodologies ( block 255 ). finally , if simplified - object os 204 does not have lots of holes ( the “ no ” prong of block 245 ), it may be decomposed using level set methodologies ( block 260 ). once object o 202 has been decomposed in accordance with one of blocks 235 , 240 , 255 and 260 , the resulting shape may again be simplified ( as in block 220 ). alternatively , in post - decomposition simplification as part of , for example , block 240 the smoothness of the resulting shape may no longer be of paramount concern and so simplification may be applied aggressively . one suitable algorithm to simplify object o 202 ( and possibly blocks 235 , 240 , 255 and 260 ) is the ramer - douglas - peucker ( rdp ) algorithm . the rdp algorithm defines ‘ dissimilar ’ based on the maximum distance ( specified , for example , by a threshold ) between an original curve and a simplified version thereof , where the simplified curve consists of a subset of the points that defined the original curve . in one embodiment the threshold may be user specified ( e . g ., by the program developer ). in another embodiment , the threshold may be automatically determined based on , for example , the ratio of an individual feature &# 39 ; s size versus the overall size of the shape . in still another embodiment , the threshold may be a fixed value ; either a specified number or a specified percentage of some characteristic of the curve comprising the outline ( e . g ., an angle threshold interpreted as a crease in the curve so that creases are preserved ). the rdp algorithm simplifies a given curve or path by recursively removing those pixels that don &# 39 ; t deviate by more than a specified ( threshold or epsilon ) amount from a line connecting two of it &# 39 ; s neighbor pixels . consider fig3 a , where pixel b deviates from line segment ac by more than a specified threshold t ( left ) and is , therefore , retained in the curve ( right ). in contrast , fig3 b shows that when pixel b deviates from line segment ac by less than the specified threshold t ( left ), it may be discarded ( right ). as shown here , the threshold may be related to the ‘ fidelity ’ one wishes to model the original object . if a very small threshold is specified , more of the pixels making up an object &# 39 ; s outline will be retained . the larger a threshold , the more pixels from the object &# 39 ; s outline will be eliminated or discarded . in another embodiment , curve simplification operations in accordance with block 220 may include pre - processing the object &# 39 ; s outline or contour to identify features that may be beneficial to preserve ( e . g ., sharp corners ). during such an operation , the identified curve features could be weighted to discount their eligibility for elimination so as to reduce the likelihood that such features are “ simplified out ” or eliminated from the final outline . in one embodiment , edge segments identified as beneficial could be weighted according to the dot product of the second derivate of the curve with a vector perpendicular to the curve . using this approach , a dot product approaching zero represents a kink in the curve and is more likely to be important and thus preserved , whereas a dot product of one indicates a smooth sample point , making it more eligible ( i . e ., more likely ) for elimination as it does not necessarily contribute a salient feature . in one embodiment , this saliency measure may be combined with the rdp epsilon value ( see discussion above ). in embodiments such as this , a threshold value may be specified that determines what features are beneficial ( e . g ., “ kinks ”) and which are non - beneficial ( e . g ., flat , or nearly flat , regions of the outline ). dot products greater than the specified threshold could be interpreted as indicating the feature is non - beneficial , while values less than , or equal to , the specified threshold may be interpreted as indicating the feature in beneficial . by way of background , a distance field is a derived representation of a digital image , where each element in the field expresses that element &# 39 ; s closest distance to the surface of an object represented as a polygonal object . ( the convention is that positive values are outside the object while negative values are inside .) distance fields , such as may be used in accordance with block 235 , may be constructed using various distance metrics for example the euclidean or manhattan distance metrics . distance fields are often used for collision detection in cloth animation , multi - body dynamics , deformable objects , mesh generation , motion planning , and sculpting . one of ordinary skill in the art will recognize that the implementation of distance fields applicable to a given situation may be informed by myriad details particular to the designer &# 39 ; s environment . the level set method ( lsm ) in accordance with block 260 is a numerical technique for tracking interfaces and shapes . the advantage of level set methods are that one can perform numerical computations involving curves and surfaces on a fixed cartesian grid without having to parameterize the objects . level set methods also make it relatively easy to follow shapes that change topology , for example when a shape splits in two , develops holes , or the reverse of these operations . these abilities make level sets an excellent tool to modeling time - varying objects , like inflation of an airbag , or a drop of oil floating in water . as with the use of distance fields , one of ordinary skill in the art will recognize that the implementation of a given level set method will depend upon the details of the designer &# 39 ; s specific environment . spatial partitioning in general , and binary space partitioning ( bsp ) in particular , in accordance with block 255 is a generic process for recursively subdividing a space into convex sets by hyperplanes until the partitioning meets some specified requirement ( s ). this approach to subdividing a space gives rise to a representation of objects within the space by means of a tree data structure known as a bsp tree . the specific choice of partitioning plane and criterion for terminating the partitioning process varies depending on the purpose of the bsp tree . for example , in computer graphics rendering , the scene is often divided until each node in the bsp tree contains only polygons that can render in arbitrary order . bsp trees may be used in 3d video games where the static geometry of a scene is often used together with a z - buffer , to correctly merge movable objects such as doors and characters onto the background scene . a novel shape convex decomposition operation in accordance with one embodiment ( e . g ., block 240 ) may be expressed as pseudo - code as shown in table 1 . the algorithm outlined in table 1 has been shown to be efficient in both the amount of time taken to decompose a given object or shape and the amount of memory needed to do so . the illustrated polygon decomposition pseudo - code begins by initializing a result list “ result ” to an empty - list . next , the shape to be decomposed may be preconditioned ( see tables 2 and 3 ) and , if successful , the shape &# 39 ; s reflex points may be counted . as used here , a vertex of a simple polygon is reflex if it has an interior angle ( i . e ., if the interior angle at the vertex ) is greater than pi ( π ) radians . any reflex count approach that meets the needs of the developer may be used . a series of examples based on different shapes will now be described in terms of the pseudo - code presented in tables 1 - 3 . referring first to table 1 , pseudo - code in accordance with one embodiment begins by initializing a result object ( set , string , collection , . . . ) to empty . the shape to be decomposed may then be checked to determine if it meets certain pre - conditions . referring to table 2 , precondition pseudo - code in accordance with one embodiment determines if the shape to be decomposed is a “ good ” convex shape and , if it is , returns a logical true value and , if it is not , returns a logical false value . referring to table 3 , illustrative pseudo - code defines a shape as “ good ” if it has no reflex points , triangles representing the shape do not cover an original point of the shape , and the shape has no edge intersections . those of ordinary skill in the art will recognize that this is not the only definition of what constitutes a good convex shape or object . the particular definition adopted for any given implementation may be a function of many factors peculiar to that implementation . returning again to table 1 , if the precondition check returns false the polygon decomposition operation may be terminated . if the precondition check returns true , polygon decomposition operation continue to line ‘ a ’. referring now to fig4 , shape - 1 as shown in fig4 a may be determined to have 2 vertex points in accordance with line ‘ a ’ so that line ‘ b ’ operations are skipped . for pedagogical reasons , shape - 1 &# 39 ; s contour or outline may be labeled ( starting at an arbitrary point ) as shown in fig4 b . in the adopted representation , shape - 1 &# 39 ; s reflex points are c and k . referring to fig4 c and line ‘ c ’ in table 1 , an arbitrary one of these vertices ( e . g ., vertex c ) may be selected as a starting point and shape - 1 traversed in a counterclockwise ( ccw ) direction to vertex k ( line ‘ d ’ in table 1 ). ( note , had traversal not stopped at point k and continued to l ( or beyond ), the resulting subshape cdefghjkl would not have been convex .) this walk shows shape - 1 may be partitioned into 2 subshapes by dotted line segment ck : subshape - 1 ( ss1 ) and subshape - 2 ( ss2 ). continuing at line ‘ f ’ in table 1 , because both ss1 and ss2 are good in the sense of table 3 , the “ best ” subshape may be selected . what defines “ better ” may vary depending on the implementation . in one embodiment , better may mean larger . in another embodiment , better may mean smaller . for purposes of the current example , better means “ largest enclosed area .” referring to fig4 d , because ss2 has a larger enclosed area than ss1 it may be removed from shape - 1 and placed into the result list . at the same time , ss1 may be closed by inserting line segment ck and those points associated with ss2 removed from further consideration , although their location is remembered . ss1 may then be passed to line ‘ a ’ in table 1 . referring to line ‘ b ’ in table 1 and fig4 e , because ss1 has no further reflex points it may be added to the result set , where after shape - 1 has been decomposed . referring now to shape - 2 in fig5 a , and after numbering each vertex as shown in fig5 b , shape - 2 may be determined to have a single reflex point in accordance with line ‘ a ’ in table 1 . processing continues in accordance with table 1 at line ‘ h ’. starting at the reflex point c in fig5 c , shape - 2 may be traversed ccw until reaching that vertex just keeps the shape created by a line segment from vertex c to itself convex . in fig5 c , that would be vertex g . ( note , that a line segment from vertex c to vertex h would create an interior angle at vertex c greater than π radians .) line segment cg creates 2 subshapes ss1 and ss2 , both of which are “ good ” in the sense of table 3 ( table 1 at line t ). because both shapes are good , ss1 may be arbitrarily chosen to be removed and placed into the result set as shown in fig5 d . the remaining subshape , ss2 , may then be passed back to line ‘ a ’ in table 1 . referring to fig5 e , because ss2 has no reflex points ( table 1 at line ‘ b ’) it too may be placed into the result set after the polygon decomposition of shape - 2 is complete . referring now to fig6 , the polygonal decomposition of shape - 3 as shown in fig6 a ( and vertex - numbered shape - 3 in accordance with fig6 b ) can begin by determining the shape has 2 reflex points c and f ( table 1 at line ‘ a ’). referring to fig6 c and arbitrarily selecting the reflex point at vertex c as a starting point , shape - 3 may be traversed ccw to vertex e , resulting in triangle cde ( table 1 at line ‘ d ’). this triangle , however is not “ good ” in the sense of table 3 because it “ covers ” another of the shape &# 39 ; s vertices — vertex f ( table 1 at line ‘ e ’). referring to fig6 d , repeating this process beginning at vertex f results in another “ bad ” subshape , triangle fab ( table 1 at lines ‘ e ’, ‘ c ’ and ‘ d ’). having found no “ good ” convex subshapes while traversing shape - 3 in the ccw direction , shape traversal operations may be repeated while moving in the clockwise ( cw ) direction ( table 1 at line ‘ g ’). referring to fig6 e , traversing shape - 3 in a cw direction starting at vertex c yields triangle cba or convex ss1 . ( note , continuing the cw traversal to vertex f yields non - convex subshape cbaf .) after removing ss1 from shape - 3 and placing it in the result list ( fig6 f ), the remaining portion of shape - 3 may be traversed in the cw direction beginning at vertex f ( fig6 g ). doing this identifies convex ss2 ( triangle fed ). removing ss2 and placing it in the result list yields polygon afdc or ss3 ( fig6 h ). because ss3 is itself convex , it may be placed directly into the result list where after shape - 3 has been decomposed ( fig6 j ). as noted above , embodiments of the disclosed subject matter include software . as such , a general description of a common software architecture is provided in terms of the simplified layer - type diagram shown in fig7 . the notation employed here is generally intended to imply that software elements in one layer use resources from the layers below and provide services to layers above . in practice , however , all components of a particular software element in a particular layer may not behave entirely in that manner . like hardware examples discussed below , software architecture or environment 700 is not intended to be exclusive in any way but rather illustrative . this is especially true for layer - type schemas such as that shown in fig7 , which software developers tend to express in myriad ways . with those caveats regarding software in mind , software architecture 700 includes operating system ( os ) kernel and device driver layer 705 , core services layer 710 , media layer 715 and application layer 720 . os kernel and device driver layer 705 can provide a kernel environment and support for file systems , networking , security , interprocess communication and device drivers ( as an interface to hardware components , not shown ). core services layer 710 can provide low - level services related to hardware ( e . g ., graphics processing units and / or other special purpose hardware computational units ) and networks . media layer 715 can provide essential services to user - level applications ( e . g ., 725 ) but which have no direct bearing on the application &# 39 ; s user interface ( e . g ., 730 ). specifically , media layer 715 can provide the technologies to incorporate two - dimensional ( 2d ) and three - dimensional ( 3d ) graphics , animations , image effects , and audio and video functionality into user - level applications . application layer 720 can include technologies for building a user - level application &# 39 ; s user interface ( e . g ., 730 ), for responding to user events and for managing application behavior . in general , communication between elements in different layers ( e . g ., between user application 725 and graphics functionality in application layer 720 ) is governed by frameworks and application programming interfaces ( apis ). for any given implementation , each of the illustrated layers may be a combination of two or more other layers . some functionality described here may not be provided in all implementations . further , while this disclosure may omit mentioning certain software and firmware , such omission has been made from illustrative environment 700 , but not from intended embodiments . by way of example , polygon decomposition in accordance with this disclosure may be used by user - level application 725 to generate the display of dynamic objects on user interface 730 . to accomplish this , user application 725 may use api and frameworks to call into media layer 720 . media layer 720 may seek support from lower levels ( e . g ., core services layer 710 ) to provide the requested services . in one embodiment user application 725 resides on the same computer system that provides software environment 700 . in another embodiment , user application 725 uses software environment 700 through a network connection . that is , user application 725 may be executing on one computer system and connected , through a network , to another computer system that provides software environment 700 . referring to fig8 , the disclosed embodiments may be performed by representative computer system 800 ( e . g ., a general purpose computer system or a dedicated image processing workstation ). computer system 800 may include one or more processors 805 , memory 810 ( 810 b and 810 b ), one or more storage devices 815 , graphics hardware 820 , device sensors 825 ( e . g ., proximity sensor / ambient light sensor , accelerometer and / or gyroscope ), communication interface 830 , user interface adapter 835 and display adapter 840 — all of which may be coupled via system bus or backplane 845 . memory 810 may include one or more different types of media ( typically solid - state ) used by processor 805 and graphics hardware 820 . for example , memory 810 may include memory cache , read - only memory ( rom ), and / or random access memory ( ram ). storage 815 may include one more non - transitory storage mediums including , for example , magnetic disks ( fixed , floppy , and removable ) and tape , optical media such as cd - roms and digital video disks ( dvds ), and semiconductor memory devices such as electrically programmable read - only memory ( eprom ), and electrically erasable programmable read - only memory ( eeprom ). memory 810 and storage 815 may be used to retain media ( e . g ., audio , image and video files ), preference information , device profile information , computer program instructions organized into one or more modules and written in any desired computer programming language , and any other suitable data . when executed by processor 805 and / or graphics hardware 820 such computer program code may implement one or more of the methods described herein . communication interface 830 may be used to connect computer system 800 to one or more networks ( see discussion above ). illustrative networks include , but are not limited to : a local network such as a usb network ; a business &# 39 ; local area network ; or a wide area network such as the internet and may use any suitable technology ( e . g ., wired or wireless ). user interface adapter 835 may be used to connect keyboard 850 , microphone 855 , pointer device 860 , speaker 865 and other user interface devices such as a touch - pad and / or a touch screen ( not shown ). display adapter 840 may be used to connect one or more display units 870 . processor 805 may execute instructions necessary to carry out or control the operation of many functions performed by device 800 ( e . g ., such as the generation and / or processing of images in accordance with tables 1 - 3 ). processor 805 may , for instance , drive display 810 and receive user input from user interface 815 . user interface 815 can take a variety of forms , such as a button , keypad , dial , a click wheel , keyboard , display screen and / or a touch screen . user interface 815 could , for example , be the conduit through which a software developer creates a program using techniques described herein . processor 805 may be a system - on - chip such as those found in mobile devices and include one or more dedicated graphics processing units ( gpus ), having one or more processing cores . processor 805 may be based on reduced instruction - set computer ( risc ) or complex instruction - set computer ( cisc ) architectures or any other suitable architecture and may include one or more processing cores . graphics hardware 820 may be special purpose computational hardware for processing graphics and / or assisting processor 805 perform computational tasks . in one embodiment , graphics hardware 820 may include one or more programmable graphics processing units ( gpus ). in another embodiment , each of one or more gpu &# 39 ; s have multiple cores . referring to fig9 , a simplified functional block diagram of illustrative electronic device 900 is shown according to one embodiment . electronic device 900 could be , for example , a mobile telephone , personal media device , portable camera , or a tablet , notebook or desktop computer system . as shown , electronic device 900 may include processor 905 , display 910 , user interface 915 , graphics hardware 920 , device sensors 925 ( e . g ., proximity sensor / ambient light sensor , accelerometer and / or gyroscope ), microphone 930 , audio codec ( s ) 935 , speaker ( s ) 940 , communications circuitry 945 , image capture circuit or unit 950 , video codec ( s ) 955 , memory 960 , storage 965 , and communications bus 970 . in one embodiment memory 960 and storage 965 may be as described above with respect to fig8 . processor 905 may execute instructions necessary to carry out or control the operation of device 900 as described above with respect to processor 805 . processor 905 may , for instance , drive display 910 and receive user input from user interface 915 . user interface 915 can take a variety of forms , such as a button , keypad , dial , a click wheel , keyboard , display screen and / or a touch screen . processor 905 may be , for example , any of the processor types identified above vis - à - vis processor 805 . graphics hardware 920 may be special purpose computational hardware for processing graphics and / or assisting processor 905 perform computational tasks . in one embodiment , graphics hardware 920 may include one or more programmable gpus as discussed above with respect to graphics hardware 820 . processor 905 and / or graphics hardware 920 may execute a user application retained on storage 965 that , through api and framework calls invoke operations in accordance with this disclosure ( e . g ., decomposition selection operation 200 or polygon decomposition processes in accordance with tables 1 - 3 operating in , or through , software architecture 700 ). the result of such operations my be the display of dynamic objects on display 910 as controlled by user input received via user interface 915 . it is to be understood that the above description is intended to be illustrative , and not restrictive . it will be recognized by one of ordinary skill in the art that the usefulness of representing objects as one or more simplified convex shapes is not limited to the generation and presentation of 2d shapes for a computer game . as a general approach to selecting which decomposition technique to apply to any given polygon or the decomposition of those polygons , the techniques and methods described herein are applicable to any situation in which convex polygons may be used . the foregoing material has been presented to enable any person skilled in the art to make and use the invention as claimed and is provided in the context of particular embodiments , variations of which will be readily apparent to those skilled in the art ( e . g ., some of the disclosed embodiments may be used in combination with each other ). further , fig1 - 9 do not exhaustively highlight the methods inherent in the pseudo - code provided in tables 1 - 3 . in one or more embodiments , one or more of the operations described here with respect to fig2 and / or the steps described with respect to tables 1 - 3 may be omitted , repeated , and / or performed in a different order . accordingly , the specific arrangement of steps shown in these figures should not be construed as limiting the scope of the technique . the scope of the invention therefore should be determined with reference to the appended claims , along with the full scope of equivalents to which such claims are entitled . in the appended claims , the terms “ including ” and “ in which ” are used as the plain - english equivalents of the respective terms “ comprising ” and “ wherein .”
techniques are disclosed for providing easily computable representations of dynamic objects so that a graphic systems &# 39 ; physics engine can more accurately and realistically determine the result of physical actions on , or with , such dynamic objects . more particularly , disclosed techniques generate a convex decomposition of an arbitrarily complex polygonal shape that is then simplified in a manner that preserves physically significant details , resulting in an object having a relatively small number of convex shapes that cover the original polygonal shape . the salience of a physically significant detail may be controlled via a threshold value which may be user or system specified .