• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            牽著老婆滿街逛

            嚴以律己,寬以待人. 三思而后行.
            GMail/GTalk: yanglinbo#google.com;
            MSN/Email: tx7do#yahoo.com.cn;
            QQ: 3 0 3 3 9 6 9 2 0 .

            Collision detection with Recursive Dimensional Clustering

            http://lab.polygonal.de/articles/recursive-dimensional-clustering/

            Collision detection with Recursive Dimensional Clustering

            Brute force comparison

            Collision detection can be done in many ways. The most straightforward and simplest way is to just test every object against all other objects. Because every object has to test only for others after it in the list of objects, and testing an object with itself is useless, we arrive at the well known brute force comparison algorithm:

            for (i = 0; i <  n; i++)
            {
                a
            = obj[i];

               
            for (j = i + 1; j <  n; j++)
               
            {
                    b
            = obj[j];
                    collide
            (a, b)
               
            }
            }

            This double nested loop has a time complexity (n is the number of objects to check) of:
            brute force time complexity
            It can be immediately seen that this suffers from a big problem: exponential growth. An excellent article by Dave Roberts describes this problem in more detail and also covers several alternative approaches to collision detection.

            Space partitioning

            The algorithm represented here uses space partitioning, which means it subdivides the screen into smaller regions. Each region then obviously contains a fewer number of objects. The collision checks for all the entities in the region (space garbage, alien spaceships, orks, whatever) are then performed by the brute force comparison - which is very efficient for a small number of objects.

            Two other common spatial partitioning schemes are Binary Space Partitioning (BSP) and Quadtree/Octree Partitioning. All have in common that they recursively subdivide the space into smaller pieces. RDC however, does not construct a tree based structure and must be recomputed every frame. BSP and Quad trees on the other side are best used when precomputed since they are expensive to modify.

            So first, we limit the number of collision checks by using spatial partitioning and second, we wrap each object in a bounding shape (e.g. bounding sphere) to quickly eliminate objects that aren’t colliding.

            RDC has an average time complexity of:
            RDC time complexity
            While the number of tests using brute-force alone explodes, RDC method increases approximately linearly.

            The algorithm

            RDC was described by Steve Rabin, in the book Game Programming Gems II: “Recursive Dimensional Clustering: A Fast Algorithm for Collision Detection”. Without going into the depth as much, I’ll try to recap the basic principles, followed by an working implementation which you can download and try for yourself.

            The steps involved in the RDC algorithm are as follows:

            Step1: Iterate trough all objects and store the intervals for a given axis in a list data structure. e.g. for the x-axis we store the minimum (open) and maximum (close) x position of the object boundary. An easy way to do this is using displayObjectInstance.getBounds(). The same is done for the y-axis (and of course for the z-axis, if you are in 3D space). Each boundary has to also remember what entity it belongs to and if its a ‘open’ or ‘close’ type:

            class Boundary
            {
               
            public var type:String;
               
            public var position:Number;
               
            public var object:Object;
            }

            Step2: Sort the collected list of boundary objects in ascending order from lowest to highest position:

            var boundaries:Array = getIntervals(objects, axis)
            boundaries
            .sortOn("position", Array.NUMERIC);

            Step3: Iterate trough the sorted boundary list and store objects with overlapping intervals into groups:

            var group:Array = [];
            var groupCollection:Array;
            var count:int = 0;

            for (var i:int = 0; i <  boundaries.length; i++)
            {
               
            var object:Boundary = boundaries[i];

               
            if (object.type == "open")
               
            {
                    count
            ++;
                   
            group.push(object);
               
            }
               
            else
               
            {
                    count
            --;
                   
            if (count == 0)
                   
            {
                        groupCollection
            .push(group);
                       
            group = [];
                   
            }
               
            }
            }

            If you are dealing just with one dimension (which would be a strange game…) you would be done.
            For this to work in higher dimensions, you have to also subdivide the group along the other axis (y in 2d, y and z in 3d), and then re-analyze those groups along every other axis as well. For the 2d case, this means:

            1. subdivide along the x-axis
            2. subdivide the result along the y-axis.
            3. re-subdivide the result along the x-axis.

            Those steps are repeated until the recursion depth is reached. This is best shown with some pictures:

            x-axis no intersection
            All objects are happily separated, no groups are found.

            x-axis intersection
            The open/close boundaries of object a and b overlap -
            thus both are put into a group.

            y-axis no intersection
            Even though the intervals of object a and b overlap along the
            x-axis, they are still separated along the y-axis.

            y-axis reanalyze x-axis
            Subdividing along the x-axis results in one group [A, B, C].
            Second pass along y-axis splits the group into [B], [A, C].
            Subdividing along the x-axis again splits [A,C], so finally we
            get the correct result: [A], [B], [C].

            Interactive demo

            This should give you a better idea what RDC does. The value in the input field defines how many objects a group must have to stop recursion. By lowering the number, you actually increase the recursion depth (slower computation). So you tell the algorithm: “try to make smaller groups by subdividing further!”. If you set this value to 1, only one object is allowed per group. If you set the value too high (faster computation) you get bigger groups. This can also be seen as a blending factor between brute force comparison and RDC. Usually you have to find a value in between, so that perhaps each group contains 5-10 object to make this algorithm efficient.

            The ’s’ key toggles snap on/off. This is to show a potential problem that arises when the boundaries of two object share the same position. The sorting algorithm then arbitrary puts both object in a group (e.g. if the open boundary of object is stored before the close boundary of object b in the list), although they aren’t colliding, but just touching.
            You can resolve the issue in the sorting function, but as we want the algorithm to be as fast as possible, this is not a good idea. Instead, it’s best to use a tiny threshold value, which is accumulated to the interval. If the threshold value is positive, the boundaries are ‘puffed’ in, and object touching each other are not counted as colliding. If the value is negative, touching objects are grouped together and checked for collision later.

            ‘+/-’ keys simple increase/decrease the number of objects, and ‘d’ key toggles drawing of the boundaries, which gets very messy on large number of objects. Green rectangles denote the final computed groups, whereas gray groups are temporary groups formed by the recursive nature of the algorithm and are further subdivided.

            Drag the circles around, begin with a small number of object (3-4) and watch what the algo does.

            Full screen demo: interactive, animated (Flash Player 9)

            pro’s

            - recursive dimensional clustering is most efficient if the objects are distributed evenly across the screen and not in collision.

            - it is great for static objects since you can precompute the groups and use them as bounding boxes for dynamic objects.

            con’s

            - the worst case is when all objects are in contact with each other and the recursion depth is very high - the algorithm cannot isolate groups and is just wasting valuable processing time.

            - because of the recursive nature the algorithm is easy to grasp, but tricky to implement.

            the AVM2 is very fast, so unless you use expensive collision tests or have a large number of objects, a simple brute force comparison with a bounding sphere distance check is still faster than RDC.

            Download, implementation and usage

            Download the source code here. Please note that it is coded for clarity, not speed.
            Usage is very simple. You create an instance of the RDC class and pass a reference to a collision function to the constructor. The function is called with both objects as arguments if a collision is detected. A more elegant solution would use event handlers.

            function collide(a:*, b:*)
            {
                 
            // do something meaningful
            }

            var rdc:RDC = new RDC(collide);

            gameLoop
            ()
            {
               
            // start with x-axis (0), followed by y-axis (1)
                rdc
            .recursiveClustering([object0, object1, ...], 0, 1);
            }

            Have fun!
            Mike

            posted on 2007-12-28 16:57 楊粼波 閱讀(407) 評論(0)  編輯 收藏 引用

            亚洲国产精品人久久| 色综合久久88色综合天天 | 精品伊人久久久| 久久精品一本到99热免费| 久久精品国产精品亚洲毛片| 久久精品视频网| 欧美亚洲另类久久综合婷婷| 狠狠色综合网站久久久久久久高清| 国产毛片欧美毛片久久久| 久久成人精品视频| 超级碰碰碰碰97久久久久| 国产精品99久久免费观看| 久久99久久成人免费播放| 亚洲精品国精品久久99热一| 久久九九全国免费| 久久天天躁狠狠躁夜夜不卡| 久久99国产精品久久99果冻传媒| 色综合久久天天综线观看| 国产精品久久久久久久久| 亚洲国产精品嫩草影院久久 | 久久综合久久综合久久| 一本一道久久a久久精品综合| 久久青草国产手机看片福利盒子| 久久精品国产久精国产果冻传媒| 国产成人久久精品麻豆一区| 久久精品天天中文字幕人妻| 久久久久久亚洲精品影院| 国产精品青草久久久久福利99| 久久亚洲精品成人AV| 久久久久亚洲AV无码专区首JN| 久久国产香蕉一区精品| 69久久精品无码一区二区| 久久婷婷国产综合精品| 亚洲午夜久久久影院伊人| 国产精品久久久久蜜芽| 日韩va亚洲va欧美va久久| 精品久久久久久无码中文字幕 | 久久综合九色欧美综合狠狠| 国产99久久精品一区二区| 久久99精品久久久久久hb无码| 欧洲精品久久久av无码电影|