1 //
2 // Copyright 2017 DreamWorks Animation LLC.
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24
25 #ifndef OPENSUBDIV3_FAR_SPARSE_MATRIX_H
26 #define OPENSUBDIV3_FAR_SPARSE_MATRIX_H
27
28 #include "../version.h"
29
30 #include "../vtr/array.h"
31
32 #include <algorithm>
33
34
35 namespace OpenSubdiv {
36 namespace OPENSUBDIV_VERSION {
37
38 namespace Far {
39
40 //
41 // SparseMatrix
42 //
43 // The SparseMatrix class is used by the PatchBuilder to store coefficients
44 // for a set of patch points derived from some other set of points -- usually
45 // the refined points in a subdivision level. The compressed sparse row
46 // format (CSR) is used as it provides us with stencils for points that
47 // correspond to rows and so can be more directly and efficiently copied.
48 //
49 // It has potential for other uses and so may eventually warrant a seperate
50 // header file of its own. For now, in keeping with the trend of exposing
51 // classes only where used, it is defined with the PatchBuilder.
52 //
53 // We may also want to explore the possibility of being able to assign
54 // static buffers as members here -- allowing common matrices to be set
55 // directly rather than repeatedly replicated.
56 //
57 template <typename REAL>
58 class SparseMatrix {
59 public:
60 typedef int column_type;
61 typedef REAL element_type;
62
63 public:
64 // Declaration and access methods:
SparseMatrix()65 SparseMatrix() : _numRows(0), _numColumns(0), _numElements(0) { }
66
GetNumRows()67 int GetNumRows() const { return _numRows; }
GetNumColumns()68 int GetNumColumns() const { return _numColumns; }
GetNumElements()69 int GetNumElements() const { return _numElements; }
70 int GetCapacity() const;
71
GetRowSize(int rowIndex)72 int GetRowSize(int rowIndex) const {
73 return _rowOffsets[rowIndex + 1] - _rowOffsets[rowIndex];
74 }
75
GetRowColumns(int rowIndex)76 Vtr::ConstArray<column_type> GetRowColumns( int rowIndex) const {
77 return Vtr::ConstArray<column_type>(&_columns[_rowOffsets[rowIndex]],
78 GetRowSize(rowIndex));
79 }
GetRowElements(int rowIndex)80 Vtr::ConstArray<element_type> GetRowElements(int rowIndex) const {
81 return Vtr::ConstArray<element_type>(&_elements[_rowOffsets[rowIndex]],
82 GetRowSize(rowIndex));
83 }
84
GetColumns()85 Vtr::ConstArray<column_type> GetColumns() const {
86 return Vtr::ConstArray<column_type>(&_columns[0], GetNumElements());
87 }
GetElements()88 Vtr::ConstArray<element_type> GetElements() const {
89 return Vtr::ConstArray<element_type>(&_elements[0], GetNumElements());
90 }
91
92 public:
93 // Modification methods
94 void Resize(int numRows, int numColumns, int numNonZeroEntriesToReserve);
95 void Copy(SparseMatrix const & srcMatrix);
96 void Swap(SparseMatrix & otherMatrix);
97
98 void SetRowSize(int rowIndex, int size);
99
SetRowColumns(int rowIndex)100 Vtr::Array<column_type> SetRowColumns( int rowIndex) {
101 return Vtr::Array<column_type>(&_columns[_rowOffsets[rowIndex]],
102 GetRowSize(rowIndex));
103 }
SetRowElements(int rowIndex)104 Vtr::Array<element_type> SetRowElements(int rowIndex) {
105 return Vtr::Array<element_type>(&_elements[_rowOffsets[rowIndex]],
106 GetRowSize(rowIndex));
107 }
108
109 private:
110 // Simple dimensions:
111 int _numRows;
112 int _numColumns;
113 int _numElements;
114
115 std::vector<int> _rowOffsets; // remember one more entry here than rows
116
117 // XXXX (barfowl) - Note that the use of std::vector for the columns and
118 // element arrays was causing performance issues in the incremental
119 // resizing of consecutive rows, so we've been exploring alternatives...
120 std::vector<column_type> _columns;
121 std::vector<element_type> _elements;
122 };
123
124 template <typename REAL>
125 inline int
GetCapacity()126 SparseMatrix<REAL>::GetCapacity() const {
127
128 return (int) _elements.size();
129 }
130
131 template <typename REAL>
132 inline void
Resize(int numRows,int numCols,int numElementsToReserve)133 SparseMatrix<REAL>::Resize(int numRows, int numCols, int numElementsToReserve) {
134
135 _numRows = numRows;
136 _numColumns = numCols;
137 _numElements = 0;
138
139 _rowOffsets.resize(0);
140 _rowOffsets.resize(_numRows + 1, -1);
141 _rowOffsets[0] = 0;
142
143 if (numElementsToReserve > GetCapacity()) {
144 _columns.resize(numElementsToReserve);
145 _elements.resize(numElementsToReserve);
146 }
147 }
148 template <typename REAL>
149 inline void
SetRowSize(int rowIndex,int rowSize)150 SparseMatrix<REAL>::SetRowSize(int rowIndex, int rowSize) {
151
152 assert(_rowOffsets[rowIndex] == _numElements);
153
154 int & newVectorSize = _rowOffsets[rowIndex + 1];
155 newVectorSize = _rowOffsets[rowIndex] + rowSize;
156
157 _numElements = newVectorSize;
158 if (newVectorSize > GetCapacity()) {
159 _columns.resize(newVectorSize);
160 _elements.resize(newVectorSize);
161 }
162 }
163
164 template <typename REAL>
165 inline void
Copy(SparseMatrix const & src)166 SparseMatrix<REAL>::Copy(SparseMatrix const & src) {
167
168 _numRows = src._numRows;
169 _numColumns = src._numColumns;
170
171 _rowOffsets = src._rowOffsets;
172
173 _numElements = src._numElements;
174
175 _columns = src._columns;
176 _elements = src._elements;
177 }
178
179 template <typename REAL>
180 inline void
Swap(SparseMatrix & other)181 SparseMatrix<REAL>::Swap(SparseMatrix & other) {
182
183 std::swap(_numRows, other._numRows);
184 std::swap(_numColumns, other._numColumns);
185 std::swap(_numElements, other._numElements);
186
187 _rowOffsets.swap(other._rowOffsets);
188 _columns.swap(other._columns);
189 _elements.swap(other._elements);
190 }
191
192 } // end namespace Far
193
194 } // end namespace OPENSUBDIV_VERSION
195 using namespace OPENSUBDIV_VERSION;
196
197 } // end namespace OpenSubdiv
198
199 #endif /* OPENSUBDIV3_FAR_SPARSE_MATRIX_H */
200