calculateBoundaries

[Dane]

Before you begin reading the code below, let it be known that this is how the coordinate system works that the snippet is for:

+X = Right
-Y = Up
+Z = Forward

I’m not very familiar with geometry, but I’m confident in my understanding and research abilities to any information given to me.

	public void calculateBoundaries() {
		this.lengthXZ = 0;

		this.minBoundX = 999999;
		this.maxBoundX = -999999;

		this.maxBoundY = 0;
		this.minBoundY = 0;

		this.maxBoundZ = -99999;
		this.minBoundZ = 99999;

		for (int v = 0; v < this.vertexCount; v++) {
			int x = this.vertexX[v];
			int y = this.vertexY[v];
			int z = this.vertexZ[v];

			if (x < this.minBoundX) {
				this.minBoundX = x;
			}

			if (x > this.maxBoundX) {
				this.maxBoundX = x;
			}

			if (z < this.minBoundZ) {
				this.minBoundZ = z;
			}

			if (z > this.maxBoundZ) {
				this.maxBoundZ = z;
			}

			if (-y > this.maxBoundY) {
				this.maxBoundY = -y;
			}

			if (y > this.minBoundY) {
				this.minBoundY = y;
			}

			int lengthSquared = x * x + z * z;

			if (lengthSquared > this.lengthXZ) {
				this.lengthXZ = lengthSquared;
			}
		}

		this.lengthXZ = (int) Math.sqrt((double) this.lengthXZ);
		this.minDepth = (int) Math.sqrt((double) (this.lengthXZ * this.lengthXZ + this.maxBoundY * this.maxBoundY));
		this.maxDepth = this.minDepth + (int) Math.sqrt((double) (this.lengthXZ * this.lengthXZ + this.minBoundY * this.minBoundY));
	}

I’m trying to understand this more. lengthXZ is later multiplied by the sin(cameraPitch) and cos(cameraPitch) values for some algorithm to check if the model is within the screen. The most important part of this code to me is understanding the assignments to lengthXZ, minDepth, and maxDepth.

minDepth and maxDepth are used for sorting triangles by depth before being drawn.

I did some googling and found Elliptic Paraboloid which has the equation z = Ax^2 + By^2. I feel like it’s related, as the Y and Z coordinates in this application have been flipped, so they must apply in the same way for y = Ax^2 + Bz^2. http://www.math.umn.edu/~rogness/quadrics/ellparab.shtml

By the looks of it, these are the equations for the assignments: (minDepth using maxY and maxDepth using minY was not an oversight)

lengthXZ = sqrt( x^2 + z^2 )
minDepth = sqrt( x^2 + z^2 + maxY^2 )
maxDepth = sqrt( x^2 + z^2 + minY^2 )

Any input is appreciated. Thanks ;D ;D

[Jesse]

The elliptic paraboloid stuff is interesting, but I don’t think it’s directly relevant here (it’s just incidental to the fact that you’re performing length and squared length computations).

For what it’s worth, here:

maxDepth = sqrt( x^2 + z^2 + minY^2 )

You’ve omitted the inclusion of ‘minDepth’ in the original code, although that may be intentional.

The use of integers and the arbitrary boundary initializers (+/-99999) could also be problematic, depending on the circumstances, but maybe that’s done for a reason as well.

If you need more info, perhaps you could tell us a little more about the context, such as where the code is from, what space the computations take place in, and so on.

[Dane]

Hi, first I’d like to thank you for replying. ;D

@Jesse

The elliptic paraboloid stuff is interesting, but I don’t think it’s directly relevant here (it’s just incidental to the fact that you’re performing length and squared length computations).

I suspected it to be that way. Was fun to look at tho! :-X

@Jesse

maxDepth = sqrt( x^2 + z^2 + minY^2 )

You’ve omitted the inclusion of ‘minDepth’ in the original code, although that may be intentional.

I forgot it.

@Jesse

The use of integers and the arbitrary boundary initializers (+/-99999) could also be problematic, depending on the circumstances, but maybe that’s done for a reason as well.

That is done for a reason. For example, the minimum boundaries start as very high numbers because the vertices corresponding component should always be below it. The opposite goes for max boundaries.

@Jesse

