X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2FTetrahedron.hs;h=9f68364042e7563a3b10d23f01e72f2845ba74af;hb=4d695b8d0b05a02d562bdee3d2a1b98ce6a5e747;hp=ad164d2426dce01e85cbf3d22cab0d0a19380410;hpb=7d6bba8440f4327de6272e5c513959425f841c5d;p=spline3.git diff --git a/src/Tetrahedron.hs b/src/Tetrahedron.hs index ad164d2..9f68364 100644 --- a/src/Tetrahedron.hs +++ b/src/Tetrahedron.hs @@ -1,56 +1,109 @@ module Tetrahedron where +import qualified Data.Vector as V ( + singleton, + snoc, + sum + ) import Numeric.LinearAlgebra hiding (i, scale) +import Prelude hiding (LT) +import Test.QuickCheck (Arbitrary(..), Gen) -import Cube (back, - Cube(datum), - down, - front, - Gridded, - left, - right, - top) +import Cardinal +import Comparisons (nearly_ge) +import FunctionValues import Misc (factorial) import Point import RealFunction import ThreeDimensional -data Tetrahedron = Tetrahedron { cube :: Cube, - v0 :: Point, - v1 :: Point, - v2 :: Point, - v3 :: Point } - deriving (Eq) +data Tetrahedron = + Tetrahedron { fv :: FunctionValues, + v0 :: Point, + v1 :: Point, + v2 :: Point, + v3 :: Point, + precomputed_volume :: Double + } + deriving (Eq) -instance Show Tetrahedron where - show t = "Tetrahedron (Cube: " ++ (show (cube t)) ++ ") " ++ - "(v0: " ++ (show (v0 t)) ++ ") (v1: " ++ (show (v1 t)) ++ - ") (v2: " ++ (show (v2 t)) ++ ") (v3: " ++ (show (v3 t)) ++ - ")\n\n" -instance Gridded Tetrahedron where - back t = back (cube t) - down t = down (cube t) - front t = front (cube t) - left t = left (cube t) - right t = right (cube t) - top t = top (cube t) +instance Arbitrary Tetrahedron where + arbitrary = do + rnd_v0 <- arbitrary :: Gen Point + rnd_v1 <- arbitrary :: Gen Point + rnd_v2 <- arbitrary :: Gen Point + rnd_v3 <- arbitrary :: Gen Point + rnd_fv <- arbitrary :: Gen FunctionValues + + -- We can't assign an incorrect precomputed volume, + -- so we have to calculate the correct one here. + let t' = Tetrahedron rnd_fv rnd_v0 rnd_v1 rnd_v2 rnd_v3 0 + let vol = volume t' + return (Tetrahedron rnd_fv rnd_v0 rnd_v1 rnd_v2 rnd_v3 vol) + + +instance Show Tetrahedron where + show t = "Tetrahedron:\n" ++ + " fv: " ++ (show (fv t)) ++ "\n" ++ + " v0: " ++ (show (v0 t)) ++ "\n" ++ + " v1: " ++ (show (v1 t)) ++ "\n" ++ + " v2: " ++ (show (v2 t)) ++ "\n" ++ + " v3: " ++ (show (v3 t)) ++ "\n" instance ThreeDimensional Tetrahedron where - center t = ((v0 t) + (v1 t) + (v2 t) + (v3 t)) `scale` (1/4) + center (Tetrahedron _ v0' v1' v2' v3' _) = + (v0' + v1' + v2' + v3') `scale` (1/4) + contains_point t p = - (b0 t p) >= 0 && (b1 t p) >= 0 && (b2 t p) >= 0 && (b3 t p) >= 0 + b0_unscaled `nearly_ge` 0 && + b1_unscaled `nearly_ge` 0 && + b2_unscaled `nearly_ge` 0 && + b3_unscaled `nearly_ge` 0 + where + -- Drop the useless division and volume calculation that we + -- would do if we used the regular b0,..b3 functions. + b0_unscaled :: Double + b0_unscaled = volume inner_tetrahedron + where inner_tetrahedron = t { v0 = p } + + b1_unscaled :: Double + b1_unscaled = volume inner_tetrahedron + where inner_tetrahedron = t { v1 = p } + + b2_unscaled :: Double + b2_unscaled = volume inner_tetrahedron + where inner_tetrahedron = t { v2 = p } + + b3_unscaled :: Double + b3_unscaled = volume inner_tetrahedron + where inner_tetrahedron = t { v3 = p } polynomial :: Tetrahedron -> (RealFunction Point) polynomial t = - sum [ (c t i j k l) `cmult` (beta t i j k l) | i <- [0..3], - j <- [0..3], - k <- [0..3], - l <- [0..3], - i + j + k + l == 3] + V.sum $ V.singleton ((c t 0 0 0 3) `cmult` (beta t 0 0 0 3)) `V.snoc` + ((c t 0 0 1 2) `cmult` (beta t 0 0 1 2)) `V.snoc` + ((c t 0 0 2 1) `cmult` (beta t 0 0 2 1)) `V.snoc` + ((c t 0 0 3 0) `cmult` (beta t 0 0 3 0)) `V.snoc` + ((c t 0 1 0 2) `cmult` (beta t 0 1 0 2)) `V.snoc` + ((c t 0 1 1 1) `cmult` (beta t 0 1 1 1)) `V.snoc` + ((c t 0 1 2 0) `cmult` (beta t 0 1 2 0)) `V.snoc` + ((c t 0 2 0 1) `cmult` (beta t 0 2 0 1)) `V.snoc` + ((c t 0 2 1 0) `cmult` (beta t 0 2 1 0)) `V.snoc` + ((c t 0 3 0 0) `cmult` (beta t 0 3 0 0)) `V.snoc` + ((c t 1 0 0 2) `cmult` (beta t 1 0 0 2)) `V.snoc` + ((c t 1 0 1 1) `cmult` (beta t 1 0 1 1)) `V.snoc` + ((c t 1 0 2 0) `cmult` (beta t 1 0 2 0)) `V.snoc` + ((c t 1 1 0 1) `cmult` (beta t 1 1 0 1)) `V.snoc` + ((c t 1 1 1 0) `cmult` (beta t 1 1 1 0)) `V.snoc` + ((c t 1 2 0 0) `cmult` (beta t 1 2 0 0)) `V.snoc` + ((c t 2 0 0 1) `cmult` (beta t 2 0 0 1)) `V.snoc` + ((c t 2 0 1 0) `cmult` (beta t 2 0 1 0)) `V.snoc` + ((c t 2 1 0 0) `cmult` (beta t 2 1 0 0)) `V.snoc` + ((c t 3 0 0 0) `cmult` (beta t 3 0 0 0)) -- | Returns the domain point of t with indices i,j,k,l. @@ -87,422 +140,148 @@ beta t i j k l b3_term = (b3 t) `fexp` l +-- | The coefficient function. c t i j k l returns the coefficient +-- c_ijkl with respect to the tetrahedron t. The definition uses +-- pattern matching to mimic the definitions given in Sorokina and +-- Zeilfelder, pp. 84-86. If incorrect indices are supplied, the +-- function will simply error. c :: Tetrahedron -> Int -> Int -> Int -> Int -> Double -c x 0 0 3 0 = datum $ (1/8) * (i + f + l + t + lt + fl + ft + flt) - where - f = front x - flt = front (left (top x)) - fl = front (left x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - t = top x - - -c x 0 0 0 3 = datum $ (1/8) * (i + f + r + t + rt + fr + ft + frt) - where - f = front x - fr = front (right x) - frt = front (right (top x)) - ft = front (top x) - i = cube x - r = right x - rt = right (top x) - t = top x - - -c x 0 0 2 1 = datum $ (5/24)*(i + f + t + ft) + (1/24)*(l + fl + lt + flt) - where - f = front x - flt = front (left (top x)) - fl = front (left x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - t = top x - - -c x 0 0 1 2 = datum $ (5/24)*(i + f + t + ft) + (1/24)*(r + fr + rt + frt) - where - f = front x - frt = front (right (top x)) - fr = front (right x) - ft = front (top x) - i = cube x - r = right x - rt = right (top x) - t = top x - - -c x 0 1 2 0 = datum $ - (5/24)*(i + f) + - (1/8)*(l + t + fl + ft) + - (1/24)*(lt + flt) - where - f = front x - flt = front (left (top x)) - fl = front (left x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - t = top x - - -c x 0 1 0 2 = datum $ - (5/24)*(i + f) + - (1/8)*(r + t + fr + ft) + - (1/24)*(rt + frt) - where - f = front x - fr = front (right x) - frt = front (right (top x)) - ft = front (top x) - i = cube x - r = right x - rt = right (top x) - t = top x - - -c x 0 1 1 1 = datum $ - (13/48)*(i + f) + - (7/48)*(t + ft) + - (1/32)*(l + r + fl + fr) + - (1/96)*(lt + rt + flt + frt) - where - f = front x - flt = front (left (top x)) - fl = front (left x) - fr = front (right x) - frt = front (right (top x)) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - r = right x - rt = right (top x) - t = top x - - -c x 0 2 1 0 = datum $ - (13/48)*(i + f) + - (17/192)*(l + t + fl + ft) + - (1/96)*(lt + flt) + - (1/64)*(r + d + fr + fd) + - (1/192)*(rt + ld + frt + fld) - where - d = down x - f = front x - fd = front (down x) - fld = front (left (down x)) - flt = front (left (top x)) - fl = front (left x) - fr = front (right x) - frt = front (right (top x)) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rt = right (top x) - t = top x - - -c x 0 2 0 1 = datum $ - (13/48)*(i + f) + - (17/192)*(r + t + fr + ft) + - (1/96)*(rt + frt) + - (1/64)*(l + d + fl + fd) + - (1/192)*(rd + lt + flt + frd) - where - d = down x - f = front x - fd = front (down x) - flt = front (left (top x)) - fl = front (left x) - frd = front (right (down x)) - fr = front (right x) - frt = front (right (top x)) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - - -c x 0 3 0 0 = datum $ - (13/48)*(i + f) + - (5/96)*(l + r + t + d + fl + fr + ft + fd) + - (1/192)*(rt + rd + lt + ld + frt + frd + flt + fld) - where - d = down x - f = front x - fd = front (down x) - fld = front (left (down x)) - flt = front (left (top x)) - fl = front (left x) - frd = front (right (down x)) - fr = front (right x) - frt = front (right (top x)) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - -c x 1 0 2 0 = datum $ (1/4)*i + (1/6)*(f + l + t) + (1/12)*(lt + fl + ft) - where - f = front x - fl = front (left x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - t = top x - - -c x 1 0 0 2 = datum $ (1/4)*i + (1/6)*(f + r + t) + (1/12)*(rt + fr + ft) - where - f = front x - fr = front (right x) - ft = front (top x) - i = cube x - r = right x - rt = right (top x) - t = top x - - -c x 1 0 1 1 = datum $ - (1/3)*i + - (5/24)*(f + t) + - (1/12)*ft + - (1/24)*(l + r) + - (1/48)*(lt + rt + fl + fr) - where - f = front x - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - r = right x - rt = right (top x) - t = top x - - -c x 1 1 1 0 = datum $ - (1/3)*i + - (5/24)*f + - (1/8)*(l + t) + - (5/96)*(fl + ft) + - (1/48)*(d + r + lt) + - (1/96)*(fd + ld + rt + fr) - where - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rt = right (top x) - t = top x - - -c x 1 1 0 1 = datum $ - (1/3)*i + - (5/24)*f + - (1/8)*(r + t) + - (5/96)*(fr + ft) + - (1/48)*(d + l + rt) + - (1/96)*(fd + lt + rd + fl) - where - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - - - -c x 1 2 0 0 = datum $ - (1/3)*i + - (5/24)*f + - (7/96)*(l + r + t + d) + - (1/32)*(fl + fr + ft + fd) + - (1/96)*(rt + rd + lt + ld) - where - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - - -c x 2 0 1 0 = datum $ - (3/8)*i + - (7/48)*(f + t + l) + - (1/48)*(r + d + b + lt + fl + ft) + - (1/96)*(rt + bt + fr + fd + ld + bl) - where - b = back x - bl = back (left x) - bt = back (top x) - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rt = right (top x) - t = top x - - -c x 2 0 0 1 = datum $ - (3/8)*i + - (7/48)*(f + t + r) + - (1/48)*(l + d + b + rt + fr + ft) + - (1/96)*(lt + bt + fl + fd + rd + br) - where - b = back x - br = back (right x) - bt = back (top x) - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - - - -c x 2 1 0 0 = datum $ - (3/8)*i + - (1/12)*(t + r + l + d) + - (1/64)*(ft + fr + fl + fd) + - (7/48)*f + - (1/48)*b + - (1/96)*(rt + ld + lt + rd) + - (1/192)*(bt + br + bl + bd) - where - b = back x - bd = back (down x) - bl = back (left x) - br = back (right x) - bt = back (top x) - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - - -c x 3 0 0 0 = datum $ - (3/8)*i + - (1/12)*(t + f + l + r + d + b) + - (1/96)*(lt + fl + ft + rt + bt + fr) + - (1/96)*(fd + ld + bd + br + rd + bl) - where - b = back x - bd = back (down x) - bl = back (left x) - br = back (right x) - bt = back (top x) - d = down x - f = front x - fd = front (down x) - fl = front (left x) - fr = front (right x) - ft = front (top x) - i = cube x - l = left x - ld = left (down x) - lt = left (top x) - r = right x - rd = right (down x) - rt = right (top x) - t = top x - +c t 0 0 3 0 = eval (fv t) $ + (1/8) * (I + F + L + T + LT + FL + FT + FLT) + +c t 0 0 0 3 = eval (fv t) $ + (1/8) * (I + F + R + T + RT + FR + FT + FRT) + +c t 0 0 2 1 = eval (fv t) $ + (5/24)*(I + F + T + FT) + + (1/24)*(L + FL + LT + FLT) + +c t 0 0 1 2 = eval (fv t) $ + (5/24)*(I + F + T + FT) + + (1/24)*(R + FR + RT + FRT) + +c t 0 1 2 0 = eval (fv t) $ + (5/24)*(I + F) + + (1/8)*(L + T + FL + FT) + + (1/24)*(LT + FLT) + +c t 0 1 0 2 = eval (fv t) $ + (5/24)*(I + F) + + (1/8)*(R + T + FR + FT) + + (1/24)*(RT + FRT) + +c t 0 1 1 1 = eval (fv t) $ + (13/48)*(I + F) + + (7/48)*(T + FT) + + (1/32)*(L + R + FL + FR) + + (1/96)*(LT + RT + FLT + FRT) + +c t 0 2 1 0 = eval (fv t) $ + (13/48)*(I + F) + + (17/192)*(L + T + FL + FT) + + (1/96)*(LT + FLT) + + (1/64)*(R + D + FR + FD) + + (1/192)*(RT + LD + FRT + FLD) + +c t 0 2 0 1 = eval (fv t) $ + (13/48)*(I + F) + + (17/192)*(R + T + FR + FT) + + (1/96)*(RT + FRT) + + (1/64)*(L + D + FL + FD) + + (1/192)*(RD + LT + FLT + FRD) + +c t 0 3 0 0 = eval (fv t) $ + (13/48)*(I + F) + + (5/96)*(L + R + T + D + FL + FR + FT + FD) + + (1/192)*(RT + RD + LT + LD + FRT + FRD + FLT + FLD) + +c t 1 0 2 0 = eval (fv t) $ + (1/4)*I + + (1/6)*(F + L + T) + + (1/12)*(LT + FL + FT) + +c t 1 0 0 2 = eval (fv t) $ + (1/4)*I + + (1/6)*(F + R + T) + + (1/12)*(RT + FR + FT) + +c t 1 0 1 1 = eval (fv t) $ + (1/3)*I + + (5/24)*(F + T) + + (1/12)*FT + + (1/24)*(L + R) + + (1/48)*(LT + RT + FL + FR) + +c t 1 1 1 0 = eval (fv t) $ + (1/3)*I + + (5/24)*F + + (1/8)*(L + T) + + (5/96)*(FL + FT) + + (1/48)*(D + R + LT) + + (1/96)*(FD + LD + RT + FR) + +c t 1 1 0 1 = eval (fv t) $ + (1/3)*I + + (5/24)*F + + (1/8)*(R + T) + + (5/96)*(FR + FT) + + (1/48)*(D + L + RT) + + (1/96)*(FD + LT + RD + FL) + +c t 1 2 0 0 = eval (fv t) $ + (1/3)*I + + (5/24)*F + + (7/96)*(L + R + T + D) + + (1/32)*(FL + FR + FT + FD) + + (1/96)*(RT + RD + LT + LD) + +c t 2 0 1 0 = eval (fv t) $ + (3/8)*I + + (7/48)*(F + T + L) + + (1/48)*(R + D + B + LT + FL + FT) + + (1/96)*(RT + BT + FR + FD + LD + BL) + +c t 2 0 0 1 = eval (fv t) $ + (3/8)*I + + (7/48)*(F + T + R) + + (1/48)*(L + D + B + RT + FR + FT) + + (1/96)*(LT + BT + FL + FD + RD + BR) + +c t 2 1 0 0 = eval (fv t) $ + (3/8)*I + + (1/12)*(T + R + L + D) + + (1/64)*(FT + FR + FL + FD) + + (7/48)*F + + (1/48)*B + + (1/96)*(RT + LD + LT + RD) + + (1/192)*(BT + BR + BL + BD) + +c t 3 0 0 0 = eval (fv t) $ + (3/8)*I + + (1/12)*(T + F + L + R + D + B) + + (1/96)*(LT + FL + FT + RT + BT + FR) + + (1/96)*(FD + LD + BD + BR + RD + BL) c _ _ _ _ _ = error "coefficient index out of bounds" +-- | The matrix used in the tetrahedron volume calculation as given in +-- Lai & Schumaker, Definition 15.4, page 436. vol_matrix :: Tetrahedron -> Matrix Double -vol_matrix t = (4><4) $ +vol_matrix t = (4><4) [1, 1, 1, 1, x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 ] where - x1 = x_coord (v0 t) - x2 = x_coord (v1 t) - x3 = x_coord (v2 t) - x4 = x_coord (v3 t) - y1 = y_coord (v0 t) - y2 = y_coord (v1 t) - y3 = y_coord (v2 t) - y4 = y_coord (v3 t) - z1 = z_coord (v0 t) - z2 = z_coord (v1 t) - z3 = z_coord (v2 t) - z4 = z_coord (v3 t) - --- Computed using the formula from Lai & Schumaker, Definition 15.4, --- page 436. + (x1, y1, z1) = v0 t + (x2, y2, z2) = v1 t + (x3, y3, z3) = v2 t + (x4, y4, z4) = v3 t + +-- | Computed using the formula from Lai & Schumaker, Definition 15.4, +-- page 436. volume :: Tetrahedron -> Double volume t | (v0 t) == (v1 t) = 0 @@ -514,22 +293,29 @@ volume t | otherwise = (1/6)*(det (vol_matrix t)) +-- | The barycentric coordinates of a point with respect to v0. b0 :: Tetrahedron -> (RealFunction Point) -b0 t point = (volume inner_tetrahedron) / (volume t) +b0 t point = (volume inner_tetrahedron) / (precomputed_volume t) where inner_tetrahedron = t { v0 = point } + +-- | The barycentric coordinates of a point with respect to v1. b1 :: Tetrahedron -> (RealFunction Point) -b1 t point = (volume inner_tetrahedron) / (volume t) +b1 t point = (volume inner_tetrahedron) / (precomputed_volume t) where inner_tetrahedron = t { v1 = point } + +-- | The barycentric coordinates of a point with respect to v2. b2 :: Tetrahedron -> (RealFunction Point) -b2 t point = (volume inner_tetrahedron) / (volume t) +b2 t point = (volume inner_tetrahedron) / (precomputed_volume t) where inner_tetrahedron = t { v2 = point } + +-- | The barycentric coordinates of a point with respect to v3. b3 :: Tetrahedron -> (RealFunction Point) -b3 t point = (volume inner_tetrahedron) / (volume t) +b3 t point = (volume inner_tetrahedron) / (precomputed_volume t) where inner_tetrahedron = t { v3 = point }