The Mighty Simplex (2023)(galileo-unbound.blog)
galileo-unbound.blog
The Mighty Simplex (2023)
https://galileo-unbound.blog/2023/05/03/the-mighty-simplex/
5 comments
The simplex method in linear programming was one of the first times I ever had something relatively complex "click" for me.
It's funny, I still think about that feeling weekly. My memory of it happening while working out a homework problem is actually sort of like in the first Harry Potter movie when Harry gets his wand: warm, bright lighting, widening eyes, and a feeling like my head was a helium balloon.
It's funny, I still think about that feeling weekly. My memory of it happening while working out a homework problem is actually sort of like in the first Harry Potter movie when Harry gets his wand: warm, bright lighting, widening eyes, and a feeling like my head was a helium balloon.
So a simplex is a hypertriangle? The minimal shape that can be made with planes in any dimension?
Understanding that 10 years ago might have made it easier for me to understand collision detection algorithms for game physics
Understanding that 10 years ago might have made it easier for me to understand collision detection algorithms for game physics
Exactly! It's n+1 points in n dimensions (when finite). Another way to think about it (the way that I know because it extends into general Banach spaces and not just n dimensional spaces) is that each point inside is the unique weighted average of the extreme points (corners). So in 2d, if you have a square you can get that middle point by averaging all the corners, or averaging two opposing corners, so it's not a simplex.
https://news.ycombinator.com/item?id=12572696
DonHopkins on Sept 24, 2016 | prev | next [–]
That is a neat idea! It reminds me of another cool constraint based animation system called "Embedded Constraint Graphics" that Tom Ngo developed at Interval Research Corporation, for which he filed a patent on Aug 6, 1996. So hey, didn't that patent just expire a month ago?
Golan Levin used the ECG graphical editor to create the vector based face cartoons for his "Mouther" project, by simply dragging the eyes and mouth and other features around like you'd naturally want to be able to do. [2]
It's a really brilliant way to automatically create directly manipulatable interactive graphics from target examples, which you can interpolate between along multiple dimensions at once (zones of a simplicial complex [3]), by dragging different parts of the graphics appropriately. It would figure out how to map the direction and amount you're dragging at a particular location, to appropriate movement in the n-dimensional target interpolation space. It was great for making cartoony direct manipulation user interface widgets!
"A constraint-based graphics system employs different examples of an image to define the constraints of the system. The examples are grouped into subsets which can be interpolated with one another, according to a user-specified input that determines the relative proportion of each example image. An animation can be created by defining a sequence of such interpolated images. Alternatively, a user can directly manipulate observable components of an image to define a particular state for the image. Automatic transformations are defined to provide registration of an image within an overall scene by shifting the frame of reference for an image so that unnatural movements do not occur as the animation proceeds through a sequence of states. The structure of the system permits an animation to be divided into distinct components that can be combined with complementary components of other animations, to provide new results. These components include a clip motion which defines a sequence of states, a clip character which applies the clip motion to a particular image configuration, and clip art."
"The various image examples can be associated with one another in a manner that defines a topological data structure which identifies their relationships. An example of such a data structure for the images of FIGS. 2A-2D is shown in FIG. 3. Referring thereto, each of the four image examples is associated with a vertex of a geometric shape. Specifically, the three image examples of FIGS. 2A, 2B, and 2C, which form one subset, define a triangular shape. The second subset, comprising the examples of FIGS. 2A, 2B, and 2D, defines a second triangle. Since the examples of FIGS. 2A and 2B are shared between the two subsets, the two triangles are joined along a common interface. Each subset of examples constitutes a simplex, or zone, and all of the zones together form a combinatorial structure, or state space, known as a simplicial complex. In the case illustrated in FIG. 5, the state space is composed of two triangular zones, ABC and ABD. While both zones in this case are two-dimensional structures, it is also possible for a state space to include one-dimensional zones, i.e. a line whose end points are defined by two examples, as well as multi-dimensional zones such as a tetrahedron defined by four examples."
"The combinatorial structure defines a state space for the graphics system. Any given point within this space defines a particular image, and movement within the state space causes the appearance of the image to change. More particularly, each of the vertices corresponds to one of the image examples shown in FIGS. 2A-2D. A point located between two vertices results in an interpolated image comprised of a representative portion of each of the two images associated with the respective vertices. Thus, as one moves from the lowest vertex A in the structure of FIG. 3 up the vertical line 10 to the highest vertex B, the figure's arms smoothly move from the position shown in FIG. 2A to that shown in FIG. 2B. Movement from the lowest vertex A to the left vertex C causes a transition in the image from that of FIG. 2A to that of FIG. 2C. A point located somewhere within the triangle defined by the three vertices A, B and C corresponds to an image in which the arms are partially raised and the right leg is partially lifted. For example, the point 12 represents a position in which the image is a weighted composite consisting of 60% of FIG. 2B, 30% of FIG. 2A and 10% of FIG. 2C. The percentages sum up to unity, and the weight values which correspond to these percentages, i.e. 0.6, 0.3 and 0.1, constitute a vector in barycentric coordinates. In a relatively simple embodiment of the invention, the examples are interpolated linearly; but in a different embodiment, the interpolation could employ non-linear functions, such as cubic polynomials. Any state s within the state space can be specified by a zone, in this case the zone containing the examples A, B and C, together with the vector, i.e. 0.3, 0.6, 0.1!."
[1] https://www.google.com/patents/US5933150
[2] https://www.flong.com/archive/projects/mouther/
[3] https://en.wikipedia.org/wiki/Simplicial_complex
DonHopkins on Sept 24, 2016 | prev | next [–]
That is a neat idea! It reminds me of another cool constraint based animation system called "Embedded Constraint Graphics" that Tom Ngo developed at Interval Research Corporation, for which he filed a patent on Aug 6, 1996. So hey, didn't that patent just expire a month ago?
Golan Levin used the ECG graphical editor to create the vector based face cartoons for his "Mouther" project, by simply dragging the eyes and mouth and other features around like you'd naturally want to be able to do. [2]
It's a really brilliant way to automatically create directly manipulatable interactive graphics from target examples, which you can interpolate between along multiple dimensions at once (zones of a simplicial complex [3]), by dragging different parts of the graphics appropriately. It would figure out how to map the direction and amount you're dragging at a particular location, to appropriate movement in the n-dimensional target interpolation space. It was great for making cartoony direct manipulation user interface widgets!
"A constraint-based graphics system employs different examples of an image to define the constraints of the system. The examples are grouped into subsets which can be interpolated with one another, according to a user-specified input that determines the relative proportion of each example image. An animation can be created by defining a sequence of such interpolated images. Alternatively, a user can directly manipulate observable components of an image to define a particular state for the image. Automatic transformations are defined to provide registration of an image within an overall scene by shifting the frame of reference for an image so that unnatural movements do not occur as the animation proceeds through a sequence of states. The structure of the system permits an animation to be divided into distinct components that can be combined with complementary components of other animations, to provide new results. These components include a clip motion which defines a sequence of states, a clip character which applies the clip motion to a particular image configuration, and clip art."
"The various image examples can be associated with one another in a manner that defines a topological data structure which identifies their relationships. An example of such a data structure for the images of FIGS. 2A-2D is shown in FIG. 3. Referring thereto, each of the four image examples is associated with a vertex of a geometric shape. Specifically, the three image examples of FIGS. 2A, 2B, and 2C, which form one subset, define a triangular shape. The second subset, comprising the examples of FIGS. 2A, 2B, and 2D, defines a second triangle. Since the examples of FIGS. 2A and 2B are shared between the two subsets, the two triangles are joined along a common interface. Each subset of examples constitutes a simplex, or zone, and all of the zones together form a combinatorial structure, or state space, known as a simplicial complex. In the case illustrated in FIG. 5, the state space is composed of two triangular zones, ABC and ABD. While both zones in this case are two-dimensional structures, it is also possible for a state space to include one-dimensional zones, i.e. a line whose end points are defined by two examples, as well as multi-dimensional zones such as a tetrahedron defined by four examples."
"The combinatorial structure defines a state space for the graphics system. Any given point within this space defines a particular image, and movement within the state space causes the appearance of the image to change. More particularly, each of the vertices corresponds to one of the image examples shown in FIGS. 2A-2D. A point located between two vertices results in an interpolated image comprised of a representative portion of each of the two images associated with the respective vertices. Thus, as one moves from the lowest vertex A in the structure of FIG. 3 up the vertical line 10 to the highest vertex B, the figure's arms smoothly move from the position shown in FIG. 2A to that shown in FIG. 2B. Movement from the lowest vertex A to the left vertex C causes a transition in the image from that of FIG. 2A to that of FIG. 2C. A point located somewhere within the triangle defined by the three vertices A, B and C corresponds to an image in which the arms are partially raised and the right leg is partially lifted. For example, the point 12 represents a position in which the image is a weighted composite consisting of 60% of FIG. 2B, 30% of FIG. 2A and 10% of FIG. 2C. The percentages sum up to unity, and the weight values which correspond to these percentages, i.e. 0.6, 0.3 and 0.1, constitute a vector in barycentric coordinates. In a relatively simple embodiment of the invention, the examples are interpolated linearly; but in a different embodiment, the interpolation could employ non-linear functions, such as cubic polynomials. Any state s within the state space can be specified by a zone, in this case the zone containing the examples A, B and C, together with the vector, i.e. 0.3, 0.6, 0.1!."
[1] https://www.google.com/patents/US5933150
[2] https://www.flong.com/archive/projects/mouther/
[3] https://en.wikipedia.org/wiki/Simplicial_complex
But the real thing I wanted to mention here was the Poulsen Simplex [1]. This is the unique Choquet simplex [2] for which the extreme points are dense. This means that it's like an uncountably infinite dimensional triangle where no matter where you are inside the triangle, you're arbitrarily close to a corner. It's my favorite shape and absolutely wild and impossible to conceptualize (even though I worked with it daily for years!)
[0] https://en.wikipedia.org/wiki/Invariant_measure
[1] https://eudml.org/doc/74350
[2] https://en.wikipedia.org/wiki/Choquet_theory