Sign in to follow this  
vracicot

Voroni Diagram, need help [SOLVED]

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this