Slashdot Mirror


Fast Generation of 3D City Models

FleaPlus writes "New Scientist and UC Berkeley News report on research by Avideh Zakhor and Christian Früh on rapidly and automatically generating photo-realistic 3D models (coral cache) of city environments. This is reminiscent of research mentioned here in March, although the approach is rather different. Applications for areas like urban planning, entertainment, emergency response, and the military are discussed. Zakhor's group is also working on 4D systems, to allow for recording of events over time as moving 3D models."

84 comments

  1. Finally!! by Anonymous Coward · · Score: 5, Funny

    The long awaited release of Sim City 5

    1. Re:Finally!! by Anonymous Coward · · Score: 0

      San Andreas already did this crap.

  2. SGI? by dclaw · · Score: 2, Interesting

    If I remember correctly... companies like Silicon Graphics have been doing this for several years for the military using their reality center systems to analyze satellite photographs of combat zones in real time.

    --
    feeling lonely? grab a balled up pillow for company
    1. Re:SGI? by Anonymous Coward · · Score: 1, Insightful

      can we have a special moderation adjective for the first asswipe to say 'Meh, people have been doing this for years!' Something like "-1, Nothing New Under the Sun"? Thank you.

    2. Re:SGI? by Janitha · · Score: 2, Interesting

      But that was mostly done with scanning the distance around a given point (or several points), and it had no image but just a depth map, even if there was image it would be used to simply identify more the object at a given point, not to this scale.

      This is quite impressive, yet they still have to work out those glitches that are quite visible. Its fast, but they are giving away precision for speed.

      The other thing I don't understand is the used for rapid generation of these, speed is good, but cutting down on how accurate it is for speed is not acceptable. A better view would be pre-rendering the images with more precision/accuracy. Not like buildings come and go every day.

    3. Re:SGI? by dclaw · · Score: 1

      true, it was not done to this scale... and was certainly not photo-realistic... but, it was still distinct enough to make out exact buildings and landmarks.... and certainly enough to make out billboards and other such high visibility marketing.... and the last iteration I saw of such technology, which was about 2 years ago was using multiple satellite images of an area:

      1 or more top down pictures of the area, plus usually a 4-way side view of the area... giving "recognizable" quality representations of buildings that were rendered to accurate size.

      anyway... yeah..... further explanation concluded.... I was at work when I wrote that quick blurb....

      --
      feeling lonely? grab a balled up pillow for company
    4. Re:SGI? by Money+for+Nothin' · · Score: 1

      can we have a special moderation adjective for the first asswipe to say 'Meh, people have been doing this for years!' Something like "-1, Nothing New Under the Sun"?

      You want an acronym that would be spelled "NNUTS"? :)
  3. Flight Simulator by Anonymous Coward · · Score: 3, Informative

    This would be awesome for flight sims. If you want to view this in this in Linux here is a viewer.

    1. Re:Flight Simulator by roseblood · · Score: 1, Insightful

      This would be awesome for flight sims.

      This way when you crash your virtual air-liner into an occupied landmark structure you'll be able to accurately determine which floor, even witch windows, will be hit as you commit you're holy jihad and make your way to the company of 72 (isn't 42 enough?) virgins.

      --
      There are lies, damned lies, and statistics.
    2. Re:Flight Simulator by Anonymous Coward · · Score: 0

      I used Tux Racer to plan out my terrorist attack, ramming my sled into the side of the United States embassy in Antarctica. It didn't even punch through the wall though, and I broke my pinkie, and they all laughed. :(

    3. Re:Flight Simulator by Anonymous Coward · · Score: 0
      Eric Bin Raymond: The September 11th Conspiracy Revealed

      When you have a crime to investigate, and you have no suspects, where do you start? Obviously you begin by looking at the person or persons who have the most to gain by perpetrating the crime.

      This is why we must consider: who had something to gain from the disasterous crimes of September 11th? Obviously not Osama Bin Laden, who would net no financial windfall from the destruction of the World Trade Center and the Pentagon. Although he has loudly applauded the "terrorist" acts of September 11th and even tacitly taken credit for them, there is no reason to believe that he is anything more than a bandwagon jumper. Being blamed for the destruction of the World Trade Center has done more for his image than any amount of militant Islamic rhetoric.

      But if not Bin Laden, then who?

      It so happens that on December 11th, "coincidentally" 2 months after the tragedy, Credit Suisse First Boston quietly agreed to pay out US$100 million in order to settle an 18 month old investigation into its handling of certain high-profile technology IPOs (Initial Public Offerings). One of the most controversial amongst these being the IPO of VA Linux Systems, Inc. (LNUX) .

      VA Linux Systems, Inc., now known as VA Software, is widely derided as a poster child of the dot-com bust, though inexplicably still in business. At the time of the IPO, VA Linux (Software) shares opened trading at nearly 10 times their $30 offer price, closing the first day of trading at $239.25. This meteoric rise made many early investors rich, strangely on account of a company which purports to sell a hobbyist operating system which can be obtained for free on the Internet. "The VA Linux initial public offering is a prime example of market manipulation in an IPO by investment banks, their customers and the issuing firm," said Steven Schulman, a partner in the law firm Milberg Weiss Bershad Hynes & Lerach, which specializes in filing shareholder suits.

      "Because certain favored customers of the investment banks agreed to buy shares in a new issue at inflated prices in the aftermarket (in return for getting an allocation of the shares at the initial offering price) the share prices to which the IPO eventually soared were actually driven by artificial market forces," continues Schulman.

      But what does the VA Software (Linux) IPO have to do with the attacks on September 11th, and what has that to do with the Credit Suisse settlement? Well, considering that VA Linux (Software) got CSFB into trouble in the first place, it stands to reason that the VA Linux (Software) Board of Directors were complicit in the stock fraud from beginning to end. As the investigation progressed against CSFB, the unscrupulous VA Software/Linux executives, their pockets bulging with filthy lucre plundered from trusting, hard-working investors, must have realized that their days in the country club were numbered if the SEC discovered their wrongdoings.

      The SEC, or Securities Exchange Commission, is a federal regulatory agency, and cannot be bribed. Therefore, with a possible stint in federal prison looming large, Larry Augustin and the rest of the crooks, including outspoken gun violence advocate Eric S. Raymond, decided to undertake more active means to halt the investigation.

      The Plan

      It so happened that all the evidence in the CSFB/

  4. Military, eh? by peculiarmethod · · Score: 1

    Now the military can fake invasions in cities while working with the media to control us all. Cool. /removal of tin

    --
    ** "It's not my job to stand between the people talking to me, and the ones listening to me." -- Pego the Jerk
    1. Re:Military, eh? by Phil06 · · Score: 2, Funny

      If there is a way to help oppressed people rid themselves of murderous tyrants without killing lots of people and destroying cities I'm all for it. Then we wouldn't need a miltary anymore because democracies don't start wars.

      --
      "...and yet, I blame society" Duke - Repo Man
    2. Re:Military, eh? by triznitch · · Score: 1

      democracies don't start wars.

      mod that up for funny.

      --
      "In times of universal deceit, telling the truth will be a revolutionary act." -George Orwell
    3. Re:Military, eh? by Anonymous Coward · · Score: 0

      umm actually democracies do start wars. in a democracy the majority decides everything, so it is basically mob rule. if all of a sudden the majority wanted to take away rights from all white people it could happen. obviously democracies can be oppressive. For example take nazi germany - they democratically elected Hitler into power.

      and a military is about self-defense. it's pretty naive to think that there will never be evil. we will always need a military in order to ensure the safety of our citizens.

      hate to burst your bubble, but pacifism only leads to trouble.

    4. Re:Military, eh? by Phil06 · · Score: 1

      The US has nothing againts the people of Iraq. We tried through all kinds of technology to only take out the murderous genocidal tyrant aggressor Saddam Hussein. The war would have not even started if the technology had worked. It didn't, I'm all for trying to improve the technology so we don't have to destroy a country in order to save it. Saddam killed all the people who disagreed with him, the opposite of democracy. That is not funny.

      --
      "...and yet, I blame society" Duke - Repo Man
    5. Re:Military, eh? by andreyw · · Score: 0, Offtopic

      http://news.bbc.co.uk/1/hi/uk_politics/vote_2005/f rontpage/4503061.stm

      Why the fuck did we go to war, causing more instability in the region, countless civilian and military deaths, destruction of property and countless archaelogical sites and finds, again??

    6. Re:Military, eh? by triznitch · · Score: 1

      so we don't have to destroy a country in order to save it

      i suppose there is no room for relativism in the world. however, if there was then i do not understand why the united states is the only country in the world that knows what is right and every one else needs to be saved. please keep your xenophobic and arrogant opinions to yourself. it is not the united states' job to save everyone. we cannot even save ourselves. and even if that was our job, how is forced starvation of a people through sanctions followed up with massive bombing and military occupation helpful? i'm sure the germans thought they could save us during world war two. point is: the united states does not have some sort of righteousness attributed to it just because it is the united states. we murder and plunder and use imperial aggression just as much, if not more, than the next country. if it is wrong for another nation to do it, it is wrong for the united states to do it too. iraq was not about defense and it is not about liberation. if we were interested in liberation we would stop funding brutal dictatorships and training human rights violators in latin america.

      --
      "In times of universal deceit, telling the truth will be a revolutionary act." -George Orwell
  5. Photo Realistic 3d? by drspliff · · Score: 1, Troll

    Excuse me.. but 'photo realistic' usually means that it is close or completly indiscernable the same as an actual photo of a real city. To be honest I've seen similar things from Sim City 2000 and see no real merit from the 'final product'. Really, how is this new? Sim City? huh? Nevermind!

    1. Re:Photo Realistic 3d? by Anonymous Coward · · Score: 0
      To be honest I've seen similar things from Sim City 2000 and see no real merit from the 'final product'.
      No, it IS photo realistic, they took a photograph of someone playing Sim City.
    2. Re:Photo Realistic 3d? by Anonymous Coward · · Score: 1, Interesting

      What's new here is that street-level capture took 25 minutes of driving and was completely automated.

    3. Re:Photo Realistic 3d? by Anonymous Coward · · Score: 0

      fuck me?! you need to grow a dong first you caulking tube of ass ointment

    4. Re:Photo Realistic 3d? by Anonymous Coward · · Score: 0

      she? they're both guys.

  6. torrent of the 100MB VRML model: Berkeley.zip by Anonymous Coward · · Score: 3, Informative
  7. Coral cache link in article text? by Anonymous Coward · · Score: 0

    Who are you and what have you done with the real Timothy?

    1. Re:Coral cache link in article text? by Anonymous Coward · · Score: 0

      Timmy's cinnamon ring is being violated right now. He'll be returned (mostly) unharmed soon. Sorry for the inconvenience.

  8. Re:lol WWWWIDE PAEG!! by Anonymous Coward · · Score: 2, Funny

    Slashcode is smarter than you.

  9. Nah by FlyByPC · · Score: 1

    I've seen more realistic scenery in Flight Simulator.

    --
    Paleotechnologist and connoisseur of pretty shiny things.
    1. Re:Nah by Murphy+Murph · · Score: 1
      I've seen more realistic scenery in Flight Simulator.


      Prettier maybe, but not more accurate or easy to compile.
      --
      I dub thee... Sir Phobos, Knight of Mars, Beater of Ass.
    2. Re:Nah by Tyler+Eaves · · Score: 1

      You might be surprised what can be obtained. In my Flightsim install, while admittedly buildings aren't accurate outside of the major cities, I've got every road, powerline, and railroad track in the US. Also got terrain with 15m (or less) data point spacing across the entire US. Flying over the rockies looks absolutely stunning.

      --
      TODO: Something witty here...
  10. torrent of the 100MB VRML model: Berkeley.zip by uwtorrents · · Score: 0, Redundant
  11. some links by Anonymous Coward · · Score: 1, Informative

    http://www.engadget.com/entry/1234000960042343/

    this also provides some more info on this

    http://meinherz.net/

  12. lidar by kebes · · Score: 4, Interesting

    This technique should be replaced with (or combined with) LIDAR techniques. LIDAR (Light Detecting And Ranging) is like a laser version of radar, and it can be used to generate 3D maps of objects or topography fairly quickly. A LIDAR-enabled plane can do a fly-over of a city and quickly generate 3D maps. For instance, check out these LIDAR images of New York pre and post 9/11.

    I've always thought that these 3D maps of cities should be combined with satellite imagery so that you could 'paint' the rooftops onto the buildings and streets. In fact, most satellite images are at a slight angle, allowing you to paint the facades of buildings. The techniques from TFA show how you could paint even more facades in the 3D model/map fairly easily. I think the LIDAR data would greatly simplify the painting algorithm, since the correct 3D shape of every object is known.

    I can't wait for the day when we can browse 3D maps online of any city. It would be useful for surveyors and architects of course, but also useful for planning trips, learning geography, and so on.

    1. Re:lidar by ian+mills · · Score: 1

      nice troll. Why don't you try reading the linked page nextime? Thats exactly what they're doing.
      From the FA.
      Airborne Modeling Generation of 3D models of rooftops and terrain shape from airborne laser scans and photos.
      Processing airborne laser scans
      Reconstructing surface geometry
      Texture mapping

    2. Re:lidar by way2trivial · · Score: 1

      I'm into panoramic photography, and always wondered, how involved would it be to mount a fisheye lens to a video camera mounted on the front left corner of a car hood, and drive up and down each street of a city (both directions) including all alleys, connected to a REALLY GOOD gps system, then have a QTVR composite that lets me manovuer at will through the city, up down/back right, turn, spin... I could have a map of a town, pick any street and orientation as a start point, and then just turn and advance- and the video would be of my 'location' as chosen...

      what kind of database/live edit system would it take to combine all that video to make transitions around corners smooth at the point where the video lines crossed on perpendicular streets?

      --
      every day http://en.wikipedia.org/wiki/Special:Random
    3. Re:lidar by Hast · · Score: 1

      I'd say you'd be better off using multiple cameras so that you capture multiple directions at once. If you don't you'll probably have a very hard time making the result match up. (Ie have the same spot in the road in both directions at the same time.)

      There are systems like this however. If you look up computer vision research you can typically see stuff about systems that automatically build a "map" of the world. (Typically used with robots.)

  13. 4d Futurists by sellin'papes · · Score: 3, Interesting
    Reminds me the futurist painters in the 1920s and 30s. They would try and capture an object from all different angles and movements for a period of time in one image.

    For instance Picasso (in his early days) did paintings of peoples faces from different angles and with different emotions all as one face.

    --
    This is my last post.
    [6th Estate]
    1. Re:4d Futurists by zeromemory · · Score: 1

      Reminds me the futurist painters in the 1920s and 30s.

      They were called cubists.

    2. Re:4d Futurists by Anonymous Coward · · Score: 0

      Ok way off topic but .... Uh the futurist used Cubism. Picasso was a cubist. Braque was a cubist. Filippo Tommaso Marinetti was a futurist. The futurist basically stole the cubist aesthetic and applied it to the instudrial era of the 1920's "Cubism had run its course by the end of World War I, but among the movements directly influenced by it were Orphism, Purism, Precisionism, Futurism, Constructivism, and, to some degree, Expressionism." "Futurism is an Italian modernist movement celebrating the technological era. It was largely inspired by the development of Cubism. The core themes of Futurist thought and art were machines and motion.http://www.artcyclopedia.com/>

    3. Re:4d Futurists by sellin'papes · · Score: 1

      I stand corrected. And the dates I mentioned are off by...oh about two years or so. Cubism

      --
      This is my last post.
      [6th Estate]
    4. Re:4d Futurists by Anonymous Coward · · Score: 0

      Futurism is not the same as Cubism.

  14. Photorealistic? by Anonymous Coward · · Score: 0
    What the hell?

    Where are the crackwhores, pimps and junkies?

  15. Re:lol WWWWIDE PAEG!! by Anonymous Coward · · Score: 0

    That, sir, is a bloody insult!

  16. Why is it so quiet on Slashdot? by Anonymous Coward · · Score: 0

    Is some big backbone route in the USA broken or is it some kind of a holiday? I hope you're not saying that people are actually spending a Saturday night out, for chrissake!

  17. yess! by Anonymous Coward · · Score: 0

    finally live action 3d pr0n!!!!!!!!!!!!!!!!!

  18. PWN3D!!1 by Anonymous Coward · · Score: 0

    You, I mean.

    Please die. Or at least get one of those "brain" things.

  19. Wonder how it fares with European cities by Matthias+Wiesmann · · Score: 4, Interesting
    All the examples shown in linked article are US style cities, with straight roads and relatively simple roughly cubical buildings. I wonder how this technique fare with more complex buildings and street arrangement, as you find in the center of many European cities.

    I would really be impressed if they could automatically generate a 3D model of the three dimensional mess that is Lausanne:

  20. That's what they claim... by Urusai · · Score: 1

    ...I claim he was just painting angular, childish drawings requiring no particular talent, and then threw some meta-artistic gloss on it.

    1. Re:That's what they claim... by zeromemory · · Score: 1

      I claim he was just painting angular, childish drawings requiring no particular talent

      I respectfully beg to differ. When you or any child can paint something as nice as Les Desmoiselles d'Avignon, I'll admit that Picasso was without talent. Sure, a lot of 'modern' art these days is bunk, but Picasso shouldn't be classified with that junk.

    2. Re:That's what they claim... by I+don't+want+to+spen · · Score: 2, Insightful
      I thought so too (a long time ago). But then I saw some of his earlier, realistic stuff and realised that he painted abstract art because he wanted to, not because he had to. Look at this for an example.

      I still prefer Dali though ...

      --
      Don't go to a brothel if you want to buy broth
    3. Re:That's what they claim... by RollingThunder · · Score: 1, Insightful

      That's "nice"?

      I guess it is in the eye of the beholder. I see disjointed garbage.

    4. Re:That's what they claim... by Anonymous Coward · · Score: 1, Funny
      You still prefer Dali? That's because he was a fag and a poseur. That's why so many Slashdotters would prefer him.
      But... you're a Slashdotter too...
  21. a lot of people doing it by S3D · · Score: 1

    for example
    http://www.geosimcities.com/showroom_Phil.htm They were using laser to scan cityscape too.

  22. Integrate with GPS by Anonymous Coward · · Score: 0

    It would be great to have this integrated to a GPS or something .. you can polan routes and tell what sort of a neighborhood a restaurant is in etc. I await the day for cameras to be equipped with GPS .. well current camera phones .. they dont write GPS data into the EXIF do they. Anyway .. integrate that tech with location and time etc. and you can have reviews of restuarants and picture or video records of neighborhoods etc. at whatever times. It would be awesome. All at the tap of one's fingers .. google is helping facilitate this with google maps .. now we need a wiki type thing to enable this sort of thing.

    1. Re:Integrate with GPS by Anonymous Coward · · Score: 0

      Yeah, foreally though... you know what would be totally awesome, if you SHUT THE FUCK UP... right, awesome...

  23. How do they account for light/shadows by DrFalkyn · · Score: 1

    The problem with these techniques is there are no algorithms I know of that account for the effect of light/shadows effectively. So the textures on your objects are going to include shadows. You can notice this effect on one of the images that have linked to in the article.

    1. Re:How do they account for light/shadows by Anonymous Coward · · Score: 0

      So they brute force it, repeat the scans at multiple times of day. The trick would be to realign the scans to account for the variation in route, but at the resolution and frequency they are using alignment with enough precision to augment results should be very possible. Multiple sweeps of the same area would then gradually improve the precision of the results.

      A very few minor additional layers would greatly improve the still-shots posted on the site. 'real' streets with lane markers comes to mind as an easy upgrade with very good side effects (mapping applications with complex intersections).

      maps.google.com next innovation, zoom-in to virtual street level. That would be cool.

    2. Re:How do they account for light/shadows by RichardX · · Score: 1

      Just a guess, but couldn't you tell it where the light source is in the 3D image and have it calculate the lighting/shadows (as you would in any 3D scene) - get them to match up with the shadows you observe in the image, and use that to colour correct the textures

      --
      Curiosity was framed. Ignorance killed the cat.
  24. Yahoo A9 Yellow Pages? by oblique303 · · Score: 1
    I wonder how long until Yahoo's A9 search engine (or another company in a competing effort) incorporates this technology into their "Block View" street digitization project.

    http://a9.com/-/company/YellowPages.jsp

    Yahoo has been digitizing the front of buildings in major cities for some time now. It'd be great to see this imagery merged with Google's satellite view data from their KeyHole acquisition, to allow for 3d flythroughs of your favorite metropolitan area.

    This could take sites like MapQuest to a new level, providing 3d photo-realistic flythroughs of your route between two locations. Sure beats reading directions!

    1. Re:Yahoo A9 Yellow Pages? by SteelV · · Score: 1

      Actually A9.com is Amazon's, not Yahoo's. Don't really see why Yahoo would make another search engine to compete with itself, anyway.

    2. Re:Yahoo A9 Yellow Pages? by Anonymous Coward · · Score: 0

      Yes, I enjoy viewing that website on my Dell Macintosh. If you'll excuse me, I need to go get into my Toyota Mustang and drive to the store.

  25. When I see this... by John+Pfeiffer · · Score: 1

    ...I can't think of anything more intelligent to say than "Damn, the next Sim City is going to be AWESOME!"

    That and, as a computer animator, I can see this being very useful various CG fields.

    --

    Friend: "The NIC is misconfigured..." Me: "No prob, I'll just telnet in and fix it." *Silence*
  26. If you are a windows fanatic... by Anonymous Coward · · Score: 0

    There now follows an ASCII representation of your genitalia (actual size when shown on a 3" monitor)

    :-

    Thank you.

  27. 4D by marcuspl · · Score: 1
    I understand what they mean by a "4D modelling system" and all, but is that really the most adequate term for 3D scene recording / editing? Does it even have a cool-buzz-word-hype ring to it?

    Or was it called "4D Studio Max"? It has been a while since I abandoned the world of 4D editing, for good ol' simple 1D (top down yeah?) programming...

    1. Re:4D by Tomfrh · · Score: 1

      Calling it 4D is pompous.

      We all know that 3D models can change over time.

  28. import into game by nomaan · · Score: 0

    take these maps, and put them in a driving game. would love to drive around my city virtually.. and then get stuck in grid lock traffic in the morning ..

  29. Fuzzy Logic by or+another+similar+t · · Score: 0
    This is actually rather interesting with shades of matrix. I imagine software like this will help greatly when it comes time to colonize the moon. By then we should (hopefully) have precise and comprehensive data about the environment in terms of the moons physical construction as well as radiation and space debris data. Just feed the data into the program and have a future version of this software design a habitat system almost as well (if not better) than humans could design. That could cut a decade off such an endeavor. I imagine the designs would need to be corrected here and there -- but the possibilities are fantastic.

    Now imagine sending a fleet of probes to Mars consisting of an array of satellites and ground based robots that determine and design everything necessary for perminent human habitation. Imagine taking the initiative and sending such fleets throughout the solar system to all sorts of places we will want a foothold decades before mounting such complex missions. Such a system could red flag all sorts of problems with environments that would have otherwise caused a manned crew to turn around and go home. One step further: Imagine sending (even later in time) more advanced fleets that could study a place and contruct a human habitation with robots and materials before humans even left Earth to head where ever. Even further: now imagine sending such fleets to other star systems centuries before humans. The environment could assesed. Suitable structures built and pressurized with atmosphere. Everything could then be maintained by yet another group of robots for centuries or even millennia with every aspect of the greater system under the direction of planning software. Hell they could mine endless reserves of materials and chemicals that humans would want upon arrival. Alot of this would likely require advanced nanotech.

    I am sure it can be taken to even greater extremes.

    -I have a science fiction novella to write!

    BTW - I have been visiting slashdot everyday since it opened in what, 96 or 97? As of this post I have only now bothered to create an account! So FIRST POST in a sense I guess.

  30. woah by bobo+the+hobo · · Score: 1

    it's not every day you see posts on slashdot that have giant detailed 3d models of two blocks from your house...

  31. If you... by dhazard · · Score: 1

    If you dont squint your left or right eye and really really look at it you can kinda see how it resembles... Dali's The Persistence Of Memory painting.

  32. More information on 3D scene generation by Anonymous Coward · · Score: 0

    See content acquisition section here.

  33. Game Maps? by BrianRaker · · Score: 1

    How easy would it be to take this modeling infomation and to import it into one of our favorite games, such as CounterStrike or CS:Source?

    --
    As I walk through the valley of death I fear no one, for I am the meanest sonova bitch in the valley!
    1. Re:Game Maps? by Anonymous Coward · · Score: 0

      Simple. You learn the file formats, and you write a converter in your favourite language. And yes, I do mean you.

      One assumes they're using an easy-to-parse point description format, and that the textures are saved in something convenient. The game map formats are well-known or, in other cases, can be converted to from well-known formats, so it should just be data-juggling. Of course, that assumes that the game engine can happily render the metric butt-load of data that these maps use, otherwise you'll have to come up with a smoothing algorithm to ditch unnecessary vertices.