From: Jean Privat Date: Tue, 15 Sep 2015 19:18:44 +0000 (-0400) Subject: Merge: lib: intro the matrix package X-Git-Tag: v0.7.8~19 X-Git-Url: http://nitlanguage.org?hp=19b8d731a129e7e2295760d04d12ce0b79d818eb Merge: lib: intro the matrix package This PR intro `Matrix` to represent a matrix of floats. The main module offers only general services and the `projection` module adds services useful for 3D manipulations. The package is oriented towards matrices of floats and was designed alongside Gamnit. As such, is a bit specialized and may not be appropriate for all usage of matrices (such as integer matrices). So if you prefer, I can move these back to Gamnit. But since this module does not have any dependencies and `Matrix` can be useful for a wide array of context, I chose to leave it in lib. Pull-Request: #1719 Reviewed-by: Jean Privat --- diff --git a/lib/matrix/matrix.nit b/lib/matrix/matrix.nit new file mode 100644 index 0000000..73131ca --- /dev/null +++ b/lib/matrix/matrix.nit @@ -0,0 +1,295 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Services for matrices of `Float` values +module matrix + +# A rectangular array of `Float` +# +# Require: `width > 0 and height > 0` +class Matrix + super Cloneable + + # Number of columns + var width: Int + + # Number of rows + var height: Int + + # Items of this matrix, rows by rows + private var items: Array[Float] is lazy do + return new Array[Float].filled_with(0.0, width*height) + end + + # Create a matrix from nested sequences + # + # Require: all rows are of the same length + # + # ~~~ + # var matrix = new Matrix.from([[1.0, 2.0], + # [3.0, 4.0]]) + # assert matrix.to_s == """ + # 1.0 2.0 + # 3.0 4.0""" + # ~~~ + init from(items: SequenceRead[SequenceRead[Float]]) + do + if items.is_empty then + init(0, 0) + return + end + + init(items.first.length, items.length) + + for j in height.times do assert items[j].length == width + + for j in height.times do + for i in width.times do + self[j, i] = items[j][i] + end + end + end + + # Get each row of this matrix in nested arrays + # + # ~~~ + # var items = [[1.0, 2.0], + # [3.0, 4.0]] + # var matrix = new Matrix.from(items) + # assert matrix.to_a == items + # ~~~ + fun to_a: Array[Array[Float]] + do + var a = new Array[Array[Float]] + for j in height.times do + var row = new Array[Float] + for i in width.times do + row.add self[j, i] + end + a.add row + end + return a + end + + # Create a matrix from an `Array[Float]` composed of rows after rows + # + # Require: `width > 0 and height > 0` + # Require: `array.length >= width*height` + # + # ~~~ + # var matrix = new Matrix.from_array(2, 2, [1.0, 2.0, + # 3.0, 4.0]) + # assert matrix.to_s == """ + # 1.0 2.0 + # 3.0 4.0""" + # ~~~ + init from_array(width, height: Int, array: SequenceRead[Float]) + do + assert width > 0 + assert height > 0 + assert array.length >= width*height + + init(width, height) + + for i in height.times do + for j in width.times do + self[j, i] = array[i + j*width] + end + end + end + + # Create an identity matrix + # + # Require: `size >= 0` + # + # ~~~ + # var i = new Matrix.identity(3) + # assert i.to_s == """ + # 1.0 0.0 0.0 + # 0.0 1.0 0.0 + # 0.0 0.0 1.0""" + # ~~~ + new identity(size: Int) + do + assert size >= 0 + + var matrix = new Matrix(size, size) + for i in size.times do + for j in size.times do + matrix[j, i] = if i == j then 1.0 else 0.0 + end + end + return matrix + end + + # Create a new clone of this matrix + redef fun clone do return new Matrix.from_array(width, height, items.clone) + + # Get the value at column `y` and row `x` + # + # Require: `x >= 0 and x <= width and y >= 0 and y <= height` + # + # ~~~ + # var matrix = new Matrix.from([[0.0, 0.1], + # [1.0, 1.1]]) + # + # assert matrix[0, 0] == 0.0 + # assert matrix[0, 1] == 0.1 + # assert matrix[1, 0] == 1.0 + # assert matrix[1, 1] == 1.1 + # ~~~ + fun [](y, x: Int): Float + do + assert x >= 0 and x < width + assert y >= 0 and y < height + + return items[x + y*width] + end + + # Set the `value` at row `y` and column `x` + # + # Require: `x >= 0 and x <= width and y >= 0 and y <= height` + # + # ~~~ + # var matrix = new Matrix.identity(2) + # + # matrix[0, 0] = 0.0 + # matrix[0, 1] = 0.1 + # matrix[1, 0] = 1.0 + # matrix[1, 1] = 1.1 + # + # assert matrix.to_s == """ + # 0.0 0.1 + # 1.0 1.1""" + # ~~~ + fun []=(y, x: Int, value: Float) + do + assert x >= 0 and x < width + assert y >= 0 and y < height + + items[x + y*width] = value + end + + # Matrix product (×) + # + # Require: `self.width == other.height` + # + # ~~~ + # var m = new Matrix.from([[3.0, 4.0], + # [5.0, 6.0]]) + # var i = new Matrix.identity(2) + # + # assert m * i == m + # assert (m * m).to_s == """ + # 29.0 36.0 + # 45.0 56.0""" + # + # var a = new Matrix.from([[1.0, 2.0, 3.0], + # [4.0, 5.0, 6.0]]) + # var b = new Matrix.from([[1.0], + # [2.0], + # [3.0]]) + # var c = a * b + # assert c.to_s == """ + # 14.0 + # 32.0""" + # ~~~ + fun *(other: Matrix): Matrix + do + assert self.width == other.height + + var out = new Matrix(other.width, self.height) + for j in self.height.times do + for i in other.width.times do + var sum = items.first.zero + for k in self.width.times do sum += self[j, k] * other[k, i] + out[j, i] = sum + end + end + return out + end + + # Get the transpose of this matrix + # + # ~~~ + # var matrix = new Matrix.from([[1.0, 2.0, 3.0], + # [4.0, 5.0, 6.0]]) + # assert matrix.transposed.to_a == [[1.0, 4.0], + # [2.0, 5.0], + # [3.0, 6.0]] + # + # var i = new Matrix.identity(3) + # assert i.transposed == i + # ~~~ + fun transposed: Matrix + do + var out = new Matrix(height, width) + for k, v in self do out[k.x, k.y] = v + return out + end + + # Iterate over the values in this matrix + fun iterator: MapIterator[MatrixCoordinate, Float] do return new MatrixIndexIterator(self) + + redef fun to_s + do + var lines = new Array[String] + for y in height.times do + lines.add items.subarray(y*width, width).join(" ") + end + return lines.join("\n") + end + + redef fun ==(other) do return other isa Matrix and other.items == self.items + redef fun hash do return items.hash +end + +private class MatrixIndexIterator + super MapIterator[MatrixCoordinate, Float] + + var matrix: Matrix + + redef var key = new MatrixCoordinate(0, 0) + + redef fun is_ok do return key.y < matrix.height + + redef fun item + do + assert is_ok + return matrix[key.y, key.x] + end + + redef fun next + do + assert is_ok + var key = key + if key.x == matrix.width - 1 then + key.x = 0 + key.y += 1 + else + key.x += 1 + end + end +end + +# Position key when iterating over the values of a matrix +class MatrixCoordinate + # Index of the current column + var x: Int + + # Index of the current row + var y: Int + + redef fun to_s do return "({x},{y})" +end diff --git a/lib/matrix/package.ini b/lib/matrix/package.ini new file mode 100644 index 0000000..4bd9013 --- /dev/null +++ b/lib/matrix/package.ini @@ -0,0 +1,11 @@ +[package] +name=matrix +tags=lib +maintainer=Alexis Laferrière +license=Apache-2.0 +[upstream] +browse=https://github.com/nitlang/nit/tree/master/lib/matrix/ +git=https://github.com/nitlang/nit.git +git.directory=lib/matrix/ +homepage=http://nitlanguage.org +issues=https://github.com/nitlang/nit/issues diff --git a/lib/matrix/projection.nit b/lib/matrix/projection.nit new file mode 100644 index 0000000..908761a --- /dev/null +++ b/lib/matrix/projection.nit @@ -0,0 +1,153 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Services on `Matrix` to transform and project 3D coordinates +module projection + +intrude import matrix + +redef class Matrix + + # Create an orthogonal projection matrix + # + # `left, right, bottom, top, near, far` defines the world clip planes. + new orthogonal(left, right, bottom, top, near, far: Float) + do + var dx = right - left + var dy = top - bottom + var dz = far - near + + assert dx != 0.0 and dy != 0.0 and dz != 0.0 + + var mat = new Matrix.identity(4) + mat[0, 0] = 2.0 / dx + mat[3, 0] = -(right + left) / dx + mat[1, 1] = 2.0 / dy + mat[3, 1] = -(top + bottom) / dy + mat[2, 2] = 2.0 / dz + mat[3, 2] = -(near + far) / dz + return mat + end + + # Create a perspective transformation matrix + # + # Using the given vertical `field_of_view_y` in radians, the `aspect_ratio` + # and the `near`/`far` world distances. + new perspective(field_of_view_y, aspect_ratio, near, far: Float) + do + var frustum_height = (field_of_view_y/2.0).tan * near + var frustum_width = frustum_height * aspect_ratio + + return new Matrix.frustum(-frustum_width, frustum_width, + -frustum_height, frustum_height, + near, far) + end + + # Create a frustum transformation matrix + # + # `left, right, bottom, top, near, far` defines the world clip planes. + new frustum(left, right, bottom, top, near, far: Float) + do + var dx = right - left + var dy = top - bottom + var dz = far - near + + assert near > 0.0 + assert far > 0.0 + assert dx > 0.0 + assert dy > 0.0 + assert dz > 0.0 + + var mat = new Matrix(4, 4) + + mat[0, 0] = 2.0 * near / dx + mat[0, 1] = 0.0 + mat[0, 2] = 0.0 + mat[0, 3] = 0.0 + + mat[1, 0] = 0.0 + mat[1, 1] = 2.0 * near / dy + mat[1, 2] = 0.0 + mat[1, 3] = 0.0 + + mat[2, 0] = (right + left) / dx + mat[2, 1] = (top + bottom) / dy + mat[2, 2] = -(near + far) / dz + mat[2, 3] = -1.0 + + mat[3, 0] = 0.0 + mat[3, 1] = 0.0 + mat[3, 2] = -2.0 * near * far / dz + mat[3, 3] = 0.0 + + return mat + end + + # Apply a translation by `x, y, z` to this matrix + fun translate(x, y, z: Float) + do + for i in [0..3] do + self[3, i] = self[3,i] + self[0, i] * x + self[1, i] * y + self[2, i] * z + end + end + + # Apply scaling on `x, y, z` to this matrix + fun scale(x, y, z: Float) + do + for i in [0..3] do + self[0, i] = self[0, i] * x + self[1, i] = self[1, i] * y + self[2, i] = self[2, i] * z + end + end + + # Create a rotation matrix by `angle` around the vector defined by `x, y, z` + new rotation(angle, x, y, z: Float) + do + var mat = new Matrix.identity(4) + + var mag = (x*x + y*y + z*z).sqrt + var sin = angle.sin + var cos = angle.cos + + if mag > 0.0 then + x = x / mag + y = y / mag + z = z / mag + + var inv_cos = 1.0 - cos + + mat[0, 0] = inv_cos*x*x + cos + mat[0, 1] = inv_cos*x*y - z*sin + mat[0, 2] = inv_cos*z*x + y*sin + + mat[1, 0] = inv_cos*x*y + z*sin + mat[1, 1] = inv_cos*y*y + cos + mat[1, 2] = inv_cos*y*z - x*sin + + mat[2, 0] = inv_cos*z*x - y*sin + mat[2, 1] = inv_cos*y*z + x*sin + mat[2, 2] = inv_cos*z*z + cos + end + return mat + end + + # Apply a rotation of `angle` radians around the vector `x, y, z` + fun rotate(angle, x, y, z: Float) + do + var rotation = new Matrix.rotation(angle, x, y, z) + var rotated = self * rotation + self.items = rotated.items + end +end