Well I think i've just ironed out all the bugs in the view culling for this by now, so I thought maybe others would find it handy.
Basically you feed the class with a bunch of 2d points and then just call calculateHull(), which strips the points down to a minimal set (and puts them in the correct ordering, natch). It uses the Jarvis' march method (also known as the gif-wrapping method) which makes it good for use with lots of points but few actual edges in the bounding hull (like i'm using it for). But even with complex objects it still seems to be pretty quick.
I use this with Cohen-Sutherland view clipping for my world sectors (see the isVisible method) but thats a pretty simple extension of any point-in-view testing.
Enjoy
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
219
220
221
222
223
| package PrismEngine;
import org.lwjgl.*;
import org.lwjgl.opengl.*;
import org.lwjgl.input.*;
import java.io.*;
import java.nio.*;
import java.util.*;
import javax.swing.*;
import java.awt.event.*;
import OrangyTang.OpenGLToolkit.*;
public class ConvexHull2D
{
private ArrayList points;
private ArrayList testedPoints;
public ConvexHull2D()
{
points = new ArrayList();
testedPoints = new ArrayList();
}
public void addPoint(float x, float y)
{
Point2f newPoint = new Point2f(x, y);
points.add(newPoint);
}
public void clear()
{
points.clear();
}
public void calculateHull()
{
if (points.size() > 0)
{
ArrayList hullPoints = new ArrayList();
Point2f startPoint = (Point2f)points.get(0);
for (int i=0; i<points.size(); i++)
{
Point2f testPoint = (Point2f)points.get(i);
if (testPoint.y < startPoint.y)
{
startPoint = testPoint;
}
else if (testPoint.y == startPoint.y)
{
if (testPoint.x < startPoint.x)
startPoint = testPoint;
}
}
hullPoints.add(startPoint);
Point2f currentPoint = startPoint;
Point2f currentDirection = new Point2f(1.0f, 0.0f);
Point2f nextPoint = null;
int debug = 0;
while (true)
{
float currentAngle = 181f;
for (int i=0; i<points.size(); i++)
{
Point2f testPoint = (Point2f)points.get(i);
Point2f testDirection = new Point2f(testPoint);
testDirection.subtract(currentPoint);
testDirection.normalise();
float testAngle = currentDirection.angle(testDirection);
if (testAngle < currentAngle)
{
currentAngle = testAngle;
nextPoint = testPoint;
}
else if (testAngle == currentAngle)
{
if (currentPoint.distanceTo(testPoint) > currentPoint.distanceTo(nextPoint) )
nextPoint = testPoint;
}
}
if (nextPoint == hullPoints.get(0) || debug>1000)
break;
hullPoints.add(nextPoint);
currentDirection.set(nextPoint);
currentDirection.subtract(currentPoint);
currentPoint = nextPoint;
nextPoint = null;
debug++;
}
points = hullPoints;
} }
public boolean isVisible(Frustum viewFrustum)
{
return isVisible(viewFrustum, null);
}
public boolean isVisible(Frustum viewFrustum, Matrix4f transformMatrix)
{
if (transformMatrix != null)
{
testedPoints.clear();
Vector3f currentVector = new Vector3f();
for (int i=0; i<points.size(); i++)
{
Vector3f newVector = new Vector3f();
Point2f currentPoint = (Point2f)points.get(i);
currentVector.set(currentPoint.x, currentPoint.y, 0f);
newVector.transformPoint(transformMatrix, currentVector);
testedPoints.add(newVector);
}
}
int regionCodes = 0;
for (int i=0; i<points.size(); i++)
{
Point2f testPoint = (Point2f)points.get(i);
int currentCode = viewFrustum.findRegion(testPoint.x, testPoint.y, 0.0f, transformMatrix);
if (i == 0)
{
regionCodes = currentCode;
}
else
{
regionCodes &= currentCode;
}
}
if (regionCodes == 0)
{
return true;
}
else
{
return false;
}
}
public void render(GL gl, float height)
{
gl.begin(GL.LINE_LOOP);
{
for (int i=0; i<points.size(); i++)
{
Point2f current = (Point2f)points.get(i);
gl.vertex3f(current.x, current.y, height);
gl.vertex3f(current.x, current.y, 0.0f);
gl.vertex3f(current.x, current.y, height);
}
}
gl.end();
}
public void renderTested(GL gl)
{
gl.begin(GL.LINES);
{
for (int i=0; i<testedPoints.size(); i++)
{
Vector3f point = (Vector3f)testedPoints.get(i);
gl.vertex3f(point.x, point.y, point.z);
gl.vertex3f(point.x, point.y, point.z+1f);
}
}
gl.end();
}
} |
And the associated Point2f class I use:
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
| package PrismEngine;
import org.lwjgl.Math;
import OrangyTang.OpenGLToolkit.*;
public class Point2f
{
public float x;
public float y;
public Point2f()
{
this.x = 0f;
this.y = 0f;
}
public Point2f(float x, float y)
{
this.x = x;
this.y = y;
}
public Point2f(Point2f point)
{
this.x = point.x;
this.y = point.y;
}
public void set(Point2f point)
{
this.x = point.x;
this.y = point.y;
}
public void set(float x, float y)
{
this.x = x;
this.y = y;
}
public void subtract(Point2f point)
{
x -= point.x;
y -= point.y;
}
public void add(Point2f point)
{
x += point.x;
y += point.y;
}
public float dot(Point2f point)
{
return point.x*x + point.y*y;
}
public float length()
{
float dot = dot(this);
return Math.sqrt(dot);
}
public void normalise()
{
float length = length();
x = x/length;
y = y/length;
}
public float angle(Point2f point)
{
float angle = (this.dot(point))/(this.length()*point.length() );
return Math.acos(angle);
}
public float distanceTo(Point2f point)
{
float dx = point.x - x;
float dy = point.y - y;
return Math.sqrt(dx*dx + dy*dy);
}
} |
