Sinan Gunes and Cihat Turhan
-
Implementation of Least-Effort Trajectories for Emergent Crowd Behavior in Crowd Simulations
1. Introduction
Crowd simulation is a significant approach to simulate flow of people, objects and animals. Today’s application is generally based on social sciences, traffic engineering, architecture, urban planning, robotics etc. [1].
We will use C++ and OpenGL to simulate the crowd. We will utilize Principle of Least Effort (PLE), that is minimum energy principle of an individual. This principle is based on Lagrangian formulations in classical mechanics [2].
2. Problem Definition
We will implement an algorithm to demonstrate large-scale crowds at interactive rates based on PLE which is generated by J. Guy at al [1]. Our method will use an optimization technique to compute energy-efficient bodies, paths without collision that minimizes the amount of effort for each individual in a large crowd.
3. Assessing Solutions
The technique requires high CPU computing as it’s needed to calculate each individual’s trajectory so in the first stage it won’t be a real time application. In addition, this application may not work in old systems because new OpenGL shell doesn’t have backward compatibility.
References
- Stephen J. Guy, Sean Curtis, Ming C. Lin, and Dinesh Manocha, Jatin Chhugani and Pradeep Dubey, PLEdestrians: A Least-Effort Approach to Crowd Simulation,
Eurographics/ACM SIGGRAPH Symposium on Computer Animation, Madrid, Spain, 2010.
- George Kingsley Zipf, Human behavior and The Principle of Least Effort, Addison-Wesley Press, 1949.
- Stephen J. Guy, Sean Curtis, Ming C. Lin, and Dinesh Manocha, Least-Effort Trajectories Lead to Emergent Crowd Behaviors,
Physical Review E, vol. 85, p. 16110, 2012.
Hasan Hamzaçebi and Onur Yorulmaz
-
Implementation of a Program Finding the Intersection, Union, and Difference of Two Polygons in 2D
This project will mainly focus on the intersection, union, and difference of two simple polygons on a plane (2D polygons). The polygons are not restricted to be convex. However, complex polygons will not be included, since there may not be an interior and exterior region differentiation, which makes it impossible to calculate a union, intersection or difference. The requested properties may be calculated separately or combinatory (i.e. if finding the union is found to be advantageous to find difference, then this union region may be calculated first).
The implemented software is planned to get input via two different methods; a text file that contains the information of the polygons in DCEL format, or a visual input area in which the users can select the successive points that form the simple polygons. In the second method, mouse will mainly be used to add a new point. Keyboard can also be used to add points by giving the coordinate values. Resulting region, which can be union, intersection or difference of the polygons, will be shown on the screen as well as it will be given as an output to a text file with DCEL format. When we apply simple transformations to the input polygons using mouse,
such as translation, scaling and rotation, resulting polygons will be calculated and shown interactively on the screen.
In our implementation, we are planning to use the algorithm by Maharaj Mukherjee "An Efficient and Simple Polygon Intersection Algorithm". The algorithm focuses on intersection, however we believe it can be extended to union and difference. The algorithm has several steps with several complexities. The first step seems to have the highest complexity which finds all the intersecting edges. Complexity at this step is O(n_p × n_q) where n_p and n_q are the number of edges of the polygons P and Q. Where n_p and n_q are close numbers, the dominant complexity of the algorithm is estimated to be O(n^2).
Ramazan YILMAZ
-
Finding the Closest Point for Each Point in a Given Set of Points
In this project, I plan to solve the problem of finding the closest point for each point in a given set of points using the sweeping technique. The trivial algorithm’s running time complexity is O(n^2). I will try to beat that algorithm using the sweeping technique. Using sweeping technique reduces the complexity from O(n^2) to O(nlogn) for the problem of finding the closest pair of points given a point set. I hope to beat the obvious algrorithm for the aforementioned problem in a similar fashion.
I will use JavaFX during the implementation of the algorithm, and I intend to embellish the user interface using tiny animations and effects. The program will
animate the algorithm step-by-step during the execution and show the all the closest pairs interactively.
Erdem Özdemir and Fahreddin Sükrü Torun
-
Implementation of Orthogonal Range Searching Using kd-trees
In this project, we will implement Orthogonal Range Searching using
kd-tree data structure. Our application will take the inputs (using mouse)
from the user and will illustrate the construction of the kd-tree and
search process in a user friendly manner. We will use Java via 2D graphic
library during the implementation of the algorithm. The algorithm execution
will be shown interactively step-by-step on the data set.
Seher Acer and Ozlem Basak Iskender
-
Parallel Convex Hull Algorithms
We will parallelize the recursive convex hull algorithm (in slides 227-235) that utilizes the divide-and-conquer paradigm. We will divide the point set into k approximately equal-sized subsets, where k is a power of two, and assign each subset to a unique parallel processing element (PE). First, all PEs compute their convex hulls in parallel and the resulting convex hulls are repeatedly merged up to a final one in logk iterations in a bottom-up manner. At each iteration, some of the PEs send/receive their convex hulls to/from some other PEs and two convex hulls are merged in the receivers.
As a baseline algorithm, we will implement the serial Graham’s scan algorithm, and compare the running times of two algorithms with varying number of points and number of PEs.
Gokcen Cimen and Ufuk Celikcan
-
Camera Positioning for Perception-based Viewpoint Preference Using Slab Method and Octree Structure
The problem of finding good views of a 3D object is an issue that has been discussed within numerous researches in perception, computer vision, and computer graphics. Therefore a large variety of measures quantifying the goodness of views and some special-case viewpoint selection algorithms have been developed over the years.
Combining perception-based methods with an effective computational geometric approach, we plan to offer a novel algorithm to position the camera looking at a 3D object leveraging the framework used by Secord et al. [1] to optimize the parameters of a general model for viewpoint goodness. This framework is chosen due to its flexibility to incorporate new attributes like our saliency features.
In this project, we will follow an approach deciding where to position a camera by considering what information should be conveyed achieving maximum saliency. Thus, we plan to evaluate the goodness of viewpoints by using an Octree Space Partitioning (OSP) algorithm and choose the best viewpoint by calculating the total sum of mesh saliency visible from all possible viewpoints.
Reference:
[1] Adrian Secord, Jingwan Lu, Adam Finkelstein, Manish Singh, and Andrew Nealen. 2011. Perceptual models of viewpoint preference. ACM Trans. Graph. 30, 5, Article 109 (October 2011), 12 pages. DOI=10.1145/2019627.2019628 http://doi.acm.org/10.1145/2019627.2019628
Hasan Balci and Mehmet Faruk Ongun
-
?????
Cem Murat Turgut
-
Implementation of Delaunay Triangulation in 3-dimensions.
The program should have a good user interface to enter the input points and to see the
results.
Fethi Burak Sazoglu
-
Comparison of Mergehull and Quickhull Algorithms for finding Convex Hull in 2D
Convex hull of a set of points in 2D can be conducted by a divide and conquer algorithm that resembles merge-sort [1]. Quickhull is another divide and conquer approach for the same problem, but in quickhull the subproblem size cannot be controlled as the point set is divided into 2 sets with a line passing through the points with maximum and minimum x coordinates. However, merge-sort approach directly divides the set into 2 equal sized subsets of points.
The conquer part of mergehull algorithm is the union of 2 convex polygons as subproblems returns convex polygons. They can be merged in O (N) time, by finding an angular order of points in both subproblems about a point inside one of the polygons and applying Graham’s scan [2].
Quickhull continuously divides the points into 2 regions with the line passing through the points with the maximum and minimum x coordinates, which are guaranteed to be in the convex hull. However, the line does not split the points into equal-size subsets. Thus, in worst case quickhull is an O (N^2) algorithm.
The divide and conquer phases of the algorithms will be showed step by step during the extraction of the convex hull. The point set will be taken via mouse or keyboard from the user. In later stages, the users can be allowed to change the location of a point during the execution of the algorithm to visualize the change in the execution of the algorithm. Upon execution of each conquer stage the convex hull of each subproblem will be shown in a short period of time until next conquer step. Users can compare the time it takes to compute the convex hull using merge-hull and quickhull with the proposed implementation.
References
[1] Franco P. Preparata, S.J. Hong. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Commun. ACM, vol. 20, no. 2, pp. 87–93, 1977.
[2] Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133
Bahaeddin Eravci
-
Partitioning a Polygon into Convex Polygons
Most geometric problems are simpler and faster on convex objects than on non-convex ones. Because of this, algorithms that partition 2D concave polygons into convex polygons are an important pre-processing step in the implementation of other complex algorithms.
Triangulation is the most essential partitioning algorithm but one may also be seeking minimal number of polygons after the partitioning. This gave way to different algorithms in this area, some being optimal, some sub-optimal.
In this project an algorithm will be implemented to partition 2D polygons into convex sub-polygons. The input will be either by selecting points in the plane by mouse, or by a text file of the vertices of the polygon. It will be coded in MATLAB. The possible algorithms to be used is the Hertel-Mehlhorn algorithm.
Ozgur Gultekin
-
?????
Mahmut Burak Senol
-
Design and Implementation of 3D Voronoi Diagram for a Set of Points in 3D.
The program will be tested by using some random data and finding the nearest
neighbors of points using the 3D Voronoi Diagram. You should be able to
display the 3D output graphically with appropriate transformations (rotation, zoom in/out, etc.).