BRL-CAD
uvpoints.cpp
Go to the documentation of this file.
1 /* U V P O I N T S . C P P
2  * BRL-CAD
3  *
4  * Copyright (c) 2010-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 /* test routines related to quad trees and uv points for NURBS - this
22  * is not the final form of this code, just testing.
23  */
24 
25 #include "common.h"
26 
27 #include <iostream>
28 #include <string>
29 #include <fstream>
30 #include <iomanip>
31 #include <vector>
32 #include <set>
33 #include <list>
34 #include <math.h>
35 #include <time.h>
36 
37 #define POOL_SIZE 1024
38 
39 
40 /* Number of subdivisions to perform */
41 /*#define MAX_TREE_DEPTH 6*/
42 #define TREE_DEBUG 0
43 int rejected = 0;
44 int counting = 0;
45 
46 /* For memory management stuff see the tutorial at
47  * http://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/section9.html */
49 {
50 private:
51  std::list<void*> QuadNodePtrList;
52  std::vector<void*> MemoryPoolList;
53 public:
56  void* allocate(size_t);
57  void free(void*);
58 };
59 
60 
61 void* MemoryManager::allocate(size_t size)
62 {
63  void* base = 0;
64  if (QuadNodePtrList.empty()) {
65  base = new char[size * POOL_SIZE];
66  MemoryPoolList.push_back(base);
67  for (int i = 0; i < POOL_SIZE; ++i) {
68  QuadNodePtrList.push_front(&(static_cast<char*>(base)[i*size]));
69  }
70  }
71  void* blockPtr = QuadNodePtrList.front();
72  /* *((static_cast<QuadNode*>(blockPtr)) + sizeof(QuadNode) - 2) = sizeof(QuadNode);
73  *((static_cast<QuadNode*>(blockPtr)) + sizeof(QuadNode) - 1) = 0;*/
74  QuadNodePtrList.pop_front();
75  return blockPtr;
76 }
77 
78 
79 void MemoryManager::free(void* object)
80 {
81  QuadNodePtrList.push_front(object);
82 }
83 
84 
86 
87 /**
88  * UVKey Class - minimal class for holding UV space coordinate keys
89  */
90 
91 class UVKey {
92 public:
93  UVKey(std::string newkey);
94  const std::string& getKey() const;
95 private:
96  std::string key;
97 };
98 
99 
100 UVKey::UVKey(std::string newkey)
101 {
102  key.assign(newkey);
103 }
104 
105 
106 const std::string& UVKey::getKey() const
107 {
108  const std::string& keyref = key;
109  return keyref;
110 }
111 
112 
113 /**
114  * UVKeyComp - Tell the C++ set how to compare keys for sorting
115  */
116 class UVKeyComp {
117 public:
118  bool operator()(const UVKey& key1, const UVKey& key2)
119  {
120  if (key1.getKey().compare(key2.getKey()) < 0) {
121  return true;
122  } else {
123  return false;
124  }
125  }
126 };
127 
128 
129 /**
130  * QuadNode - Holds information about the UV coordinates associated with
131  * a node in a subdivision quad tree. Assumes the following relationship
132  * between point indices and positioning:
133  *
134  *
135  * 3-------------------2
136  * | |
137  * | 6 8 |
138  * | |
139  * V | 4 |
140  * | |
141  * | 5 7 |
142  * | |
143  * 0-------------------1
144  * U
145  *
146  */
147 
148 class QuadNode {
149 public:
150  void SubDivide(int MAX_TREE_DEPTH);
151  std::set<UVKey, UVKeyComp> *keys;
152  void AppendKeys(std::set <UVKey, UVKeyComp> *keys, int MAX_TREE_DEPTH);
153  size_t PU[9];
154  size_t PV[9];
155  int depth;
157  inline void* operator new(size_t)
158  {
159  return QuadMemoryManager.allocate(sizeof(QuadNode));
160  }
161  inline void operator delete(void* object)
162  {
163  QuadMemoryManager.free(object);
164  }
165 };
166 
167 
168 void ints_to_key(std::string *cppstr, int left, int right, int MAX_TREE_DEPTH)
169 {
170  char formatstring[20];
171  char maxkeystr[20];
172  char finalstring[20];
173  int max_key_length;
174  int max_key = pow(2, MAX_TREE_DEPTH + 1);
175  sprintf(maxkeystr, "%d", max_key);
176  max_key_length = strlen(maxkeystr);
177  sprintf(formatstring, "%%\'0%dd%%\'0%dd", max_key_length, max_key_length);
178  sprintf(finalstring, formatstring, left, right);
179  cppstr->assign(finalstring);
180 }
181 
182 
183 void QuadNode::AppendKeys(std::set<UVKey, UVKeyComp> *newkeys, int MAX_TREE_DEPTH)
184 {
185  UVKey *point;
186  std::set<UVKey, UVKeyComp>::iterator item;
187  std::string keystring;
188 
189  for (int i = 0; i < 9; i++) {
190  counting++;
191  ints_to_key(&keystring, PU[i], PV[i], MAX_TREE_DEPTH);
192  item = newkeys->find(keystring);
193  if (item == newkeys->end()) {
194  point = new UVKey(keystring);
195  /* FIXME: newkeys was keys, but shadows member data.
196  * which were we inserting into here?
197  */
198  newkeys->insert(*point);
199  } else {
200  rejected++;
201  }
202  keystring.erase();
203  }
204 }
205 
206 
207 /*
208  * When subdivision is made, parent coordinate values are used
209  * to deduce those of the children. Some are direct copies, as
210  * follows (this relates quadrant conventions to the above diagram
211  * identifying point positions by number)
212  *
213  * 3---------------- ----------------2
214  * | | | |
215  * | | | |
216  * V | 6 | | 8 |
217  * | | | |
218  * | | | |
219  * ----------------4 4----------------
220  * U U
221  *
222  * Quadrant 3 Quadrant 2
223  *
224  * ----------------4 4----------------
225  * | | | |
226  * | | | |
227  * V | 5 | | 7 |
228  * | | | |
229  * | | | |
230  * 0---------------- ----------------1
231  * U U
232  *
233  * Quadrant 0 Quadrant 1
234  */
235 
236 void QuadNode::SubDivide(int MAX_TREE_DEPTH)
237 {
238  /* Quadrant 0 */
239  Children[0] = new QuadNode();
240  Children[0]->depth = depth + 1;
241  Children[0]->keys = keys;
242  Children[0]->PU[0] = PU[0];
243  Children[0]->PV[0] = PV[0];
244  Children[0]->PU[1] = PU[4];
245  Children[0]->PV[1] = PV[0];
246  Children[0]->PU[2] = PU[4];
247  Children[0]->PV[2] = PV[4];
248  Children[0]->PU[3] = PU[0];
249  Children[0]->PV[3] = PV[4];
250  Children[0]->PU[4] = PU[5];
251  Children[0]->PV[4] = PV[5];
252  Children[0]->PU[5] = (Children[0]->PU[4] - Children[0]->PU[0])/2 + Children[0]->PU[0];
253  Children[0]->PV[5] = (Children[0]->PV[4] - Children[0]->PV[0])/2 + Children[0]->PV[0];
254  Children[0]->PU[6] = Children[0]->PU[5];
255  Children[0]->PV[6] = 3*(Children[0]->PV[4] - Children[0]->PV[0])/2 + Children[0]->PV[0];
256  Children[0]->PU[7] = 3*(Children[0]->PU[4] - Children[0]->PU[0])/2 + Children[0]->PU[0];
257  Children[0]->PV[7] = Children[0]->PV[5];
258  Children[0]->PU[8] = Children[0]->PU[7];
259  Children[0]->PV[8] = Children[0]->PV[6];
260  Children[0]->AppendKeys(keys, MAX_TREE_DEPTH);
261 #if TREE_DEBUG
262  cout << "Q0 Depth: " << depth + 1 << "\n";
263  cout << "PU: {";
264  for (int i = 0; i < 9; i++) {
265  cout << Children[0]->PU[i] << ", ";
266  }
267  cout << "}\n";
268  cout << "PV: {";
269  for (int i = 0; i < 9; i++) {
270  cout << Children[0]->PV[i] << ", ";
271  }
272  cout << "}\n";
273 #endif
274  if (Children[0]->depth < MAX_TREE_DEPTH)
275  Children[0]->SubDivide(MAX_TREE_DEPTH);
276 
277 
278  /* Quadrant 1 */
279  Children[1] = new QuadNode();
280  Children[1]->depth = depth + 1;
281  Children[1]->keys = keys;
282  Children[1]->PU[0] = PU[4];
283  Children[1]->PV[0] = PV[1];
284  Children[1]->PU[1] = PU[1];
285  Children[1]->PV[1] = PV[1];
286  Children[1]->PU[2] = PU[1];
287  Children[1]->PV[2] = PV[4];
288  Children[1]->PU[3] = PU[4];
289  Children[1]->PV[3] = PV[4];
290  Children[1]->PU[4] = PU[7];
291  Children[1]->PV[4] = PV[7];
292  Children[1]->PU[5] = (Children[1]->PU[4] - Children[1]->PU[0])/2 + Children[1]->PU[0];
293  Children[1]->PV[5] = (Children[1]->PV[4] - Children[1]->PV[0])/2 + Children[1]->PV[0];
294  Children[1]->PU[6] = Children[1]->PU[5];
295  Children[1]->PV[6] = 3*(Children[1]->PV[4] - Children[1]->PV[0])/2 + Children[1]->PV[0];
296  Children[1]->PU[7] = 3*(Children[1]->PU[4] - Children[1]->PU[0])/2 + Children[1]->PU[0];
297  Children[1]->PV[7] = Children[1]->PV[5];
298  Children[1]->PU[8] = Children[1]->PU[7];
299  Children[1]->PV[8] = Children[1]->PV[6];
300  Children[1]->AppendKeys(keys, MAX_TREE_DEPTH);
301 #if TREE_DEBUG
302  cout << "Q1 Depth: " << depth + 1 << "\n";
303  cout << "PU: {";
304  for (int i = 0; i < 9; i++) {
305  cout << Children[1]->PU[i] << ", ";
306  }
307  cout << "}\n";
308  cout << "PV: {";
309  for (int i = 0; i < 9; i++) {
310  cout << Children[1]->PV[i] << ", ";
311  }
312  cout << "}\n";
313 #endif
314  if (Children[1]->depth < MAX_TREE_DEPTH)
315  Children[1]->SubDivide(MAX_TREE_DEPTH);
316 
317  /* Quadrant 2 */
318  Children[2] = new QuadNode();
319  Children[2]->depth = depth + 1;
320  Children[2]->keys = keys;
321  Children[2]->PU[0] = PU[4];
322  Children[2]->PV[0] = PV[4];
323  Children[2]->PU[1] = PU[2];
324  Children[2]->PV[1] = PV[4];
325  Children[2]->PU[2] = PU[2];
326  Children[2]->PV[2] = PV[2];
327  Children[2]->PU[3] = PU[4];
328  Children[2]->PV[3] = PV[2];
329  Children[2]->PU[4] = PU[8];
330  Children[2]->PV[4] = PV[8];
331  Children[2]->PU[5] = (Children[2]->PU[4] - Children[2]->PU[0])/2 + Children[2]->PU[0];
332  Children[2]->PV[5] = (Children[2]->PV[4] - Children[2]->PV[0])/2 + Children[2]->PV[0];
333  Children[2]->PU[6] = Children[2]->PU[5];
334  Children[2]->PV[6] = 3*(Children[2]->PV[4] - Children[2]->PV[0])/2 + Children[2]->PV[0];
335  Children[2]->PU[7] = 3*(Children[2]->PU[4] - Children[2]->PU[0])/2 + Children[2]->PU[0];
336  Children[2]->PV[7] = Children[2]->PV[5];
337  Children[2]->PU[8] = Children[2]->PU[7];
338  Children[2]->PV[8] = Children[2]->PV[6];
339  Children[2]->AppendKeys(keys, MAX_TREE_DEPTH);
340 #if TREE_DEBUG
341  cout << "Q2 Depth: " << depth + 1 << "\n";
342  cout << "PU: {";
343  for (int i = 0; i < 9; i++) {
344  cout << Children[2]->PU[i] << ", ";
345  }
346  cout << "}\n";
347  cout << "PV: {";
348  for (int i = 0; i < 9; i++) {
349  cout << Children[2]->PV[i] << ", ";
350  }
351  cout << "}\n";
352 #endif
353 
354  if (Children[2]->depth < MAX_TREE_DEPTH)
355  Children[2]->SubDivide(MAX_TREE_DEPTH);
356 
357  /* Quadrant 3 */
358  Children[3] = new QuadNode();
359  Children[3]->depth = depth + 1;
360  Children[3]->keys = keys;
361  Children[3]->PU[0] = PU[3];
362  Children[3]->PV[0] = PV[4];
363  Children[3]->PU[1] = PU[4];
364  Children[3]->PV[1] = PV[4];
365  Children[3]->PU[2] = PU[4];
366  Children[3]->PV[2] = PV[3];
367  Children[3]->PU[3] = PU[3];
368  Children[3]->PV[3] = PV[3];
369  Children[3]->PU[4] = PU[6];
370  Children[3]->PV[4] = PV[6];
371  Children[3]->PU[5] = (Children[3]->PU[4] - Children[3]->PU[0])/2 + Children[3]->PU[0];
372  Children[3]->PV[5] = (Children[3]->PV[4] - Children[3]->PV[0])/2 + Children[3]->PV[0];
373  Children[3]->PU[6] = Children[3]->PU[5];
374  Children[3]->PV[6] = 3*(Children[3]->PV[4] - Children[3]->PV[0])/2 + Children[3]->PV[0];
375  Children[3]->PU[7] = 3*(Children[3]->PU[4] - Children[3]->PU[0])/2 + Children[3]->PU[0];
376  Children[3]->PV[7] = Children[3]->PV[5];
377  Children[3]->PU[8] = Children[3]->PU[7];
378  Children[3]->PV[8] = Children[3]->PV[6];
379  Children[3]->AppendKeys(keys, MAX_TREE_DEPTH);
380 #if TREE_DEBUG
381  cout << "Q3 Depth: " << depth + 1 << "\n";
382  cout << "PU: {";
383  for (int i = 0; i < 9; i++) {
384  cout << Children[3]->PU[i] << ", ";
385  }
386  cout << "}\n";
387  cout << "PV: {";
388  for (int i = 0; i < 9; i++) {
389  cout << Children[3]->PV[i] << ", ";
390  }
391  cout << "}\n";
392 #endif
393 
394  if (Children[3]->depth < MAX_TREE_DEPTH)
395  Children[3]->SubDivide(MAX_TREE_DEPTH);
396 
397 }
398 
399 
400 /**
401  * UVKeyQuadTree - This holds a bounding box subdivision tree using
402  * a quad tree on a generic UV space - this is used to identify keys that
403  * will potentially need to have points evaluated for a real surface tree
404  * build
405  */
407 public:
408  UVKeyQuadTree(std::set<UVKey, UVKeyComp> *keys, int MAX_TREE_DEPTH);
410 };
411 
412 
413 UVKeyQuadTree::UVKeyQuadTree(std::set<UVKey, UVKeyComp> *keys, int MAX_TREE_DEPTH)
414 {
415  UVKey *point;
416  std::set<UVKey, UVKeyComp>::iterator item;
417  std::string keynum;
418 
419  root = new QuadNode();
420  root->depth = 0;
421  root->keys = keys;
422  root->PU[0] = 0;
423  root->PV[0] = 0;
424  root->PU[1] = pow(2, MAX_TREE_DEPTH + 1);
425  root->PV[1] = 0;
426  root->PU[2] = pow(2, MAX_TREE_DEPTH + 1);
427  root->PV[2] = pow(2, MAX_TREE_DEPTH + 1);
428  root->PU[3] = 0;
429  root->PV[3] = pow(2, MAX_TREE_DEPTH + 1);
430  root->PU[4] = pow(2, MAX_TREE_DEPTH + 1)/2;
431  root->PV[4] = pow(2, MAX_TREE_DEPTH + 1)/2;
432  root->PU[5] = pow(2, MAX_TREE_DEPTH + 1)/4;
433  root->PV[5] = pow(2, MAX_TREE_DEPTH + 1)/4;
434  root->PU[6] = pow(2, MAX_TREE_DEPTH + 1)/4;
435  root->PV[6] = 3*pow(2, MAX_TREE_DEPTH + 1)/4;
436  root->PU[7] = 3*pow(2, MAX_TREE_DEPTH + 1)/4;
437  root->PV[7] = pow(2, MAX_TREE_DEPTH + 1)/4;
438  root->PU[8] = 3*pow(2, MAX_TREE_DEPTH + 1)/4;
439  root->PV[8] = 3*pow(2, MAX_TREE_DEPTH + 1)/4;
440  for (int i = 0; i < 9; i++) {
441  counting++;
442  std::cout << root->PU[i] << ", " << root->PV[i] << "\n";
443  ints_to_key(&keynum, root->PU[i], root->PV[i], MAX_TREE_DEPTH);
444  item = keys->find(keynum);
445  if (item == keys->end()) {
446  point = new UVKey(keynum);
447  keys->insert(*point);
448  }
449  keynum.erase();
450  }
451 }
452 
453 
454 int main(int argc, char **argv)
455 {
456  int matsize;
457  time_t t0, t1;
458  int MAX_TREE_DEPTH, tdiff;
459  if (argc == 1) {
460  MAX_TREE_DEPTH = 2;
461  } else {
462  MAX_TREE_DEPTH = atoi(argv[1]);
463  }
464  t0 = time(NULL);
465  t1 = time(NULL);
466  matsize = pow(2, MAX_TREE_DEPTH + 1) + 1;
467  std::vector<std::vector<int> > matitems (matsize , std::vector<int> (matsize));
468  int k = 0;
469 
470  std::cout << "Max tree depth: " << MAX_TREE_DEPTH << "\n";
471  if (MAX_TREE_DEPTH < 3) {
472  std::cout << "Matrix: \n";
473  for (int i = 0; i < matsize; i++) {
474  for (int j = 0; j < matsize; j++)
475  matitems[i][j] = k++;
476  }
477 
478  for (int i = matsize - 1; i >= 0; i--) {
479  for (int j = 0; j < matsize; j++)
480  std::cout<< std::setw (MAX_TREE_DEPTH) << std::setfill('0') << j << ", " << std::setw (MAX_TREE_DEPTH) << std::setfill('0') << i <<' ';
481  std::cout<<'\n';
482  }
483  std::cout<<'\n';
484  }
485 
486 
487  std::set <UVKey, UVKeyComp> keys;
488  std::set<UVKey, UVKeyComp>::iterator keyiterator;
489  UVKeyQuadTree *testtree = new UVKeyQuadTree(&keys, MAX_TREE_DEPTH);
490  testtree->root->SubDivide(MAX_TREE_DEPTH);
491  t1 = time(NULL);
492  tdiff = (int)difftime(t1, t0);
493  printf("subdivide: %d sec\n", tdiff);
494  t0 = time(NULL);
495 
496  std::ofstream keyfile;
497  keyfile.open("keys.txt");
498  for (keyiterator = keys.begin(); keyiterator != keys.end(); keyiterator++) {
499  keyfile << keyiterator->getKey() << "\n";
500  }
501  keyfile.close();
502 
503  std::cout << "Total checked: " << counting << "\n";
504  std::cout << "Rejected from Set: " << rejected << "\n";
505  std::cout << "Set Contains " << keys.size() << " items\n";
506 }
507 
508 
509 // Local Variables:
510 // tab-width: 8
511 // mode: C++
512 // c-basic-offset: 4
513 // indent-tabs-mode: t
514 // c-file-style: "stroustrup"
515 // End:
516 // ex: shiftwidth=4 tabstop=8
const std::string & getKey() const
Definition: uvpoints.cpp:106
void * allocate(size_t)
Definition: uvpoints.cpp:61
int main(int argc, char **argv)
Definition: uvpoints.cpp:454
std::set< UVKey, UVKeyComp > * keys
Definition: uvpoints.cpp:151
UVKey(std::string newkey)
Definition: uvpoints.cpp:100
void AppendKeys(std::set< UVKey, UVKeyComp > *keys, int MAX_TREE_DEPTH)
Definition: uvpoints.cpp:183
UVKeyQuadTree(std::set< UVKey, UVKeyComp > *keys, int MAX_TREE_DEPTH)
Definition: uvpoints.cpp:413
MemoryManager QuadMemoryManager
Definition: uvpoints.cpp:85
Header file for the BRL-CAD common definitions.
long time(time_t *)
void free(void *)
Definition: uvpoints.cpp:79
void ints_to_key(std::string *cppstr, int left, int right, int MAX_TREE_DEPTH)
Definition: uvpoints.cpp:168
#define POOL_SIZE
Definition: uvpoints.cpp:37
void SubDivide(int MAX_TREE_DEPTH)
Definition: uvpoints.cpp:236
QuadNode * root
Definition: uvpoints.cpp:409
int rejected
Definition: uvpoints.cpp:43
int depth
Definition: uvpoints.cpp:155
Coord * point
Definition: chull3d.cpp:52
int counting
Definition: uvpoints.cpp:44
bool operator()(const UVKey &key1, const UVKey &key2)
Definition: uvpoints.cpp:118
size_t PU[9]
Definition: uvpoints.cpp:153
size_t PV[9]
Definition: uvpoints.cpp:154
ustring object
QuadNode * Children[4]
Definition: uvpoints.cpp:156