3

What I'm trying to achieve:

Have a look at the following image from this paper

polygonisation

It's taking a road graph that is likely represented as segments/junctions, giving the lines width (call it what you like, sweeping, thickening) and then generating triangulated geometry for the roads.

Why I am asking this question:

This operation seems to be a fairly standard thing to do, but I can't any papers that directly deal with how to do it. Most GIS / procedural city generation papers focus on the generation of the road graph itself (e.g. creating interesting topologies), but the step involving taking the graph data and generating triangle meshes / UVs is always glossed over.

Here's a really nice video of complex road intersections with nice texturing and good-looking junctions. This is the level of quality I'd eventually like to achieve, but an incremental step towards this would be more than acceptable to me. Here's another video showing interactive road graph creation with a 3d visualisation.

There is a paper to go with that video but nothing is said about the triangulation strategy :(

I have my own approach to try that's too long-winded to detail here, but I'd much rather implement an existing solution / algorithm if one exists, as it'll be better than anything I cook up in the next few weeks.

Can anyone point me in the right direction?

Thanks.

Mark Simpson
  • 23,245
  • 2
  • 44
  • 44

1 Answers1

2

What you are seeking is the offset polygon for each of the regions bounded by roads. If all those regions are convex, this is an easy computation. If some are nonconvex, then it is more difficult, but still well-studied. You can find links at Wikipedia under straight skeleton, or here on StackOverflow under "An algorithm for inflating/deflating (offsetting, buffering) polygons."

Community
  • 1
  • 1
Joseph O'Rourke
  • 4,346
  • 16
  • 25
  • Thanks for the response. If you're saying that I should operate on the polygons bounded by the roads rather than the road lines, how would that work when road widths vary on a per-road basis, or there is not a complete 'island' to use? – Mark Simpson May 16 '12 at 16:01
  • It would not work well for variable road widths; you are right. For that you should concentrate on the roads instead. Grow each (like offsetting a polygonal chain), forming a polygon. Then union the raod polygons. – Joseph O'Rourke May 17 '12 at 00:18
  • I emailed Peter Wonka (http://peterwonka.net/) and he sent me an excellent paper. I will see if it's OK to share and then upload it somewhere, as it's the best resource I've seen, but it's not publicly available on the internet, as far as I can see. – Mark Simpson May 17 '12 at 14:10
  • @MarkSimpson Can you provide the name of the paper? Is it published? – kitsune Apr 21 '13 at 18:56
  • @kitsune It's called "Procedural construction of streets" by Marco Zimmermann. I've uploaded it here: http://www.sendspace.com/file/rby7ge – Mark Simpson Apr 21 '13 at 22:57
  • 1
    @MarkSimpson Thanks a lot! Funny incident: I actually studied CS at the ETHZ around the time that thesis was published :) – kitsune Apr 22 '13 at 13:50
  • @kitsune hopefully a few more papers will be added to http://vterrain.org/Culture/Roads/ -- I sent them in a while back, but the site author hasn't had the time to update the page yet. – Mark Simpson Apr 23 '13 at 14:39
  • 1
    @MarkSimpson The link with the paper doesn't work anymore. Could you please upload the paper again? – vvoovv Apr 14 '17 at 22:29
  • 1
    @woow: I've uploaded it to my own site now. http://defragdev.com/files/Zimmermann.Procedural_construction_of_streets.Semesterarbeit.V2.pdf – Mark Simpson Apr 16 '17 at 02:36