If you need more info, perhaps you could tell us a little more about the context, such as where the code is from, what space the computations take place in, and so on.

The code is from an old RuneScape game client from 2004. calculateBoundaries is usually only called once after a model has been constructed. The fields it assigns are used in the drawing of the model. (The game has software based rendering)

I couldn’t identify any of the variables a thru j because of my lack in knowledge. Ignore the right bit shifts by 16, the numbers use fixed-point integers.

	public final void draw(int yaw, int sinCameraPitch, int cosCameraPitch, int sinCameraYaw, int cosCameraYaw, int sceneX, int sceneY, int sceneZ, int uid) {
		int a = ((sceneZ * cosCameraYaw) - (sceneX * sinCameraYaw)) >> 16;
		int b = ((sceneY * sinCameraPitch) + (a * cosCameraPitch)) >> 16;
		int c = (this.lengthXZ * cosCameraPitch) >> 16;
		int d = b + c;

		if (d <= Scene.NEAR_Z || b >= Scene.FAR_Z) {
			return;
		}

		int e = ((sceneZ * sinCameraYaw) + (sceneX * cosCameraYaw)) >> 16;
		int minScreenX = e - this.lengthXZ << 9; // screen width is 512. (1 << 9) = 512

		if (minScreenX / d >= Graphics2D.centerX) {
			return;
		}

		int maxScreenX = e + this.lengthXZ << 9; // screen width is 512. (1 << 9) = 512

		if (maxScreenX / d <= -Graphics2D.centerX) {
			return;
		}

		int f = ((sceneY * cosCameraPitch) - (a * sinCameraPitch)) >> 16;
		int g = (this.lengthXZ * sinCameraPitch) >> 16;

		int maxScreenY = (f + g) << 9; // screen width is 512. (1 << 9) = 512

		if (maxScreenY / d <= -Graphics2D.centerY) {
			return;
		}

		int h = g + (this.maxBoundY * cosCameraPitch >> 16);

		int minScreenY = (f - h) << 9; // screen width is 512. (1 << 9) = 512

		if (minScreenY / d >= Graphics2D.centerY) {
			return;
		}

		int i = c + (this.maxBoundY * sinCameraPitch >> 16);
		boolean project = false;

		if (b - i <= Scene.NEAR_Z) {
			project = true;
		}

		boolean hasInput = false;

		if (uid > 0 && allowInput) {
			int j = b - c;

			if (j <= Scene.NEAR_Z) {
				j = Scene.NEAR_Z;
			}

			if (e > 0) {
				minScreenX /= d;
				maxScreenX /= j;
			} else {
				maxScreenX /= d;
				minScreenX /= j;
			}

			if (f > 0) {
				minScreenY /= d;
				maxScreenY /= j;
			} else {
				maxScreenY /= d;
				minScreenY /= j;
			}

			int x = mouseX - Graphics3D.centerX;
			int y = mouseY - Graphics3D.centerY;

			if (x > minScreenX && x < maxScreenX && y > minScreenY && y < maxScreenY) {
				hasInput = true;
			}
		}

		int cx = Graphics3D.centerX;
		int cy = Graphics3D.centerY;

		int yawsin = 0;
		int yawcos = 0;

		if (yaw != 0) {
			yawsin = sin[yaw];
			yawcos = cos[yaw];
		}

		for (int v = 0; v < vertexCount; v++) {
			int x = vertexX[v];
			int y = vertexY[v];
			int z = vertexZ[v];

			if (yaw != 0) {
				int w = z * yawsin + x * yawcos >> 16;
				z = z * yawcos - x * yawsin >> 16;
				x = w;
			}

			x += sceneX;
			y += sceneY;
			z += sceneZ;

			int w = z * sinCameraYaw + x * cosCameraYaw >> 16;
			z = z * cosCameraYaw - x * sinCameraYaw >> 16;
			x = w;

			w = y * cosCameraPitch - z * sinCameraPitch >> 16;
			z = y * sinCameraPitch + z * cosCameraPitch >> 16;
			y = w;

			vertexDepth[v] = z - b;

			if (z >= Scene.NEAR_Z) {
				vertexScreenX[v] = cx + (x << 9) / z;
				vertexScreenY[v] = cy + (y << 9) / z;
			} else {
				vertexScreenX[v] = -5000;
				project = true;
			}

			if (project || texturedCount > 0) {
				projectSceneX[v] = x;
				projectSceneY[v] = y;
				projectSceneZ[v] = z;
			}
		}

		try {
			draw(uid, project, hasInput);
		} catch (Exception ignored) {

		}
	}

