Subversion Repository Public Repository

Divide-Framework

This repository has no backups
This repository's network speed is throttled to 100KB/sec

Diff Revisions 336 vs 337 for /trunk/Source Code/Libs/src/ReCast/DetourTileCache/Source/DetourTileCacheBuilder.cpp

Diff revisions: vs.
  @@ -26,809 +26,809 @@
26 26
27 27 template<class T> class dtFixedArray
28 28 {
29 - dtTileCacheAlloc* m_alloc;
30 - T* m_ptr;
31 - const int m_size;
32 - inline T* operator=(T* p);
33 - inline void operator=(dtFixedArray<T>& p);
34 - inline dtFixedArray();
29 + dtTileCacheAlloc* m_alloc;
30 + T* m_ptr;
31 + const int m_size;
32 + inline T* operator=(T* p);
33 + inline void operator=(dtFixedArray<T>& p);
34 + inline dtFixedArray();
35 35 public:
36 - inline dtFixedArray(dtTileCacheAlloc* a, const int s) : m_alloc(a), m_ptr((T*)a->alloc(sizeof(T)*s)), m_size(s) {}
37 - inline ~dtFixedArray() { if (m_alloc) m_alloc->free(m_ptr); }
38 - inline operator T*() { return m_ptr; }
39 - inline int size() const { return m_size; }
36 + inline dtFixedArray(dtTileCacheAlloc* a, const int s) : m_alloc(a), m_ptr((T*)a->alloc(sizeof(T)*s)), m_size(s) {}
37 + inline ~dtFixedArray() { if (m_alloc) m_alloc->free(m_ptr); }
38 + inline operator T*() { return m_ptr; }
39 + inline int size() const { return m_size; }
40 40 };
41 41
42 42 inline int getDirOffsetX(int dir)
43 43 {
44 - const int offset[4] = { -1, 0, 1, 0, };
45 - return offset[dir&0x03];
44 + const int offset[4] = { -1, 0, 1, 0, };
45 + return offset[dir&0x03];
46 46 }
47 47
48 48 inline int getDirOffsetY(int dir)
49 49 {
50 - const int offset[4] = { 0, 1, 0, -1 };
51 - return offset[dir&0x03];
50 + const int offset[4] = { 0, 1, 0, -1 };
51 + return offset[dir&0x03];
52 52 }
53 53
54 - static const int MAX_VERTS_PER_POLY = 6; // TODO: use the DT_VERTS_PER_POLYGON
55 - static const int MAX_REM_EDGES = 48; // TODO: make this an expression.
54 + static const int MAX_VERTS_PER_POLY = 6; // TODO: use the DT_VERTS_PER_POLYGON
55 + static const int MAX_REM_EDGES = 48; // TODO: make this an expression.
56 56
57 57
58 58
59 59 dtTileCacheContourSet* dtAllocTileCacheContourSet(dtTileCacheAlloc* alloc)
60 60 {
61 - dtAssert(alloc);
61 + dtAssert(alloc);
62 62
63 - dtTileCacheContourSet* cset = (dtTileCacheContourSet*)alloc->alloc(sizeof(dtTileCacheContourSet));
64 - memset(cset, 0, sizeof(dtTileCacheContourSet));
65 - return cset;
63 + dtTileCacheContourSet* cset = (dtTileCacheContourSet*)alloc->alloc(sizeof(dtTileCacheContourSet));
64 + memset(cset, 0, sizeof(dtTileCacheContourSet));
65 + return cset;
66 66 }
67 67
68 68 void dtFreeTileCacheContourSet(dtTileCacheAlloc* alloc, dtTileCacheContourSet* cset)
69 69 {
70 - dtAssert(alloc);
70 + dtAssert(alloc);
71 71
72 - if (!cset) return;
73 - for (int i = 0; i < cset->nconts; ++i)
74 - alloc->free(cset->conts[i].verts);
75 - alloc->free(cset->conts);
76 - alloc->free(cset);
72 + if (!cset) return;
73 + for (int i = 0; i < cset->nconts; ++i)
74 + alloc->free(cset->conts[i].verts);
75 + alloc->free(cset->conts);
76 + alloc->free(cset);
77 77 }
78 78
79 79 dtTileCachePolyMesh* dtAllocTileCachePolyMesh(dtTileCacheAlloc* alloc)
80 80 {
81 - dtAssert(alloc);
81 + dtAssert(alloc);
82 82
83 - dtTileCachePolyMesh* lmesh = (dtTileCachePolyMesh*)alloc->alloc(sizeof(dtTileCachePolyMesh));
84 - memset(lmesh, 0, sizeof(dtTileCachePolyMesh));
85 - return lmesh;
83 + dtTileCachePolyMesh* lmesh = (dtTileCachePolyMesh*)alloc->alloc(sizeof(dtTileCachePolyMesh));
84 + memset(lmesh, 0, sizeof(dtTileCachePolyMesh));
85 + return lmesh;
86 86 }
87 87
88 88 void dtFreeTileCachePolyMesh(dtTileCacheAlloc* alloc, dtTileCachePolyMesh* lmesh)
89 89 {
90 - dtAssert(alloc);
91 -
92 - if (!lmesh) return;
93 - alloc->free(lmesh->verts);
94 - alloc->free(lmesh->polys);
95 - alloc->free(lmesh->flags);
96 - alloc->free(lmesh->areas);
97 - alloc->free(lmesh);
90 + dtAssert(alloc);
91 +
92 + if (!lmesh) return;
93 + alloc->free(lmesh->verts);
94 + alloc->free(lmesh->polys);
95 + alloc->free(lmesh->flags);
96 + alloc->free(lmesh->areas);
97 + alloc->free(lmesh);
98 98 }
99 99
100 100
101 101
102 102 struct dtLayerSweepSpan
103 103 {
104 - unsigned short ns; // number samples
105 - unsigned char id; // region id
106 - unsigned char nei; // neighbour id
104 + unsigned short ns; // number samples
105 + unsigned char id; // region id
106 + unsigned char nei; // neighbour id
107 107 };
108 108
109 109 static const int DT_LAYER_MAX_NEIS = 16;
110 110
111 111 struct dtLayerMonotoneRegion
112 112 {
113 - int area;
114 - unsigned char neis[DT_LAYER_MAX_NEIS];
115 - unsigned char nneis;
116 - unsigned char regId;
117 - unsigned char areaId;
113 + int area;
114 + unsigned char neis[DT_LAYER_MAX_NEIS];
115 + unsigned char nneis;
116 + unsigned char regId;
117 + unsigned char areaId;
118 118 };
119 119
120 120 struct dtTempContour
121 121 {
122 - inline dtTempContour(unsigned char* vbuf, const int nvbuf,
123 - unsigned short* pbuf, const int npbuf) :
124 - verts(vbuf), nverts(0), cverts(nvbuf),
125 - poly(pbuf), npoly(0), cpoly(npbuf)
126 - {
127 - }
128 - unsigned char* verts;
129 - int nverts;
130 - int cverts;
131 - unsigned short* poly;
132 - int npoly;
133 - int cpoly;
122 + inline dtTempContour(unsigned char* vbuf, const int nvbuf,
123 + unsigned short* pbuf, const int npbuf) :
124 + verts(vbuf), nverts(0), cverts(nvbuf),
125 + poly(pbuf), npoly(0), cpoly(npbuf)
126 + {
127 + }
128 + unsigned char* verts;
129 + int nverts;
130 + int cverts;
131 + unsigned short* poly;
132 + int npoly;
133 + int cpoly;
134 134 };
135 135
136 136
137 137
138 138
139 139 inline bool overlapRangeExl(const unsigned short amin, const unsigned short amax,
140 - const unsigned short bmin, const unsigned short bmax)
140 + const unsigned short bmin, const unsigned short bmax)
141 141 {
142 - return (amin >= bmax || amax <= bmin) ? false : true;
142 + return (amin >= bmax || amax <= bmin) ? false : true;
143 143 }
144 144
145 145 static void addUniqueLast(unsigned char* a, unsigned char& an, unsigned char v)
146 146 {
147 - const int n = (int)an;
148 - if (n > 0 && a[n-1] == v) return;
149 - a[an] = v;
150 - an++;
147 + const int n = (int)an;
148 + if (n > 0 && a[n-1] == v) return;
149 + a[an] = v;
150 + an++;
151 151 }
152 152
153 153 inline bool isConnected(const dtTileCacheLayer& layer,
154 - const int ia, const int ib, const int walkableClimb)
154 + const int ia, const int ib, const int walkableClimb)
155 155 {
156 - if (layer.areas[ia] != layer.areas[ib]) return false;
157 - if (dtAbs((int)layer.heights[ia] - (int)layer.heights[ib]) > walkableClimb) return false;
158 - return true;
156 + if (layer.areas[ia] != layer.areas[ib]) return false;
157 + if (dtAbs((int)layer.heights[ia] - (int)layer.heights[ib]) > walkableClimb) return false;
158 + return true;
159 159 }
160 160
161 161 static bool canMerge(unsigned char oldRegId, unsigned char newRegId, const dtLayerMonotoneRegion* regs, const int nregs)
162 162 {
163 - int count = 0;
164 - for (int i = 0; i < nregs; ++i)
165 - {
166 - const dtLayerMonotoneRegion& reg = regs[i];
167 - if (reg.regId != oldRegId) continue;
168 - const int nnei = (int)reg.nneis;
169 - for (int j = 0; j < nnei; ++j)
170 - {
171 - if (regs[reg.neis[j]].regId == newRegId)
172 - count++;
173 - }
174 - }
175 - return count == 1;
163 + int count = 0;
164 + for (int i = 0; i < nregs; ++i)
165 + {
166 + const dtLayerMonotoneRegion& reg = regs[i];
167 + if (reg.regId != oldRegId) continue;
168 + const int nnei = (int)reg.nneis;
169 + for (int j = 0; j < nnei; ++j)
170 + {
171 + if (regs[reg.neis[j]].regId == newRegId)
172 + count++;
173 + }
174 + }
175 + return count == 1;
176 176 }
177 177
178 178
179 179 dtStatus dtBuildTileCacheRegions(dtTileCacheAlloc* alloc,
180 - dtTileCacheLayer& layer,
181 - const int walkableClimb)
180 + dtTileCacheLayer& layer,
181 + const int walkableClimb)
182 182 {
183 - dtAssert(alloc);
184 -
185 - const int w = (int)layer.header->width;
186 - const int h = (int)layer.header->height;
187 -
188 - memset(layer.regs,0xff,sizeof(unsigned char)*w*h);
189 -
190 - const int nsweeps = w;
191 - dtFixedArray<dtLayerSweepSpan> sweeps(alloc, nsweeps);
192 - if (!sweeps)
193 - return DT_FAILURE | DT_OUT_OF_MEMORY;
194 - memset(sweeps,0,sizeof(dtLayerSweepSpan)*nsweeps);
195 -
196 - // Partition walkable area into monotone regions.
197 - unsigned char prevCount[256];
198 - unsigned char regId = 0;
199 -
200 - for (int y = 0; y < h; ++y)
201 - {
202 - if (regId > 0)
203 - memset(prevCount,0,sizeof(unsigned char)*regId);
204 - unsigned char sweepId = 0;
205 -
206 - for (int x = 0; x < w; ++x)
207 - {
208 - const int idx = x + y*w;
209 - if (layer.areas[idx] == DT_TILECACHE_NULL_AREA) continue;
210 -
211 - unsigned char sid = 0xff;
212 -
213 - // -x
214 - const int xidx = (x-1)+y*w;
215 - if (x > 0 && isConnected(layer, idx, xidx, walkableClimb))
216 - {
217 - if (layer.regs[xidx] != 0xff)
218 - sid = layer.regs[xidx];
219 - }
220 -
221 - if (sid == 0xff)
222 - {
223 - sid = sweepId++;
224 - sweeps[sid].nei = 0xff;
225 - sweeps[sid].ns = 0;
226 - }
227 -
228 - // -y
229 - const int yidx = x+(y-1)*w;
230 - if (y > 0 && isConnected(layer, idx, yidx, walkableClimb))
231 - {
232 - const unsigned char nr = layer.regs[yidx];
233 - if (nr != 0xff)
234 - {
235 - // Set neighbour when first valid neighbour is encoutered.
236 - if (sweeps[sid].ns == 0)
237 - sweeps[sid].nei = nr;
238 -
239 - if (sweeps[sid].nei == nr)
240 - {
241 - // Update existing neighbour
242 - sweeps[sid].ns++;
243 - prevCount[nr]++;
244 - }
245 - else
246 - {
247 - // This is hit if there is nore than one neighbour.
248 - // Invalidate the neighbour.
249 - sweeps[sid].nei = 0xff;
250 - }
251 - }
252 - }
253 -
254 - layer.regs[idx] = sid;
255 - }
256 -
257 - // Create unique ID.
258 - for (int i = 0; i < sweepId; ++i)
259 - {
260 - // If the neighbour is set and there is only one continuous connection to it,
261 - // the sweep will be merged with the previous one, else new region is created.
262 - if (sweeps[i].nei != 0xff && (unsigned short)prevCount[sweeps[i].nei] == sweeps[i].ns)
263 - {
264 - sweeps[i].id = sweeps[i].nei;
265 - }
266 - else
267 - {
268 - if (regId == 255)
269 - {
270 - // Region ID's overflow.
271 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
272 - }
273 - sweeps[i].id = regId++;
274 - }
275 - }
276 -
277 - // Remap local sweep ids to region ids.
278 - for (int x = 0; x < w; ++x)
279 - {
280 - const int idx = x+y*w;
281 - if (layer.regs[idx] != 0xff)
282 - layer.regs[idx] = sweeps[layer.regs[idx]].id;
283 - }
284 - }
285 -
286 - // Allocate and init layer regions.
287 - const int nregs = (int)regId;
288 - dtFixedArray<dtLayerMonotoneRegion> regs(alloc, nregs);
289 - if (!regs)
290 - return DT_FAILURE | DT_OUT_OF_MEMORY;
291 -
292 - memset(regs, 0, sizeof(dtLayerMonotoneRegion)*nregs);
293 - for (int i = 0; i < nregs; ++i)
294 - regs[i].regId = 0xff;
295 -
296 - // Find region neighbours.
297 - for (int y = 0; y < h; ++y)
298 - {
299 - for (int x = 0; x < w; ++x)
300 - {
301 - const int idx = x+y*w;
302 - const unsigned char ri = layer.regs[idx];
303 - if (ri == 0xff)
304 - continue;
305 -
306 - // Update area.
307 - regs[ri].area++;
308 - regs[ri].areaId = layer.areas[idx];
309 -
310 - // Update neighbours
311 - const int ymi = x+(y-1)*w;
312 - if (y > 0 && isConnected(layer, idx, ymi, walkableClimb))
313 - {
314 - const unsigned char rai = layer.regs[ymi];
315 - if (rai != 0xff && rai != ri)
316 - {
317 - addUniqueLast(regs[ri].neis, regs[ri].nneis, rai);
318 - addUniqueLast(regs[rai].neis, regs[rai].nneis, ri);
319 - }
320 - }
321 - }
322 - }
323 -
324 - for (int i = 0; i < nregs; ++i)
325 - regs[i].regId = (unsigned char)i;
326 -
327 - for (int i = 0; i < nregs; ++i)
328 - {
329 - dtLayerMonotoneRegion& reg = regs[i];
330 -
331 - int merge = -1;
332 - int mergea = 0;
333 - for (int j = 0; j < (int)reg.nneis; ++j)
334 - {
335 - const unsigned char nei = reg.neis[j];
336 - dtLayerMonotoneRegion& regn = regs[nei];
337 - if (reg.regId == regn.regId)
338 - continue;
339 - if (reg.areaId != regn.areaId)
340 - continue;
341 - if (regn.area > mergea)
342 - {
343 - if (canMerge(reg.regId, regn.regId, regs, nregs))
344 - {
345 - mergea = regn.area;
346 - merge = (int)nei;
347 - }
348 - }
349 - }
350 - if (merge != -1)
351 - {
352 - const unsigned char oldId = reg.regId;
353 - const unsigned char newId = regs[merge].regId;
354 - for (int j = 0; j < nregs; ++j)
355 - if (regs[j].regId == oldId)
356 - regs[j].regId = newId;
357 - }
358 - }
359 -
360 - // Compact ids.
361 - unsigned char remap[256];
362 - memset(remap, 0, 256);
363 - // Find number of unique regions.
364 - regId = 0;
365 - for (int i = 0; i < nregs; ++i)
366 - remap[regs[i].regId] = 1;
367 - for (int i = 0; i < 256; ++i)
368 - if (remap[i])
369 - remap[i] = regId++;
370 - // Remap ids.
371 - for (int i = 0; i < nregs; ++i)
372 - regs[i].regId = remap[regs[i].regId];
373 -
374 - layer.regCount = regId;
375 -
376 - for (int i = 0; i < w*h; ++i)
377 - {
378 - if (layer.regs[i] != 0xff)
379 - layer.regs[i] = regs[layer.regs[i]].regId;
380 - }
381 -
382 - return DT_SUCCESS;
183 + dtAssert(alloc);
184 +
185 + const int w = (int)layer.header->width;
186 + const int h = (int)layer.header->height;
187 +
188 + memset(layer.regs,0xff,sizeof(unsigned char)*w*h);
189 +
190 + const int nsweeps = w;
191 + dtFixedArray<dtLayerSweepSpan> sweeps(alloc, nsweeps);
192 + if (!sweeps)
193 + return DT_FAILURE | DT_OUT_OF_MEMORY;
194 + memset(sweeps,0,sizeof(dtLayerSweepSpan)*nsweeps);
195 +
196 + // Partition walkable area into monotone regions.
197 + unsigned char prevCount[256];
198 + unsigned char regId = 0;
199 +
200 + for (int y = 0; y < h; ++y)
201 + {
202 + if (regId > 0)
203 + memset(prevCount,0,sizeof(unsigned char)*regId);
204 + unsigned char sweepId = 0;
205 +
206 + for (int x = 0; x < w; ++x)
207 + {
208 + const int idx = x + y*w;
209 + if (layer.areas[idx] == DT_TILECACHE_NULL_AREA) continue;
210 +
211 + unsigned char sid = 0xff;
212 +
213 + // -x
214 + const int xidx = (x-1)+y*w;
215 + if (x > 0 && isConnected(layer, idx, xidx, walkableClimb))
216 + {
217 + if (layer.regs[xidx] != 0xff)
218 + sid = layer.regs[xidx];
219 + }
220 +
221 + if (sid == 0xff)
222 + {
223 + sid = sweepId++;
224 + sweeps[sid].nei = 0xff;
225 + sweeps[sid].ns = 0;
226 + }
227 +
228 + // -y
229 + const int yidx = x+(y-1)*w;
230 + if (y > 0 && isConnected(layer, idx, yidx, walkableClimb))
231 + {
232 + const unsigned char nr = layer.regs[yidx];
233 + if (nr != 0xff)
234 + {
235 + // Set neighbour when first valid neighbour is encoutered.
236 + if (sweeps[sid].ns == 0)
237 + sweeps[sid].nei = nr;
238 +
239 + if (sweeps[sid].nei == nr)
240 + {
241 + // Update existing neighbour
242 + sweeps[sid].ns++;
243 + prevCount[nr]++;
244 + }
245 + else
246 + {
247 + // This is hit if there is nore than one neighbour.
248 + // Invalidate the neighbour.
249 + sweeps[sid].nei = 0xff;
250 + }
251 + }
252 + }
253 +
254 + layer.regs[idx] = sid;
255 + }
256 +
257 + // Create unique ID.
258 + for (int i = 0; i < sweepId; ++i)
259 + {
260 + // If the neighbour is set and there is only one continuous connection to it,
261 + // the sweep will be merged with the previous one, else new region is created.
262 + if (sweeps[i].nei != 0xff && (unsigned short)prevCount[sweeps[i].nei] == sweeps[i].ns)
263 + {
264 + sweeps[i].id = sweeps[i].nei;
265 + }
266 + else
267 + {
268 + if (regId == 255)
269 + {
270 + // Region ID's overflow.
271 + return DT_FAILURE | DT_BUFFER_TOO_SMALL;
272 + }
273 + sweeps[i].id = regId++;
274 + }
275 + }
276 +
277 + // Remap local sweep ids to region ids.
278 + for (int x = 0; x < w; ++x)
279 + {
280 + const int idx = x+y*w;
281 + if (layer.regs[idx] != 0xff)
282 + layer.regs[idx] = sweeps[layer.regs[idx]].id;
283 + }
284 + }
285 +
286 + // Allocate and init layer regions.
287 + const int nregs = (int)regId;
288 + dtFixedArray<dtLayerMonotoneRegion> regs(alloc, nregs);
289 + if (!regs)
290 + return DT_FAILURE | DT_OUT_OF_MEMORY;
291 +
292 + memset(regs, 0, sizeof(dtLayerMonotoneRegion)*nregs);
293 + for (int i = 0; i < nregs; ++i)
294 + regs[i].regId = 0xff;
295 +
296 + // Find region neighbours.
297 + for (int y = 0; y < h; ++y)
298 + {
299 + for (int x = 0; x < w; ++x)
300 + {
301 + const int idx = x+y*w;
302 + const unsigned char ri = layer.regs[idx];
303 + if (ri == 0xff)
304 + continue;
305 +
306 + // Update area.
307 + regs[ri].area++;
308 + regs[ri].areaId = layer.areas[idx];
309 +
310 + // Update neighbours
311 + const int ymi = x+(y-1)*w;
312 + if (y > 0 && isConnected(layer, idx, ymi, walkableClimb))
313 + {
314 + const unsigned char rai = layer.regs[ymi];
315 + if (rai != 0xff && rai != ri)
316 + {
317 + addUniqueLast(regs[ri].neis, regs[ri].nneis, rai);
318 + addUniqueLast(regs[rai].neis, regs[rai].nneis, ri);
319 + }
320 + }
321 + }
322 + }
323 +
324 + for (int i = 0; i < nregs; ++i)
325 + regs[i].regId = (unsigned char)i;
326 +
327 + for (int i = 0; i < nregs; ++i)
328 + {
329 + dtLayerMonotoneRegion& reg = regs[i];
330 +
331 + int merge = -1;
332 + int mergea = 0;
333 + for (int j = 0; j < (int)reg.nneis; ++j)
334 + {
335 + const unsigned char nei = reg.neis[j];
336 + dtLayerMonotoneRegion& regn = regs[nei];
337 + if (reg.regId == regn.regId)
338 + continue;
339 + if (reg.areaId != regn.areaId)
340 + continue;
341 + if (regn.area > mergea)
342 + {
343 + if (canMerge(reg.regId, regn.regId, regs, nregs))
344 + {
345 + mergea = regn.area;
346 + merge = (int)nei;
347 + }
348 + }
349 + }
350 + if (merge != -1)
351 + {
352 + const unsigned char oldId = reg.regId;
353 + const unsigned char newId = regs[merge].regId;
354 + for (int j = 0; j < nregs; ++j)
355 + if (regs[j].regId == oldId)
356 + regs[j].regId = newId;
357 + }
358 + }
359 +
360 + // Compact ids.
361 + unsigned char remap[256];
362 + memset(remap, 0, 256);
363 + // Find number of unique regions.
364 + regId = 0;
365 + for (int i = 0; i < nregs; ++i)
366 + remap[regs[i].regId] = 1;
367 + for (int i = 0; i < 256; ++i)
368 + if (remap[i])
369 + remap[i] = regId++;
370 + // Remap ids.
371 + for (int i = 0; i < nregs; ++i)
372 + regs[i].regId = remap[regs[i].regId];
373 +
374 + layer.regCount = regId;
375 +
376 + for (int i = 0; i < w*h; ++i)
377 + {
378 + if (layer.regs[i] != 0xff)
379 + layer.regs[i] = regs[layer.regs[i]].regId;
380 + }
381 +
382 + return DT_SUCCESS;
383 383 }
384 384
385 385
386 386
387 387 static bool appendVertex(dtTempContour& cont, const int x, const int y, const int z, const int r)
388 388 {
389 - // Try to merge with existing segments.
390 - if (cont.nverts > 1)
391 - {
392 - unsigned char* pa = &cont.verts[(cont.nverts-2)*4];
393 - unsigned char* pb = &cont.verts[(cont.nverts-1)*4];
394 - if ((int)pb[3] == r)
395 - {
396 - if (pa[0] == pb[0] && (int)pb[0] == x)
397 - {
398 - // The verts are aligned aling x-axis, update z.
399 - pb[1] = (unsigned char)y;
400 - pb[2] = (unsigned char)z;
401 - return true;
402 - }
403 - else if (pa[2] == pb[2] && (int)pb[2] == z)
404 - {
405 - // The verts are aligned aling z-axis, update x.
406 - pb[0] = (unsigned char)x;
407 - pb[1] = (unsigned char)y;
408 - return true;
409 - }
410 - }
411 - }
412 -
413 - // Add new point.
414 - if (cont.nverts+1 > cont.cverts)
415 - return false;
416 -
417 - unsigned char* v = &cont.verts[cont.nverts*4];
418 - v[0] = (unsigned char)x;
419 - v[1] = (unsigned char)y;
420 - v[2] = (unsigned char)z;
421 - v[3] = (unsigned char)r;
422 - cont.nverts++;
423 -
424 - return true;
389 + // Try to merge with existing segments.
390 + if (cont.nverts > 1)
391 + {
392 + unsigned char* pa = &cont.verts[(cont.nverts-2)*4];
393 + unsigned char* pb = &cont.verts[(cont.nverts-1)*4];
394 + if ((int)pb[3] == r)
395 + {
396 + if (pa[0] == pb[0] && (int)pb[0] == x)
397 + {
398 + // The verts are aligned aling x-axis, update z.
399 + pb[1] = (unsigned char)y;
400 + pb[2] = (unsigned char)z;
401 + return true;
402 + }
403 + else if (pa[2] == pb[2] && (int)pb[2] == z)
404 + {
405 + // The verts are aligned aling z-axis, update x.
406 + pb[0] = (unsigned char)x;
407 + pb[1] = (unsigned char)y;
408 + return true;
409 + }
410 + }
411 + }
412 +
413 + // Add new point.
414 + if (cont.nverts+1 > cont.cverts)
415 + return false;
416 +
417 + unsigned char* v = &cont.verts[cont.nverts*4];
418 + v[0] = (unsigned char)x;
419 + v[1] = (unsigned char)y;
420 + v[2] = (unsigned char)z;
421 + v[3] = (unsigned char)r;
422 + cont.nverts++;
423 +
424 + return true;
425 425 }
426 426
427 427
428 428 static unsigned char getNeighbourReg(dtTileCacheLayer& layer,
429 - const int ax, const int ay, const int dir)
429 + const int ax, const int ay, const int dir)
430 430 {
431 - const int w = (int)layer.header->width;
432 - const int ia = ax + ay*w;
433 -
434 - const unsigned char con = layer.cons[ia] & 0xf;
435 - const unsigned char portal = layer.cons[ia] >> 4;
436 - const unsigned char mask = (unsigned char)(1<<dir);
437 -
438 - if ((con & mask) == 0)
439 - {
440 - // No connection, return portal or hard edge.
441 - if (portal & mask)
442 - return 0xf8 + (unsigned char)dir;
443 - return 0xff;
444 - }
445 -
446 - const int bx = ax + getDirOffsetX(dir);
447 - const int by = ay + getDirOffsetY(dir);
448 - const int ib = bx + by*w;
449 -
450 - return layer.regs[ib];
431 + const int w = (int)layer.header->width;
432 + const int ia = ax + ay*w;
433 +
434 + const unsigned char con = layer.cons[ia] & 0xf;
435 + const unsigned char portal = layer.cons[ia] >> 4;
436 + const unsigned char mask = (unsigned char)(1<<dir);
437 +
438 + if ((con & mask) == 0)
439 + {
440 + // No connection, return portal or hard edge.
441 + if (portal & mask)
442 + return 0xf8 + (unsigned char)dir;
443 + return 0xff;
444 + }
445 +
446 + const int bx = ax + getDirOffsetX(dir);
447 + const int by = ay + getDirOffsetY(dir);
448 + const int ib = bx + by*w;
449 +
450 + return layer.regs[ib];
451 451 }
452 452
453 453 static bool walkContour(dtTileCacheLayer& layer, int x, int y, dtTempContour& cont)
454 454 {
455 - const int w = (int)layer.header->width;
456 - const int h = (int)layer.header->height;
457 -
458 - cont.nverts = 0;
459 -
460 - int startX = x;
461 - int startY = y;
462 - int startDir = -1;
463 -
464 - for (int i = 0; i < 4; ++i)
465 - {
466 - const int dir = (i+3)&3;
467 - unsigned char rn = getNeighbourReg(layer, x, y, dir);
468 - if (rn != layer.regs[x+y*w])
469 - {
470 - startDir = dir;
471 - break;
472 - }
473 - }
474 - if (startDir == -1)
475 - return true;
476 -
477 - int dir = startDir;
478 - const int maxIter = w*h;
479 -
480 - int iter = 0;
481 - while (iter < maxIter)
482 - {
483 - unsigned char rn = getNeighbourReg(layer, x, y, dir);
484 -
485 - int nx = x;
486 - int ny = y;
487 - int ndir = dir;
488 -
489 - if (rn != layer.regs[x+y*w])
490 - {
491 - // Solid edge.
492 - int px = x;
493 - int pz = y;
494 - switch(dir)
495 - {
496 - case 0: pz++; break;
497 - case 1: px++; pz++; break;
498 - case 2: px++; break;
499 - }
500 -
501 - // Try to merge with previous vertex.
502 - if (!appendVertex(cont, px, (int)layer.heights[x+y*w], pz,rn))
503 - return false;
504 -
505 - ndir = (dir+1) & 0x3; // Rotate CW
506 - }
507 - else
508 - {
509 - // Move to next.
510 - nx = x + getDirOffsetX(dir);
511 - ny = y + getDirOffsetY(dir);
512 - ndir = (dir+3) & 0x3; // Rotate CCW
513 - }
514 -
515 - if (iter > 0 && x == startX && y == startY && dir == startDir)
516 - break;
517 -
518 - x = nx;
519 - y = ny;
520 - dir = ndir;
521 -
522 - iter++;
523 - }
524 -
525 - // Remove last vertex if it is duplicate of the first one.
526 - unsigned char* pa = &cont.verts[(cont.nverts-1)*4];
527 - unsigned char* pb = &cont.verts[0];
528 - if (pa[0] == pb[0] && pa[2] == pb[2])
529 - cont.nverts--;
530 -
531 - return true;
532 - }
455 + const int w = (int)layer.header->width;
456 + const int h = (int)layer.header->height;
457 +
458 + cont.nverts = 0;
459 +
460 + int startX = x;
461 + int startY = y;
462 + int startDir = -1;
463 +
464 + for (int i = 0; i < 4; ++i)
465 + {
466 + const int dir = (i+3)&3;
467 + unsigned char rn = getNeighbourReg(layer, x, y, dir);
468 + if (rn != layer.regs[x+y*w])
469 + {
470 + startDir = dir;
471 + break;
472 + }
473 + }
474 + if (startDir == -1)
475 + return true;
476 +
477 + int dir = startDir;
478 + const int maxIter = w*h;
479 +
480 + int iter = 0;
481 + while (iter < maxIter)
482 + {
483 + unsigned char rn = getNeighbourReg(layer, x, y, dir);
484 +
485 + int nx = x;
486 + int ny = y;
487 + int ndir = dir;
488 +
489 + if (rn != layer.regs[x+y*w])
490 + {
491 + // Solid edge.
492 + int px = x;
493 + int pz = y;
494 + switch(dir)
495 + {
496 + case 0: pz++; break;
497 + case 1: px++; pz++; break;
498 + case 2: px++; break;
499 + }
500 +
501 + // Try to merge with previous vertex.
502 + if (!appendVertex(cont, px, (int)layer.heights[x+y*w], pz,rn))
503 + return false;
504 +
505 + ndir = (dir+1) & 0x3; // Rotate CW
506 + }
507 + else
508 + {
509 + // Move to next.
510 + nx = x + getDirOffsetX(dir);
511 + ny = y + getDirOffsetY(dir);
512 + ndir = (dir+3) & 0x3; // Rotate CCW
513 + }
514 +
515 + if (iter > 0 && x == startX && y == startY && dir == startDir)
516 + break;
517 +
518 + x = nx;
519 + y = ny;
520 + dir = ndir;
521 +
522 + iter++;
523 + }
524 +
525 + // Remove last vertex if it is duplicate of the first one.
526 + unsigned char* pa = &cont.verts[(cont.nverts-1)*4];
527 + unsigned char* pb = &cont.verts[0];
528 + if (pa[0] == pb[0] && pa[2] == pb[2])
529 + cont.nverts--;
530 +
531 + return true;
532 + }
533 533
534 534
535 535 static float distancePtSeg(const int x, const int z,
536 - const int px, const int pz,
537 - const int qx, const int qz)
536 + const int px, const int pz,
537 + const int qx, const int qz)
538 538 {
539 - float pqx = (float)(qx - px);
540 - float pqz = (float)(qz - pz);
541 - float dx = (float)(x - px);
542 - float dz = (float)(z - pz);
543 - float d = pqx*pqx + pqz*pqz;
544 - float t = pqx*dx + pqz*dz;
545 - if (d > 0)
546 - t /= d;
547 - if (t < 0)
548 - t = 0;
549 - else if (t > 1)
550 - t = 1;
551 -
552 - dx = px + t*pqx - x;
553 - dz = pz + t*pqz - z;
554 -
555 - return dx*dx + dz*dz;
539 + float pqx = (float)(qx - px);
540 + float pqz = (float)(qz - pz);
541 + float dx = (float)(x - px);
542 + float dz = (float)(z - pz);
543 + float d = pqx*pqx + pqz*pqz;
544 + float t = pqx*dx + pqz*dz;
545 + if (d > 0)
546 + t /= d;
547 + if (t < 0)
548 + t = 0;
549 + else if (t > 1)
550 + t = 1;
551 +
552 + dx = px + t*pqx - x;
553 + dz = pz + t*pqz - z;
554 +
555 + return dx*dx + dz*dz;
556 556 }
557 557
558 558 static void simplifyContour(dtTempContour& cont, const float maxError)
559 559 {
560 - cont.npoly = 0;
561 -
562 - for (int i = 0; i < cont.nverts; ++i)
563 - {
564 - int j = (i+1) % cont.nverts;
565 - // Check for start of a wall segment.
566 - unsigned char ra = cont.verts[j*4+3];
567 - unsigned char rb = cont.verts[i*4+3];
568 - if (ra != rb)
569 - cont.poly[cont.npoly++] = (unsigned short)i;
570 - }
571 - if (cont.npoly < 2)
572 - {
573 - // If there is no transitions at all,
574 - // create some initial points for the simplification process.
575 - // Find lower-left and upper-right vertices of the contour.
576 - int llx = cont.verts[0];
577 - int llz = cont.verts[2];
578 - int lli = 0;
579 - int urx = cont.verts[0];
580 - int urz = cont.verts[2];
581 - int uri = 0;
582 - for (int i = 1; i < cont.nverts; ++i)
583 - {
584 - int x = cont.verts[i*4+0];
585 - int z = cont.verts[i*4+2];
586 - if (x < llx || (x == llx && z < llz))
587 - {
588 - llx = x;
589 - llz = z;
590 - lli = i;
591 - }
592 - if (x > urx || (x == urx && z > urz))
593 - {
594 - urx = x;
595 - urz = z;
596 - uri = i;
597 - }
598 - }
599 - cont.npoly = 0;
600 - cont.poly[cont.npoly++] = (unsigned short)lli;
601 - cont.poly[cont.npoly++] = (unsigned short)uri;
602 - }
603 -
604 - // Add points until all raw points are within
605 - // error tolerance to the simplified shape.
606 - for (int i = 0; i < cont.npoly; )
607 - {
608 - int ii = (i+1) % cont.npoly;
609 -
610 - const int ai = (int)cont.poly[i];
611 - const int ax = (int)cont.verts[ai*4+0];
612 - const int az = (int)cont.verts[ai*4+2];
613 -
614 - const int bi = (int)cont.poly[ii];
615 - const int bx = (int)cont.verts[bi*4+0];
616 - const int bz = (int)cont.verts[bi*4+2];
617 -
618 - // Find maximum deviation from the segment.
619 - float maxd = 0;
620 - int maxi = -1;
621 - int ci, cinc, endi;
622 -
623 - // Traverse the segment in lexilogical order so that the
624 - // max deviation is calculated similarly when traversing
625 - // opposite segments.
626 - if (bx > ax || (bx == ax && bz > az))
627 - {
628 - cinc = 1;
629 - ci = (ai+cinc) % cont.nverts;
630 - endi = bi;
631 - }
632 - else
633 - {
634 - cinc = cont.nverts-1;
635 - ci = (bi+cinc) % cont.nverts;
636 - endi = ai;
637 - }
638 -
639 - // Tessellate only outer edges or edges between areas.
640 - while (ci != endi)
641 - {
642 - float d = distancePtSeg(cont.verts[ci*4+0], cont.verts[ci*4+2], ax, az, bx, bz);
643 - if (d > maxd)
644 - {
645 - maxd = d;
646 - maxi = ci;
647 - }
648 - ci = (ci+cinc) % cont.nverts;
649 - }
650 -
651 -
652 - // If the max deviation is larger than accepted error,
653 - // add new point, else continue to next segment.
654 - if (maxi != -1 && maxd > (maxError*maxError))
655 - {
656 - cont.npoly++;
657 - for (int j = cont.npoly-1; j > i; --j)
658 - cont.poly[j] = cont.poly[j-1];
659 - cont.poly[i+1] = (unsigned short)maxi;
660 - }
661 - else
662 - {
663 - ++i;
664 - }
665 - }
666 -
667 - // Remap vertices
668 - int start = 0;
669 - for (int i = 1; i < cont.npoly; ++i)
670 - if (cont.poly[i] < cont.poly[start])
671 - start = i;
672 -
673 - cont.nverts = 0;
674 - for (int i = 0; i < cont.npoly; ++i)
675 - {
676 - const int j = (start+i) % cont.npoly;
677 - unsigned char* src = &cont.verts[cont.poly[j]*4];
678 - unsigned char* dst = &cont.verts[cont.nverts*4];
679 - dst[0] = src[0];
680 - dst[1] = src[1];
681 - dst[2] = src[2];
682 - dst[3] = src[3];
683 - cont.nverts++;
684 - }
560 + cont.npoly = 0;
561 +
562 + for (int i = 0; i < cont.nverts; ++i)
563 + {
564 + int j = (i+1) % cont.nverts;
565 + // Check for start of a wall segment.
566 + unsigned char ra = cont.verts[j*4+3];
567 + unsigned char rb = cont.verts[i*4+3];
568 + if (ra != rb)
569 + cont.poly[cont.npoly++] = (unsigned short)i;
570 + }
571 + if (cont.npoly < 2)
572 + {
573 + // If there is no transitions at all,
574 + // create some initial points for the simplification process.
575 + // Find lower-left and upper-right vertices of the contour.
576 + int llx = cont.verts[0];
577 + int llz = cont.verts[2];
578 + int lli = 0;
579 + int urx = cont.verts[0];
580 + int urz = cont.verts[2];
581 + int uri = 0;
582 + for (int i = 1; i < cont.nverts; ++i)
583 + {
584 + int x = cont.verts[i*4+0];
585 + int z = cont.verts[i*4+2];
586 + if (x < llx || (x == llx && z < llz))
587 + {
588 + llx = x;
589 + llz = z;
590 + lli = i;
591 + }
592 + if (x > urx || (x == urx && z > urz))
593 + {
594 + urx = x;
595 + urz = z;
596 + uri = i;
597 + }
598 + }
599 + cont.npoly = 0;
600 + cont.poly[cont.npoly++] = (unsigned short)lli;
601 + cont.poly[cont.npoly++] = (unsigned short)uri;
602 + }
603 +
604 + // Add points until all raw points are within
605 + // error tolerance to the simplified shape.
606 + for (int i = 0; i < cont.npoly; )
607 + {
608 + int ii = (i+1) % cont.npoly;
609 +
610 + const int ai = (int)cont.poly[i];
611 + const int ax = (int)cont.verts[ai*4+0];
612 + const int az = (int)cont.verts[ai*4+2];
613 +
614 + const int bi = (int)cont.poly[ii];
615 + const int bx = (int)cont.verts[bi*4+0];
616 + const int bz = (int)cont.verts[bi*4+2];
617 +
618 + // Find maximum deviation from the segment.
619 + float maxd = 0;
620 + int maxi = -1;
621 + int ci, cinc, endi;
622 +
623 + // Traverse the segment in lexilogical order so that the
624 + // max deviation is calculated similarly when traversing
625 + // opposite segments.
626 + if (bx > ax || (bx == ax && bz > az))
627 + {
628 + cinc = 1;
629 + ci = (ai+cinc) % cont.nverts;
630 + endi = bi;
631 + }
632 + else
633 + {
634 + cinc = cont.nverts-1;
635 + ci = (bi+cinc) % cont.nverts;
636 + endi = ai;
637 + }
638 +
639 + // Tessellate only outer edges or edges between areas.
640 + while (ci != endi)
641 + {
642 + float d = distancePtSeg(cont.verts[ci*4+0], cont.verts[ci*4+2], ax, az, bx, bz);
643 + if (d > maxd)
644 + {
645 + maxd = d;
646 + maxi = ci;
647 + }
648 + ci = (ci+cinc) % cont.nverts;
649 + }
650 +
651 +
652 + // If the max deviation is larger than accepted error,
653 + // add new point, else continue to next segment.
654 + if (maxi != -1 && maxd > (maxError*maxError))
655 + {
656 + cont.npoly++;
657 + for (int j = cont.npoly-1; j > i; --j)
658 + cont.poly[j] = cont.poly[j-1];
659 + cont.poly[i+1] = (unsigned short)maxi;
660 + }
661 + else
662 + {
663 + ++i;
664 + }
665 + }
666 +
667 + // Remap vertices
668 + int start = 0;
669 + for (int i = 1; i < cont.npoly; ++i)
670 + if (cont.poly[i] < cont.poly[start])
671 + start = i;
672 +
673 + cont.nverts = 0;
674 + for (int i = 0; i < cont.npoly; ++i)
675 + {
676 + const int j = (start+i) % cont.npoly;
677 + unsigned char* src = &cont.verts[cont.poly[j]*4];
678 + unsigned char* dst = &cont.verts[cont.nverts*4];
679 + dst[0] = src[0];
680 + dst[1] = src[1];
681 + dst[2] = src[2];
682 + dst[3] = src[3];
683 + cont.nverts++;
684 + }
685 685 }
686 686
687 687 static unsigned char getCornerHeight(dtTileCacheLayer& layer,
688 - const int x, const int y, const int z,
689 - const int walkableClimb,
690 - bool& shouldRemove)
691 - {
692 - const int w = (int)layer.header->width;
693 - const int h = (int)layer.header->height;
694 -
695 - int n = 0;
696 -
697 - unsigned char portal = 0xf;
698 - unsigned char height = 0;
699 - unsigned char preg = 0xff;
700 - bool allSameReg = true;
701 -
702 - for (int dz = -1; dz <= 0; ++dz)
703 - {
704 - for (int dx = -1; dx <= 0; ++dx)
705 - {
706 - const int px = x+dx;
707 - const int pz = z+dz;
708 - if (px >= 0 && pz >= 0 && px < w && pz < h)
709 - {
710 - const int idx = px + pz*w;
711 - const int lh = (int)layer.heights[idx];
712 - if (dtAbs(lh-y) <= walkableClimb && layer.areas[idx] != DT_TILECACHE_NULL_AREA)
713 - {
714 - height = dtMax(height, (unsigned char)lh);
715 - portal &= (layer.cons[idx] >> 4);
716 - if (preg != 0xff && preg != layer.regs[idx])
717 - allSameReg = false;
718 - preg = layer.regs[idx];
719 - n++;
720 - }
721 - }
722 - }
723 - }
724 -
725 - int portalCount = 0;
726 - for (int dir = 0; dir < 4; ++dir)
727 - if (portal & (1<<dir))
728 - portalCount++;
729 -
730 - shouldRemove = false;
731 - if (n > 1 && portalCount == 1 && allSameReg)
732 - {
733 - shouldRemove = true;
734 - }
735 -
736 - return height;
688 + const int x, const int y, const int z,
689 + const int walkableClimb,
690 + bool& shouldRemove)
691 + {
692 + const int w = (int)layer.header->width;
693 + const int h = (int)layer.header->height;
694 +
695 + int n = 0;
696 +
697 + unsigned char portal = 0xf;
698 + unsigned char height = 0;
699 + unsigned char preg = 0xff;
700 + bool allSameReg = true;
701 +
702 + for (int dz = -1; dz <= 0; ++dz)
703 + {
704 + for (int dx = -1; dx <= 0; ++dx)
705 + {
706 + const int px = x+dx;
707 + const int pz = z+dz;
708 + if (px >= 0 && pz >= 0 && px < w && pz < h)
709 + {
710 + const int idx = px + pz*w;
711 + const int lh = (int)layer.heights[idx];
712 + if (dtAbs(lh-y) <= walkableClimb && layer.areas[idx] != DT_TILECACHE_NULL_AREA)
713 + {
714 + height = dtMax(height, (unsigned char)lh);
715 + portal &= (layer.cons[idx] >> 4);
716 + if (preg != 0xff && preg != layer.regs[idx])
717 + allSameReg = false;
718 + preg = layer.regs[idx];
719 + n++;
720 + }
721 + }
722 + }
723 + }
724 +
725 + int portalCount = 0;
726 + for (int dir = 0; dir < 4; ++dir)
727 + if (portal & (1<<dir))
728 + portalCount++;
729 +
730 + shouldRemove = false;
731 + if (n > 1 && portalCount == 1 && allSameReg)
732 + {
733 + shouldRemove = true;
734 + }
735 +
736 + return height;
737 737 }
738 738
739 739
740 740 // TODO: move this somewhere else, once the layer meshing is done.
741 741 dtStatus dtBuildTileCacheContours(dtTileCacheAlloc* alloc,
742 - dtTileCacheLayer& layer,
743 - const int walkableClimb, const float maxError,
744 - dtTileCacheContourSet& lcset)
745 - {
746 - dtAssert(alloc);
747 -
748 - const int w = (int)layer.header->width;
749 - const int h = (int)layer.header->height;
750 -
751 - lcset.nconts = layer.regCount;
752 - lcset.conts = (dtTileCacheContour*)alloc->alloc(sizeof(dtTileCacheContour)*lcset.nconts);
753 - if (!lcset.conts)
754 - return DT_FAILURE | DT_OUT_OF_MEMORY;
755 - memset(lcset.conts, 0, sizeof(dtTileCacheContour)*lcset.nconts);
756 -
757 - // Allocate temp buffer for contour tracing.
758 - const int maxTempVerts = (w+h)*2 * 2; // Twice around the layer.
759 -
760 - dtFixedArray<unsigned char> tempVerts(alloc, maxTempVerts*4);
761 - if (!tempVerts)
762 - return DT_FAILURE | DT_OUT_OF_MEMORY;
763 -
764 - dtFixedArray<unsigned short> tempPoly(alloc, maxTempVerts);
765 - if (!tempPoly)
766 - return DT_FAILURE | DT_OUT_OF_MEMORY;
767 -
768 - dtTempContour temp(tempVerts, maxTempVerts, tempPoly, maxTempVerts);
769 -
770 - // Find contours.
771 - for (int y = 0; y < h; ++y)
772 - {
773 - for (int x = 0; x < w; ++x)
774 - {
775 - const int idx = x+y*w;
776 - const unsigned char ri = layer.regs[idx];
777 - if (ri == 0xff)
778 - continue;
779 -
780 - dtTileCacheContour& cont = lcset.conts[ri];
781 -
782 - if (cont.nverts > 0)
783 - continue;
784 -
785 - cont.reg = ri;
786 - cont.area = layer.areas[idx];
787 -
788 - if (!walkContour(layer, x, y, temp))
789 - {
790 - // Too complex contour.
791 - // Note: If you hit here ofte, try increasing 'maxTempVerts'.
792 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
793 - }
794 -
795 - simplifyContour(temp, maxError);
796 -
797 - // Store contour.
798 - cont.nverts = temp.nverts;
799 - if (cont.nverts > 0)
800 - {
801 - cont.verts = (unsigned char*)alloc->alloc(sizeof(unsigned char)*4*temp.nverts);
802 - if (!cont.verts)
803 - return DT_FAILURE | DT_OUT_OF_MEMORY;
804 -
805 - for (int i = 0, j = temp.nverts-1; i < temp.nverts; j=i++)
806 - {
807 - unsigned char* dst = &cont.verts[j*4];
808 - unsigned char* v = &temp.verts[j*4];
809 - unsigned char* vn = &temp.verts[i*4];
810 - unsigned char nei = vn[3]; // The neighbour reg is stored at segment vertex of a segment.
811 - bool shouldRemove = false;
812 - unsigned char lh = getCornerHeight(layer, (int)v[0], (int)v[1], (int)v[2],
813 - walkableClimb, shouldRemove);
814 -
815 - dst[0] = v[0];
816 - dst[1] = lh;
817 - dst[2] = v[2];
818 -
819 - // Store portal direction and remove status to the fourth component.
820 - dst[3] = 0x0f;
821 - if (nei != 0xff && nei >= 0xf8)
822 - dst[3] = nei - 0xf8;
823 - if (shouldRemove)
824 - dst[3] |= 0x80;
825 - }
826 - }
827 - }
828 - }
829 -
830 - return DT_SUCCESS;
831 - }
742 + dtTileCacheLayer& layer,
743 + const int walkableClimb, const float maxError,
744 + dtTileCacheContourSet& lcset)
745 + {
746 + dtAssert(alloc);
747 +
748 + const int w = (int)layer.header->width;
749 + const int h = (int)layer.header->height;
750 +
751 + lcset.nconts = layer.regCount;
752 + lcset.conts = (dtTileCacheContour*)alloc->alloc(sizeof(dtTileCacheContour)*lcset.nconts);
753 + if (!lcset.conts)
754 + return DT_FAILURE | DT_OUT_OF_MEMORY;
755 + memset(lcset.conts, 0, sizeof(dtTileCacheContour)*lcset.nconts);
756 +
757 + // Allocate temp buffer for contour tracing.
758 + const int maxTempVerts = (w+h)*2 * 2; // Twice around the layer.
759 +
760 + dtFixedArray<unsigned char> tempVerts(alloc, maxTempVerts*4);
761 + if (!tempVerts)
762 + return DT_FAILURE | DT_OUT_OF_MEMORY;
763 +
764 + dtFixedArray<unsigned short> tempPoly(alloc, maxTempVerts);
765 + if (!tempPoly)
766 + return DT_FAILURE | DT_OUT_OF_MEMORY;
767 +
768 + dtTempContour temp(tempVerts, maxTempVerts, tempPoly, maxTempVerts);
769 +
770 + // Find contours.
771 + for (int y = 0; y < h; ++y)
772 + {
773 + for (int x = 0; x < w; ++x)
774 + {
775 + const int idx = x+y*w;
776 + const unsigned char ri = layer.regs[idx];
777 + if (ri == 0xff)
778 + continue;
779 +
780 + dtTileCacheContour& cont = lcset.conts[ri];
781 +
782 + if (cont.nverts > 0)
783 + continue;
784 +
785 + cont.reg = ri;
786 + cont.area = layer.areas[idx];
787 +
788 + if (!walkContour(layer, x, y, temp))
789 + {
790 + // Too complex contour.
791 + // Note: If you hit here ofte, try increasing 'maxTempVerts'.
792 + return DT_FAILURE | DT_BUFFER_TOO_SMALL;
793 + }
794 +
795 + simplifyContour(temp, maxError);
796 +
797 + // Store contour.
798 + cont.nverts = temp.nverts;
799 + if (cont.nverts > 0)
800 + {
801 + cont.verts = (unsigned char*)alloc->alloc(sizeof(unsigned char)*4*temp.nverts);
802 + if (!cont.verts)
803 + return DT_FAILURE | DT_OUT_OF_MEMORY;
804 +
805 + for (int i = 0, j = temp.nverts-1; i < temp.nverts; j=i++)
806 + {
807 + unsigned char* dst = &cont.verts[j*4];
808 + unsigned char* v = &temp.verts[j*4];
809 + unsigned char* vn = &temp.verts[i*4];
810 + unsigned char nei = vn[3]; // The neighbour reg is stored at segment vertex of a segment.
811 + bool shouldRemove = false;
812 + unsigned char lh = getCornerHeight(layer, (int)v[0], (int)v[1], (int)v[2],
813 + walkableClimb, shouldRemove);
814 +
815 + dst[0] = v[0];
816 + dst[1] = lh;
817 + dst[2] = v[2];
818 +
819 + // Store portal direction and remove status to the fourth component.
820 + dst[3] = 0x0f;
821 + if (nei != 0xff && nei >= 0xf8)
822 + dst[3] = nei - 0xf8;
823 + if (shouldRemove)
824 + dst[3] |= 0x80;
825 + }
826 + }
827 + }
828 + }
829 +
830 + return DT_SUCCESS;
831 + }
832 832
833 833
834 834
  @@ -836,235 +836,235 @@
