Revision: 41580
http://brlcad.svn.sourceforge.net/brlcad/?rev=41580&view=rev
Author: starseeker
Date: 2010-12-13 19:13:51 +0000 (Mon, 13 Dec 2010)
Log Message:
-----------
This is not usable code yet, but it's reached the point where I'd hate to lose
it so commiting it as EXTRA_DIST - experimenting with memory management and uv
coordinate approaches.
Modified Paths:
--------------
brlcad/trunk/src/librt/Makefile.am
Added Paths:
-----------
brlcad/trunk/src/librt/uvpoints.cpp
Modified: brlcad/trunk/src/librt/Makefile.am
===================================================================
--- brlcad/trunk/src/librt/Makefile.am 2010-12-12 16:34:37 UTC (rev 41579)
+++ brlcad/trunk/src/librt/Makefile.am 2010-12-13 19:13:51 UTC (rev 41580)
@@ -301,7 +301,8 @@
timer-nt.c \
timer52brl.c \
timerhep.c \
- timerunix.c
+ timerunix.c \
+ uvpoints.cpp
if BUILD_REGEX
DEPADD = src/other/libregex
Added: brlcad/trunk/src/librt/uvpoints.cpp
===================================================================
--- brlcad/trunk/src/librt/uvpoints.cpp (rev 0)
+++ brlcad/trunk/src/librt/uvpoints.cpp 2010-12-13 19:13:51 UTC (rev 41580)
@@ -0,0 +1,476 @@
+/* U V P O I N T S . C P P
+ * BRL-CAD
+ *
+ * Copyright (c) 2010 United States Government as represented by
+ * the U.S. Army Research Laboratory.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * version 2.1 as published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this file; see the file named COPYING for more
+ * information.
+ */
+
+/* test routines related to quad trees and uv points for NURBS - this
+ * is not the final form of this code, just testing.
+ */
+
+#include <iostream>
+#include <string>
+#include <fstream>
+#include <iomanip>
+#include <vector>
+#include <set>
+#include <list>
+#include <math.h>
+
+#define POOL_SIZE 1024
+
+using namespace std;
+
+/* For memory management stuff see the tutorial at
+ *
http://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/section9.html
*/
+class MemoryManager
+{
+ private:
+ std::list<void*> QuadNodePtrList;
+ std::vector<void*> MemoryPoolList;
+ public:
+ MemoryManager( ) {}
+ ~MemoryManager( ) {}
+ void* allocate(size_t);
+ void free(void*);
+};
+
+void* MemoryManager::allocate(size_t size)
+{
+ void* base = 0;
+ if (QuadNodePtrList.empty()) {
+ base = new char[size * POOL_SIZE];
+ MemoryPoolList.push_back(base);
+ for(int i = 0; i < POOL_SIZE; ++i) {
+
QuadNodePtrList.push_front(&(static_cast<char*>(base)[i*size]));
+ }
+ }
+ void* blockPtr = QuadNodePtrList.front();
+/* *((static_cast<QuadNode*>(blockPtr)) + sizeof(QuadNode) - 2) =
sizeof(QuadNode);
+ *((static_cast<QuadNode*>(blockPtr)) + sizeof(QuadNode) - 1) = 0;*/
+ QuadNodePtrList.pop_front();
+ return blockPtr;
+}
+
+void MemoryManager::free(void* object)
+{
+ QuadNodePtrList.push_front(object);
+}
+
+MemoryManager QuadMemoryManager;
+
+/* Number of subdivisions to perform */
+#define MAX_TREE_DEPTH 6
+
+int rejected = 0;
+int counting = 0;
+using namespace std;
+
+/**
+ * UVKey Class - minimal class for holding UV space coordinate keys
+ */
+
+class UVKey {
+ public:
+ UVKey(string newkey);
+ string getKey() const;
+ private:
+ string key;
+};
+
+UVKey::UVKey(string newkey)
+{
+ key.assign(newkey);
+}
+
+string UVKey::getKey() const
+{
+ return key;
+}
+
+/**
+ * UVKeyComp - Tell the C++ set how to compare keys for sorting
+ */
+class UVKeyComp {
+ public:
+ bool operator()(const UVKey& key1, const UVKey& key2)
+ {
+ if(key1.getKey().compare(key2.getKey()) < 0) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+};
+
+
+
+/**
+ * QuadNode - Holds information about the UV coordinates associated with
+ * a node in a subdivision quad tree. Assumes the following relationship
+ * between point indicies and positioning:
+ *
+ *
+ * 3-------------------2
+ * | |
+ * | 6 8 |
+ * | |
+ * V | 4 |
+ * | |
+ * | 5 7 |
+ * | |
+ * 0-------------------1
+ * U
+
+ *
+ */
+
+class QuadNode {
+ public:
+ void SubDivide();
+ set<UVKey, UVKeyComp> *keys;
+ void AppendKeys(set <UVKey, UVKeyComp> *keys);
+ size_t PU[9];
+ size_t PV[9];
+ int depth;
+ QuadNode *Children[4];
+ inline void* operator new(size_t size)
+ {
+ return QuadMemoryManager.allocate(sizeof(QuadNode));
+ }
+ inline void operator delete(void* object)
+ {
+ QuadMemoryManager.free(object);
+ }
+};
+
+int ints_to_key(string *cppstr, int left, int right)
+{
+ char formatstring[20];
+ char maxkeystr[20];
+ char finalstring[20];
+ int max_key_length;
+ int max_key = pow(2, MAX_TREE_DEPTH + 2);
+ sprintf(maxkeystr, "%d", max_key);
+ max_key_length = strlen(maxkeystr);
+ sprintf(formatstring, "%%\'0%dd%%\'0%dd", max_key_length,
max_key_length);
+ sprintf(finalstring, formatstring, left, right);
+ cppstr->assign(finalstring);
+}
+
+
+void QuadNode::AppendKeys(set <UVKey, UVKeyComp> *keys)
+{
+ UVKey *point;
+ set<UVKey, UVKeyComp>::iterator item;
+ string keystring;
+ int i;
+ for( int i = 0; i < 9; i++ ) {
+ counting++;
+ ints_to_key(&keystring, PU[i], PV[i]);
+ item = keys->find(keystring);
+ if(item == keys->end()) {
+ point = new UVKey(keystring);
+ keys->insert(*point);
+ } else {
+ rejected++;
+ }
+ keystring.erase();
+ }
+}
+
+/*
+ * When subdivision is made, parent coordinate values are used
+ * to deduce those of the children. Some are direct copies, as
+ * follows (this relates quadrant conventions to the above diagram
+ * identifying point positions by number)
+ *
+ * 3---------------- ----------------2
+ * | | | |
+ * | | | |
+ * V | 6 | | 8 |
+ * | | | |
+ * | | | |
+ * ----------------4 4----------------
+ * U U
+ *
+ * Quadrant 3 Quadrant 2
+ *
+ * ----------------4 4----------------
+ * | | | |
+ * | | | |
+ * V | 5 | | 7 |
+ * | | | |
+ * | | | |
+ * 0---------------- ----------------1
+ * U U
+ *
+ * Quadrant 0 Quadrant 1
+ */
+
+void QuadNode::SubDivide()
+{
+ int i;
+ /* Quadrant 0 */
+ Children[0] = new QuadNode();
+ Children[0]->depth = depth + 1;
+ Children[0]->keys = keys;
+ Children[0]->PU[0] = PU[0];
+ Children[0]->PV[0] = PV[0];
+ Children[0]->PU[1] = PU[4];
+ Children[0]->PV[1] = PV[0];
+ Children[0]->PU[2] = PU[4];
+ Children[0]->PV[2] = PV[4];
+ Children[0]->PU[3] = PU[0];
+ Children[0]->PV[3] = PV[4];
+ Children[0]->PU[4] = (Children[0]->PU[1] -
Children[0]->PU[0])/2 + Children[0]->PU[0];
+ Children[0]->PV[4] = (Children[0]->PV[2] -
Children[0]->PV[1])/2 + Children[0]->PV[0];
+ Children[0]->PU[5] = (Children[0]->PU[1] -
Children[0]->PU[0])/4 + Children[0]->PU[0];
+ Children[0]->PV[5] = (Children[0]->PV[3] -
Children[0]->PV[0])/4 + Children[0]->PV[0];
+ Children[0]->PU[6] = Children[0]->PU[5];
+ Children[0]->PV[6] = 3*(Children[0]->PV[3] -
Children[0]->PV[0])/4 + Children[0]->PV[0];
+ Children[0]->PU[7] = 3*(Children[0]->PU[1] -
Children[0]->PU[0])/4 + Children[0]->PU[0];
+ Children[0]->PV[7] = Children[0]->PV[5];
+ Children[0]->PU[8] = Children[0]->PU[7];
+ Children[0]->PV[8] = Children[0]->PV[6];
+ Children[0]->AppendKeys(keys);
+ /* cout << "Q0 Depth: " << depth + 1 << "\n";
+ cout << "PU: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[0]->PU[i] << ",";
+ }
+ cout << "}\n";
+ cout << "PV: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[0]->PV[i] << ",";
+ }
+ cout << "}\n";*/
+ if (Children[0]->depth < MAX_TREE_DEPTH)
+ Children[0]->SubDivide();
+
+
+ /* Quadrant 1 */
+ Children[1] = new QuadNode();
+ Children[1]->depth = depth + 1;
+ Children[1]->keys = keys;
+ Children[1]->PU[0] = PU[4];
+ Children[1]->PV[0] = PV[1];
+ Children[1]->PU[1] = PU[1];
+ Children[1]->PV[1] = PV[1];
+ Children[1]->PU[2] = PU[1];
+ Children[1]->PV[2] = PV[4];
+ Children[1]->PU[3] = PU[4];
+ Children[1]->PV[3] = PV[4];
+ Children[1]->PU[4] = (Children[1]->PU[1] -
Children[1]->PU[0])/2 + Children[1]->PU[0];
+ Children[1]->PV[4] = (Children[1]->PV[2] -
Children[1]->PV[1])/2 + Children[1]->PV[0];
+ Children[1]->PU[5] = (Children[1]->PU[1] -
Children[1]->PU[0])/4 + Children[1]->PU[0];
+ Children[1]->PV[5] = (Children[1]->PV[3] -
Children[1]->PV[0])/4 + Children[1]->PV[0];
+ Children[1]->PU[6] = Children[1]->PU[5];
+ Children[1]->PV[6] = 3*(Children[1]->PV[3] -
Children[1]->PV[0])/4 + Children[1]->PV[0];
+ Children[1]->PU[7] = 3*(Children[1]->PU[1] -
Children[1]->PU[0])/4 + Children[1]->PU[0];
+ Children[1]->PV[7] = Children[1]->PV[5];
+ Children[1]->PU[8] = Children[1]->PU[7];
+ Children[1]->PV[8] = Children[1]->PV[6];
+ Children[1]->AppendKeys(keys);
+/* cout << "Q1 Depth: " << depth + 1 << "\n";
+ cout << "PU: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[1]->PU[i] << ",";
+ }
+ cout << "}\n";
+ cout << "PV: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[1]->PV[i] << ",";
+ }
+ cout << "}\n";*/
+ if (Children[1]->depth < MAX_TREE_DEPTH)
+ Children[1]->SubDivide();
+
+ /* Quadrant 2 */
+ Children[2] = new QuadNode();
+ Children[2]->depth = depth + 1;
+ Children[2]->keys = keys;
+ Children[2]->PU[0] = PU[4];
+ Children[2]->PV[0] = PV[4];
+ Children[2]->PU[1] = PU[2];
+ Children[2]->PV[1] = PV[4];
+ Children[2]->PU[2] = PU[2];
+ Children[2]->PV[2] = PV[2];
+ Children[2]->PU[3] = PU[4];
+ Children[2]->PV[3] = PV[2];
+ Children[2]->PU[4] = (Children[2]->PU[1] -
Children[2]->PU[0])/2 + Children[2]->PU[0];
+ Children[2]->PV[4] = (Children[2]->PV[2] -
Children[2]->PV[1])/2 + Children[2]->PV[0];
+ Children[2]->PU[5] = (Children[2]->PU[1] -
Children[2]->PU[0])/4 + Children[2]->PU[0];
+ Children[2]->PV[5] = (Children[2]->PV[3] -
Children[2]->PV[0])/4 + Children[2]->PV[0];
+ Children[2]->PU[6] = Children[2]->PU[5];
+ Children[2]->PV[6] = 3*(Children[2]->PV[3] -
Children[2]->PV[0])/4 + Children[2]->PV[0];
+ Children[2]->PU[7] = 3*(Children[2]->PU[1] -
Children[2]->PU[0])/4 + Children[2]->PU[0];
+ Children[2]->PV[7] = Children[2]->PV[5];
+ Children[2]->PU[8] = Children[2]->PU[7];
+ Children[2]->PV[8] = Children[2]->PV[6];
+ Children[2]->AppendKeys(keys);
+/* cout << "Q2 Depth: " << depth + 1 << "\n";
+ cout << "PU: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[2]->PU[i] << ",";
+ }
+ cout << "}\n";
+ cout << "PV: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[2]->PV[i] << ",";
+ }
+ cout << "}\n";*/
+
+ if (Children[2]->depth < MAX_TREE_DEPTH)
+ Children[2]->SubDivide();
+
+ /* Quadrant 3 */
+ Children[3] = new QuadNode();
+ Children[3]->depth = depth + 1;
+ Children[3]->keys = keys;
+ Children[3]->PU[0] = PU[3];
+ Children[3]->PV[0] = PV[4];
+ Children[3]->PU[1] = PU[4];
+ Children[3]->PV[1] = PV[4];
+ Children[3]->PU[2] = PU[4];
+ Children[3]->PV[2] = PV[3];
+ Children[3]->PU[3] = PV[3];
+ Children[3]->PV[3] = PV[3];
+ Children[3]->PU[4] = (Children[3]->PU[1] -
Children[3]->PU[0])/2 + Children[3]->PU[0];
+ Children[3]->PV[4] = (Children[3]->PV[2] -
Children[3]->PV[1])/2 + Children[3]->PV[0];
+ Children[3]->PU[5] = (Children[3]->PU[1] -
Children[3]->PU[0])/4 + Children[3]->PU[0];
+ Children[3]->PV[5] = (Children[3]->PV[3] -
Children[3]->PV[0])/4 + Children[3]->PV[0];
+ Children[3]->PU[6] = Children[3]->PU[5];
+ Children[3]->PV[6] = 3*(Children[3]->PV[3] -
Children[3]->PV[0])/4 + Children[3]->PV[0];
+ Children[3]->PU[7] = 3*(Children[3]->PU[1] -
Children[3]->PU[0])/4 + Children[3]->PU[0];
+ Children[3]->PV[7] = Children[3]->PV[5];
+ Children[3]->PU[8] = Children[3]->PU[7];
+ Children[3]->PV[8] = Children[3]->PV[6];
+ Children[3]->AppendKeys(keys);
+/* cout << "Q3 Depth: " << depth + 1 << "\n";
+ cout << "PU: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[3]->PU[i] << ",";
+ }
+ cout << "}\n";
+ cout << "PV: {";
+ for( int i = 0; i < 9; i++ ) {
+ cout << Children[3]->PV[i] << ",";
+ }
+ cout << "}\n";*/
+
+ if (Children[3]->depth < MAX_TREE_DEPTH)
+ Children[3]->SubDivide();
+
+}
+
+/**
+ * UVKeyQuadTree - This holds a bounding box subdivision tree using
+ * a quad tree on a generic UV space - this is used to identify keys that
+ * will potentially need to have points evaluated for a real surface tree
+ * build
+ */
+class UVKeyQuadTree {
+ public:
+ UVKeyQuadTree(set<UVKey, UVKeyComp> *keys);
+ QuadNode *root;
+};
+
+UVKeyQuadTree::UVKeyQuadTree(set<UVKey, UVKeyComp> *keys)
+{
+ UVKey *point;
+ set<UVKey, UVKeyComp>::iterator item;
+ int Ucoord;
+ int Vcoord;
+ string keynum;
+ int i;
+
+ root = new QuadNode();
+ root->depth = 0;
+ root->keys = keys;
+ root->PU[0] = 0;
+ root->PV[0] = 0;
+ root->PU[1] = pow(2, MAX_TREE_DEPTH + 2);
+ root->PV[1] = 0;
+ root->PU[2] = pow(2, MAX_TREE_DEPTH + 2);
+ root->PV[2] = pow(2, MAX_TREE_DEPTH + 2);
+ root->PU[3] = 0;
+ root->PV[3] = pow(2, MAX_TREE_DEPTH + 2);
+ root->PU[4] = pow(2, MAX_TREE_DEPTH + 2)/2;
+ root->PV[4] = pow(2, MAX_TREE_DEPTH + 2)/2;
+ root->PU[5] = pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PV[5] = pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PU[6] = pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PV[6] = 3*pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PU[7] = 3*pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PV[7] = pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PU[8] = 3*pow(2, MAX_TREE_DEPTH + 2)/4;
+ root->PV[8] = 3*pow(2, MAX_TREE_DEPTH + 2)/4;
+ for( int i = 0; i < 9; i++ ) {
+ counting++;
+ ints_to_key(&keynum, root->PU[i], root->PV[i]);
+ item = keys->find(keynum);
+ if(item == keys->end()) {
+ point = new UVKey(keynum);
+ keys->insert(*point);
+ }
+ keynum.erase();
+ }
+}
+
+int main()
+{
+ int matsize;
+ matsize = pow(2, MAX_TREE_DEPTH + 2) + 1;
+ vector<vector<int> > matitems ( matsize , vector<int> ( matsize ) );
+ int k = 0;
+
+ cout << "Max tree depth: " << MAX_TREE_DEPTH << "\n";
+ if (MAX_TREE_DEPTH < 3) {
+ cout << "Matrix: \n";
+ for ( int i = 0; i < matsize; i++ ) {
+ for ( int j = 0; j < matsize; j++ )
+ matitems[i][j] = k++;
+ }
+
+ for ( int i = 0; i < matsize; i++ ) {
+ for ( int j = 0; j < matsize; j++ )
+ cout<< setw ( 3 ) << i << j <<' ';
+ cout<<'\n';
+ }
+ cout<<'\n';
+ }
+
+ set <UVKey, UVKeyComp> keys;
+ set<UVKey, UVKeyComp>::iterator keyiterator;
+ UVKeyQuadTree *testtree = new UVKeyQuadTree(&keys);
+ testtree->root->SubDivide();
+
+/* for(keyiterator = keys.begin(); keyiterator != keys.end();
keyiterator++) {
+ cout << "Key: " << keyiterator->getKey() << "\n";
+ }*/
+ ofstream keyfile;
+ keyfile.open("keys.txt");
+ for(keyiterator = keys.begin(); keyiterator != keys.end();
keyiterator++) {
+ keyfile << keyiterator->getKey() << "\n";
+ }
+ keyfile.close();
+
+ cout << "Total checked: " << counting << "\n";
+ cout << "Rejected from Set: " << rejected << "\n";
+ cout << "Set Contains " << keys.size() << " items\n";
+}
Property changes on: brlcad/trunk/src/librt/uvpoints.cpp
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: svn:eol-style
+ native
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
