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 Mar 29 2015 09:57 AM

Posts I've Made

In Topic: Collision resolution with walls

23 February 2015 - 05:51 PM

Definitely decouple collision testing from keyboard input, and compute those two completely separate from each other.


That is, when processing keyboard input, use the pressed keys to define acceleration/impulse/velocity/position update to your object (whatever the type of motion you want to model is), and then in collision detection and response, don't read the keys at all that the user pressed. If necessary, you could store the previous position of the object, but just don't read the keys.

In Topic: Non axis aligned collision detection

23 February 2015 - 05:48 PM

http://www.realtimerendering.com/intersections.html is a good source for links on intersection tests. Also since you say that you know how to test for object intersection when the objects are axis aligned, I presume you instead refer to testing intersection against axis aligned bounding boxes (AABB), or otherwise that statement makes little sense. There exists fast and simple algorithms for performing collision detection between oriented bounding boxes as well, see e.g. http://clb.demon.fi/MathGeoLib/nightly/docs/OBB_Intersects.php . For intersecting more complex shapes, typically one uses convex polyhedrons, for which the GJK and SAT algorithms apply, see e.g. https://github.com/juj/MathGeoLib/tree/master/src/Algorithm . Intersecting arbitrary concave polyhedrons in 3D becomes an art by itself, for which heavy use of spatial query structures like OBBTree and RAPID can be used, but for real-time uses, these are not very fast, and therefore not recommended.

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.