Based on the Mosaic (Fast) transformation in dmj3.uxf
with the kind permission of Damien M. Jones.
class MT_VoronoiTexture(common.ulb:TrapShape) {
;
; Based on the Mosaic (Fast) transformation in dmj3.uxf
; with the kind permission of Damien M. Jones.
; <p>
; Mark Townsend, June 2008
;
public:
func MT_VoronoiTexture(Generic pparent)
TrapShape.TrapShape(pparent)
fPattern = new @p_pattern(this)
;
; The general idea is to generate, one time, the
; entire list of center points for each tile. But,
; as the list is generated, it is stored in sorted
; order (by X coordinate). This will allow fast
; finding of nearest center point.
;
; We store centerpoints as an array of float instead
; of an array of complex so we don't have to keep
; cutting our tree node numbers in half.
;
int i = 0
int j = 0
int k = 0
int l = 0
int rightbranch = 0
float random1 = @seed1
float random2 = @seed2
complex p = 0
float range = 1.0 / 2147483648.0
tiletree[0] = -1; initialize tree (one leaf node)
tiletree[1] = -1
tileorder[0] = -1; initialize order (one double-endpoint)
tileorder[1] = -1
WHILE (i < @mostiles); still another tile to generate
;
; generate random data
;
random1 = (random1 * 1103515245 + 12345) % 2147483648.0
random2 = (random2 * 1103515245 + 12345) % 2147483648.0
p = ((random1 - 1073741824) + flip(random2 - 1073741824)) * range * @mosscale
tilecenters[j] = real(p)
tilecenters[j+1] = imag(p)
;
; find appropriate insertion point in the tree
;
IF (i > 0); have at least one item in the tree
k = 0; current node
WHILE (k >= 0); not at a leaf node
l = k; save current node
IF (real(p) < tilecenters[k] || \
(real(p) == tilecenters[k] && \
imag(p) < tilecenters[k+1])) ; less than current node
k = tiletree[k]; follow left branch
rightbranch = 0
ELSE; greater than current node
k = tiletree[k+1]; follow right branch
rightbranch = 1
ENDIF
ENDWHILE
;
; insert node into tree
;
tiletree[j] = -1; this node is a leaf node
tiletree[j+1] = -1
tiletree[l+rightbranch] = j; point this item to it
;
; insert node into sorted list
;
IF (rightbranch == 0); followed the left branch
IF (tileorder[l] >= 0); not the leftmost node so far
tileorder[tileorder[l]+1] = j; follow it and point it to the new node
ENDIF
tileorder[j] = tileorder[l]; point new node to nodes it's between
tileorder[j+1] = l
tileorder[l] = j; point previous tree node's left to this node
ELSE
IF (tileorder[l+1] >= 0); not the rightmost node so far
tileorder[tileorder[l+1]] = j; follow it and point it to the new node
ENDIF
tileorder[j] = l; point new node to nodes it's between
tileorder[j+1] = tileorder[l+1]
tileorder[l+1] = j; point previous tree node's right to this node
ENDIF
ENDIF
i = i + 1
j = j + 2
ENDWHILE
endfunc
float func Iterate(complex pz)
TrapShape.Iterate(pz)
;
; At this point, we already have a list of tile
; centers, with forward and backward order links,
; and a tree structure for finding the closest X
; value. For each pixel, find the tile center with
; the closest X value, then scan outwards until
; the tile centers under examination are too far
; (in the X direction) to beat what we already have.
;
int i2 = 0
int j2 = 0
int k2 = 0
int l2 = 0
int i3 = 0
int j3 = 0
BOOL scanleft = TRUE
BOOL scanright = TRUE
float d = 0
float closest1 = 1e20
float closest2 = 1e20
complex q = 0
complex point1 = 0
;
; First, find the closest X value.
;
k2 = 0; current node
WHILE (k2 >= 0); not at a leaf node
l2 = k2; save current node
IF (real(pz) < tilecenters[k2] || \
(real(pz) == tilecenters[k2] && \
imag(pz) < tilecenters[k2+1])) ; less than current node
k2 = tiletree[k2]; follow left branch
ELSE; greater than current node
k2 = tiletree[k2+1]; follow right branch
ENDIF
ENDWHILE
q = tilecenters[l2]+flip(tilecenters[l2+1]) ; tile center (as a complex)
closest1 = |q - pz|; save distance
point1 = q; save center
i2 = tileorder[l2]; left node to check
j2 = tileorder[l2+1]; right node to check
WHILE (scanleft || scanright); still scanning in at least one direction
IF (i2 < 0); hit the leftmost node
scanleft = FALSE; don't scan to the left
ENDIF
IF (scanleft); scanning to the left...
q = tilecenters[i2]+flip(tilecenters[i2+1]) ; tile center (as a complex)
d = sqr(real(q) - real(pz)); distance on X axis
IF (d > closest1); X distance alone is greater than our closest
scanleft = FALSE; so nothing else can possibly match
ELSE; well maybe it's closer
d = |q - pz|; distance to this tile
IF (d < closest1); new closest value!
closest1 = d; save distance
l2 = i2; save index
point1 = q; save center
ENDIF
i2 = tileorder[i2]; follow link to the left
ENDIF
ENDIF
IF (j2 < 0); hit the rightmost node
scanright = FALSE; don't scan to the right
ENDIF
IF (scanright); scanning to the right...
q = tilecenters[j2]+flip(tilecenters[j2+1]) ; tile center (as a complex)
d = sqr(real(q) - real(pz)); distance on X axis
IF (d > closest1); X distance alone is greater than our closest
scanright = FALSE; so nothing else can possibly match
ELSE; well maybe it's closer
d = |q - pz|; distance to this tile
IF (d < closest1); new closest value!
closest1 = d; save distance
l2 = j2; save index
point1 = q; save center
ENDIF
j2 = tileorder[j2+1]; follow link to the right
ENDIF
ENDIF
ENDWHILE
;
; We now have the location of the closest tile
; (point1) and the index of it (l2). If we're
; shading, we'll need the second-closest point,
; too. We scan left and right for it.
;
if @mode == "Mosaic"
; If we're in Mosaic mode iterate the pattern
; and exit here.
return fPattern.Iterate(point1)
endif
scanleft = TRUE
scanright = TRUE
i3 = tileorder[l2]; left node to check
j3 = tileorder[l2+1]; right node to check
WHILE (scanleft || scanright); still scanning in at least one direction
IF (i3 < 0); hit the leftmost node
scanleft = FALSE; don't scan to the left
ENDIF
IF (scanleft); scanning to the left...
q = tilecenters[i3]+flip(tilecenters[i3+1]) ; tile center (as a complex)
d = sqr(real(q) - real(pz)); distance on X axis
IF (d > closest2); X distance alone is greater than our closest
scanleft = FALSE; so nothing else can possibly match
ELSE; well maybe it's closer
d = |q - pz|; distance to this tile
IF (d < closest2); new closest value!
closest2 = d; save distance
ENDIF
i3 = tileorder[i3]; follow link to the left
ENDIF
ENDIF
IF (j3 < 0); hit the rightmost node
scanright = FALSE; don't scan to the right
ENDIF
IF (scanright); scanning to the right...
q = tilecenters[j3]+flip(tilecenters[j3+1]) ; tile center (as a complex)
d = sqr(real(q) - real(pz)); distance on X axis
IF (d > closest2); X distance alone is greater than our closest
scanright = FALSE; so nothing else can possibly match
ELSE; well maybe it's closer
d = |q - pz|; distance to this tile
IF (d < closest2); new closest value!
closest2 = d; save distance
ENDIF
j3 = tileorder[j3+1]; follow link to the right
ENDIF
ENDIF
ENDWHILE
closest1 = closest1^(1/@metric)
closest2 = closest2^(1/@metric)
float v = (closest2-closest1)
if @invert
return 1 - v
else
return v
endif
endfunc
private:
float tilecenters[@mostiles*2]; tile center points
int tiletree[@mostiles*2]; tile tree structure
int tileorder[@mostiles*2]; tile ordering
TrapShape fPattern
default:
title = "Voronoi Texture"
param mode
caption = "Mode"
enum = "Crackle" "Mosaic"
endparam
float param metric
caption = "Metric"
default = 2
visible = @mode == "Crackle"
endparam
param invert
caption = "Invert Value"
default = true
visible = @mode == "Crackle"
endparam
TrapShape param p_pattern
caption = "Pattern"
default = MT_PerlinNoiseTexture
visible = @mode == "Mosaic"
endparam
param mostiles
caption = "Number of Tiles"
default = 500
hint = "Sets the number of tiles. More tiles take \
longer to render."
endparam
param mosscale
caption = "Tile Density"
default = 5.0
hint = "Specifies the overall scale of the tiles. Smaller numbers \
will pack the tiles together more closely."
endparam
param seed1
caption = "Random Seed 1"
default = 51853571
hint = "This is the 'seed' for the random number generator for \
horizontal positions."
endparam
param seed2
caption = "Random Seed 2"
default = 8072177
hint = "This is the 'seed' for the random number generator for \
vertical positions."
endparam
}