diff options
author | Marc Sunet <jeannekamikaze@gmail.com> | 2012-08-28 18:25:27 +0200 |
---|---|---|
committer | Marc Sunet <jeannekamikaze@gmail.com> | 2012-08-28 18:25:27 +0200 |
commit | 8c6c0bbe54a179350f1ecd6d7c227245133ecc7d (patch) | |
tree | c29124f6d9841a63fd1642f6d14ccecf7c30fce7 | |
parent | e03885548a3062724e35d30317a0bfdbb66d5915 (diff) |
Translated collision and collision entities to 2D
-rw-r--r-- | Spear.cabal | 32 | ||||
-rw-r--r-- | Spear.lkshs | 12 | ||||
-rw-r--r-- | Spear/Collision/Collision.hs | 79 | ||||
-rw-r--r-- | Spear/Collision/Collisioner.hs | 52 | ||||
-rw-r--r-- | Spear/Math/AABB.hs | 12 | ||||
-rw-r--r-- | Spear/Math/Circle.hs | 33 | ||||
-rw-r--r-- | Spear/Math/Octree.hs | 284 | ||||
-rw-r--r-- | Spear/Math/QuadTree.hs | 248 | ||||
-rw-r--r-- | Spear/Math/Sphere.hs | 35 | ||||
-rw-r--r-- | Spear/Scene/Scene.hs | 4 |
10 files changed, 360 insertions, 431 deletions
diff --git a/Spear.cabal b/Spear.cabal index acad880..ffe11dc 100644 --- a/Spear.cabal +++ b/Spear.cabal | |||
@@ -6,7 +6,7 @@ license: BSD3 | |||
6 | license-file: LICENSE | 6 | license-file: LICENSE |
7 | maintainer: jeannekamikaze@gmail.com | 7 | maintainer: jeannekamikaze@gmail.com |
8 | homepage: http://spear.shellblade.net | 8 | homepage: http://spear.shellblade.net |
9 | synopsis: A 3D game framework. | 9 | synopsis: A 2.5D game framework. |
10 | category: Game | 10 | category: Game |
11 | author: Marc Sunet | 11 | author: Marc Sunet |
12 | data-dir: "" | 12 | data-dir: "" |
@@ -16,24 +16,24 @@ library | |||
16 | StateVar -any, base -any, bytestring -any, directory -any, | 16 | StateVar -any, base -any, bytestring -any, directory -any, |
17 | mtl -any, transformers -any, resourcet -any, parsec >=3.1.3, | 17 | mtl -any, transformers -any, resourcet -any, parsec >=3.1.3, |
18 | containers -any, vector -any, array -any | 18 | containers -any, vector -any, array -any |
19 | exposed-modules: Spear.Physics.Types Spear.App | 19 | exposed-modules: Spear.Math.QuadTree Spear.Physics.Types Spear.App |
20 | Spear.App.Application Spear.App.Input Spear.Assets.Image | 20 | Spear.App.Application Spear.App.Input Spear.Assets.Image |
21 | Spear.Assets.Model Spear.Collision Spear.Math.AABB | 21 | Spear.Assets.Model Spear.Collision Spear.Math.AABB |
22 | Spear.Collision.Collision Spear.Collision.Collisioner | 22 | Spear.Collision.Collision Spear.Collision.Collisioner |
23 | Spear.Math.Sphere Spear.Math.Triangle | 23 | Spear.Math.Circle Spear.Math.Triangle Spear.Collision.Types |
24 | Spear.Collision.Types Spear.Game Spear.GLSL Spear.GLSL.Buffer | 24 | Spear.Game Spear.GLSL Spear.GLSL.Buffer Spear.GLSL.Error |
25 | Spear.GLSL.Error Spear.GLSL.Management Spear.GLSL.Texture | 25 | Spear.GLSL.Management Spear.GLSL.Texture Spear.GLSL.Uniform |
26 | Spear.GLSL.Uniform Spear.GLSL.VAO Spear.Math.Camera | 26 | Spear.GLSL.VAO Spear.Math.Camera Spear.Math.Entity |
27 | Spear.Math.Entity Spear.Math.Matrix3 Spear.Math.Matrix4 | 27 | Spear.Math.Matrix3 Spear.Math.Matrix4 Spear.Math.MatrixUtils |
28 | Spear.Math.MatrixUtils Spear.Math.Octree Spear.Math.Plane | 28 | Spear.Math.Plane Spear.Math.Quaternion Spear.Math.Spatial |
29 | Spear.Math.Quaternion Spear.Math.Spatial Spear.Math.Vector3 | 29 | Spear.Math.Vector3 Spear.Math.Vector4 Spear.Physics |
30 | Spear.Math.Vector4 Spear.Physics Spear.Physics.Rigid | 30 | Spear.Physics.Rigid Spear.Render.AnimatedModel |
31 | Spear.Render.AnimatedModel Spear.Render.Material Spear.Render.Model | 31 | Spear.Render.Material Spear.Render.Model Spear.Render.Program |
32 | Spear.Render.Program Spear.Render.Renderable | 32 | Spear.Render.Renderable Spear.Render.StaticModel |
33 | Spear.Render.StaticModel Spear.Render.Texture Spear.Scene.Graph | 33 | Spear.Render.Texture Spear.Scene.Graph Spear.Scene.Light |
34 | Spear.Scene.Light Spear.Scene.Loader Spear.Scene.Scene | 34 | Spear.Scene.Loader Spear.Scene.Scene Spear.Scene.SceneResources |
35 | Spear.Scene.SceneResources Spear.Setup Spear.Sys.Timer | 35 | Spear.Setup Spear.Sys.Timer Spear.Sys.Store Spear.Sys.Store.ID |
36 | Spear.Sys.Store Spear.Sys.Store.ID Spear.Updatable Spear.Math.Vector2 | 36 | Spear.Updatable Spear.Math.Vector2 |
37 | exposed: True | 37 | exposed: True |
38 | buildable: True | 38 | buildable: True |
39 | build-tools: hsc2hs -any | 39 | build-tools: hsc2hs -any |
diff --git a/Spear.lkshs b/Spear.lkshs index 9aa6160..2663b79 100644 --- a/Spear.lkshs +++ b/Spear.lkshs | |||
@@ -1,18 +1,18 @@ | |||
1 | Version of session file format: | 1 | Version of session file format: |
2 | 1 | 2 | 1 |
3 | Time of storage: | 3 | Time of storage: |
4 | "Tue Aug 28 17:22:50 CEST 2012" | 4 | "Tue Aug 28 18:24:30 CEST 2012" |
5 | Layout: VerticalP (TerminalP {paneGroups = fromList [], paneTabs = Just TopP, currentPage = -1, detachedId = Nothing, detachedSize = Nothing}) (HorizontalP (TerminalP {paneGroups = fromList [("Browser",HorizontalP (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) (HorizontalP (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) 247) 202)], paneTabs = Just BottomP, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) 691) 954 | 5 | Layout: VerticalP (TerminalP {paneGroups = fromList [], paneTabs = Just TopP, currentPage = -1, detachedId = Nothing, detachedSize = Nothing}) (HorizontalP (TerminalP {paneGroups = fromList [("Browser",HorizontalP (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) (HorizontalP (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) 240) 199)], paneTabs = Just BottomP, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) (TerminalP {paneGroups = fromList [], paneTabs = Nothing, currentPage = 0, detachedId = Nothing, detachedSize = Nothing}) 696) 954 |
6 | Population: [(Just (ErrorsSt ErrorsState),[SplitP RightP,SplitP TopP]),(Just (FilesSt FilesState),[SplitP RightP,SplitP TopP]),(Just (InfoSt (InfoState (Just (Real (RealDescr {dscName' = "map", dscMbTypeStr' = Just "map ::\n (e -> AABB -> CollisionType) -> (e -> e) -> Octree e -> Octree e", dscMbModu' = Just (PM {pack = PackageIdentifier {pkgName = PackageName "Spear", pkgVersion = Version {versionBranch = [0,1], versionTags = []}}, modu = ModuleName ["Spear","Math","Octree"]}), dscMbLocation' = Just (Location {locationSLine = 185, locationSCol = 1, locationELine = 185, locationECol = 90}), dscMbComment' = Just " Applies the given function to the entities in the octree.\n Entities that break out of their cell are reallocated appropriately.", dscTypeHint' = VariableDescr, dscExported' = False}))))),[SplitP RightP,SplitP TopP,GroupP "Browser",SplitP BottomP,SplitP BottomP]),(Just (LogSt LogState),[SplitP RightP,SplitP BottomP]),(Just (ModulesSt (ModulesState 328 (PackageScope False,False) (Just (ModuleName ["Spear","Math","Octree"]),Just "map") (ExpanderState {packageExp = ([],[]), packageExpNoBlack = ([[0,4],[0,1],[0]],[]), packageDExp = ([],[]), packageDExpNoBlack = ([],[]), workspaceExp = ([],[]), workspaceExpNoBlack = ([],[]), workspaceDExp = ([],[]), workspaceDExpNoBlack = ([],[]), systemExp = ([],[]), systemExpNoBlack = ([],[])}))),[SplitP RightP,SplitP TopP,GroupP "Browser",SplitP BottomP,SplitP TopP]),(Just (WorkspaceSt WorkspaceState),[SplitP RightP,SplitP TopP,GroupP "Browser",SplitP TopP])] | 6 | Population: [(Just (ErrorsSt ErrorsState),[SplitP RightP,SplitP TopP]),(Just (FilesSt FilesState),[SplitP RightP,SplitP TopP]),(Just (InfoSt (InfoState Nothing)),[SplitP RightP,SplitP TopP,GroupP "Browser",SplitP BottomP,SplitP BottomP]),(Just (LogSt LogState),[SplitP RightP,SplitP BottomP]),(Just (ModulesSt (ModulesState 328 (PackageScope False,False) (Nothing,Nothing) (ExpanderState {packageExp = ([],[]), packageExpNoBlack = ([[0]],[]), packageDExp = ([],[]), packageDExpNoBlack = ([],[]), workspaceExp = ([],[]), workspaceExpNoBlack = ([],[]), workspaceDExp = ([],[]), workspaceDExpNoBlack = ([],[]), systemExp = ([],[]), systemExpNoBlack = ([],[])}))),[SplitP RightP,SplitP TopP,GroupP "Browser",SplitP BottomP,SplitP TopP]),(Just (WorkspaceSt WorkspaceState),[SplitP RightP,SplitP TopP,GroupP "Browser",SplitP TopP])] |
7 | Window size: (1820,939) | 7 | Window size: (1820,939) |
8 | Completion size: | 8 | Completion size: |
9 | (750,400) | 9 | (750,400) |
10 | Workspace: Just "/home/jeanne/programming/haskell/Spear/Spear.lkshw" | 10 | Workspace: Just "/home/jeanne/programming/haskell/Spear/Spear.lkshw" |
11 | Active pane: Just "Workspace" | 11 | Active pane: Just "Modules" |
12 | Toolbar visible: | 12 | Toolbar visible: |
13 | True | 13 | True |
14 | FindbarState: (False,FindState {entryStr = "asd", entryHist = ["idxs","asd","elemIndexa","elemtIn","splitAt","allocaBytes","copyArray","allocaArray","allocaa","putStrLn","assigned","Triangle"], replaceStr = "objects", replaceHist = [], caseSensitive = True, entireWord = False, wrapAround = False, regex = False, lineNr = 1}) | 14 | FindbarState: (False,FindState {entryStr = "asad", entryHist = ["asad","Octree","idxs","asd","elemIndexa","elemtIn","splitAt","allocaBytes","copyArray","allocaArray","allocaa","putStrLn"], replaceStr = "QuadTree", replaceHist = [], caseSensitive = True, entireWord = False, wrapAround = False, regex = False, lineNr = 1}) |
15 | Recently opened files: | 15 | Recently opened files: |
16 | ["/home/jeanne/programming/haskell/Spear/Spear/Collision/Types.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Triangle.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Sphere.hs","/home/jeanne/programming/haskell/Spear/Spear/Scene/Scene.hs","/home/jeanne/programming/haskell/Spear/Spear/Collision/Collisioner.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/AABB.hs","/home/jeanne/programming/haskell/Spear/demos/simple-scene/Game/GameObject/Factory.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Octree.hs","/home/jeanne/programming/haskell/Spear/Spear/Collision/Collision.hs","/home/jeanne/programming/haskell/Spear/Spear/Collision.hs","/home/jeanne/programming/haskell/Spear/Spear/Physics.hs","/home/jeanne/programming/haskell/Spear/Spear/Physics/World.hs"] | 16 | ["/home/jeanne/programming/haskell/Spear/Spear/Math/AABB.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Circle.hs","/home/jeanne/programming/haskell/Spear/Spear/Collision/Collision.hs","/home/jeanne/programming/haskell/Spear/Spear/Collision/Collisioner.hs","/home/jeanne/programming/haskell/Spear/Spear/Scene/Scene.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/QuadTree.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Sphere.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Triangle.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Spatial.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Quaternion.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Plane.hs","/home/jeanne/programming/haskell/Spear/Spear/Math/Octree.hs"] |
17 | Recently opened workspaces: | 17 | Recently opened workspaces: |
18 | ["/home/jeanne/programming/haskell/hagen/hagen.lkshw","/home/jeanne/programming/haskell/foo/foo.lkshw","/home/jeanne/programming/haskell/Spear/Spear.lkshw","/home/jeanne/programming/haskell/nexus/nexus.lkshw","/home/jeanne/leksah.lkshw"] \ No newline at end of file | 18 | ["/home/jeanne/programming/haskell/hagen/hagen.lkshw","/home/jeanne/programming/haskell/foo/foo.lkshw","/home/jeanne/programming/haskell/Spear/Spear.lkshw","/home/jeanne/programming/haskell/nexus/nexus.lkshw","/home/jeanne/leksah.lkshw"] \ No newline at end of file |
diff --git a/Spear/Collision/Collision.hs b/Spear/Collision/Collision.hs index 08f33b5..3a4c614 100644 --- a/Spear/Collision/Collision.hs +++ b/Spear/Collision/Collision.hs | |||
@@ -1,22 +1,21 @@ | |||
1 | module Spear.Collision.Collision | 1 | module Spear.Collision.Collision |
2 | ( | 2 | ( |
3 | Collisionable(..) | 3 | Collisionable(..) |
4 | , aabbFromSphere | 4 | , aabbFromCircle |
5 | ) | 5 | ) |
6 | where | 6 | where |
7 | 7 | ||
8 | 8 | ||
9 | import Spear.Collision.Types | 9 | import Spear.Collision.Types |
10 | import Spear.Math.AABB | 10 | import Spear.Math.AABB |
11 | import Spear.Math.Sphere | 11 | import Spear.Math.Circle |
12 | import Spear.Math.Plane | 12 | import Spear.Math.Plane |
13 | import Spear.Math.Vector3 | 13 | import Spear.Math.Vector2 |
14 | 14 | ||
15 | 15 | ||
16 | class Collisionable a where | 16 | class Collisionable a where |
17 | collideBox :: AABB -> a -> CollisionType | 17 | collideBox :: AABB -> a -> CollisionType |
18 | collideSphere :: Sphere -> a -> CollisionType | 18 | collideSphere :: Circle -> a -> CollisionType |
19 | collidePlane :: Plane -> a -> CollisionType | ||
20 | 19 | ||
21 | 20 | ||
22 | instance Collisionable AABB where | 21 | instance Collisionable AABB where |
@@ -30,35 +29,27 @@ instance Collisionable AABB where | |||
30 | | (x min1) > (x max2) = NoCollision | 29 | | (x min1) > (x max2) = NoCollision |
31 | | (y max1) < (y min2) = NoCollision | 30 | | (y max1) < (y min2) = NoCollision |
32 | | (y min1) > (y max2) = NoCollision | 31 | | (y min1) > (y max2) = NoCollision |
33 | | (z max1) < (z min2) = NoCollision | ||
34 | | (z min1) > (z max2) = NoCollision | ||
35 | | otherwise = Collision | 32 | | otherwise = Collision |
36 | 33 | ||
37 | collideSphere sphere@(Sphere c r) aabb@(AABB min max) | 34 | collideSphere sphere@(Circle c r) aabb@(AABB min max) |
38 | | test == FullyContains || test == FullyContainedBy = test | 35 | | test == FullyContains || test == FullyContainedBy = test |
39 | | normSq (c - boxC) > (l + r)^2 = NoCollision | 36 | | normSq (c - boxC) > (l + r)^2 = NoCollision |
40 | | otherwise = Collision | 37 | | otherwise = Collision |
41 | where | 38 | where |
42 | test = aabb `collideBox` aabbFromSphere sphere | 39 | test = aabb `collideBox` aabbFromCircle sphere |
43 | boxC = min + (max-min)/2 | 40 | boxC = min + (max-min)/2 |
44 | l = norm $ min + (vec3 (x boxC) (y min) (z min)) - min | 41 | l = norm $ min + (vec2 (x boxC) (y min)) - min |
45 | 42 | ||
46 | collidePlane pl aabb@(AABB {}) | ||
47 | | sameSide tests = NoCollision | ||
48 | | otherwise = Collision | ||
49 | where | ||
50 | tests = fmap (classify pl) $ aabbPoints aabb | ||
51 | sameSide (x:xs) = all (==x) xs | ||
52 | 43 | ||
53 | 44 | ||
54 | instance Collisionable Sphere where | 45 | instance Collisionable Circle where |
55 | 46 | ||
56 | collideBox box sphere = case collideSphere sphere box of | 47 | collideBox box sphere = case collideSphere sphere box of |
57 | FullyContains -> FullyContainedBy | 48 | FullyContains -> FullyContainedBy |
58 | FullyContainedBy -> FullyContains | 49 | FullyContainedBy -> FullyContains |
59 | x -> x | 50 | x -> x |
60 | 51 | ||
61 | collideSphere s1@(Sphere c1 r1) s2@(Sphere c2 r2) | 52 | collideSphere s1@(Circle c1 r1) s2@(Circle c2 r2) |
62 | | distance_centers <= sub_radii = if (r1 > r2) then FullyContains else FullyContainedBy | 53 | | distance_centers <= sub_radii = if (r1 > r2) then FullyContains else FullyContainedBy |
63 | | distance_centers <= sum_radii = Collision | 54 | | distance_centers <= sum_radii = Collision |
64 | | otherwise = NoCollision | 55 | | otherwise = NoCollision |
@@ -67,50 +58,24 @@ instance Collisionable Sphere where | |||
67 | sum_radii = (r1 + r2)^2 | 58 | sum_radii = (r1 + r2)^2 |
68 | sub_radii = (r1 - r2)^2 | 59 | sub_radii = (r1 - r2)^2 |
69 | 60 | ||
70 | collidePlane pl s = NoCollision | ||
71 | 61 | ||
72 | 62 | ||
73 | aabbPoints :: AABB -> [Vector3] | 63 | aabbPoints :: AABB -> [Vector2] |
74 | aabbPoints (AABB min max) = [p1,p2,p3,p4,p5,p6,p7,p8] | 64 | aabbPoints (AABB min max) = [p1,p2,p3,p4,p5,p6,p7,p8] |
75 | where | 65 | where |
76 | p1 = vec3 (x min) (y min) (z min) | 66 | p1 = vec2 (x min) (y min) |
77 | p2 = vec3 (x min) (y min) (z max) | 67 | p2 = vec2 (x min) (y min) |
78 | p3 = vec3 (x min) (y max) (z min) | 68 | p3 = vec2 (x min) (y max) |
79 | p4 = vec3 (x min) (y max) (z max) | 69 | p4 = vec2 (x min) (y max) |
80 | p5 = vec3 (x max) (y min) (z min) | 70 | p5 = vec2 (x max) (y min) |
81 | p6 = vec3 (x max) (y min) (z max) | 71 | p6 = vec2 (x max) (y min) |
82 | p7 = vec3 (x max) (y max) (z min) | 72 | p7 = vec2 (x max) (y max) |
83 | p8 = vec3 (x max) (y max) (z max) | 73 | p8 = vec2 (x max) (y max) |
84 | 74 | ||
85 | 75 | ||
86 | -- | Create the minimal AABB fully containing the specified Sphere. | 76 | -- | Create the minimal AABB fully containing the specified Sphere. |
87 | aabbFromSphere :: Sphere -> AABB | 77 | aabbFromCircle :: Circle -> AABB |
88 | aabbFromSphere (Sphere c r) = AABB bot top | 78 | aabbFromCircle (Circle c r) = AABB bot top |
89 | where | ||
90 | bot = c - (vec3 r r r) | ||
91 | top = c + (vec3 r r r) | ||
92 | |||
93 | |||
94 | -- | Create the minimal AABB fully containing the specified 'BoundingVolume's. | ||
95 | {-aabb :: [BoundingVolume] -> BoundingVolume | ||
96 | aabb = Spear.Collision.BoundingVolume.fromList BoundingBox . foldr generate [] | ||
97 | where | 79 | where |
98 | generate (AABB min max) acc = p1:p2:p3:p4:p5:p6:p7:p8:acc | 80 | bot = c - (vec2 r r) |
99 | where | 81 | top = c + (vec2 r r) |
100 | p1 = vec3 (x min) (y min) (z min) | ||
101 | p2 = vec3 (x min) (y min) (z max) | ||
102 | p3 = vec3 (x min) (y max) (z min) | ||
103 | p4 = vec3 (x min) (y max) (z max) | ||
104 | p5 = vec3 (x max) (y min) (z min) | ||
105 | p6 = vec3 (x max) (y min) (z max) | ||
106 | p7 = vec3 (x max) (y max) (z min) | ||
107 | p8 = vec3 (x max) (y max) (z max) | ||
108 | |||
109 | generate (Sphere c r) acc = p1:p2:p3:p4:p5:p6:acc | ||
110 | where | ||
111 | p1 = c + unitX * (vec3 r r r) | ||
112 | p2 = c - unitX * (vec3 r r r) | ||
113 | p3 = c + unitY * (vec3 r r r) | ||
114 | p4 = c - unitY * (vec3 r r r) | ||
115 | p5 = c + unitZ * (vec3 r r r) | ||
116 | p6 = c - unitZ * (vec3 r r r)-} | ||
diff --git a/Spear/Collision/Collisioner.hs b/Spear/Collision/Collisioner.hs index 266244d..af6fee5 100644 --- a/Spear/Collision/Collisioner.hs +++ b/Spear/Collision/Collisioner.hs | |||
@@ -13,8 +13,8 @@ where | |||
13 | import Spear.Collision.Collision as C | 13 | import Spear.Collision.Collision as C |
14 | import Spear.Collision.Types | 14 | import Spear.Collision.Types |
15 | import Spear.Math.AABB | 15 | import Spear.Math.AABB |
16 | import Spear.Math.Sphere | 16 | import Spear.Math.Circle |
17 | import Spear.Math.Vector3 | 17 | import Spear.Math.Vector2 |
18 | 18 | ||
19 | 19 | ||
20 | -- | A collisioner component. | 20 | -- | A collisioner component. |
@@ -22,7 +22,7 @@ data Collisioner | |||
22 | -- | An axis-aligned bounding box. | 22 | -- | An axis-aligned bounding box. |
23 | = AABBCol { getBox :: !AABB } | 23 | = AABBCol { getBox :: !AABB } |
24 | -- | A bounding sphere. | 24 | -- | A bounding sphere. |
25 | | SphereCol { getSphere :: !Sphere } | 25 | | CircleCol { getSphere :: !Circle } |
26 | 26 | ||
27 | 27 | ||
28 | -- | Create a 'Collisioner' from the specified 'AABB'. | 28 | -- | Create a 'Collisioner' from the specified 'AABB'. |
@@ -31,47 +31,45 @@ aabbCollisioner = AABBCol | |||
31 | 31 | ||
32 | 32 | ||
33 | -- | Create a 'Collisioner' from the specified 'BSphere'. | 33 | -- | Create a 'Collisioner' from the specified 'BSphere'. |
34 | sphereCollisioner :: Sphere -> Collisioner | 34 | sphereCollisioner :: Circle -> Collisioner |
35 | sphereCollisioner = SphereCol | 35 | sphereCollisioner = CircleCol |
36 | 36 | ||
37 | 37 | ||
38 | -- | Create the minimal 'AABB' fully containing the specified collisioners. | 38 | -- | Create the minimal 'AABB' fully containing the specified collisioners. |
39 | buildAABB :: [Collisioner] -> AABB | 39 | buildAABB :: [Collisioner] -> AABB |
40 | buildAABB cols = aabb $ Spear.Collision.Collisioner.generatePoints cols | 40 | buildAABB cols = aabb $ generatePoints cols |
41 | 41 | ||
42 | 42 | ||
43 | -- | Create the minimal 'AABB' collisioner fully containing the specified 'BSphere'. | 43 | -- | Create the minimal 'AABB' collisioner fully containing the specified 'BSphere'. |
44 | boxFromSphere :: Sphere -> Collisioner | 44 | boxFromSphere :: Circle -> Collisioner |
45 | boxFromSphere = AABBCol . aabbFromSphere | 45 | boxFromSphere = AABBCol . aabbFromCircle |
46 | 46 | ||
47 | 47 | ||
48 | generatePoints :: [Collisioner] -> [Vector3] | 48 | generatePoints :: [Collisioner] -> [Vector2] |
49 | generatePoints = foldr generate [] | 49 | generatePoints = foldr generate [] |
50 | where | 50 | where |
51 | generate (AABBCol (AABB min max)) acc = p1:p2:p3:p4:p5:p6:p7:p8:acc | 51 | generate (AABBCol (AABB min max)) acc = p1:p2:p3:p4:p5:p6:p7:p8:acc |
52 | where | 52 | where |
53 | p1 = vec3 (x min) (y min) (z min) | 53 | p1 = vec2 (x min) (y min) |
54 | p2 = vec3 (x min) (y min) (z max) | 54 | p2 = vec2 (x min) (y min) |
55 | p3 = vec3 (x min) (y max) (z min) | 55 | p3 = vec2 (x min) (y max) |
56 | p4 = vec3 (x min) (y max) (z max) | 56 | p4 = vec2 (x min) (y max) |
57 | p5 = vec3 (x max) (y min) (z min) | 57 | p5 = vec2 (x max) (y min) |
58 | p6 = vec3 (x max) (y min) (z max) | 58 | p6 = vec2 (x max) (y min) |
59 | p7 = vec3 (x max) (y max) (z min) | 59 | p7 = vec2 (x max) (y max) |
60 | p8 = vec3 (x max) (y max) (z max) | 60 | p8 = vec2 (x max) (y max) |
61 | 61 | ||
62 | generate (SphereCol (Sphere c r)) acc = p1:p2:p3:p4:p5:p6:acc | 62 | generate (CircleCol (Circle c r)) acc = p1:p2:p3:p4:acc |
63 | where | 63 | where |
64 | p1 = c + unitX * (vec3 r r r) | 64 | p1 = c + unitx * (vec2 r r) |
65 | p2 = c - unitX * (vec3 r r r) | 65 | p2 = c - unitx * (vec2 r r) |
66 | p3 = c + unitY * (vec3 r r r) | 66 | p3 = c + unity * (vec2 r r) |
67 | p4 = c - unitY * (vec3 r r r) | 67 | p4 = c - unity * (vec2 r r) |
68 | p5 = c + unitZ * (vec3 r r r) | ||
69 | p6 = c - unitZ * (vec3 r r r) | ||
70 | 68 | ||
71 | 69 | ||
72 | -- | Collide the given collisioners. | 70 | -- | Collide the given collisioners. |
73 | collide :: Collisioner -> Collisioner -> CollisionType | 71 | collide :: Collisioner -> Collisioner -> CollisionType |
74 | collide (AABBCol box1) (AABBCol box2) = collideBox box1 box2 | 72 | collide (AABBCol box1) (AABBCol box2) = collideBox box1 box2 |
75 | collide (SphereCol s1) (SphereCol s2) = collideSphere s1 s2 | 73 | collide (CircleCol s1) (CircleCol s2) = collideSphere s1 s2 |
76 | collide (AABBCol box) (SphereCol sphere) = collideBox box sphere | 74 | collide (AABBCol box) (CircleCol sphere) = collideBox box sphere |
77 | collide (SphereCol sphere) (AABBCol box) = collideSphere sphere box | 75 | collide (CircleCol sphere) (AABBCol box) = collideSphere sphere box |
diff --git a/Spear/Math/AABB.hs b/Spear/Math/AABB.hs index 362ddd6..55e3083 100644 --- a/Spear/Math/AABB.hs +++ b/Spear/Math/AABB.hs | |||
@@ -7,22 +7,22 @@ module Spear.Math.AABB | |||
7 | where | 7 | where |
8 | 8 | ||
9 | 9 | ||
10 | import Spear.Math.Vector3 as Vector | 10 | import Spear.Math.Vector2 |
11 | 11 | ||
12 | 12 | ||
13 | -- | An axis-aligned bounding box. | 13 | -- | An axis-aligned bounding box. |
14 | data AABB = AABB {-# UNPACK #-} !Vector3 {-# UNPACK #-} !Vector3 | 14 | data AABB = AABB {-# UNPACK #-} !Vector2 {-# UNPACK #-} !Vector2 |
15 | 15 | ||
16 | 16 | ||
17 | -- | Create a 'AABB' from the given points. | 17 | -- | Create a 'AABB' from the given points. |
18 | aabb :: [Vector3] -> AABB | 18 | aabb :: [Vector2] -> AABB |
19 | 19 | ||
20 | aabb [] = error "Attempting to build a BoundingVolume from an empty list!" | 20 | aabb [] = error "Attempting to build a BoundingVolume from an empty list!" |
21 | 21 | ||
22 | aabb (x:xs) = foldr update (AABB x x) xs | 22 | aabb (x:xs) = foldr update (AABB x x) xs |
23 | where update p (AABB min max) = AABB (Vector.min p min) (Vector.max p max) | 23 | where update p (AABB min max) = AABB (v2min p min) (v2max p max) |
24 | 24 | ||
25 | 25 | ||
26 | -- | Return 'True' if the given 'AABB' contains the given point, 'False' otherwise. | 26 | -- | Return 'True' if the given 'AABB' contains the given point, 'False' otherwise. |
27 | aabbpt :: AABB -> Vector3 -> Bool | 27 | aabbpt :: AABB -> Vector2 -> Bool |
28 | (AABB min max) `aabbpt` v = v >= min && v <= max | 28 | aabbpt (AABB min max) v = v >= min && v <= max |
diff --git a/Spear/Math/Circle.hs b/Spear/Math/Circle.hs new file mode 100644 index 0000000..a34de0b --- /dev/null +++ b/Spear/Math/Circle.hs | |||
@@ -0,0 +1,33 @@ | |||
1 | module Spear.Math.Circle | ||
2 | ( | ||
3 | Circle(..) | ||
4 | , circle | ||
5 | , circlept | ||
6 | ) | ||
7 | where | ||
8 | |||
9 | |||
10 | import Spear.Math.Vector2 | ||
11 | |||
12 | |||
13 | -- | A bounding volume. | ||
14 | data Circle = Circle | ||
15 | { center :: {-# UNPACK #-} !Vector2 | ||
16 | , radius :: {-# UNPACK #-} !Float | ||
17 | } | ||
18 | |||
19 | |||
20 | -- | Create a 'Sphere' from the given points. | ||
21 | circle :: [Vector2] -> Circle | ||
22 | circle [] = error "Attempting to build a Circle from an empty list!" | ||
23 | circle (x:xs) = Circle c r | ||
24 | where | ||
25 | c = min + (max-min)/2 | ||
26 | r = norm $ max - c | ||
27 | (min,max) = foldr update (x,x) xs | ||
28 | update p (min,max) = (v2min p min, v2max p max) | ||
29 | |||
30 | |||
31 | -- | Return 'True' if the given 'Sphere' contains the given point, 'False' otherwise. | ||
32 | circlept :: Circle -> Vector2 -> Bool | ||
33 | circlept (Circle c r) p = r*r >= normSq (p - c) | ||
diff --git a/Spear/Math/Octree.hs b/Spear/Math/Octree.hs deleted file mode 100644 index 15f7dde..0000000 --- a/Spear/Math/Octree.hs +++ /dev/null | |||
@@ -1,284 +0,0 @@ | |||
1 | module Spear.Math.Octree | ||
2 | ( | ||
3 | Octree | ||
4 | , makeOctree | ||
5 | , clone | ||
6 | , Spear.Math.Octree.insert | ||
7 | , insertl | ||
8 | , Spear.Math.Octree.map | ||
9 | , gmap | ||
10 | , population | ||
11 | ) | ||
12 | where | ||
13 | |||
14 | import Spear.Collision.Types | ||
15 | import Spear.Math.AABB | ||
16 | import Spear.Math.Vector3 | ||
17 | |||
18 | import Control.Applicative ((<*>)) | ||
19 | import Data.List | ||
20 | import Data.Functor | ||
21 | import Data.Monoid | ||
22 | import qualified Data.Foldable as F | ||
23 | |||
24 | |||
25 | -- | Represents an Octree. | ||
26 | data Octree e | ||
27 | = Octree | ||
28 | { | ||
29 | root :: !AABB, | ||
30 | ents :: ![e], | ||
31 | c1 :: !(Octree e), | ||
32 | c2 :: !(Octree e), | ||
33 | c3 :: !(Octree e), | ||
34 | c4 :: !(Octree e), | ||
35 | c5 :: !(Octree e), | ||
36 | c6 :: !(Octree e), | ||
37 | c7 :: !(Octree e), | ||
38 | c8 :: !(Octree e) | ||
39 | } | ||
40 | | | ||
41 | Leaf | ||
42 | { | ||
43 | root :: !AABB, | ||
44 | ents :: ![e] | ||
45 | } | ||
46 | |||
47 | |||
48 | -- | Builds an Octree using the specified AABB as the root and having the specified depth. | ||
49 | makeOctree :: Int -> AABB -> Octree e | ||
50 | makeOctree d root@(AABB min max) | ||
51 | | d == 0 = Leaf root [] | ||
52 | | otherwise = Octree root [] c1 c2 c3 c4 c5 c6 c7 c8 | ||
53 | where | ||
54 | boxes = subdivide root | ||
55 | c1 = makeOctree (d-1) $ boxes !! 0 | ||
56 | c2 = makeOctree (d-1) $ boxes !! 1 | ||
57 | c3 = makeOctree (d-1) $ boxes !! 2 | ||
58 | c4 = makeOctree (d-1) $ boxes !! 3 | ||
59 | c5 = makeOctree (d-1) $ boxes !! 4 | ||
60 | c6 = makeOctree (d-1) $ boxes !! 5 | ||
61 | c7 = makeOctree (d-1) $ boxes !! 6 | ||
62 | c8 = makeOctree (d-1) $ boxes !! 7 | ||
63 | |||
64 | |||
65 | subdivide :: AABB -> [AABB] | ||
66 | subdivide (AABB min max) = [a1, a2, a3, a4, a5, a6, a7, a8] | ||
67 | where | ||
68 | v = (max-min) / 2 | ||
69 | c = vec3 (x min + x v) (y min + y v) (z min + z v) | ||
70 | a1 = AABB min c | ||
71 | a2 = AABB ( vec3 (x min) (y min) (z c) ) ( vec3 (x c) (y c) (z max) ) | ||
72 | a3 = AABB ( vec3 (x min) (y c) (z min) ) ( vec3 (x c) (y max) (z c) ) | ||
73 | a4 = AABB ( vec3 (x min) (y c) (z c) ) ( vec3 (x c) (y max) (z max) ) | ||
74 | a5 = AABB ( vec3 (x c) (y min) (z min) ) ( vec3 (x max) (y c) (z c) ) | ||
75 | a6 = AABB ( vec3 (x c) (y min) (z c) ) ( vec3 (x max) (y c) (z max) ) | ||
76 | a7 = AABB ( vec3 (x c) (y c) (z min) ) ( vec3 (x max) (y max) (z c) ) | ||
77 | a8 = AABB c max | ||
78 | |||
79 | |||
80 | -- | Clones the structure of an octree. The new octree has no entities. | ||
81 | clone :: Octree e -> Octree e | ||
82 | clone (Leaf root ents) = Leaf root [] | ||
83 | clone (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = Octree root [] c1' c2' c3' c4' c5' c6' c7' c8' | ||
84 | where | ||
85 | c1' = clone c1 | ||
86 | c2' = clone c2 | ||
87 | c3' = clone c3 | ||
88 | c4' = clone c4 | ||
89 | c5' = clone c5 | ||
90 | c6' = clone c6 | ||
91 | c7' = clone c7 | ||
92 | c8' = clone c8 | ||
93 | |||
94 | |||
95 | keep :: (e -> AABB -> CollisionType) -> AABB -> e -> Bool | ||
96 | keep testAABB aabb e = test == FullyContainedBy | ||
97 | where test = e `testAABB` aabb | ||
98 | |||
99 | |||
100 | -- | Inserts an entity into the given octree. | ||
101 | insert :: (e -> AABB -> CollisionType) -> Octree e -> e -> Octree e | ||
102 | insert testAABB octree e = octree' where (octree', _) = insert' testAABB e octree | ||
103 | |||
104 | |||
105 | insert' :: (e -> AABB -> CollisionType) -> e -> Octree e -> (Octree e, Bool) | ||
106 | |||
107 | |||
108 | insert' testAABB e l@(Leaf root ents) | ||
109 | | test == True = (Leaf root (e:ents), True) | ||
110 | | otherwise = (l, False) | ||
111 | where | ||
112 | test = keep testAABB root e | ||
113 | |||
114 | |||
115 | insert' testAABB e o@(Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) | ||
116 | | test == False = (o, False) | ||
117 | | otherwise = | ||
118 | if isContainedInChild then (Octree root ents c1' c2' c3' c4' c5' c6' c7' c8', True) | ||
119 | else (Octree root (e:ents) c1 c2 c3 c4 c5 c6 c7 c8, True) | ||
120 | where | ||
121 | children = [c1,c2,c3,c4,c5,c6,c7,c8] | ||
122 | test = keep testAABB root e | ||
123 | descend = fmap (Spear.Math.Octree.insert' testAABB e) children | ||
124 | (children', results) = unzip descend | ||
125 | isContainedInChild = or results | ||
126 | c1' = children' !! 0 | ||
127 | c2' = children' !! 1 | ||
128 | c3' = children' !! 2 | ||
129 | c4' = children' !! 3 | ||
130 | c5' = children' !! 4 | ||
131 | c6' = children' !! 5 | ||
132 | c7' = children' !! 6 | ||
133 | c8' = children' !! 7 | ||
134 | |||
135 | |||
136 | -- | Inserts a list of entities into the given octree. | ||
137 | insertl :: (e -> AABB -> CollisionType) -> Octree e -> [e] -> Octree e | ||
138 | insertl testAABB octree es = octree' where (octree', _) = insertl' testAABB es octree | ||
139 | |||
140 | |||
141 | insertl' :: (e -> AABB -> CollisionType) -> [e] -> Octree e -> (Octree e, [e]) | ||
142 | |||
143 | insertl' testAABB es (Leaf root ents) = (Leaf root ents', outliers) | ||
144 | where | ||
145 | ents' = ents ++ ents_kept | ||
146 | ents_kept = filter (keep testAABB root) es | ||
147 | outliers = filter (not . keep testAABB root) es | ||
148 | |||
149 | insertl' testAABB es (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
150 | (Octree root ents' c1' c2' c3' c4' c5' c6' c7' c8', outliers) | ||
151 | where | ||
152 | ents' = ents ++ ents_kept | ||
153 | new_ents = es ++ ents1 ++ ents2 ++ ents3 ++ ents4 ++ ents5 ++ ents6 ++ ents7 ++ ents8 | ||
154 | ents_kept = filter (keep testAABB root) new_ents | ||
155 | outliers = filter (not . keep testAABB root) new_ents | ||
156 | (c1', ents1) = insertl' testAABB es c1 | ||
157 | (c2', ents2) = insertl' testAABB es c2 | ||
158 | (c3', ents3) = insertl' testAABB es c3 | ||
159 | (c4', ents4) = insertl' testAABB es c4 | ||
160 | (c5', ents5) = insertl' testAABB es c5 | ||
161 | (c6', ents6) = insertl' testAABB es c6 | ||
162 | (c7', ents7) = insertl' testAABB es c7 | ||
163 | (c8', ents8) = insertl' testAABB es c8 | ||
164 | |||
165 | |||
166 | -- | Extracts all entities from an octree. The resulting octree has no entities. | ||
167 | extract :: Octree e -> (Octree e, [e]) | ||
168 | extract (Leaf root ents) = (Leaf root [], ents) | ||
169 | extract (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = (Octree root [] c1' c2' c3' c4' c5' c6' c7' c8', ents') | ||
170 | where | ||
171 | (c1', ents1) = extract c1 | ||
172 | (c2', ents2) = extract c2 | ||
173 | (c3', ents3) = extract c3 | ||
174 | (c4', ents4) = extract c4 | ||
175 | (c5', ents5) = extract c5 | ||
176 | (c6', ents6) = extract c6 | ||
177 | (c7', ents7) = extract c7 | ||
178 | (c8', ents8) = extract c8 | ||
179 | ents' = ents ++ ents1 ++ ents2 ++ ents3 ++ ents4 ++ ents5 ++ ents6 ++ ents7 ++ ents8 | ||
180 | |||
181 | |||
182 | -- | Applies the given function to the entities in the octree. | ||
183 | -- Entities that break out of their cell are reallocated appropriately. | ||
184 | map :: (e -> AABB -> CollisionType) -> (e -> e) -> Octree e -> Octree e | ||
185 | map testAABB f o = let (o', outliers) = map' testAABB f o in insertl testAABB o' outliers | ||
186 | |||
187 | |||
188 | map' :: (e -> AABB -> CollisionType) -> (e -> e) -> Octree e -> (Octree e, [e]) | ||
189 | |||
190 | |||
191 | map' testAABB f (Leaf root ents) = (Leaf root ents_kept, outliers) | ||
192 | where | ||
193 | ents' = fmap f ents | ||
194 | ents_kept = filter (keep testAABB root) ents' | ||
195 | outliers = filter (not . keep testAABB root) ents' | ||
196 | |||
197 | |||
198 | map' testAABB f (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
199 | (Octree root ents_kept c1' c2' c3' c4' c5' c6' c7' c8', outliers) | ||
200 | where | ||
201 | ents' = (fmap f ents) ++ out1 ++ out2 ++ out3 ++ out4 ++ out5 ++ out6 ++ out7 ++ out8 | ||
202 | ents_kept = filter (keep testAABB root) ents' | ||
203 | outliers = filter (not . keep testAABB root) ents' | ||
204 | (c1', out1) = map' testAABB f c1 | ||
205 | (c2', out2) = map' testAABB f c2 | ||
206 | (c3', out3) = map' testAABB f c3 | ||
207 | (c4', out4) = map' testAABB f c4 | ||
208 | (c5', out5) = map' testAABB f c5 | ||
209 | (c6', out6) = map' testAABB f c6 | ||
210 | (c7', out7) = map' testAABB f c7 | ||
211 | (c8', out8) = map' testAABB f c8 | ||
212 | |||
213 | |||
214 | -- | Applies a function to the entity groups in the octree. | ||
215 | -- Entities that break out of their cell are reallocated appropriately. | ||
216 | gmap :: (e -> AABB -> CollisionType) -> (e -> e -> e) -> Octree e -> Octree e | ||
217 | gmap testAABB f o = let (o', outliers) = gmap' testAABB f o in insertl testAABB o' outliers | ||
218 | |||
219 | |||
220 | gmap' :: (e -> AABB -> CollisionType) -> (e -> e -> e) -> Octree e -> (Octree e, [e]) | ||
221 | |||
222 | gmap' testAABB f (Leaf root ents) = (Leaf root ents_kept, outliers) | ||
223 | where | ||
224 | ents' = f <$> ents <*> ents | ||
225 | ents_kept = filter (keep testAABB root) ents' | ||
226 | outliers = filter (not . keep testAABB root) ents' | ||
227 | |||
228 | gmap' testAABB f (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
229 | (Octree root ents_kept c1' c2' c3' c4' c5' c6' c7' c8', outliers) | ||
230 | where | ||
231 | ents' = (f <$> ents <*> ents) ++ out1 ++ out2 ++ out3 ++ out4 ++ out5 ++ out6 ++ out7 ++ out8 | ||
232 | ents_kept = filter (keep testAABB root) ents' | ||
233 | outliers = filter (not . keep testAABB root) ents' | ||
234 | (c1', out1) = gmap' testAABB f c1 | ||
235 | (c2', out2) = gmap' testAABB f c2 | ||
236 | (c3', out3) = gmap' testAABB f c3 | ||
237 | (c4', out4) = gmap' testAABB f c4 | ||
238 | (c5', out5) = gmap' testAABB f c5 | ||
239 | (c6', out6) = gmap' testAABB f c6 | ||
240 | (c7', out7) = gmap' testAABB f c7 | ||
241 | (c8', out8) = gmap' testAABB f c8 | ||
242 | |||
243 | |||
244 | population :: Octree e -> Int | ||
245 | population = F.foldr (\_ acc -> acc+1) 0 | ||
246 | |||
247 | |||
248 | |||
249 | |||
250 | instance Functor Octree where | ||
251 | |||
252 | fmap f (Leaf root ents) = Leaf root $ fmap f ents | ||
253 | |||
254 | fmap f (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
255 | Octree root (fmap f ents) c1' c2' c3' c4' c5' c6' c7' c8' | ||
256 | where | ||
257 | c1' = fmap f c1 | ||
258 | c2' = fmap f c2 | ||
259 | c3' = fmap f c3 | ||
260 | c4' = fmap f c4 | ||
261 | c5' = fmap f c5 | ||
262 | c6' = fmap f c6 | ||
263 | c7' = fmap f c7 | ||
264 | c8' = fmap f c8 | ||
265 | |||
266 | |||
267 | |||
268 | instance F.Foldable Octree where | ||
269 | |||
270 | foldMap f (Leaf root ents) = mconcat . fmap f $ ents | ||
271 | |||
272 | foldMap f (Octree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
273 | mconcat (fmap f ents) `mappend` | ||
274 | c1' `mappend` c2' `mappend` c3' `mappend` c4' `mappend` | ||
275 | c5' `mappend` c6' `mappend` c7' `mappend` c8' | ||
276 | where | ||
277 | c1' = F.foldMap f c1 | ||
278 | c2' = F.foldMap f c2 | ||
279 | c3' = F.foldMap f c3 | ||
280 | c4' = F.foldMap f c4 | ||
281 | c5' = F.foldMap f c5 | ||
282 | c6' = F.foldMap f c6 | ||
283 | c7' = F.foldMap f c7 | ||
284 | c8' = F.foldMap f c8 | ||
diff --git a/Spear/Math/QuadTree.hs b/Spear/Math/QuadTree.hs new file mode 100644 index 0000000..2e92265 --- /dev/null +++ b/Spear/Math/QuadTree.hs | |||
@@ -0,0 +1,248 @@ | |||
1 | module Spear.Math.QuadTree | ||
2 | ( | ||
3 | QuadTree | ||
4 | , makeQuadTree | ||
5 | , clone | ||
6 | , Spear.Math.QuadTree.insert | ||
7 | , Spear.Math.QuadTree.map | ||
8 | , gmap | ||
9 | ) | ||
10 | where | ||
11 | |||
12 | import Spear.Collision.Types | ||
13 | import Spear.Math.AABB | ||
14 | import Spear.Math.Vector2 | ||
15 | |||
16 | import Control.Applicative ((<*>)) | ||
17 | import Data.List | ||
18 | import Data.Functor | ||
19 | import Data.Monoid | ||
20 | import qualified Data.Foldable as F | ||
21 | |||
22 | |||
23 | -- | Represents an QuadTree. | ||
24 | data QuadTree e | ||
25 | = QuadTree | ||
26 | { root :: !AABB | ||
27 | , ents :: ![e] | ||
28 | , c1 :: !(QuadTree e) | ||
29 | , c2 :: !(QuadTree e) | ||
30 | , c3 :: !(QuadTree e) | ||
31 | , c4 :: !(QuadTree e) | ||
32 | , c5 :: !(QuadTree e) | ||
33 | , c6 :: !(QuadTree e) | ||
34 | , c7 :: !(QuadTree e) | ||
35 | , c8 :: !(QuadTree e) | ||
36 | } | ||
37 | | | ||
38 | Leaf | ||
39 | { root :: !AABB | ||
40 | , ents :: ![e] | ||
41 | } | ||
42 | |||
43 | |||
44 | -- | Builds an QuadTree using the specified AABB as the root and having the specified depth. | ||
45 | makeQuadTree :: Int -> AABB -> QuadTree e | ||
46 | makeQuadTree d root@(AABB min max) | ||
47 | | d == 0 = Leaf root [] | ||
48 | | otherwise = QuadTree root [] c1 c2 c3 c4 c5 c6 c7 c8 | ||
49 | where | ||
50 | boxes = subdivide root | ||
51 | c1 = makeQuadTree (d-1) $ boxes !! 0 | ||
52 | c2 = makeQuadTree (d-1) $ boxes !! 1 | ||
53 | c3 = makeQuadTree (d-1) $ boxes !! 2 | ||
54 | c4 = makeQuadTree (d-1) $ boxes !! 3 | ||
55 | c5 = makeQuadTree (d-1) $ boxes !! 4 | ||
56 | c6 = makeQuadTree (d-1) $ boxes !! 5 | ||
57 | c7 = makeQuadTree (d-1) $ boxes !! 6 | ||
58 | c8 = makeQuadTree (d-1) $ boxes !! 7 | ||
59 | |||
60 | |||
61 | subdivide :: AABB -> [AABB] | ||
62 | subdivide (AABB min max) = [a1, a2, a3, a4, a5, a6, a7, a8] | ||
63 | where | ||
64 | v = (max-min) / 2 | ||
65 | c = vec2 (x min + x v) (y min + y v) | ||
66 | a1 = AABB min c | ||
67 | a2 = AABB ( vec2 (x min) (y min)) ( vec2 (x c) (y c) ) | ||
68 | a3 = AABB ( vec2 (x min) (y c) ) ( vec2 (x c) (y max)) | ||
69 | a4 = AABB ( vec2 (x min) (y c) ) ( vec2 (x c) (y max)) | ||
70 | a5 = AABB ( vec2 (x c) (y min)) ( vec2 (x max) (y c) ) | ||
71 | a6 = AABB ( vec2 (x c) (y min)) ( vec2 (x max) (y c) ) | ||
72 | a7 = AABB ( vec2 (x c) (y c) ) ( vec2 (x max) (y max)) | ||
73 | a8 = AABB c max | ||
74 | |||
75 | |||
76 | -- | Clones the structure of an octree. The new octree has no entities. | ||
77 | clone :: QuadTree e -> QuadTree e | ||
78 | clone (Leaf root ents) = Leaf root [] | ||
79 | clone (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = QuadTree root [] c1' c2' c3' c4' c5' c6' c7' c8' | ||
80 | where | ||
81 | c1' = clone c1 | ||
82 | c2' = clone c2 | ||
83 | c3' = clone c3 | ||
84 | c4' = clone c4 | ||
85 | c5' = clone c5 | ||
86 | c6' = clone c6 | ||
87 | c7' = clone c7 | ||
88 | c8' = clone c8 | ||
89 | |||
90 | |||
91 | keep :: (e -> AABB -> CollisionType) -> AABB -> e -> Bool | ||
92 | keep testAABB aabb e = test == FullyContainedBy | ||
93 | where test = e `testAABB` aabb | ||
94 | |||
95 | |||
96 | -- | Inserts a list of entities into the given octree. | ||
97 | insert :: (e -> AABB -> CollisionType) -> QuadTree e -> [e] -> QuadTree e | ||
98 | insert testAABB octree es = octree' where (octree', _) = insert' testAABB es octree | ||
99 | |||
100 | |||
101 | insert' :: (e -> AABB -> CollisionType) -> [e] -> QuadTree e -> (QuadTree e, [e]) | ||
102 | |||
103 | insert' testAABB es (Leaf root ents) = (Leaf root ents', outliers) | ||
104 | where | ||
105 | ents' = ents ++ ents_kept | ||
106 | ents_kept = filter (keep testAABB root) es | ||
107 | outliers = filter (not . keep testAABB root) es | ||
108 | |||
109 | insert' testAABB es (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
110 | (QuadTree root ents' c1' c2' c3' c4' c5' c6' c7' c8', outliers) | ||
111 | where | ||
112 | ents' = ents ++ ents_kept | ||
113 | new_ents = es ++ ents1 ++ ents2 ++ ents3 ++ ents4 ++ ents5 ++ ents6 ++ ents7 ++ ents8 | ||
114 | ents_kept = filter (keep testAABB root) new_ents | ||
115 | outliers = filter (not . keep testAABB root) new_ents | ||
116 | (c1', ents1) = insert' testAABB es c1 | ||
117 | (c2', ents2) = insert' testAABB es c2 | ||
118 | (c3', ents3) = insert' testAABB es c3 | ||
119 | (c4', ents4) = insert' testAABB es c4 | ||
120 | (c5', ents5) = insert' testAABB es c5 | ||
121 | (c6', ents6) = insert' testAABB es c6 | ||
122 | (c7', ents7) = insert' testAABB es c7 | ||
123 | (c8', ents8) = insert' testAABB es c8 | ||
124 | |||
125 | |||
126 | -- | Extracts all entities from an octree. The resulting octree has no entities. | ||
127 | extract :: QuadTree e -> (QuadTree e, [e]) | ||
128 | extract (Leaf root ents) = (Leaf root [], ents) | ||
129 | extract (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = (QuadTree root [] c1' c2' c3' c4' c5' c6' c7' c8', ents') | ||
130 | where | ||
131 | (c1', ents1) = extract c1 | ||
132 | (c2', ents2) = extract c2 | ||
133 | (c3', ents3) = extract c3 | ||
134 | (c4', ents4) = extract c4 | ||
135 | (c5', ents5) = extract c5 | ||
136 | (c6', ents6) = extract c6 | ||
137 | (c7', ents7) = extract c7 | ||
138 | (c8', ents8) = extract c8 | ||
139 | ents' = ents ++ ents1 ++ ents2 ++ ents3 ++ ents4 ++ ents5 ++ ents6 ++ ents7 ++ ents8 | ||
140 | |||
141 | |||
142 | -- | Applies the given function to the entities in the octree. | ||
143 | -- Entities that break out of their cell are reallocated appropriately. | ||
144 | map :: (e -> AABB -> CollisionType) -> (e -> e) -> QuadTree e -> QuadTree e | ||
145 | map testAABB f o = | ||
146 | let (o', outliers) = map' testAABB f o | ||
147 | in Spear.Math.QuadTree.insert testAABB o' outliers | ||
148 | |||
149 | |||
150 | map' :: (e -> AABB -> CollisionType) -> (e -> e) -> QuadTree e -> (QuadTree e, [e]) | ||
151 | |||
152 | |||
153 | map' testAABB f (Leaf root ents) = (Leaf root ents_kept, outliers) | ||
154 | where | ||
155 | ents' = fmap f ents | ||
156 | ents_kept = filter (keep testAABB root) ents' | ||
157 | outliers = filter (not . keep testAABB root) ents' | ||
158 | |||
159 | |||
160 | map' testAABB f (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
161 | (QuadTree root ents_kept c1' c2' c3' c4' c5' c6' c7' c8', outliers) | ||
162 | where | ||
163 | ents' = (fmap f ents) ++ out1 ++ out2 ++ out3 ++ out4 ++ out5 ++ out6 ++ out7 ++ out8 | ||
164 | ents_kept = filter (keep testAABB root) ents' | ||
165 | outliers = filter (not . keep testAABB root) ents' | ||
166 | (c1', out1) = map' testAABB f c1 | ||
167 | (c2', out2) = map' testAABB f c2 | ||
168 | (c3', out3) = map' testAABB f c3 | ||
169 | (c4', out4) = map' testAABB f c4 | ||
170 | (c5', out5) = map' testAABB f c5 | ||
171 | (c6', out6) = map' testAABB f c6 | ||
172 | (c7', out7) = map' testAABB f c7 | ||
173 | (c8', out8) = map' testAABB f c8 | ||
174 | |||
175 | |||
176 | -- | Applies a function to the entity groups in the octree. | ||
177 | -- Entities that break out of their cell are reallocated appropriately. | ||
178 | gmap :: (e -> AABB -> CollisionType) -> (e -> e -> e) -> QuadTree e -> QuadTree e | ||
179 | gmap testAABB f o = | ||
180 | let (o', outliers) = gmap' testAABB f o | ||
181 | in Spear.Math.QuadTree.insert testAABB o' outliers | ||
182 | |||
183 | |||
184 | gmap' :: (e -> AABB -> CollisionType) -> (e -> e -> e) -> QuadTree e -> (QuadTree e, [e]) | ||
185 | |||
186 | gmap' testAABB f (Leaf root ents) = (Leaf root ents_kept, outliers) | ||
187 | where | ||
188 | ents' = f <$> ents <*> ents | ||
189 | ents_kept = filter (keep testAABB root) ents' | ||
190 | outliers = filter (not . keep testAABB root) ents' | ||
191 | |||
192 | gmap' testAABB f (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
193 | (QuadTree root ents_kept c1' c2' c3' c4' c5' c6' c7' c8', outliers) | ||
194 | where | ||
195 | ents' = (f <$> ents <*> ents) ++ out1 ++ out2 ++ out3 ++ out4 ++ out5 ++ out6 ++ out7 ++ out8 | ||
196 | ents_kept = filter (keep testAABB root) ents' | ||
197 | outliers = filter (not . keep testAABB root) ents' | ||
198 | (c1', out1) = gmap' testAABB f c1 | ||
199 | (c2', out2) = gmap' testAABB f c2 | ||
200 | (c3', out3) = gmap' testAABB f c3 | ||
201 | (c4', out4) = gmap' testAABB f c4 | ||
202 | (c5', out5) = gmap' testAABB f c5 | ||
203 | (c6', out6) = gmap' testAABB f c6 | ||
204 | (c7', out7) = gmap' testAABB f c7 | ||
205 | (c8', out8) = gmap' testAABB f c8 | ||
206 | |||
207 | |||
208 | population :: QuadTree e -> Int | ||
209 | population = F.foldr (\_ acc -> acc+1) 0 | ||
210 | |||
211 | |||
212 | |||
213 | |||
214 | instance Functor QuadTree where | ||
215 | |||
216 | fmap f (Leaf root ents) = Leaf root $ fmap f ents | ||
217 | |||
218 | fmap f (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
219 | QuadTree root (fmap f ents) c1' c2' c3' c4' c5' c6' c7' c8' | ||
220 | where | ||
221 | c1' = fmap f c1 | ||
222 | c2' = fmap f c2 | ||
223 | c3' = fmap f c3 | ||
224 | c4' = fmap f c4 | ||
225 | c5' = fmap f c5 | ||
226 | c6' = fmap f c6 | ||
227 | c7' = fmap f c7 | ||
228 | c8' = fmap f c8 | ||
229 | |||
230 | |||
231 | |||
232 | instance F.Foldable QuadTree where | ||
233 | |||
234 | foldMap f (Leaf root ents) = mconcat . fmap f $ ents | ||
235 | |||
236 | foldMap f (QuadTree root ents c1 c2 c3 c4 c5 c6 c7 c8) = | ||
237 | mconcat (fmap f ents) `mappend` | ||
238 | c1' `mappend` c2' `mappend` c3' `mappend` c4' `mappend` | ||
239 | c5' `mappend` c6' `mappend` c7' `mappend` c8' | ||
240 | where | ||
241 | c1' = F.foldMap f c1 | ||
242 | c2' = F.foldMap f c2 | ||
243 | c3' = F.foldMap f c3 | ||
244 | c4' = F.foldMap f c4 | ||
245 | c5' = F.foldMap f c5 | ||
246 | c6' = F.foldMap f c6 | ||
247 | c7' = F.foldMap f c7 | ||
248 | c8' = F.foldMap f c8 | ||
diff --git a/Spear/Math/Sphere.hs b/Spear/Math/Sphere.hs deleted file mode 100644 index 4a9e3fc..0000000 --- a/Spear/Math/Sphere.hs +++ /dev/null | |||
@@ -1,35 +0,0 @@ | |||
1 | module Spear.Math.Sphere | ||
2 | ( | ||
3 | Sphere(..) | ||
4 | , sphere | ||
5 | , spherept | ||
6 | ) | ||
7 | where | ||
8 | |||
9 | |||
10 | import Spear.Math.Vector3 as Vector | ||
11 | |||
12 | |||
13 | -- | A bounding volume. | ||
14 | data Sphere = Sphere | ||
15 | { center :: {-# UNPACK #-} !Vector3 | ||
16 | , radius :: {-# UNPACK #-} !Float | ||
17 | } | ||
18 | |||
19 | |||
20 | -- | Create a 'Sphere' from the given points. | ||
21 | sphere :: [Vector3] -> Sphere | ||
22 | |||
23 | sphere [] = error "Attempting to build a BoundingVolume from an empty list!" | ||
24 | |||
25 | sphere (x:xs) = Sphere c r | ||
26 | where | ||
27 | c = min + (max-min)/2 | ||
28 | r = norm $ max - c | ||
29 | (min,max) = foldr update (x,x) xs | ||
30 | update p (min,max) = (Vector.min p min, Vector.max p max) | ||
31 | |||
32 | |||
33 | -- | Return 'True' if the given 'Sphere' contains the given point, 'False' otherwise. | ||
34 | spherept :: Sphere -> Vector3 -> Bool | ||
35 | (Sphere center radius) `spherept` p = radius*radius >= normSq (p - center) | ||
diff --git a/Spear/Scene/Scene.hs b/Spear/Scene/Scene.hs index fe0eff8..4658ddb 100644 --- a/Spear/Scene/Scene.hs +++ b/Spear/Scene/Scene.hs | |||
@@ -1,4 +1,7 @@ | |||
1 | module Spear.Scene.Scene | 1 | module Spear.Scene.Scene |
2 | where | ||
3 | |||
4 | {-module Spear.Scene.Scene | ||
2 | ( | 5 | ( |
3 | -- * Data types | 6 | -- * Data types |
4 | Scene | 7 | Scene |
@@ -150,3 +153,4 @@ collide' col scene@ListScene {} = | |||
150 | render :: (obj -> Game s ()) -> Scene obj -> Game s () | 153 | render :: (obj -> Game s ()) -> Scene obj -> Game s () |
151 | render rend (scene@ListScene {}) = Prelude.mapM_ rend $ objects scene | 154 | render rend (scene@ListScene {}) = Prelude.mapM_ rend $ objects scene |
152 | render rend (scene@OctreeScene {}) = F.mapM_ rend $ world scene | 155 | render rend (scene@OctreeScene {}) = F.mapM_ rend $ world scene |
156 | -} \ No newline at end of file | ||