Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 14 Next capture
2021 2022 2023
2 captures
13 Jun 22 - 14 Jun 22
sparklines
Close Help
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
6
Question by CaptainChristian · May 01, 2013 at 12:30 PM · c#easyefficient

C# - Simple Voronoi/Delaunay Diagrams For Starters

Hi,

I would like to use voronoi and delaunay diagrams for the generation of different road network types. So far, I haven't found a package offering both adapted for unity. I know there are a couple of huge packages containing all sorts of algorithms, there are smaller ones that don't yield the desired results or simply don't work in unity and some that are only used for terrain manipulation. However I need one I can feed with a list of points or something similar, which then outputs a list of edges and vertices I can connect easily.

Is there a small package for starters I can use right off the bat or with little modification?

Comment
Add comment · Show 6
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image Fattie · May 01, 2013 at 02:25 PM 1
Share

trying typing "Delaunay" in to the search field here for many leads

http://answers.unity3d.com/questions/307544/mesh-from-vertices-polygon-from-spline.html

avatar image CaptainChristian · May 03, 2013 at 09:31 AM 2
Share

I would if the answer was actually helpful. It is not like I haven't used the search field, but that the search query in no case returned something I could use. Therefore I am still searching for a working algorithm or one that can be easily modified.

It doesn't need to be all fancy and contain a hundred other algorithms I could use at some point in development. Only a working voronoi and delaunay diagram generation algorithm is required to fit my needs. But this algorithm needs to be spot on.

Bottom line: I am still doing research on this matter.

avatar image Fattie · May 03, 2013 at 09:34 AM 0
Share

if you click on the link in the comment, someone has provided full code for the desired or very close algorithm. hope it helps. here is the link again

http://answers.unity3d.com/questions/307544/mesh-from-vertices-polygon-from-spline.html

avatar image OP_toss · Dec 13, 2013 at 11:46 PM 1
Share

This is old but for anyone else looking, here's the Fortune Voronoi Graph algorithm implemented in C#

http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

With a little fenangling, I was able to convert this to a Unity-friendly version and build a mesh from it :D

avatar image CaptainChristian · Dec 14, 2013 at 10:14 AM 0
Share

Do you $$anonymous$$d sharing your code with us?

Show more comments

2 Replies

· Add your reply
  • Sort: 
avatar image
10
Best Answer

Answer by jceipek · Jun 08, 2014 at 11:28 PM

This is really old now but is still unanswered (I had the same problem as OP_toss when I tried using the C# implementation here).

I just finished porting one of the best AS3 implementations of Fortune's algorithm to C# for Unity. You can get it here: https://github.com/jceipek/Unity-delaunay (MIT licensed).

It's probably not perfect, but it doesn't seem to suffer from the same verts at infinity problems that seem to exist in every other version I tried: Example

Comment
Add comment · Show 7 · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image Keshire · Jun 19, 2014 at 08:55 PM 1
Share

Seems like a few people were wanting to write up a new delaunay implementation at the same time. Frit wrote one up too a week or two ago. I was writing one up too.

https://github.com/PouletFrit/csDelaunay

I've gotten almost all of AmitP's graphing rewritten. http://tinyurl.com/q5s6ub8

I'd rather create a mesh out of this data ins$$anonymous$$d of just drawing screen lines or texture lines. But I'm not sure how to go about that. Creating a mesh out of the delaunay triangles should be trivial. But how do you represent the voronoi polygons?

avatar image CaptainChristian · Jun 24, 2014 at 12:05 PM 0
Share

Thank you for your effort in this matter. I really appreciate it!

avatar image jceipek · Jun 24, 2014 at 02:10 PM 0
Share

$$anonymous$$eshire, I'm pretty sure my port lets you get the verts of each polygon. From there, you can delaunay triangulate each polygon. If you need a continuous mesh of all polygons, just merge overlapping points. Sorry I can't be more help right now - answering from my phone because I can't get online.

avatar image greel · Aug 29, 2014 at 04:14 PM 0
Share

Hey jceipek,

is there a way to generate a list of nodes that have a reference to their respective neighbors with your library?

avatar image UniDro · Jan 28, 2015 at 02:10 PM 0
Share

as3delaunay works. well sometimes. I got Unity freeze in 20% cases. 30% more cases I got:

/** Something has gone badly wrong */ Debug.LogError("$$anonymous$$ajor error: was trying to close the loop of an outer Cell, but couldn't find a restart point");

also is there a way to fill corners too. because this implementation seems to cut all the corners. I mean points [0,0], [0,height], [width,0] and [width,height]. here's how it looks http://pix.academ.org/img/2015/01/29/3eedbc33f1e3f49675b25479667f427e.png

meshes http://pix.academ.org/img/2015/01/28/640x480_8585791640386f9297265e1ee05fb225.png

jceipek, in other words - if I connect vertices, and create meshes from them, corners will never be inside.

Show more comments
avatar image
1

Answer by Fattie · Aug 07, 2017 at 10:29 PM

For 2017...

I had a look around, and really

https://github.com/jceipek/Unity-delaunay

seems to be the best one out there, still ! Thanks, jceipek !

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this Question

Answers Answers and Comments

15 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Multiple Cars not working 1 Answer

Distribute terrain in zones 3 Answers

Emit particles for all clients 1 Answer

Renderer on object disabled after level reload 1 Answer

Initialising List array for use in a custom Editor 1 Answer


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges