이번에는 npc와의 상호작용과 이를 통해 npc와 대화를 할 수 있도록 만들어보자. 상호작용은 저번에 추가해준 InputAction을 통해 작동하도록 하자.

우선 대화 text는 Ink 라이브러리를 통해 만들어줄 것이다. Ink는 Asset Store를 통해 Import해주고  Inky라는 에디터를 통해 대화를 만들어주면 된다. 

Inky는 다음 링크를 통해 다운받을 수 있다.

https://www.inklestudios.com/ink/

 

ink - inkle's narrative scripting language

Support us! ink is the product of years of thought, design, development and testing. If ink has proved useful to you, please consider making a donation to help us continue to develop the tool. Thank you!

www.inklestudios.com

 

나는 상호작용 버튼을 눌렀을 때 레이케스트를 실행하고 만약 상호작용 가능한 객체라면 상호작용했을 때의 함수를 호출해주는 식으로 만들어보았다.

 // 상호작용 콜백함수
 public void Perform(InputAction.CallbackContext context)
 {

     InteractWithObject();
 }

 private void InteractWithObject()
 {
     DebugEx.Log($"InteractStarted");
     RaycastHit2D hit = Physics2D.Raycast(transform.position, facingDirection, interactDistance, LayerMask.GetMask("Interactable"));

     if (hit.collider != null)
     {
         IInteractable interactable = hit.collider.GetComponent<IInteractable>();
         if (interactable != null)
         {
             interactable.Interact();
         }
     }
 }
 
  private void OnDrawGizmos()
 {
     // 레이케스트 시각화
     Gizmos.color = Color.green;
     Gizmos.DrawLine(transform.position, transform.position + (Vector3)facingDirection * interactDistance);
 }


private void OnEnable()
{
    playerInputActions.PlayerAction.Interact.performed += Perform;
    playerInputActions.Enable();
}

 

그리고 이와 상호작용할 수 있도록 인터페이스를 하나 만들어주었다. 상호가능한 객체라면 이 인터페이스를 상속받게 하여 상호작용했을 때의 이벤트를 실행하도록 해주었다.

namespace Controllers.Entity
{
    public interface IInteractable
    {
        /// <summary>
        /// IInteractable의 필수 구현 사항
        /// </summary>
        void Interact();
    }
}

 

대화창이 출력되고 대화에 대한 정보를 관리해줄 DialogueManager를 만들어주자. 

using Ink.Runtime;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.EventSystems;

public class DialogueManager : MonoBehaviour
{
    [Header("NPC Data")]
    private npcData npcdata;
    public Story currentStory;

    private const string SPEAKER_TAG = "speaker";                   //테그값들 테그값 : 변수
    private const string PORTRAIT_TAG = "portrait";

    public UI_DialoguePopup popup;

    public bool dialogueIsPlaying { get; private set; }             //현재 대화창에 진입했는지 확인할 변수

    private void Awake()
    {
        dialogueIsPlaying = false;
    }


    public void GetTalk2(TextAsset dialogue, npcData npc)
    {
       
        Player player = Managers.Game.GetPlayer().GetComponent<Player>();
        npcdata = npc;
        currentStory = new Story(dialogue.text);
        popup = Managers.UI.ShowPopupUI<UI_DialoguePopup>();

        //태그 초기화
        dialogueIsPlaying = true;
        ContinueStory();
    }

    public void ContinueStory()
    {
        if (currentStory.canContinue) //더 보여줄 이야기가 있다면
        {
            popup.displayNameText.text = npcdata.getName();
            popup.dialogueText.text = currentStory.Continue();  // 한줄 출력
        }
        else
        {
            ExitDialogueMode();
        }
    }

    private void ExitDialogueMode()
    {
        dialogueIsPlaying = false;
        popup.dialogueText.text = "";
        Managers.UI.ClosePopupUI();
    }
}

그리고 npc에 관한 정보를 담고 이 상호작용 인터페이스를 상속받는 npcdata 클래스를 만들어주었다. 이때 

using Controllers.Entity;
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using VInspector;

public class npcData : MonoBehaviour, IInteractable
{
    [Tab("Visual Cue")]
    [SerializeField] public GameObject[] visualCue;
    [Tab("NPC Inform")]
    [SerializeField] private int npcId;
    [SerializeField] private string npcName;
    [SerializeField] private bool isNpc;
    [SerializeField] public Sprite[] npcPortrait;
    [SerializeField] private TextAsset dialogue;
    public bool playerInRange;

    public string getName() { return npcName; }

    private void Awake()
    {
        playerInRange = false;
        foreach (GameObject cue in visualCue)
        {
            cue.SetActive(false);
        }
    }


    private void OnCollisionEnter2D(Collision2D collision)
    {
        if (collision.gameObject.CompareTag("Player"))
        {
            playerInRange = true;
        }
    }

    private void OnCollisionExit2D(Collision2D collision)
    {
        if (collision.gameObject.CompareTag("Player"))
        {
            playerInRange = false;
        }
    }


    public void Interact()
    {
        if (playerInRange && !Managers.Dialogue.dialogueIsPlaying)
        {
           Managers.Dialogue.GetTalk2(dialogue, this);
        }
        else if (playerInRange && Managers.Dialogue.dialogueIsPlaying)
        {
            Managers.Dialogue.ContinueStory();
        }

    }
}

 

이렇게 해준 다음 대화창 이미지를 관리해줄 클래스도 만들어주자

using System;
using System.Collections;
using System.Collections.Generic;
using TMPro;
using UnityEngine;
using UnityEngine.EventSystems;
using UnityEngine.UI;

public class UI_DialoguePopup : UI_Popup
{
    [SerializeField] private GameObject DialoguePopup;
    [SerializeField] public GameObject dialoguePanel;
    [SerializeField] public TextMeshProUGUI dialogueText;
    [SerializeField] public TextMeshProUGUI displayNameText;
    [SerializeField] public Image portraitImage;

    [SerializeField] public TextMeshProUGUI[] choicesText;
    [SerializeField] public GameObject[] choices;
    [SerializeField] public GameObject choicep;
    [SerializeField] public Button[] choiceButton;
    private bool isAction;

    public override void Init()
    {
        DialoguePopup = this.gameObject;
        dialoguePanel = DialoguePopup.transform.GetChild(0).gameObject;
        dialogueText = dialoguePanel.transform.GetChild(0).gameObject.GetComponent<TextMeshProUGUI>();
        displayNameText = dialoguePanel.transform.GetChild(3).GetChild(0).GetComponent<TextMeshProUGUI>();
        portraitImage = dialoguePanel.transform.GetChild(4).GetComponent<Image>();

        choicep = dialoguePanel.transform.GetChild(2).gameObject;
        choices = new GameObject[2] { dialoguePanel.transform.GetChild(2).GetChild(0).gameObject, dialoguePanel.transform.GetChild(2).GetChild(1).gameObject };
        choicesText = new TextMeshProUGUI[2] { choices[0].GetComponentInChildren<TextMeshProUGUI>(), choices[1].GetComponentInChildren<TextMeshProUGUI>() };
        choiceButton = new Button[2] { choices[0].GetComponent<Button>(), choices[1].GetComponent<Button>() };
    }

    private void Awake()
    {
        Init();
    }
   
}

 

이렇게 해주면 대화창이 올바르게 출력되는 것을 볼 수 있다.

 



강의

https://inf.run/zKor1

 

학습 페이지

 

www.inflearn.com

 

 

오늘은 Normal Mapping 과 Displacement Mapping에 대해 학습하고 예제코드를 분석해보자.

우선 Normal Mapping은 물체를 정밀하게 표현하기 위해서는 삼각형의 개수를 늘리는 방법도 있지만 이 방법은 너무 부하가 많아진다. 그렇기 때문에 삼각형의 개수를 늘리지 않고 물체 표면의 Normal 값을 조정해주는 것으로 물체의 표면을 정밀하게 표현한다. 

이때 조정할 노멀 값을 모아서 노말 텍스처를 만들어주게 되는데 이때 텍스처에는 tagent Space 좌표계가 적용되어 있는데 이때 n(normal)값이 제일 많기 때문에 파란색으로 표현되곤 한다. 이 텍스처의 normal값을 추출해서 물체에 적용해주면 된다.

우선 코드를 실행시켜보면 왼쪽에는 Normal Mapping이 적용되지 않은 모습이고 오른쪽에는 Normal Mapping이 적용된 모습이다.

 

보통 노멀매핑은 24비트로 8비트씩 나눠서 3개의 좌표를 사용한다. 1바이트이기 때문에 각 값은 0~1사이의 값으로

표현한다. 이를 float -1~1까지의 값으로 치환해주는 공식을 통해 치환해주게 된다.

이때 tagent space라는 개념이 나오는데 이 정보는 매쉬의 정점에 포함된 정보로 이 좌표계를 기준으로 하는 x,y,z정보를 텍스처공간에 저장해주고 이 값을 통해 Normal Mapping을 해주는 것이다. 이때  정점 정보를 입력해줄 때 VertexIn 구조체의 정보와 같이 노멀정보와 탄젠트 정보를 넣어주어야한다. 

 

예제 코드에서 쉐이더 부분을 살펴보자면 노멀 정보를 가져와서 월드좌표로 바꿔주는 부분이 함수로 만들어져있고 이를 PS단계에서 호출하여 사용해주고 있다.

struct VertexIn
{
    float3 PosL     : POSITION;
    float3 NormalL  : NORMAL;
    float2 Tex      : TEXCOORD;
    float3 TangentL : TANGENT;
};

struct VertexOut
{
    float4 PosH     : SV_POSITION;
    float3 PosW     : POSITION;
    float3 NormalW  : NORMAL;
    float3 TangentW : TANGENT;
    float2 Tex      : TEXCOORD;
};

VertexOut VS(VertexIn vin)
{
    VertexOut vout;

    // Transform to world space space.
    vout.PosW = mul(float4(vin.PosL, 1.0f), gWorld).xyz;
    vout.NormalW = mul(vin.NormalL, (float3x3)gWorldInvTranspose);
    vout.TangentW = mul(vin.TangentL, (float3x3)gWorld);

    // Transform to homogeneous clip space.
    vout.PosH = mul(float4(vin.PosL, 1.0f), gWorldViewProj);

    // Output vertex attributes for interpolation across triangle.
    vout.Tex = mul(float4(vin.Tex, 0.0f, 1.0f), gTexTransform).xy;

    return vout;
}

Texture2D gNormalMap;

float3 normalMapSample = gNormalMap.Sample(samLinear, pin.Tex).rgb;
float3 bumpedNormalW = NormalSampleToWorldSpace(normalMapSample, pin.NormalW, pin.TangentW);

 

월드좌표로 변환해줄 때 텍스처에서 UV좌표를 이용하여 특정 좌표를 구한다음에 그 값을 -1~1사이의 값으로 공식을 통해 변환해준 다음 월드좌표로 변환해주고 있다. 이때 이미 VS값에서 World를 구해줬지만 PS단계에서 보간때문에 normal과 tagent의 수직이 깨질 수 있기 때문에 이를 수정해주기 위해 탄젠트 값을 다시 연산을 해준 다음 탄젠트 스페이스에서 월드 스페이스로 변환해주고 있다.

//---------------------------------------------------------------------------------------
// Transforms a normal map sample to world space.
//---------------------------------------------------------------------------------------
float3 NormalSampleToWorldSpace(float3 normalMapSample, float3 unitNormalW, float3 tangentW)
{
	// Uncompress each component from [0,1] to [-1,1].
	float3 normalT = 2.0f * normalMapSample - 1.0f;

	// Build orthonormal basis.
	float3 N = unitNormalW;
	float3 T = normalize(tangentW - dot(tangentW, N) * N);
	float3 B = cross(N, T);

	float3x3 TBN = float3x3(T, B, N);

	// Transform from tangent space to world space.
	float3 bumpedNormalW = mul(normalT, TBN);

	return bumpedNormalW;
}

 

그리고 이렇게 변환된 값을  통해 빛연산을 해주고 있다.

