From bedd6906eabdd513042d6a178d4dc56a3a41d1d3 Mon Sep 17 00:00:00 2001 From: Fox Caminiti Date: Fri, 16 Dec 2022 20:16:43 -0500 Subject: v3, file/build organization --- src/bezier.cpp | 415 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 415 insertions(+) create mode 100644 src/bezier.cpp (limited to 'src/bezier.cpp') diff --git a/src/bezier.cpp b/src/bezier.cpp new file mode 100644 index 0000000..6fca5cc --- /dev/null +++ b/src/bezier.cpp @@ -0,0 +1,415 @@ + +static real32 +Bezier_SolveYForX(v2 Point_P0, v2 Point_P1, v2 Point_P2, v2 Point_P3, real32 TargetX) { + + real32 Y = 0; + + v2 m1 = (Point_P2 - Point_P0) / (2 * Tau); + v2 m2 = (Point_P3 - Point_P1) / (2 * Tau); + + real32 Precision = 0.000001; + real32 t = (TargetX - Point_P0.x) / (Point_P3.x - Point_P0.x); + + int Iterations = 0; + for (;;) { + real32 t2 = t * t; + real32 t3 = t2 * t; + real32 mt = 1-t; + real32 mt2 = mt * mt; + real32 mt3 = mt2 * mt; + v2 Point = (Point_P0 * mt3) + (3 * Point_P1 * mt2 * t) + (3 * Point_P2 * mt * t2) + (Point_P3 * t3); + + bool32 Cond1 = (Point.x <= (TargetX - Precision)); + bool32 Cond2 = (Point.x >= (TargetX + Precision)); + + if ((Cond1 || Cond2) && Iterations < 10) { + t = t * TargetX / Point.x; + Iterations++; + } else { + Y = Point.y; + break; + } + } + + return Y; +} + +static bezier_point * +Bezier_LookupAddress(memory *Memory, property_channel *Property, uint16 Index, bool32 AssertExists) +{ + Assert(Index < MAX_KEYFRAMES_PER_BLOCK); // TODO(fox): Test multiple keyframe blocks! + block_bezier *Bezier = (block_bezier *)Memory_Block_AddressAtIndex(Memory, F_Bezier, Property->Block_Bezier_Index[0], AssertExists); + return &Bezier->Point[Index]; +} + +static void +Bezier_Interact_Evaluate(project_state *State, bezier_point *PointAddress, v2 *Pos, real32 GraphZoomHeight, real32 Y_Increment) +{ + Pos[0] = PointAddress->Pos[0]; + Pos[1] = PointAddress->Pos[1]; + Pos[2] = PointAddress->Pos[2]; + if (PointAddress->IsSelected) { + if (State->Interact_Active == interact_type_keyframe_move) { + if (State->Interact_Modifier != 2) + Pos[PointAddress->IsSelected - 1].x += (int32)State->Interact_Offset[0]; + if (State->Interact_Modifier != 1) + Pos[PointAddress->IsSelected - 1].y -= (State->Interact_Offset[1] / GraphZoomHeight / Y_Increment); + } else if (State->Interact_Active == interact_type_keyframe_scale) { + Pos[1].x += State->Interact_Offset[0]; + Pos[2].x -= State->Interact_Offset[0]; + } else if (State->Interact_Active == interact_type_keyframe_rotate) { + // how do I do this?? + Assert(0); + } + } +} + +static void +Bezier_Add(memory *Memory, memory_table_list TableName, property_channel *Property, bezier_point PointData, uint16 *ArrayLocation) +{ + if (!Property->Block_Bezier_Count) { + // TODO(fox): Test multiple keyframe blocks! + Assert(Property->Keyframe_Count < MAX_KEYFRAMES_PER_BLOCK); + Property->Block_Bezier_Index[0] = Memory_Block_AllocateNew(Memory, F_Bezier); + block_bezier *Bezier = (block_bezier *)Memory_Block_AddressAtIndex(Memory, F_Bezier, Property->Block_Bezier_Index[0], 0); + Bezier->Occupied = true; + History_Action_Swap(Memory, TableName, sizeof(Property->Block_Bezier_Count), &Property->Block_Bezier_Count); + Property->Block_Bezier_Count++; + } + // First check to see if the point to add overlaps an existing keyframe: + if (ArrayLocation) { + for (int p = 0; p < Property->Keyframe_Count; p++) { + int k = ArrayLocation[p]; + bezier_point *Point = Bezier_LookupAddress(Memory, Property, k); + if (Point->Pos[0].x == PointData.Pos[0].x) { + History_Action_Swap(Memory, F_Bezier, sizeof(*Point), Point); + *Point = PointData; + return; + } + } + } + int k = 0; + for (;;) { + bezier_point *Point = Bezier_LookupAddress(Memory, Property, k, 0); + if (!Point->Occupied) { + History_Action_Swap(Memory, F_Bezier, sizeof(*Point), Point); + *Point = PointData; + History_Action_Swap(Memory, TableName, sizeof(Property->Keyframe_Count), &Property->Keyframe_Count); + Property->Keyframe_Count++; + return; + } + k++; + } +} + +#if 0 +// A modified version of the bezier code in ImGui with extra features for bitmap and path interaction. + +// Function to convert a ratio back into a point for the bezier handles. +v2 Line_RatioToPoint(v2 a, v2 b, real32 ratio) +{ + v2 ab_dir = b - a; + real32 ab_len_sqr = ab_dir.x * ab_dir.x + ab_dir.y * ab_dir.y; + real32 dot = ratio*ab_len_sqr; + return a + ab_dir * dot / V2(ab_len_sqr); +} + +// The ratio here is just the dot product divided by the squared length. +v2 Bezier_LineClosestPoint2(v2 a, v2 b, v2 p, real32 *ratio) +{ + v2 ap = p - a; + v2 ab_dir = b - a; + real32 dot = ap.x * ab_dir.x + ap.y * ab_dir.y; + if (dot < 0.0f) { + *ratio = 0.0f; + return a; + } + real32 ab_len_sqr = ab_dir.x * ab_dir.x + ab_dir.y * ab_dir.y; + if (dot > ab_len_sqr) { + *ratio = 1.0f; + return b; + } + *ratio = dot / ab_len_sqr; + return a + ab_dir * dot / ab_len_sqr; +} + +// Following the algorithm, we take the ratio from the _leftmost_ point in each +// subdivision of the cubic spline until we're within tess_tol, and then we +// interpolate it with the subdivision's rightmost point in the ClosestPoint call. +// The pow(0.5, level) represents the ratio of the next subdivision's leftmost +// point (AKA the rightmost point of the current subdivision). + +// finds the point closest to p and also fills out its ratio along the curve +static void Bezier_CubicClosestPointCasteljauStep(v2 p, v2 *p_closest, real32 ratio, real32 *r_closest, v2 *p_last, real32 *p_closest_dist2, + real32 x1, real32 y1, real32 x2, real32 y2, real32 x3, real32 y3, real32 x4, real32 y4, real32 tess_tol, int level) +{ + real32 dx = x4 - x1; + real32 dy = y4 - y1; + real32 d2 = ((x2 - x4) * dy - (y2 - y4) * dx); + real32 d3 = ((x3 - x4) * dy - (y3 - y4) * dx); + d2 = (d2 >= 0) ? d2 : -d2; + d3 = (d3 >= 0) ? d3 : -d3; + if ((d2 + d3) * (d2 + d3) < tess_tol * (dx * dx + dy * dy)) + { + v2 p_current = V2(x4, y4); + real32 added_ratio; + v2 p_line = Bezier_LineClosestPoint2(*p_last, p_current, p, &added_ratio); + real32 dist2 = LengthSq(p - p_line); + if (dist2 < *p_closest_dist2) + { + *p_closest = p_line; + *p_closest_dist2 = dist2; + *r_closest = ratio + pow(0.5, level)*added_ratio; + } + *p_last = p_current; + } + else if (level < 10) + { + real32 x12 = (x1 + x2)*0.5f, y12 = (y1 + y2)*0.5f; + real32 x23 = (x2 + x3)*0.5f, y23 = (y2 + y3)*0.5f; + real32 x34 = (x3 + x4)*0.5f, y34 = (y3 + y4)*0.5f; + real32 x123 = (x12 + x23)*0.5f, y123 = (y12 + y23)*0.5f; + real32 x234 = (x23 + x34)*0.5f, y234 = (y23 + y34)*0.5f; + real32 x1234 = (x123 + x234)*0.5f, y1234 = (y123 + y234)*0.5f; + Bezier_CubicClosestPointCasteljauStep(p, p_closest, ratio, r_closest, p_last, p_closest_dist2, x1, y1, x12, y12, x123, y123, x1234, y1234, tess_tol, level + 1); + Bezier_CubicClosestPointCasteljauStep(p, p_closest, ratio + pow(0.5, level+1), r_closest, p_last, p_closest_dist2, x1234, y1234, x234, y234, x34, y34, x4, y4, tess_tol, level + 1); + } +} + +// finds the min/max bounds of the curve +static void Bezier_CubicMinMaxCasteljauStep(v2 *p_min, v2 *p_max, real32 x1, real32 y1, real32 x2, real32 y2, real32 x3, real32 y3, real32 x4, real32 y4, real32 tess_tol, int level) +{ + real32 dx = x4 - x1; + real32 dy = y4 - y1; + real32 d2 = ((x2 - x4) * dy - (y2 - y4) * dx); + real32 d3 = ((x3 - x4) * dy - (y3 - y4) * dx); + d2 = (d2 >= 0) ? d2 : -d2; + d3 = (d3 >= 0) ? d3 : -d3; + if ((d2 + d3) * (d2 + d3) < tess_tol * (dx * dx + dy * dy)) + { + v2 p_current = V2(x4, y4); + if (p_current.x < p_min->x) { + p_min->x = p_current.x; + } + if (p_current.y < p_min->y) { + p_min->y = p_current.y; + } + if (p_current.x > p_max->x) { + p_max->x = p_current.x; + } + if (p_current.y > p_max->y) { + p_max->y = p_current.y; + } + } + else if (level < 10) + { + real32 x12 = (x1 + x2)*0.5f, y12 = (y1 + y2)*0.5f; + real32 x23 = (x2 + x3)*0.5f, y23 = (y2 + y3)*0.5f; + real32 x34 = (x3 + x4)*0.5f, y34 = (y3 + y4)*0.5f; + real32 x123 = (x12 + x23)*0.5f, y123 = (y12 + y23)*0.5f; + real32 x234 = (x23 + x34)*0.5f, y234 = (y23 + y34)*0.5f; + real32 x1234 = (x123 + x234)*0.5f, y1234 = (y123 + y234)*0.5f; + Bezier_CubicMinMaxCasteljauStep(p_min, p_max, x1, y1, x12, y12, x123, y123, x1234, y1234, tess_tol, level + 1); + Bezier_CubicMinMaxCasteljauStep(p_min, p_max, x1234, y1234, x234, y234, x34, y34, x4, y4, tess_tol, level + 1); + } +} + +// return all points +static void Bezier_CubicCalcPointsCasteljauStep(void *Data, uint32 *Increment, real32 x1, real32 y1, real32 x2, real32 y2, real32 x3, real32 y3, real32 x4, real32 y4, real32 tess_tol, int level) +{ + real32 dx = x4 - x1; + real32 dy = y4 - y1; + real32 d2 = ((x2 - x4) * dy - (y2 - y4) * dx); + real32 d3 = ((x3 - x4) * dy - (y3 - y4) * dx); + d2 = (d2 >= 0) ? d2 : -d2; + d3 = (d3 >= 0) ? d3 : -d3; + if ((d2 + d3) * (d2 + d3) < tess_tol * (dx * dx + dy * dy)) + { + *((real32 *)Data + *Increment*3) = x4; + *((real32 *)Data + *Increment*3 + 1) = y4; + *((real32 *)Data + *Increment*3 + 2) = 0; + *Increment += 1; + } + else if (level < 10) + { + real32 x12 = (x1 + x2)*0.5f, y12 = (y1 + y2)*0.5f; + real32 x23 = (x2 + x3)*0.5f, y23 = (y2 + y3)*0.5f; + real32 x34 = (x3 + x4)*0.5f, y34 = (y3 + y4)*0.5f; + real32 x123 = (x12 + x23)*0.5f, y123 = (y12 + y23)*0.5f; + real32 x234 = (x23 + x34)*0.5f, y234 = (y23 + y34)*0.5f; + real32 x1234 = (x123 + x234)*0.5f, y1234 = (y123 + y234)*0.5f; + Bezier_CubicCalcPointsCasteljauStep(Data, Increment, x1, y1, x12, y12, x123, y123, x1234, y1234, tess_tol, level + 1); + Bezier_CubicCalcPointsCasteljauStep(Data, Increment, x1234, y1234, x234, y234, x34, y34, x4, y4, tess_tol, level + 1); + } +} + +real32 Bezier_CubicRatioOfPoint(v2 p1, v2 p2, v2 p3, v2 p4, v2 p) +{ + real32 tess_tol = TESS_TOL; + v2 p_last = p1; + v2 p_closest; + real32 p_closest_dist2 = FLT_MAX; + real32 ratio = 0; + Bezier_CubicClosestPointCasteljauStep(p, &p_closest, 0, &ratio, &p_last, &p_closest_dist2, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, tess_tol, 0); + return ratio; +} + +void Bezier_CubicCalcPoints(v2 p1, v2 p2, v2 p3, v2 p4, void *Data, uint32 *Increment) +{ + real32 tess_tol = TESS_TOL; + void *Pointer = Data; + Bezier_CubicCalcPointsCasteljauStep(Pointer, Increment, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, tess_tol, 0); +} + +// These functions will become more generalized as shapes are added. + +static void +Mask_AddPointToLine(mask *Mask, uint16 Index, v2 Pos) +{ + for (int i = Mask->NumberOfPoints - 1; i > Index; i--) { + Mask->Point[i+1] = Mask->Point[i]; + } + mask_point *PointToAdd = &Mask->Point[Index+1]; + PointToAdd->Pos = Pos; + Mask->NumberOfPoints++; +} + +static void +Mask_PushPoint(mask *Mask, v2 Pos) +{ + mask_point *PointToAdd = &Mask->Point[Mask->NumberOfPoints]; + PointToAdd->Pos = Pos; + Mask->NumberOfPoints++; +} + +static void +Mask_ShiftPointers(mask *Mask, int16 Increment, int16 StopAt) { + if (Increment > 0) { + int16 i = Mask->NumberOfPoints - 1; + while (i >= StopAt) { + mask_point *CurrentPoint = &Mask->Point[i]; + mask_point *NextPoint = &Mask->Point[i + Increment]; + *NextPoint = *CurrentPoint; + i--; + } + } else { + int16 i = StopAt; + while (i <= Mask->NumberOfPoints - 1) { + mask_point *CurrentPoint = &Mask->Point[i]; + mask_point *NextPoint = &Mask->Point[i - Increment]; + *CurrentPoint = *NextPoint; + i++; + } + } +} + +static void +Mask_DeletePoint(memory *Memory, mask *Mask, uint16 Index) +{ + History_Entry_Commit(Memory, action_entry_default, "Delete keyframe"); + mask_point *MaskPointIndex = &Mask->Point[Index]; + History_Action_StoreData(Memory, MaskPointIndex, sizeof(mask_point)); + + History_Action_Change_Decrement(Memory, &Mask->NumberOfPoints, action_type_change_u16); + // History_Action_Shift(Memory, action_type_shift_bezier, Mask, -1, Index); + void *StartingAddress = &Mask->Point[0]; + History_Action_Shift_2(Memory, StartingAddress, sizeof(mask_point), Mask->NumberOfPoints, -1, Index); + // Mask_ShiftPointers(Mask, -1, Index); + History_Entry_End(Memory); +} + +// It's more useful to input the ratio here instead of the cursor position +// since we have to use it to calculate the four new handle lengths (two on the +// new point and one on each edge). +static void +Mask_AddPointToCurve(memory *Memory, mask *Mask, uint16 Index, real32 ratio) +{ + mask_point *Point0 = &Mask->Point[Index]; + mask_point *Point1 = &Mask->Point[Index+1]; + if (Index + 1 == Mask->NumberOfPoints) + Point1 = &Mask->Point[0]; + + v2 Point0_Pos_Right = Point0->Pos + Point0->TangentRight; + v2 Point1_Pos_Left = Point1->Pos + Point1->TangentLeft; + v2 Handle0_Half = Line_RatioToPoint(Point0->Pos, Point0_Pos_Right, ratio); + v2 Handle1_Half = Line_RatioToPoint(Point1_Pos_Left, Point1->Pos, ratio); + v2 Top_Half = Line_RatioToPoint(Point0_Pos_Right, Point1_Pos_Left, ratio); + v2 NewHandleLeft = Line_RatioToPoint(Handle0_Half, Top_Half, ratio); + v2 NewHandleRight = Line_RatioToPoint(Top_Half, Handle1_Half, ratio); + v2 NewPos = Line_RatioToPoint(NewHandleLeft, NewHandleRight, ratio); + + History_Entry_Commit(Memory, action_entry_default, "Add point to curve"); + + v2 NewPoint0Pos = -(Point0->Pos - Handle0_Half); + v2 NewPoint1Pos = -(Point1->Pos - Handle1_Half); + History_Action_Change_V2(Memory, &Point0->TangentRight, &Point0->TangentRight, &NewPoint0Pos); + History_Action_Change_V2(Memory, &Point1->TangentLeft, &Point1->TangentLeft, &NewPoint1Pos); + + void *StartingAddress = &Mask->Point[0]; + History_Action_Shift_2(Memory, StartingAddress, sizeof(mask_point), Mask->NumberOfPoints, 1, Index); + + mask_point *PointToAdd = &Mask->Point[Index+1]; + + // NOTE(fox): The above shift duplicates the keyframe at Index into where + // we're writing, Index+1. I'm using the Change action (which is normally + // for changing values that already exist) on this intermediate keyframe + // slot to save having to write a bunch of special actions for shifting and + // adding new data. + + History_Action_Change_V2(Memory, &PointToAdd->Pos, &PointToAdd->Pos, &NewPos); + v2 NewLeftPos = -(NewPos - NewHandleLeft); + v2 NewRightPos = -(NewPos - NewHandleRight); + History_Action_Change_V2(Memory, &PointToAdd->TangentLeft, &PointToAdd->TangentLeft, &NewLeftPos); + History_Action_Change_V2(Memory, &PointToAdd->TangentRight, &PointToAdd->TangentRight, &NewRightPos); + + History_Action_Change_Increment(Memory, &Mask->NumberOfPoints, action_type_change_u16); + History_Entry_End(Memory); +} + +static void +Mask_RasterizePoints(mask *Mask) +{ + Mask->NumberOfVerts = 0; + for (int i = 0; i < Mask->NumberOfPoints; i++) { + mask_point Point0 = Mask->Point[i]; + mask_point Point1 = Mask->Point[i+1]; + if (i+1 == Mask->NumberOfPoints) + Point1 = Mask->Point[0]; + + if (Point0.HandleBezier && Point1.HandleBezier) { + Bezier_CubicCalcPoints(Point0.Pos, Point0.Pos + Point0.TangentRight, Point1.Pos + Point1.TangentLeft, Point1.Pos, + Mask->TriangulatedPointCache, &Mask->NumberOfVerts); + } else if (Point0.HandleBezier) { + Bezier_CubicCalcPoints(Point0.Pos, Point0.Pos + Point0.TangentRight, Point1.Pos, Point1.Pos, + Mask->TriangulatedPointCache, &Mask->NumberOfVerts); + } else if (Point1.HandleBezier) { + Bezier_CubicCalcPoints(Point0.Pos, Point0.Pos, Point1.Pos + Point1.TangentLeft, Point1.Pos, + Mask->TriangulatedPointCache, &Mask->NumberOfVerts); + } else { + real32 *Data = (real32 *)Mask->TriangulatedPointCache + Mask->NumberOfVerts*3; + *(Data++) = Point0.Pos.x; + *(Data++) = Point0.Pos.y; + *(Data++) = 0; + // NOTE(fox): CubicCalcPoints sometimes misses generating the start + // point of the next path in the above two cases, so I'm making + // straight lines always add both points as a hotfix. This leads + // to cases of duplicate verts, but it doesn't seem like it harms + // the rendering in any way. + *(Data++) = Point1.Pos.x; + *(Data++) = Point1.Pos.y; + *(Data++) = 0; + Mask->NumberOfVerts += 2; + } + } +} + +void Mask_TriangulateAndRasterize(memory *Memory, project_layer *Layer, mask *Mask) +{ + if (!Mask->TriangulatedPointCache) { + Mask->TriangulatedPointCache = AllocateMemory(Memory, 50*1024, P_VectorPoints); + } + Mask_RasterizePoints(Mask); + + GL_RasterizeShape(Layer, Mask); +} +#endif -- cgit v1.2.3