836 836
837 837 inline int computeVertexHash2(int x, int y, int z)
838 838 {
839 - const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
840 - const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
841 - const unsigned int h3 = 0xcb1ab31f;
842 - unsigned int n = h1 * x + h2 * y + h3 * z;
843 - return (int)(n & (VERTEX_BUCKET_COUNT2-1));
839 + const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
840 + const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
841 + const unsigned int h3 = 0xcb1ab31f;
842 + unsigned int n = h1 * x + h2 * y + h3 * z;
843 + return (int)(n & (VERTEX_BUCKET_COUNT2-1));
844 844 }
845 845
846 846 static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z,
847 - unsigned short* verts, unsigned short* firstVert, unsigned short* nextVert, int& nv)
847 + unsigned short* verts, unsigned short* firstVert, unsigned short* nextVert, int& nv)
848 848 {
849 - int bucket = computeVertexHash2(x, 0, z);
850 - unsigned short i = firstVert[bucket];
851 -
852 - while (i != DT_TILECACHE_NULL_IDX)
853 - {
854 - const unsigned short* v = &verts[i*3];
855 - if (v[0] == x && v[2] == z && (dtAbs(v[1] - y) <= 2))
856 - return i;
857 - i = nextVert[i]; // next
858 - }
859 -
860 - // Could not find, create new.
861 - i = (unsigned short)nv; nv++;
862 - unsigned short* v = &verts[i*3];
863 - v[0] = x;
864 - v[1] = y;
865 - v[2] = z;
866 - nextVert[i] = firstVert[bucket];
867 - firstVert[bucket] = i;
868 -
869 - return (unsigned short)i;
849 + int bucket = computeVertexHash2(x, 0, z);
850 + unsigned short i = firstVert[bucket];
851 +
852 + while (i != DT_TILECACHE_NULL_IDX)
853 + {
854 + const unsigned short* v = &verts[i*3];
855 + if (v[0] == x && v[2] == z && (dtAbs(v[1] - y) <= 2))
856 + return i;
857 + i = nextVert[i]; // next
858 + }
859 +
860 + // Could not find, create new.
861 + i = (unsigned short)nv; nv++;
862 + unsigned short* v = &verts[i*3];
863 + v[0] = x;
864 + v[1] = y;
865 + v[2] = z;
866 + nextVert[i] = firstVert[bucket];
867 + firstVert[bucket] = i;
868 +
869 + return (unsigned short)i;
870 870 }
871 871
872 872
873 873 struct rcEdge
874 874 {
875 - unsigned short vert[2];
876 - unsigned short polyEdge[2];
877 - unsigned short poly[2];
875 + unsigned short vert[2];
876 + unsigned short polyEdge[2];
877 + unsigned short poly[2];
878 878 };
879 879
880 880 static bool buildMeshAdjacency(dtTileCacheAlloc* alloc,
881 - unsigned short* polys, const int npolys,
882 - const unsigned short* verts, const int nverts,
883 - const dtTileCacheContourSet& lcset)
884 - {
885 - // Based on code by Eric Lengyel from:
886 - // http://www.terathon.com/code/edges.php
887 -
888 - const int maxEdgeCount = npolys*MAX_VERTS_PER_POLY;
889 - dtFixedArray<unsigned short> firstEdge(alloc, nverts + maxEdgeCount);
890 - if (!firstEdge)
891 - return false;
892 - unsigned short* nextEdge = firstEdge + nverts;
893 - int edgeCount = 0;
894 -
895 - dtFixedArray<rcEdge> edges(alloc, maxEdgeCount);
896 - if (!edges)
897 - return false;
898 -
899 - for (int i = 0; i < nverts; i++)
900 - firstEdge[i] = DT_TILECACHE_NULL_IDX;
901 -
902 - for (int i = 0; i < npolys; ++i)
903 - {
904 - unsigned short* t = &polys[i*MAX_VERTS_PER_POLY*2];
905 - for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
906 - {
907 - if (t[j] == DT_TILECACHE_NULL_IDX) break;
908 - unsigned short v0 = t[j];
909 - unsigned short v1 = (j+1 >= MAX_VERTS_PER_POLY || t[j+1] == DT_TILECACHE_NULL_IDX) ? t[0] : t[j+1];
910 - if (v0 < v1)
911 - {
912 - rcEdge& edge = edges[edgeCount];
913 - edge.vert[0] = v0;
914 - edge.vert[1] = v1;
915 - edge.poly[0] = (unsigned short)i;
916 - edge.polyEdge[0] = (unsigned short)j;
917 - edge.poly[1] = (unsigned short)i;
918 - edge.polyEdge[1] = 0xff;
919 - // Insert edge
920 - nextEdge[edgeCount] = firstEdge[v0];
921 - firstEdge[v0] = (unsigned short)edgeCount;
922 - edgeCount++;
923 - }
924 - }
925 - }
926 -
927 - for (int i = 0; i < npolys; ++i)
928 - {
929 - unsigned short* t = &polys[i*MAX_VERTS_PER_POLY*2];
930 - for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
931 - {
932 - if (t[j] == DT_TILECACHE_NULL_IDX) break;
933 - unsigned short v0 = t[j];
934 - unsigned short v1 = (j+1 >= MAX_VERTS_PER_POLY || t[j+1] == DT_TILECACHE_NULL_IDX) ? t[0] : t[j+1];
935 - if (v0 > v1)
936 - {
937 - bool found = false;
938 - for (unsigned short e = firstEdge[v1]; e != DT_TILECACHE_NULL_IDX; e = nextEdge[e])
939 - {
940 - rcEdge& edge = edges[e];
941 - if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
942 - {
943 - edge.poly[1] = (unsigned short)i;
944 - edge.polyEdge[1] = (unsigned short)j;
945 - found = true;
946 - break;
947 - }
948 - }
949 - if (!found)
950 - {
951 - // Matching edge not found, it is an open edge, add it.
952 - rcEdge& edge = edges[edgeCount];
953 - edge.vert[0] = v1;
954 - edge.vert[1] = v0;
955 - edge.poly[0] = (unsigned short)i;
956 - edge.polyEdge[0] = (unsigned short)j;
957 - edge.poly[1] = (unsigned short)i;
958 - edge.polyEdge[1] = 0xff;
959 - // Insert edge
960 - nextEdge[edgeCount] = firstEdge[v1];
961 - firstEdge[v1] = (unsigned short)edgeCount;
962 - edgeCount++;
963 - }
964 - }
965 - }
966 - }
967 -
968 - // Mark portal edges.
969 - for (int i = 0; i < lcset.nconts; ++i)
970 - {
971 - dtTileCacheContour& cont = lcset.conts[i];
972 - if (cont.nverts < 3)
973 - continue;
974 -
975 - for (int j = 0, k = cont.nverts-1; j < cont.nverts; k=j++)
976 - {
977 - const unsigned char* va = &cont.verts[k*4];
978 - const unsigned char* vb = &cont.verts[j*4];
979 - const unsigned char dir = va[3] & 0xf;
980 - if (dir == 0xf)
981 - continue;
982 -
983 - if (dir == 0 || dir == 2)
984 - {
985 - // Find matching vertical edge
986 - const unsigned short x = (unsigned short)va[0];
987 - unsigned short zmin = (unsigned short)va[2];
988 - unsigned short zmax = (unsigned short)vb[2];
989 - if (zmin > zmax)
990 - dtSwap(zmin, zmax);
991 -
992 - for (int m = 0; m < edgeCount; ++m)
993 - {
994 - rcEdge& e = edges[m];
995 - // Skip connected edges.
996 - if (e.poly[0] != e.poly[1])
997 - continue;
998 - const unsigned short* eva = &verts[e.vert[0]*3];
999 - const unsigned short* evb = &verts[e.vert[1]*3];
1000 - if (eva[0] == x && evb[0] == x)
1001 - {
1002 - unsigned short ezmin = eva[2];
1003 - unsigned short ezmax = evb[2];
1004 - if (ezmin > ezmax)
1005 - dtSwap(ezmin, ezmax);
1006 - if (overlapRangeExl(zmin,zmax, ezmin, ezmax))
1007 - {
1008 - // Reuse the other polyedge to store dir.
1009 - e.polyEdge[1] = dir;
1010 - }
1011 - }
1012 - }
1013 - }
1014 - else
1015 - {
1016 - // Find matching vertical edge
1017 - const unsigned short z = (unsigned short)va[2];
1018 - unsigned short xmin = (unsigned short)va[0];
1019 - unsigned short xmax = (unsigned short)vb[0];
1020 - if (xmin > xmax)
1021 - dtSwap(xmin, xmax);
1022 - for (int m = 0; m < edgeCount; ++m)
1023 - {
1024 - rcEdge& e = edges[m];
1025 - // Skip connected edges.
1026 - if (e.poly[0] != e.poly[1])
1027 - continue;
1028 - const unsigned short* eva = &verts[e.vert[0]*3];
1029 - const unsigned short* evb = &verts[e.vert[1]*3];
1030 - if (eva[2] == z && evb[2] == z)
1031 - {
1032 - unsigned short exmin = eva[0];
1033 - unsigned short exmax = evb[0];
1034 - if (exmin > exmax)
1035 - dtSwap(exmin, exmax);
1036 - if (overlapRangeExl(xmin,xmax, exmin, exmax))
1037 - {
1038 - // Reuse the other polyedge to store dir.
1039 - e.polyEdge[1] = dir;
1040 - }
1041 - }
1042 - }
1043 - }
1044 - }
1045 - }
1046 -
1047 -
1048 - // Store adjacency
1049 - for (int i = 0; i < edgeCount; ++i)
1050 - {
1051 - const rcEdge& e = edges[i];
1052 - if (e.poly[0] != e.poly[1])
1053 - {
1054 - unsigned short* p0 = &polys[e.poly[0]*MAX_VERTS_PER_POLY*2];
1055 - unsigned short* p1 = &polys[e.poly[1]*MAX_VERTS_PER_POLY*2];
1056 - p0[MAX_VERTS_PER_POLY + e.polyEdge[0]] = e.poly[1];
1057 - p1[MAX_VERTS_PER_POLY + e.polyEdge[1]] = e.poly[0];
1058 - }
1059 - else if (e.polyEdge[1] != 0xff)
1060 - {
1061 - unsigned short* p0 = &polys[e.poly[0]*MAX_VERTS_PER_POLY*2];
1062 - p0[MAX_VERTS_PER_POLY + e.polyEdge[0]] = 0x8000 | (unsigned short)e.polyEdge[1];
1063 - }
1064 -
1065 - }
1066 -
1067 - return true;
881 + unsigned short* polys, const int npolys,
882 + const unsigned short* verts, const int nverts,
883 + const dtTileCacheContourSet& lcset)
884 + {
885 + // Based on code by Eric Lengyel from:
886 + // http://www.terathon.com/code/edges.php
887 +
888 + const int maxEdgeCount = npolys*MAX_VERTS_PER_POLY;
889 + dtFixedArray<unsigned short> firstEdge(alloc, nverts + maxEdgeCount);
890 + if (!firstEdge)
891 + return false;
892 + unsigned short* nextEdge = firstEdge + nverts;
893 + int edgeCount = 0;
894 +
895 + dtFixedArray<rcEdge> edges(alloc, maxEdgeCount);
896 + if (!edges)
897 + return false;
898 +
899 + for (int i = 0; i < nverts; i++)
900 + firstEdge[i] = DT_TILECACHE_NULL_IDX;
901 +
902 + for (int i = 0; i < npolys; ++i)
903 + {
904 + unsigned short* t = &polys[i*MAX_VERTS_PER_POLY*2];
905 + for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
906 + {
907 + if (t[j] == DT_TILECACHE_NULL_IDX) break;
908 + unsigned short v0 = t[j];
909 + unsigned short v1 = (j+1 >= MAX_VERTS_PER_POLY || t[j+1] == DT_TILECACHE_NULL_IDX) ? t[0] : t[j+1];
910 + if (v0 < v1)
911 + {
912 + rcEdge& edge = edges[edgeCount];
913 + edge.vert[0] = v0;
914 + edge.vert[1] = v1;
915 + edge.poly[0] = (unsigned short)i;
916 + edge.polyEdge[0] = (unsigned short)j;
917 + edge.poly[1] = (unsigned short)i;
918 + edge.polyEdge[1] = 0xff;
919 + // Insert edge
920 + nextEdge[edgeCount] = firstEdge[v0];
921 + firstEdge[v0] = (unsigned short)edgeCount;
922 + edgeCount++;
923 + }
924 + }
925 + }
926 +
927 + for (int i = 0; i < npolys; ++i)
928 + {
929 + unsigned short* t = &polys[i*MAX_VERTS_PER_POLY*2];
930 + for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
931 + {
932 + if (t[j] == DT_TILECACHE_NULL_IDX) break;
933 + unsigned short v0 = t[j];
934 + unsigned short v1 = (j+1 >= MAX_VERTS_PER_POLY || t[j+1] == DT_TILECACHE_NULL_IDX) ? t[0] : t[j+1];
935 + if (v0 > v1)
936 + {
937 + bool found = false;
938 + for (unsigned short e = firstEdge[v1]; e != DT_TILECACHE_NULL_IDX; e = nextEdge[e])
939 + {
940 + rcEdge& edge = edges[e];
941 + if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
942 + {
943 + edge.poly[1] = (unsigned short)i;
944 + edge.polyEdge[1] = (unsigned short)j;
945 + found = true;
946 + break;
947 + }
948 + }
949 + if (!found)
950 + {
951 + // Matching edge not found, it is an open edge, add it.
952 + rcEdge& edge = edges[edgeCount];
953 + edge.vert[0] = v1;
954 + edge.vert[1] = v0;
955 + edge.poly[0] = (unsigned short)i;
956 + edge.polyEdge[0] = (unsigned short)j;
957 + edge.poly[1] = (unsigned short)i;
958 + edge.polyEdge[1] = 0xff;
959 + // Insert edge
960 + nextEdge[edgeCount] = firstEdge[v1];
961 + firstEdge[v1] = (unsigned short)edgeCount;
962 + edgeCount++;
963 + }
964 + }
965 + }
966 + }
967 +
968 + // Mark portal edges.
969 + for (int i = 0; i < lcset.nconts; ++i)
970 + {
971 + dtTileCacheContour& cont = lcset.conts[i];
972 + if (cont.nverts < 3)
973 + continue;
974 +
975 + for (int j = 0, k = cont.nverts-1; j < cont.nverts; k=j++)
976 + {
977 + const unsigned char* va = &cont.verts[k*4];
978 + const unsigned char* vb = &cont.verts[j*4];
979 + const unsigned char dir = va[3] & 0xf;
980 + if (dir == 0xf)
981 + continue;
982 +
983 + if (dir == 0 || dir == 2)
984 + {
985 + // Find matching vertical edge
986 + const unsigned short x = (unsigned short)va[0];
987 + unsigned short zmin = (unsigned short)va[2];
988 + unsigned short zmax = (unsigned short)vb[2];
989 + if (zmin > zmax)
990 + dtSwap(zmin, zmax);
991 +
992 + for (int m = 0; m < edgeCount; ++m)
993 + {
994 + rcEdge& e = edges[m];
995 + // Skip connected edges.
996 + if (e.poly[0] != e.poly[1])
997 + continue;
998 + const unsigned short* eva = &verts[e.vert[0]*3];
999 + const unsigned short* evb = &verts[e.vert[1]*3];
1000 + if (eva[0] == x && evb[0] == x)
1001 + {
1002 + unsigned short ezmin = eva[2];
1003 + unsigned short ezmax = evb[2];
1004 + if (ezmin > ezmax)
1005 + dtSwap(ezmin, ezmax);
1006 + if (overlapRangeExl(zmin,zmax, ezmin, ezmax))
1007 + {
1008 + // Reuse the other polyedge to store dir.
1009 + e.polyEdge[1] = dir;
1010 + }
1011 + }
1012 + }
1013 + }
1014 + else
1015 + {
1016 + // Find matching vertical edge
1017 + const unsigned short z = (unsigned short)va[2];
1018 + unsigned short xmin = (unsigned short)va[0];
1019 + unsigned short xmax = (unsigned short)vb[0];
1020 + if (xmin > xmax)
1021 + dtSwap(xmin, xmax);
1022 + for (int m = 0; m < edgeCount; ++m)
1023 + {
1024 + rcEdge& e = edges[m];
1025 + // Skip connected edges.
1026 + if (e.poly[0] != e.poly[1])
1027 + continue;
1028 + const unsigned short* eva = &verts[e.vert[0]*3];
1029 + const unsigned short* evb = &verts[e.vert[1]*3];
1030 + if (eva[2] == z && evb[2] == z)
1031 + {
1032 + unsigned short exmin = eva[0];
1033 + unsigned short exmax = evb[0];
1034 + if (exmin > exmax)
1035 + dtSwap(exmin, exmax);
1036 + if (overlapRangeExl(xmin,xmax, exmin, exmax))
1037 + {
1038 + // Reuse the other polyedge to store dir.
1039 + e.polyEdge[1] = dir;
1040 + }
1041 + }
1042 + }
1043 + }
1044 + }
1045 + }
1046 +
1047 +
1048 + // Store adjacency
1049 + for (int i = 0; i < edgeCount; ++i)
1050 + {
1051 + const rcEdge& e = edges[i];
1052 + if (e.poly[0] != e.poly[1])
1053 + {
1054 + unsigned short* p0 = &polys[e.poly[0]*MAX_VERTS_PER_POLY*2];
1055 + unsigned short* p1 = &polys[e.poly[1]*MAX_VERTS_PER_POLY*2];
1056 + p0[MAX_VERTS_PER_POLY + e.polyEdge[0]] = e.poly[1];
1057 + p1[MAX_VERTS_PER_POLY + e.polyEdge[1]] = e.poly[0];
1058 + }
1059 + else if (e.polyEdge[1] != 0xff)
1060 + {
1061 + unsigned short* p0 = &polys[e.poly[0]*MAX_VERTS_PER_POLY*2];
1062 + p0[MAX_VERTS_PER_POLY + e.polyEdge[0]] = 0x8000 | (unsigned short)e.polyEdge[1];
1063 + }
1064 +
1065 + }
1066 +
1067 + return true;
1068 1068 }
1069 1069
1070 1070
  @@ -1073,1079 +1073,1079 @@
