Reverted incorrect merge (missing files)
[blender.git] / extern / solid / src / broad / BP_EndpointList.cpp
1 /*
2  * SOLID - Software Library for Interference Detection
3  * 
4  * Copyright (C) 2001-2003  Dtecta.  All rights reserved.
5  *
6  * This library may be distributed under the terms of the Q Public License
7  * (QPL) as defined by Trolltech AS of Norway and appearing in the file
8  * LICENSE.QPL included in the packaging of this file.
9  *
10  * This library may be distributed and/or modified under the terms of the
11  * GNU General Public License (GPL) version 2 as published by the Free Software
12  * Foundation and appearing in the file LICENSE.GPL included in the
13  * packaging of this file.
14  *
15  * This library is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
17  *
18  * Commercial use or any other use of this library not covered by either 
19  * the QPL or the GPL requires an additional license from Dtecta. 
20  * Please contact info@dtecta.com for enquiries about the terms of commercial
21  * use of this library.
22  */
23
24 #include <float.h>
25 #include <algorithm>
26
27 #include "BP_EndpointList.h"
28 #include "BP_Scene.h"
29 #include "BP_Proxy.h"
30 #include "BP_ProxyList.h"
31
32 DT_Index BP_EndpointList::stab(const BP_Endpoint& pos, BP_ProxyList& proxies) const 
33 {
34         DT_Index result = std::upper_bound(begin(), end(), pos) - begin();
35         
36         if (result != 0) 
37         {
38                 DT_Index i = result - 1;
39                 DT_Count count = (*this)[i].getCount(); 
40                 while (count) 
41                 {
42                         const BP_Endpoint& endpoint = (*this)[i];
43                         if (endpoint.getType() == BP_Endpoint::MINIMUM &&
44                                 pos < (*this)[endpoint.getEndIndex()]) 
45                         {
46                                 proxies.add(endpoint.getProxy());
47                                 --count;
48                         }
49                         assert(i != 0 || count == 0);
50                         --i;
51                 }                                                                                       
52         }
53         return result;
54 }
55
56 DT_Scalar BP_EndpointList::nextLambda(DT_Index& index, 
57                                                                           DT_Scalar source, 
58                                                                           DT_Scalar delta) const
59 {
60         if (delta != 0.0f) 
61         {
62                 if (delta < 0.0f) 
63                 {
64                         if (index != 0) 
65                         {
66                                 return ((*this)[--index].getPos() - source) / delta;
67                         }
68                 }
69                 else 
70                 {
71                         if (index != size()) 
72                         {
73                                 return ((*this)[index++].getPos() - source) / delta;
74                         }
75                 }
76         }
77         return FLT_MAX;
78 }
79
80
81 void BP_EndpointList::range(const BP_Endpoint& min, 
82                                                         const BP_Endpoint& max,
83                                                         DT_Index& first, DT_Index& last,
84                                                         BP_ProxyList& proxies) const 
85 {
86         first = stab(min, proxies);
87         last  = std::upper_bound(begin(), end(), max) - begin();
88         
89         DT_Index i;
90         for (i = first; i != last; ++i) 
91         {
92                 const BP_Endpoint& endpoint = (*this)[i];
93                 if (endpoint.getType() == BP_Endpoint::MINIMUM) 
94                 {
95                         proxies.add(endpoint.getProxy());
96                 }
97         }
98 }
99
100 void BP_EndpointList::addInterval(const BP_Endpoint& min, 
101                                                                   const BP_Endpoint& max,
102                                                                   BP_ProxyList& proxies) 
103 {
104         assert(invariant());
105         DT_Index first, last;
106         range(min, max, first, last, proxies);
107         insert(begin() + last, max);
108         insert(begin() + first, min);
109         ++last; 
110         
111         (*this)[first].getCount() = first != 0 ? (*this)[first - 1].getCount() : 0;
112         (*this)[last].getCount() = (*this)[last - 1].getCount();
113         
114         
115         DT_Index i;
116         for (i = first; i != last; ++i) 
117         {
118                 ++(*this)[i].getCount();
119                 (*this)[i].getIndex() = i;
120         } 
121         for (; i != size(); ++i) 
122         {
123                 (*this)[i].getIndex() = i;
124         } 
125         
126         assert(invariant());
127 }
128
129 void BP_EndpointList::removeInterval(DT_Index first, DT_Index last,
130                                                                          BP_ProxyList& proxies) 
131
132         assert(invariant());
133         
134         BP_Endpoint min = (*this)[first];
135         BP_Endpoint max = (*this)[last]; 
136         
137         erase(begin() + last);
138         erase(begin() + first);
139         --last;
140         
141         DT_Index i;
142         for (i = first; i != last; ++i) 
143         {
144                 --(*this)[i].getCount();
145                 (*this)[i].getIndex() = i;
146         } 
147         for (; i != size(); ++i) 
148         {
149                 (*this)[i].getIndex() = i;
150         } 
151         
152         range(min, max, first, last, proxies);
153         
154         assert(invariant());
155 }
156
157 void BP_EndpointList::move(DT_Index index, DT_Scalar pos, Uint32 type,  
158                                                    BP_Scene& scene, T_Overlap overlap)
159 {
160         assert(invariant());
161         
162         BP_Endpoint endpoint = (*this)[index];
163     DT_Scalar delta = pos - endpoint.getPos();
164         
165     if (delta != DT_Scalar(0.0)) 
166         {
167                 endpoint.setPos(pos, type);
168                 if (delta < DT_Scalar(0.0)) 
169                 {
170                         while (index != 0 && endpoint < (*this)[index - 1]) 
171                         {
172                                 (*this)[index] = (*this)[index - 1];
173                                 (*this)[index].getIndex() = index;
174                                 encounters((*this)[index], endpoint, scene, overlap);
175                                 --index;
176                         }
177                 }
178                 else 
179                 {
180                         DT_Index last = size() - 1;
181                         while (index != last && (*this)[index + 1] < endpoint) 
182                         {
183                                 (*this)[index] = (*this)[index + 1];
184                                 (*this)[index].getIndex() = index;
185                                 encounters(endpoint, (*this)[index], scene, overlap);
186                                 ++index;
187                         }
188                 }
189                 (*this)[index] = endpoint;
190                 (*this)[index].getIndex() = index;
191     }
192
193         assert(invariant());
194 }
195
196 void BP_EndpointList::encounters(const BP_Endpoint& a, const BP_Endpoint& b,
197                                                                  BP_Scene& scene, T_Overlap overlap)
198 {
199         assert(a.getProxy() != b.getProxy());
200         
201         if (a.getType() != b.getType()) 
202         {
203                 if (a.getType() == BP_Endpoint::MAXIMUM) 
204                 {
205                         if (overlap(*a.getProxy(), *b.getProxy())) 
206                         {
207                                 scene.callBeginOverlap(a.getProxy()->getObject(), 
208                                                                            b.getProxy()->getObject());
209                         }
210                         ++a.getCount();
211                         ++b.getCount();
212                 }
213                 else 
214                 {
215                         if (overlap(*a.getProxy(), *b.getProxy())) 
216                         {
217                                 scene.callEndOverlap(a.getProxy()->getObject(), 
218                                                                          b.getProxy()->getObject());
219                         }
220                         --a.getCount();
221                         --b.getCount();
222                 }
223         }
224         else 
225         {
226                 if (a.getType() == BP_Endpoint::MAXIMUM) 
227                 {
228                         --a.getCount();
229                         ++b.getCount();
230                 }
231                 else 
232                 {
233                         ++a.getCount();
234                         --b.getCount();
235                 }
236         }
237 }