karlssonper / cs348a Goto Github PK
View Code? Open in Web Editor NEWGeometric Modeling - Final Project
Home Page: http://graphics.stanford.edu/courses/cs348a-12-winter/
Geometric Modeling - Final Project
Home Page: http://graphics.stanford.edu/courses/cs348a-12-winter/
--------------------------------------------------------- | ___ ___ ____ _ _ ___ | | / __| / __| |__ / | | | ( _ ) __ _ | | | (__ \__ \ |_ \ |_ _| / _ \ / _` | | | \___| |___/ |___/ _|_|_ \___/ \__,_| | | _|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| | | '-0-0-'"'-0-0-'"'-0-0-'"'-0-0-'"'-0-0-'"'-0-0-" | | (yes, that is a train. Let's go train! | | | | Stanford cs348a - Geometric Modeling | | Final Project | | by Per Karlsson - [email protected] | | Victor Sand - [email protected] | | Steven Lesser - [email protected] | | | | Mouse - Rotate Camera view | | Press 'w/s' - Walk forward/backwards | | Press 'a/d' - Strafe left/right | | Press 'q/e' - Move tour object | | Press 'k/l' - Decrease/Increase tour speed | | | | Press '1' - Display original path | | Press '2' - Display optimal path | | Press '3' - Display both paths | | | | Press '4' - Toggle Path | | Press '5' - Toggle Control Points | | Press '6' - Toggle Control Polygon | | Press '7' - Toggle Control Polygon Extended | | Press '8' - Toggle Control Polygon Filled | | Press '9' - Toggle Sights Bounding Box | | Press 'x' - Toggle Tourer Box | | Press 't' - Toggle Terrain | | Press 'z' - Toggle Sights | | | | Press 'c' - Add New Sight | | Press 'r' - Remove Sight | | Press 'f' - Toggle first person mode | | Press 'v' - Calculate number of arcs | | Press 'b' - Calculate total length | | Press 'n' - Calculate min distance | | Press 'm' - Calculate max curvature | | | | Press 'esc' - Quit | --------------------------------------------------------- =========== How to build ============== mkdir build && cd build && cmake -DCMAKE_BUILD_TYPE=RELEASE -DCMAKE_INSTALL_PREFIX=.. .. && make install && cd .. Run the program from the bin folder. =========== High-Res textures ============== To download high res textures wget http://www.stanford.edu/~perk/texture2048.data wget http://www.stanford.edu/~perk/texture4096.data Run the program with ./main <whereever_you_put_the_texture>/texture2048.data Here is our write-up for the final project flight path program. CS348a - Final Project Per Karlsson ([email protected]) Victor Sand ([email protected]) Steve Lesser ([email protected]) =========== Part A: MinMaxer for triangulation ============== For triangulation we used the Delaunay1 algorithm on the given heightfield. We found it to be sufficiently fast for our purposes and noticably faster than the minmaxSlope despite no visual difference. Some of the other choices were not used due to them ignoring the z-value. The Delaunay1 (Lawson Flip) was chosen over the Incremental Flip version also because of speed (as desicribed in the MinMaxer documentation) while giving good results. Interfacing with MinMaxer involved modifying their sample files to read in our given heightfield data and then modifying a triangle printing function to dump the generated triangles to a data file. These values are then read into our program on launch and used to generate a Terrain class which assembles the data into a uniform grid for efficient collision detection and adds texture coordinates so we can map a Google Maps image of the area onto the terrain. ============= Part B: Planning a Smooth Tour =============== To compute our tour we used the previously attained triangulation data, a loaded list of points of interest (POIs) and a math engine capable of detecting collisions on the terrain with points, line segments, and bezier curves. Our algorithm proceeded as follows: Initialize a control point midway between each POI and raised a fraction of the total length of the distance between the control points For each POI p except the first and last: Get the midway control point cp0 previous to p Get the midway control point cp2 following p Form a plane P with the points cp0,p,cp2 Create vectors v1=(p-cp0).normalize and v2=(p-cp2).normalize Expand a triangle from point p which lies in plane P with the given constraints: One vertex t1 lies in the line p+(v1+v2)*a where a is a scalar One vertex t0 lies in the line segment from t1 to cp0 One vertex t2 lies in the line segment from t1 to cp2 t1 and t2 are equidistant from t0 p lies in the center of t0,t1,t2 Place control points at t0, t1 and t2 if collision is detected or curvature is extreme: Move control points cp0 and cp2 up in the air or away from each other and recursively perform this same algorithm on their adjacent POI endFor For the first and last POI: set a control point at the POI endFor The reasoning behind this algorithm is that it is generally safest for a flight to never go lower than it absolutely has to, hence the POI should be the lowest points on the local curve. To ensure this a bezier curve is formed around each POI such that the lowest point intersects the POI. One way to accomplish this is to form a triangle around the POI with the POI lying the the center of it so if the triangle's vertices were control points of a bezier curve, the curve would intersect the POI at t=0.5 interpolation. In order for this to work out, an additional control point must be added between each pair of POI so there is a longer "travel curve" between each pair of POIs and a shorter "dive curve" around each POI. The algorithm is essentially a way to effeciently construct these requirements by looking at a single POI and the two adjacent "travel curve" control points at a time. The rest of the algorithm arises naturally from ensuring C1 continuity and staying within particular fixed planes. To avoid collisions, we detect collisions along the candidate bezier curves of each POI and the following "travel curve." Collisions are effeciently found with the aid of a uniform grid spatial data structure. If collisions are found we adjust the positions of the midpoint control points since raising them generates a more dramatic dive for the adjacent control points and allows the flight to move over more obstacles. The control points are then re-evaluated for each adjacent POI. Similarly, extreme curvatures are handled by detecting when a curve creates a curvature greater than a specified minimum, and if so the mid control points are moved away from each other so there is more space between control points and a gentler curve. We used a d=100 size bounding cube of region to collide with as a valid hit with the POI. =============== Part C: Viewing the Tour ==================== We created our program using GLUT to offer capabilities of animation, user input, and multiple views. We render our terrain using a texture map we obtained from Google Maps and warped in photoshop to align with the given data. Multiple views can be toggled including a minimap showing an overall view of the area. Additionally points can be added and removed by interacting with the command line. Our animation is done by evaluating the bezier curves in order and using gluLookAt to set the current position as a position on the curve and the point to look as a point a little further ahead of the current point. This gives a roller coaster effect and is pretty fun. A top-down orthographic minimap is provided to visualize the global progress of the camera. We render the POIs as multiple colored boxes and additionally render each control point with a green box to better visualize the construction of the quad. ============== Part D: On the Fly Changes =================== Our algorithm constructs the path by iterating through the POIs and locally constructing the control points around the POI. Hence to remove a POI we need only remove it and then reconstruct the two adjacent POIs. To add a POI we add a new midpoint and construct the two new path segment surrounding the new POI and reconstruct the previous two adjacent POIs (since their midpoints relative to the now moved point have changed). ========== Part E: Tours for Unordered Sites ================ Since our algorithm for planning a smooth tour described in Part B is guaranteed to work between any sights, our method to find the optimal path for all sights uses euclidean distance. The method can be described in the following way: pick a starting point A add A to a ordered list find point B with the minimum distance from point A add B to the ordered list find point C with the minimum distance to point B from points which are not yet in the ordered list .. .. until all points have been added to the ordered list We simply try all sights as starting points and the one who produces the smallest total length of the sight tour is picked as the final starting point. This method is not close to any global solution of the general Traveling Salesman Problem but it works very well for the given data in this assignment. The major drawback of this method is that we can be unlucky and in the end only have remaining points that are very far from each other. ========== Part F: Metrics ================================== Total length: 182622 units Minimum vertical distance: 54.2 units Maximum curvature: 0.27 units Number of distinct curves: 27 The measurements are done by evaluation at a certain number of points for each curve segment. To make sure that accuracy is adequate, the stepsize has been gradually lowered until the values start to converge at a satisfactory rate. ================== CONTROL POINTS =========================== Control Point (0): (-3603.0,4592.0,206.1) Control Point (1): (138.0,2497.5,936.7) Control Point (2): (3376.7,543.5,362.9) Control Point (3): (4153.5, 74.8,225.3) Control Point (4): (3840.7,925.8,367.5) Control Point (5): (1498.5,7298.0,1432.3) Control Point (6): (-654.4,13864.0,292.3) Control Point (7): (-867.3,14513.3,179.5) Control Point (8): (-1127.4,13881.0,289.9) Control Point (9): (-2204.0,11263.5,747.0) Control Point (10): (-3455.1,8784.1,271.6) Control Point (11): (-3777.8,8144.5,149.0) Control Point (12): (-3089.3,8257.1,352.9) Control Point (13): (686.5,8875.0,1470.7) Control Point (14): (4475.7,9322.5,1353.2) Control Point (15): (5323.6,9422.6,1326.9) Control Point (16): (4473.0,9496.5,1355.0) Control Point (17): (594.0,9833.5,1483.2) Control Point (18): (-3282.4,10222.0,375.5) Control Point (19): (-4145.8,10308.5,128.8) Control Point (20): (-3269.7,10164.0,287.8) Control Point (21): (3037.2,9123.3,1432.6) Control Point (22): (8685.2,5892.0,573.9) Control Point (23): (9273.7,5555.3,484.4) Control Point (24): (8627.2,5756.9,580.1) Control Point (25): (1360.8,8023.3,1655.2) Control Point (26): (-5332.9,10525.2,374.3) Control Point (27): (-6827.5,11083.8, 88.3) Control Point (28): (-5255.4,10785.8,348.0) Control Point (29): (3887.0,9052.5,1858.3) Control Point (30): (13131.2,7585.2,340.6) Control Point (31): (14406.9,7382.7,131.2) Control Point (32): (13390.4,6610.5,419.2) Control Point (33): (9289.5,3495.0,1580.9) Control Point (34): (4861.1,-60.3,254.2) Control Point (35): (4635.0,-241.8,186.4) Control Point (36): (4844.9,-439.3,261.4) Control Point (37): (7991.0,-3399.5,1385.3) Control Point (38): (10660.8,-5637.2,488.3) Control Point (39): (11672.8,-6485.4,148.3) Control Point (40): (10946.2,-7608.0,415.3) Control Point (41): (8856.5,-10836.8,1183.0) Control Point (42): (5372.1,-13848.2,259.8) Control Point (43): (5009.8,-14161.3,163.8) Control Point (44): (5315.6,-13788.5,240.9) Control Point (45): (12190.8,-5407.9,1975.3) Control Point (46): (18859.7,1654.4,454.4) Control Point (47): (20495.7,3386.9, 81.3) Control Point (48): (18117.0,3272.3,463.5) Control Point (49): (6855.0,2729.5,2272.9) Control Point (50): (-5463.1,2581.0,281.3) Control Point (51): (-6093.1,2573.4,179.5) Control Point (52): (-5482.0,2421.9,284.2) Control Point (53): (-2761.0,1747.5,750.3) Control Point (54): (261.0,959.0,270.1) // Often used commands! command of doom: mkdir build && cd build && cmake -DCMAKE_BUILD_TYPE=DEBUG -DCMAKE_INSTALL_PREFIX=.. .. && make install setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:$HOME/Dev/cs348a/project.git/lib
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.