Firstly, I want to thank you for all the time and attention you've obviously put into this code.  <br><br>On Tue, Mar 2, 2010 at 12:27 AM, Friedrich Romstedt <span dir="ltr"><<a href="mailto:friedrichromstedt@gmail.com">friedrichromstedt@gmail.com</a>></span> wrote:<br>

<div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
The loop I can replace by numpy operations:<br>
<br>
>>> v_array<br>
array([[1, 2, 3],<br>
       [4, 5, 6],<br>
       [7, 8, 9]])<br>
>>> n_array<br>
array([[ 0.1,  0.2,  0.3],<br>
       [ 0.4,  0.5,  0.6]])<br>
>>> f_list<br>
array([[0, 1, 2, 0],<br>
       [2, 1, 0, 1]])<br>
<br>
Retrieving the v1 vectors:<br>
<br>
>>> v1s = v_array[f_list[:, 0]]<br>
>>> v1s<br>
array([[1, 2, 3],<br>
       [7, 8, 9]])<br>
<br>
Retrieving the normal vectors:<br>
<br>
>>> ns = n_array[f_list[:, 3]]<br>
>>> ns<br>
array([[ 0.1,  0.2,  0.3],<br>
       [ 0.4,  0.5,  0.6]])<br></blockquote><div>I don't think you understand quite what I'm looking for here.  Every vec4 in <span style="font-family: courier new,monospace;">f_list</span> describes a triangle.  The first, second, and third are indices of vertices in <span style="font-family: courier new,monospace;">v_array</span>.  The fourth is an index of <span style="font-family: courier new,monospace;">n_array</span>.  From your code, I've learned that I can do this, which is more what I want:<br>

<span style="font-family: courier new,monospace;">v1s = v_array[f_list[:,0:3]]</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">ns = n_array[f_list[:,3]]</span><br>Obviously, this changes the arrays quite a bit.  With changes, the code doesn't actually crash until the <span style="font-family: courier new,monospace;">corners = </span>line.  Do the following lines that do the dot product and comparison still behave correctly?  They should be finding, for each triangle, whether or not the associated normal is less than 90 degrees.  The triangle's edges should then be added to an array.  See end.  <br>

</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Now how to calculate the pairwise dot product (I suppress the<br>
difference of v1 to some_point for now):<br>
<br>
>>> inner = numpy.inner(ns, v1s)<br>
>>> inner<br>
array([[  1.4,   5. ],<br>
       [  3.2,  12.2]])<br>
<br>
This calculates *all* pairwise dot products, we have to select the<br>
diagonal of this square ndarray:<br>
<br>
>>> dotprods = inner[[numpy.arange(0, 2), numpy.arange(0, 2)]]<br>
>>> dotprods<br>
array([  1.4,  12.2])<br>
<br>
Now we can create a boolean array saying where the dotprod is > 0<br>
(i.e, angle < 90°), and select those triangles:<br>
<br>
>>> select = dotprods > 0<br>
>>> select<br>
array([ True,  True], dtype=bool)<br>
>>> selected = f_list[select]<br>
>>> selected<br>
array([[0, 1, 2, 0],<br>
       [2, 1, 0, 1]])<br></blockquote><div>This seems like a clever idea. <br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
In this case it's the full list.  Now build the triangles corners array:<br>
<br>
>>> corners = v_array[selected[:, :3]]<br>
>>> corners<br>
array([[[1, 2, 3],<br>
        [4, 5, 6],<br>
        [7, 8, 9]],<br>
<br>
       [[7, 8, 9],<br>
        [4, 5, 6],<br>
        [1, 2, 3]]])<br>
>>><br>
<br>
This has indices [triangle, vertex number (0, 1, or 2), xyz].<br>
And compute the edges (I think you can make use of them):<br>
<br>
>>> edges_dist = numpy.asarray([corners[:, 1] - corners[:, 0], corners[:, 2] - corners[:, 0], corners[:, 2] - corners[:, 1]])<br>
>>> edges_dist<br>
array([[[ 3,  3,  3],<br>
        [-3, -3, -3]],<br>
<br>
       [[ 6,  6,  6],<br>
        [-6, -6, -6]],<br>
<br>
       [[ 3,  3,  3],<br>
        [-3, -3, -3]]])<br>
<br>
This has indices [corner number, triangle, xyz].<br>
I think it's easier to compare then "reversed" edges, because then<br>
edge[i, j] == -edge[k, l]?<br>
<br>
But of course:<br>
<br>
>>> edges = numpy.asarray([[corners[:, 0], corners[:, 1]], [corners[:, 1], corners[:, 2]], [corners[:, 2], corners[:, 0]]])<br>
>>> edges<br>
array([[[[1, 2, 3],<br>
         [7, 8, 9]],<br>
<br>
        [[4, 5, 6],<br>
         [4, 5, 6]]],<br>
<br>
<br>
       [[[4, 5, 6],<br>
<div class="im">         [4, 5, 6]],<br>
<br>
        [[7, 8, 9],<br>
</div>         [1, 2, 3]]],<br>
<br>
<br>
       [[[7, 8, 9],<br>
         [1, 2, 3]],<br>
<br>
        [[1, 2, 3],<br>
         [7, 8, 9]]]])<br>