// Sum the light contribution from each light source.  
[unroll]
for (int i = 0; i < gLightCount; ++i)
{
    float4 A, D, S;
    ComputeDirectionalLight(gMaterial, gDirLights[i], bumpedNormalW, toEye,
        A, D, S);

    ambient += A;
    diffuse += D;
    spec += S;
}

litColor = texColor * (ambient + diffuse) + spec;

if (gReflectionEnabled)
{
    float3 incident = -toEye;
    float3 reflectionVector = reflect(incident, bumpedNormalW);
    float4 reflectionColor = gCubeMap.Sample(samLinear, reflectionVector);

    litColor += gMaterial.Reflect * reflectionColor;
}

 

다음은 Displacement Mapping 표면에 굴곡과 균열을 묘사하는 높이 값을 넘겨주고 이를 통해 기하구조를 변경하는 것이다. 구현은 노멀매핑에서 w값을 height로 사용하거나 따로 텍스처를 만들어주면 된다. 왼쪽이 Normal Mapping만 적용된 화면이고 오른쪽이 Displacement Mapping까지 적용된 모습이다.

 

이 표면의 높이값을 실시간으로 조정해주기 위해서는 매쉬를 직접 조정해주는 방법도 있지만 이렇게 하면 부하가 심해지기 때문에 정점을 건드리지 않고 조정해줄 방법을 찾아야하는데 Tesellation 단계를 통해 조정을 해준다. 

 

코드를 보면 예제에서는 노멀 텍스처w값을 추출해서 사용하는 것을 볼 수 있다.

Texture2D gNormalMap;


PatchTess PatchHS(InputPatch<VertexOut, 3> patch,
    uint patchID : SV_PrimitiveID)
{
    PatchTess pt;

    // Average tess factors along edges, and pick an edge tess factor for 
    // the interior tessellation.  It is important to do the tess factor
    // calculation based on the edge properties so that edges shared by 
    // more than one triangle will have the same tessellation factor.  
    // Otherwise, gaps can appear.
    pt.EdgeTess[0] = 0.5f * (patch[1].TessFactor + patch[2].TessFactor);
    pt.EdgeTess[1] = 0.5f * (patch[2].TessFactor + patch[0].TessFactor);
    pt.EdgeTess[2] = 0.5f * (patch[0].TessFactor + patch[1].TessFactor);
    pt.InsideTess = pt.EdgeTess[0];

    return pt;
}

struct HullOut
{
    float3 PosW     : POSITION;
    float3 NormalW  : NORMAL;
    float3 TangentW : TANGENT;
    float2 Tex      : TEXCOORD;
};

[domain("tri")]
[partitioning("fractional_odd")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(3)]
[patchconstantfunc("PatchHS")]
HullOut HS(InputPatch<VertexOut, 3> p,
    uint i : SV_OutputControlPointID,
    uint patchId : SV_PrimitiveID)
{
    HullOut hout;

    // Pass through shader.
    hout.PosW = p[i].PosW;
    hout.NormalW = p[i].NormalW;
    hout.TangentW = p[i].TangentW;
    hout.Tex = p[i].Tex;

    return hout;
}



struct DomainOut
{
    float4 PosH     : SV_POSITION;
    float3 PosW     : POSITION;
    float3 NormalW  : NORMAL;
    float3 TangentW : TANGENT;
    float2 Tex      : TEXCOORD;
};

//테셀레이션- 최종 위치결정
[domain("tri")]
DomainOut DS(PatchTess patchTess,
    float3 bary : SV_DomainLocation,
    const OutputPatch<HullOut, 3> tri)
{
    DomainOut dout;

    dout.PosW = bary.x * tri[0].PosW + bary.y * tri[1].PosW + bary.z * tri[2].PosW;
    dout.NormalW = bary.x * tri[0].NormalW + bary.y * tri[1].NormalW + bary.z * tri[2].NormalW;
    dout.TangentW = bary.x * tri[0].TangentW + bary.y * tri[1].TangentW + bary.z * tri[2].TangentW;
    dout.Tex = bary.x * tri[0].Tex + bary.y * tri[1].Tex + bary.z * tri[2].Tex;

    dout.NormalW = normalize(dout.NormalW);



    const float MipInterval = 20.0f;
    float mipLevel = clamp((distance(dout.PosW, gEyePosW) - MipInterval) / MipInterval, 0.0f, 6.0f);

    //텍스처에서 height 추출
    float h = gNormalMap.SampleLevel(samLinear, dout.Tex, mipLevel).a;

    //포지션 조정
    dout.PosW += (gHeightScale * (h - 1.0)) * dout.NormalW;

      //포지션 조정
    dout.PosH = mul(float4(dout.PosW, 1.0f), gViewProj);

    return dout;
}


오늘은 Sky Box에 대해 코드를 보며 학습해보자.

우선 예제코드를 실행해보면 풍경이 담긴 Sky Box가 적용되어 있는 모습을 볼 수 있다.

 

전에 Sky Box를 구현할 때는 커다란 구를 만들어두고 여기에 텍스처를 붙이고 우리가 안에서 그 텍스처를 보는 방식으로 

구현했었다. 이때 안쪽을 볼 수 있게 하기 위해 기존에 컬링으로 후면을 제거해줬는데 이를 없애고 전면을 없애는 방식으로 바꿔주어야 했고 카메라가 움직임에 따라 따라가게 해야했다. 그리고 스카이박스는 깊이를 1에 가깝게 만들어서 물체가

그려질 수 있고 Sky Box가 제일 끝에 위치하도록 만들어 줬다.

 

지금이 예제에는 구가 아닌 큐브를 통해 6면에 텍스처를 붙여주는 것으로 Sky Box를 구현해주고 있다. 이를 위해 상하좌우 풍경에 따라 다른 텍스처를 매핑해줘야한다. 이렇게 해주기 위해 3D Look up Vector를 사용하여 매핑해준다. 이 벡터를 활용하는 방법은 중심에서 가리키는 벡터에 따라 그려주는 연산을 해준다.

 

우선 쉐이더 코드를 살펴보자. 텍스처를 받아오는 변수로 TextureCube를 통해 받아오고 있으며 이를 PS단계에서 Sampler 연산을 해줄 때 pin.PosL가 Look up Vector이다. 

