# Voroni Diagram, need help [SOLVED]

This topic is 4119 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all. My English is poor, so please bare with me :) I'm fooling around with landscape generation. So far so good, until I hit the Voroni diagram... For simplicity purpose, I generated a diagram without any equation and it seems to work properly (left image). However, the pseudocode I found here gives me a weird result (right image). On Left: distanceBuffer(x, y) = nearestDistance On right: distanceBuffer(x, y) = nearestDistance2 - nearestDistance But there is something that bothers me in this:
If nearestDistance < minimumDistance Then minimumDistance = nearestDistance
If nearestDistance > maximumDistance Then maximumDistance = nearestDistance

For x As Integer = 0 To tableSizeX
For y As Integer = 0 To tableSizeY
pixel(x, y) = (distanceBuffer(x, y) - minimumDistance) / (maximumDistance - minimumDistance)
Next
Next
If I'm using 2 distances, how come I'm only using minimum and maximum distance from distance #1? Here's the whole thing (yes, it's in VB.net, sorry, I'm a hobbyist and know no other languages for now... working on it):
Private Sub GenerateVoronoi()

' Generate Voronoi
If voronoiPoints = 0 Then

' No voroni cells to generate, just copy from perlin table
voronoiTable = perlinTable

Else

' Create at least 1 Voroni cell
Dim numPoints As Integer = voronoiPoints - 1

' Okay, this is going to be crazy fun...
Dim distanceBuffer(bufferSizeX, bufferSizeY) As Single
Dim positionX(numPoints) As Single
Dim positionY(numPoints) As Single
Dim minimumDistance As Single = Single.MaxValue
Dim maximumDistance As Single = 0

' Randomly fill the buffer
For i As Integer = 0 To numPoints
positionX(i) = Rnd() * bufferSizeX
positionY(i) = Rnd() * bufferSizeY
Next

' Get distance for every pixel
For x As Integer = 0 To bufferSizeX
For y As Integer = 0 To bufferSizeY

' Find nearest point
Dim nearestDistance As Single = Single.MaxValue
Dim nearestDistance2 As Single = Single.MaxValue
For i As Integer = 0 To numPoints

' Get distance for this point
Dim point1 As New MTV3D65.TV_2DVECTOR(x, y)
Dim point2 As New MTV3D65.TV_2DVECTOR(positionX(i), positionY(i))
Dim distance As Single = CoreGlobal.GetDistance2D(point1, point2)

' Set nearest distance
If distance < nearestDistance Then
nearestDistance = distance
ElseIf distance < nearestDistance2 Then
nearestDistance2 = distance
End If

Next

' Set distance table
Select Case voronoiGeneration
Case EnumVoronoi.Normal

' Set distance
distanceBuffer(x, y) = nearestDistance

' Check distance from nearest point
If nearestDistance < minimumDistance Then minimumDistance = nearestDistance
If nearestDistance > maximumDistance Then maximumDistance = nearestDistance

Case EnumVoronoi.Negative

' Set distance
distanceBuffer(x, y) = nearestDistance2 - nearestDistance

' Check distance from nearest point
If nearestDistance < minimumDistance Then minimumDistance = nearestDistance
If nearestDistance > maximumDistance Then maximumDistance = nearestDistance

Case EnumVoronoi.Multiplied

' Set distance
distanceBuffer(x, y) = nearestDistance * nearestDistance2

' Check distance from nearest point
If nearestDistance < minimumDistance Then minimumDistance = nearestDistance
If nearestDistance > maximumDistance Then maximumDistance = nearestDistance

End Select

Next
Next

' Set table
For x As Integer = 0 To bufferSizeX
For y As Integer = 0 To bufferSizeY
voronoiTable(x, y) = (distanceBuffer(x, y) - minimumDistance) / (maximumDistance - minimumDistance)
Next
Next

End If

End Sub
[Edited by - vracicot on July 5, 2008 8:34:52 PM]

##### Share on other sites
Quote:
 Original post by vracicotIf I'm using 2 distances, how come I'm only using minimum and maximum distance from distance #1?

The second distance measure (nearestDistance2) is only needed in the cases of both EnumVoronoi.Negative and EnumVoronoi.Multiplied and its contribution gets assigned to distanceBuffer(x, y) - See the big Select construct.

In point of fact, wouldn't that whole thing be better off like this:

' Set distance table
Select Case voronoiGeneration
Case EnumVoronoi.Normal
distanceBuffer(x, y) = nearestDistance

Case EnumVoronoi.Negative
distanceBuffer(x, y) = nearestDistance2 - nearestDistance

Case EnumVoronoi.Multiplied
distanceBuffer(x, y) = nearestDistance * nearestDistance2

End Select

' Check distance from nearest point
If nearestDistance < minimumDistance Then minimumDistance = nearestDistance
If nearestDistance > maximumDistance Then maximumDistance = nearestDistance