1073 1073
1074 1074 inline int area2(const unsigned char* a, const unsigned char* b, const unsigned char* c)
1075 1075 {
1076 - return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) - ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]);
1076 + return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) - ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]);
1077 1077 }
1078 1078
1079 - // Exclusive or: true iff exactly one argument is true.
1080 - // The arguments are negated to ensure that they are 0/1
1081 - // values. Then the bitwise Xor operator may apply.
1082 - // (This idea is due to Michael Baldwin.)
1079 + // Exclusive or: true iff exactly one argument is true.
1080 + // The arguments are negated to ensure that they are 0/1
1081 + // values. Then the bitwise Xor operator may apply.
1082 + // (This idea is due to Michael Baldwin.)
1083 1083 inline bool xorb(bool x, bool y)
1084 1084 {
1085 - return !x ^ !y;
1085 + return !x ^ !y;
1086 1086 }
1087 1087
1088 1088 // Returns true iff c is strictly to the left of the directed
1089 1089 // line through a to b.
1090 1090 inline bool left(const unsigned char* a, const unsigned char* b, const unsigned char* c)
1091 1091 {
1092 - return area2(a, b, c) < 0;
1092 + return area2(a, b, c) < 0;
1093 1093 }
1094 1094
1095 1095 inline bool leftOn(const unsigned char* a, const unsigned char* b, const unsigned char* c)
1096 1096 {
1097 - return area2(a, b, c) <= 0;
1097 + return area2(a, b, c) <= 0;
1098 1098 }
1099 1099
1100 1100 inline bool collinear(const unsigned char* a, const unsigned char* b, const unsigned char* c)
1101 1101 {
1102 - return area2(a, b, c) == 0;
1102 + return area2(a, b, c) == 0;
1103 1103 }
1104 1104
1105 - // Returns true iff ab properly intersects cd: they share
1106 - // a point interior to both segments. The properness of the
1107 - // intersection is ensured by using strict leftness.
1105 + // Returns true iff ab properly intersects cd: they share
1106 + // a point interior to both segments. The properness of the
1107 + // intersection is ensured by using strict leftness.
1108 1108 static bool intersectProp(const unsigned char* a, const unsigned char* b,
1109 - const unsigned char* c, const unsigned char* d)
1109 + const unsigned char* c, const unsigned char* d)
1110 1110 {
1111 - // Eliminate improper cases.
1112 - if (collinear(a,b,c) || collinear(a,b,d) ||
1113 - collinear(c,d,a) || collinear(c,d,b))
1114 - return false;
1115 -
1116 - return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b));
1111 + // Eliminate improper cases.
1112 + if (collinear(a,b,c) || collinear(a,b,d) ||
1113 + collinear(c,d,a) || collinear(c,d,b))
1114 + return false;
1115 +
1116 + return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b));
1117 1117 }
1118 1118
1119 1119 // Returns T iff (a,b,c) are collinear and point c lies
1120 1120 // on the closed segement ab.
1121 1121 static bool between(const unsigned char* a, const unsigned char* b, const unsigned char* c)
1122 1122 {
1123 - if (!collinear(a, b, c))
1124 - return false;
1125 - // If ab not vertical, check betweenness on x; else on y.
1126 - if (a[0] != b[0])
1127 - return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0]));
1128 - else
1129 - return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2]));
1123 + if (!collinear(a, b, c))
1124 + return false;
1125 + // If ab not vertical, check betweenness on x; else on y.
1126 + if (a[0] != b[0])
1127 + return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0]));
1128 + else
1129 + return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2]));
1130 1130 }
1131 1131
1132 1132 // Returns true iff segments ab and cd intersect, properly or improperly.
1133 1133 static bool intersect(const unsigned char* a, const unsigned char* b,
1134 - const unsigned char* c, const unsigned char* d)
1134 + const unsigned char* c, const unsigned char* d)
1135 1135 {
1136 - if (intersectProp(a, b, c, d))
1137 - return true;
1138 - else if (between(a, b, c) || between(a, b, d) ||
1139 - between(c, d, a) || between(c, d, b))
1140 - return true;
1141 - else
1142 - return false;
1136 + if (intersectProp(a, b, c, d))
1137 + return true;
1138 + else if (between(a, b, c) || between(a, b, d) ||
1139 + between(c, d, a) || between(c, d, b))
1140 + return true;
1141 + else
1142 + return false;
1143 1143 }
1144 1144
1145 1145 static bool vequal(const unsigned char* a, const unsigned char* b)
1146 1146 {
1147 - return a[0] == b[0] && a[2] == b[2];
1147 + return a[0] == b[0] && a[2] == b[2];
1148 1148 }
1149 1149
1150 1150 // Returns T iff (v_i, v_j) is a proper internal *or* external
1151 1151 // diagonal of P, *ignoring edges incident to v_i and v_j*.
1152 1152 static bool diagonalie(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
1153 1153 {
1154 - const unsigned char* d0 = &verts[(indices[i] & 0x7fff) * 4];
1155 - const unsigned char* d1 = &verts[(indices[j] & 0x7fff) * 4];
1156 -
1157 - // For each edge (k,k+1) of P
1158 - for (int k = 0; k < n; k++)
1159 - {
1160 - int k1 = next(k, n);
1161 - // Skip edges incident to i or j
1162 - if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
1163 - {
1164 - const unsigned char* p0 = &verts[(indices[k] & 0x7fff) * 4];
1165 - const unsigned char* p1 = &verts[(indices[k1] & 0x7fff) * 4];
1166 -
1167 - if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
1168 - continue;
1169 -
1170 - if (intersect(d0, d1, p0, p1))
1171 - return false;
1172 - }
1173 - }
1174 - return true;
1154 + const unsigned char* d0 = &verts[(indices[i] & 0x7fff) * 4];
1155 + const unsigned char* d1 = &verts[(indices[j] & 0x7fff) * 4];
1156 +
1157 + // For each edge (k,k+1) of P
1158 + for (int k = 0; k < n; k++)
1159 + {
1160 + int k1 = next(k, n);
1161 + // Skip edges incident to i or j
1162 + if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
1163 + {
1164 + const unsigned char* p0 = &verts[(indices[k] & 0x7fff) * 4];
1165 + const unsigned char* p1 = &verts[(indices[k1] & 0x7fff) * 4];
1166 +
1167 + if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
1168 + continue;
1169 +
1170 + if (intersect(d0, d1, p0, p1))
1171 + return false;
1172 + }
1173 + }
1174 + return true;
1175 1175 }
1176 1176
1177 1177 // Returns true iff the diagonal (i,j) is strictly internal to the
1178 1178 // polygon P in the neighborhood of the i endpoint.
1179 - static bool inCone(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
1179 + static bool inCone(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
1180 1180 {
1181 - const unsigned char* pi = &verts[(indices[i] & 0x7fff) * 4];
1182 - const unsigned char* pj = &verts[(indices[j] & 0x7fff) * 4];
1183 - const unsigned char* pi1 = &verts[(indices[next(i, n)] & 0x7fff) * 4];
1184 - const unsigned char* pin1 = &verts[(indices[prev(i, n)] & 0x7fff) * 4];
1185 -
1186 - // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
1187 - if (leftOn(pin1, pi, pi1))
1188 - return left(pi, pj, pin1) && left(pj, pi, pi1);
1189 - // Assume (i-1,i,i+1) not collinear.
1190 - // else P[i] is reflex.
1191 - return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
1181 + const unsigned char* pi = &verts[(indices[i] & 0x7fff) * 4];
1182 + const unsigned char* pj = &verts[(indices[j] & 0x7fff) * 4];
1183 + const unsigned char* pi1 = &verts[(indices[next(i, n)] & 0x7fff) * 4];
1184 + const unsigned char* pin1 = &verts[(indices[prev(i, n)] & 0x7fff) * 4];
1185 +
1186 + // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
1187 + if (leftOn(pin1, pi, pi1))
1188 + return left(pi, pj, pin1) && left(pj, pi, pi1);
1189 + // Assume (i-1,i,i+1) not collinear.
1190 + // else P[i] is reflex.
1191 + return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
1192 1192 }
1193 1193
1194 1194 // Returns T iff (v_i, v_j) is a proper internal
1195 1195 // diagonal of P.
1196 1196 static bool diagonal(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
1197 1197 {
1198 - return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
1198 + return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
1199 1199 }
1200 1200
1201 1201 static int triangulate(int n, const unsigned char* verts, unsigned short* indices, unsigned short* tris)
1202 1202 {
1203 - int ntris = 0;
1204 - unsigned short* dst = tris;
1205 -
1206 - // The last bit of the index is used to indicate if the vertex can be removed.
1207 - for (int i = 0; i < n; i++)
1208 - {
1209 - int i1 = next(i, n);
1210 - int i2 = next(i1, n);
1211 - if (diagonal(i, i2, n, verts, indices))
1212 - indices[i1] |= 0x8000;
1213 - }
1214 -
1215 - while (n > 3)
1216 - {
1217 - int minLen = -1;
1218 - int mini = -1;
1219 - for (int i = 0; i < n; i++)
1220 - {
1221 - int i1 = next(i, n);
1222 - if (indices[i1] & 0x8000)
1223 - {
1224 - const unsigned char* p0 = &verts[(indices[i] & 0x7fff) * 4];
1225 - const unsigned char* p2 = &verts[(indices[next(i1, n)] & 0x7fff) * 4];
1226 -
1227 - const int dx = (int)p2[0] - (int)p0[0];
1228 - const int dz = (int)p2[2] - (int)p0[2];
1229 - const int len = dx*dx + dz*dz;
1230 - if (minLen < 0 || len < minLen)
1231 - {
1232 - minLen = len;
1233 - mini = i;
1234 - }
1235 - }
1236 - }
1237 -
1238 - if (mini == -1)
1239 - {
1240 - // Should not happen.
1241 - /* printf("mini == -1 ntris=%d n=%d\n", ntris, n);
1242 - for (int i = 0; i < n; i++)
1243 - {
1244 - printf("%d ", indices[i] & 0x0fffffff);
1245 - }
1246 - printf("\n");*/
1247 - return -ntris;
1248 - }
1249 -
1250 - int i = mini;
1251 - int i1 = next(i, n);
1252 - int i2 = next(i1, n);
1253 -
1254 - *dst++ = indices[i] & 0x7fff;
1255 - *dst++ = indices[i1] & 0x7fff;
1256 - *dst++ = indices[i2] & 0x7fff;
1257 - ntris++;
1258 -
1259 - // Removes P[i1] by copying P[i+1]...P[n-1] left one index.
1260 - n--;
1261 - for (int k = i1; k < n; k++)
1262 - indices[k] = indices[k+1];
1263 -
1264 - if (i1 >= n) i1 = 0;
1265 - i = prev(i1,n);
1266 - // Update diagonal flags.
1267 - if (diagonal(prev(i, n), i1, n, verts, indices))
1268 - indices[i] |= 0x8000;
1269 - else
1270 - indices[i] &= 0x7fff;
1271 -
1272 - if (diagonal(i, next(i1, n), n, verts, indices))
1273 - indices[i1] |= 0x8000;
1274 - else
1275 - indices[i1] &= 0x7fff;
1276 - }
1277 -
1278 - // Append the remaining triangle.
1279 - *dst++ = indices[0] & 0x7fff;
1280 - *dst++ = indices[1] & 0x7fff;
1281 - *dst++ = indices[2] & 0x7fff;
1282 - ntris++;
1283 -
1284 - return ntris;
1203 + int ntris = 0;
1204 + unsigned short* dst = tris;
1205 +
1206 + // The last bit of the index is used to indicate if the vertex can be removed.
1207 + for (int i = 0; i < n; i++)
1208 + {
1209 + int i1 = next(i, n);
1210 + int i2 = next(i1, n);
1211 + if (diagonal(i, i2, n, verts, indices))
1212 + indices[i1] |= 0x8000;
1213 + }
1214 +
1215 + while (n > 3)
1216 + {
1217 + int minLen = -1;
1218 + int mini = -1;
1219 + for (int i = 0; i < n; i++)
1220 + {
1221 + int i1 = next(i, n);
1222 + if (indices[i1] & 0x8000)
1223 + {
1224 + const unsigned char* p0 = &verts[(indices[i] & 0x7fff) * 4];
1225 + const unsigned char* p2 = &verts[(indices[next(i1, n)] & 0x7fff) * 4];
1226 +
1227 + const int dx = (int)p2[0] - (int)p0[0];
1228 + const int dz = (int)p2[2] - (int)p0[2];
1229 + const int len = dx*dx + dz*dz;
1230 + if (minLen < 0 || len < minLen)
1231 + {
1232 + minLen = len;
1233 + mini = i;
1234 + }
1235 + }
1236 + }
1237 +
1238 + if (mini == -1)
1239 + {
1240 + // Should not happen.
1241 + /* printf("mini == -1 ntris=%d n=%d\n", ntris, n);
1242 + for (int i = 0; i < n; i++)
1243 + {
1244 + printf("%d ", indices[i] & 0x0fffffff);
1245 + }
1246 + printf("\n");*/
1247 + return -ntris;
1248 + }
1249 +
1250 + int i = mini;
1251 + int i1 = next(i, n);
1252 + int i2 = next(i1, n);
1253 +
1254 + *dst++ = indices[i] & 0x7fff;
1255 + *dst++ = indices[i1] & 0x7fff;
1256 + *dst++ = indices[i2] & 0x7fff;
1257 + ntris++;
1258 +
1259 + // Removes P[i1] by copying P[i+1]...P[n-1] left one index.
1260 + n--;
1261 + for (int k = i1; k < n; k++)
1262 + indices[k] = indices[k+1];
1263 +
1264 + if (i1 >= n) i1 = 0;
1265 + i = prev(i1,n);
1266 + // Update diagonal flags.
1267 + if (diagonal(prev(i, n), i1, n, verts, indices))
1268 + indices[i] |= 0x8000;
1269 + else
1270 + indices[i] &= 0x7fff;
1271 +
1272 + if (diagonal(i, next(i1, n), n, verts, indices))
1273 + indices[i1] |= 0x8000;
1274 + else
1275 + indices[i1] &= 0x7fff;
1276 + }
1277 +
1278 + // Append the remaining triangle.
1279 + *dst++ = indices[0] & 0x7fff;
1280 + *dst++ = indices[1] & 0x7fff;
1281 + *dst++ = indices[2] & 0x7fff;
1282 + ntris++;
1283 +
1284 + return ntris;
1285 1285 }
1286 1286
1287 1287
1288 1288 static int countPolyVerts(const unsigned short* p)
1289 1289 {
1290 - for (int i = 0; i < MAX_VERTS_PER_POLY; ++i)
1291 - if (p[i] == DT_TILECACHE_NULL_IDX)
1292 - return i;
1293 - return MAX_VERTS_PER_POLY;
1290 + for (int i = 0; i < MAX_VERTS_PER_POLY; ++i)
1291 + if (p[i] == DT_TILECACHE_NULL_IDX)
1292 + return i;
1293 + return MAX_VERTS_PER_POLY;
1294 1294 }
1295 1295
1296 1296 inline bool uleft(const unsigned short* a, const unsigned short* b, const unsigned short* c)
1297 1297 {
1298 - return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) -
1299 - ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]) < 0;
1298 + return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) -
1299 + ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]) < 0;
1300 1300 }
1301 1301
1302 1302 static int getPolyMergeValue(unsigned short* pa, unsigned short* pb,
1303 - const unsigned short* verts, int& ea, int& eb)
1303 + const unsigned short* verts, int& ea, int& eb)
1304 1304 {
1305 - const int na = countPolyVerts(pa);
1306 - const int nb = countPolyVerts(pb);
1307 -
1308 - // If the merged polygon would be too big, do not merge.
1309 - if (na+nb-2 > MAX_VERTS_PER_POLY)
1310 - return -1;
1311 -
1312 - // Check if the polygons share an edge.
1313 - ea = -1;
1314 - eb = -1;
1315 -
1316 - for (int i = 0; i < na; ++i)
1317 - {
1318 - unsigned short va0 = pa[i];
1319 - unsigned short va1 = pa[(i+1) % na];
1320 - if (va0 > va1)
1321 - dtSwap(va0, va1);
1322 - for (int j = 0; j < nb; ++j)
1323 - {
1324 - unsigned short vb0 = pb[j];
1325 - unsigned short vb1 = pb[(j+1) % nb];
1326 - if (vb0 > vb1)
1327 - dtSwap(vb0, vb1);
1328 - if (va0 == vb0 && va1 == vb1)
1329 - {
1330 - ea = i;
1331 - eb = j;
1332 - break;
1333 - }
1334 - }
1335 - }
1336 -
1337 - // No common edge, cannot merge.
1338 - if (ea == -1 || eb == -1)
1339 - return -1;
1340 -
1341 - // Check to see if the merged polygon would be convex.
1342 - unsigned short va, vb, vc;
1343 -
1344 - va = pa[(ea+na-1) % na];
1345 - vb = pa[ea];
1346 - vc = pb[(eb+2) % nb];
1347 - if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
1348 - return -1;
1349 -
1350 - va = pb[(eb+nb-1) % nb];
1351 - vb = pb[eb];
1352 - vc = pa[(ea+2) % na];
1353 - if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
1354 - return -1;
1355 -
1356 - va = pa[ea];
1357 - vb = pa[(ea+1)%na];
1358 -
1359 - int dx = (int)verts[va*3+0] - (int)verts[vb*3+0];
1360 - int dy = (int)verts[va*3+2] - (int)verts[vb*3+2];
1361 -
1362 - return dx*dx + dy*dy;
1305 + const int na = countPolyVerts(pa);
1306 + const int nb = countPolyVerts(pb);
1307 +
1308 + // If the merged polygon would be too big, do not merge.
1309 + if (na+nb-2 > MAX_VERTS_PER_POLY)
1310 + return -1;
1311 +
1312 + // Check if the polygons share an edge.
1313 + ea = -1;
1314 + eb = -1;
1315 +
1316 + for (int i = 0; i < na; ++i)
1317 + {
1318 + unsigned short va0 = pa[i];
1319 + unsigned short va1 = pa[(i+1) % na];
1320 + if (va0 > va1)
1321 + dtSwap(va0, va1);
1322 + for (int j = 0; j < nb; ++j)
1323 + {
1324 + unsigned short vb0 = pb[j];
1325 + unsigned short vb1 = pb[(j+1) % nb];
1326 + if (vb0 > vb1)
1327 + dtSwap(vb0, vb1);
1328 + if (va0 == vb0 && va1 == vb1)
1329 + {
1330 + ea = i;
1331 + eb = j;
1332 + break;
1333 + }
1334 + }
1335 + }
1336 +
1337 + // No common edge, cannot merge.
1338 + if (ea == -1 || eb == -1)
1339 + return -1;
1340 +
1341 + // Check to see if the merged polygon would be convex.
1342 + unsigned short va, vb, vc;
1343 +
1344 + va = pa[(ea+na-1) % na];
1345 + vb = pa[ea];
1346 + vc = pb[(eb+2) % nb];
1347 + if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
1348 + return -1;
1349 +
1350 + va = pb[(eb+nb-1) % nb];
1351 + vb = pb[eb];
1352 + vc = pa[(ea+2) % na];
1353 + if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
1354 + return -1;
1355 +
1356 + va = pa[ea];
1357 + vb = pa[(ea+1)%na];
1358 +
1359 + int dx = (int)verts[va*3+0] - (int)verts[vb*3+0];
1360 + int dy = (int)verts[va*3+2] - (int)verts[vb*3+2];
1361 +
1362 + return dx*dx + dy*dy;
1363 1363 }
1364 1364
1365 1365 static void mergePolys(unsigned short* pa, unsigned short* pb, int ea, int eb)
1366 1366 {
1367 - unsigned short tmp[MAX_VERTS_PER_POLY*2];
1368 -
1369 - const int na = countPolyVerts(pa);
1370 - const int nb = countPolyVerts(pb);
1371 -
1372 - // Merge polygons.
1373 - memset(tmp, 0xff, sizeof(unsigned short)*MAX_VERTS_PER_POLY*2);
1374 - int n = 0;
1375 - // Add pa
1376 - for (int i = 0; i < na-1; ++i)
1377 - tmp[n++] = pa[(ea+1+i) % na];
1378 - // Add pb
1379 - for (int i = 0; i < nb-1; ++i)
1380 - tmp[n++] = pb[(eb+1+i) % nb];
1381 -
1382 - memcpy(pa, tmp, sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1367 + unsigned short tmp[MAX_VERTS_PER_POLY*2];
1368 +
1369 + const int na = countPolyVerts(pa);
1370 + const int nb = countPolyVerts(pb);
1371 +
1372 + // Merge polygons.
1373 + memset(tmp, 0xff, sizeof(unsigned short)*MAX_VERTS_PER_POLY*2);
1374 + int n = 0;
1375 + // Add pa
1376 + for (int i = 0; i < na-1; ++i)
1377 + tmp[n++] = pa[(ea+1+i) % na];
1378 + // Add pb
1379 + for (int i = 0; i < nb-1; ++i)
1380 + tmp[n++] = pb[(eb+1+i) % nb];
1381 +
1382 + memcpy(pa, tmp, sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1383 1383 }
1384 1384
1385 1385
1386 1386 static void pushFront(unsigned short v, unsigned short* arr, int& an)
1387 1387 {
1388 - an++;
1389 - for (int i = an-1; i > 0; --i)
1390 - arr[i] = arr[i-1];
1391 - arr[0] = v;
1388 + an++;
1389 + for (int i = an-1; i > 0; --i)
1390 + arr[i] = arr[i-1];
1391 + arr[0] = v;
1392 1392 }
1393 1393
1394 1394 static void pushBack(unsigned short v, unsigned short* arr, int& an)
1395 1395 {
1396 - arr[an] = v;
1397 - an++;
1396 + arr[an] = v;
1397 + an++;
1398 1398 }
1399 1399
1400 1400 static bool canRemoveVertex(dtTileCachePolyMesh& mesh, const unsigned short rem)
1401 1401 {
1402 - // Count number of polygons to remove.
1403 - int numRemovedVerts = 0;
1404 - int numTouchedVerts = 0;
1405 - int numRemainingEdges = 0;
1406 - for (int i = 0; i < mesh.npolys; ++i)
1407 - {
1408 - unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1409 - const int nv = countPolyVerts(p);
1410 - int numRemoved = 0;
1411 - int numVerts = 0;
1412 - for (int j = 0; j < nv; ++j)
1413 - {
1414 - if (p[j] == rem)
1415 - {
1416 - numTouchedVerts++;
1417 - numRemoved++;
1418 - }
1419 - numVerts++;
1420 - }
1421 - if (numRemoved)
1422 - {
1423 - numRemovedVerts += numRemoved;
1424 - numRemainingEdges += numVerts-(numRemoved+1);
1425 - }
1426 - }
1427 -
1428 - // There would be too few edges remaining to create a polygon.
1429 - // This can happen for example when a tip of a triangle is marked
1430 - // as deletion, but there are no other polys that share the vertex.
1431 - // In this case, the vertex should not be removed.
1432 - if (numRemainingEdges <= 2)
1433 - return false;
1434 -
1435 - // Check that there is enough memory for the test.
1436 - const int maxEdges = numTouchedVerts*2;
1437 - if (maxEdges > MAX_REM_EDGES)
1438 - return false;
1439 -
1440 - // Find edges which share the removed vertex.
1441 - unsigned short edges[MAX_REM_EDGES];
1442 - int nedges = 0;
1443 -
1444 - for (int i = 0; i < mesh.npolys; ++i)
1445 - {
1446 - unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1447 - const int nv = countPolyVerts(p);
1448 -
1449 - // Collect edges which touches the removed vertex.
1450 - for (int j = 0, k = nv-1; j < nv; k = j++)
1451 - {
1452 - if (p[j] == rem || p[k] == rem)
1453 - {
1454 - // Arrange edge so that a=rem.
1455 - int a = p[j], b = p[k];
1456 - if (b == rem)
1457 - dtSwap(a,b);
1458 -
1459 - // Check if the edge exists
1460 - bool exists = false;
1461 - for (int m = 0; m < nedges; ++m)
1462 - {
1463 - unsigned short* e = &edges[m*3];
1464 - if (e[1] == b)
1465 - {
1466 - // Exists, increment vertex share count.
1467 - e[2]++;
1468 - exists = true;
1469 - }
1470 - }
1471 - // Add new edge.
1472 - if (!exists)
1473 - {
1474 - unsigned short* e = &edges[nedges*3];
1475 - e[0] = (unsigned short)a;
1476 - e[1] = (unsigned short)b;
1477 - e[2] = 1;
1478 - nedges++;
1479 - }
1480 - }
1481 - }
1482 - }
1483 -
1484 - // There should be no more than 2 open edges.
1485 - // This catches the case that two non-adjacent polygons
1486 - // share the removed vertex. In that case, do not remove the vertex.
1487 - int numOpenEdges = 0;
1488 - for (int i = 0; i < nedges; ++i)
1489 - {
1490 - if (edges[i*3+2] < 2)
1491 - numOpenEdges++;
1492 - }
1493 - if (numOpenEdges > 2)
1494 - return false;
1495 -
1496 - return true;
1402 + // Count number of polygons to remove.
1403 + int numRemovedVerts = 0;
1404 + int numTouchedVerts = 0;
1405 + int numRemainingEdges = 0;
1406 + for (int i = 0; i < mesh.npolys; ++i)
1407 + {
1408 + unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1409 + const int nv = countPolyVerts(p);
1410 + int numRemoved = 0;
1411 + int numVerts = 0;
1412 + for (int j = 0; j < nv; ++j)
1413 + {
1414 + if (p[j] == rem)
1415 + {
1416 + numTouchedVerts++;
1417 + numRemoved++;
1418 + }
1419 + numVerts++;
1420 + }
1421 + if (numRemoved)
1422 + {
1423 + numRemovedVerts += numRemoved;
1424 + numRemainingEdges += numVerts-(numRemoved+1);
1425 + }
1426 + }
1427 +
1428 + // There would be too few edges remaining to create a polygon.
1429 + // This can happen for example when a tip of a triangle is marked
1430 + // as deletion, but there are no other polys that share the vertex.
1431 + // In this case, the vertex should not be removed.
1432 + if (numRemainingEdges <= 2)
1433 + return false;
1434 +
1435 + // Check that there is enough memory for the test.
1436 + const int maxEdges = numTouchedVerts*2;
1437 + if (maxEdges > MAX_REM_EDGES)
1438 + return false;
1439 +
1440 + // Find edges which share the removed vertex.
1441 + unsigned short edges[MAX_REM_EDGES];
1442 + int nedges = 0;
1443 +
1444 + for (int i = 0; i < mesh.npolys; ++i)
1445 + {
1446 + unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1447 + const int nv = countPolyVerts(p);
1448 +
1449 + // Collect edges which touches the removed vertex.
1450 + for (int j = 0, k = nv-1; j < nv; k = j++)
1451 + {
1452 + if (p[j] == rem || p[k] == rem)
1453 + {
1454 + // Arrange edge so that a=rem.
1455 + int a = p[j], b = p[k];
1456 + if (b == rem)
1457 + dtSwap(a,b);
1458 +
1459 + // Check if the edge exists
1460 + bool exists = false;
1461 + for (int m = 0; m < nedges; ++m)
1462 + {
1463 + unsigned short* e = &edges[m*3];
1464 + if (e[1] == b)
1465 + {
1466 + // Exists, increment vertex share count.
1467 + e[2]++;
1468 + exists = true;
1469 + }
1470 + }
1471 + // Add new edge.
1472 + if (!exists)
1473 + {
1474 + unsigned short* e = &edges[nedges*3];
1475 + e[0] = (unsigned short)a;
1476 + e[1] = (unsigned short)b;
1477 + e[2] = 1;
1478 + nedges++;
1479 + }
1480 + }
1481 + }
1482 + }
1483 +
1484 + // There should be no more than 2 open edges.
1485 + // This catches the case that two non-adjacent polygons
1486 + // share the removed vertex. In that case, do not remove the vertex.
1487 + int numOpenEdges = 0;
1488 + for (int i = 0; i < nedges; ++i)
1489 + {
1490 + if (edges[i*3+2] < 2)
1491 + numOpenEdges++;
1492 + }
1493 + if (numOpenEdges > 2)
1494 + return false;
1495 +
1496 + return true;
1497 1497 }
1498 1498
1499 1499 static dtStatus removeVertex(dtTileCachePolyMesh& mesh, const unsigned short rem, const int maxTris)
1500 1500 {
1501 - // Count number of polygons to remove.
1502 - int numRemovedVerts = 0;
1503 - for (int i = 0; i < mesh.npolys; ++i)
1504 - {
1505 - unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1506 - const int nv = countPolyVerts(p);
1507 - for (int j = 0; j < nv; ++j)
1508 - {
1509 - if (p[j] == rem)
1510 - numRemovedVerts++;
1511 - }
1512 - }
1513 -
1514 - int nedges = 0;
1515 - unsigned short edges[MAX_REM_EDGES*3];
1516 - int nhole = 0;
1517 - unsigned short hole[MAX_REM_EDGES];
1518 - int nharea = 0;
1519 - unsigned short harea[MAX_REM_EDGES];
1520 -
1521 - for (int i = 0; i < mesh.npolys; ++i)
1522 - {
1523 - unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1524 - const int nv = countPolyVerts(p);
1525 - bool hasRem = false;
1526 - for (int j = 0; j < nv; ++j)
1527 - if (p[j] == rem) hasRem = true;
1528 - if (hasRem)
1529 - {
1530 - // Collect edges which does not touch the removed vertex.
1531 - for (int j = 0, k = nv-1; j < nv; k = j++)
1532 - {
1533 - if (p[j] != rem && p[k] != rem)
1534 - {
1535 - if (nedges >= MAX_REM_EDGES)
1536 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
1537 - unsigned short* e = &edges[nedges*3];
1538 - e[0] = p[k];
1539 - e[1] = p[j];
1540 - e[2] = mesh.areas[i];
1541 - nedges++;
1542 - }
1543 - }
1544 - // Remove the polygon.
1545 - unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*MAX_VERTS_PER_POLY*2];
1546 - memcpy(p,p2,sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1547 - memset(p+MAX_VERTS_PER_POLY,0xff,sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1548 - mesh.areas[i] = mesh.areas[mesh.npolys-1];
1549 - mesh.npolys--;
1550 - --i;
1551 - }
1552 - }
1553 -
1554 - // Remove vertex.
1555 - for (int i = (int)rem; i < mesh.nverts; ++i)
1556 - {
1557 - mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0];
1558 - mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1];
1559 - mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2];
1560 - }
1561 - mesh.nverts--;
1562 -
1563 - // Adjust indices to match the removed vertex layout.
1564 - for (int i = 0; i < mesh.npolys; ++i)
1565 - {
1566 - unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1567 - const int nv = countPolyVerts(p);
1568 - for (int j = 0; j < nv; ++j)
1569 - if (p[j] > rem) p[j]--;
1570 - }
1571 - for (int i = 0; i < nedges; ++i)
1572 - {
1573 - if (edges[i*3+0] > rem) edges[i*3+0]--;
1574 - if (edges[i*3+1] > rem) edges[i*3+1]--;
1575 - }
1576 -
1577 - if (nedges == 0)
1578 - return DT_SUCCESS;
1579 -
1580 - // Start with one vertex, keep appending connected
1581 - // segments to the start and end of the hole.
1582 - pushBack(edges[0], hole, nhole);
1583 - pushBack(edges[2], harea, nharea);
1584 -
1585 - while (nedges)
1586 - {
1587 - bool match = false;
1588 -
1589 - for (int i = 0; i < nedges; ++i)
1590 - {
1591 - const unsigned short ea = edges[i*3+0];
1592 - const unsigned short eb = edges[i*3+1];
1593 - const unsigned short a = edges[i*3+2];
1594 - bool add = false;
1595 - if (hole[0] == eb)
1596 - {
1597 - // The segment matches the beginning of the hole boundary.
1598 - if (nhole >= MAX_REM_EDGES)
1599 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
1600 - pushFront(ea, hole, nhole);
1601 - pushFront(a, harea, nharea);
1602 - add = true;
1603 - }
1604 - else if (hole[nhole-1] == ea)
1605 - {
1606 - // The segment matches the end of the hole boundary.
1607 - if (nhole >= MAX_REM_EDGES)
1608 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
1609 - pushBack(eb, hole, nhole);
1610 - pushBack(a, harea, nharea);
1611 - add = true;
1612 - }
1613 - if (add)
1614 - {
1615 - // The edge segment was added, remove it.
1616 - edges[i*3+0] = edges[(nedges-1)*3+0];
1617 - edges[i*3+1] = edges[(nedges-1)*3+1];
1618 - edges[i*3+2] = edges[(nedges-1)*3+2];
1619 - --nedges;
1620 - match = true;
1621 - --i;
1622 - }
1623 - }
1624 -
1625 - if (!match)
1626 - break;
1627 - }
1628 -
1629 -
1630 - unsigned short tris[MAX_REM_EDGES*3];
1631 - unsigned char tverts[MAX_REM_EDGES*3];
1632 - unsigned short tpoly[MAX_REM_EDGES*3];
1633 -
1634 - // Generate temp vertex array for triangulation.
1635 - for (int i = 0; i < nhole; ++i)
1636 - {
1637 - const unsigned short pi = hole[i];
1638 - tverts[i*4+0] = (unsigned char)mesh.verts[pi*3+0];
1639 - tverts[i*4+1] = (unsigned char)mesh.verts[pi*3+1];
1640 - tverts[i*4+2] = (unsigned char)mesh.verts[pi*3+2];
1641 - tverts[i*4+3] = 0;
1642 - tpoly[i] = (unsigned short)i;
1643 - }
1644 -
1645 - // Triangulate the hole.
1646 - int ntris = triangulate(nhole, tverts, tpoly, tris);
1647 - if (ntris < 0)
1648 - {
1649 - // TODO: issue warning!
1650 - ntris = -ntris;
1651 - }
1652 -
1653 - if (ntris > MAX_REM_EDGES)
1654 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
1655 -
1656 - unsigned short polys[MAX_REM_EDGES*MAX_VERTS_PER_POLY];
1657 - unsigned char pareas[MAX_REM_EDGES];
1658 -
1659 - // Build initial polygons.
1660 - int npolys = 0;
1661 - memset(polys, 0xff, ntris*MAX_VERTS_PER_POLY*sizeof(unsigned short));
1662 - for (int j = 0; j < ntris; ++j)
1663 - {
1664 - unsigned short* t = &tris[j*3];
1665 - if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
1666 - {
1667 - polys[npolys*MAX_VERTS_PER_POLY+0] = hole[t[0]];
1668 - polys[npolys*MAX_VERTS_PER_POLY+1] = hole[t[1]];
1669 - polys[npolys*MAX_VERTS_PER_POLY+2] = hole[t[2]];
1670 - pareas[npolys] = (unsigned char)harea[t[0]];
1671 - npolys++;
1672 - }
1673 - }
1674 - if (!npolys)
1675 - return DT_SUCCESS;
1676 -
1677 - // Merge polygons.
1678 - int maxVertsPerPoly = MAX_VERTS_PER_POLY;
1679 - if (maxVertsPerPoly > 3)
1680 - {
1681 - for (;;)
1682 - {
1683 - // Find best polygons to merge.
1684 - int bestMergeVal = 0;
1685 - int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
1686 -
1687 - for (int j = 0; j < npolys-1; ++j)
1688 - {
1689 - unsigned short* pj = &polys[j*MAX_VERTS_PER_POLY];
1690 - for (int k = j+1; k < npolys; ++k)
1691 - {
1692 - unsigned short* pk = &polys[k*MAX_VERTS_PER_POLY];
1693 - int ea, eb;
1694 - int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb);
1695 - if (v > bestMergeVal)
1696 - {
1697 - bestMergeVal = v;
1698 - bestPa = j;
1699 - bestPb = k;
1700 - bestEa = ea;
1701 - bestEb = eb;
1702 - }
1703 - }
1704 - }
1705 -
1706 - if (bestMergeVal > 0)
1707 - {
1708 - // Found best, merge.
1709 - unsigned short* pa = &polys[bestPa*MAX_VERTS_PER_POLY];
1710 - unsigned short* pb = &polys[bestPb*MAX_VERTS_PER_POLY];
1711 - mergePolys(pa, pb, bestEa, bestEb);
1712 - memcpy(pb, &polys[(npolys-1)*MAX_VERTS_PER_POLY], sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1713 - pareas[bestPb] = pareas[npolys-1];
1714 - npolys--;
1715 - }
1716 - else
1717 - {
1718 - // Could not merge any polygons, stop.
1719 - break;
1720 - }
1721 - }
1722 - }
1723 -
1724 - // Store polygons.
1725 - for (int i = 0; i < npolys; ++i)
1726 - {
1727 - if (mesh.npolys >= maxTris) break;
1728 - unsigned short* p = &mesh.polys[mesh.npolys*MAX_VERTS_PER_POLY*2];
1729 - memset(p,0xff,sizeof(unsigned short)*MAX_VERTS_PER_POLY*2);
1730 - for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
1731 - p[j] = polys[i*MAX_VERTS_PER_POLY+j];
1732 - mesh.areas[mesh.npolys] = pareas[i];
1733 - mesh.npolys++;
1734 - if (mesh.npolys > maxTris)
1735 - return DT_FAILURE | DT_BUFFER_TOO_SMALL;
1736 - }
1737 -
1738 - return DT_SUCCESS;
1501 + // Count number of polygons to remove.
1502 + int numRemovedVerts = 0;
1503 + for (int i = 0; i < mesh.npolys; ++i)
1504 + {
1505 + unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1506 + const int nv = countPolyVerts(p);
1507 + for (int j = 0; j < nv; ++j)
1508 + {
1509 + if (p[j] == rem)
1510 + numRemovedVerts++;
1511 + }
1512 + }
1513 +
1514 + int nedges = 0;
1515 + unsigned short edges[MAX_REM_EDGES*3];
1516 + int nhole = 0;
1517 + unsigned short hole[MAX_REM_EDGES];
1518 + int nharea = 0;
1519 + unsigned short harea[MAX_REM_EDGES];
1520 +
1521 + for (int i = 0; i < mesh.npolys; ++i)
1522 + {
1523 + unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1524 + const int nv = countPolyVerts(p);
1525 + bool hasRem = false;
1526 + for (int j = 0; j < nv; ++j)
1527 + if (p[j] == rem) hasRem = true;
1528 + if (hasRem)
1529 + {
1530 + // Collect edges which does not touch the removed vertex.
1531 + for (int j = 0, k = nv-1; j < nv; k = j++)
1532 + {
1533 + if (p[j] != rem && p[k] != rem)
1534 + {
1535 + if (nedges >= MAX_REM_EDGES)
1536 + return DT_FAILURE | DT_BUFFER_TOO_SMALL;
1537 + unsigned short* e = &edges[nedges*3];
1538 + e[0] = p[k];
1539 + e[1] = p[j];
1540 + e[2] = mesh.areas[i];
1541 + nedges++;
1542 + }
1543 + }
1544 + // Remove the polygon.
1545 + unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*MAX_VERTS_PER_POLY*2];
1546 + memcpy(p,p2,sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1547 + memset(p+MAX_VERTS_PER_POLY,0xff,sizeof(unsigned short)*MAX_VERTS_PER_POLY);
1548 + mesh.areas[i] = mesh.areas[mesh.npolys-1];
1549 + mesh.npolys--;
1550 + --i;
1551 + }
1552 + }
1553 +
1554 + // Remove vertex.
1555 + for (int i = (int)rem; i < mesh.nverts; ++i)
1556 + {
1557 + mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0];
1558 + mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1];
1559 + mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2];
1560 + }
1561 + mesh.nverts--;
1562 +
1563 + // Adjust indices to match the removed vertex layout.
1564 + for (int i = 0; i < mesh.npolys; ++i)
1565 + {
1566 + unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
1567 + const int nv = countPolyVerts(p);
1568 + for (int j = 0; j < nv; ++j)
1569 + if (p[j] > rem) p[j]--;
1570 + }
1571 + for (int i = 0; i < nedges; ++i)
1572