TextureCube gCubeMap;

float4 PS(VertexOut pin) : SV_Target
{
	return gCubeMap.Sample(samTriLinearSam, pin.PosL);
}

 

그리고 이 pin값은 VS단계에서 위치를 xyww로 밀어주고 있다. 이는 깊이값이 정확하게 1이 되도록 해주는 것이다. 이를 통해 SkyBox가 제일 뒤에 있어서 물체가 그려질 수 있다. 그리고 원점을 기준으로하는 로컬좌표를 넘겨주는 것으로 로컬좌표를 통해 각 정점의 위치로의 벡터도 나중에 만들어 줄 수 있게 한다.

VertexOut VS(VertexIn vin)
{
	VertexOut vout;

	// Set z = w so that z/w = 1 (i.e., skydome always on far plane).
	vout.PosH = mul(float4(vin.PosL, 1.0f), gWorldViewProj).xyww;

	// Use local vertex position as cubemap lookup vector.
	vout.PosL = vin.PosL;

	return vout;
}

 

그리고 밑의 코드를 보면 컬링을 꺼주고 원래 깊이가 1인 오브젝트도 그려줄 수 있도록 옵션 설정을 해주고 있다.

RasterizerState NoCull
{
	CullMode = None;
};

DepthStencilState LessEqualDSS
{
	// Make sure the depth function is LESS_EQUAL and not just LESS.  
	// Otherwise, the normalized depth values at z = 1 (NDC) will 
	// fail the depth test if the depth buffer was cleared to 1.
	DepthFunc = LESS_EQUAL;
};

 

이렇게 해주면 큐브 매핑을 통한 기본적인 Sky Box를 구현할 수 있다.

 

다음으로 다이나믹 큐브맵에 대해 알아보자. 다이나믹 큐브맵을 주변 환경을 반사하는 모습을 표현할 때 자주 활용된다.

우선 예제코드를 실행해보면 가운데 구에 주변 환경이 반사되어 보이는 것을 볼 수 있다.

 

이것을 구현하는 것은 스텐실을 활용해서 실시간으로 여섯면을 만들어줘야한다. Dynamic Cube라고 했지만 구 모양을 그려주고 있는데 이는 큐브모양을 look up vector를 통해 오려붙여서 구를 만들어 줄 수 가 있다. 구에 반사되는 모습은 카메라를 원점에 위치시키고 반사 공식을 통해 구한 각 6면의 장면을 텍스처로 만든 다음 이를 적용 시켜 주면 된다.

 

코드를 살펴보면 동적으로 큐브맵 텍스처를 만들기 위해 각 장면을 화면이 아닌 텍스처에 먼저 그려주기 위한 변수가 있다. 그리고 원래 DrawScene이 원래 Scene을 그리지만 당장 화면에 그려주는 것이 아니라 텍스처로 그려줄 수 있다는 것을 볼 수 있다. 

이때 구의 각면에 적용할 DepthStencilView도 따로 적용해주고 있다. 이는 구에 적용하는 해상도에 맞춰서 적용해줘야하기 때문이다.

//각 장면을 텍스처로 저장하기 위한 변수
ComPtr<ID3D11RenderTargetView> _dynamicCubeMapRTV[6];

//6면의 카메라
Camera _cubeMapCamera[6];


void DynamicCubeMapDemo::DrawScene()
{
	ID3D11RenderTargetView* renderTargets[1];

	// 각 면을 텍스처로 저장
	_deviceContext->RSSetViewports(1, &_cubeMapViewport);
	for (int i = 0; i < 6; ++i)
	{
		// Clear cube map face and depth buffer.
		_deviceContext->ClearRenderTargetView(_dynamicCubeMapRTV[i].Get(), reinterpret_cast<const float*>(&Colors::Silver));
		_deviceContext->ClearDepthStencilView(_dynamicCubeMapDSV.Get(), D3D11_CLEAR_DEPTH | D3D11_CLEAR_STENCIL, 1.0f, 0);

		// Bind cube map face as render target.
		renderTargets[0] = _dynamicCubeMapRTV[i].Get();
		_deviceContext->OMSetRenderTargets(1, renderTargets, _dynamicCubeMapDSV.Get());

		// Draw the scene with the exception of the center sphere to this cube map face.
		DrawScene(_cubeMapCamera[i], false);
	}

	// 화면에 그려줄 수 있도록 렌더타켓 초기화
	_deviceContext->RSSetViewports(1, &_viewport);
	renderTargets[0] = _renderTargetView.Get();
	_deviceContext->OMSetRenderTargets(1, renderTargets, _depthStencilView.Get());

	// Have hardware generate lower mipmap levels of cube map.
	_deviceContext->GenerateMips(_dynamicCubeMapSRV.Get());

	// 구를 포함한 전체 그려주기
	_deviceContext->ClearRenderTargetView(_renderTargetView.Get(), reinterpret_cast<const float*>(&Colors::Silver));
	_deviceContext->ClearDepthStencilView(_depthStencilView.Get(), D3D11_CLEAR_DEPTH | D3D11_CLEAR_STENCIL, 1.0f, 0);

	DrawScene(_camera, true);

	HR(_swapChain->Present(0, 0));
}

 

 

여기서 핵심은 UV매핑이 아닌 Look up Vector를 활용하여 텍스처를 그려줄 수 있고 이를 통해 환경이나 거울 같은 오브젝트를 그려줄 때도 사용할 수 있다는 것을 알 수 있다.


오늘은 Picking에 대한 내용을 복습하고 예제코드를 분석해보자.

우선 예제코드를 실행해보면 

자동차 오브젝트가 있다. 이 자동차 오브젝트를 우클릭해보면 클릭하는 면에 클릭이 적용되고 있는 모습을 볼 수 있다.

 

피킹은 마우스 커서로 우리가 찍은 좌표를 통해 물체를 파악하는 것이다. 이것이 중요한 이유는 3D 게임에서 클릭을 한다고 했을 때 2D화면 좌표계에서 선택한 좌표를 3D로 변환줘야한다. 이를 통해 어떤 것을 클릭해주는 지 알 수 있기 때문이다.

 

