-
Notifications
You must be signed in to change notification settings - Fork 0
/
Grid.java
218 lines (194 loc) · 7.35 KB
/
Grid.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
/**
* Copyright (C) 2009-2023 Hal Hildebrand. All rights reserved.
*
* This program is free software: you can redistribute it and/or modify it under
* the terms of the GNU Affero General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option) any
* later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
* details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package com.hellblazer.luciferase.lucien.grid;
import static com.hellblazer.luciferase.lucien.grid.V.A;
import static com.hellblazer.luciferase.lucien.grid.V.B;
import static com.hellblazer.luciferase.lucien.grid.V.C;
import static com.hellblazer.luciferase.lucien.grid.V.D;
import java.util.Collections;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
import javax.vecmath.Tuple3f;
import com.hellblazer.luciferase.common.IdentitySet;
/**
* A Delaunay tetrahedralization. This implementation is optimized for
* Luciferase, not for any other particular use. As such, it is based on floats,
* not doubles - although predicates are evaluated with doubles to ensure
* nothing horrible blows up. The extent of the "Big Tetrahedron" that defines
* the maximum extent of the universe for this tetrahedralization is thus {-32k,
* +32k}. This implementation also uses the "fast" version of the inSphere
* predicate, rather than the exact. The exact version is most expensive so made
* the call here. The result is that the generated mesh isn't precisely exact.
* As long as it doesn't blow up, for the purposes of kinetic point tracking,
* we're happy.
* <p>
* We are largely concerned with the topology of the tracked points, and their
* relative location, not the precise form of the mesh that encodes the
* topology. Because we throw the tetrahedra away on every rebuild, there's
* really little need for an index and so random walk is used. It is assumed
* that the vast majority, if not damn near entirety of operations concerning
* the Sentinel and its tracked components and topology will be operating with a
* vertex after the tetrahedralization has occurred. Consequently operations on
* Vertex and Tetrahedron are the defacto operation origination rather at the
* Sentinel level.
*
* @author <a href="mailto:hal.hildebrand@gmail.com">Hal Hildebrand</a>
*/
public class Grid implements Iterable<Vertex> {
/**
* Cannonical enumeration of the vertex ordinals
*/
public static final V[] VERTICES = { A, B, C, D };
/**
* A pre-built table of all the permutations of remaining faces to check in
* location.
*/
protected static final V[][][] ORDER = new V[][][] { { { B, C, D }, { C, B, D }, { C, D, B }, { B, D, C },
{ D, B, C }, { D, C, B } },
{ { A, C, D }, { C, A, D }, { C, D, A }, { A, D, C },
{ D, A, C }, { D, C, A } },
{ { B, A, D }, { A, B, D }, { A, D, B }, { B, D, A },
{ D, B, A }, { D, A, B } },
{ { B, C, A }, { C, B, A }, { C, A, B }, { B, A, C },
{ A, B, C }, { A, C, B } } };
/**
* Scale of the universe
*/
private static float SCALE = (float) Math.pow(2, 16);
public static Vertex[] getFourCorners() {
Vertex[] fourCorners = new Vertex[4];
fourCorners[0] = new Vertex(-1, 1, -1, SCALE);
fourCorners[1] = new Vertex(1, 1, 1, SCALE);
fourCorners[2] = new Vertex(1, -1, -1, SCALE);
fourCorners[3] = new Vertex(-1, -1, 1, SCALE);
return fourCorners;
}
/**
* Construct a Tetrahedron which is set up to encompass the numerical span
*
* @return
*/
public static Tetrahedron myOwnPrivateIdaho(Grid s) {
Vertex[] U = new Vertex[4];
int i = 0;
for (Vertex v : s.extent()) {
U[i++] = new Vertex(v);
}
return new Tetrahedron(U);
}
/**
* The four corners of the maximally bounding tetrahedron
*/
protected final Vertex[] fourCorners;
/**
* the Head of the vertices list
*/
protected Vertex head;
/**
* The number of points in this Grid
*/
protected int size = 0;
Grid(Vertex[] fourCorners) {
this.fourCorners = fourCorners;
}
Grid(Vertex[] fourCorners, Vertex head) {
this(fourCorners);
this.head = head;
}
/**
* Answer the four corners of the universe
*
* @return
*/
public Vertex[] extent() {
return fourCorners;
}
@Override
public Iterator<Vertex> iterator() {
return head != null ? head.iterator() : new Iterator<Vertex>() {
@Override
public boolean hasNext() {
return false;
}
@Override
public Vertex next() {
throw new NoSuchElementException();
}
};
}
/**
* Locate the tetrahedron which contains the query point via a stochastic walk
* through the delaunay triangulation. This location algorithm is a slight
* variation of the 3D jump and walk algorithm found in: "Fast randomized point
* location without preprocessing in two- and three-dimensional Delaunay
* triangulations", Computational Geometry 12 (1999) 63-83.
*
* @param query - the query point
* @param start - the starting tetrahedron
* @param random - the source of entropy for the randomized algo
* @return the Tetrahedron containing the query
*/
public Tetrahedron locate(Tuple3f query, Tetrahedron start, Random random) {
assert query != null;
return start.locate(query, random);
}
public int size() {
return size;
}
/**
* Answer the stream of all vertices in this tetrahedralization
*
* @return
*/
public Stream<Vertex> stream() {
return StreamSupport.stream(spliterator(), false);
}
/**
* Answer the set of all tetrahedrons in this tetrahedralization
*
* @return
*/
public Set<Tetrahedron> tetrahedrons() {
if (size == 0) {
return Collections.emptySet();
}
Set<Tetrahedron> all = new IdentitySet<>(size);
var stack = new Stack<Tetrahedron>();
stack.push(head.getAdjacent());
while (!stack.isEmpty()) {
var next = stack.pop();
if (all.add(next)) {
next.children(stack, all);
}
}
return all;
}
Vertex getHead() {
return head;
}
void setHead(Vertex head) {
this.head = head;
}
void setSize(int size) {
this.size = size;
}
}