-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathREADME
163 lines (100 loc) · 6.5 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
This is a C++ implementation of Tom Forsyth's linear-speed vertex cache optimisation algorithm
( http://www.eelpi.gotdns.org/papers/papers.html ).
The optimizer does not change the way the mesh looks like; it does not add or remove triangle, and does not
manipulate individual vertex attributes. Instead, it reorders triangles (and optionally vertices) to
make better of of the GPU vertex cache and memory bandwidth, preserving the shape. Visual changes to the mesh
are considered an error.
BUILDING INSTRUCTIONS
=====================
vcache_optimizer itself is made up of headers only; it does not have to be built.
In order to build the tests and the ply viewer, follow these steps:
Linux:
------
./waf configure
./waf
To run the ply viewer without running the optimizer, execute
> build/ply_viewer/ply_viewer <name of PLY file to show>
this will run the PLY viewer, load the specified PLY file, and show it.
To let the optimizer run after loading, run this instead:
> build/ply_viewer/ply_viewer <name of PLY file to show> -optimize
Windows:
--------
<TODO VisualC build steps>
USAGE
=====
vcache_optimizer works with surface meshes made up of triangles. Volume meshes, quad meshes etc. are not supported.
The meshes can be made up of submeshes, as it is common with meshes in computer games; there, submeshes are used
to support multiple materials in the same mesh (one material per submesh).
Submeshes in the mesh are expected to be separated from each other. This holds true at least for the triangles;
for example, a mixed set of triangles like "1 1 2 2 1 3 1", where 1/2/3 refers to a triangle of submesh 1/2/3,
is invalid. A valid version of this set would be "1 1 1 1 2 2 3". Another would be "2 2 1 1 1 1 3". If such
an ordering is inevitable, then the getters defined below must do some internal mapping. From the point of
view of the vcache_optimizer, the triangles are ordered contiguously and separated.
The submeshes may use a common set of vertices. In this case, get_num_vertices() should return the total number
of vertices and get_vertex() should ignore the submesh parameter. If submeshes share vertices, the vertex
reordering should be disabled, otherwise submeshes may get corrupted.
In order to use vcache_optimizer , the mesh type has to conform to the VcacheMesh concept. Several functions are required,
as well as a traits class defining some types.
The traits class has the following type definitions:
- submesh_id_t
fulfills the CopyConstructibe and EqualityComparable concepts
used for identifying submeshes
- vertex_t
fulfills the CopyConstructibe concept
contains or at least refers to a vertex. Copying an instance of this class copies a vertex.
The vcache_optimizer code uses this type for using getting/setting vertices using get_vertex / set_vertex.
- triangles_t
fulfills the CopyConstructibe concept
contains or at least refers to a triangle. Copying an instance of this class copies a triangle.
The vcache_optimizer code uses this type for using getting/setting triangles using get_triangle / set_triangle.
In addition, the triangles_t type defines an index ( [] ) operator for retrieving triangle vertex indices.
The index may be 0, 1, or 2. Triangles are made up of three vertex indices.
- vertex_index_t / triangle_index_t
integral number types
convertible to size_t
The traits class can be implemented and supplied in two ways:
1. Supply it as a template parameter to vcache_optimizer
The traits class can have any name and be in any namespace.
Example:
vcache_optimizer < mymesh, float, mytraits > optimizer;
2. Specialize the mesh_traits template
The traits class must be in the vcache_optimizer namespace.
Example:
namespace vcache_optimizer
{
template < >
typename mesh_traits < mymesh >
{
...
}
}
vcache_optimizer < mymesh > optimizer;
The following free functions must be defined for the mesh.
- triangle_t create_new_triangle(VcacheMesh &vcache_mesh, vertex_index_t const &vtx1, vertex_index_t const &vtx2, vertex_index_t const &vtx3)
Creates a new triangle of triangle_t type, made up of the vertex indices vtx1,vtx2,vtx3.
- std::size_t get_num_triangles(VcacheMesh const &vcache_mesh, submesh_id_t const &submesh_id)
Returns the number of triangles the specified submesh has inside vcache_mesh.
- std::size_t get_num_vertices(VcacheMesh const &vcache_mesh, submesh_id_t const &submesh_id)
Returns the number of vertices the specified submesh has inside vcache_mesh.
- triangle_t get_triangle(VcacheMesh const &vcache_mesh, submesh_id_t const &submesh_id, triangle_index_t const &index)
Returns a triangle with the given index, from the specified submesh inside the vcache_mesh.
The minimum index is 0, the maximum index is (get_num_triangles() - 1).
- vertex_t get_vertex(VcacheMesh const &vcache_mesh, submesh_id_t const &submesh_id, vertex_index_t const &index)
Returns a vertex with the given index, from the specified submesh inside the vcache_mesh.
The minimum index is 0, the maximum index is (get_num_vertices() - 1).
- void set_triangle(VcacheMesh &vcache_mesh, submesh_id_t const &submesh_id, triangle_index_t const &index, triangle_t const &new_triangle)
Sets the given triangle in the specified submesh inside the vcache_mesh.
The minimum index is 0, the maximum index is (get_num_triangles() - 1).
- void set_vertex(VcacheMesh &vcache_mesh, submesh_id_t const &submesh_id, vertex_index_t const &index, vertex_t const &new_vertex)
Sets the given vertex in the specified submesh inside the vcache_mesh.
The minimum index is 0, the maximum index is (get_num_vertices() - 1).
vcache_optimizer itself is a functor; to perform the optimization, call it like this:
optimizer(my_mesh, "id_of_submesh_to_be_optimized", true/false);
The first parameter is the mesh meeting the VcacheMesh concept requirments.
The second parameter is the ID of the sumesh to be optimized. If your mesh does not have submeshes, you can specify an empty string here.
The third parameter is optional, and true by default. It specifies whether or not the optimizer shall do the second step: reorder vertices.
As explained in Tom Forsyths paper, this secondary step tries to reorder the vertices for a more linearized access pattern, improving the use
of memory bandwidth. However, in a mesh with submeshes, vertex reordering may be undesirable. Set the third parameter to false in that case.
LICENSING
=========
This optimizer code is released under the Boost Software License, version 1.0. The file LICENSE_1_0.txt contains a copy of this license.