Instructions

All of the files you need to modify can be found in the src/Assignment2/Polygon2D directory. There are four high-level things you will need to do to make your Catamari roll.

High-Level Tasks

• Implement line segment intersection in LineSegment.ts
• Implement a function that calculates the transform from polygon coordinates to world coordinates in Polygon2DModel.
• Implement polygon intersection in Polygon2D.ts
• Implement a function to roll stuff up in Polygon2DModel.ts

Part 1: Line Segment Intersection

We need to detect collisions if we want to roll up cats. As we saw in class, this collision detection can be broken down into testing for intersections between all the edges in one polygon and all the edges in another. But we suggest starting with the simpler case of detecting intersections between two simple line segments.

Tasks in [LineSegment.ts](TODO: add github link):

• Implement intersect(other:LineSegment):Vec2|undefined

You can implement this without worrying about transformation hierarchies for now; instead, we suggest using custom unit tests. Take a look at the tests in the src/Assignment2/Tests directory and add try adding some custom tests to src/Assignment2/Tests/MyTests.test.js

When this and other are on the same line and have overlapping portion, return the point on the overlapping portion as illustrated below.

(The illustration demonstrates 4 possible cases of line segments conbination with overlapping portion. Return the redpoint on the illustration.)

1. If other.start is on this segment, return other.start.

2. else If other.end is on this segment , return other.end.

3. else: (we reach the last case on our 4-case illustration, where this is totally inside other) return this.start.

Hint: Use Precision.epsilon for float comparison.

Tasks in [MyTests.test.js](TODO: add github link):

• Implement unit tests to test your intersection code.

Part 2: World transforms & the Scene Graph

Once you have basic segment intersection working, let's build up to testing polygons against other polygons. To do that, we first need a way to transform the geometry of one polygon into the coordinate system used to define the other. A useful function here will be:

Polygon2D.GetTransformedBy(m:Mat3|Mat4):Polygon2D

which takes one polygon geometry and returns a new polygon with vertices that have been transformed by the provided matrix. With this function in hand, we still need to figure out the matrices that transform one object into the coordinate system of another. For this we need to understand how a scene graph works.

The scene graph is a hierarchy of coordinate systems rooted at the world coordinates of our game. Our player and each of our cats are nodes in this graph, represented as subclasses of the Polygon2DModel class. Each node model has a model.transform attribute that represents the Mat3 transformation from model coordinates (the coordinate system where the vertices stored in the Polygon2D model.verts are defined) to a parent coordinate system. Initially, all models have the shared World Coordinates as their coordinate system. When a cat gets rolled up, though, the parent coordinate system will change. When the parent is not world coordinates, then we will need to use a product of multiple transformations to get our polygon into world coordinates.

Implement the function model.getWorldTransform():Mat3, which should return the matrix that transforms a model's vertices into world coordinates. You can use model.parent to get the parent of a model, and you can check to see if the parent is another Polygon2DModel (i.e., not the root of the scene graph) using:

if(model.parent && parent instanceof Polygon2DModel){
    // this means the model is a child of some other model
}

Tasks in Polygon2DModel.ts

• getWorldTransform():Mat3

Part 3: Polygon Intersection

Now we have a way to transform the vertices of one polygon into the coordinate system of another. Use this and the LineSegment test you wrote in Part 1 to implement polygon collision detection.

You will implement three functions in Polygon2D for this:

• edgeAt(index:number):LineSegment a helper function that gets the ith edge of a polygon and returns it as a line segment
• getIntersectionsWithSegment(segment:LineSegment):Vec2[] a function that tests a polygon for intersections with a single line segment, returning all intersections
• getIntersectionsWithPolygon(other:Polygon2D) a function that tests a polygon for intersections with another polygon (by testing all of the segments in that polygon), returning all intersections

For these functions, assume that the polygons lie in the same coordinate system. Handle the difference in coordinate system in the getIntersectionsWith function in Polygon2DModel (hint: you can utilize the getIntersectionsWithPolygon function from Polygon2D and Polygon2D.GetTransformedBy(m:Mat3|Mat4):Polygon2D function).

Tasks in Polygon2D.ts:

• edgeAt(index:number):LineSegment
• getIntersectionsWithSegment(segment:LineSegment):Vec2[]
• getIntersectionsWithPolygon(other:Polygon2D)

Tasks in Polygon2DModel.ts

• getIntersectionsWith(other: Polygon2DModel): Vec2[]

Part 4: Roll It Up

Now that we have a way to detect intersections, let's get rolling! Write the rollItUp(target:Polygon2DModel) function, which will test for intersection with another polygon and adds it as a child if an intersection is found. The function adoptChild(newChild:Polygon2DModel) should be useful here:

    /**
     * Adds the provided Polygon2DModel as a child, and sets the child's parent to be this.
     * @param newChild
     */
    adoptChild(newChild:Polygon2DModel){
        newChild.reparent(this, false);
    }

Note that when one node becomes the child of another, its parent changes. And since the transform property of a node represents the transformation that maps its vertices to its parent, then this transform must change as well.

The fun of Katamari Damacy (and in our case, the moderate amusement of Catamari Damacy...) is that when you roll stuff up it makes the katamari (catamari) bigger, and the stuff you rolled can roll up more stuff. You can see how this works in the timeUpdate(t: number) function in CatamariGameSceneModel.ts:

const self = this;
// We are going to iterate over ALL of the cats.
for(let c of this.cats){
  // We are running this as the scene graph root object,
  // so if c.parent is `this` then it is a loose cat...
  if(c.parent === this){
    // Test for intersection with the player
    if(this.player.rollItUp(c)) {
      console.log("Cat captured by Prince!")
    }else{
      // If there is not an intersection with the player,
      // check to see if there is an intersection with any of
      // the player's descendants
      self.player.mapOverDescendants((capturedCat)=>{
        if((capturedCat as Polygon2DModel).rollItUp(c)){
          console.log("Cat captured by cat!")
        }
      })
    }
  }
}

Tasks in [Polygon2D.ts](TODO: add github link):

• rollItUp(target:Polygon2DModel):boolean

With that, roll up all the stuff!