<br>
This has indices [edge number (0, 1, or 2), corner number in edge (0<br>
or 1), triangle].<br>
But this may not be what you want (not flattened in triangle number).<br>
Therefore:<br>
<br>
>>> edges0 = numpy.asarray([corners[:, 0], corners[:, 1]])<br>
>>> edges1 = numpy.asarray([corners[:, 1], corners[:, 2]])<br>
>>> edges2 = numpy.asarray([corners[:, 2], corners[:, 0]])<br>
>>> edges0<br>
array([[[1, 2, 3],<br>
        [7, 8, 9]],<br>
<br>
       [[4, 5, 6],<br>
        [4, 5, 6]]])<br>
>>> edges1<br>
array([[[4, 5, 6],<br>
<div class="im">        [4, 5, 6]],<br>
<br>
       [[7, 8, 9],<br>
</div>        [1, 2, 3]]])<br>
>>> edges2<br>
array([[[7, 8, 9],<br>
        [1, 2, 3]],<br>
<br>
       [[1, 2, 3],<br>
        [7, 8, 9]]])<br>
<br>
>>> edges = numpy.concatenate((edges0, edges1, edges2), axis = 0)<br>
>>> edges<br>
array([[[1, 2, 3],<br>
        [7, 8, 9]],<br>
<br>
       [[4, 5, 6],<br>
        [4, 5, 6]],<br>
<br>
       [[4, 5, 6],<br>
<div class="im">        [4, 5, 6]],<br>
<br>
       [[7, 8, 9],<br>
</div>        [1, 2, 3]],<br>
<div class="im"><br>
       [[7, 8, 9],<br>
        [1, 2, 3]],<br>
<br>
</div>       [[1, 2, 3],<br>
        [7, 8, 9]]])<br>
<br>
This should be as intended.<br>
The indices are [flat edge number, edge side (left or right), xyz].<br>
<br>
Now I guess you have to iterate over all pairs of them, don't know a<br>
numpy accelerated method.  Maybe it's even faster to draw the edges<br>
twice than to invest O(N_edges ** 2) complexity for comparing?<br></blockquote><div>Unfortunately, no.   The whole point of the algorithm is to extrude back-facing triangles (those with normals facing away from the light) backward, leaving polygons behind in a light volume.  Although a shadow volume tutorial can explain this in a more detailed way, basically, for every triangle, if it is back-facing, add its edges to a list.  Remove the duplicate edges.  So, the edge between two back-facing triangles-that-meet-along-an-edge is not kept.  However, if a back-facing triangle and a front-facing triangle meet, only the back-facing triangle's edge is present in the list, and so it is not removed.  Thus, only the border edges between the front-facing triangles and the back facing triangles remain in the list.  As front-facing triangles face the light and back-facing triangles don't, a silhouette edge is built up.  When these edges are extruded, they're extremely useful.  The following image <a href="http://www.gamedev.net/reference/articles/1873/image010.gif">http://www.gamedev.net/reference/articles/1873/image010.gif</a> shows the process.  The four triangles are all back facing.  If duplicate edges are removed, only edges I0-I2, I2-I4, I4-I3, and I3-I0 remain--the silhouette edges.  <br>

<br>Still to do, remove the duplicate edges (actually where a good deal of the optimization lies too).  <br><br>So, for every back-facing triangle <span style="font-family: courier new,monospace;">[v1,v2,v3,n]</span>, (where <span style="font-family: courier new,monospace;">v</span><i style="font-family: courier new,monospace;">n</i> is a vertex <i>index</i>), the edges <span style="font-family: courier new,monospace;">[v1,v2]</span>, <span style="font-family: courier new,monospace;">[v2,v3]</span>, and <span style="font-family: courier new,monospace;">[v3,v1]</span> need to be added to a list.  I.e., <span style="font-family: courier new,monospace;">f_list</span> needs to be converted into a list of edges in this way.  Then, duplicate edge pairs need to be removed, noting that <span style="font-family: courier new,monospace;">[v1,v2]</span> and <span style="font-family: courier new,monospace;">[v2,v1]</span> are still a pair (in my Python code, I simply sorted the edges before removing duplicates: <span style="font-family: courier new,monospace;">[123,4] -> [4,123]</span> and <span style="font-family: courier new,monospace;">[56,968] -> [56,968]</span>).  The final edge list then should be converted back into actual vertices by indexing it into v_array (I think I understand how to do this now!): <span style="font-family: courier new,monospace;">[ [1,2], [4,6], ... ] -> [ [[0.3,1.6,4.5],[9.1,4.7,7.7]], [[0.4,5.5,8.3],[9.6,8.1,0.3]], ... ]</span><br>

</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">It may seem a bit complicated, but I hope this impression is mainly<br>
because of the many outputs ...<br>
<br>
I double-checked everything, *hope* everything is correct.</blockquote><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
So far from me,<br>
<div><div></div><div>Friedrich <br></div></div></blockquote><div>Once again, thanks so much,<br>Ian<br></div></div>