Jump to content
  • Advertisement
Sign in to follow this  
vracicot

Voroni Diagram, need help [SOLVED]

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by vracicot
If 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 this post


Link to post
Share on other sites
Quote:
Original post by dmatter
In 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by dmatter
Are 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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!