##### Share on other sites
Quote:
 Original post by dmatterIn point of fact, wouldn't that whole thing be better off like this:

er... yes, makes more sense!

but still doesn't fix my problem of trying to reproduce this:

but I'm only able to get this:

##### Share on other sites
Are you using the exact same data sets and same random number seed?

If even one thing is different then I wouldn't expect them to look the same. To me, yours looks like a lower resolution version - perhaps those jaggies indicate something is a miss though.

##### Share on other sites
Quote:
 Original post by dmatterAre you using the exact same data sets and same random number seed?

Well dmatter, that was a part of it! There was also a redundance in my loop which made some values go under 0... So silly of me. Thanks a bunch for pointing me out :)

And, of course, the code for people who will be looking at this thread in the future:

Private Sub GenerateVoronoi()

' Generate Voronoi
If voronoiPoints = 0 Then

' No cells to generate
voronoiTable = perlinTable

Else

' Create at least 1 cell
Dim numPoints As Integer = voronoiPoints - 1

' Okay, this is going to be crazy fun... :s
Dim distanceBuffer(tableSizeX, tableSizeY) As Single
Dim distanceFromCenter(numPoints) As Single
Dim positionX(numPoints) As Single
Dim positionY(numPoints) As Single
Dim minimumDistance As Single
Dim maximumDistance As Single
Dim minimumDistanceTotal As Single = Single.MaxValue
Dim maximumDistanceTotal As Single = Single.MinValue

' Set cells
For i As Integer = 0 To numPoints

' Randomly fill the cells
positionX(i) = Rnd() * tableSizeX
positionY(i) = Rnd() * tableSizeY

' Get distance from middle of table
Dim point1 As New MTV3D65.TV_2DVECTOR(positionX(i), positionY(i))
Dim point2 As New MTV3D65.TV_2DVECTOR(tableSizeX * 0.5!, tableSizeY * 0.5!)
distanceFromCenter(i) = CoreGlobal.GetDistance2D(point1, point2)

Next

' Get distance for every pixel
For x As Integer = 0 To tableSizeX
For y As Integer = 0 To tableSizeY

' Reset
minimumDistance = Single.MaxValue
maximumDistance = Single.MinValue

' Find nearest point
For i As Integer = 0 To numPoints

' Get distance for this point
Dim point1 As New MTV3D65.TV_2DVECTOR(x, y)
Dim point2 As New MTV3D65.TV_2DVECTOR(positionX(i), positionY(i))
Dim distance As Single = CoreGlobal.GetDistance2D(point1, point2)

' Set nearest distance
If distance < minimumDistance Then
maximumDistance = minimumDistance
minimumDistance = distance
ElseIf distance < maximumDistance Then
maximumDistance = distance
End If

Next

' Set distance table
Select Case voronoiGeneration
Case EnumVoronoi.Normal : distanceBuffer(x, y) = minimumDistance
Case EnumVoronoi.Negative : distanceBuffer(x, y) = maximumDistance - minimumDistance
Case EnumVoronoi.Multiplied : distanceBuffer(x, y) = maximumDistance * minimumDistance
End Select

' Check distance from nearest point
If distanceBuffer(x, y) < minimumDistanceTotal Then
minimumDistanceTotal = distanceBuffer(x, y)
ElseIf distanceBuffer(x, y) > maximumDistanceTotal Then
maximumDistanceTotal = distanceBuffer(x, y)
End If

Next
Next

' Reset
minimumDistance = Single.MaxValue
maximumDistance = Single.MinValue

' Check distance from center
For i As Integer = 0 To numPoints
If distanceFromCenter(i) < minimumDistance Then
minimumDistance = distanceFromCenter(i)
ElseIf distanceFromCenter(i) > maximumDistance Then
maximumDistance = distanceFromCenter(i)
End If
Next

' Set table
For x As Integer = 0 To tableSizeX
For y As Integer = 0 To tableSizeY
voronoiTable(x, y) = (distanceBuffer(x, y) - minimumDistanceTotal) / (maximumDistanceTotal - minimumDistanceTotal)
Next
Next

' Normalize 0..1
voronoiTable = NormalizeTable(voronoiTable)

' Check inverted colors
If voronoiInverted Then
For x As Integer = 0 To tableSizeX
For y As Integer = 0 To tableSizeY
voronoiTable(x, y) = 1 - voronoiTable(x, y)
Next
Next
End If

' Concatenate tables
For x As Integer = 0 To tableSizeX
For y As Integer = 0 To tableSizeY

' Lerp between the two tables
voronoiPerlinTable(x, y) = CoreGlobal.LinearLERP(perlinTable(x, y), _
voronoiTable(x, y), _
voronoiPresence)

Next
Next

End If

End Sub

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 30
• 9
• 16
• 22