피킹 연산은 우리가 물체를 그려주기 위해 했던 로컬,월드,뷰,프로젝션,NDC,Screen까지의 연산의 반대로 해주면 된다.

이때 매쉬랑 충돌 판정을 한다는 것은 매쉬의 모든 삼각형을 순회하면서 레이케스팅을 해주는 것이다.

만약 예제코드와 같이 자동차안에서도 삼각형으로 분할되어 있는 세밀한 부분에 티킹 연산을 해준다고 하면 기존 오브젝트가 있는 로컬좌표로 클릭한 스크린 좌표를 변환해서 연산해주는 것이  더 좋을 것이다.

피킹연산은 CPU에서 이루어 진다. 월드 변환은 GPU에서 이루어 지고 이에 관한 정보도 GPU에서 가지고 있다. 그렇기 때문에 CPU에서는 피킹 연산에서  각 월드 좌표를 가지고 있지 않고 연산량이 적은 좌표계로 변환해서 연산해주면 된다. 

즉 레이케스트의 광선을 오브젝트의 로컬로 변환해서 연산해주면 되는 것이다.

 

그리고 연산에서 먼저 세밀한 부분에 피킹 연산을 해주기 보다는 충돌 영역을 지정해두고 여기에 충돌하면 2단계로 세밀한 부분에 피킹 연산을 해주는 것으로 최적화 해줄 수 있다.

 

코드를 보면 광선을 로컬좌표로 변환하고 있고 이를 통해 레이케스팅 연산을 해주고 있다. 이때 위에서 이야기한대로 먼저 대략적인 충돌영역으로 충돌처리를 해주고 만약 충돌했다면 2단계로 모든 삼각형에 순회를 해주며 충돌 연산을 해주고 있다. 그리고 피킹을 했을 때 가장 가까이 있는 오브젝트에 피킹을 해주어야하기 때문에 이러한 값을 추가해서 검사해주는 것을 볼 수 있다.

void PickingDemo::Pick(int32 sx, int32 sy)
{
	XMMATRIX P = _camera.Proj();

	Matrix m = P;
	// Compute picking ray in view space.
	float vx = (+2.0f * sx / _clientWidth - 1.0f) / m(0, 0); // P(0, 0);
	float vy = (-2.0f * sy / _clientHeight + 1.0f) / m(1, 1); // P(1, 1);

	// 뷰좌표계에서 광선정의
	XMVECTOR rayOrigin = ::XMVectorSet(0.0f, 0.0f, 0.0f, 1.0f);
	XMVECTOR rayDir = ::XMVectorSet(vx, vy, 1.0f, 0.0f);

	// 광선을 로컬좌표로 변환
	XMMATRIX V = _camera.View();
	XMVECTOR D1 = ::XMMatrixDeterminant(V);
	XMMATRIX invView = ::XMMatrixInverse(&D1, V);

	XMMATRIX W = ::XMLoadFloat4x4(&_meshWorld);
	XMVECTOR D2 = ::XMMatrixDeterminant(W);
	XMMATRIX invWorld = ::XMMatrixInverse(&D2, W);

	XMMATRIX toLocal = ::XMMatrixMultiply(invView, invWorld);

	rayOrigin = ::XMVector3TransformCoord(rayOrigin, toLocal);
	rayDir = ::XMVector3TransformNormal(rayDir, toLocal);

	// Make the ray direction unit length for the intersection tests.
	rayDir = ::XMVector3Normalize(rayDir);

	// If we hit the bounding box of the Mesh, then we might have picked a Mesh triangle,
	// so do the ray/triangle tests.
	//
	// If we did not hit the bounding box, then it is impossible that we hit 
	// the Mesh, so do not waste effort doing ray/triangle tests.

	// Assume we have not picked anything yet, so init to -1.
	_pickedTriangle = -1;
	float tmin = 0.0f;

	if (_meshBox.Intersects(rayOrigin, rayDir, tmin))
	{
		// Find the nearest ray/triangle intersection.
		tmin = MathHelper::Infinity;
		for (UINT i = 0; i < _meshIndices.size() / 3; ++i)
		{
			// Indices for this triangle.
			UINT i0 = _meshIndices[i * 3 + 0];
			UINT i1 = _meshIndices[i * 3 + 1];
			UINT i2 = _meshIndices[i * 3 + 2];

			// Vertices for this triangle.
			XMVECTOR v0 = ::XMLoadFloat3(&_meshVertices[i0].pos);
			XMVECTOR v1 = ::XMLoadFloat3(&_meshVertices[i1].pos);
			XMVECTOR v2 = ::XMLoadFloat3(&_meshVertices[i2].pos);

			// We have to iterate over all the triangles in order to find the nearest intersection.
			float t = 0.0f;

			if (TriangleTests::Intersects(rayOrigin, rayDir, v0, v1, v2, t))
			{
				if (t < tmin)
				{
					// 가장 가까운 삼각형체크
					tmin = t;
					_pickedTriangle = i;
				}
			}
		}
	}
}

 

오늘은 Instancing과 Culling에 대해 복습해보고 예제코드를 분석해보자

 

우선 Instancing이 왜 필요할까에 대해 생각해보자. 각각의 오브젝트를 개별로 그려준다고 했을 때, 똑같은 오브젝트가 있더라도 다른 오브젝트가 그려주고 다시 똑같은 오브젝트를 그려준다고 하면 그려주기 위한 비용이 다시 생기기 때문에

드로우콜이 많이 발생한다. 효율적으로 그려주기 위해서는 같은 물체라면 한번에 다 그려주고 다른 오브젝트를 그려주는 것이 좋다. 이때 같은 물체라는 것은 같은 쉐이더와 머테리얼로 그려주는 물체를 의미한다.

 

우선 예제코드를 실행시켜보자. 실행화면 위쪽에 보면 125개의 물체 중에 13개만 보이고 있다는 것을 알 수 있다. 여기서 만약 2번을 눌러주면 인스턴싱모드가 꺼지면서 125개가 다 그려지며 프레임이 낮아지는 것을 볼 수 있다. 이때 13개가 보인다는 것은 컬링과 관련이 있다.

 

