clockwerk-opensim-stable – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | vero | 1 | /* The MIT License |
2 | * |
||
3 | * Copyright (c) 2010 Intel Corporation. |
||
4 | * All rights reserved. |
||
5 | * |
||
6 | * Based on the convexdecomposition library from |
||
7 | * <http://codesuppository.googlecode.com> by John W. Ratcliff and Stan Melax. |
||
8 | * |
||
9 | * Permission is hereby granted, free of charge, to any person obtaining a copy |
||
10 | * of this software and associated documentation files (the "Software"), to deal |
||
11 | * in the Software without restriction, including without limitation the rights |
||
12 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
||
13 | * copies of the Software, and to permit persons to whom the Software is |
||
14 | * furnished to do so, subject to the following conditions: |
||
15 | * |
||
16 | * The above copyright notice and this permission notice shall be included in |
||
17 | * all copies or substantial portions of the Software. |
||
18 | * |
||
19 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
||
20 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
||
21 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
||
22 | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
||
23 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
||
24 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
||
25 | * THE SOFTWARE. |
||
26 | */ |
||
27 | |||
28 | using System; |
||
29 | using System.Collections.Generic; |
||
30 | using System.Diagnostics; |
||
31 | |||
32 | namespace OpenSim.Region.Physics.ConvexDecompositionDotNet |
||
33 | { |
||
34 | public enum PlaneTriResult : int |
||
35 | { |
||
36 | PTR_FRONT, |
||
37 | PTR_BACK, |
||
38 | PTR_SPLIT |
||
39 | } |
||
40 | |||
41 | public static class PlaneTri |
||
42 | { |
||
43 | private static float DistToPt(float3 p, float4 plane) |
||
44 | { |
||
45 | return p.x * plane.x + p.y * plane.y + p.z * plane.z + plane.w; |
||
46 | } |
||
47 | |||
48 | private static PlaneTriResult getSidePlane(float3 p, float4 plane, float epsilon) |
||
49 | { |
||
50 | float d = DistToPt(p, plane); |
||
51 | |||
52 | if ((d + epsilon) > 0f) |
||
53 | return PlaneTriResult.PTR_FRONT; // it is 'in front' within the provided epsilon value. |
||
54 | |||
55 | return PlaneTriResult.PTR_BACK; |
||
56 | } |
||
57 | |||
58 | private static void add(float3 p, float3[] dest, ref int pcount) |
||
59 | { |
||
60 | dest[pcount++] = new float3(p); |
||
61 | Debug.Assert(pcount <= 4); |
||
62 | } |
||
63 | |||
64 | // assumes that the points are on opposite sides of the plane! |
||
65 | private static void intersect(float3 p1, float3 p2, float3 split, float4 plane) |
||
66 | { |
||
67 | float dp1 = DistToPt(p1, plane); |
||
68 | float[] dir = new float[3]; |
||
69 | |||
70 | dir[0] = p2[0] - p1[0]; |
||
71 | dir[1] = p2[1] - p1[1]; |
||
72 | dir[2] = p2[2] - p1[2]; |
||
73 | |||
74 | float dot1 = dir[0] * plane[0] + dir[1] * plane[1] + dir[2] * plane[2]; |
||
75 | float dot2 = dp1 - plane[3]; |
||
76 | |||
77 | float t = -(plane[3] + dot2) / dot1; |
||
78 | |||
79 | split.x = (dir[0] * t) + p1[0]; |
||
80 | split.y = (dir[1] * t) + p1[1]; |
||
81 | split.z = (dir[2] * t) + p1[2]; |
||
82 | } |
||
83 | |||
84 | public static PlaneTriResult planeTriIntersection(float4 plane, FaceTri triangle, float epsilon, ref float3[] front, out int fcount, ref float3[] back, out int bcount) |
||
85 | { |
||
86 | fcount = 0; |
||
87 | bcount = 0; |
||
88 | |||
89 | // get the three vertices of the triangle. |
||
90 | float3 p1 = triangle.P1; |
||
91 | float3 p2 = triangle.P2; |
||
92 | float3 p3 = triangle.P3; |
||
93 | |||
94 | PlaneTriResult r1 = getSidePlane(p1, plane, epsilon); // compute the side of the plane each vertex is on |
||
95 | PlaneTriResult r2 = getSidePlane(p2, plane, epsilon); |
||
96 | PlaneTriResult r3 = getSidePlane(p3, plane, epsilon); |
||
97 | |||
98 | if (r1 == r2 && r1 == r3) // if all three vertices are on the same side of the plane. |
||
99 | { |
||
100 | if (r1 == PlaneTriResult.PTR_FRONT) // if all three are in front of the plane, then copy to the 'front' output triangle. |
||
101 | { |
||
102 | add(p1, front, ref fcount); |
||
103 | add(p2, front, ref fcount); |
||
104 | add(p3, front, ref fcount); |
||
105 | } |
||
106 | else |
||
107 | { |
||
108 | add(p1, back, ref bcount); // if all three are in 'back' then copy to the 'back' output triangle. |
||
109 | add(p2, back, ref bcount); |
||
110 | add(p3, back, ref bcount); |
||
111 | } |
||
112 | return r1; // if all three points are on the same side of the plane return result |
||
113 | } |
||
114 | |||
115 | // ok.. we need to split the triangle at the plane. |
||
116 | |||
117 | // First test ray segment P1 to P2 |
||
118 | if (r1 == r2) // if these are both on the same side... |
||
119 | { |
||
120 | if (r1 == PlaneTriResult.PTR_FRONT) |
||
121 | { |
||
122 | add(p1, front, ref fcount); |
||
123 | add(p2, front, ref fcount); |
||
124 | } |
||
125 | else |
||
126 | { |
||
127 | add(p1, back, ref bcount); |
||
128 | add(p2, back, ref bcount); |
||
129 | } |
||
130 | } |
||
131 | else |
||
132 | { |
||
133 | float3 split = new float3(); |
||
134 | intersect(p1, p2, split, plane); |
||
135 | |||
136 | if (r1 == PlaneTriResult.PTR_FRONT) |
||
137 | { |
||
138 | |||
139 | add(p1, front, ref fcount); |
||
140 | add(split, front, ref fcount); |
||
141 | |||
142 | add(split, back, ref bcount); |
||
143 | add(p2, back, ref bcount); |
||
144 | |||
145 | } |
||
146 | else |
||
147 | { |
||
148 | add(p1, back, ref bcount); |
||
149 | add(split, back, ref bcount); |
||
150 | |||
151 | add(split, front, ref fcount); |
||
152 | add(p2, front, ref fcount); |
||
153 | } |
||
154 | |||
155 | } |
||
156 | |||
157 | // Next test ray segment P2 to P3 |
||
158 | if (r2 == r3) // if these are both on the same side... |
||
159 | { |
||
160 | if (r3 == PlaneTriResult.PTR_FRONT) |
||
161 | { |
||
162 | add(p3, front, ref fcount); |
||
163 | } |
||
164 | else |
||
165 | { |
||
166 | add(p3, back, ref bcount); |
||
167 | } |
||
168 | } |
||
169 | else |
||
170 | { |
||
171 | float3 split = new float3(); // split the point |
||
172 | intersect(p2, p3, split, plane); |
||
173 | |||
174 | if (r3 == PlaneTriResult.PTR_FRONT) |
||
175 | { |
||
176 | add(split, front, ref fcount); |
||
177 | add(split, back, ref bcount); |
||
178 | |||
179 | add(p3, front, ref fcount); |
||
180 | } |
||
181 | else |
||
182 | { |
||
183 | add(split, front, ref fcount); |
||
184 | add(split, back, ref bcount); |
||
185 | |||
186 | add(p3, back, ref bcount); |
||
187 | } |
||
188 | } |
||
189 | |||
190 | // Next test ray segment P3 to P1 |
||
191 | if (r3 != r1) // if these are both on the same side... |
||
192 | { |
||
193 | float3 split = new float3(); // split the point |
||
194 | intersect(p3, p1, split, plane); |
||
195 | |||
196 | if (r1 == PlaneTriResult.PTR_FRONT) |
||
197 | { |
||
198 | add(split, front, ref fcount); |
||
199 | add(split, back, ref bcount); |
||
200 | } |
||
201 | else |
||
202 | { |
||
203 | add(split, front, ref fcount); |
||
204 | add(split, back, ref bcount); |
||
205 | } |
||
206 | } |
||
207 | |||
208 | return PlaneTriResult.PTR_SPLIT; |
||
209 | } |
||
210 | } |
||
211 | } |