X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2FGrid.hs;h=ca66437a6bb13b73d591b68d1b16d3ead8d60c89;hb=3f7331f579118687cd73b977ce6aa7d401f88a09;hp=d31ffabdf2aa122cadacf0cc9d85513f4989033a;hpb=aed1b3cc557b67aca7d8b3259f44715078db94ae;p=spline3.git diff --git a/src/Grid.hs b/src/Grid.hs index d31ffab..ca66437 100644 --- a/src/Grid.hs +++ b/src/Grid.hs @@ -10,40 +10,38 @@ module Grid ( ) where -import Data.Array (Array, array, (!)) import qualified Data.Array.Repa as R -import Test.HUnit +import Test.HUnit (Assertion, assertEqual) import Test.Framework (Test, testGroup) import Test.Framework.Providers.HUnit (testCase) import Test.Framework.Providers.QuickCheck2 (testProperty) -import Test.QuickCheck (Arbitrary(..), Gen, Positive(..), choose) - -import Assertions -import Comparisons +import Test.QuickCheck ((==>), + Arbitrary(..), + Gen, + Positive(..), + Property, + choose) +import Assertions (assertAlmostEqual, assertClose, assertTrue) +import Comparisons ((~=)) import Cube (Cube(Cube), find_containing_tetrahedron, tetrahedra, tetrahedron) -import Examples -import FunctionValues +import Examples (trilinear, trilinear9x9x9, zeros, naturals_1d) +import FunctionValues (make_values, value_at) import Point (Point) -import PolynomialArray (PolynomialArray) -import ScaleFactor -import Tetrahedron (Tetrahedron, c, number, polynomial, v0, v1, v2, v3) -import ThreeDimensional +import ScaleFactor (ScaleFactor) +import Tetrahedron (Tetrahedron, c, polynomial, v0, v1, v2, v3) +import ThreeDimensional (ThreeDimensional(..)) import Values (Values3D, dims, empty3d, zoom_shape) -type CubeGrid = Array (Int,Int,Int) Cube - - -- | Our problem is defined on a Grid. The grid size is given by the -- positive number h. The function values are the values of the -- function at the grid points, which are distance h from one -- another in each direction (x,y,z). data Grid = Grid { h :: Double, -- MUST BE GREATER THAN ZERO! - function_values :: Values3D, - cube_grid :: CubeGrid } + function_values :: Values3D } deriving (Eq, Show) @@ -59,28 +57,8 @@ instance Arbitrary Grid where make_grid :: Double -> Values3D -> Grid make_grid grid_size values | grid_size <= 0 = error "grid size must be positive" - | otherwise = Grid grid_size values (cubes grid_size values) - - --- | Returns a three-dimensional array of cubes centered on the grid --- points (h*i, h*j, h*k) with the appropriate 'FunctionValues'. -cubes :: Double -> Values3D -> CubeGrid -cubes delta fvs - = array (lbounds, ubounds) - [ ((i,j,k), cube_ijk) - | i <- [0..xmax], - j <- [0..ymax], - k <- [0..zmax], - let tet_vol = (1/24)*(delta^(3::Int)), - let cube_ijk = - Cube delta i j k (make_values fvs i j k) tet_vol] - where - xmax = xsize - 1 - ymax = ysize - 1 - zmax = zsize - 1 - lbounds = (0, 0, 0) - ubounds = (xmax, ymax, zmax) - (xsize, ysize, zsize) = dims fvs + | otherwise = Grid grid_size values + -- | Takes a grid and a position as an argument and returns the cube @@ -94,10 +72,13 @@ cube_at g i j k | j >= ysize = error "j >= ysize in cube_at" | k < 0 = error "k < 0 in cube_at" | k >= zsize = error "k >= zsize in cube_at" - | otherwise = (cube_grid g) ! (i,j,k) + | otherwise = Cube delta i j k fvs' tet_vol where fvs = function_values g (xsize, ysize, zsize) = dims fvs + fvs' = make_values fvs i j k + delta = h g + tet_vol = (1/24)*(delta^(3::Int)) -- The first cube along any axis covers (-h/2, h/2). The second -- covers (h/2, 3h/2). The third, (3h/2, 5h/2), and so on. @@ -132,39 +113,35 @@ find_containing_cube g p = k = calculate_containing_cube_coordinate g z -{-# INLINE zoom_lookup #-} -zoom_lookup :: Grid -> PolynomialArray -> ScaleFactor -> a -> (R.DIM3 -> Double) -zoom_lookup g polynomials scale_factor _ = - zoom_result g polynomials scale_factor +zoom_lookup :: Values3D -> ScaleFactor -> a -> (R.DIM3 -> Double) +zoom_lookup v3d scale_factor _ = + zoom_result v3d scale_factor -{-# INLINE zoom_result #-} -zoom_result :: Grid -> PolynomialArray -> ScaleFactor -> R.DIM3 -> Double -zoom_result g polynomials (sfx, sfy, sfz) (R.Z R.:. m R.:. n R.:. o) = - (polynomials ! (i, j, k, (number t))) p +zoom_result :: Values3D -> ScaleFactor -> R.DIM3 -> Double +zoom_result v3d (sfx, sfy, sfz) (R.Z R.:. m R.:. n R.:. o) = + f p where + g = make_grid 1 v3d offset = (h g)/2 m' = (fromIntegral m) / (fromIntegral sfx) - offset n' = (fromIntegral n) / (fromIntegral sfy) - offset o' = (fromIntegral o) / (fromIntegral sfz) - offset p = (m', n', o') :: Point cube = find_containing_cube g p - -- Figure out i,j,k without importing those functions. - Cube _ i j k _ _ = cube t = find_containing_tetrahedron cube p + f = polynomial t + - -zoom :: Grid -> PolynomialArray -> ScaleFactor -> Values3D -zoom g polynomials scale_factor +zoom :: Values3D -> ScaleFactor -> Values3D +zoom v3d scale_factor | xsize == 0 || ysize == 0 || zsize == 0 = empty3d | otherwise = - R.force $ R.traverse arr transExtent (zoom_lookup g polynomials scale_factor) + R.force $ R.unsafeTraverse v3d transExtent f where - arr = function_values g - (xsize, ysize, zsize) = dims arr + (xsize, ysize, zsize) = dims v3d transExtent = zoom_shape scale_factor - - + f = zoom_lookup v3d scale_factor -- | Check all coefficients of tetrahedron0 belonging to the cube @@ -314,6 +291,7 @@ test_trilinear_reproduced = | i <- [0..2], j <- [0..2], k <- [0..2], + c0 <- cs, t <- tetrahedra c0, let p = polynomial t, let i' = fromIntegral i, @@ -321,7 +299,7 @@ test_trilinear_reproduced = let k' = fromIntegral k] where g = make_grid 1 trilinear - c0 = cube_at g 1 1 1 + cs = [ cube_at g ci cj ck | ci <- [0..2], cj <- [0..2], ck <- [0..2] ] test_zeros_reproduced :: Assertion @@ -333,12 +311,13 @@ test_zeros_reproduced = k <- [0..2], let i' = fromIntegral i, let j' = fromIntegral j, - let k' = fromIntegral k] + let k' = fromIntegral k, + c0 <- cs, + t0 <- tetrahedra c0, + let p = polynomial t0 ] where g = make_grid 1 zeros - c0 = cube_at g 1 1 1 - t0 = tetrahedron c0 0 - p = polynomial t0 + cs = [ cube_at g ci cj ck | ci <- [0..2], cj <- [0..2], ck <- [0..2] ] -- | Make sure we can reproduce a 9x9x9 trilinear from the 3x3x3 one. @@ -365,18 +344,18 @@ test_trilinear9x9x9_reproduced = -- -- Example from before the fix: -- --- > b0 (tetrahedron c 15) p --- -3.4694469519536365e-18 +-- b1 (tetrahedron c 20) (0, 17.5, 0.5) +-- -0.0 -- test_tetrahedra_collision_sensitivity :: Assertion test_tetrahedra_collision_sensitivity = assertTrue "tetrahedron collision tests isn't too sensitive" $ - contains_point t15 p + contains_point t20 p where g = make_grid 1 naturals_1d - cube = cube_at g 0 17 1 - p = (0, 16.75, 0.5) :: Point - t15 = tetrahedron cube 15 + cube = cube_at g 0 18 0 + p = (0, 17.5, 0.5) :: Point + t20 = tetrahedron cube 20 prop_cube_indices_never_go_out_of_bounds :: Grid -> Gen Bool @@ -407,21 +386,127 @@ prop_cube_indices_never_go_out_of_bounds g = idx_z <= zsize - 1 +-- | Given in Sorokina and Zeilfelder, p. 80, (2.9). Note that the +-- third and fourth indices of c-t10 have been switched. This is +-- because we store the triangles oriented such that their volume is +-- positive. If T and T-tilde share \ and v0,v0-tilde point +-- in opposite directions, one of them has to have negative volume! +prop_c0120_identity :: Grid -> Property +prop_c0120_identity g = + and [xsize >= 3, ysize >= 3, zsize >= 3] ==> + c t0 0 1 2 0 ~= (c t0 1 0 2 0 + c t10 1 0 0 2) / 2 + where + fvs = function_values g + (xsize, ysize, zsize) = dims fvs + cube0 = cube_at g 1 1 1 + cube1 = cube_at g 0 1 1 + t0 = tetrahedron cube0 0 -- These two tetrahedra share a face. + t10 = tetrahedron cube1 10 + + +-- | Given in Sorokina and Zeilfelder, p. 80, (2.9). See +-- 'prop_c0120_identity'. +prop_c0111_identity :: Grid -> Property +prop_c0111_identity g = + and [xsize >= 3, ysize >= 3, zsize >= 3] ==> + c t0 0 1 1 1 ~= (c t0 1 0 1 1 + c t10 1 0 1 1) / 2 + where + fvs = function_values g + (xsize, ysize, zsize) = dims fvs + cube0 = cube_at g 1 1 1 + cube1 = cube_at g 0 1 1 + t0 = tetrahedron cube0 0 -- These two tetrahedra share a face. + t10 = tetrahedron cube1 10 + + +-- | Given in Sorokina and Zeilfelder, p. 80, (2.9). See +-- 'prop_c0120_identity'. +prop_c0201_identity :: Grid -> Property +prop_c0201_identity g = + and [xsize >= 3, ysize >= 3, zsize >= 3] ==> + c t0 0 2 0 1 ~= (c t0 1 1 0 1 + c t10 1 1 1 0) / 2 + where + fvs = function_values g + (xsize, ysize, zsize) = dims fvs + cube0 = cube_at g 1 1 1 + cube1 = cube_at g 0 1 1 + t0 = tetrahedron cube0 0 -- These two tetrahedra share a face. + t10 = tetrahedron cube1 10 + + +-- | Given in Sorokina and Zeilfelder, p. 80, (2.9). See +-- 'prop_c0120_identity'. +prop_c0102_identity :: Grid -> Property +prop_c0102_identity g = + and [xsize >= 3, ysize >= 3, zsize >= 3] ==> + c t0 0 1 0 2 ~= (c t0 1 0 0 2 + c t10 1 0 2 0) / 2 + where + fvs = function_values g + (xsize, ysize, zsize) = dims fvs + cube0 = cube_at g 1 1 1 + cube1 = cube_at g 0 1 1 + t0 = tetrahedron cube0 0 -- These two tetrahedra share a face. + t10 = tetrahedron cube1 10 + + +-- | Given in Sorokina and Zeilfelder, p. 80, (2.9). See +-- 'prop_c0120_identity'. +prop_c0210_identity :: Grid -> Property +prop_c0210_identity g = + and [xsize >= 3, ysize >= 3, zsize >= 3] ==> + c t0 0 2 1 0 ~= (c t0 1 1 1 0 + c t10 1 1 0 1) / 2 + where + fvs = function_values g + (xsize, ysize, zsize) = dims fvs + cube0 = cube_at g 1 1 1 + cube1 = cube_at g 0 1 1 + t0 = tetrahedron cube0 0 -- These two tetrahedra share a face. + t10 = tetrahedron cube1 10 + + +-- | Given in Sorokina and Zeilfelder, p. 80, (2.9). See +-- 'prop_c0120_identity'. +prop_c0300_identity :: Grid -> Property +prop_c0300_identity g = + and [xsize >= 3, ysize >= 3, zsize >= 3] ==> + c t0 0 3 0 0 ~= (c t0 1 2 0 0 + c t10 1 2 0 0) / 2 + where + fvs = function_values g + (xsize, ysize, zsize) = dims fvs + cube0 = cube_at g 1 1 1 + cube1 = cube_at g 0 1 1 + t0 = tetrahedron cube0 0 -- These two tetrahedra share a face. + t10 = tetrahedron cube1 10 + + +-- | All of the properties from Section (2.9), p. 80. These require a +-- grid since they refer to two adjacent cubes. +p80_29_properties :: Test.Framework.Test +p80_29_properties = + testGroup "p. 80, Section (2.9) Properties" [ + testProperty "c0120 identity" prop_c0120_identity, + testProperty "c0111 identity" prop_c0111_identity, + testProperty "c0201 identity" prop_c0201_identity, + testProperty "c0102 identity" prop_c0102_identity, + testProperty "c0210 identity" prop_c0210_identity, + testProperty "c0300 identity" prop_c0300_identity ] + grid_tests :: Test.Framework.Test grid_tests = testGroup "Grid Tests" [ trilinear_c0_t0_tests, + p80_29_properties, testCase "tetrahedra collision test isn't too sensitive" - test_tetrahedra_collision_sensitivity, - testCase "trilinear reproduced" test_trilinear_reproduced, - testCase "zeros reproduced" test_zeros_reproduced ] + test_tetrahedra_collision_sensitivity, + testProperty "cube indices within bounds" + prop_cube_indices_never_go_out_of_bounds ] -- Do the slow tests last so we can stop paying attention. slow_tests :: Test.Framework.Test slow_tests = testGroup "Slow Tests" [ - testProperty "cube indices within bounds" - prop_cube_indices_never_go_out_of_bounds, - testCase "trilinear9x9x9 reproduced" test_trilinear9x9x9_reproduced ] + testCase "trilinear reproduced" test_trilinear_reproduced, + testCase "trilinear9x9x9 reproduced" test_trilinear9x9x9_reproduced, + testCase "zeros reproduced" test_zeros_reproduced ]