이때 같은 물체에서 달라지는 부분은 position과 같은 부분으로 이 연산은 쉐이더 코드의 VS부분의 구조체를 보면 된다. 아래에  변수가 VS단계에 입력으로 들어오는 부분에 인스턴싱관련된 부분이다.

struct VertexIn
{
    float3 PosL     : POSITION;
    float3 NormalL  : NORMAL;
    float2 Tex      : TEXCOORD;
    // 인스턴싱
    row_major float4x4 World  : WORLD;
    float4 Color    : COLOR;
    uint InstanceId : SV_InstanceID;
};

 

코드 상에서는 Vertex부분에 쉐이더코드에 맞게 묘사해주도록 변수가 맞춰져있다.

typedef struct D3D11_INPUT_ELEMENT_DESC
{
    LPCSTR SemanticName;
    UINT SemanticIndex;
    DXGI_FORMAT Format;
    UINT InputSlot;			//인스턴싱일때 구분해줘야함
    UINT AlignedByteOffset;
    D3D11_INPUT_CLASSIFICATION InputSlotClass;
    UINT InstanceDataStepRate;
} 	D3D11_INPUT_ELEMENT_DESC;
    
static ComPtr<ID3D11InputLayout> InstancedBasic32;
    
const D3D11_INPUT_ELEMENT_DESC InputLayoutDesc::InstancedBasic32[8] =
{
	{"POSITION", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 0, D3D11_INPUT_PER_VERTEX_DATA, 0},
	{"NORMAL",   0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 12, D3D11_INPUT_PER_VERTEX_DATA, 0},
	{"TEXCOORD", 0, DXGI_FORMAT_R32G32_FLOAT, 0, 24, D3D11_INPUT_PER_VERTEX_DATA, 0},
	{ "WORLD", 0, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 0, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "WORLD", 1, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 16, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "WORLD", 2, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 32, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "WORLD", 3, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 48, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "COLOR", 0, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 64,  D3D11_INPUT_PER_INSTANCE_DATA, 1 }
};

 

이때 D3D11_INPUT_PER_INSTANCE_DATA 뒤에 나오는 1이라는 수는 instance data step이라는 옵션으로 instance별 자료 원소 하나당 그릴 instance의 개수이다. 이렇게 묘사해준 값을 IA단계에서 넘겨줘야한다. IASetVertexBuffers에서 2번째 매개변수를 2로 설정해주고 있는 것을 볼 수 있다. 이 2는 2가지 값을 넘겨주고 있다는 것인데 이 2가지 값은 SkullVertexBuffer와 InstanceBuffer이다.

이렇게 해준다음 마지막에 DrawIndexedInstanced로 그려주면 된다. 이때 몇개를 그려줄지에 대한 값도 넘겨줘야한다.

ID3D11Buffer* vbs[2] = { _skullVB.Get(), _instancedBuffer.Get() };

_deviceContext->IASetVertexBuffers(0, 2, vbs, stride, offset);
_deviceContext->IASetIndexBuffer(_skullIB.Get(), DXGI_FORMAT_R32_UINT, 0);

_deviceContext->DrawIndexedInstanced(_skullIndexCount, _visibleObjectCount, 0, 0, 0);

이때 InstanceBuffer를 묘사해주는 부분을 가보면 InstanceData를 통해 데이터를 채워주고 이 값에 따라 InstanceBuffer를 채워준다.

void InstancingAndCullingDemo::BuildInstancedBuffer()
{
	const int32 n = 5;
	_instancedData.resize(n * n * n);

	float width = 200.0f;
	float height = 200.0f;
	float depth = 200.0f;

	float x = -0.5f * width;
	float y = -0.5f * height;
	float z = -0.5f * depth;
	float dx = width / (n - 1);
	float dy = height / (n - 1);
	float dz = depth / (n - 1);

	for (int k = 0; k < n; ++k)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				// Position instanced along a 3D grid.
				_instancedData[k * n * n + i * n + j].World = XMFLOAT4X4(
					1.0f, 0.0f, 0.0f, 0.0f,
					0.0f, 1.0f, 0.0f, 0.0f,
					0.0f, 0.0f, 1.0f, 0.0f,
					x + j * dx, y + i * dy, z + k * dz, 1.0f);

				// Random color.
				_instancedData[k * n * n + i * n + j].Color.x = MathHelper::RandF(0.0f, 1.0f);
				_instancedData[k * n * n + i * n + j].Color.y = MathHelper::RandF(0.0f, 1.0f);
				_instancedData[k * n * n + i * n + j].Color.z = MathHelper::RandF(0.0f, 1.0f);
				_instancedData[k * n * n + i * n + j].Color.w = 1.0f;
			}
		}
	}

	D3D11_BUFFER_DESC vbd;
	vbd.Usage = D3D11_USAGE_DYNAMIC;
	vbd.ByteWidth = sizeof(InstancedData) * _instancedData.size();
	vbd.BindFlags = D3D11_BIND_VERTEX_BUFFER;
	vbd.CPUAccessFlags = D3D11_CPU_ACCESS_WRITE;
	vbd.MiscFlags = 0;
	vbd.StructureByteStride = 0;

	HR(_device->CreateBuffer(&vbd, 0, _instancedBuffer.GetAddressOf()));
}

 

 Rasterizer에서 실행되는 것으로 영역에서 벗어난 부분이라면 보이지 않게 하는 데 이 부분에서 컬링이 실행되긴한다.

하지만 그 앞 단계까지에서 그려줄 애들은 이미 계산을 해준 상태이기 때문에 만약 안그려줘도 되는 아이라면 CPU단에서 처리해주는 것이 효율적일 것이다. 이를 해주는 것이 절두체 컬링(Frustum Culling)이다.

 

아래 코드를 보면 2개의 변수가 각각 해골이 그려져있는 영역과 카메라의 절두체 영역으로 절두체 컬링을 위한 것이다. 

//해골 영역
BoundingBox _skullBox;
//절두체 영역
BoundingFrustum _camFrustum;

 

