Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 22 May 2004
Offline Last Active Jan 26 2015 09:12 AM

Posts I've Made

In Topic: What is a good average vertex-per-face count?

15 January 2015 - 09:49 AM

Yeah, like said above, vertices per face is not an interesting metric. The total number of vertices and the total number of triangles are more important. If an artist needs to do e.g. a hard edge on a seam to deliver some effect, the artist will need to do a hard edge on a seam and there's no way around it. Perhaps the opportunity in improving vertices per face might occur if for some odd reason two faces that share a vertex should have the same normal direction at the vertex, but somehow ended up having normals that are almost identical but not quite, and as a result the vertex got (unintentionally) duplicated for the two adjacent faces. Although I imagine such mistakes would be quite rare in practice.

In Topic: Planar reflections on non planar surfaces... help

15 January 2015 - 09:19 AM

I am reading two problems here, which to me sounds completely different. The first one is the problem of computing reflections when the surface that produces the reflections is not in a plane, and the second one you mention is that the reflections go wrong if the camera view rotation angle is not zero.


The first problem is a hard problem that cannot be solved just by plugging in a trigonometric formula in some appropriate place. This is because if the surface that produces the reflections is not planar but has varying normals in different directions in space, then these normals can scatter the reflected rays in arbitrary directions without much coherency. The only correct way to model that would be to do full raytracing, which is not very feasible on GPUs in the general context.


If the surface that does cause the reflections is "mostly planar", it can be successfully approximated by treating it as if it was just a plane, in which case the problem is solvable by rendering the geometry twice, and applying a reflection matrix to generate the reflection. Googling for "reflection matrix" will find results for this. Computing reflections via the reflection matrix equation is able to handle arbitrary camera orientations/rotation angles correctly.


When the surface is not very planar, a popular way is to do "screen space reflections" to approximate the reflection. See e.g. https://docs.unrealengine.com/latest/INT/Engine/Rendering/PostProcessEffects/ScreenSpaceReflection/index.html and http://www.gamasutra.com/blogs/BartlomiejWronski/20140129/209609/The_future_of_screenspace_reflections.php for descriptions. I'd probably do this approach if I had to pick one.


Other reflection methods involve precomputing cube maps for points in space, or impostors. E.g. https://www.cs.purdue.edu/cgvlab/papers/popescu/popescuGemEG06.pdf , however those can be quite expensive to compute.

In Topic: inverted GJK --- you're a genius if you can solve this

12 January 2015 - 03:24 PM

Sounds like the containment idea went bust, but answering this question nevertheless in case it might be useful.


Testing whether a convex polyhedron A is fully contained withing another convex polyhedron B can be done in V*F steps, where V is the number of vertices in polyhedron A, and F is the number of faces in B. The algorithm is very simple:


    for(f in F):

        for(v in V):

            if v is in positive halfspace of f:

                return False // The vertex v of A is not contained in B, so the whole object is not contained.

    return True // All vertices of A are in the negative halfspace of all the faces of B, so A is contained fully in B.


There is a faster way to do this in practice, by implementing a hill climbing search of the vertex neighbor graph of A. Instead of looping through each vertex v in V linearly, start from an arbitrary vertex, and climb up vertex neighbors towards the direction of the plane normal of f, until the you reach a vertex v that is in positive halfspace, or determine that all vertices are in negative halfspace. This is much faster, but still theoretically O(V*F). In practice it's best to sort the faces of B in such order that the six most closest cardinal axes are first in the list. Then iterating over the six first faces is effectively a broadphase "convex polyhedron contained in AABB" test which rejects invalid cases very quickly. Also with SSE, one can process four vertices against one plane in one go (or one vertex against four planes, whichever suits better).


Third, there is a way to preprocess a convex polyhedron to use what is called a Dobkin-Kirkpatrick hierarchy. After that, the convex polyhedron is contained in another convex polyhedron can be done in log(V)*F steps. This optimization comes from the faster way to locate supporting vertices that Dobkin-Kirkpatrick hierarchy guarantees.

In Topic: How many non isomorphic connected bipartite simple graphs are there with four...

16 December 2014 - 10:29 PM

If I understood the title of the post correctly, then I think the number four refers to the total number of vertices in the bipartite graph (as is customary), instead of the number of vertices on both sides.


If so, then with a bit of doodling, I was able to come up with the following graphs, which are all bipartite, connected, simple and have four vertices:




To compute the total number of non-isomorphic such graphs, you need to check

  a) are any of the graphs in the above picture isomorphic to each other, or is that the full set?

  b) is the above set missing any graphs that are not isomorphic to the already drawn ones?


Not all bipartite graphs are connected. For example if you have four vertices all on one side of the partition, then none of them can be connected. Also, try removing any edge from the bottommost graph in the above picture, and then the graph is no longer connected.


Because of the desired bipartite property, there are a lot fewer possible configurations to enumerate. Then to prove the non-isomorphism you can use the techniques you've already learned.

In Topic: glDrawElements invalid operation

07 June 2014 - 08:00 AM

Try adding an assert(vao && numIndices >= 0 && numIndices % 3 == 0);  in 'void Mesh::Draw()'. If everything is drawing ok, but the error is being spammed, I assume it's something like you have one or two Meshes in the scene for which vao is null or similar.


If that doesn't help, I'd spin up AMD CodeXL (works on all GPUs, not just AMD) and take a trace of the GL calls with that. It will show the stream clearly and the state of the GL context at the time of the error.