Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / cdjs / reduce_collision_set.js
1 // Copyright (c) 2001-2010, Purdue University. All rights reserved.
2 // Copyright (C) 2015 Apple Inc. All rights reserved.
3 // 
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are met:
6 //  * Redistributions of source code must retain the above copyright
7 //    notice, this list of conditions and the following disclaimer.
8 //  * Redistributions in binary form must reproduce the above copyright
9 //    notice, this list of conditions and the following disclaimer in the
10 //    documentation and/or other materials provided with the distribution.
11 //  * Neither the name of the Purdue University nor the
12 //    names of its contributors may be used to endorse or promote products
13 //    derived from this software without specific prior written permission.
14 // 
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
19 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26 var drawMotionOnVoxelMap = (function() {
27     var voxelSize = Constants.GOOD_VOXEL_SIZE;
28     var horizontal = new Vector2D(voxelSize, 0);
29     var vertical = new Vector2D(0, voxelSize);
30     
31     function voxelHash(position) {
32         var xDiv = (position.x / voxelSize) | 0;
33         var yDiv = (position.y / voxelSize) | 0;
34         
35         var result = new Vector2D();
36         result.x = voxelSize * xDiv;
37         result.y = voxelSize * yDiv;
38         
39         if (position.x < 0)
40             result.x -= voxelSize;
41         if (position.y < 0)
42             result.y -= voxelSize;
43         
44         return result;
45     }
46     
47     return function(voxelMap, motion) {
48         var seen = new RedBlackTree();
49         
50         function putIntoMap(voxel) {
51             var array = voxelMap.get(voxel);
52             if (!array)
53                 voxelMap.put(voxel, array = []);
54             array.push(motion);
55         }
56         
57         function isInVoxel(voxel) {
58             if (voxel.x > Constants.MAX_X ||
59                 voxel.x < Constants.MIN_X ||
60                 voxel.y > Constants.MAX_Y ||
61                 voxel.y < Constants.MIN_Y)
62                 return false;
63             
64             var init = motion.posOne;
65             var fin = motion.posTwo;
66             
67             var v_s = voxelSize;
68             var r = Constants.PROXIMITY_RADIUS / 2;
69             
70             var v_x = voxel.x;
71             var x0 = init.x;
72             var xv = fin.x - init.x;
73             
74             var v_y = voxel.y;
75             var y0 = init.y;
76             var yv = fin.y - init.y;
77             
78             var low_x, high_x;
79             low_x = (v_x - r - x0) / xv;
80             high_x = (v_x + v_s + r - x0) / xv;
81             
82             if (xv < 0) {
83                 var tmp = low_x;
84                 low_x = high_x;
85                 high_x = tmp;
86             }
87             
88             var low_y, high_y;
89             low_y = (v_y - r - y0) / yv;
90             high_y = (v_y + v_s + r - y0) / yv;
91             
92             if (yv < 0) {
93                 var tmp = low_y;
94                 low_y = high_y;
95                 high_y = tmp;
96             }
97             
98             if (false) {
99                 print("v_x = " + v_x + ", x0 = " + x0 + ", xv = " + xv + ", v_y = " + v_y + ", y0 = " + y0 + ", yv = " + yv + ", low_x = " + low_x + ", low_y = " + low_y + ", high_x = " + high_x + ", high_y = " + high_y);
100             }
101             
102             return (((xv == 0 && v_x <= x0 + r && x0 - r <= v_x + v_s) /* no motion in x */ || 
103                      ((low_x <= 1 && 1 <= high_x) || (low_x <= 0 && 0 <= high_x) ||
104                       (0 <= low_x && high_x <= 1))) && 
105                     ((yv == 0 && v_y <= y0 + r && y0 - r <= v_y + v_s) /* no motion in y */ || 
106                      ((low_y <= 1 && 1 <= high_y) || (low_y <= 0 && 0 <= high_y) ||
107                       (0 <= low_y && high_y <= 1))) && 
108                     (xv == 0 || yv == 0 || /* no motion in x or y or both */
109                      (low_y <= high_x && high_x <= high_y) ||
110                      (low_y <= low_x && low_x <= high_y) ||
111                      (low_x <= low_y && high_y <= high_x)));
112         }
113         
114         function recurse(nextVoxel) {
115             if (!isInVoxel(nextVoxel, motion))
116                 return;
117             if (seen.put(nextVoxel, true))
118                 return;
119             
120             putIntoMap(nextVoxel);
121             
122             recurse(nextVoxel.minus(horizontal));
123             recurse(nextVoxel.plus(horizontal));
124             recurse(nextVoxel.minus(vertical));
125             recurse(nextVoxel.plus(vertical));
126             recurse(nextVoxel.minus(horizontal).minus(vertical));
127             recurse(nextVoxel.minus(horizontal).plus(vertical));
128             recurse(nextVoxel.plus(horizontal).minus(vertical));
129             recurse(nextVoxel.plus(horizontal).plus(vertical));
130         }
131         
132         recurse(voxelHash(motion.posOne));
133     };
134 })();
135
136 function reduceCollisionSet(motions) {
137     var voxelMap = new RedBlackTree();
138     for (var i = 0; i < motions.length; ++i)
139         drawMotionOnVoxelMap(voxelMap, motions[i]);
140         
141     var result = [];
142     voxelMap.forEach(function(key, value) {
143         if (value.length > 1)
144             result.push(value);
145     });
146     return result;
147 }
148