이를 통해 카메라의 절두체 안에 있는지 체크하고 만약 있다면 그려주는 코드는 UpdateScene에 있다.

void InstancingAndCullingDemo::UpdateScene(float dt)
{
if (_frustumCullingEnabled)
{
	XMVECTOR detView = XMMatrixDeterminant(_camera.View());
	XMMATRIX invView = XMMatrixInverse(&detView, _camera.View());

	D3D11_MAPPED_SUBRESOURCE mappedData;
	_deviceContext->Map(_instancedBuffer.Get(), 0, D3D11_MAP_WRITE_DISCARD, 0, &mappedData);

	InstancedData* dataView = reinterpret_cast<InstancedData*>(mappedData.pData);

	for (uint32 i = 0; i < _instancedData.size(); ++i)
	{
		XMMATRIX W = ::XMLoadFloat4x4(&_instancedData[i].World);
		XMVECTOR D = ::XMMatrixDeterminant(W);
		XMMATRIX invWorld = ::XMMatrixInverse(&D, W);

		// View space to the object's local space.
		XMMATRIX toLocal = ::XMMatrixMultiply(invView, invWorld);

		// Decompose the matrix into its individual parts.
		XMVECTOR scale;
		XMVECTOR rotQuat;
		XMVECTOR translation;
		::XMMatrixDecompose(&scale, &rotQuat, &translation, toLocal);

		// Transform the camera frustum from view space to the object's local space.
		BoundingFrustum localspaceFrustum;

		_camFrustum.Transform(localspaceFrustum, XMVectorGetX(scale), rotQuat, translation);
		//XNA::TransformFrustum(&localspaceFrustum, &_camFrustum, );

		// 그려줘야하는지 체크
		if (localspaceFrustum.Contains(_skullBox))
		{
			// Write the instance data to dynamic VB of the visible objects.
			dataView[_visibleObjectCount++] = _instancedData[i];
		}
	}

	_deviceContext->Unmap(_instancedBuffer.Get(), 0);
}
}

 

절두체 판단에서는 한면에 대해서 이 물체가 절두체 이전에 있는지 이후에 있는지를 통해 그려주는지 판단해주고 이를 6면에 대해서 해주면 된다. 이 중에 하나라도 통과하지 못하면 그려주지 않는다.


Tessellation영역은 파이프라인에서 Hull Shader,Tessellator, Domain Shader를 합친 것이다. 이때 Hull Shader와 Domain Shader는 쉐이더 코드를 통해 사용할 수 있고 Tessellator는 옵션을 통해 사용해줄 수 있다.

 

Tessellatoion은 기하 구조를 더 작은 삼각형들로 분할하고 새로 생긴 정점들의 위치를 적절한 방식으로 조절해주는 것이다. 주로 지형 지물, 터레인에서 많이 사용되고 특히 GPU에서의 LOD(멀수록 퀄리티 떨어져 보임)연산에서 연관이 많다.

 

이 Tessellatoion을 사용할 때는 삼각형을 매개변수로 사용하는 것이 아닌 D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST 이런 변수를 입력으로 받는다. 이것은 4개의 제어점으로 이것을 분할해서 사용하는 것이다. Tessellation은 이 제어점을 기준으로 하는 패치가 기본 단위로 연산이 이루어 진다.

예제코드를 실행하게 되면 멀어질수록 삼각형이 적어지고 가까이 갈수록 삼각형의 개수가 많아져서 세밀하게 보이게 된다.

 

쉐이더 코드를 살펴보면 기존의 VS와 PS단계에서 추가된 코드를 볼 수 있다. 우선 Hull Shader 코드에서  각 Tessellation의 기본 단위인 패치마다 실행되는 ConstantHS 단계를 먼저 살펴보자. 이 단계에서 얼마나 더 세분화해줄 지에 관련된 계수를 출력해준다. 이 계수에 해당하는 변수는 각 변의 세분정도를 나타내는 EdgeTess와 내부의 분할정도를 나타내는 InsideTess가 있다.

struct PatchTess
{
	float EdgeTess[4]   : SV_TessFactor;
	float InsideTess[2] : SV_InsideTessFactor;
};

PatchTess ConstantHS(InputPatch<VertexOut, 4> patch, uint patchID : SV_PrimitiveID)
{
	PatchTess pt;

	//거리계산 - 패치들의 평균값
	float3 centerL = 0.25f * (patch[0].PosL + patch[1].PosL + patch[2].PosL + patch[3].PosL);
	float3 centerW = mul(float4(centerL, 1.0f), gWorld).xyz;

	//패치들과 카메라간의 거리 파악
	float d = distance(centerW, gEyePosW);


	//20(최소)~100(최대)사이
	const float d0 = 20.0f;
	const float d1 = 100.0f;
	float tess = 64.0f * saturate((d1 - d) / (d1 - d0));

	//각 변의 세분정도
	pt.EdgeTess[0] = tess;
	pt.EdgeTess[1] = tess;
	pt.EdgeTess[2] = tess;
	pt.EdgeTess[3] = tess;

	//내부의 분할정도
	pt.InsideTess[0] = tess;
	pt.InsideTess[1] = tess;

	return pt;
}

 

이 다음 단계는 출력하는 제어점마다 한번씩 실행되는 HS 단계로 표면을 어떻게 표현할지를 정해준다. 현재는 그냥 통과 시켜주고 있지만 설정해줄 수 있는 부분이 많다.

struct HullOut
{
	float3 PosL : POSITION;
};

[domain("quad")]
[partitioning("integer")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(4)]
[patchconstantfunc("ConstantHS")]
[maxtessfactor(64.0f)]
//출력하는 제어점마다 한번씩- 표면
HullOut HS(InputPatch<VertexOut, 4> p,
	uint i : SV_OutputControlPointID,
	uint patchId : SV_PrimitiveID)
{
	HullOut hout;

	hout.PosL = p[i].PosL;

	return hout;
}

 

