机器学习课业代写 机器学习代写 编程作业代写 编程代码代写
335Properties and Applications of Binary Hypothesis Testing Detection, Estimation, and Learning 机器学习课业代写 1 How to submit your solution • The submission deadline is 23:59 on February 4,...
View detailsSearch the whole station
Java作业代写 General instructions Search for the keyword updated to find any places where the PDF has been updated.We will provide you with some examples
Please see the submission instructions at the end of this document for more details.
In this assignment you’ll see a practical example of how trees and recursion can be used. We will consider the problem of collision detection in computer graphics and animation.
The goal will be to accelerate an interactive 2D physics simulation involving many balls bouncing around like in some chaotic billiards-like game. Like any modern realtime game, our simulation will run in an infinite loop called the “game loop” which in each iteration will update the scene and display a new “frame”, or image, to your screen.
For every frame, our physics engine must first detect when two balls are “overlapping” or ‘in contact with” or “colliding with” each other, then resolve the contact by separating the two balls and modelling a momentum transfer between them (aka bouncing). It then updates the positions of all the balls using their new velocities. These updates are done in the code provided to you. FYI, you can learn more about these problems in COMP 559 Computer Animation if you are so inclined.
Your task is simply to write the collision detection code for our simulation. You will be given a list of circles and you will need to return a list of all the “contacts” between any two pairs of circles in the list. We want you to do this in two different ways.
Your first inclination may be to write a nested for loop over all the circles to check every pair for potential contact. Indeed this would work, and we’d like for you to implement this, but this is not the optimal approach as its time complexity is O(n^{2}) where n is the number of circles. To get a feel for how bad this is, imagine there were 100,000 circles. To check every pair for contact would result in 10 billion (10^{10}) circle-to-circle contact queries which is an absurd amount and would be far too slow.
If you think a bit you’ll realize that checking for contact between circles on opposite ends of the screen is a waste of time, as you can only be in contact with other circles that are “nearby”. In other words, you can dramatically speed up the simulation by reducing the “search space” of each circle. We generally perform such search-space reductions by doing a first pass over the data and building a data structure that allows us to speed up subsequent collision queries. These techniques are applied in many areas like real-time graphics (google ”raytracing”) and machine learning (google ”k-d trees”).
In this assignment we’ll focus on a particular tree-like acceleration structure called a Bounding Volume Hierarchy (BVH). As its name suggests, a BVH is a hierarchy or tree consisting of “bounding volumes”. A bounding volume is simply a volume, or more generally shape, which bounds or encloses its child volumes. In this assignment we’ll use 2D axis-aligned bounding boxes as bounding volumes; these are rectangles whose left/right edges are vertical and top/bottom edges are horizontal, i.e., they are not rotated. Our BVH will also be be binary, which means that each node in the tree will have at most two children. We will store the circles within the leaves of this tree.
So you can imagine the root of our BVH as a box with at most two children, where each child is also a box with at most two children, and so on until you reach a leaf node containing one circle. The child boxes of any node in our tree must be nested fully inside their parent’s box, but sibling boxes are allowed to overlap each other.
You’ll soon see the full BVH construction algorithm, but for now you can imagine that we put all the balls on the left side of the screen in a big box, and all the balls on the right side in another box. Now imagine you’re a ball and you want to see which other balls you’re touching. Suppose you look around and notice that you are not in contact with the right-side box. This means that you cannot be in contact with any of the balls which are inside that box, effectively halving the search space. This search-space halving gets recursively repeated at every level of the tree. Similar to a binary search, this allows us to cut the per-ball collision detection complexity to O(log n) on average.
Why do we say on average? Well, for context, recall the lectures on quicksort. The first step in quicksort is to pick a pivot and partition the input list into two disjoint lists, one with elements which are smaller than the pivot, and one with elements which are larger. Ideally, both of these lists will be of equal length, which leads to a quicksort runtime of O(n log n), but if the split is unbalanced then you may encounter quicksort’s worst-case runtime of O(n^{2}). However, on average, if your list is full of random numbers, you can expect the runtime to be “closer” to O(n log n).
The construction algorithm (explained later) contains a split() method which takes a list of circles and spatially partitions them. If the split at each node perfectly halves the input list, then the height of our BVH will be log n. In practice, however, our splits may be slightly worse due to the random positioning of the balls, leading to a BVH of height greater than log n. The height of the tree matters because it gives us an upper bound on the number of circle-boundingBox contact queries we must make to reach a leaf in the BVH.
Since the circles are moving, you’ll need to build a new BVH tree every frame. This takes time O(n log n) in the best case and O(n^{2}) in the worst case. This behavior is analogous to quicksort, and we will leave it to you to figure out this analogy.
You don’t need to understand this class for this assignment, but you should run it. Essentially, it runs the main physics simulation and rendering loop in the following order : (1) all contacts are detected using naive or accelerated means; (2) detected contacts are resolved, meaning the balls are assigned new velocities simulating a bounce (3) new positions of all balls are calculated using the velocities and (4) balls at these new positions are displayed.
To play around with the simulation, you can simply use your mouse to grab a ball and drag it around. The balls will then bounce off each other and off the walls. You can also release a ball to “throw it”. A demonstration video of the expected behaviour can be found here . If you press the “r” key on your keyboard, the balls will be reset to a random initial configuration.
Circles which are in contact with other circles will be colored blue, and circles which are not in contact with any circles will be colored white. We expect you to use the visualizer in part to debug your assignment and to see what’s going on.
The initScene() method is responsible for filling the scene with randomly placed balls. To debug a failed contact test, you may want to replace the body of this method by just setting circles to PublicTesterUtils.randomInit() with the appropriate parameters to visualize the scene used for testing. The error messages in the tests will tell you what parameters to use.
Each Box object is defined by two corner points bottomLeft and topRight. You don’t need to modify anything here, but will need to use several methods of this class.
The Box class has several methods that are given in the starter code, including:
Each Circle object has a position, velocity, radius, and id. This id is unique to each circle, i.e., no two circles can share the same id. You must use this id to ensure that a circle does not “contact” itself.
Each circle has a getBoundingBox() method which returns the tightest Box that fully encloses the circle. This is used by the BVH.buildtightBoundingBox() method described in the next section.
Each circle also has an isContacting() method, which takes a Circle c and returns a ContactResult object if this Circle and c are in contact, and null otherwise. For our physics simulation to work properly it needs to know slightly more than whether or not Circle a and Circle b are in contact. It also needs to know the relative direction and distance between the centers of the two circles, which is exactly the information contained in the returned ContactResult. You do not need to modify this method.
A bounding volume hierarchy is a rooted tree. In the lectures, we modelled (rooted) trees using two separate classes “tree” and “node”, and indeed this is commonly done. In this assignment we take a different approach and define only a single “node” class called BVH. This is arguably more elegant as every “node” in a tree is just the root of another tree, and so you only need a single class. On the other hand, a disadvantage of doing this from an object oriented perspective is that it exposes the underlying data structure: users of the class would have access to the nodes of the tree.
Each BVH object has fields boundingBox, child1, child2, and containedCircle. The following method is given to you:
You must implement the following methods:
There actually exist many reasonable ways to do this, and as such we won’t enforce a particular splitting strategy so long as the tree you produce is not horribly unbalanced.
A common splitting strategy which we recommend you implement is to first determine the longest axis of boundingBox and then partition the circles based on whether the corresponding component of their center point is less than or greater than the midpoint of the boundingBox along that axis.
As an example, suppose the width of boundingBox is greater than its height. This means we want to split the box along the x axis. We can use one of the methods of the Box class to find the midpoint of the box along the x axis. We can then create two ArrayLists of Circle objects from which we define the “left” and “right” children, and then iterate over each Circle object, placing it into the appropriate list based on its position.x field. The case where height is greater than width is analogous, except we split along the y axis instead.
This class is responsible for detecting contacts between circles. You will notice that all methods here are static i.e., they only need the arguments passed to them in order to perform their task. Details about a contact are stored in ContactResult objects (see below).
You must implement the following methods:
Note that the ordering of a and b in a ContactResult DOES NOT matter. This means that we don’t care if you do a.isContacting(b) or b.isContacting(a) for two circles a and b because their return values are equivalent. Because of this, you can add both of them to the HashSet without producing duplicate contacts.
Note that you can use the enhanced for loop to iterate over a HashSet.
– If the bounding box of c does not intersect bounding box of bvh, return an empty hashset of ContactResult.
– If bvh is a leaf node, check if c is in contact with this leaf node’s containedCircle. If so, add to the HashSet of ContactResult and return the HashSet.
– If bvh is a non-leaf node and it’s children are non-null, then call the method recursively on the children. You should add any contacts detected within the children to the HashSet and return it.
This method should be efficient. In particular you should not traverse the entire tree, since this would defeat the purpose of the tree! Only traverse the nodes whose boundingBoxes you are in contact with.
You must again use the circle ids to avoid contacts between a circle and itself.
Note that like in getContactsNaive(), we don’t care about the ordering of the two circles in your contactResults, and that a circle may be in contact with many other circles simultaneously so you cannot early terminate once you find the first contact.
This class holds information about a contact once it has been detected. You don’t need to modify this class and only need to understand it at a high level. Circle a, b are the two circles in contact, contactNormal is a vector pointing from one circle to the other and penetrationDepth is the amount of overlap between two circles. The last two variables are used for physics calculations. Note that the ”contact” model here allows the circles to interpenetrate slightly before they bounce off each other.
In order to demonstrate how custom iterators can be created, we would like you to implement an iterator for the BVH datatype. Note that this portion of the assignment is completely unrelated to the above contact-finding portion. As such, you SHOULD NOT use your iterator in your contact-finding code.
The iterator we’d like for you to build will allow you to use a for-each loop to iterate over all the circles contained within a BVH as demonstrated in the exposed test BVHIteratorTest(). To do this, you will first need to implement the following methods inside the BVHIterator class, which implements the Iterator<Circle> interface:
Finally, notice that there is a method iterator() in the BVH class which you must implement. This method should simply returns a new BVHIterator() object. This method is what enables you to write for (Circle c : bvh) . DO NOT FORGET TO IMPLEMENT THIS METHOD.
This class contains exposed tests to help with your implementation. Feel free to look at individual test cases to see what exactly is being tested.
Implement the required methods in the BVH, ContactFinder and BVHIterator classes as described above.
Please follow the instructions on Ed Lessons Assignment 4.
Good luck and happy coding!
更多代写：CS澳大利亚网课代修收费 线上考试作弊方法 英国Geography地理代写 His历史学论文代写 澳洲assignment代写 代写德语论文
Properties and Applications of Binary Hypothesis Testing Detection, Estimation, and Learning 机器学习课业代写 1 How to submit your solution • The submission deadline is 23:59 on February 4,...
View details完不成程序作业该怎么办？可以找programming代写老师帮忙吗？ programming程序代写 相信很多在国外留学的同学，对国外的专业考试和作业有着莫名的紧张感和无力感，因为对当地文化不是很了解。和老师同学沟通...
View detailsESE 124 (Programming Fundamentals) Final exam review 编程基础代写 A.Sample exam questions 1) Write the following program: Use struct data type to store information about courses. Every cour...
View detailsEECE 7374 Programming Assignment 2 Reliable Transport Protocols 传输协议代写 You should work on this assignment individually or in a team of two members. One submission per team. 1.Object...
View details