[Jesse]

[quote]For example, the minimum boundaries start as very high numbers because the vertices corresponding component should always be below it. The opposite goes for max boundaries.
[/quote]
Sure, I understand that. I was just pointing out that the value ‘99999’ is arbitrary. I’m sure it’s fine in the given context, but for modern code I’d use the actual numeric limit for the type instead. I understand this is old code though.

Beyond that, honestly this doesn’t look like the easiest code to unravel Assuming though that sceneX/Y/Z is the model position relative to the camera, maybe we can make sense of the first few lines.

The variable ‘a’ looks like it’s maybe the z value of the sceneX/Y/Z position after being rotated into view space to account for yaw. ‘b’ may be a similar correction for pitch. After this the maximum extent of the object (computed earlier) is factored in. The function then early-outs if the object is outside the projection range based on these values.

It looks like the code that follows does similar checks against the edges of the frustum and so on. It would take some time to make sense of it all, but that’s a start at least.

[Dane]

@Jesse

Sure, I understand that. I was just pointing out that the value ‘99999’ is arbitrary. I’m sure it’s fine in the given context, but for modern code I’d use the actual numeric limit for the type instead. I understand this is old code though.

The person who wrote this can be spotted riding a giant ant on his twitter. He wrote this specific function I would guess about 12 years ago.

@Jesse

Beyond that, honestly this doesn’t look like the easiest code to unravel Assuming though that sceneX/Y/Z is the model position relative to the camera, maybe we can make sense of the first few lines.

sceneX/Y/Z is indeed the location relative to the camera. So model position is just the delta of the positions? I’m not familiar with that lexicon.

sceneX = objectX - cameraX
sceneY = objectY - cameraY
sceneZ = objectZ - cameraZ

@Jesse

The variable ‘a’ looks like it’s maybe the z value of the sceneX/Y/Z position after being rotated into view space to account for yaw. ‘b’ may be a similar correction for pitch.

I find it difficult to read rotations, how were you able to suspect that it is the z value? I see both sceneZ, sceneX, and the cameraYaw is used. But I find it hard to picture in my head the point of negating x * sin(yaw) from z * cos(yaw). View space is just another word for screen coordinates right?

[quote=“Jesse,post:4,topic:54153”]
That is precisely the functionality. I also forgot to mention that the constants NEAR_Z and FAR_Z equal 50 and 3500 respectively. The function returns any time the model is completely off the screen, but may also sometimes disappear earlier due to what I assume are precision errors or limitations on angles. But let’s just ignore that information for now.

[Jesse]

By model position, I just mean the position of the model. So yeah, based on the code you posted, we can conclude that sceneX/Y/Z is the position of the model relative to the camera position.

[quote]I find it difficult to read rotations, how were you able to suspect that it is the z value?
[/quote]
In 2-d, a rotation matrix looks like this (column vectors - all examples off the top of my head, so no guarantees of correctness):

c = cos(angle)
s = sin(angle)

[ c -s ]
[ s  c ]

When rotating into camera space, we want to do the opposite of the camera rotation. For example, if the camera yaw is 45 degrees, we want to rotate by -45 degrees. To get the opposite rotation, you invert the matrix, like this:

[  c s ]
[ -s c ]

If you transform a vector by this matrix, you get:

[  c s ][x] = [  cx+sy ]
[ -s c ][y]   [ -sx+cy ]

Notice that if you substitute z for y, the second component of the result above is exactly how ‘a’ is computed: that is, a = cz-sx. In other words, it’s the result of transforming ‘z’ into view space.

[quote]View space is just another word for screen coordinates right?
[/quote]
Not quite. View space (sometimes called camera space) is the local space of the camera, conceptually speaking. ‘Screen space’ usually refers to a later stage in the pipeline.

[Dane]

I’ll just have to take some lessons on trigonometric functions. I never took trigonometry. :-X

I found some homework. http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/3d-basics-r673

Thanks for your time.