그 다음이 Tessellator 단계이다. 이 단계에서는 쉐이더에서 정해준 값에 따라 분할이 일어나는 단계로 GPU가 해주는 작업이고 Domain shader단계로 넘어가게 된다. 이 단계에서는 동적으로 생성과 기존 정점의 행렬연산을 해주게 된다. Tesselation의 VS단계라고 보면 된다.

struct DomainOut
{
	float4 PosH : SV_POSITION;
};

// The domain shader is called for every vertex created by the tessellator.  
// It is like the vertex shader after tessellation.
[domain("quad")]
DomainOut DS(PatchTess patchTess,
	float2 uv : SV_DomainLocation,
	const OutputPatch<HullOut, 4> quad)
{
	DomainOut dout;

	// Bilinear interpolation.
	float3 v1 = lerp(quad[0].PosL, quad[1].PosL, uv.x);
	float3 v2 = lerp(quad[2].PosL, quad[3].PosL, uv.x);
	float3 p = lerp(v1, v2, uv.y);

	// Displacement mapping
	p.y = 0.3f * (p.z * sin(p.x) + p.x * cos(p.z));

	dout.PosH = mul(float4(p, 1.0f), gWorldViewProj);

	return dout;
}

 

Tesselation은 GS단계와 비슷하지만 하나의 물체가 있는 상태에서 분할하는 느낌이고 GS단계는 별도의 물체를 생성할 수도 있는 느낌이라고 생각하면 된다. GS는 파티클이나 빌보드에 많이 사용되고 Tesselation은 Terrain같은 지형지물에 많이 사용한다.

https://www.acmicpc.net/problem/1463

 

세가지 연산을 적절히 사용해서 최소 연산 수를 통해 1로 만드는 연산을 해야하는데 이때 점화식을 만들어서 해보자.

우선 1을 뺐을때와 2로 나눴을때 3으로 나눴을때의 연산 수 비교해서 최소값 배열을 2부터n까지 계산해두고 필요한 수를 꺼내서 사용하면 된다.

 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int>dp(n + 1);

	dp[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		//우선 1빼보기
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)
		{
			//1뺐을때와 2로 나누었을때 비교
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
		if (i % 3 == 0)
		{
			//1뺐을때와 3로 나누었을때 비교
			dp[i] = min(dp[i], dp[i / 3] + 1);
		}
	}

	cout << dp[n];
}

https://www.acmicpc.net/problem/1932

 

 

삼각형을 2차원 벡터를 통해 입력받고 이 벡터와 크기가 같은 벡터를  선언해주고 이 벡터에 누적합을 계산해서 넣어주면 된다. 이때 현재 층에서 내려갈 때 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서 선택해서 내려가야하는데  내려가있는 입장에서 생각해보면 경우를 나눠서 계산을 해줘야한다.

가장 왼쪽의 경우에는 x-1, y 위치의 원소에 자신의 값을 더해주면 된다.

가장 오른쪽의 경우에는 x-1, y-1 위치의 값에 자신의 값을 더해주면 된다.

가운데의 경우에는  x-1,y-1 와 x-1,y위치 중에 큰 값과 자신의 값을 저해주면 된다.

마지막행에서 최대값을 찾아서 출력해주면 된다.

 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> triangle(n, vector<int>(n, 0));


	for (int i = 0; i < n; i++)
	{
		for (int j =0; j<=i; j++)
		{
			cin >> triangle[i][j];
		}
		
	}
	
	vector<vector<int>> dp(n, vector<int>(n, 0));

	dp[0][0] = triangle[0][0];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			//가장 왼쪽
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i)	//가장 오른쪽
			{
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else      //가운데
			{
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		result = max(dp[n - 1][i], result);
	}

	cout << result << "\n";
}

https://www.acmicpc.net/problem/1149

 

먼저 모든 집의 RGB에 해당하는 비용 값을 벡터를 통해 입력받고 n-1까지의 합벡터를 채워주면 되는데 이때 RGB를 더할 때 문제에서 각 집을 칠할 때 이전 집과 같은 색을 사용할 수 없으므로, 이 조건을 만족하며 비용을 최소화하는 선택만을 하도록 하여 자신을 제외한 이전에 계산된 비용중에서 최소값과 자신의 비용을 더한 것이 현재 위치의 합 배열이 값으로 계산해주면 된다.

 

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> cost(n, vector<int>(3));
	vector<vector<int>> dp(n, vector<int>(3));

	//RGB입력받기
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}

	// 첫 번째 집 초기화
	dp[0][0] = cost[0][0];
	dp[0][1] = cost[0][1];
	dp[0][2] = cost[0][2];

	//미리 모든 경우의수 계산
	for (int i = 1; i < n; i++)
	{
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
	}

	int result = min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
	cout << result << endl;

	return 0;
}

 

https://www.acmicpc.net/problem/1012

 

 

케이스 수만큼 반복을 해주는데 이때 그래프 크기를 입력받고 이에 맞게 assign함수를 통해 벡터를 m,n의 크기로 초기화해주고 배추가 있는 부분만 1로 수정해준다. 그리고 그래프를 전체 순회하면서 1인부분을 만난다면 BFS방식으로 순회하면서 방문처리를 해준다. 그리고 모두 방문처리가 완료되면 true를 반환해서 result값을 1 더해주고 이 result에 1이 몇번 더해졌는지 출력해주면 된다. 

 

정답코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
bool BFS(int x, int y);
vector<vector<int>> graph;
vector < vector<bool> >visited;
int main()
{
	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		m = 0, n = 0;
		int k;

		cin >> m >> n >> k;

		graph.assign(m, vector<int>(n, 0));
		visited.assign(m, vector<bool>(n, false));

		//배추 입력
		for (int i = 0; i < k; i++)
		{
			int X, Y;
			cin >> X >> Y;

			graph[X][Y] = 1;
		}

		int result = 0;

		//그래프 순회
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (graph[i][j] == 1 && !visited[i][j])
				{
					if (BFS(i, j)) result++;
				}
			}
		}

		cout << result << "\n";
	}
}

bool BFS(int x, int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[x][y] = true;

	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n)
			{
				if (graph[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					visited[next_x][next_y] = true;
					q.push({ next_x,next_y });
				}
			}
		}
	}

	return true;
}

+ Recent posts