001/** 002 * Copyright (c) 2008-2014 Ardor Labs, Inc. 003 * 004 * This file is part of Ardor3D. 005 * 006 * Ardor3D is free software: you can redistribute it and/or modify it 007 * under the terms of its license which may be found in the accompanying 008 * LICENSE file or at <http://www.ardor3d.com/LICENSE>. 009 */ 010 011package com.ardor3d.math.functions; 012 013import java.util.HashMap; 014import java.util.Map; 015 016import com.ardor3d.math.MathUtils; 017import com.ardor3d.math.Vector3; 018 019/** 020 * Function that produces a <a href="http://en.wikipedia.org/wiki/Voronoi_diagram">Voronoi graph</a> by placing a random 021 * point in every 1x1x1 unit cube in space and then finding the closest of these points at each eval location. 022 * 023 */ 024public class VoroniFunction3D implements Function3D { 025 026 private static final int SEARCH_RADIUS = 2; // can miss corner cases with only a radius of 1 027 028 private double _frequency = 1; 029 private boolean _useDistance = false; 030 private double _displacement = 1; 031 private int _seed = 0; 032 033 // A cache for cube values 034 private final Map<Key, Vector3> _points = new HashMap<>(); 035 036 /** 037 * Construct with default values. 038 */ 039 public VoroniFunction3D() { 040 } 041 042 /** 043 * Construct a new Voronoi graph function. 044 * 045 * @param frequency 046 * used to modulate input coordinates 047 * @param displacement 048 * use to modulate the contribution of the random points in each unit cube. 049 * @param useDistance 050 * if true, we will add the distance from the closest point to our output, giving us variation across the 051 * cell. 052 * @param seed 053 * the random seed value to give to our integer random function. 054 */ 055 public VoroniFunction3D(final double frequency, final double displacement, final boolean useDistance, 056 final int seed) { 057 _frequency = frequency; 058 _displacement = displacement; 059 _useDistance = useDistance; 060 _seed = seed; 061 } 062 063 @Override 064 public double eval(final double x, final double y, final double z) { 065 final double dx = x * _frequency, dy = y * _frequency, dz = z * _frequency; 066 067 // find which integer based unit cube we're in 068 final int ix = (int) MathUtils.floor(dx), iy = (int) MathUtils.floor(dy), iz = (int) MathUtils.floor(dz); 069 070 final Key k = new Key(); 071 final Vector3 minPoint = new Vector3(); 072 double nearestSq = Double.MAX_VALUE; 073 // Each cube has a point... Walk through all nearby cubes and see where our closest point lies. 074 for (int a = ix - VoroniFunction3D.SEARCH_RADIUS; a <= ix + VoroniFunction3D.SEARCH_RADIUS; a++) { 075 k.x = a; 076 for (int b = iy - VoroniFunction3D.SEARCH_RADIUS; b <= iy + VoroniFunction3D.SEARCH_RADIUS; b++) { 077 k.y = b; 078 for (int c = iz - VoroniFunction3D.SEARCH_RADIUS; c <= iz + VoroniFunction3D.SEARCH_RADIUS; c++) { 079 k.z = c; 080 Vector3 point = _points.get(k); 081 if (point == null) { 082 final double pX = a + point(a, b, c, _seed); 083 final double pY = b + point(a, b, c, _seed + 1); 084 final double pZ = c + point(a, b, c, _seed + 2); 085 point = new Vector3(pX, pY, pZ); 086 // cache for future lookups 087 _points.put(new Key(k), point); 088 } 089 final double xDist = point.getX() - dx; 090 final double yDist = point.getY() - dy; 091 final double zDist = point.getZ() - dz; 092 final double distSq = xDist * xDist + yDist * yDist + zDist * zDist; 093 094 // check distance 095 if (distSq < nearestSq) { 096 nearestSq = distSq; 097 minPoint.set(point); 098 } 099 } 100 } 101 } 102 103 double value; 104 if (_useDistance) { 105 // Determine the distance to the nearest point. 106 value = MathUtils.sqrt(nearestSq); 107 } else { 108 value = 0.0; 109 } 110 111 // Return the calculated distance + with the displacement value applied using the value of our cube. 112 return value + (_displacement * point(MathUtils.floor(minPoint.getXf()), MathUtils.floor(minPoint.getYf()), 113 MathUtils.floor(minPoint.getZf()), 0)); 114 } 115 116 /** 117 * Calc the "random" point in unit cube that starts at the given coords. 118 * 119 * @param unitX 120 * the x value of the unit cube 121 * @param unitY 122 * the y value of the unit cube 123 * @param unitZ 124 * the z value of the unit cube 125 * @param seed 126 * the seed of the random generator 127 * @return the "random" point in unit cube that starts at the given coords 128 */ 129 private double point(final int unitX, final int unitY, final int unitZ, final int seed) { 130 int n = (4241 * unitX + 7817 * unitY + 38261 * unitZ + 1979 * seed) & 0x7fffffff; 131 n = (n >> 13) ^ n; 132 return 1.0 - ((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff) / (double) 0x40000000; 133 } 134 135 public double getFrequency() { 136 return _frequency; 137 } 138 139 public void setFrequency(final double frequency) { 140 _frequency = frequency; 141 } 142 143 public boolean isUseDistance() { 144 return _useDistance; 145 } 146 147 public void setUseDistance(final boolean useDistance) { 148 _useDistance = useDistance; 149 } 150 151 public double getDisplacement() { 152 return _displacement; 153 } 154 155 public void setDisplacement(final double displacement) { 156 _displacement = displacement; 157 } 158 159 public int getSeed() { 160 return _seed; 161 } 162 163 public void setSeed(final int seed) { 164 _seed = seed; 165 } 166 167 private static class Key { 168 int x, y, z; 169 170 public Key() { 171 } 172 173 public Key(final Key k) { 174 x = k.x; 175 y = k.y; 176 z = k.z; 177 } 178 179 @Override 180 public int hashCode() { 181 int result = 17; 182 183 result += 31 * result + x; 184 result += 31 * result + y; 185 result += 31 * result + z; 186 187 return result; 188 } 189 190 @Override 191 public boolean equals(final Object o) { 192 if (this == o) { 193 return true; 194 } 195 if (!(o instanceof Key)) { 196 return false; 197 } 198 final Key comp = (Key) o; 199 return x == comp.x && y == comp.y && z == comp.z; 200 } 201 } 202}