The de facto standard for storing human motion data on a computer involves a representation based on Euler angles.This representation, while effective, has several shortcomings.Triplets of Euler angles are not unique, and the same posture may be expressed using different combinations of angles.Furthermore, many possible Euler angle triplets correspond to unnatural positions for human joints.This means that, in general, a large part of the representational space remains unused.In this paper, we further investigate a recently proposed representation inspired by molecular representations.It uses only two (instead of three) degrees of freedom per joint: a vector and a torsion angle.Using the two key ingredients of this new representation, we present a complete analysis of the Graphics Lab Motion Capture Database.The data found in this analysis provide us with some powerful insights about natural and unnatural human postures in human motions.These insights can potentially lead to possible constraints on human motions which may be used to more effectively solve open problems in the computer graphics community, most notably the problem of (human) motion adaptation.

We present a GPU implementation in C and CUDA of a matrix-by-vector procedure that is particularly tailored to a special class of distance geometry problems in dimension 1, which we name "paradoxical DGP instances".This matrix-byvector reformulation was proposed in previous studies on an optical processor specialized for this kind of computations.Our computational experiments show that a consistent speed-up is observed when comparing our GPU implementation against a standard algorithm for distance geometry, called the Branchand-Prune algorithm.These results confirm that a suitable implementation of the matrix-by-vector procedure in the context of optic computing is very promising.We also remark, however, that the total number of detected solutions grows with the instance size in our implementations, which appears to be an important limitation to the effective implementation of the optical processor.

The Distance Geometry Problem (DGP) consists of finding the coordinates of a given set of points where the distances between some pairs of points are known. The DGP has several applications and one of the most relevant ones arises in the context of structural biology, where NMR experiments are performed to estimate distances between some atom pairs in a given molecule, and the possible conformations for the molecule are calculated through the formulation and the solution of a DGP. We focus our attention on DGP instances for which some special assumptions allow us to discretize the DGP search space and to potentially perform the complete enumeration of the solution set. We refer to the subclass of DGP instances satisfying such discretizability assumptions as the Discretizable DGP (DDGP). In this context, we propose a new procedure for the generation of DDGP instances where real data and simulated data (from known molecular models) can coexist. Our procedure can give rise to peculiar DDGP instances that we use for studying the impact of every distance type, involved in NMR protein structure determination, on the quality of the found solutions. Surprisingly, our experiments suggest that the distance types implying a larger effect on the solution quality are not the ones related to NMR data, but rather the more abundant, but much less informative, van der Waals distance type.

Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃ ℝ-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions. In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is by an angle of δ "blocked" by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.

Distance-based motion adaptation leads to the formulation of a dynamical Distance Geometry Problem (dynDGP) where the involved distances simultaneously represent the morphology of the animated character, as well as a possible motion.The explicit use of inter-joint distances allows us to easily verify the presence of joint contacts, which one generally wishes to preserve when adapting a given motion to characters having a different morphology.In this work, we focus our attention on suitable representations of human-like animated characters, and study the advantages (and disadvantages) in using some of them.In the initial works on distance-based motion adaptation, a 3ndimensional vector was employed for representing the positions of the n joints of the character at a given frame.Here, we investigate the use of another, very popular in computer graphics, representation that basically replaces every joint position in the three-dimensional space with a set of three sorted Euler angles.We show that the latter can in fact be useful for avoiding some of the artifacts that were observed in previous computational experiments, but we argue that this Euler-angle representation, from a motion adaptation point of view, does not seem to be the optimal one.By paying particular attention to the degrees of freedom of the studied representations, it turns out that a novel character representation, inspired by representations used in structural biology for molecules, may allow us to reduce the character degrees of freedom to their minimal value.As a result, statistical analysis on human motion databases, where the motions are given with this new representation, can potentially provide important insights on human motions.This study is an initial step towards the identification of a full set of constraints capable of ensuring that unnatural postures for humans cannot be created while tackling motion adaptation problems.